Multiple Graph Embeddings into a Processor Array with Spanning Buses |
| |
| Affiliation: | 1. Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel;2. School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, United States;3. Department of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel;1. Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA 94720, USA;2. Helen Wills Neuroscience Institute, University of California, Berkeley, Berkeley, CA 94720, USA;3. UCB/UCSF Joint Graduate Program in Bioengineering, University of California, Berkeley, Berkeley, CA 94720, USA;1. Mathematics Department, United States Naval Academy, Annapolis, MD, USA;2. School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand;3. Department of Mathematics, Louisiana State University, Baton Rouge, LA, USA |
| |
| Abstract: | A processor array with spanning buses (PASB) is a well-known, versatile parallel architecture. A PASB is obtained from a two-dimensional mesh by replacing each linear connection with a bus. In this paper, we show how to optimally embed multiple copies of a graph into a PASB by a labeling strategy. Our embeddings simultaneously achieve an optimal expansion, congestion, and alignment cost. First, we propose a labeling scheme for anN-node graphG, possibly disconnected, such that this labeling makes it possible to optimally embed multiple copies ofGinto anN′×N′ PASB whereN′ is divisible byN. Second, we show that many important classes of graphs admit this labeling: for example, tree, cycle, mesh of trees, and product graphs such as mesh, torus, or hypercube. Finally, we show how to optimally embed multiple copies of a graph into a multidimensional and possibly nonsquare PASB. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
