N-body problems encompass a variety of fields such as electrostatics, molecularbiology and astrophysics. If there are N particles in the system, the brute force algorithmfor these problems based on particle-particle interaction takes O(N2), whichis clearly expensive for large values of N. There have been some approximation algorithmslike the Barnes-Hut Method and the Fast Multipole Method (FMM) proposedfor these problems to reduce the complexity. However, the applicability of these algorithmsare limited to operators with analytic multipole expansions or restricted tosimulations involving low accuracy. The shortcoming of N-body treecodes are moreevident for particles in motion where the movement of the particles are not consideredwhen evaluating the potential. If the displacement of the particles are small, thenupdating the multipole coefficients for all the nodes in the tree may not be requiredfor computing the potential to a reasonable accuracy. This study focuses on some ofthe limitations of the existing approximation schemes and presents new algorithmsthat can be used for N-body simulations to efficiently compute potentials and forces.In the case of electrostatics, existing algorithms use Cartesian coordinates to evaluatethe potentials of the form r−, where 1. The use of such coordinates toseparate the variables results in cumbersome expressions and does not exploit the inherent spherical symmetry found in these kernels. For such potentials, we providea new multipole expansion series and construct a method which is asymptoticallysuperior than the current treecodes. The advantage of this expansion series is furtherdemonstrated by an algorithm that can compute the forces to the desired accuracy.For particles in motion, we introduce a new method in which we retain the multipolecoefficients when performing multipole updates (to the parent nodes) at every timestep. This results in considerable savings in time while maintaining the accuracy. Wefurther illustrate the efficiency of our algorithms through numerical experiments.

N-body problems encompass a variety of fields such as electrostatics, molecularbiology and astrophysics. If there are N particles in the system, the brute force algorithmfor these problems based on particle-particle interaction takes O(N2), whichis clearly expensive for large values of N. There have been some approximation algorithmslike the Barnes-Hut Method and the Fast Multipole Method (FMM) proposedfor these problems to reduce the complexity. However, the applicability of these algorithmsare limited to operators with analytic multipole expansions or restricted tosimulations involving low accuracy. The shortcoming of N-body treecodes are moreevident for particles in motion where the movement of the particles are not consideredwhen evaluating the potential. If the displacement of the particles are small, thenupdating the multipole coefficients for all the nodes in the tree may not be requiredfor computing the potential to a reasonable accuracy. This study focuses on some ofthe limitations of the existing approximation schemes and presents new algorithmsthat can be used for N-body simulations to efficiently compute potentials and forces.In the case of electrostatics, existing algorithms use Cartesian coordinates to evaluatethe potentials of the form r−, where 1. The use of such coordinates toseparate the variables results in cumbersome expressions and does not exploit the inherent spherical symmetry found in these kernels. For such potentials, we providea new multipole expansion series and construct a method which is asymptoticallysuperior than the current treecodes. The advantage of this expansion series is furtherdemonstrated by an algorithm that can compute the forces to the desired accuracy.For particles in motion, we introduce a new method in which we retain the multipolecoefficients when performing multipole updates (to the parent nodes) at every timestep. This results in considerable savings in time while maintaining the accuracy. Wefurther illustrate the efficiency of our algorithms through numerical experiments.

Tree-based methods have wide applications for solving large-scale problems in electromagnetics, astrophysics, quantum chemistry, fluid mechanics, acoustics, and many more areas. This thesis focuses on their applicability for solving large-scale problems in electromagnetics. The Barnes-Hut (BH) algorithm and the Fast Multipole Method (FMM) are introduced along with a survey of important previous work. The required theory for applying those methods to problems in electromagnetics is presented with particular emphasis on the capacitance extraction problem and broadband full-wave scattering. A novel single source approximation is introduced for approximating clusters of electrostatic sources in multi-layered media. The approximation is derived by matching the spectra of the field in the vicinity of the stationary phase point. Combined with the BH algorithm, a new algorithm is shown to be an efficient method for evaluating electrostatic fields in multilayered media. Specifically, the new BH algorithm is well suited for fast capacitance extraction. The BH algorithm is also adapted to the scalar Helmholtz kernel by using the same methodology to derive an accurate single source approximation. The result is a fast algorithm that is suitable for accelerating the solution of the Electric Field Integral Equation (EFIE) for electrically small structures. Finally, a new version of FMM is presented that is stable and efficient from the low frequency regime to mid-range frequencies. By applying analytical derivatives to the field expansions at the observation points, the proposed method can rapidly evaluate vectorial kernels that arise in the FMM-accelerated solution of EFIE, the Magnetic Field Integral Equation (MFIE), and the Combined Field Integral Equation (CFIE).

Tree-based methods have wide applications for solving large-scale problems in electromagnetics, astrophysics, quantum chemistry, fluid mechanics, acoustics, and many more areas. This thesis focuses on their applicability for solving large-scale problems in electromagnetics. The Barnes-Hut (BH) algorithm and the Fast Multipole Method (FMM) are introduced along with a survey of important previous work. The required theory for applying those methods to problems in electromagnetics is presented with particular emphasis on the capacitance extraction problem and broadband full-wave scattering. A novel single source approximation is introduced for approximating clusters of electrostatic sources in multi-layered media. The approximation is derived by matching the spectra of the field in the vicinity of the stationary phase point. Combined with the BH algorithm, a new algorithm is shown to be an efficient method for evaluating electrostatic fields in multilayered media. Specifically, the new BH algorithm is well suited for fast capacitance extraction. The BH algorithm is also adapted to the scalar Helmholtz kernel by using the same methodology to derive an accurate single source approximation. The result is a fast algorithm that is suitable for accelerating the solution of the Electric Field Integral Equation (EFIE) for electrically small structures. Finally, a new version of FMM is presented that is stable and efficient from the low frequency regime to mid-range frequencies. By applying analytical derivatives to the field expansions at the observation points, the proposed method can rapidly evaluate vectorial kernels that arise in the FMM-accelerated solution of EFIE, the Magnetic Field Integral Equation (MFIE), and the Combined Field Integral Equation (CFIE).

The Cell processor is an example of the trade-offs made when designing a mass market power efficient multi-core machine, but the machine-exposing architecture and raw communication mechanisms of Cell are hard to manage for a programmer. Cell's design is simple and causes software complexity to go up in the areas of achieving low threading overhead, good bandwidth efficiency, and load balance. Several attempts have been made to produce efficient and effective programming systems for Cell, but the attempts have been too specialized and thus fall short. We present Jack Rabbit, an efficient thread pool work queue implementation, with load balancing mechanisms and double buffering. Our system incurs low threading overhead, gets good load balance, and achieves bandwidth efficiency. Our system represents a step towards an effective way to program Cell and any similar current or future processors. / text

The main topic of this thesis is the implementation and subsequent optimization of high performance applications on a cluster of Intel Xeon Phi coprocessors. Using two approaches to solve the N-Body problem, the possibilities of the program execution on a cluster of processors, coprocessors or both device types have been demonstrated. Two particular versions of the N-Body problem have been chosen - the naive and Barnes-hut. Both problems have been implemented and optimized. For better comparison of the achieved results, we only considered achieved acceleration against single node runs using processors only. In the case of the naive version a 15-fold increase has been achieved when using combination of processors and coprocessors on 8 computational nodes. The performance in this case was 9 TFLOP/s. Based on the obtained results we concluded the advantages and disadvantages of the program execution in the distributed environments using processors, coprocessors or both.