Mapping Divide-and-Conquer Algorithms to Parallel Architectures
| dc.contributor.author | Lo, V. | |
| dc.contributor.author | Rajopadhye, S. V. | |
| dc.contributor.author | Gupta, S. | |
| dc.contributor.author | Keldsen, D. | |
| dc.contributor.author | Mohamed, M. | |
| dc.contributor.author | Telle, Jan | |
| dc.date.accessioned | 2023-06-26T18:12:12Z | |
| dc.date.available | 2023-06-26T18:12:12Z | |
| dc.date.issued | 1990-01-19 | |
| dc.description | 24 pages | en_US |
| dc.description.abstract | In this paper, we identify the binomial tree as an ideal computation structure for parallel divide-and-conquer algorithms. We show its superiority to the classic full binary tree structure with respect to speedup and efficiency. We also present elegant and efficient algorithms for mapping the binomial tree to two interconnection networks commonly used in multicomputers, namely the hypercube and the two-dimensional mesh. Our mappings are optimal with respect to both average dilation and link contention. We discuss the practical implications of these results for message-passing architectures using store-and-forward routing vs. those using wormhole routing. | en_US |
| dc.identifier.uri | https://hdl.handle.net/1794/28442 | |
| dc.language.iso | en | en_US |
| dc.publisher | University of Oregon | en_US |
| dc.rights | Creative Commons BY-NC-ND 4.0-US | en_US |
| dc.subject | binomial tree | en_US |
| dc.subject | full binary tree structure | en_US |
| dc.subject | average dilation | en_US |
| dc.subject | link contention | en_US |
| dc.title | Mapping Divide-and-Conquer Algorithms to Parallel Architectures | en_US |
| dc.type | Article | en_US |