Marek Tudruj

The paper concerns methods for using Extremal Optimization (EO) for processor load balancing during execution of distributed programs. A load balancing algorithm for clusters of multicore processors is presented and discussed. In this algorithm the EO approach is used to periodically detect the best tasks as candidates for migration and for a guided selection of the best processors to receive the migrated tasks. To decrease the complexity of selection for migration, we propose a guided EO algorithm which assumes a two step stochastic selection during the solution improvement based on two separate fitness functions. The functions are based on specific program models which estimate relations between the programs and the executive hardware. The proposed load balancing algorithm is assessed by experiments with simulated load balancing of distributed program graphs. The algorithm is compared against an EO - based algorithm with random placement of migrated tasks and a classic genetic algorithm.

The paper presents an analysis of the suitability of the architecture of dynamic SMP clusters with communication on the fly for massively parallel fine grain numerical computations. It is assumed that the proposed architecture is implemented using the highly modular " system on chip" and "network on chip" technology. This technology is considered to provide soon a very large number of co-operating processors embedded in a single parallel system, thus enabling massively parallel computations. The proposed architecture of dynamic clusters with communication on the fly meets requirements of large scale fine grain computations and can be successfully applied in this technology. Experimental simulation results are presented concerning efficiency of fine grain parallel implementation of a typical numerical problem which is matrix multiplication based on recursive data decomposition. Selection of optimal parallel computation grain is discussed. Estimations of the efficiency of the proposed methods for fine grain computations for large problem size are presented.