HPC Project 2: The Master-Worker & Message-Passing Patterns

This week's assignment is a fairly simple project to give you practice using the master-worker and message-passing patterns. The assignment is to write a program that sends a message around a ring of processes, using the master-worker and message-passing patterns. More precisely:

• The master process (i.e., rank 0) should:
  1. Record the starting time.
  2. Create a message containing its rank.
  3. Send that message to the next process (i.e., with rank 1),
  4. Receive a message from the last worker process (i.e., with rank n-1), and
  5. Print the message received to the screen, along with the time required for the message to traverse the ring.
• Each worker process should:
  1. Receive a message from the process "before" it in the ring (i.e., rank i-1),
  2. Create a new message consisting of the message just received, followed by a space, followed by their rank (e.g., i), and
  3. Send this new message on to the next process (i.e., with rank i+1), using the modulus operation to "wrap around" from the last worker to the master.

      0 1 2 3 4 5 6 7
      time: 0.15324 secs

In the CS labs:

1. Write your program and test it using different arguments for the -np switch, so that you are confident it works correctly before continuing.

2. Using the MPI_Wtime() function, add code that causes the master process to calculate how long it takes the message to circulate around the "ring". Have the master output the message it receives and the time, but do not include any I/O operations in your timing -- your timing should just measure how long it takes to transmit the message around the ring.

3. Since you are competing for network bandwidth and CPU cycles with others in the lab, this time may vary significantly from execution to execution, even using the same number of processes.

   To try to compensate for this variance, run your program 3 times for a given number of processes. In a spreadsheet, record these times; then use the spreadsheet to compute both the average and variance of the 3 trip-time measurements. Use this procedure to test, record, and determine the average and variance of the times for rings of 4, 8, 16, 32, 64, 128, and 256 processes. (Don't use a calculator--use the spreadsheet functions to calculate these averages and variance values!)

   Be careful to only compute the time it takes the message to traverse the ring -- your master should only time the interval between sending its message and receiving its message.

On The Cluster:

1. Transfer your program to the cluster (borg). Make a copy of the Makefile you used last week, modify it to work with this week's program, and then use it to compile your program.
2. Repeat the timing experiments you performed in the CS lab, recording 3 trip-times around the ring for rings of 4, 8, 16, 32, 64, 128, and 256 processes.
3. For each different ring-size, use your spreadsheet to compute the average and variance of the three trip-times.

On Your Own:

In your spreadsheet, create a line-chart that plots the average times you computed for the CS Lab vs. on the cluster. The X-axis should be the number of processes; the Y-axis should be the time. Give your chart a descriptive title, be sure to label your axes (including any units), and include a legend that indicates which system each line represents in a way that will be clear on a gray-scale printer (e.g., use a solid line for one and a dashed line for the other). Your X-axis markers should be the actual values you used: 4, 8, 16, 32, 64, 128, and 256 processes.

Then create a second similar line-chart in which you plot the variances you computed for each ring-size, with the number of processes on the X-axis and the variance on the Y-axis.

Size both of these charts so that each will occupy an entire page when printed, so as to reveal as much detail as possible. If both lines are close together, experiment with using a log-scale for the Y-axis to see if that will increase the separation. If necessary, copy-paste these charts into a word-processing program for printing.

Hand In

1. A 1-page written analysis in which you interpret your line-charts and spreadsheet data, discussing both the averages and variances. Try to account for what you observe there; provide a hypothesis for why it is occurring, and cite evidence in support of your hypothesis, Make your analysis as quantitative as possible, citing actual values from the data you collected to support the statements you make.

   Compare the data you collected this week with what you collected last week. If you notice differences, quantify those differences and try to identify the reason for the difference.

   If you used AI in completing this project, attach an additional page in which you document your use of it, as described in the course policies.

2. Your two line-charts.
3. The spreadsheet data you used to create the line-charts.
4. A script file in which you cat your program, show that it compiles correctly, and then show it executing in the lab using 8 processes.
5. The Slurm .out file produced by one of your 8-process runs on the cluster.

CS > 374 > Exercises > 02 > Homework Project