Euro-Par'99 Parallel Processing: 5th International Euro-Par Conference, Toulouse, France, August 31 - September 3, 1999, Proceedings (Lecture Notes in Computer Science)

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. Some Parallel Algorithms for Integer Factorisation....Pages 1-22 MERCATOR, the Mission....Pages 23-29 Adaptive Scheduling for Task Farming with Grid Middleware....Pages 30-43 Applying Human Factors to the Design of Performance Tools....Pages 44-60 Building the Teraflops/Petabytes Production Supercomputing Center....Pages 61-77 A Coming of Age for Beowulf-Class Computing....Pages 78-88 Support Tools and Environments....Pages 89-89 Systematic Debugging of Parallel Programs in DIWIDE Based on Collective Breakpoints and Macrosteps1....Pages 90-97 Project Workspaces for Parallel Computing - The TRAPPER Approach....Pages 98-107 PVMbuilder - A Tool for Parallel Programming....Pages 108-112 Message-Passing Specification in a CORBA Environment....Pages 113-116 Using Preemptive Thread Migration to Load-Balance Data-Parallel Applications....Pages 117-124 A Light-Weight Integrated Programming Environment⋆....Pages 125-134 INTERLACE: An Interoperation and Linking Architecture for Computational Engines....Pages 135-138 Multi-protocol Communications and High Speed Networks....Pages 139-143 An Online Algorithm for Dimension-Bound Analysis....Pages 144-153 Correction of Monitor Intrusion for Testing Nondeterministic MPI-Programs....Pages 154-158 Improving the Performance of Distributed Shared Memory Environments on Grid Multiprocessors....Pages 159-162 Performance Evaluation and Prediction....Pages 163-164 Performance Analysis of Wormhole Switching with Adaptive Routing in a Two-Dimensional Torus....Pages 165-172 Message Passing Evaluation and Analysis on Cray T3E and SGI Origin 2000 Systems....Pages 173-182 Performance Evaluation and Modeling of the Fujitsu AP3000 Message-Passing Libraries⋆....Pages 183-187 Improving Communication Support for Parallel Applications⋆....Pages 188-192 A Performance Estimator for Parallel Programs....Pages 193-202 Min-Cut Methods for Mapping Dataflow Graphs....Pages 203-212 Influence of Variable Time Operations in Static Instruction Scheduling⋆....Pages 213-216 Evaluation of LH*LH for a Multicomputer Architecture....Pages 217-228 Set Associative Cache Behavior Optimization⋆....Pages 229-238 A Performance Study of Modern Web Server Applications....Pages 239-247 An Evaluation of High Performance Fortran Compilers Using the HPFBench Benchmark Suite....Pages 248-257 Performance Evaluation of Object Oriented Middleware....Pages 258-261 PopSPY: A PowerPC Instrumentation Tool for Multiprocessor Simulation....Pages 262-265 Performance Evaluation and Benchmarking of Native Signal Processing....Pages 266-270 Scheduling and Load Balancing....Pages 271-271 A Polynomial-Time Branching Procedure for the Multiprocessor Scheduling Problem....Pages 272-279 Optimal and Alternating-Direction Load Balancing Schemes....Pages 280-290 Process Mapping Given by Processor and Network Dynamic Load Prediction....Pages 291-294 Ordering Unsymmetric Matrices into Bordered Block Diagonal Form for Parallel Processing....Pages 295-302 Dynamic Load Balancing for Ocean Circulation Model with Adaptive Meshing....Pages 303-312 DRAMA: A Library for Parallel Dynamic Load Balancing of Finite Element Applications⋆....Pages 313-316 Job Scheduling in a Multi-layer Vision System....Pages 317-321 A New Algorithm for Multi-objective Graph Partitioning⋆....Pages 322-331 Scheduling Iterative Programs onto LogP-Machine....Pages 332-339 Scheduling Arbitrary Task Graphs on LogP Machines....Pages 340-349 Scheduling with Communication Delays and On-Line Disturbances....Pages 350-357 Scheduling User-Level Threads on Distributed Shared-Memory Multiprocessors⋆....Pages 358-368 Using duplication for the multiprocessor scheduling problem with hierarchical communications....Pages 369-372 Compilers for High Performance Systems....Pages 373-374 Storage Mapping Optimization for Parallel Programs....Pages 375-382 Array SSA for Explicitly Parallel Programs....Pages 383-390 Parallel Data-Flow Analysis of Explicitly Parallel Programs....Pages 391-400 Localization of Data Transfer in Processor Arrays....Pages 401-408 Scheduling Structured Systems....Pages 409-412 Compiling Data Parallel Tasks for Coordinated Execution⋆....Pages 413-417 Flexible Data Distribution in PGHPF....Pages 418-421 On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems⋆....Pages 422-429 I/O-Conscious Tiling for Disk-Resident Data Sets....Pages 430-439 Post-Scheduling Optimization of Parallel Programs....Pages 440-444 Piecewise Execution of Nested Parallel Programs - A Thread-Based Approach....Pages 445-448 Parallel and Distributed Databases....Pages 449-449 Distributed Database Checkpointing....Pages 450-458 A Generalized Transaction Theory for Database and Non-database Tasks....Pages 459-468 On Disk Allocation of Intermediate Query Results in Parallel Database Systems....Pages 469-476 Highly Concurrent Locking in Shared Memory Database Systems....Pages 477-481 Parallel Processing of Multiple Text Queries on Hypercube Interconnection Networks⋆....Pages 482-486 Fault Avoidance and Fault Removal in Real-Time Systems & Fault-Tolerant Computing....Pages 487-488 Quality of Service Management in Distributed Asynchronous Real-Time Systems....Pages 489-496 Multiprocessor Scheduling of Real-Time Tasks with Resource Requirements....Pages 497-504 Designing Multiprocessor/Distributed Real-Time Systems Using the ASSERTS Toolkit....Pages 505-510 UML Framework for the Design of Real-Time Robot Controllers....Pages 511-514 Software Implemented Fault Tolerance in Hypercube....Pages 515-518 Managing Fault Tolerance Transparently Using CORBA Services....Pages 519-522 Theory and Models for Parallel Computation....Pages 523-524 Parallel Algorithms for Grounded Range Search and Applications....Pages 525-532 Multi-level Cooperative Search: A New Paradigm for Combinatorial Optimization and an Application to Graph Partitioning....Pages 533-542 A Quantitative Measure of Portability with Application to Bandwidth-Latency Models for Parallel Computing⋆ (Extended Abstract)....Pages 543-551 A Cost Model For Asynchronous and Structured Message Passing⋆....Pages 552-556 A Parallel Simulation of Cellular Automata by Spatial Machines....Pages 557-560 High-Performance Computing and Applications....Pages 561-561 Null Messages Cancellation Through Load Balancing in Distributed Simulations....Pages 562-569 Efficient Load-Balancing and Communication Overlap in Parallel Shear-Warp Algorithm on a Cluster of PCs....Pages 570-577 A Hierarchical Approach for Parallelization of a Global Optimization Method for Protein Structure Prediction....Pages 579-585 Parallelization of a Compositional Simulator with a Galerkin Coarse/Fine Method⋆....Pages 586-594 Some Investigations of Domain Decomposition Techniques in Parallel CFD....Pages 595-602 A Parallel Ocean Model for High Resolution Studies....Pages 603-607 Nonoverlapping Domain Decomposition Applied to a Computational Fluid Mechanics Code....Pages 608-612 zA PC Cluster with Application-Quality MPI....Pages 613-623 Using Network of Workstations to Support a Web-Based Visualization Service....Pages 624-632 High-Speed LANs: New Environments for Parallel and Distributed Applications....Pages 633-642 Consequences of Modern Hardware Design for Numerical Simulations and Their Realization in FEAST....Pages 643-650 A Structured SADT Approach to the Support of a Parallel Adaptive 3D CFD Code....Pages 651-658 A Parallel Algorithm for 3D Geometry Transformations in OpenGL....Pages 659-662 Parallel Implementation in a Industrial Framework of Statistical Tolerancing Analysis in Microelectronics....Pages 663-667 Interaction Between Data Parallel Compilation and Data Transfer and Storage Cost Minimization for Multimedia Applications....Pages 668-676 Parallel Numerical Simulation of a Marine Host-Parasite System....Pages 677-685 Parallel Methods of Training for Multilayer Neural Network....Pages 686-690 Partitioning of Vector-Topological Data for Parallel GIS Operations: Assessment and Performance Analysis....Pages 691-694 Parallel Computer Architecture - What Is Its Future?....Pages 695-697 The Algebraic Path Problem Revisited....Pages 698-707 Vector ISA Extension for Sparse Matrix-Vector Multiplication....Pages 708-715 A Study of a Simultaneous Multithreaded Processor Implementation....Pages 716-726 The MorphoSys Parallel Reconfigurable System....Pages 727-734 A Graph-Oriented Task Manager for Small Multiprocessor Systems....Pages 735-744 Implementing Snoop-Coherence Protocol for Future SMP Architectures....Pages 745-752 An Adaptive Limited Pointers Directory Scheme for Cache Coherence of Scalable Multiprocessors....Pages 753-756 Two Schemes to Improve the Performance of a Sort-Last 3D Parallel Rendering Machine with Texture Caches....Pages 757-760 ManArray Processor Interconnection Network: An Introduction....Pages 761-765 Distributed Systems and Algorithms....Pages 767-768 A Cooperation Service for CORBA Objects. From the Model to the Applications⋆....Pages 769-776 Symphony: Managing Virtual Servers in the Global Village⋆....Pages 777-784 Épidaure : A Java Distributed Tool for Building DAI Applications....Pages 785-789 A Client/Broker/Server Substrate with 50 π s Round-Trip Overhead....Pages 790-794 Universal Constructs in Distributed Computations....Pages 795-805 Illustrating the Use of Vector Clocks in Property Detection: An Example and a Counter-Example....Pages 806-814 A Node Count-Independent Logical Clock for Scaling Lazy Release Consistency Protocol....Pages 815-822 Mutual Exclusion Between Neighboring Nodes in an Arbitrary System Graph Tree That Stabilizes Using Read/Write Atomicity....Pages 823-830 Parallel Programming: Models, Methods, and Languages....Pages 831-832 Exploiting Advanced Task Parallelism in High Performance Fortran via a Task Library....Pages 833-844 A Run-Time System for Dynamic Grain Packing....Pages 845-852 Optimising Skeletal-Stream Parallelism on a BSP Computer....Pages 853-857 Parallel Programming by Transformation....Pages 858-865 Condensed Graphs: A Multi-level, Parallel, Intermediate Representation⋆....Pages 866-876 A Skeleton for Parallel Dynamic Programming....Pages 877-887 Programming Effort vs. Performance with a Hybrid Programming Model for Distributed Memory Parallel Architectures....Pages 888-898 DAOS — Scalable And-Or Parallelism....Pages 899-908 Write Detection in Home-Based Software DSMs⋆....Pages 909-913 D’Caml: Native Support for Distributed ML Programming in Heterogeneous Environment....Pages 914-924 ParBlocks - A New Methodology for Specifying Concurrent Method Executions in Opus⋆....Pages 925-929 Static Parallelization of Functional Programs: Elimination of Higher-Order Functions & Optimized Inlining....Pages 930-934 A Library to Implement Neural Networks on MIMD Machines⋆....Pages 935-938 Architectures and Algorithms for Vision and Other Senses....Pages 939-939 LUX: An Heterogeneous Function Composition Parallel Computer for Graphics....Pages 940-949 A Parallel Accelerator Architecture for Multimedia Video Compression....Pages 950-960 A Parallel Architecture for Stereoscopic Processing....Pages 961-968 A Robust Neural Network Based Object Recognition System and Its SIMD Implementation....Pages 969-976 Multimedia Extensions and Sub-word Parallelism in Image Processing: Preliminary Results....Pages 977-986 Vanishing Point Detection in the Hough Transform Space....Pages 987-994 Parallel Structure in an Integrated Speech-Recognition Network....Pages 995-1004 3D Optoelectronic Fix Point Unit and Its Advantages Processing 3D Data⋆....Pages 1005-1012 Parallel Wavelet Transforms on Multiprocessors⋆....Pages 1013-1017 Vector Quantization-Fractal Image Coding Algorithm Based on Delaunay Triangulation....Pages 1018-1021 Numerical Algorithms for Linear and Nonlinear Algebra....Pages 1023-1023 mpC + ScaLAPACK = Efficient Solving Linear Algebra Problems on Heterogeneous Networks....Pages 1024-1031 Parallel Subdomain-Based Preconditioner for the Schur Complement....Pages 1032-1039 A Preconditioner for Improved Fermion Actions....Pages 1040-1043 Application of a Class of Preconditioners to Large Scale Linear Programming Problems....Pages 1044-1048 Estimating Computer Performance for Parallel Sparse QR Factorisation....Pages 1049-1058 A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization⋆....Pages 1059-1067 Scheduling of Algorithms Based on Elimination Trees on NUMA Systems....Pages 1068-1072 Block-Striped Partitioning and Neville Elimination....Pages 1073-1077 A Comparison of Parallel Solvers for Diagonally Dominant and General Narrow-Banded Linear Systems II....Pages 1078-1087 Using Pentangular Factorizations for the Reduction to Banded Form....Pages 1088-1095 Experience with a Recursive Perturbation Based Algorithm for Symmetric Indefinite Linear Systems⋆....Pages 1096-1103 Parallel Cyclic Wavefront Algorithms for Solving Semidefinite Lyapunov Equations⋆....Pages 1104-1111 Parallel Constrained Optimization via Distribution of Variables....Pages 1112-1119 Solving Stable Stein Equations on Distributed Memory Computers⋆....Pages 1120-1123 Convergence Acceleration for the Euler Equations Using a Parallel Semi-Toeplitz Preconditioner....Pages 1124-1127 A Stable and Efficient Parallel Block Gram-Schmidt Algorithm....Pages 1128-1135 On the Extension of the Code GAM for Parallel Computing⋆....Pages 1136-1143 PAMIHR. A Parallel FORTRAN Program for Multidimensional Quadrature on Distributed Memory Architectures....Pages 1144-1148 Stability Issues of the Wang’s Partitioning Algorithm for Banded and Tridiagonal Linear Systems⋆....Pages 1149-1152 Emerging Topics in Advanced Computing in Europe....Pages 1153-1154 The HPF+ Project: Supporting HPF for Advanced Industrial Applications⋆....Pages 1155-1165 TIRAN: Flexible and Portable Fault Tolerance Solutions for Cost Effective Dependable Applications....Pages 1166-1170 OCEANS - Optimising Compilers for Embedded Applications⋆....Pages 1171-1175 Cray T3E Performances of a Parallel Code for a Stochastic Dynamic Assets and Liabilities Management Model⋆....Pages 1176-1186 Parametric Simulation of Multi-body Systems on Networks of Heterogeneous Computers....Pages 1187-1194 Parallel Data Mining in the HYPERBANK Project⋆....Pages 1195-1198 High Performance Computing for Optimum Design of Multi-body Systems....Pages 1199-1202 Routing and Communication in Interconnection Networks....Pages 1203-1203 Optimizing Message Delivery in Asynchronous Distributed Applications⋆....Pages 1204-1208 Circuit-Switched Broadcasting in Multi-port Multi-dimensional Torus Networks⋆....Pages 1209-1221 Impact of the Head-of-Line Blocking on Parallel Computer Networks: Hardware to Applications⋆....Pages 1222-1230 Interval Routing on Layered Cross Product of Trees and Cycles⋆....Pages 1231-1239 Instruction-Level Parallelism and Uniprocessor Architecture....Pages 1241-1242 Design Considerations of High Performance Data Cache with Prefetching....Pages 1243-1250 Annotated Memory References: A Mechanism for Informed Cache Management....Pages 1251-1254 Understanding and Improving Register Assignment⋆....Pages 1255-1259 Compiler-Directed Reordering of Data by Cyclic Graph Coloring....Pages 1260-1264 Code Cloning Tracing: A “Pay per Trace” Approach....Pages 1265-1268 Execution-Based Scheduling for VLIW Architectures....Pages 1269-1280 Decoupling Recovery Mechanism for Data Speculation from Dynamic Instruction Scheduling Structure....Pages 1281-1290 Implementation of Hybrid Context Based Value Predictors Using Value Sequence Classification....Pages 1291-1295 Heterogeneous Clustered Processors: Organisation and Design....Pages 1296-1300 An Architecture Framework for Introducing Predicated Execution into Embedded Microprocessors....Pages 1301-1311 Multi-stage Cascaded Prediction....Pages 1312-1321 Mispredicted Path Cache Effects....Pages 1322-1331 Concurrent and Distributed Programming with Objects....Pages 1333-1333 Non-regular Process Types....Pages 1334-1343 Decision Procedure for Temporal Logic of Concurrent Objects....Pages 1344-1352 Aliasing Models for Object Migration⋆....Pages 1353-1368 Dynamic Extension of CORBA Servers....Pages 1369-1376 On the Concurrent Object Model of UML*....Pages 1377-1384 Object Oriented Design for Reusable Parallel Linear Algebra Software....Pages 1385-1392 Global Environment Modelling....Pages 1393-1394 The Parallelization of the Princeton Ocean Model....Pages 1395-1402 Modular Fortran 90 Implementation of a Parallel Atmospheric General Circulation Model....Pages 1403-1410 Implementation of the Limited-Area Numerical Weather Prediction Model Aladin in Distributed Memory....Pages 1411-1416 Parallelization of the French Meteorological Mesoscale Model MésoNH....Pages 1417-1422 The PALM Project: MPMD Paradigm for an Oceanic Data Assimilation Software....Pages 1423-1430 A Parallel Distributed Fast 3D Poisson Solver for Méso-NH....Pages 1431-1434 Porting a Limited Area Numerical Weather Forecasting Model on a Scalable Shared Memory Parallel Computer....Pages 1435-1438 High Performance Data Mining and Knowledge Discovery....Pages 1439-1440 Mining of Association Rules in Very Large Databases: A Structured Parallel Approach⋆....Pages 1441-1450 Parallel k/h -Means Clustering for Large Data Sets....Pages 1451-1454 Performance Analysis for Parallel Generalized Association Rule Mining on a Large Scale PC Cluster....Pages 1455-1459 Inducing Load Balancing and Efficient Data Distribution Prior to Association Rule Discovery in a Parallel Environment....Pages 1460-1463 Symbolic Computation....Pages 1465-1465 Parallelism in Aldor — The Communication Library П it for Parallel, Distributed Computation....Pages 1466-1475 A Library for Parallel Modular Arithmetic....Pages 1476-1483 Performance Evaluation of Or-Parallel Logic Programming Systems on Distributed Shared-Memory Architectures⋆....Pages 1484-1491 A Parallel Symbolic Computation Environment: Structures and Mechanics....Pages 1492-1495