On relaxed squashed embedding of graphs into a hypercube

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). The main objective here is to automate step (i). 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.