Name
Abstract | ||
|---|---|---|
A conflict-free routing scheme is presented for a class of parallel and distributed computing systems. The core of the scheme is a quadtree communication structure. The quadtree structure suggests a general approach to mapping a class of parallel algorithms with intensive communication requirements for selecting data from many different sources and distributing data from a single source. By properly merging messages and efficiently replicating data, the quadtree structure can complete required communications in O(log4 M) parallel steps, where M is the network size. It is shown that the size of a quadtree communication structure can be contracted and stretched by adjusting the number of descendent nodes without affecting its conflict-free property. The relationship between the computation/communication ratio of various parallel algorithms and the number of tree levels is presented, and finally, their joint effect on the response time of combining and distributing data messages is examined. This analysis helps determine the optimal adaptation of the quadtree for minimizing the overall algorithm execution time |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1109/12.30864 | IEEE Trans. Computers |
Keywords | Field | DocType |
response time,multiprocessor interconnection networks,quadtree communication structure,distributed computing systems,multistage interconnection networks,parallel computing systems,mapping,various parallel algorithm,parallel step,parallel algorithms,data message,communication ratio,conflict-free routing scheme,parallel algorithm,conflict-free property,quadtree structure,tree levels,intensive communication requirement,distributed processing,computer network,distributed computing,data processing,switches,parallel processing,routing,merging,concurrent computing,community structure | Data processing,Parallel algorithm,Computer science,Parallel computing,Response time,Multistage interconnection networks,Execution time,Mathematical logic,Distributed computing,Computation,Quadtree | Journal |
Volume | Issue | ISSN |
38 | 8 | 0018-9340 |
Citations | PageRank | References |
3 | 0.44 | 11 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| W. Lin | 1 | 58 | 6.91 |
| T.-L. Sheu | 2 | 4 | 1.17 |
| Chita R. Das | 3 | 1046 | 45.21 |
| Tse-Yun Feng | 4 | 1167 | 374.72 |
| C.-L. Wu | 5 | 3 | 0.44 |