A new approach to task decomposition for parallel particle-in-cell simulation

Particle-in-Cell method is a simulation technique which is predominantly used in important scientific areas, such as plasma physics, semiconductor device physics, global climate modeling, and galaxy dynamics. These simulations which are generally performed on supercomputers require a long CPU time. Moreover, the enormous amount of data involved in these problems require a large memory space.; In this thesis, two primary approaches to parallelizing the Particle-in-Cell problem are discussed first. One approach, partitioning grid space (PAGS), focuses on saving memory space by partitioning the grid cells among PEs. The inherent problem with this approach is the difficulty in maintaining the load balance throughout the simulation.; On the other hand, memory space is not of concern in the other approach, partitioning particles (PAP). This approach is designed to attain a perfectly balanced load among PEs and thus a high speedup, by always keeping the data local. However, communication or remote memory access time can still degrade the performance. Depending on the system and problem parameters the latter approach may or may not provide a higher speedup than the former approach.; The new task decomposition scheme introduced in this thesis, hybrid partitioning, is evolved out of the two decomposition approaches. The objective of the hybrid partitioning is to provide an efficient and flexible task partitioning scheme by which one can reduce the size of memory required on each PE without sacrificing the system performance or vice versa.; One of the major advantages of the hybrid partitioning is the versatility that this technique offers for decomposing the PIC problem. Hybrid partitioning is a flexible task decomposition method which utilizes multiprocessor systems to their highest potentials. It offers a set of partitioning instances such that one can choose an instance depending on the size of the memory available on a system.; The hybrid partitioning has been implemented on the MIMD parallel processors. Two classes of these multiprocessors, message-passing and shared memory, systems are employed. Different implementation schemes have been developed for each class of these systems.