Numerical integration of ordinary differential equation on multiprocessing systems

Abstract

In this thesis, we explore how to solve Ordinary Differential Equations (ODEs) on parallel computers. A comprehensive study of the current state-of-the-art methods for both sequential and parallel integration of ODEs is conducted. This helps define the desirable properties of parallel computers and the algorithms suitable for solving ODEs efficiently. A new algorithm is developed and optimized for maximum performance in a general multiprocessing environment. It is tested on various systems of ODEs in simulated environments, and compared with other parallel and sequential methods. Simulation results demonstrate that the proposed algorithm is both effective and competitive. The study also reveals a drawback in existing task partitioning schemes used for solving ODEs. To address this, a new task partitioning scheme is designed and evaluated through further simulations. These results establish the superiority of the new scheme and guide the design of an ideal multiprocessing digital differential analyzer, which shows functional and morphological similarities to analog computers. Following this, a prototype digital differential analyzer is built. The thesis describes its hardware design, along with the necessary system software and a runtime system to support a high-level language multiprocessing compiler. A small four-processor machine is realized, capable of solving differential equations with speedups ranging from 1.2 to 3.6, depending on the system of equations. It also performs well on non-ODE application problems. The thesis concludes by proposing ideas for the design of hardware, topology, algorithms, task partitioning schemes, and user interfaces to achieve acceptable performance in larger multiprocessors built for solving ODEs.