Write a SERIAL C++ program that determines the communication and computation pattern for the tree-based parallel reduction we discussed in class. Input the number of processors (or cores) 'p'. Generate random numbers in vector 'A' for the values stored at each processor (make 'A[i]' hold the value at processor 'i'). Lastly, output how the algorithm progresses and some statistics.
Restrict the 'A' values to be between 10 and 99, INCLUSIVE. Use a "uniform_int_distribution" in conjunction with a "minstd_rand" linear congruential engine, seeded with 0.
Input the number of processors 'p'. Assume 'p' is between 1 and 512, inclusive. It need NOT be a power of 2.
Use PRECISELY the format below with the EXACT same SPACING and SPELLING.
p ==> <UserInput>
For each stage, starting at 0, output the messages received and the computed sums. Finally, output the summary data shown below. The 'S' values are the partial sums. 'S[0]' should hold the global sum.
In the output, a line like "Recv: 0 from 1, v = 20, sum = 30" means processor 0 received a message from processor 1, the message contained the value 20 ('v'), and processor 0 computed the partial sum 30 ('sum').
The sample output assumes the user entered p = 8. Multiples of 10 are generated for 'A' so the computations can be more easily verified. Your output will be different because 'A' will be different.
Use PRECISELY the format shown below with the EXACT same SPACING and SPELLING.
Sample Output
p ==> 8 Stage 0 ------- Recv: 0 from 1, v = 20, sum = 30 Recv: 2 from 3, v = 40, sum = 70 Recv: 4 from 5, v = 60, sum = 110 Recv: 6 from 7, v = 80, sum = 150 Stage 1 ------- Recv: 0 from 2, v = 70, sum = 100 Recv: 4 from 6, v = 150, sum = 260 Stage 2 ------- Recv: 0 from 4, v = 260, sum = 360 Summary ======= A[] = [10, 20, 30, 40, 50, 60, 70, 80] S[] = [360, 20, 70, 40, 260, 60, 150, 80] # stages = 3 # adds = 7
Use at least three functions, excluding main. As always, use good design practices.
Submit a single C++ source file with an extension of ".cc". Ensure you seed the random number generator with 0.
You may NOT use the "pow" function as it's unnecessary.