Name
Abstract | ||
|---|---|---|
This paper presents novel embeddings of various classical topologies into the OPAM multicomputer. OPAM consists of a large number of processors that are connected by a two level, crossbar based interconnection network. The network combines a large, optical circuit-switched crossbar (reconfigurable network), with many small, packet-switching crossbars. The needed embedding is very different than the classical approaches. The goal in our case is to minimize routing decisions, so that communication requests can be satisfied by passing through two small crossbars. We show how to map parallel programs to this architecture using graph contraction notations. The family of parallel programs that we consider consists of multiple processes and communication links that are represented by connected, regular graphs such as rings, trees, two dimensional grids, cube connected cycles and hypercubes. In each case we show how to partition the vertex set of the program's graph to subsets, and how to assign each subset a cluster of processors in order to realize the topology of the given problem. In some of the cases we also prove that our partition and assignment algorithms are optimal. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1109/71.536941 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | Field | DocType |
multiprocessing systems,multiprocessor interconnection networks,network routing,parallel algorithms,parallel machines,parallel programming,reconfigurable architectures,OPAM multicomputer,assignment algorithms,classical communication topology embedding,communication links,connected regular graphs,cube connected cycles,graph contraction notations,hypercubes,multiple processes,optical circuit-switched crossbar,packet-switching crossbars,parallel program mapping,partition algorithms,processors,reconfigurable network,rings,routing decision minimization,scalable OPAM architecture,trees,two dimensional grids,two level crossbar based interconnection network,vertex set partitioning | Tree (graph theory),Computer science,Parallel algorithm,Parallel computing,Edge contraction,Network topology,Regular graph,Connectivity,Cube-connected cycles,Hypercube,Distributed computing | Journal |
Volume | Issue | ISSN |
7 | 9 | 1045-9219 |
Citations | PageRank | References |
6 | 0.56 | 22 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amnon Barak | 1 | 590 | 119.00 |
| Eugen Schenfeld | 2 | 296 | 38.01 |