Load balancing schemes for extrapolation methods

✍ Scribed by Rauber, Thomas; Rünger, Gudula

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 307 KB
• Volume: 9
• Category: Article
• ISSN: 1040-3108
• DOI: 10.1002/(sici)1096-9128(199703)9:3<181::aid-cpe245>3.0.co;2-6

✦ Synopsis

Solving initial value problems (IVPs) for ordinary differential equations (ODEs) has long been believed to be an inherently sequential procedure. But IVP solvers using the extrapolation method provide high quality solutions and offer a great potential for parallelism. In this paper, we present algorithms for extrapolation methods on distributed memory multiprocessors that combine different levels of parallelism. These algorithms differ mainly in the partitioning of the processors into groups which are responsible for the execution of the independent tasks of the extrapolation method. We present the algorithms in a compute-communicate scheme using appropriate primitives for the communication. A detailed analysis shows that a sophisticated load balancing scheme is required to achieve good speedup. We describe an optimal method based on Lagrange multipliers, investigate several simple heuristic schemes, and compare the heuristic schemes with an estimation for the optimal solution. An implementation of these schemes on an Intel iPSC/860 confirms the predicted runtimes.