Monday May 12, 2014
A shared memory algorithm is an algorithm that uses multiple computational threads that perform tasks in parallel and can access the same data. Your task is to modify an existing serial algorithm to target shared memory.
The "Precipitate Algorithm Solution txt" below contains a serial algorithm for a model of precipitating particles. Your task is to modify this algorithm so that it can be executed by multiple threads working together at the same time. In particular, you should indicate:

1) For each step, whether the step should be executed by a single thread or a team of threads.
2) Where the synchronization points are, at which an individual thread cannot advance until the entire team reaches that point.
3) Which data needs to be kept private as opposed to shared.

Keep in mind that threads can access and write to the same shared memory, but that synchronization points should be used to make sure threads update this memory in the correct order; otherwise, the result is non-deterministic. Keep in mind also that threads can have blocks of private memory, into which no other threads can write.

Some steps cannot occur in parallel if there are dependencies between the steps. See the solution to a previous challenge problem for these:

A solution will look like the serial algorithm, annotated with notes about items 1, 2, and 3 above.
Show solution
Challenge Resources:
©1994-2022   |   Shodor   |   Privacy Policy   |   NSDL   |   XSEDE   |   Blue Waters   |   ACM SIGHPC   |   feedback  |   facebook   |   twitter   |   rss   |   youtube   |   XSEDE Code of Conduct   |   Not Logged In. Login