Automatic parallel code generation for message passing on distributed memory systems

The availability of a very accurate dependence graph for a scalar code is the basis for the automatic generation of an efficient parallel implementation. The strategy for this task which is encapsulated in a comprehensive data partitioning code generation algorithm is described. This algorithm involves the data partition, calculation of assignment ranges for partitioned arrays, addition of a comprehensive set of execution control masks, altering loop limits, addition and optimisation of communications for all data. In this context, the development and implementation of strategies to merge communications wherever possible has proved an important feature in producing efficient parallel implementations for numerical mesh based codes. The code generation strategies described here are embedded within the Computer Aided Parallelisation tools (CAPTools) software as a key part of a toolkit for automating as much as possible of the parallelisation process for mesh based numerical codes. The algorithms used enables parallelisation of real computational mechanics codes with only minor user interaction and without any prior manual customisation of the serial code to suit the parallelisation tool.

Integrating user knowledge with information from parallelisation tools to facilitate the automatic generation of efficient parallel FORTRAN code

User supplied knowledge and interaction is a vital component of a toolkit for producing high quality parallel implementations of scalar FORTRAN numerical code. In this paper we consider the necessary components that such a parallelisation toolkit should possess to provide an effective environment to identify, extract and embed user relevant user knowledge. We also examine to what extent these facilities are available in leading parallelisation tools; in particular we discuss how these issues have been addressed in the development of the user interface of the Computer Aided Parallelisation Tools (CAPTools). The CAPTools environment has been designed to enable user exploration, interaction and insertion of user knowledge to facilitate the automatic generation of very efficient parallel code. A key issue in the user's interaction is control of the volume of information so that the user is focused on only that which is needed. User control over the level and extent of information revealed at any phase is supplied using a wide variety of filters. Another issue is the way in which information is communicated. Dependence analysis and its resulting graphs involve a lot of sophisticated rather abstract concepts unlikely to be familiar to most users of parallelising tools. As such, considerable effort has been made to communicate with the user in terms that they will understand. These features, amongst others, and their use in the parallelisation process are described and their effectiveness discussed.

The Exodus evacuation model applied to building evacuation scenarios

The purpose of this paper is to demonstrate the potential of the EXODUS evacuation model in building environments. The latest PC/workstation version of EXODUS is described and is also applied to a large hypothetical supermarket/restaurant complex measuring 50 m x 40 m. A range of scenarios is presented where population characteristics (such as size, individual travel speeds, and individual response times), and enclosure configuration characteristics (such as number of exits, size of exits, and opening times of exits) are varied. The results demonstrate a wide range of occupant behavior including overtaking, queuing, redirection, and conflict avoidance. Evacuation performance is measured by a number of model predicted parameters including individual exit flow rates, overall evacuation flow rates, total evacuation time, average evacuation time per occupant, average travel distance, and average wait time. The simulations highlight the profound impact that variations in individual travel speeds and occupant response times have in determining the overall evacuation performance. 1. Jin, T., and Yamada T., "Experimental Study of Human Behavior in Smoke Filled Corridors," Proceedings of The Second International Symposium on Fire Safety Science, 1988, pp. 511-519. 2. Galea, E.R., and Galparsoro, J.M.P., "EXODUS: An Evacuation Model for Mass Transport Vehicles," UK CAA Paper 93006 ISBN 086039 543X, CAA London, 1993. 3. Galea, E.R., and Galparsoro, J.M.P., "A Computer Based Simulation Model for the Prediction of Evacuation from Mass Transport Vehicles," Fire Safety Journal, Vol. 22, 1994, pp. 341-366. 4. Galea, E.R., Owen, M., and Lawrence, P., "Computer Modeling of Human Be havior in Aircraft Fire Accidents," to appear in the Proceedings of Combus tion Toxicology Symposium, CAMI, Oklahoma City, OK, 1995. 5. Kisko, T.M. and Francis, R.L., "EVACNET+: A Computer Program to Determine Optimal Building Evacuation Plans," Fire Safety Journal, Vol. 9, 1985, pp. 211-220. 6. Levin, B., "EXITT, A Simulation Model of Occupant Decisions and Actions in Residential Fires," Proceedings of The Second International Symposium on Fire Safety Science, 1988, pp. 561-570. 7. Fahy, R.F., "EXIT89: An Evacuation Model for High-Rise Buildings," Pro ceedings of The Third International Sym posium on Fire Safety Science, 1991, pp. 815-823. 8. Thompson, P.A., and Marchant, E.W., "A Computer Model for the Evacuation of Large Building Populations," Fire Safety Journal, Vol. 24, 1995, pp. 131-148. 9. Still, K., "New Computer System Can Predict Human Behavior Response to Building Fires," FIRE 84, 1993, pp. 40-41. 10. Ketchell, N., Cole, S.S., Webber, D.M., et.al., "The Egress Code for Human Move ment and Behavior in Emergency Evacu ations," Engineering for Crowd Safety (Smith, R.A., and Dickie, J.F., Eds.), Elsevier, 1993, pp. 361-370. 11. Takahashi, K., Tanaka, T. and Kose, S., "An Evacuation Model for Use in Fire Safety Design of Buildings," Proceedings of The Second International Symposium on Fire Safety Science, 1988, pp. 551- 560. 12. G2 Reference Manual, Version 3.0, Gensym Corporation, Cambridge, MA. 13. XVT Reference Manual, Version 3.0 XVT Software Inc., Boulder, CO. 14. Galea, E.R., "On the Field Modeling Approach to the Simulation of Enclosure Fires, Journal of Fire Protection Engineering, Vol. 1, No. 1, 1989, pp. 11-22. 15. Purser, D.A., "Toxicity Assessment of Combustion Products," SFPE Handbook of Fire Protection Engineering, National Fire Protection Association, Quincy, MA, pp. 1-200 - 1-245, 1988. 16. Hankin, B.D., and Wright, R.A., "Pas senger Flows in Subways," Operational Research Quarterly, Vol. 9, 1958, pp. 81-88. 17. HMSO, The Building Regulations 1991 - Approved Document B, section B 1 (1992 edition), HMSO publications, London, pp. 9-40. 18. Polus A., Schofer, J.L., and Ushpiz, A., "Pedestrian Flow and Level of Service," Journal of Transportation Engineering, Vol. 109, 1983, pp. 46-47. 19. Muir, H., Marrison, C., and Evans, A., "Aircraft Evacuations: the Effect of Passenger Motivation and Cabin Con figuration Adjacent to the Exit," CAA Paper 89019, ISBN 0 86039 406 9, 1989. 20. Muir, H., Private communication to appear as a CAA report, 1996.

Automatic code generation of overlapped communications in a parallelisation tool

This paper addresses the exploitation of overlapping communication with calculation within parallel FORTRAN 77 codes for computational fluid dynamics (CFD) and computational structured dynamics (CSD). The obvious objective is to overlap interprocessor communication with calculation on each processor in a distributed memory parallel system and so improve the efficiency of the parallel implementation. A general strategy for converting synchronous to overlapped communication is presented together with tools to enable its automatic implementation in FORTRAN 77 codes. This strategy is then implemented within the parallelisation toolkit, CAPTools, to facilitate the automatic generation of parallel code with overlapped communications. The success of these tools are demonstrated on two codes from the NAS-PAR and PERFECT benchmark suites. In each case, the tools produce parallel code with overlapped communications which is as good as that which could be generated manually. The parallel performance of the codes also improve in line with expectation.

Hermeneutics, accreting receptions, hypermedia: A tool for reference versus a tool for instruction

We provide a select overview of tools supporting traditional Jewish learning. Then we go on to discuss our own HyperJoseph/HyperIsaac project in instructional hypermedia. Its application is to teaching, teacher training, and self-instruction in given Bible passages. The treatment of two narratives has been developed thus far. The tool enables an analysis of the text in several respects: linguistic, narratological, etc. Moreover, the Scriptures' focality throughout the cultural history makes this domain of application particularly challenging, in that there is a requirement for the tool to encompass the accretion of receptions in the cultural repertoire, i.e., several layers of textual traditions—either hermeneutic (i.e., interpretive), or appropriations—related to the given core passage, thus including "secondary" texts (i.e., such that are responding or derivative) from as disparate realms as Roman-age and later homiletics, Medieval and later commentaries or supercommentaries, literary appropriations, references to the arts and modern scholarship, etc. in particular, the Midrash (homiletic expansions) is adept at narrative gap filling, so the narratives mushroom at the interstices where the primary text is silent. The genealogy of the project is rooted in Weiss' index of novelist Agnon's writings, which was eventually upgraded into a hypertextual tool, including Agnon's full-text and ancillary materials. Those early tools being intended primarily for reference and research-support in literary studies, the Agnon hypertext system was initially emulated in the conception of HyperJoseph, which is applied to the Joseph story from Genesis. Then, the transition from a tool for reference to an instructional tool required a thorough reconception in an educational perspective, which led to HyperIsaac, on the sacrifice of Isaac, and to a redesign and upgrade of HyperJoseph as patterned after HyperIsaac.

The implementation of an aeronautical CFD flow code onto distributed memory parallel systems

The parallelization of an industrially important in-house computational fluid dynamics (CFD) code for calculating the airflow over complex aircraft configurations using the Euler or Navier–Stokes equations is presented. The code discussed is the flow solver module of the SAUNA CFD suite. This suite uses a novel grid system that may include block-structured hexahedral or pyramidal grids, unstructured tetrahedral grids or a hybrid combination of both. To assist in the rapid convergence to a solution, a number of convergence acceleration techniques are employed including implicit residual smoothing and a multigrid full approximation storage scheme (FAS). Key features of the parallelization approach are the use of domain decomposition and encapsulated message passing to enable the execution in parallel using a single programme multiple data (SPMD) paradigm. In the case where a hybrid grid is used, a unified grid partitioning scheme is employed to define the decomposition of the mesh. The parallel code has been tested using both structured and hybrid grids on a number of different distributed memory parallel systems and is now routinely used to perform industrial scale aeronautical simulations. Copyright © 2000 John Wiley & Sons, Ltd.

SMARTFIRE: an integrated computational fluid dynamics code and expert system for fire field modelling

SMARTFIRE, an open architecture integrated CFD code and knowledge based system attempts to make fire field modeling accessible to non-experts in Computational Fluid Dynamics (CFD) such as fire fighters, architects and fire safety engineers. This is achieved by embedding expert knowledge into CFD software. This enables the 'black-art' associated with the CFD analysis such as selection of solvers, relaxation parameters, convergence criteria, time steps, grid and boundary condition specification to be guided by expert advice from the software. The user is however given the option of overriding these decisions, thus retaining ultimate control. SMARTFIRE also makes use of recent developments in CFD technology such as unstructured meshes and group solvers in order to make the CFD analysis more efficient. This paper describes the incorporation within SMARTFIRE of the expert fire modeling knowledge required for automatic problem setup and mesh generation as well as the concept and use of group solvers for automatic and manual dynamic control of the CFD code.

The Shared Memory Parallelisation of an Ocean Modelling Code using an Interactive Parallelisation Toolkit

This paper briefly describes an interactive parallelisation toolkit that can be used to generate parallel code suitable for either a distributed memory system (using message passing) or a shared memory system (using OpenMP). This study focuses on how the toolkit is used to parallelise a complex heterogeneous ocean modelling code within a few hours for use on a shared memory parallel system. The generated parallel code is essentially the serial code with OpenMP directives added to express the parallelism. The results show that substantial gains in performance can be achieved over the single thread version with very little effort.

SOFT – generating highly flexible object code from XML specifications

Many code generation tools exist to aid developers in carrying out common mappings, such as from Object to XML or from Object to relational database. Such generated code tends to possess a high binding between the Object code and the target mapping, making integration into a broader application tedious or even impossible. In this paper we suggest XML technologies and the multiple inheritance capabilities of interface based languages such as Java, offer a means to unify such executable specifications, thus building complete, consistent and useful object models declaratively, without sacrificing component flexibility.

Using an interactive parallelisation toolkit to parallelise an ocean modelling code

This paper describes an interactive parallelisation toolkit that can be used to generate parallel code suitable for either a distributed memory system (using message passing) or a shared memory system (using OpenMP). This study focuses on how the toolkit is used to parallelise a complex heterogeneous ocean modelling code within a few hours for use on a shared memory parallel system. The generated parallel code is essentially the serial code with OpenMP directives added to express the parallelism. The results show that substantial gains in performance can be achieved over the single thread version with very little effort.

An environment for OpenMP code parallelization

This chapter discusses the code parallelization environment, where a number of tools that address the main tasks, such as code parallelization, debugging, and optimization are available. The parallelization tools include ParaWise and CAPO, which enable the near automatic parallelization of real world scientific application codes for shared and distributed memory-based parallel systems. The chapter discusses the use of ParaWise and CAPO to transform the original serial code into an equivalent parallel code that contains appropriate OpenMP directives. Additionally, as user involvement can introduce errors, a relative debugging tool (P2d2) is also available and can be used to perform near automatic relative debugging of an OpenMP program that has been parallelized either using the tools or manually. In order for these tools to be effective in parallelizing a range of applications, a high quality fully inter-procedural dependence analysis, as well as user interaction is vital to the generation of efficient parallel code and in the optimization of the backtracking and speculation process used in relative debugging. Results of parallelized NASA codes are discussed and show the benefits of using the environment.

The ParaWise expert assistant - widening accessibility to efficient and scalable tool Generated OpenMP code

Despite the apparent simplicity of the OpenMP directive shared memory programming model and the sophisticated dependence analysis and code generation capabilities of the ParaWise/CAPO tools, experience shows that a level of expertise is required to produce efficient parallel code. In a real world application the investigation of a single loop in a generated parallel code can soon become an in-depth inspection of numerous dependencies in many routines. The additional understanding of dependencies is also needed to effectively interpret the information provided and supply the required feedback. The ParaWise Expert Assistant has been developed to automate this investigation and present questions to the user about, and in the context of, their application code. In this paper, we demonstrate that knowledge of dependence information and OpenMP are no longer essential to produce efficient parallel code with the Expert Assistant. It is hoped that this will enable a far wider audience to use the tools and subsequently, exploit the benefits of large parallel systems.

Generating OpenMP code using an interactive parallelization environment

Code parallelization using OpenMP for shared memory systems is relatively easier than using message passing for distributed memory systems. Despite this, it is still a challenge to use OpenMP to parallelize application codes in a way that yields effective scalable performance when executed on a shared memory parallel system. We describe an environment that will assist the programmer in the various tasks of code parallelization and this is achieved in a greatly reduced time frame and level of skill required. The parallelization environment includes a number of tools that address the main tasks of parallelism detection, OpenMP source code generation, debugging and optimization. These tools include a high quality, fully interprocedural dependence analysis with user interaction capabilities to facilitate the generation of efficient parallel code, an automatic relative debugging tool to identify erroneous user decisions in that interaction and also performance profiling to identify bottlenecks. Finally, experiences of parallelizing some NASA application codes are presented to illustrate some of the benefits of using the evolving environment.