Parallel contractions of grids for task assignment to processor networks
Ron Ben‐Natan, Amnon Barak · Networks · 1992
Abstract LetGbe a simple connected undirected graph. A contraction φ ofGis a mapping fromG=G(V, E)toG'=G'(V', E'), whereG'is also a simple connected undirected graph, such that ifu, vφV(G)are connected by an edge (adjacent) inG, then either φ(u)= φ(v) orφ(u)and φ(v)are adjacent inG'. Consider a family of contractions, called bounded contractions, in which ∀v'∈V', the degree ofv'inG', DegG'(v'), satisfiesDegG'(v')≤ |φ−1(v')|, where φ−1(v')denotes the set of vertices inGmapped tov'under φ. 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 graphs is identical to that of the desired target graph. We also prove that some contractions are not possible, regardless of their degree.