Fast algorithms for potential evaluation in N-body problems often tend to be extremely abstract and complex. This thesis presents a simple, hierarchical approach to solving the potential evaluation problem in O(n) time. The approach is developed in the field of electrostatics and can be extended to N-body problems in general. Herein, the potential vector is expressed as a product of the potential matrix and the charge vector. The potential matrix itself is a product of component matrices. The potential function satisfies the Laplace equation and is hence expressed as a linear combination of spherical harmonics, which form the general solutions of the Laplace equation. The orthogonality of the spherical harmonics is exploited to reduce execution time. The duality of the various lists in the algorithm is used to reduce storage and computational complexity. A smart tree-construction strategy leads to efficient parallelism at computation intensive stages of the algorithm. The computational complexity of the algorithm is better than that of the Fast Multipole Algorithm, which is one of the fastest contemporary algorithms to solve the potential evaluation problem. Experimental results show that accuracy of the algorithm is comparable to that of the Fast Multipole Algorithm. However, this approach uses some implementation principles from the Fast Multipole Algorithm. Parallel efficiency and scalability of the algorithms are studied by the experiments on IBM p690 multiprocessors.

This thesis presents a top to bottom analysis on designing and implementing fast algorithms for current and future systems. We present new analysis, algorithmic techniques, and implementations of the Fast Multipole Method (FMM) for solving N- body problems. We target the FMM because it is broadly applicable to a variety of scientific particle simulations used to study electromagnetic, fluid, and gravitational phenomena, among others. Importantly, the FMM has asymptotically optimal time complexity with guaranteed approximation accuracy. As such, it is among the most attractive solutions for scalable particle simulation on future extreme scale systems. We specifically address two key challenges. The first challenge is how to engineer fast code for today’s platforms. We present the first in-depth study of multicore op- timizations and tuning for FMM, along with a systematic approach for transforming a conventionally-parallelized FMM into a highly-tuned one. We introduce novel opti- mizations that significantly improve the within-node scalability of the FMM, thereby enabling high-performance in the face of multicore and manycore systems. The second challenge is how to understand scalability on future systems. We present a new algorithmic complexity analysis of the FMM that considers both intra- and inter- node communication costs. Using these models, we present results for choosing the optimal algorithmic tuning parameter. This analysis also yields the surprising prediction that although the FMM is largely compute-bound today, and therefore highly scalable on current systems, the trajectory of processor architecture designs, if there are no significant changes could cause it to become communication-bound as early as the year 2015. This prediction suggests the utility of our analysis approach, which directly relates algorithmic and architectural characteristics, for enabling a new kind of highlevel algorithm-architecture co-design. To demonstrate the scientific significance of FMM, we present two applications namely, direct simulation of blood which is a multi-scale multi-physics problem and large-scale biomolecular electrostatics. MoBo (Moving Boundaries) is the infrastruc- ture for the direct numerical simulation of blood. It comprises of two key algorithmic components of which FMM is one. We were able to simulate blood flow using Stoke- sian dynamics on 200,000 cores of Jaguar, a peta-flop system and achieve a sustained performance of 0.7 Petaflop/s. The second application we propose as future work in this thesis is biomolecular electrostatics where we solve for the electrical potential using the boundary-integral formulation discretized with boundary element methods (BEM). The computational kernel in solving the large linear system is dense matrix vector multiply which we propose can be calculated using our scalable FMM. We propose to begin with the two dielectric problem where the electrostatic field is cal- culated using two continuum dielectric medium, the solvent and the molecule. This is only a first step to solving biologically challenging problems which have more than two dielectric medium, ion-exclusion layers, and solvent filled cavities. Finally, given the difficulty in producing high-performance scalable code, productivity is a key concern. Recently, numerical algorithms are being redesigned to take advantage of the architectural features of emerging multicore processors. These new classes of algorithms express fine-grained asynchronous parallelism and hence reduce the cost of synchronization. We performed the first extensive performance study of a recently proposed parallel programming model, called Concurrent Collections (CnC). In CnC, the programmer expresses her computation in terms of application-specific operations, partially-ordered by semantic scheduling constraints. The CnC model is well-suited to expressing asynchronous-parallel algorithms, so we evaluate CnC using two dense linear algebra algorithms in this style for execution on state-of-the-art mul- ticore systems. Our implementations in CnC was able to match and in some cases even exceed competing vendor-tuned and domain specific library codes. We combine these two distinct research efforts by expressing FMM in CnC, our approach tries to marry performance with productivity that will be critical on future systems. Looking forward, we would like to extend this to distributed memory machines, specifically implement FMM in the new distributed CnC, distCnC to express fine-grained paral- lelism which would require significant effort in alternative models.

The following study examines whether the initialisation (multipole expansions at the finest level) and evaluation of the numerical method Fast Multipole Method (FMM) can benefit from implementing SSE instructions. The implementation of SSE-instructions have been studied and compared to the serial case. Moreover, studied parts of the algorithm include arithmetics on complex numbers, and the usage of applying SSE instructions to complex numbers of double precision. In conclusion, the initialisation has not experienced any improvement in terms of throughput by appliying SSE instructions. However, the evaluation reached almost the double speed-up when SSE instructions were applied. The difference in results are most likely due to the structure of the both algorithms. The initialisation is simple, but the evaluation which involves more operations can benefit from SSE instructions. Furthermore, a scheme is proposed for how SSE instructions can be applied to data sets which are not divisable by the unroll factor and to data sets of varying size.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20513号 / 情博第641号 / 新制||情||111(附属図書館) / 京都大学大学院情報学研究科複雑系科学専攻 / (主査)教授 西村 直志, 教授 磯 祐介, 准教授 吉川 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

No description available.

No description available.

No description available.

[pt] Este trabalho visa à implementação de um programa de elementos de contorno para problemas com milhões de graus de liberdade. Isto é obtido com a implementação do Método Fast Multipole (FMM), que pode reduzir o número de operações, para a solução de um problema com N graus de liberdade, de O(N(2)) para O(NlogN) ou O(N). O uso de memória também é reduzido, por não haver o armazenamento de matrizes de grandes dimensões como no caso de outros métodos numéricos. A implementação proposta é baseada em um desenvolvimento consistente do convencional, Método de colocação dos elementos de contorno (BEM) – com conceitos provenientes do Hibrido BEM – para problemas de potencial e elasticidade de larga escala em 2D e 3D. A formulação é especialmente vantajosa para problemas de topologia complicada ou que requerem soluções fundamentais complicadas. A implementação apresentada, usa um esquema para expansões de soluções fundamentais genéricas em torno de níveis hierárquicos de polos campo e fonte, tornando o FMM diretamente aplicável para diferentes soluções fundamentais. A árvore hierárquica dos polos é construída a partir de um conceito topológico de superelementos dentro de superelementos. A formulação é inicialmente acessada e validada em termos de um problema de potencial 2D. Como resolvedores iterativos não são necessários neste estágio inicial de simulação numérica, podese acessar a eficiência relativa à implementação do FMM. / [en] This work aims to present an implementation of a boundary element solver for problems with millions of degrees of freedom. This is achieved through a Fast Multipole Method (FMM) implementation, which can lower the number of operations for solving a problem, with N degrees of freedom, from O(N(2)) to O(NlogN) or O(N). The memory usage is also very small, as there is no need to store large matrixes such as required by other numerical methods. The proposed implementations are based on a consistent development of the conventional, collocation boundary element method (BEM) - with concepts taken from the variationally-based hybrid BEM - for large-scale 2D and 3D problems of potential and elasticity. The formulation is especially advantageous for problems of complicated topology or requiring complicated fundamental solutions. The FMM implementation presented in this work uses a scheme for expansions of a generic fundamental solution about hierarchical levels of source and field poles. This makes the FMM directly applicable to different kinds of fundamental solutions. The hierarchical tree of poles is built upon a topological concept of superelements inside superelements. The formulation is initially assessed and validated in terms of a simple 2D potential problem. Since iterative solvers are not required in this first step of numerical simulations, an isolated efficiency assessment of the implemented fast multipole technique is possible.

Face à la complexité grandissante des convertisseurs statiques présents dans tout système électrique, les ingénieurs de conception ont besoin d'outils de modélisation électromagnétique de plus en plus performants, notamment en ce qui concerne la Compatibilité ÉlectroMagnétique (CEM). L'objectif de ce travail est de prendre en compte, sous la forme de capacités parasites, les couplages électriques en haute fréquence dans la modélisation CEM de dispositifs d'électronique de puissance. Plusieurs formulations intégrales basées sur la Méthode des Moments, ainsi que l'Adaptive Multi-Level Fast Multipole Method ont été développées et validées pour l'extraction de ces capacités équivalentes. Cette dernière méthode, qui permet d'accélérer les temps de calcul tout en limitant la place mémoire nécessaire (pas de stockage de matrice pleine), a été adaptée au problème pour garantir une meilleure précision des résultats en fonction du maillage. Un prototype de cet algorithme de calcul a été intégré dans le logiciel InCa3D, basée sur la méthode PEEC, permettant ainsi de construire un schéma électrique équivalent à constantes localisées où les effets capacitifs sont couplés au modèle résistif et inductif de la structure. Plusieurs cas tests, issus de la littérature ou d'applications industrielles, ont été simulés par le biais de ces schémas équivalents, soit dans un solveur circuit soit dans InCa3D, afin d'évaluer leurs performances CEM conduites et rayonnées. Enfin, les comparaisons réalisées avec des mesures ont donné de bons résultats et valident ainsi l'approche proposée. Une telle stratégie peut aisément faire partie de toute modélisation de type système, car elle permet de traiter des dispositifs de complexité industrielle sur une large bande de fréquences avec un modèle léger.