|
|
Stony Brook Parallel Programming ProjectIn this paper we present a new class of equational/functional programs known as path
sequential systems that are natural for parallel evaluation. In particular, searching
for needed redices is done with minimal and ``regular'' inter-processor communication.
Even if the input program is not path sequential, it can be so transformed easily. We then
describe the opportunities for parallelism in functional programs through examples. The
known sequential algorithms for normalization, when extended for parallel evaluation, do
not lead to any significant parallelism in practice since they detect very few needed
redexes at any time. Hence we develop a method for analyzing the program to discover many
more needed redexes. This information is then used at run time to extract almost all the
parallelism in the program. In order to effectively utilize the parallelism extracted by
our analysis procedure, the parallel tasks (i.e., normalization of portions of input term)
should be distributed among the processors in such a way as to maximize concurrency while
minimizing inter-processor communication. Since the tasks are created dynamically, the
distribution (also known as load balancing) algorithm must also be dynamic. We describe
analysis techniques that yield information on whether a task is to be executed
locally or on a remote processor, and in the latter case how to choose the remote
processor. We also develop techniques to detect a class of functions called pipeline
functions to effectively utilize the parallelism they offer. |
|
Maintained by Sekar, sekar@cs.sunysb.edu |