Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems

We study two parallel scheduling problems and their use in designing parallel algorithms. First, we define a novel scheduling problem; it is solved by repeated, rapid, approximate reschedulings. This leads to a first optimal PRAM algorithm for list ranking, which runs in logarithmic time. Our second scheduling result is for computing prefix sums of logn bit numbers. We give an optimal parallel algorithm for the problem which runs in sublogarithmic time. These two scheduling results together lead to logarithmic time PRAM algorithms for the connectivity, biconnectivity and minimum spanning tree problems. The connectivity and biconnectivity algorithms are optimal unless m = o(nlog*n), in graphs of n vertices and m edges.

Authors

• Richard Cole 0001
• Uzi Vishkin

Keywords

• Tree graphs
• Phase change random access memory
• Parallel algorithms
• Processor scheduling
• Algorithm design and analysis
• Scheduling algorithm
• Partitioning algorithms
• Protocols
• Concurrent computing
• Computational modeling
• Optimization Algorithm
• Ranked List
• Log Time
• Parallel Algorithm
• Scheduling Results
• Total Weight
• Operation Time
• Active Clusters
• Head And Tail
• Actual Input
• End Of Step
• Array Size
• Binary Tree
• Executive Order
• Cluster C
• Collection Size
• List Of Nodes
• Incident Edges
• Proof Of Claim
• Head Node
• Edge Selection
• Successive Nodes
• List Of Clusters
• Running Time
• Incomplete Block