Homework

Parallel Computing

Maximizing Workflow Parallelism While Managing Task Dependencies

A workflow consists of tasks that must be coordinated for optimum efficiency.

Baking an example of a workflow.
Find a good baking recipe (a recipe with a higher number of individual tasks is always better for
parallelization!).
Generate a table that contains a list of tasks and milestones necessary to bake your selected dish. The table should also list each tasks duration and dependencies. Use your creative skills for estimating task completion times.
Calculate the sequential execution time to complete your workflow.
Draw a parallel workflow (task dependency graph) for the baking recipe house in whatever format you prefer (e.g., PERT chart, Gantt chart, freehand drawing).
Determine the parallel execution time (or the critical path length).
Determine the maximum degree of concurrency/parallelism.
Determine the parallel speedup (or, the average degree of concurrency/parallelism).
Suppose you could add extra workers to shorten any duration (which is greater than 1) to 1, which task would you choose? Why was that task chosen?

Thanks.