Euro-Par' 99 Parallel Processing : 5th International Euro-Par Conference Toulouse, France, August 31-September 3, 1999 Proceedings

Euro-Parisaninternationalconferencededicatedtothepromotionandadvan- ment of all aspects of parallel computing. The major themes can be divided into the broad categories of hardware, software, algorithms and applications for p- allel computing. The objective of Euro-Par is to provide a forum within which to promote the development of parallel computing both as an industrial te- nique and an academic discipline, extending the frontier of both the state of the art and the state of the practice. This is particularly important at a time when parallel computing is undergoing strong and sustained development and experiencing real industrial take-up. The main audience for and participants in Euro-Parareseenasresearchersinacademicdepartments,governmentlabora- ries and industrial organisations. Euro-Par’s objective is to become the primary choice of such professionals for the presentation of new results in their specic areas. Euro-Par is also interested in applications which demonstrate the e - tiveness of the main Euro-Par themes. There is now a permanent Web site for the series http://brahms. fmi. uni-passau. de/cl/europar where the history of the conference is described. Euro-Par is now sponsored by the Association of Computer Machinery and the International Federation of Information Processing. Euro-Par’99 The format of Euro-Par’99follows that of the past four conferences and consists of a number of topics eachindividually monitored by a committee of four. There were originally 23 topics for this year’s conference. The call for papers attracted 343 submissions of which 188 were accepted. Of the papers accepted, 4 were judged as distinguished, 111 as regular and 73 as short papers.

Invited Talks.- Some Parallel Algorithms for Integer Factorisation.- MERCATOR, the Mission.- Adaptive Scheduling for Task Farming with Grid Middleware.- Applying Human Factors to the Design of Performance Tools.- Building the Teraflops/Petabytes Production Supercomputing Center.- A Coming of Age for Beowulf-Class Computing.- Topic 01.- Support Tools and Environments.- Systematic Debugging of Parallel Programs in DIWIDE Based on Collective Breakpoints and Macrosteps1.- Project Workspaces for Parallel Computing - The TRAPPER Approach.- PVMbuilder - A Tool for Parallel Programming.- Message-Passing Specification in a CORBA Environment.- Using Preemptive Thread Migration to Load-Balance Data-Parallel Applications.- A Light-Weight Integrated Programming Environment?.- INTERLACE: An Interoperation and Linking Architecture for Computational Engines.- Multi-protocol Communications and High Speed Networks.- An Online Algorithm for Dimension-Bound Analysis.- Correction of Monitor Intrusion for Testing Nondeterministic MPI-Programs.- Improving the Performance of Distributed Shared Memory Environments on Grid Multiprocessors.- Topic 02.- Performance Evaluation and Prediction.- Performance Analysis of Wormhole Switching with Adaptive Routing in a Two-Dimensional Torus.- Message Passing Evaluation and Analysis on Cray T3E and SGI Origin 2000 Systems.- Performance Evaluation and Modeling of the Fujitsu AP3000 Message-Passing Libraries?.- Improving Communication Support for Parallel Applications?.- A Performance Estimator for Parallel Programs.- Min-Cut Methods for Mapping Dataflow Graphs.- Influence of Variable Time Operations in Static Instruction Scheduling?.- Evaluation of LH*LH for a Multicomputer Architecture.- Set Associative Cache Behavior Optimization?.- A Performance Study of Modern Web Server Applications.- An Evaluation of High Performance Fortran Compilers Using the HPFBench Benchmark Suite.- Performance Evaluation of Object Oriented Middleware.- PopSPY: A PowerPC Instrumentation Tool for Multiprocessor Simulation.- Performance Evaluation and Benchmarking of Native Signal Processing.- Topic 03.- Scheduling and Load Balancing.- A Polynomial-Time Branching Procedure for the Multiprocessor Scheduling Problem.- Optimal and Alternating-Direction Load Balancing Schemes.- Process Mapping Given by Processor and Network Dynamic Load Prediction.- Ordering Unsymmetric Matrices into Bordered Block Diagonal Form for Parallel Processing.- Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing.- DRAMA: A Library for Parallel Dynamic Load Balancing of Finite Element Applications?.- Job Scheduling in a Multi-layer Vision System.- A New Algorithm for Multi-objective Graph Partitioning?.- Scheduling Iterative Programs onto LogP-Machine.- Scheduling Arbitrary Task Graphs on LogP Machines.- Scheduling with Communication Delays and On-Line Disturbances.- Scheduling User-Level Threads on Distributed Shared-Memory Multiprocessors?.- Using duplication for the multiprocessor scheduling problem with hierarchical communications.- Topic 04.- Compilers for High Performance Systems.- Storage Mapping Optimization for Parallel Programs.- Array SSA for Explicitly Parallel Programs.- Parallel Data-Flow Analysis of Explicitly Parallel Programs.- Localization of Data Transfer in Processor Arrays.- Scheduling Structured Systems.- Compiling Data Parallel Tasks for Coordinated Execution?.- Flexible Data Distribution in PGHPF.- On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems?.- I/O-Conscious Tiling for Disk-Resident Data Sets.- Post-Scheduling Optimization of Parallel Programs.- Piecewise Execution of Nested Parallel Programs - A Thread-Based Approach.- Topic 05.- Parallel and Distributed Databases.- Distributed Database Checkpointing.- A Generalized Transaction Theory for Database and Non-database Tasks.- On Disk Allocation of Intermediate Query Results in Parallel Database Systems.- Highly Concurrent Locking in Shared Memory Database Systems.- Parallel Processing of Multiple Text Queries on Hypercube Interconnection Networks?.- Topics 06 + 20.- Fault Avoidance and Fault Removal in Real-Time Systems & Fault-Tolerant Computing.- Quality of Service Management in Distributed Asynchronous Real-Time Systems.- Multiprocessor Scheduling of Real-Time Tasks with Resource Requirements.- Designing Multiprocessor/Distributed Real-Time Systems Using the ASSERTS Toolkit.- UML Framework for the Design of Real-Time Robot Controllers.- Software Implemented Fault Tolerance in Hypercube.- Managing Fault Tolerance Transparently Using CORBA Services.- Topic 07.- Theory and Models for Parallel Computation.- Parallel Algorithms for Grounded Range Search and Applications.- Multi-level Cooperative Search: A New Paradigm for Combinatorial Optimization and an Application to Graph Partitioning.- A Quantitative Measure of Portability with Application to Bandwidth-Latency Models for Parallel Computing? (Extended Abstract).- A Cost Model For Asynchronous and Structured Message Passing?.- A Parallel Simulation of Cellular Automata by Spatial Machines.- Topic 08.- High-Performance Computing and Applications.- Null Messages Cancellation Through Load Balancing in Distributed Simulations.- Efficient Load-Balancing and Communication Overlap in Parallel Shear-Warp Algorithm on a Cluster of PCs.- A Hierarchical Approach for Parallelization of a Global Optimization Method for Protein Structure Prediction.- Parallelization of a Compositional Simulator with a Galerkin Coarse/Fine Method?.- Some Investigations of Domain Decomposition Techniques in Parallel CFD.- A Parallel Ocean Model for High Resolution Studies.- Nonoverlapping Domain Decomposition Applied to a Computational Fluid Mechanics Code.- zA PC Cluster with Application-Quality MPI.- Using Network of Workstations to Support a Web-Based Visualization Service.- High-Speed LANs: New Environments for Parallel and Distributed Applications.- Consequences of Modern Hardware Design for Numerical Simulations and Their Realization in FEAST.- A Structured SADT Approach to the Support of a Parallel Adaptive 3D CFD Code.- A Parallel Algorithm for 3D Geometry Transformations in OpenGL.- Parallel Implementation in a Industrial Framework of Statistical Tolerancing Analysis in Microelectronics.- Interaction Between Data Parallel Compilation and Data Transfer and Storage Cost Minimization for Multimedia Applications.- Parallel Numerical Simulation of a Marine Host-Parasite System.- Parallel Methods of Training for Multilayer Neural Network.- Partitioning of Vector-Topological Data for Parallel GIS Operations: Assessment and Performance Analysis.- Topic 09.- Parallel Computer Architecture - What Is Its Future?.- The Algebraic Path Problem Revisited.- Vector ISA Extension for Sparse Matrix-Vector Multiplication.- A Study of a Simultaneous Multithreaded Processor Implementation.- The MorphoSys Parallel Reconfigurable System.- A Graph-Oriented Task Manager for Small Multiprocessor Systems.- Implementing Snoop-Coherence Protocol for Future SMP Architectures.- An Adaptive Limited Pointers Directory Scheme for Cache Coherence of Scalable Multiprocessors.- Two Schemes to Improve the Performance of a Sort-Last 3D Parallel Rendering Machine with Texture Caches.- ManArray Processor Interconnection Network: An Introduction.- Topic 10.- Distributed Systems and Algorithms.- A Cooperation Service for CORBA Objects. From the Model to the Applications?.- Symphony: Managing Virtual Servers in the Global Village?.- Épidaure: A Java Distributed Tool for Building DAI Applications.- A Client/Broker/Server Substrate with 50 ? s Round-Trip Overhead.- Universal Constructs in Distributed Computations.- Illustrating the Use of Vector Clocks in Property Detection: An Example and a Counter-Example.- A Node Count-Independent Logical Clock for Scaling Lazy Release Consistency Protocol.- Mutual Exclusion Between Neighboring Nodes in an Arbitrary System Graph Tree That Stabilizes Using Read/Write Atomicity.- Topic 11.- Parallel Programming: Models, Methods, and Languages.- Exploiting Advanced Task Parallelism in High Performance Fortran via a Task Library.- A Run-Time System for Dynamic Grain Packing.- Optimising Skeletal-Stream Parallelism on a BSP Computer.- Parallel Programming by Transformation.- Condensed Graphs: A Multi-level, Parallel, Intermediate Representation?.- A Skeleton for Parallel Dynamic Programming.- Programming Effort vs. Performance with a Hybrid Programming Model for Distributed Memory Parallel Architectures.- DAOS — Scalable And-Or Parallelism.- Write Detection in Home-Based Software DSMs?.- D’Caml: Native Support for Distributed ML Programming in Heterogeneous Environment.- ParBlocks - A New Methodology for Specifying Concurrent Method Executions in Opus?.- Static Parallelization of Functional Programs: Elimination of Higher-Order Functions & Optimized Inlining.- A Library to Implement Neural Networks on MIMD Machines?.- Topic 12.- Architectures and Algorithms for Vision and Other Senses.- LUX: An Heterogeneous Function Composition Parallel Computer for Graphics.- A Parallel Accelerator Architecture for Multimedia Video Compression.- A Parallel Architecture for Stereoscopic Processing.- A Robust Neural Network Based Object Recognition System and Its SIMD Implementation.- Multimedia Extensions and Sub-word Parallelism in Image Processing: Preliminary Results.- Vanishing Point Detection in the Hough Transform Space.- Parallel Structure in an Integrated Speech-Recognition Network.- 3D Optoelectronic Fix Point Unit and Its Advantages Processing 3D Data?.- Parallel Wavelet Transforms on Multiprocessors?.- Vector Quantization-Fractal Image Coding Algorithm Based on Delaunay Triangulation.- Topics 13 + 19.- Numerical Algorithms for Linear and Nonlinear Algebra.- mpC + ScaLAPACK = Efficient Solving Linear Algebra Problems on Heterogeneous Networks.- Parallel Subdomain-Based Preconditioner for the Schur Complement.- A Preconditioner for Improved Fermion Actions.- Application of a Class of Preconditioners to Large Scale Linear Programming Problems.- Estimating Computer Performance for Parallel Sparse QR Factorisation.- A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization?.- Scheduling of Algorithms Based on Elimination Trees on NUMA Systems.- Block-Striped Partitioning and Neville Elimination.- A Comparison of Parallel Solvers for Diagonally Dominant and General Narrow-Banded Linear Systems II.- Using Pentangular Factorizations for the Reduction to Banded Form.- Experience with a Recursive Perturbation Based Algorithm for Symmetric Indefinite Linear Systems?.- Parallel Cyclic Wavefront Algorithms for Solving Semidefinite Lyapunov Equations?.- Parallel Constrained Optimization via Distribution of Variables.- Solving Stable Stein Equations on Distributed Memory Computers?.- Convergence Acceleration for the Euler Equations Using a Parallel Semi-Toeplitz Preconditioner.- A Stable and Efficient Parallel Block Gram-Schmidt Algorithm.- On the Extension of the Code GAM for Parallel Computing?.- PAMIHR. A Parallel FORTRAN Program for Multidimensional Quadrature on Distributed Memory Architectures.- Stability Issues of the Wang’s Partitioning Algorithm for Banded and Tridiagonal Linear Systems?.- Topic 14.- Emerging Topics in Advanced Computing in Europe.- The HPF+ Project: Supporting HPF for Advanced Industrial Applications?.- TIRAN: Flexible and Portable Fault Tolerance Solutions for Cost Effective Dependable Applications.- OCEANS - Optimising Compilers for Embedded Applications?.- Cray T3E Performances of a Parallel Code for a Stochastic Dynamic Assets and Liabilities Management Model?.- Parametric Simulation of Multi-body Systems on Networks of Heterogeneous Computers.- Parallel Data Mining in the HYPERBANK Project?.- High Performance Computing for Optimum Design of Multi-body Systems.- Topic 15.- Routing and Communication in Interconnection Networks.- Optimizing Message Delivery in Asynchronous Distributed Applications?.- Circuit-Switched Broadcasting in Multi-port Multi-dimensional Torus Networks?.- Impact of the Head-of-Line Blocking on Parallel Computer Networks: Hardware to Applications?.- Interval Routing on Layered Cross Product of Trees and Cycles?.- Topic 16.- Instruction-Level Parallelism and Uniprocessor Architecture.- Design Considerations of High Performance Data Cache with Prefetching.- Annotated Memory References: A Mechanism for Informed Cache Management.- Understanding and Improving Register Assignment?.- Compiler-Directed Reordering of Data by Cyclic Graph Coloring.- Code Cloning Tracing: A “Pay per Trace” Approach.- Execution-Based Scheduling for VLIW Architectures.- Decoupling Recovery Mechanism for Data Speculation from Dynamic Instruction Scheduling Structure.- Implementation of Hybrid Context Based Value Predictors Using Value Sequence Classification.- Heterogeneous Clustered Processors: Organisation and Design.- An Architecture Framework for Introducing Predicated Execution into Embedded Microprocessors.- Multi-stage Cascaded Prediction.- Mispredicted Path Cache Effects.- Topic 17.- Concurrent and Distributed Programming with Objects.- Non-regular Process Types.- Decision Procedure for Temporal Logic of Concurrent Objects.- Aliasing Models for Object Migration?.- Dynamic Extension of CORBA Servers.- On the Concurrent Object Model of UML*.- Object Oriented Design for Reusable Parallel Linear Algebra Software.- Topic 18.- Global Environment Modelling.- The Parallelization of the Princeton Ocean Model.- Modular Fortran 90 Implementation of a Parallel Atmospheric General Circulation Model.- Implementation of the Limited-Area Numerical Weather Prediction Model Aladin in Distributed Memory.- Parallelization of the French Meteorological Mesoscale Model MésoNH.- The PALM Project: MPMD Paradigm for an Oceanic Data Assimilation Software.- A Parallel Distributed Fast 3D Poisson Solver for Méso-NH.- Porting a Limited Area Numerical Weather Forecasting Model on a Scalable Shared Memory Parallel Computer.- Topic 22.- High Performance Data Mining and Knowledge Discovery.- Mining of Association Rules in Very Large Databases: A Structured Parallel Approach?.- Parallel k/h-Means Clustering for Large Data Sets.- Performance Analysis for Parallel Generalized Association Rule Mining on a Large Scale PC Cluster.- Inducing Load Balancing and Efficient Data Distribution Prior to Association Rule Discovery in a Parallel Environment.- Topic 23.- Symbolic Computation.- Parallelism in Aldor — The Communication Library ?it for Parallel, Distributed Computation.- A Library for Parallel Modular Arithmetic.- Performance Evaluation of Or-Parallel Logic Programming Systems on Distributed Shared-Memory Architectures?.- A Parallel Symbolic Computation Environment: Structures and Mechanics.