Cornell Virtual Workshop > Parallel Programming Concepts and High Performance Computing > Introduction to Parallel Computation

Designing Workflows

Coordination work is unavoidable when multiple workers are involved, but you can organize your parallel workflow to limit the time spent communicating and coordinating. You can also design your workflow to accommodate larger inputs and additional workers so it is easier to scale up in the future.

Designing for parallel workers

Recall the card sorting example with independent parallel workers. Instead of collating the sorted results at the end, the manager could split the cards by color and assign each worker to sort one color. The workers would follow the same card sorting strategy, producing sorted stacks of same suit cards. The early partitioning strategy means that the workers' outputs are complete, sorted, same-suit piles. At the end of the workflow, no extra effort is required to combine the workers' outputs into a final result.

In this example, the manager splits the deck by color, so each worker only receives single-color cards. As in the previous example, each worker produces sorted output but strategically allocating data by color means that the worker results are easily combined to produce the final sorted output. — In this example, the manager splits the deck by color, so each worker only receives single-color cards. As in the previous example, each worker produces sorted output, but strategically allocating data by color means that each worker's' results are easily combined to produce the final sorted output.

While it does not make much difference with two workers, pre-partitioning the data saves substantial time as the number of workers increases (in this example). It would not take any extra time for the manager to split the cards by suit among four workers than to split the cards by color among two workers. The four workers would each have fewer cards to sort, and the results are just as easy to combine. When designing a parallel workflow, consider how the data you assign to your workers impacts their efficiency and the usefulness of their output.

A timeline of worker activity when the manager pre-divides the output by suit (without sorting). It shows a lane for each of the two workers and a lane for the manager. For the first interval of time, the manager is dividing the deck by suit while the workers wait. Next, both workers are active while the manager waits. Finally, when both workers have finished, the manager quickly stacks the output from the workers while the workers wait. — The manager's collating task is replaced by a splitting task before the card sorting and a stacking task after the sorting. The workflow could accommodate additional sorters with no change in strategy.

Suppose you needed to tackle a larger sorting problem. In that case, you might be able to use data partitioning and additional workers to sort the deck in parallel. Imagine a deck of cards with a thousand suits. If you had a thousand workers, you could still split the deck by suit and solve using the same strategy. As the size of the deck increases, the time to partition the deck also increases, so it would be worthwhile to parallelize the data partitioning process as well.

Back