E-KERNEL - AN EMBEDDING KERNEL ON THE IBM VICTOR-V256 MULTIPROCESSOR FOR PROGRAM MAPPING AND NETWORK RECONFIGURATION

We present the design of E-kernel, an embedding kernel on the Victor V 256 message-passing partitionable multi-processor, developed for the s upport of program mapping and network reconfiguration. E-kernel suppor ts the embedding of a new network topology onto Victor's 2-D mesh and also the embedding of a task graph onto the 2-D mesh network or the re configured network. In the current implementation, the reconfigured ne twork can be a line or an even-size ring, and the task graphs meshes o r tori of a variety of dimensions and shapes or graphs with similar to pologies. 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 2- D mesh, line, or ring. Further, E-kernel attempts the communication op timization of these programs on the different networks automatically, thus making both the network topology and the communication optimizati on 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-kern el 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. Measureme nts of E-kernel's performance on V256 are also included.