On relaxed squashed embedding of graphs into a hypercube
Journal
SIAM Journal on Computing
Journal Volume
18
Journal Issue
6
Pages
1226-1244
Date Issued
1989
Author(s)
Shin, Kang G.
Abstract
Task allocation in an n-dimensional hypercube (or an n-cube) multicomputer consists of two sequential steps: (i) determination of the size of the cube required to accommodate an incoming task composed of a set of interacting modules, and (ii) allocation of the task to a cube of the dimension determined from (i). Step (i) is usually done manually by the users, which is often difficult and leads to the underutilization of processors in an n-cube system. The main objective here is to automate step (i). Step (ii) has already been addressed in [ IEEE Trans. Comput., 36 (1987), pp. 1396–1407]. Each incoming task is represented by a graph in which each node denotes a module of the task and each link represents the need of intermodule communication. Each module must be assigned to a subcube in such a way that node adjacencies in the associated task graph are preserved. This assignment problem is called the relaxed squashed (RS) embedding of a graph, and the minimal dimension of a cube required for a given graph is termed the weak cubical dimension of the graph. Some mathematical properties of the RS embedding are derived first. In light of these mathematical properties, fast algorithms are developed to RS embed task graphs. A heuristic function for the $A^ * $ search algorithm is also derived to determine the weak cubical dimension of a graph.
Type
journal article