Efficient parallel divide-and-conquer for a class of interconnection topologies

I-Chen Wu*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

In this paper, we propose an efficient scheduling algorithm for expanding any divide-and-conquer (D&C) computation tree on k-dimensional mesh, hypcrcube, and perfect shuffle networks with p processors. Assume that it takes in time steps to expand one node of the tree and tc time steps to transmit one datum or convey one node. For any D&C computation tree with N nodes, height h, and degree d (maximal number of children of any node), our algorithm requires at most (formula presented) time steps, where φ is O(log2 p) on a hypercube or perfect shuffle network and is (formula presented) on a (formula presented) mesh network, where (formula presented) This algorithm is general in the sense that it does not know the values of N, h, and d, and the shape of the computation tree as well, a priori. Most importantly, we can easily obtain a linear speedup by nearly a factor of p, especially when (formula presented).

Original languageEnglish
Title of host publicationISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings
EditorsR.C.T. Lee, Wen-Lian Hsu
PublisherSpringer Verlag
Pages229-240
Number of pages12
ISBN (Print)9783540549451
DOIs
StatePublished - 1 Jan 1991
Event2nd Annual International Symposium on Algorithms, ISA 1991 - Taipei, China
Duration: 16 Dec 199118 Dec 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume557 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd Annual International Symposium on Algorithms, ISA 1991
CountryChina
CityTaipei
Period16/12/9118/12/91

Fingerprint Dive into the research topics of 'Efficient parallel divide-and-conquer for a class of interconnection topologies'. Together they form a unique fingerprint.

Cite this