Euro-Par’97 Parallel Processing Third International Euro-Par Conference, Passau, Germany, August 26–29, 1997, Proceedings

This book constitutes the refereed proceedings of the Third International Euro-Par Conference, held in Passau, Germany, in August 1997.
The 178 revised papers presented were selected from more than 300 submissions on the basis of 1101 reviews. The papers are organized in accordance with the conference workshop structure in tracks on support tools and environments, routing and communication, automatic parallelization, parallel and distributed algorithms, programming languages, programming models and methods, numerical algorithms, parallel architectures, HPC applications, scheduling and load balancing, performance evaluation, instruction-level parallelism, database systems, symbolic computation, real-time systems, and an ESPRIT workshop.

Basis of parallel speculative execution.- Unifying theories for parallel programming.- Automatic parallelization of irregular and pointer-based computations: Perspectives from logic and constraint programming.- Static and dynamic data management in networks.- Iterative algorithms on high performance architectures.- A performance tuning approach for shared-memory multiprocessors.- Workshop 01: Support tools and environments.- Nova visualization for optimization of data-parallel programs.- On correcting the intrusion of tracing non-deterministic programs by software.- Using control and data flow analysis for race evaluation.- Client server computing on message passing systems: Experiences with PVM-RPC.- Exdasy — A user-friendly and extendable data distribution system.- Interconnecting multiple heterogeneous parallel application components.- EDPEPPS: An integrated graphical toolset for the design and performance evaluation of portable parallel software.- Load balancing based on process migration for MPI.- A processors management system for PVM.- A full program control flow representation for real programs.- Workshop 02: Routing and communication in interconnection networks.- Efficient total-exchange in wormhole-routed toroidal cubes.- An analysis of deflection-based wormhole routing with virtual channels.- Wormhole deadlock prediction.- Broadcast and associative operations on fat-trees.- On the fault tolerance of fat-trees.- Minimal routing in the triangular grid and in a family of related tori.- Embedding complete k-ary Trees into 2-dimensional meshes and tori.- Optimal gossip in store-and-forward noncombining 2-D tori.- Cutwidth of the mesh of d-ary trees.- Embedding and emulation results for static multichannel mesh of optical buses.- Routing on asyncronous processor networks.- The complexity of shortest path and dilation bounded interval routing.- Finding a pair on a mesh with multiple broadcasting is hard.- Routing on the PADAM: Degrees of optimality.- Workshop 03: Automatic parallelization and high-performance compilers.- Handling memory cache policy with integer points countings.- A graphical tool for automatic parallelization and scheduling of programs on multiprocessors.- Identifying critical loads in real programs for decoupled VSM systems.- Runtime interprocedural data placement optimisation for lazy parallel libraries (extended abstract).- A technique for mapping sparse matrix computations into regular processor arrays.- A relational approach to the compilation of sparse matrix programs.- Solutions to the communication minimization problem for affine recurrence equations.- Dependence-free clustering of shift-invariant data structures.- Experiences in analyzing data dependences for programs with pointers and structures.- Applicability of program comprehension to sparse matrix computations.- Hamiltonian recurrence for ILP.- Optimizing storage size for static control programs in automatic parallelizers.- Optimal distribution assignment placement.- Workshop 04+08+13: Parallel and distributed algorithms.- Parallel merge sort on concurrent-read owner-write PRAM.- Feasible models of computation: Three-dimensionality and energy consumption.- Sample sort on meshes.- Sorting on a massively parallel system using a library of basic primitives: Modeling and experimental results.- Parallel priority Queue and list contraction: The BSP approach.- Priority queue operations on EREW-PRAM.- Concurrent rebalancing of AVL trees: A fine-grained approach.- NC approximation algorithms for 2-connectivity augmentation in a graph.- Approximating scheduling problems in parallel.- A new staircase separator theorem.- Tentative time warp.- Synchronized DSM models.- A space-efficient and self-stabilizing depth-first token circulation protocol for asynchronous message-passing systems.- Distributed self-stabilizing algorithm for minimum spanning tree construction.- Partly-consistent cuts of databases.- Exploiting atomic broadcast in replicated databases (extended abstract).- Workshop 05+06: Programming languages and concurrent object-oriented programming.- Synchronising asynchronous communications.- Typechecking of Pei expressions.- Functional parallel programming with explicit processes: Beyond SPMD.- Testing semantics for unbounded nondeterminism.- An efficient compilation framework for languages based on a concurrent process calculus.- Behavioural types for a calculus of concurrent objects.- Time in message sequence charts: A formal approach.- Integrating an entry consistency memory model and concurrent object-oriented programming.- Modeling the dynamic behavior of objects on events, messages and methods (extended abstract).- A quality design solution for object synchronization.- NeXeme: A distributed scheme based on Nexus.- Athapascan runtime: Efficiency for irregular problems.- Optimization of out-of-core computations using chain vectors.- Workshop 07: Programming models and methods.- Parlists — A generalization of powerlists.- Skeletons for data parallelism in p31.- Embodying parallel functional skeletons: An experimental implementation on top of MPI.- On dividing and conquering independently.- M-Tree: A parallel abstract data type for block-irregular adaptive applications.- A monadic calculus for parallel costing of a functional language of arrays.- A methodology for deriving parallel programs with a family of parallel abstract machines.- Parallel distributed programming with Haskell+PVM.- A parallelisation approach for supporting scalable and portable computing.- Workshop 09: Parallel numerical algorithms.- Scalability of parallel sparse Cholesky factorization.- Optimal parallel algorithms for solving tridiagonal linear systems.- Robust parallel Lanczos methods for clustered eigenvalues.- A fully parallel symmetric matrix transformation.- Numerical experiments with a parallel fast direct elliptic solver on Cray T3E.- New matrix-by-vector multiplications based on a nonoverlapping domain decomposition data distribution.- A comparison between different parallelization methods on workstation clusters to solve CFD-problems.- Scalable parallel SSOR preconditioning for lattice computations in gauge theories.- Deteriorating convergence for asynchronous methods on linear least squares problems.- Workshops 10+11+14: Parallel computer architecture and image processing.- The Delft-Java engine: An introduction.- Scheduling instructions with uncertain latencies in asynchronous architectures.- Co-processor system design for fine-grain message handling in KUMP/D.- A virtual-physical on-chip cache for shared memory multiprocessors.- Shared vs. snoop: Evaluation of cache structure for single-chip multiprocessors.- Morphological hough transform on the instruction systolic array.- An analytical design of high-speed pixel transformation for object boundary enhancement.- Karhünen-Loève transform: An exercise in simple image-processing parallel pipelines.- Use of F-code as a very high level intermediate laguage for DSP.- Workshop 12: Applications of high-performance computing.- Experiments on using WPVM for industrial visual inspection problems.- Object-oriented parallel software for radio wave propagation simulation in urban environment.- A portable parallel implementation of a 3D semiconductor device simulator.- A parallel sparse LU decomposition with application to semiconductor device simulation.- A parallel simulation of a quantitative large-strain polycrystal deformation.- Parallel genetic algorithms applied to optimum shape design in aeronautics.- Parallel multidimensional calculation of steady-state and time-dependent flows with combustion.- A two-level parallel strategy for rotorcraft optimization and design.- Workshop 15: Scheduling and load balancing.- Performance comparison of load balancing policies based on a diffusion scheme.- Effectively scheduling parallel tasks and communications on networks of workstations.- On linear schedules of task graphs for generalized logp-machin