Paper Info
Title
Parallel Contractions Of Grids For Task Assignment To Processor Networks
Abstract
Let G be a simple connected undirected graph. A contraction phi of G is a mapping from G = G(V, E) to G' = G'(V', E'), where G' is also a simple connected undirected graph, such that if u, nu is-an-element-of V(G) are connected by an edge (adjacent) in G, then either phi(u) = phi(nu) or phi(u) and phi(nu) are adjacent in G'. Consider a family of contractions, called bounded contractions, in which for-all-nu' is-an-element-of V', the degree of nu' in G', Deg(G')(nu'), satisfies Deg(G')(nu') less-than-or-equal-to \phi-1(nu')\, where phi-1(nu') denotes the set of vertices in G mapped to nu' under phi. These types of contractions are useful in the assignment (mapping) of parallel programs to a network of interconnected processors, where the number of communication channels of each processor is small. In this paper, we are concerned with bounded contractions of two-dimensional grids such as mesh, hexagonal, and triangular arrays. For each of these graphs, we give contraction schemes that yield mappings of the minimal possible degree, such that the topology of the resulting graph is identical to that of the desired target graph. We also prove that some contractions are not possible, regardless of their degree.
Year
DOI
Venue
1992
10.1002/net.3230220605
NETWORKS
Field
DocType
Volume
Graph,Discrete mathematics,Mathematical optimization,Combinatorics,Bound graph,Vertex (geometry),Lattice (order),Hexagonal crystal system,Parallel processing,Grid,Mathematics,Bounded function
Journal
22
Issue
ISSN
Citations 
6
0028-3045
2
PageRank 
References 
Authors
0.92
5
2
Name
Order
Citations
PageRank
Ron Ben-Natan161.87
Amnon Barak2590119.00