We present the design of E-kernel, an embedding kernel on the Victor V256 message-passing partitionable multiprocessor, developed for the support of program mapping and network reconfiguration. E-kernel supports the embedding of a new network topology onto Victor's 2D mesh and also the embedding of a task graph onto the 2D mesh network or the reconfigured network. In the current implementation, the reconfigured network can be a line or an even-size ring, and the task graphs meshes or tori of a variety of dimensions and shapes or graphs with similar topologies. For application programs having these task graph topologies and that are designed according to the communication model of E-kernel, they can be run without any change on partitions connected by the 2D mesh, line, or ring. Further, E-kernel attempts the communication optimization of these programs on the different networks automatically, thus making both the network topology and the communication optimization attempt completely transparent to the application programs. Many of the embeddings used in E-kernel are optimal or asymptotically optimal (with respect to minimum dilation cost). The implementation of E-kernel translated some of the many theoretical results in graph embeddings into practical tools for program mapping and network reconfiguration in a parallel system. E-kernel is functional on Victor V256. Measurements of E-kernel's performance on V256 are also included.>

Abstract Given an undirected 0‐1 flow network G with n nodes, Gomory and Hu's algorithm solves the multiterminal maximum flow problem by constructing a cut‐tree for G. Their algorithm requires solving n − 1 maximum flow problems. A perturbed network of G is a network generated from G by deleting or adding an edge to G. For a given network G and an edge (s, t) to be deleted from (resp., added to) G, a marginal cut‐tree T is a cut‐tree for G from which a cut‐tree for the perturbed network can be generated easily by reducing (resp., increasing) by 1 the weight of every edge in the path between s and t in T. Given an undirected 0‐1 flow network G, a cut‐tree for G, and an edge to be deleted from or added to G, we present an algorithm to generate a cut‐tree for the perturbed network by first transforming the given cut‐tree for G into a marginal cut‐tree and then transforming the marginal cut‐tree into a cut‐tree for the perturbed network. This algorithm also requires solving the maximum flow problem; depending on the input data, the number of such problems to be solved is between 0 and n − 2 for edge deletion and between 0 and n − 1 for edge addition. Properties on the input data that lead, respectively, to the best‐case and worst‐case complexities of the algorithm are identified, and numerical experiments are included.