Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy

DOI10.1016/0020-0255(84)90033-1MaRDI QIDQ760204zbMATH OpenOpenAlexFDO

Authors Chuan Yi Tang, R. C. T. Lee

Publication date 1984

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(84)90033-1

zbMATH Keywords

design of parallel algorithms

Mathematics Subject Classification ID

Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Review text

We discuss how to design parallel algorithms based upon the divide-and- conquer strategy. We show that if we do not split the data too thoroughly, we may obtain a more cost-effective parallel algorithm. A theoretical result about how much we should split the data is also presented.

Recommendations

• scientific article; zbMATH DE number 3894470
• A data-parallel formulation for divide and conquer algorithms
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Fast algorithms through divide- and combine-and-conquer strategies
• scientific article; zbMATH DE number 5005293
• Optimizing Givens’ Algorithm for Multiprocessors
• Massive parallelization of divide-and-conquer algorithms over powerlists
• Efficient use of parallelism in algorithmic parameter optimization applications
• Paradigms for Fast Parallel Approximability

Cites work

• A Computing Machine Based on Tree Structures
• Applications of a Planar Separator Theorem
• Combinatorial solutions of multidimensional divide-and-conquer recurrences
• Divide and conquer for linear expected time
• Divide and Conquer Heuristics for Minimum Weighted Euclidean Matching
• Divide-and-Conquer for Parallel Processing
• scientific article; zbMATH DE number 3829220 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3705907 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Multidimensional divide-and-conquer
• Optimal Sorting Algorithms for Parallel Computers
• Two algorithms for constructing a Delaunay triangulation

Cited in

(13)

• An O(N log N) minimal spanning tree algorithm for N points in the plane
• Applications of a strategy for designing divide-and-conquer algorithms
• Using fewer processors to reduce time complexities of semigroup computations
• Massive parallelization of divide-and-conquer algorithms over powerlists
• Strategy-accurate parallel Buchberger algorithms
• A data-parallel formulation for divide and conquer algorithms
• scientific article; zbMATH DE number 5005293 (Why is no real title available?)
• Optimizing Givens’ Algorithm for Multiprocessors
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Pipelines for Divide-and-Conquer Functions
• scientific article; zbMATH DE number 1760062 (Why is no real title available?)
• How evenly should one divide to conquer quickly?
• A divide-and-conquer algorithm for constructing relative neighborhood graph

This page was built for publication: Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760204)