EFFICIENT PARALLEL DIVIDE-AND-CONQUER FOR A CLASS OF INTERCONNECTION TOPOLOGIES

被引:0
|
作者
WU, IC [1 ]
机构
[1] CARNEGIE MELLON UNIV,SCH COMP SCI,PITTSBURGH,PA 15213
关键词
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
In this paper, we propose an efficient scheduling algorithm for expanding any divide-and-conquer (D&C) computation tree on k-dimensional mesh, hypercube, and perfect shuffle networks with p processors. Assume that it takes t(n) time steps to expand one node of the tree and t(c) 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 (N/p + h)t(n) + phidht(c) time steps, where phi is O(log2 p) on a hypercube or perfect shuffle network and is O(k square-root p on a n(k-1) x ... x n0 mesh network, where n(k-1) = ... = n0 = k square-root p. 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 N much greater than ph(1 + phidt(c)/t(n)).
引用
收藏
页码:229 / 240
页数:12
相关论文
共 50 条
  • [31] Divide-and-Conquer Fusion
    Chan, Ryan S. Y.
    Pollock, Murray
    Johansen, Adam M.
    Roberts, Gareth O.
    JOURNAL OF MACHINE LEARNING RESEARCH, 2023, 24
  • [32] HEADINGS, OR DIVIDE-AND-CONQUER
    DOLLE, R
    JOURNAL OF ENVIRONMENTAL HEALTH, 1990, 53 (03) : 56 - 56
  • [33] MULTIDIMENSIONAL DIVIDE-AND-CONQUER
    BENTLEY, JL
    COMMUNICATIONS OF THE ACM, 1980, 23 (04) : 214 - 229
  • [34] Space-efficient geometric divide-and-conquer algorithms
    Bose, Prosenjit
    Maheshwari, Anil
    Morin, Pat
    Morrison, Jason
    Smid, Michiel
    Vahrenhold, Jan
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2007, 37 (03): : 209 - 227
  • [35] An Efficient Divide-and-Conquer Cascade for Nonlinear Object Detection
    Lampert, Christoph H.
    2010 IEEE CONFERENCE ON COMPUTER VISION AND PATTERN RECOGNITION (CVPR), 2010, : 1022 - 1029
  • [36] Divide-and-conquer mapping of parallel programs onto hypercube computers
    Lor, S
    Shen, H
    Maheshwari, P
    JOURNAL OF SYSTEMS ARCHITECTURE, 1997, 43 (6-7) : 373 - 390
  • [37] A divide-and-conquer method with approximate Fermi levels for parallel computations
    Takeshi Yoshikawa
    Hiromi Nakai
    Theoretical Chemistry Accounts, 2015, 134
  • [38] A parallel symmetric block-tridiagonal divide-and-conquer algorithm
    Bai, Yihua
    Ward, Robert C.
    ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2007, 33 (04):
  • [39] A PARALLEL DIVIDE-AND-CONQUER ALGORITHM FOR FINDING MINIMUM ENERGY TRAJECTORIES
    Leandro, Carlos
    Ambrosio, Jorge
    PROCEEDINGS OF THE 7TH INTERNATIONAL CONFERENCE ON MECHANICS AND MATERIALS IN DESIGN (M2D2017), 2017, : 155 - 156
  • [40] Automated transformation of sequential divide-and-conquer algorithms into parallel programs
    Freisleben, B
    Kielmann, T
    COMPUTERS AND ARTIFICIAL INTELLIGENCE, 1995, 14 (06): : 579 - 596