Time parallelization methods for the solution of initial value problems .

摘要

Many scientific problems are posed as Ordinary Differential Equations (ODEs). A large subset of these are initial value problems, which are typically solved numerically. The solution starts by using a known state-space of the ODE system to determine the state at a subsequent point it time. This process is repeated several times. When the computational demand is high due to large state space, parallel computers can be used efficiently to reduce the time of solution. Conventional parallelization strategies distribute the state space of the problem amongst processors and distribute the task of computing for a single time step amongst the processors. They are not effective when the computational problems have fine granularity, for example, when the state space is relatively small and the computational effort arises largely from the long time span of the initial value problem.;The above limitation is increasingly becoming a bottleneck for important applications, in particular due to a couple of architectural trends. One is the increase in number of cores on massively parallel machines. The high end systems of today have hundreds of thousands of cores, and machines of the near future are expected to support the order of a million simultaneous threads. Computations that were coarse grained on earlier machines are often fine grained on these. Another trend is the increased number of cores on a chip. This has provided desktop access to parallel computing for the average user. A typical low-end user requiring the solution of an ODE with a small state space would earlier not consider a parallel system. However, such a system is now available to the user. Users of both the above environments need to deal with the problem of parallelizing ODEs with small state space.;Parallelization of the time domain appears promising to deal with this problem. The idea behind this is to divide the entire time span of the initial value problem into smaller intervals and have each processor compute one interval at a time, instead of dividing the state space. The difficulty lies in that time is an intrinsically sequential quantity and one time interval can only start after its preceding interval completes, since we are solving an initial value problem. Earlier attempts at parallelizing the time domain were not very successful. This thesis proposes two different time parallelization strategies, and demonstrates their effectiveness in dealing with the bottleneck described above.;The thesis first proposes a hybrid dynamic iterations method which combines conventional sequential ODE solvers with dynamic iterations. Empirical results demonstrate a factor of two to three improvement in performance of the hybrid dynamic iterations method over a sequential solver on an 8 core processor, while conventional state-space decomposition is not useful due to the communication overhead. Compared to Picard iterations (also parallelized in the time domain), the proposed method shows better convergence and speedup results when high accuracy is required.;The second proposed method is a data-driven time parallelization algorithm. The idea is to use results from related prior computations to predict the states in a new computation, and then parallelize the new computation in the time domain. The effectiveness of the this method is demonstrated on Molecular Dynamics (MD) simulations of Carbon Nanotube (CNT) tensile tests. MD simulation is a special application of initial value problems. Empirical results show that the data-driven time parallelization method scales to two to three orders of magnitude larger numbers of processors than conventional state-space decomposition methods. This approach achieves the highest scalability for MD on general purpose computers.;The time parallel method can also be combined with state space decomposition methods to improve the scalability and efficiency of the conventional parallelization method. This thesis presents a combined data-driven time parallelization and state space decomposition method and adapts it in MD simulations of soft-matter, which is typically seen in computational biology.;Since MD method is an important atomistic simulation technique and widely used in computational chemistry, biology and materials, the data-driven time parallel method also suggests a promising approach for realistic simulations with long time span.