Dynamic evaluation strategy for fine-grain data-parallel computing
Vyacheslav B. Muchnick, Alex Shafarenko · IEE Proceedings - Computers and Digital Techniques · 1996
The placement of elemental operations (as opposed to data) of a data-driven data-parallel computation in a network of processors is examined. A fast suboptimal algorithm is proposed for such placement which tends to minimise the overall network load when the computation is essentially nonlocal. The cases of grid, torus and hypercube topology are considered. It is shown that the proposed algorithm, while having moderate computational complexity, demonstrates up to a 50% reduction in required network throughput over some straightforward placement schemes in the practical range of network sizes.