Communication Complexity for Parallel Divide-and-Conquer

The relationship between parallel computation cost and communication cost for performing divide-and-conquer (D&C) computations on a parallel system of p processors is studied. The parallel computation cost is the maximal number of the D&C nodes that any processor in the parallel system may expand, whereas the communication cost is the total number of cross nodes (nodes generated by one processor but expanded by another processor). A scheduling algorithm is proposed, and lower bounds on the communication cost are derived. The proposed scheduling algorithm is optimal with respect to the communication cost, since the parallel computation cost of the algorithm is near optimal. >

Authors

• I-Chen Wu
• H. T. Kung 0001

Keywords

• Complexity theory
• Concurrent computing
• Costs
• Computational efficiency
• Scheduling algorithm
• Contracts
• Load management
• Computer science
• Processor scheduling
• Sorting
• Time Step
• Lower Bound
• Upper Bound
• Stage 2
• Parallelization
• Proof Of Theorem
• Tree Structure
• Tree Nodes
• Computational Load
• Wavefront
• First Search
• National Science Foundation
• Root Of The Tree
• Tree Height
• Time Of Stage
• Subtree
• Parallel System
• Communication Cost
• Load Balancing