BSPGRID: VARIABLE RESOURCES PARALLEL COMPUTATION AND MULTIPROGRAMMED PARALLELISM

This paper introduces a new framework for the design of parallel algorithms that may be executed on multiprogrammed architectures with variable resources. These features, in combination with an implied ability to handle fault tolerance, facilitates environments such as the GRID. A new model, BSPGRID is presented, which exploits the bulk synchronous paradigm to allow existing algorithms to be easily adapted and used. It models computation, communication, external memory accesses (I/O) and synchronization. By combining the communication and I/O operations BSPGRID allows the easy design of portable algorithms while permitting them to execute on non-dedicated hardware and/or changing resources, which is typical for machines in a GRID. However, even with this degree of dynamicity, the model still offers a simple and tractable cost model. Each program runs in its own virtual BSPGRID machine. Its emulation on a real computer is demonstrated to show the practicality of the framework. A dense matrix multiplication algorithm and its emulation in a multiprogrammed environment is given as an example.