Goals (ideal)
- Linear speedup: problem of a given size is solved N times faster on N processors
- Scalability: problem that is N times bigger is solved in the same amount of time
on N processors (usually more attainable)
Speedup is defined as the serial execution time divided by the parallel execution
time, for a given problem size and number of processors. Perfect or linear speedup
(generally not attainable) would equal the number of processors.
"Scalability" has become a bit of a buzzword and is often confused with speedup.
However, scalability actually looks at how speedup is preserved as the problem size
and number of processors increases. Generally, scalability is a more attainable
goal than near-linear speedup (though maintaining scalability to arbitrarily large
N is difficult).
Here are the ideal (read: unrealistic) characteristics of a program that achieves
maximum speedup and scalability:
- Each process has a unique bit of work to do
...and does not need to redo any other work in order to get its bit done
- Each process stores the unique data needed to accomplish its work
...and does not require anyone else's data
- Communication between processes is therefore largely unnecessary
- Load is balanced so that each process finishes at the same time
Usually it is much more complicated than this!
Goals (realistic)
Try to minimize the dependencies between processes. Two basic types:
- Functional dependencies - needing other processes to finish subtasks
- Data dependencies - communicating information between processes
Functional dependencies tend to lead to synchronization problems, while data dependencies
lead to delays simply due to the finite speed of communications between processes.
Realistically, the work being done by one process cannot be made entirely independent
of all the others. The goal is to try to divide up the work in such a way
that the dependencies are minimized. There is no set rule for determining how to
do this. It is problem dependent.
Choices
When determining how to parallelize your application, keep in mind that:
- There may be several parallel solutions to your problem.
- The best parallel solution or algorithm may not flow directly from the best serial
solution.
- Load balancing is an important criterion when choosing among methods.
The last point is important because you don't want to have processors waiting for
"slow finishers" at synchronization points.
