The research proposed focuses on developing algorithms and system software for a high-performance multicomputer system. A multicomputer system consists of a large number of interconnected computing nodes that asynchronously cooperate via message passing to execute the tasks of parallel programs. Each network node, fabricated as a small number of VLSI chips, contains a processor, a local memory, and (preferably) a communication controller capable of routing messages without delaying the computation processor. The recent appearance of commercial multicomputer systems (i.e., hypercubes), with rudimentary software support, allows testing of many new ideas in operating systems, algorithms, communication, and parallel programming. Because there is no global memory, a multicomputer system supporting computations that dynamically create tasks must schedule those tasks on idle nodes using information local to the area where the tasks were created. Problem partitioning and new algorithm designs for communicating tasks must be explored if multicomputer systems are to be used effectively. In addition, communication software capable of efficiently routing messages to their destination are needed. The PI has partially tested, via analysis and simulation, many techniques and ideas for resolving these problems in scheduling and routing. Picasso, a hypercube operating system with modules for dynamic task scheduling and adaptive message routing, is being developed to experimentally explore the interaction of task scheduling, adaptive routing algorithms, and algorithm design.
