About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Computing
Paper
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.