Performance prediction and race detection in message-passing parallel applications

Basile Schäli
EPFL, 2009
EPFL thesis

Abstract

The combination of low cost clusters and multicore processors lowers the barrier for accessing massive amounts of computing power. As computational sciences advance, the use of in silico simulations to complement in vivo experiments promises parallel programming a bright future in multiple scientific fields. It is therefore increasingly important to develop tools helping developers to write efficient and bug-free parallel applications. This thesis focuses on performance prediction and advanced testing tools for distributed memory message-passing parallel applications. The tools have been implemented within the Dynamic Parallel Schedules (DPS) parallelization framework. They have also been partly adapted to applications written using the Message Passing Interface (MPI) standard. The first part presents a parallel application simulator which has been integrated into the DPS framework. We identified a small set of processing and networking parameters that characterize the hardware platform on which the application is running. After parameterizing the hardware platform, the running time of parallel applications can be predicted using direct execution without requiring any change to the application source code. We propose a partial direct execution technique that reduces the execution time and memory consumption of the simulation. Using partial direct execution, the simulation is no longer tied to the platform to be simulated. Simulations may thus run on a desktop computer rather than on the target parallel machine. The proposed parameterization of the application and of the hardware properties enable using the simulator to study the sensitivity of a parallel application to various operating conditions such as the data subdivision granularity, the adopted parallelization strategy and the underlying hardware platform properties. The proposed simulator helps developers identifying the factors having the largest impact on their application's performance, and determining the most suitable cluster hardware configuration. Speed should not come at the expense of correctness. Since improving parallelization efficiency often requires loosening synchronizations or implementing more complex communication patterns, developers need to ensure that their changes do not introduce potential message races or deadlocks. Deadlocks and message races are common sources of problems in parallel applications and stem from the fact that the delivery of messages from different sources is not deterministically ordered. This non-determinism makes such synchronization errors hard to reproduce and debug. The second part of the thesis presents methods for uncovering potential deadlocks and message races by taking advantage of the flow graph structures and checkpointing capabilities of DPS. We developed a debugger for DPS applications that displays an instantaneous graphical view of the global computation state and is able to control the ordering of message delivery in order to explicitly test specific orderings. The number of possible orderings explodes when the number of messages sent by the application increases. Manual testing can only cover a tiny fraction of possible executions. Therefore, we use the simulator's ability to control the execution of a parallel application, in order to automatically detect deadlocks and message races. A first method for reducing the number of orderings to be tested relies on a partial-order reduction of the search space and on the decomposition of the application execution into independently testable subparts. This method relies on a static analysis of an execution trace of the application, and can therefore only be applied to parallel applications that produce a fixed set of messages, i.e. applications producing the same messages for all delivery orderings. In order to overcome this limitation, we propose an approach relying on the dynamic construction of a state graph expressing possible executions. Both methods reduce the testing costs by several orders of magnitude, and can be combined to further improve the results. Nevertheless, testing durations may remain prohibitive for longer running applications. We therefore also define algorithms generating subsets of possible orderings that are likely to reveal erroneous executions. In the recent years, the MPI standard has emerged as the de facto standard for writing message-passing parallel applications. The final part of this thesis therefore focuses on adapting the aforementioned parallel application testing concepts to MPI applications. We first describe the extension of our work on visualizing the execution of parallel applications. We then discuss the limits and the benefits of using partial-order execution graphs to describe MPI application executions, and show that our dynamic message-passing state graph construction approach can be successfully applied.

Official source

https://infoscience.epfl.ch/record/128889?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Basile Schäli
EPFL, 2009
EPFL thesis

Abstract

Official source

https://infoscience.epfl.ch/record/128889?ln=en

About this result

Related concepts (11)

Related concepts

Related publications (2)

Related publications

Helium atoms are known to have a significant impact on materials used in fission and fusion reactors. In particular, the presence of helium atoms can change the mechanical properties and degrade the lifetime of reactors. In order to develop the helium-resistance materials, the underlying interactions between helium atoms and matrix atoms have to be understood. In the past, atomistic simulations have contributed a lot to the basic energy states of helium atoms in different defects of materials. Especially, insights into the formation energies of helium atoms at simple defects have been calculated by ab initio and molecular dynamics. The substitional helium has lower formation energy than the tetrahedral and octahedral interstitial helium atom. Additionally, the binding energies of helium with small HenVm cluster have also been found to be all positive. However, all these simulations have been performed without showing the kinetic formation process of such helium defects. The interactions of defect with larger number of helium atoms are also not explored in detail. In the first part of this thesis, a new relaxation-fitting method has been developed for cross potential of Fe-He system based on more energy data of helium-defect clusters from ab initio calculations and by including the migration energy of single free helium atom in the fitting process. Besides, the recently fitted magnetic potentials of Fe have been used to describe the Fe-Fe interactions for such cross potential. The new fitted Fe-He potentials have predicted well not only the properties of simple helium defect, but also the properties of helium clusters and diffusion process of helium atoms. Based on the new Fe-He potentials, the interactions between helium atoms and Fe with the effect of single vacancy have been simulated utilizing the classical molecular dynamics (MD) method in the single bcc Fe lattice at room temperatures by helium atoms up to 18. The binding energies of helium atom with HenV cluster are computed. By increasing number of helium atoms, the binding energy decreases first, then slowly increases up to n = 4. It is then almost constant between n = 5 to 15 but increases strongly at n = 16 to form a peak. This last increase is related to the athermal self-interstitial atom (SIA) emission in the form of dumbbell which relaxes the restrained system to He16V2 cluster. The second binding energy peak occurs at n = 18 by the formation of the second SIA to form He18V3 cluster. Close inspection of the local configuration shows the formed SIA combines with the helium-defect cluster. Calculation of the pressure of the helium-defect cluster shows local peak normal stress and shear stress values up to 9 GPa and 4 GPa, respectively. The local configurations of helium-defect cluster suggest that with increasing helium content, some symmetrical structures can be formed. By increasing the number of helium atoms inserted in single bcc Fe lattice, the clustering process of the formed SIAs with presence of helium cluster has been simulated with MD methods at room temperatures with the new fitted Fe-He potential. The first SIA is formed after 6 He atoms being inserted without vacancy. The simulations indicate that the SIA has mainly two configurations as either a dumbbell or a crowdion, which can be exchanged in the interface between helium bubble and matrix atoms. The SIA cluster can change direction and absorb more SIAs to grow. Small dislocation loops have been observed to form with Burgers vector b = 1/2 a0 on a {111} habit plane. The kinetic process of formation and growth of dislocation loop explored by MD simulations includes: (1) the formation of a self-interstitial atom by the high pressure of the helium cluster/bubble; (2) the diffusion of these self-interstitial atoms on the interface between helium bubble and matrix; (3) the clustering of the self-interstitial atoms in the form of a dislocation loop and its diffusion away from bubble when the number of SIAs in loop reaches a critical number. Moreover, the effect of grain boundary (GB) on the formation of helium clusters has been explored with MD simulations in symmetrical GBs and normal nano-grain boundary samples. Helium atoms can be trapped by GBs at free spaces. The local atomic excess free volume (LAEFV) is found to the one of the main parameters not only related with the energy state of GB but also with the nucleation and growth of He atoms in the GB.

EPFL2011

Computational characteristics and hardware implications of brain tissue simulations

Francesco Cremonesi

Understanding the link between the brain's anatomy and its function through computer simulations of neural tissue models is a widely used approach in computational neuroscience. This technique enables rapid prototyping and testing of hypotheses, allowing researchers to bridge the scales of biological phenomena. Until recently, the constant trend of improvement in computational power has supported an exponential growth in the scale and level of detail of in silico experiments. However, a systematic characterization of the performance landscape has not yet been carried out. In this work we intend to capture intrinsic computational properties of the existing mod- elling abstractions and answer questions about the intricate relationship between simulation algorithms and modern hardware architecture. Our first contribution is a novel set of hardware- agnostic metrics that enables us to bring focus to the heterogeneous landscape of brain tissue models. We develop a methodology able to capture subtle differences between cell-based models and quantify their impact on performance based on hardware features. We show that lumping simulation experiments together by referring to numbers of neurons and synapses without further detail hides fundamental differences in computational and hardware require- ments across models. In addition to analysing different neuron representations, we investigate the impact of biological heterogeneity on the performance of a cortical microcircuit model. Our analysis indicates that while general-purpose computers have until now sustained high- performance simulations of all brain tissue models, the next generation of in silico models will require hardware tailored to the underlying abstraction. We find that all formalisms saturate the memory bandwidth with a fairly small number of shared memory threads, but the reasons behind this are quite different: conductance-based models are dominated by the large memory traffic of clock-driven kernels, while current-based models are most affected by event-driven execution and memory latency. In distributed simulations the latency of the interconnect fabric is the root cause for a significant degradation in performance. We argue that performance analyses such as ours are required to enable the next generation of brain tissue simulations - or else scientific progress risks being hindered by the presence of severe hardware bottlenecks. Our methodology provides a common tool to facilitate the communication between modellers, developers and hardware designers in order to sustain the larger memory and performance requirements of future brain tissue simulations.

EPFL2019

Computational characteristics and hardware implications of brain tissue simulations

Francesco Cremonesi

EPFL2019

EPFL2011