Implementation and testing of a parallel layer peeling algorithm

Abstract

The objective of this thesis is to examine the feasibility of parallelizing a previously published sequential algorithm. This algorithm uses invariant imbedding to solve an inverse problem associated with the first order, partial differential equation describing radiative transfer. The published algorithm applied invariant imbedding methods to the two stream approximation to a one dimensional radiative transfer equation, resulting in an integrodifferential equation that takes multiple scattering events into account. Two different implementations of the above mentioned serial algorithm viz., Layer Peeling and Characteristic Tracing have been previously described, and the characteristic tracing method has been implemented in parallel. For this thesis, the parallel implementation of the layer peeling algorithm was considered. In this context, layer peeling implies that pertinent quantities are known at some layer, say the (i-I)th, which are used to move deeper, into the ith layer. The parallel implementation was considered because of the anticipated speedup in the solution of the problem under consideration. The algorithm was implemented on an NCUBE 2 machine, with a total of sixty-four processors. Two variations of the parallel algorithm were implemented viz., Block Layer Assignment (BLA), and Rotated Individual Layer Assignment (RILA). The results from the parallel implementation were verified for accuracy by solving the direct problem and using its results as input to the inverse solution. The results obtained from the inverse solution were then compared to the input of the direct solution. Several issues specific to parallel computation were considered in the parallel layer peeling implementation and analysis. These included issues such as task allocation, or the total workload breakdown for assignment to different processors, communication of interim results between processors, and synchronization of the computations from different processors. In order to achieve better performance, the parallel implementation was done by using Reflected Gray Codes for processor assignment. Reflected Gray Code ordering ensures that the address of the processor working on any layer differs in at most a single bit from the processor working on the neighboring layer, so the communication is always between nearest neighbors.