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

ISBN-13: 9783540634409 / Angielski / Miękka / 1997 / 1382 str.

Christian Lengauer; Martin Griebl; Sergei Gorlatch

Opis

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.

Spis treści

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-machines.- Rescheduling support for mapping dynamic scientific computation onto distributed memory multiprocessors.- Versatile task scheduling of binary trees for realistic machines.- Load balancing issues in the prepartitioning method.- Design of novel load-balancing algorithms with implementations on an IBM SP2.- Repartitioning of adaptive meshes: Experiments with multilevel diffusion.- On the embedding of refinements of 2-dimensional grids.- Dynamic program description as a basis for runtime optimization.- Workshop 16: Performance evaluation and prediction.- Workload analysis of computation intensive tasks: Case study on SPEC CPU95 benchmarks.- Statistical performance modeling: Case study of the NPB 2.1 results.- A general performance model for multistage interconnection networks.- Simulation of a routing algorithm using distributed simulation techniques.- Message-passing performance of parallel computers.- Prefetching and multithreading performance in bus-based multiprocessors with Petri Nets.- On synchronisation in fault-tolerant data and compute intensive programs over a network of workstations.- Performance analysis of a parallel program for wave propagation simulation.- Bounding the minimal completion time of static mappings of multithreaded solaris programs.- Workshop 17: Instruction-level parallelism.- The performance potential of value and dependence prediction.- An enhanced two-level adaptive multiple branch prediction for superscalar processors.- The effect of the speculation depth on the performance of superscalar architectures.- Allocating lifetimes to queues in software pipelined architectures.- Treegion scheduling for highly parallel processors.- Modulo scheduling with cache reuse information.- Memory address prediction for data speculation.- A realistic study on multithreaded superscalar processor design.- A limitation study into access decoupling.- Workshop 18: Parallel and distributed database systems.- Load balanced query evaluation in shared-everything environments.- Exploring load balancing in parallel processing of recursive queries.- Use of a semantically grained database system for distribution and control within design environments.- Method transformations for vertical partitioning in parallel and distributed object databases.- Benchmarking and performance tuning of multimedia servers.- Database program mapping onto a shared-nothing multiprocessor architecture: Minimizing communication costs.- Large join order optimization on parallel shared-nothing database machines using genetic algorithms.- Workshop 19: Symbolic computation.- Using the parallel Karatsuba algorithm for long integer multiplication and division.- Towards full prolog on a distributed architecture.- Improving distributed unification through type analysis.- Static granularity optimization of a committed-choice language Fleng.- Distributed arrays in the functional language concurrent clean.- Design and implementation of parallel TRAM.- Changing the distribution depth during a parallel tree search.- Workshop 19: Symbolic Computation Abstract And-Parallel Machines.- Workshop 20: Real-time systems and constraints.- Designing an embedded hard real-time system: A case study.- Reactive real-time programming with distributed agents.- An Ml-like module system for the synchronous language Signal.- Synchronous thread management in a distributed operating system's micro kernel.- Task-system analysis using slope-parametric hybrid automata.- A methodology for compilation of high-integrity real-time programs.- Schedulers for age constraint tasks and their performance evaluation.- Analyzing schedulability of astral specifications using extended timed automata.- Deriving annotations for tight calculation of execution time.- Cinderella: A retargetable environment for performance analysis of real-time software.- Esprit projects on high-performance computing and networking.- PHASE and MICA: Application specific metacomputing.- FRONTIER: Use of HPCN technologies.- PINEAPL: A European project to develop a parallel numerical library for industrial applications.- RAIN: Redundant array of inexpensive workstations for neurocomputing.- PARSAR: Parallelisation of a chirp scaling algorithm SAR processor.- OCEANS: Optimizing compilers for embedded applications.- SEEDS — Simulation environment for the evaluation of distributed traffic control systems.- EFTOS: A software framework for more dependable embedded HPC applications.- STAMPAR: A parallel processing approach for the explicit dynamic analysis of sheet stamping problems.