Recently, a new algorithm (Bank-Holst) was described for the parallel adaptive finite element solution of elliptic partial differential equations with negligible interprocess communication (22). Unlike finite difference methods, which use a fixed resolution of the problem domain, adaptive finite element techniques generate very accurate solutions of these equations by locally enriching the basis set in regions of high error through refinement of the domain discretization. The first step in the Bank-Holst parallel finite element algorithm is the solution of the equation over the entire problem domain using a coarse resolution basis set by each processor. This solution is then used, in conjunction with an a posteriori error estimator, to partition the problem domain into P subdomains, which are assigned to the P processors of a parallel computer. The algorithm is load balanced by equidistributing a posteriori error estimates across the subdomains. Each processor then solves the partial differential equation over the global mesh, but confines its adaptive refinement to the local subdomain and a small surrounding overlap region. This procedure results in a very accurate representation of the solution over the local subdomain. After all processors have completed their local adaptive solution of the equation, a global solution is constructed by the piecewise assembly of the solutions in each subdomain. It can be rigorously shown that the piecewise-assembled solution is as accurate as the solution to the problem on a single global mesh (23). Because each processor performs all of its computational work independently, the Bank-Holst algorithm requires very little interprocess communication and exhibits excellent parallel scaling. Unfortunately, although this algorithm works well for adaptive techniques, such as finite elements, it is not directly applicable to the fixed-resolution finite difference methods that currently offer the most efficient solution of the PBE for large molecular systems. However, by combining the Bank-Holst method with other techniques, we have been able to extend this algorithm to finite difference solvers.
Electrostatic "focusing" is a popular technique in finite difference methods for generating accurate solutions to the PBE in subsets of the problem domain, such as a binding or titratable sites within a protein (4, 14). Like the Bank-Holst method, the first step in electrostatic focusing is the calculation of a low-accuracy solution on a coarse finite difference mesh spanning the entire problem domain. This coarse solution is then used to define the boundary conditions for a much more accurate calculation on a finer discretization of the desired subdomain. As noted previously (22), this focusing technique is superficially related to the Bank-Holst algorithm, where the local enrichment of a coarse, global solution has been replaced by a the solution of a fine, local multigrid problem using the solution from a coarse, global problem for boundary conditions.
We have combined standard focusing techniques and the Bank-Holst algorithm into a "parallel focusing" method for the solution of the PBE. Unlike previous parallel algorithms for solving the PBE, this method has excellent parallel complexity, permitting the treatment of very large biomolecular systems on massively parallel computational platforms. Furthermore, the finite difference discretization on a regular mesh allows for fast solution by certain highly efficient multigrid solvers (12). The algorithm is summarized below:
Given the problem data and P processors of a parallel machine:
(i) Each processor i = 1...,P (a) obtains a coarse solution of the PBE over the global domain, (b) heuristically subdivides the global domain into P subdomains (
1...,P), which are assigned to processors 1...,P, (c) assigns boundary conditions to its subdomain i using the coarse global solution, and (d) solves the PBE on subdomain i.
(ii) A master processor collects observable data (free energy, etc.) from the other processors and controls I/O.
This parallel focusing algorithm begins with each processor independently solving a coarse global problem. The per-processor subdomains are chosen in a heuristic fashion as outlined in Fig. 1. Like standard focusing calculations, only a subset of the global mesh surrounding the area of interest is used for the parallel calculations. This subset is partitioned into P approximately equal subdomains, which are distributed among the processors. Each processor then performs a fine-scale finite difference calculation over this subdomain and an overlap region that usually spans about 5-10% of the neighboring subdomains. The overlap regions are included to compensate for inaccuracies in the boundary conditions derived from the global coarse solution; however, these regions are not used to assemble the fine-scale global solution and do not contribute to calculations of observables such as forces and energies. After the fine-scale calculations are complete, a master processor accumulates the desired data from the other processes and controls I/O of the solution. Like the Bank-Holst algorithm, each process computes independently on both the global coarse problem and its subdomain. These independent computations result in an algorithm that requires negligible interprocess communication and offers excellent parallel performance.
Because of its low communication requirements, this parallel focusing algorithm can be used on parallel platforms ranging from low-bandwidth networks of workstations to high-performance supercomputers. Because step d of the parallel focusing algorithm typically dominates the overall computation, this algorithm provides excellent time complexity with respect to the number of processors. Most importantly for Poisson-Boltzmann calculations on large molecules, the mesh resolution increases linearly with the number of processors.** This linear behavior has been observed on calculations involving hundreds of processors; Fig. 2 shows the scaling results for calculations on the biomolecular systems discussed below. The parallel focusing algorithm was tested on up to 700 processors and shows linear scaling over the entire range. The implications of the improved performance available through this parallel algorithm are discussed in more detail in the next section.
Parallel focusing has been implemented as an extension (23) of the APBS (Adaptive Poisson-Boltzmann Solver) software package (9) by using the PMG multigrid library to assemble and solve the PBE algebraic systems (12, 16). The parallel routines have been implemented by using MALOC, a portable hardware abstraction layer library (23), which allows interprocess communication through a variety of methods.
The following sections describe the application of the parallel focusing techniques to very large biomolecular systems whose electrostatic properties were unattainable by using traditional methods for solving the PBE. Specifically, we examine two important cellular components: a million-atom microtubule fragment and the large and small subunits of the ribosome.
Answers to all your Biology Questions
