DYNAMIC EVALUATION STRATEGY FOR FINE-GRAIN DATA-PARALLEL COMPUTING

The placement of elemental operations (as opposed to data) of a data-d riven data-parallel computation in a network of processors is examined . A fast suboptimal algorithm is proposed for such placement which ten ds to examined. A fast suboptimal algorithm is proposed for such place ment which tends to minimise the overall network load when the computa tion is essentially nonlocal. The cases of grid, torus and hypercube t opology are considered. It is shown that the proposed algorithm, while having moderate computational complexity, demonstrates up to a 50% re duction in required network throughput over some straightforward place ment schemes in the practical range of network sizes.