This paper studies some problems arised while parallelising continuum computation applications. A major problem in these applications is load imbalance since the problems usually are completely dynamic in nature. A dynamic load balancing algorithm was proposed in [11] and called Positional Scan Load Balancing (PSLB). The algorithm completely preserves the original ordering of the problem decomposition. PSLB allows for processors with different dynamic processing powers, and is suitable for embedding in a runtime system. A performance model for the PSLB algorithm is described in terms of the BSP model. We derive cost prediction formulae, and introduce crossover points, i.e. points at which it becomes beneficial to use the algorithm in terms of the problem complexity. We examine the algorithms performance experimentally with both a simulated workload and an actual parallel molecular simulation on a Cray T3D with up to 256 processors. We present results detailing the overhead, performance gain, and speedup of the algorithm for fixed problem size. We also present the algorithm performance for scaled problem size.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £70 +P&P)