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 Ck 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.

-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 Ck 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.