Euro-Par 2003 Parallel Processing: 9th International Euro-Par Conference, Klagenfurt, Austria, August 26–29, 2003 Proceedings (Lecture Notes in Computer Science Book 2790)

Euro-ParConferenceSeries The European Conference on Parallel Computing (Euro-Par) is an international conference series dedicated to the promotion and advancement of all aspects of parallel and distributed computing. The major themes fall into the categories of hardware, software, algorithms, and applications. This year, new and interesting topicswereintroduced,likePeer-to-PeerComputing,DistributedMultimedia- stems, and Mobile and Ubiquitous Computing. For the ?rst time, we organized a Demo Session showing many challenging applications. The general objective of Euro-Par is to provide a forum promoting the de- lopment of parallel and distributed computing both as an industrial technique and an academic discipline, extending the frontiers of both the state of the art and the state of the practice. The industrial importance of parallel and dist- buted computing is supported this year by a special Industrial Session as well as a vendors’ exhibition. This is particularly important as currently parallel and distributed computing is evolving into a globally important technology; the b- zword Grid Computing clearly expresses this move. In addition, the trend to a - bile world is clearly visible in this year’s Euro-Par. ThemainaudienceforandparticipantsatEuro-Parareresearchersinaca- mic departments, industrial organizations, and government laboratories. Euro- Par aims to become the primary choice of such professionals for the presentation of new results in their speci?c areas. Euro-Par has its own Internet domain with a permanent Web site where the history of the conference series is described: http://www.euro-par.org. The Euro-Par conference series is sponsored by the Association for Computer Machinery (ACM) and the International Federation for Information Processing (IFIP). Front Matter....Pages - The Verifying Compiler: A Grand Challenge for Computing Research....Pages 1-1 Evolving a Multi-language Object-Oriented Framework: Lessons from .NET....Pages 2-2 Databases, Web Services, and Grid Computing – Standards and Directions....Pages 3-3 Ibis: A Java-Based Grid Programming Environment....Pages 4-4 Topic 1 Support Tools and Environments....Pages 5-6 A Hardware Counters Based Tool for System Monitoring....Pages 7-16 ParaProf : A Portable, Extensible, and Scalable Tool for Parallel Performance Profile Analysis....Pages 17-26 On Utilizing Experiment Data Repository for Performance Analysis of Parallel Applications....Pages 27-37 Flexible Performance Debugging of Parallel and Distributed Applications....Pages 38-46 EventSpace – Exposing and Observing Communication Behavior of Parallel Cluster Applications....Pages 47-56 A Race Detection Mechanism Embedded in a Conceptual Model for the Debugging of Message-Passing Distributed Programs....Pages 57-65 DIOS++: A Framework for Rule-Based Autonomic Management of Distributed Scientific Applications....Pages 66-73 DeWiz – A Modular Tool Architecture for Parallel Program Analysis....Pages 74-80 Why Not Use a Pattern-Based Parallel Programming System?....Pages 81-86 Topic 2 Performance Evaluation and Prediction....Pages 87-87 Symbolic Performance Prediction of Speculative Parallel Programs....Pages 88-97 A Reconfigurable Monitoring System for Large-Scale Network Computing....Pages 98-108 Obtaining Hardware Performance Metrics for the BlueGene/L Supercomputer....Pages 109-118 Presentation and Analysis of Grid Performance Data....Pages 119-126 Distributed Application Monitoring for Clustered SMP Architectures....Pages 127-134 An Emulation System for Predicting Master/Slave Program Performance....Pages 135-140 POETRIES: Performance Oriented Environment for Transparent Resource-Management, Implementing End-User Parallel/Distributed Applications....Pages 141-146 Topic 3 Scheduling and Load Balancing....Pages 147-147 Static Load-Balancing Techniques for Iterative Computations on Heterogeneous Clusters....Pages 148-159 Impact of Job Allocation Strategies on Communication-Driven Coscheduling in Clusters....Pages 160-168 Trading Cycles for Information: Using Replication to Schedule Bag-of-Tasks Applications on Computational Grids....Pages 169-180 Dynamic Load Partitioning Strategies for Managing Data of Space and Time Heterogeneity in Parallel SAMR Applications....Pages 181-188 An Experimental Investigation into the Rank Function of the Heterogeneous Earliest Finish Time Scheduling Algorithm....Pages 189-194 Performance-Based Dynamic Scheduling of Hybrid Real-Time Applications on a Cluster of Heterogeneous Workstations....Pages 195-200 Recursive Refinement of Lower Bounds in the Multiprocessor Scheduling Problem....Pages 201-205 Efficient Dynamic Load Balancing Strategies for Parallel Active Set Optimization Methods....Pages 206-211 Cooperating Coscheduling in a Non-dedicated Cluster....Pages 212-217 Predicting the Best Mapping for Efficient Exploitation of Task and Data Parallelism....Pages 218-223 Dynamic Load Balancing for I/O- and Memory-Intensive Workload in Clusters Using a Feedback Control Mechanism....Pages 224-229 An Experimental Study of k -Splittable Scheduling for DNS-Based Traffic Allocation....Pages 230-235 Scheduling Strategies of Divisible Loads in DIN Networks....Pages 236-240 Topic 4 Compilers for High Performance....Pages 241-241 Partial Redundancy Elimination with Predication Techniques....Pages 242-250 SIMD Vectorization of Straight Line FFT Code....Pages 251-260 Branch Elimination via Multi-variable Condition Merging....Pages 261-270 Exploiting On-Chip Data Transfers for Improving Performance of Chip-Scale Multiprocessors....Pages 271-278 An Energy-Oriented Evaluation of Communication Optimizations for Microsensor Networks....Pages 279-286 Increasing the Parallelism of Irregular Loops with Dependences....Pages 287-296 Finding Free Schedules for Non-uniform Loops....Pages 297-302 Replicated Placements in the Polyhedron Model....Pages 303-308 Topic 5 Parallel and Distributed Databases, Data Mining, and Knowledge Discovery....Pages 309-309 A Parallel Algorithm for Incremental Compact Clustering....Pages 310-317 Preventive Multi-master Replication in a Cluster of Autonomous Databases*....Pages 318-327 Pushing Down Bit Filters in the Pipelined Execution of Large Queries....Pages 328-337 Suffix Arrays in Parallel....Pages 338-341 Revisiting Join Site Selection in Distributed Database Systems....Pages 342-347 SCINTRA: A Model for Quantifying Inconsistencies in Grid-Organized Sensor Database Systems....Pages 348-355 Topic 6 Grid Computing and Middleware Systems....Pages 356-356 Implementation of a Grid Computation Toolkit for Design Optimisation with Matlab and Condor....Pages 357-365 Grid Resource Selection for Opportunistic Job Migration....Pages 366-373 Semantic Access Control for Medical Applications in Grid Environments....Pages 374-383 Automated Negotiation for Grid Notification Services....Pages 384-393 GrADSolve – RPC for High Performance Computing on the Grid....Pages 394-403 Resource and Job Monitoring in the Grid....Pages 404-411 Delivering Data Management for Engineers on the Grid....Pages 412-416 A Resource Accounting and Charging System in Condor Environment....Pages 417-420 Secure Web Services with Globus GSI and gSOAP....Pages 421-426 Future-Based RMI: Optimizing Compositions of Remote Method Calls on the Grid....Pages 427-430 Topic 7 Applications on High-Performance Computers....Pages 431-432 CAD Grid: Corporate-Wide Resource Sharing for Parameter Studies....Pages 433-440 Cache Performance Optimizations for Parallel Lattice Boltzmann Codes....Pages 441-450 Effectiveness of Parallelizing the ILOG-CPLEX Mixed Integer Optimizer in the PUBB2 Framework....Pages 451-460 Improving Performance of Hypermatrix Cholesky Factorization....Pages 461-469 Parallel Agent-Based Simulation on a Cluster of Workstations....Pages 470-480 Low Level Parallelization of Nonlinear Diffusion Filtering Algorithms for Cluster Computing Environments....Pages 481-490 Implementation of Adaptive Control Algorithms in Robot Manipulators Using Parallel Computing....Pages 491-498 Interactive Ray Tracing on Commodity PC Clusters....Pages 499-508 Toward Automatic Management of Embarrassingly Parallel Applications....Pages 509-516 Comparing Two Long Biological Sequences Using a DSM System....Pages 517-524 Two Dimensional Airfoil Optimisation Using CFD in a Grid Computing Environment....Pages 525-532 Applied Grid Computing: Optimisation of Photonic Devices....Pages 533-536 Parallel Linear System Solution and Its Application to Railway Power Network Simulation....Pages 537-540 Topic 8 Parallel Computer Architecture and Instruction-Level Parallelism....Pages 541-542 An Overview of the Blue Gene/L System Software Organization....Pages 543-555 Trace Substitution....Pages 556-565 Optimizing a Decoupled Front-End Architecture: The Indexed Fetch Target Buffer (iFTB)....Pages 566-575 Clustered Microarchitecture Simultaneous Multithreading....Pages 576-585 Counteracting Bank Misprediction in Sliced First-Level Caches....Pages 586-596 An Enhanced Trace Scheduler for SPARC Processors....Pages 597-602 Compiler-Assisted Thread Level Control Speculation....Pages 603-608 Compression in Data Caches with Compressible Field Isolation for Recursive Data Structures....Pages 609-615 Value Compression to Reduce Power in Data Caches....Pages 616-622 Topic 9 Distributed Algorithms....Pages 623-623 Multiresolution Watershed Segmentation on a Beowulf Network....Pages 624-631 i RBP – A Fault Tolerant Total Order Broadcast for Large Scale Systems....Pages 632-639 Computational Models for Web- and Grid-Based Computation....Pages 640-650 CAS-Based Lock-Free Algorithm for Shared Deques....Pages 651-660 Energy Efficient Algorithm for Disconnected Write Operations in Mobile Web Environments....Pages 661-668 Distributed Scheduling of Mobile Priority Requests....Pages 669-674 Parallel Distributed Algorithms of the β -Model of the Small World Graphs....Pages 675-680 Topic 10 Parallel Programming: Models, Methods, and Programming Languages....Pages 681-681 Cost Optimality and Predictability of Parallel Programming with Skeletons....Pages 682-693 A Methodology for Order-Sensitive Execution of Non-deterministic Languages on Beowulf Platforms....Pages 694-703 From Complexity Analysis to Performance Analysis....Pages 704-711 The Implementation of ASSIST , an Environment for Parallel and Distributed Programming....Pages 712-721 The Design of an API for Strict Multithreading in C++....Pages 722-731 High-Level Process Control in Eden....Pages 732-741 Using Skeletons in a Java-Based Grid System....Pages 742-749 Prototyping Application Models in Concurrent ML....Pages 750-759 THROOM – Supporting POSIX Multithreaded Binaries on a Cluster....Pages 760-769 An Inter-entry Invocation Selection Mechanism for Concurrent Programming Languages....Pages 770-780 Parallel Juxtaposition for Bulk Synchronous Parallel ML....Pages 781-788 Parallelization with Tree Skeletons....Pages 789-798 Topic 11 Numerical Algorithms and Scientific Engineering Problems....Pages 799-799 Parallel ScaLAPACK-Style Algorithms for Solving Continuous-Time Sylvester Matrix Equations....Pages 800-809 RECSY – A High Performance Library for Sylvester-Type Matrix Equations....Pages 810-819 Two Level Parallelism in a Stream-Function Model for Global Ocean Circulation....Pages 820-829 Scalable Parallel RK Solvers for ODEs Derived by the Method of Lines....Pages 830-839 Hierarchical Hybrid Grids as Basis for Parallel Numerical Solution of PDE....Pages 840-843 Overlapping Computation/Communication in the Parallel One-Sided Jacobi Method....Pages 844-849 Topic 12 Architectures and Algorithms for Multimedia Applications....Pages 850-850 Distributed Multimedia Streaming over Peer-to-Peer Networks....Pages 851-858 Exploiting Traffic Balancing and Multicast Efficiency in Distributed Video-on-Demand Architectures....Pages 859-869 On Transmission Scheduling in a Server-Less Video-on-Demand System....Pages 870-879 A Proxy-Based Dynamic Multicasting Policy Using Stream’s Access Pattern....Pages 880-883 Topic 13 Theory and Algorithms for Parallel Computation....Pages 884-884 Improving Communication Sensitive Parallel Radix Sort for Unbalanced Data....Pages 885-893 Minimizing Global Communication in Parallel List Ranking....Pages 894-902 Construction of Efficient Communication Sub-structures: Non-approximability Results and Polynomial Sub-cases....Pages 903-910 c -Perfect Hashing Schemes for Binary Trees, with Applications to Parallel Memories....Pages 911-916 A Model of Pipelined Mutual Exclusion on Cache-Coherent Multiprocessors....Pages 917-922 Efficient Parallel Multiplication Algorithm for Large Integers....Pages 923-928 Topic 14 Routing and Communication in Interconnection Networks....Pages 929-929 Dynamic Streams for Efficient Communications between Migrating Processes in a Cluster....Pages 930-937 FOBS: A Lightweight Communication Protocol for Grid Computing....Pages 938-946 Low-Fragmentation Mapping Strategies for Linear Forwarding Tables in InfiniBand TM ....Pages 947-957 A Robust Mechanism for Congestion Control: INC....Pages 958-968 RoCL: A Resource Oriented Communication Library....Pages 969-979 A QoS Multicast Routing Protocol for Dynamic Group Topology....Pages 980-988 A Study of Network Capacity under Deflection Routing Schemes....Pages 989-994 Implementation and Performance Evaluation of M-VIA on AceNIC Gigabit Ethernet Card....Pages 995-1000 Topic 15 Mobile and Ubiquitous Computing....Pages 1001-1002 A Comparative Study of Protocols for Efficient Data Propagation in Smart Dust Networks....Pages 1003-1016 Network Based Mobile Station Positioning in Metropolitan Area....Pages 1017-1026 Programming Coordinated Motion Patterns with the TOTA Middleware....Pages 1027-1037 iClouds – Peer-to-Peer Information Sharing in Mobile Environments....Pages 1038-1045 Support for Personal and Service Mobility in Ubiquitous Computing Environments....Pages 1046-1055 Dynamic Layouts for Wireless ATM....Pages 1056-1063 Modeling Context-Aware Behavior by Interpreted ECA Rules....Pages 1064-1073 A Coordination Model for ad hoc Mobile Systems....Pages 1074-1081 Making Existing Interactive Applications Context-Aware....Pages 1082-1090 Benefits and Requirements of Using Multi-agent Systems on Smart Devices....Pages 1091-1098 Performance Evaluation of Two Congestion Control Mechanisms with On-Demand Distance Vector (AODV) Routing Protocol for Mobile and Wireless Networks....Pages 1099-1108 Towards an Approach for Mobile Profile Based Distributed Clustering....Pages 1109-1117 Simulating Demand-Driven Server and Service Location in Third Generation Mobile Networks....Pages 1118-1128 Designing Mobile Games for a Challenging Experience of the Urban Heritage....Pages 1129-1136 QoS Provision in IP Based Mobile Networks....Pages 1137-1140 Design of a Management System for Wireless Home Area Networking....Pages 1141-1147 Short Message Service in a Grid-Enabled Computing Environment....Pages 1148-1152 Service Migration Mechanism Using Mobile Sensor Network....Pages 1153-1158 Topic 16 Distributed Systems and Distributed Multimedia....Pages 1159-1159 Nswap: A Network Swapping Module for Linux Clusters....Pages 1160-1169 Low Overhead Agent Replication for the Reliable Mobile Agent System....Pages 1170-1179 A Transparent Software Distributed Shared Memory....Pages 1180-1189 On the Characterization of Distributed Virtual Environment Systems....Pages 1190-1198 A Proxy Placement Algorithm for the Adaptive Multimedia Server....Pages 1199-1206 A New Distributed JVM for Cluster Computing....Pages 1207-1215 An Extension of BSDL for Multimedia Bitstream Syntax Description....Pages 1216-1223 Fast Construction, Easy Configuration, and Flexible Management of a Cluster System....Pages 1224-1228 Topic 17 Peer-to-Peer Computing....Pages 1229-1229 Hierarchical Peer-to-Peer Systems....Pages 1230-1239 Enabling Peer-to-Peer Interactions for Scientific Applications on the Grid....Pages 1240-1247 A Spontaneous Overlay Search Tree....Pages 1248-1256 Fault Tolerant Peer-to-Peer Dissemination Network....Pages 1257-1264 Exploring the Catallactic Coordination Approach for Peer-to-Peer Systems....Pages 1265-1272 Incentives for Combatting Freeriding on P2P Networks....Pages 1273-1279 Topic 18 Demonstrations of Parallel and Distributed Computing....Pages 1280-1280 Demonstration of P-GRADE Job-Mode for the Grid....Pages 1281-1286 Coupling Parallel Simulation and Multi-display Visualization on a PC Cluster....Pages 1287-1290 Kerrighed: A Single System Image Cluster Operating System for High Performance Computing....Pages 1291-1294 ASSIST Demo: A High Level, High Performance, Portable, Structured Parallel Programming Environment at Work....Pages 1295-1300 KOJAK – A Tool Set for Automatic Performance Analysis of Parallel Programs....Pages 1301-1304 Visual System for Developing of Parallel Programs....Pages 1305-1308 Peer-to-Peer Communication through the Design and Implementation of Xiangqi....Pages 1309-1313 Back Matter....Pages - Euro-ParConferenceSeries The European Conference on Parallel Computing (Euro-Par) is an international conference series dedicated to the promotion and advancement of all aspects of parallel and distributed computing. The major themes fall into the categories of hardware, software, algorithms, and applications. This year, new and interesting topicswereintroduced, likePeer-to-PeerComputing, DistributedMultimedia- stems, and Mobile and Ubiquitous Computing. For the?rst time, we organized a Demo Session showing many challenging applications. The general objective of Euro-Par is to provide a forum promoting the de- lopment of parallel and distributed computing both as an industrial technique and an academic discipline, extending the frontiers of both the state of the art and the state of the practice. The industrial importance of parallel and dist- buted computing is supported this year by a special Industrial Session as well as a vendors' exhibition. This is particularly important as currently parallel and distributed computing is evolving into a globally important technology; the b- zword Grid Computing clearly expresses this move. In addition, the trend to a - bile world is clearly visible in this year's Euro-Par. ThemainaudienceforandparticipantsatEuro-Parareresearchersinaca- mic departments, industrial organizations, and government laboratories. Euro- Par aims to become the primary choice of such professionals for the presentation of new results in their speci?c areas. Euro-Par has its own Internet domain with a permanent Web site where the history of the conference series is described: http://www.euro-par.org. The Euro-Par conference series is sponsored by the Association for Computer Machinery (ACM) and the International Federation for Information Processing (IFIP) This book constitutes the refereed proceedings of the 9th International Conference on Parallel Computing, Euro-Par 2003, held in Klagenfurt, Austria in August 2003. The 109 revised full papers and 52 revised research note papers were carefully reviewed and selected from 338 submissions. The papers presented give a unique survey of the state of the art in parallel computing research, ranging from algorithms and software aspects to hardware and applications in various fields. Besides the more classical topics in parallel computing, new topics are addressed as well like peer-to-peer computing, distributed multimedia systems, and mobile and ubiquitous computing