Partitioning dependency graphs for concurrent execution: a parallel spreadsheet on a realistically modeled message passing environment
Andrew P. Wack · 1996
Effective partitioning of programs for parallel processing has become very important. We propose using spreadsheets as a convenient model and tool for parallel computation. We wish to create an easy way to exploit an existing parallel processing machine available to many people: the network of workstations. Using results from experiments with C-Linda on a network of workstations, we have developed a novel machine model that includes parameters representing the high overhead of starting a communication experienced in a message passing system. We use five parameters to characterize the cost of sending a message between two processors; communication start up time for the sender, time the sender takes to send each byte in the message, corresponding parameters for the receiver, and the transmission time per byte through the communication channel. A formula is presented for predicting these parameters under C-Linda, given workstation and network speed. A unique feature of this model is that it captures the time when the workstation is occupied during a communication event. We approach the problem of parallelizing spreadsheet programs as a matter of partitioning their dependency graphs. In this structure, nodes of the graph represent computations to be performed and the edges between the nodes represent the data dependencies between the computations. We consider the problem of finding an optimum partition of the dependency graph given the above model of communication. We examine various restrictions on the dependency graph, node weights, edge weights, and number of processors. Unlike most other work on this type of problem, ours takes into account the possible gain achieved when two or more communications are combined, thus eliminating some of the start up costs (latencies). We give a linear time algorithm for finding an optimum partition for a very restricted class of dependency graphs, which, however, includes many important cases. We further show that in many instances relaxing any one of the restrictions makes the problem NP-complete. We discuss heuristic extensions to our algorithm and show simulation results that demonstrate the superior performance of our algorithm over current heuristics.