HIGH PERFORMANCE SCIENTIFIC AND ENGINEERING COMPUTING Hardware/Software Support THE KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE HIGH PERFORMANCE SCIENTIFIC AND ENGINEERING COMPUTING Hardware/Software Support edited by Laurence Tianruo Yang St. Francis Xavier University Canada YiPan Georgia State University U.S.A. SPRINGER SClENCE+BUSINESS MEDIA, LLC Library of Congress Cataloging-in-Publication HIGH PERFORMANCE SCIENTIFIC AND ENGINEERING COMPUTING: Hardware/Software Support edited by Laurence Tianruo Yang and Yi Pan ISBN 978-1-4419-5389-6 ISBN 978-1-4757-5402-5 (eBook) DOI 10.1007/978-1-4757-5402-5 Copyright © 2004 by Springer Science+Business Media New York OriginalIy published by Kluwer Academic Publishers in 2004 AlI rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photo-copying, microfilming, recording, or otherwise, without the prior written permission of the publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Printed an acid-free paper. Contents Preface xi Part I Compilation and Architectural Support Multithreaded Parallelism with OpenMP 3 Raimi A. Rufai, Muslim Bozyigit, Jarallah S. AlGhamdi, and Moataz Ahmed 1 Introduction 3 2 Background 5 3 Performance Studies 8 4 Conclusion and Further Work 10 Appendix: Source Listing 12 2 Linear Data Distribution based on Index Analysis 15 Minyi Guo 1 Introduction 15 2 Overview of Data Distribution 16 3 Motivation 17 4 Linear Data Distribution 18 5 Index Conversion and Iteration Space Conversion 24 6 Experimental Results for Linear Distribution 26 7 Summary 28 3 Quantification of Memory Communication 31 Surendra Byna, Kirk W. Cameron and Xian-He Sun 1 Introduction 31 2 Related Work 33 3 Motivating Example 34 4 Experimental Details 36 5 Quantifying Communication Cost 37 6 Identifying Memory Communication Buffers 39 7 Conclusions and Future Work 42 4 The Need for Adaptive Dynamic Thread Scheduling 45 Chulho Shin, Seong-Won Lee and Jean-Lue Gaudiot 1 Introduction 46 2 Related Work 47 3 Adaptive Dynamic Thread Scheduling with the Detector Thread 48 vi HIGH PERFORMANCE SCIENTIFIC AND ENGINEERING COMPUTING 4 Methodology 52 5 Experimental Results 55 6 Summary and Conclusion 58 Part II Numerical Computation 5 Performance Analysis of a BiCGSTAB Solver for Multiple-Marine-Pro- 63 peller Simulation with Several MPI Libraries and Platforms Pengfei Liu and Kun Li 1 Introduction 63 2 Computational Configurations 65 3 Using the MPI Libraries 67 4 Results and Discussion 71 5 Conclusions 77 6 A New BLAS-3 Based Parallel Algorithm for Computing the Eigenvectors 79 of Real Symmetric Matrices Yusaku Yamamoto and Mitsuyoshi Igai and Ken Naono 1 Introduction 80 2 Review of the Conventional Inverse Iteration Method 81 3 The Householder Inverse Iteration Method 83 4 The Blocked Algorithm 86 5 Numerical Results 87 6 Conclusion 91 Part III Load Balancing 7 Load Balancing in SPMD Applications: Concepts and Experiments 95 A. Plastino, V. Thome, D. Vianna, R. Costa, and O. T. da Silveira Filho I Introduction 95 2 Classification of Load Balancing Algorithms 96 3 Load Imbalancing Index 99 4 Load Balancing in a Scientific SPMD Application 99 5 Concluding Remarks 106 8 Dynamic Load Balance Strategy: Application to Nonlinear Optics 109 A. Bourgeade and B. Nkonga 1 Introduction 109 2 Nonlinear Maxwell-Lorentz Equations 110 3 Numerical Approach 112 4 Message Passing Approach 115 5 Applications 117 6 Conclusion 124 9 Message-Passing Parallel Adaptive Quantum Trajectory Method 127 R. L. Carino, I. Banicescu and R. K. Vadapalli, C. A. Weatherford and 1. Zhu 1 Introduction 128 2 The Hydrodynamic Formulation of Quantum Mechanics 129 Contents vii 3 Simulation of Wavepacket Dynamics 130 4 The Moving Weighted Least Squares Algorithm 132 5 Loop Scheduling 132 6 Experiments 135 7 Concluding Remarks 137 Part IV Performance Evaluation 10 Verifying Large-Scale System Performance during Installation using Modelling 143 Darren J. Kerbyson, Adolfy Hoisie and Harvey J. Wasserman 1 Introduction 143 2 Performance Modelling 144 3 The Alpha-Server ES45 Supercomputing System 147 4 The Application and the Model 148 5 Use of the SAGE Model to Validate System Performance 148 6 Summary 155 11 Mixed Level Modelling and Simulation of Large Scale HW/SW Systems 157 Murali K. Nethi and James H. Aylor 1 Introduction 157 2 Performance Estimation Techniques 158 3 Our Modelling Approach 160 4 Mixed Level System Simulation Environment 162 5 Preliminary Results 163 6 Conclusions and Future Work 164 Part V Grid Computing 12 Engineering an Autonomic Partitioning Framework for Grid-based SAMR 169 Applications S. Chandra, X. Li, and M. Parashar 1 Introduction 169 2 Problem Description 171 3 ARMaDA: An Autonomic SAMR Partitioning Framework 174 4 An Experimental Evaluation of Autonomic Partitioning Policies 180 5 Summary and Conclusions 185 13 A Resource Discovery Service For a Mobile Agents Based Grid Infrastructure 189 R. Aversa, B. Di Martino, N. Mazzocca and S. Venticinque 1 Introduction 189 2 The Grid And Web Services Models 190 3 A Magda Overview 192 4 The Discovery And Invocation Service 194 5 Related Work 197 14 xDGDL: Towards an XML-based DataGrid Description Language 201 Erich Schikuta Vlll HIGH PERFORMANCE SCIENTIFIC AND ENGINEERING COMPUTING 1 Introduction 201 2 A Novel File Hierarchy 202 3 xDGDL -the XML Data Grid Description Language 205 4 A Practical xDGDL Example 209 5 An Application of xDGDL 211 6 Conclusions and Future Work 212 Part VI Scientific and Engineering Applications 15 A Large-scale MD Simulation for Formation Process of Carbon Cluster 217 on a Parallel Computer Ryoko Hayashi, Kenji Tanaka, Susumu Horiguchi and Yasuaki Hiwatari 1 Introduction 218 2 Basic information 218 3 Parallelization Process 225 4 Parallelization Results 227 5 Approximation of Execution Times and Outstanding Problems 229 6 Conclusion 230 16 Comparing Various Parallelizing Approaches for Tribology Simulations 231 V. Chaudhary, W. L. Hase, H. Jiang, L. Sun, and D. Thaker 1 Introduction 231 2 Parallelization Approaches 233 3 Molecular Dynamics 238 4 Experiments and Analysis 242 5 Conclusion and Future Work 244 Appendix: A. Sequential Code 249 Appendix: B. OpenMP Code 251 Appendix: C. MPI Code 251 Appendix: D. Strings DSM Code 252 17 High Performance Air Pollution Simulation on Shared Memory Systems 253 Mar(a J. Mart(n, Marta Parada and Ramon Doallo 1 Introduction 253 2 Air Pollution Modelling 254 3 Sequential Profile ofthe STEM-II Program 255 4 Optimization of the Sequential Code 258 5 Parallel Code Using OpenMP 261 18 An Ant Colony Optimization Based Routing Algorithm in Mobile Ad hoc 267 Networks and its Parallel Implementation Parimala Thulasiraman, Ruppa K. Thulasiram, and Mohammad T. Islam 1 Introduction 268 2 Background 269 3 Parallel ACO Routing Algorithm 273 4 Experimental Results 277 5 Conclusions 280 ~~~ ~ 19 Parallelizing Serializable Transactions Based on Transaction Classifica- 285 tion in Real-time Database Systems Subhash Bhalla and Masaki Hasegawa 1 Introduction 285 2 Nature of Delays 286 3 The Proposed Model 288 4 Definitions for Real-time Database System 290 5 Ordering of Transactions in a Distributed System 291 6 An Algorithm to Construct LAG 292 7 Performance Evaluation 294 8 Summary and Conclusions 297 20 Adaptive Selection of Materialized Queries in a Mediator for the Integra- 299 tion of Distributed Information Resources Kil Hong Joo and Won Suk Lee 1 Introduction 299 2 Related Work 301 3 Decayed Usage Patterns 303 4 Implementation Plans 305 5 Experiments and Analysis of Results 310 6 Conclusion 312 Index 315 Preface The field of high performance computing has obtained prominence through advances in electronic and integrated technologies beginning in the 1940s. Cur rent times are very exciting and the years to come will witness a proliferation in the use of parallel and distributed systems. The scientific and engineering application domains have a key role in shaping future research and development activities in academia and industry, especially when the solution of large and complex problems must cope with tight timing schedules. This book contains selected best papers on hardware/software support for high performance scientific and engineering computing from prestigious work shops such as PACT-SHPSEC, IPDPS-PDSECA and ICPP-HPSECA with some invited papers from prominent researchers around the world. The book is ba sically divided into six main sections. We believe all of these chapters and topics not only provide novel ideas, new results and state-of-the-art techniques in this field, but also stimulate the future research activities in the area of high performance computing for science and engineering applications. We would like to share them with our readers. Part 1: compilation and architectural support In chapter 1, Rufai et al. present OpenMP shared memory programming as a viable alternative and a much simpler way to write multithreaded programs. Guo proposes a linear data distribution technique in chapter 2, which extends the traditional block or cyclic distribution for intra-dimension as in HPF, to permit partitioning the array elements along slant lines on distributed-memory machine. Chapter 3 studies the communication issue in parallel applications. Byna et al. present a methodology for classifying the effects ofd ata size and data distribution on hardware, middleware, and application software performance. In chapter 4, Shin et al. propose an adaptive dynamic thread scheduling ap proach that partially schedules threads in the form of a detector thread at a nominal hardware and software cost. Part 2: numerical computation In chapter 5, Liu et al. describe performance analysis of a BiCGSTAB solver for Multiple-Marine-Propeller simulation with several MPI libraries and platforms. Yamamoto et al. present a new BLAS-3 based parallel algorithm for computing the eigenvectors of real symmetric matrices in chapter 6. Part 3: load balancing Chapter 7 by Plastino et al. deals with concepts and experiments related to load balancing in SPMD applications. Bourgeade et al. in chapter 8 present an efficient dynamic load balance strategy for the numerical computation of pulse propagation in nonlinear dispersive optical media. The work described