An object-oriented model for adaptive high-performance computing on the computational GRID

Tuan Anh Nguyen
EPFL, 2005
EPFL thesis

Abstract

The dissertation presents a new parallel programming paradigm for developing high performance (HPC) applications on the Grid. We address the question "How to tailor HPC applications to the Grid?" where the heterogeneity and the large scale of resources are the two main issues. We respond to the question at two different levels: the programming tool level and the parallelization concept level. At the programming tool level, the adaptation of applications to the Grid environment consists of two forms: either the application components should somehow decompose dynamically based on the available resources; or the components should be able to ask the infrastructure to select automatically the suitable resources by providing descriptive information about the resource requirements. These two forms of adaptation lead to the parallel object model on which resource requirements are integrated into shareable distributed objects under the form of object descriptions. We develop a tool called ParoC++ that implements the parallel object model. ParoC++ provides a comprehensive object-oriented infrastructure for developing and integrating HPC applications, for managing the Grid environment and for executing applications on the Grid. At the parallelization concept level, we investigate the parallelization scheme which provides the user a method to express the parallelism to satisfy the user specified time constraints for a class of problems with known (or well-estimated) complexities on the Grid. The parallelization scheme is constructed on the following two principal elements: the decomposition tree which represents the multi-level decomposition and the decomposition dependency graph which defines the partial order of execution within each decomposition. Through the scheme, the parallelism grain will be automatically chosen based on the available resources at run-time. The parallelization scheme framework has been implemented using the ParoC++. This framework provides a high level abstraction which hides all of the complexities of the Grid environment so that users can focus on the "logic" of their problems. The dissertation has been accompanied with a series of benchmarks and two real life applications from image analysis for real-time textile manufacturing and from snow simulation and avalanche warning. The results show the effectiveness of ParoC++ on developing high performance computing applications and in particular for solving the time constraint problems on the Grid.

Official source

https://infoscience.epfl.ch/record/33548?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

Tuan Anh Nguyen
EPFL, 2005
EPFL thesis

Abstract

Official source

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

About this result

Related concepts (25)

Related concepts

Related publications (4)

Related publications

Related publications (4)

Adding limited reconfigurability to superscalar processors

Marc Epalza

For the last thirty years, electronics, at first built with discrete components, and then as Integrated Circuits (IC), have brought diverse and lasting improvements to our quality of life. Examples might include digital calculators, automotive and airplane control assistance, almost all electrical household appliances, and the almost ubiquitous Personal Computer. Application-Specific Integrated Circuits (ASICs) were traditionally used for their high performance and low manufacturing cost, and were designed specifically for a single application with large volumes. But as lower product lifetimes and the pressures of fast marketing increased, ASICs' high design cost pushed for their replacement by Microprocessors. These processors, capable of implementing any functionality through a change in software, are thus often called General Purpose Processors. General purpose processors are used for everyday computing tasks, and found in all personal computers. They are also often used as building blocks for scientific supercomputers. Superscalar processors such as these require ever more processing power to run complex simulations, video games or versatile telecoms services. In the case of embedded applications, e.g. for portable devices, both performance and power consumption must be taken into account. In a bid to adapt a processor to some extent to select applications, fully reconfigurable logic can greatly improve the performance of a processor, since it is shaped for the best possible execution with the available resources. However, as reconfigurable logic is far slower than custom logic, this gain is possible only for some specific applications with large parallelism, after a detailed study of the algorithm. Even though this process can be automated, it still requires large computing resources, and cannot be performed at run time. To reduce the loss in speed compared to custom logic, it is possible to limit the reconfigurability to increase the breadth of applications where performance can be improved. However, as the application space increases, a careful analysis and design of the reconfigurability is required to minimize the speed loss, notably when dynamic reconfiguration is considered. As a case study, we analyze the feasibility of adding limited reconfigurability to the Floating Point Units (FPUs) of a general purpose processor. These rather large units execute all floating point operations, and may also be used for integer multiplication. If an application contains few or infrequent instructions that must be executed by the FPU, this idle hardware only increases power consumption without enhancing performance. This is often the case in non-scientific applications and even many recent and detailed video games which make heavy use of hardware display accelerators for 3D graphics. In a fast multiplier such as can be found in the FPU of a high performance processor, the logic to perform multiplication is a large tree of compressors to add all the partial products together. It is possible to add logic to allow the reconfiguration of part of this tree as several extra Arithmetic and Logic Units (ALU). This requires a detailed timing analysis for both the reconfigurable FPU and the extra ALUs, taking into account effects such as added wires and longer critical paths. Finally, the algorithm to decide when and how to reconfigure must be studied, in terms of eciency and complexity. The results of adding this limited reconfigurability to a mainstream superscalar processor over a large set of compute intensive benchmarks show gains of up to 56% in the best case, with an average gain of 11%. The application to an idealized huge top processor still shows slightly positive average gains, as the limits of available parallelism are reached, bounded by both the application and many of the characteristics of the processor. In all cases, binary compatibility is maintained, allowing the re-use of all existing software. We show that adding limited reconfigurability to a general purpose superscalar processor can produce interesting gains over a wide range of applications while maintaining binary compatibility, and without large modifications to the original design. Limited reconfigurability is worthwhile as it increases the design space, allowing gains to apply to a larger set of applications. These gains are achieved through careful study and optimization of the reconfigurable logic and the decision algorithm.

EPFL2004

Rigid body dynamics simulation for robot motion planning

Alan Ettlin

The development of robot motion planning algorithms is inherently a challenging task. This is more than ever true when the latest trends in motion planning are considered. Some motion planners can deal with kinematic and dynamic constraints induced by the mechanical structure of the robot. Another class of motion planners fulfill various types of optimality conditions, yet others include means of dealing with uncertainty about the robot and its environment. Sensor-based motion planners gather information typically afflicted with errors about a partially known environment in order to plan a trajectory therein. In another research area it is investigated how multiple robots best cooperate to solve a common task. In order to deal with the complexity of developing motion planning algorithms, it is proposed in this document to resort to a simulation environment. The advantages of doing so are outlined and a system named Ibex presented which is well suited to support motion planner development. The developed framework makes use of rigid body dynamics algorithms as simulation kernel. Further, various components are included which integrate the simulation into existing engineering environments. Simulation content can be conveniently developed through extensions of well-established 3D modelling tools. The co-simulation with components from other domains of physics is provided by the integration into a leading dynamic modelling environment. Robotic actuator models can be combined with a rigid body dynamics simulation using this mechanism. The same configuration also allows to conveniently develop control algorithms for a rigid body dynamics setup and offers powerful tools for handling and analysing simulation data. The developed simulation framework also offers physics-based models for simulating various sensors, most prominently a model for sensor types based on wave propagation, such as laser range finding devices. Application examples of the simulation framework are presented from the mobile robotics rough-terrain motion planning domain. Three novel rough-terrain planning algorithms are presented which are extensions of known approaches. To quantify the navigational difficulty on rough terrain, a new generic measure named "obstacleness" is proposed which forms the basis of the proposed algorithms. The first algorithm is based on Randomised Potential Field Planners (RPP) and consequently is a local algorithm. The second proposed planner extends RRTconnect , a bi-directional Rapidly Exploring Random Tree (RRT) algorithm and biases exploration of the search space towards easily traversable regions. The third planner is an extension of the second approach and uses the same heuristic to grow a series of additional local RRTs. This allows it to plan trajectories through complex distributions of navigational difficulty benefitting from easy regions throughout the motion plan. A complete example is shown in which the proposed algorithms form the basis for sensor-based dynamic re-planning simulated in the presented framework. In the scenario, a simulated planetary rover navigates a long distance over rough terrain while gathering sensor data about the terrain topography. Where obstacles are sensed which interfere with the original motion plan, dynamic re-planning routines are applied to circumnavigate the hindrances. In the course of this document a complete simulation environment is presented by means of a theoretical background and application examples which can significantly support the development of robot motion planning algorithms. The framework is capable of simulating setups which fulfil the requirements posed by stateof-the-art motion planning algorithm development.

EPFL2006

In nuclear safety, most severe accident scenarios lead to the presence of fission products in aerosol form in the closed containment atmosphere. It is important to understand the particle depletion process to estimate the risk of a release of radioactivity to the environment should a containment break occur. As a model for the containment, we use the three-dimensional differentially heated cavity (DHC) problem. DHC is a cubical box with a hot wall and a cold wall on vertical opposite sides. On the other walls of the cube we have adiabatic boundary conditions. For the velocity field the no-slip boundary condition is valid. The flow of the air in the cavity is described by the Boussinesq equations. Complex flow patterns develop and the flow characteristics depend on the non-dimensional Rayleigh and Prandtl numbers. The predominant flow type in the DHC is a turbulent natural convection flow. This work aims at reaching Rayleigh numbers and turbulent levels as high as possible given the available computational resources. The method used to simulate the turbulent flow is the large eddy simulation (LES) where the dynamics of the large eddies is resolved by the computational grid and the small eddies are modelled by the introduction of subgrid scale quantities using a filter function. Numerically, the LES equations are discretized by the spectral element method. Particle trajectories are computed using the Lagrangian particle tracking method, including the relevant forces (drag, gravity, thermophoresis). Four different particle sets with each set containing one million particles and diameters of 10 μm, 15 μm, 25 μm and 35 μm are simulated. The complexity and the size of the large three-dimensional problem requires the use of massively parallel supercomputers. Spectral element methods are naturally suitable for parallelisation by distributing the elements among the processors. For the Lagrangian particle tracking we use a method where equal numbers of particles are assigned to every processor. The flow field is broadcast and every particle processor tracks the assigned particles, a procedure which leads to a perfect load balancing. Simulation results for the flow field and particle sizes from 15 μm to 35 μm at a Rayleigh number of 109 are compared to previous results from a direct numerical simulation. First order statistics of the LES flow fields are in very good agreement with the direct numerical simulation while the agreement of second order moments is fair. Also the turbulent structures associated to the maximum of turbulent kinetic energy production are correctly reproduced. Particle statistics in the LES and the direct numerical simulation were similar and the settling rates practically identical. Contrary to previous particle simulations in LES, it was found that no model was necessary for the influence of the unresolved flow scales on the particle motions. This can be explained, because the important settling mechanism is through gravity and particle deposition at the walls by turbophoresis is negligible.

EPFL2012