1 The Problem Processor Management in Highly Parallel Systems with 2D-Grid Architectures: Buddy Schemes

Programming for parallel systems and in particular, multicomputers, is still uncomfortable and inefficient. We often observe monoprogramming operation, which inevitably leads to poor utilization and uneconomic machine usage. When multiprogramming is available, the machine is usually partitioned manually and in a rather static way without the ability to adjust the partitioning to the dynamic requests of the parallel programs. The reason for this situation is a lack of operating system software support. We therefore claim that operating systems for those machines have to provide a dynamic processor management facility comparable to storage management. Mesh-connected multicomputer (MIMD message passing) systems become more and more popular for different reasons: Firstly, for many problems to be solved the 2D-grid is the natural and appropriate communication topology. Secondly, even if the problem structure is not exactly the 2D-grid, many parallel programs based on data partitioning need only local information exchange with a few partners and can still be sufficiently well mapped to 2D-grid architectures. Thirdly, unlike the hypercube, the 2D-grid has a constant node degree, which makes the topology highly scalable. Fourthly, there are already powerful processor chips available that are specifically designed for 2D-topologies (Transputer). We assume a homogeneous multicomputer system with N = 2 n 1 × 2 n 2 identical processor nodes. Each nod