Description: Assumptions
There are p processors sorting n numbers.
Each processor begins with n=p numbers stored in the array x
All numbers are in the range 0 : : : M 1
When the sorting algorithm ends, each processors has a sorted list of numbers and for i < j every
number in processor i is less than every number in processor j
Each processor can compare two numbers and swap them (if necessary) in time .
Each machine can send data to one other machine at a time (but cannot send and receive at the same
time)
It takes + k= time to send k numbers to another machine
id speci es the identi er of the current machine
Local sort of k elements takes time approximately C k log2 k
Programming assignment (Due 4/20) Write a short program to estimate on the Linux Lab machines.
(This requires no parallelism)
Programming assignment (Due 4/20) Write a short program using MPI to estimate and in the
Linux Lab.
To Search:
- [log2] - boost-log, a cow artificially boost libr
File list (Check if you may need any files):
sorting.pdf
Download