Parallel and Distributed Processing

This volume contains the proceedings from the workshops held in conjunction with the IEEE International Parallel and Distributed Processing Symposium, IPDPS 2000, on 1-5 May 2000 in Cancun, Mexico. The workshopsprovidea forum for bringing together researchers,practiti- ers, and designers from various backgrounds to discuss the state of the art in parallelism.Theyfocusondi erentaspectsofparallelism,fromruntimesystems to formal methods, from optics to irregular problems, from biology to networks of personal computers, from embedded systems to programming environments; the following workshops are represented in this volume: { Workshop on Personal Computer Based Networks of Workstations { Workshop on Advances in Parallel and Distributed Computational Models { Workshop on Par. and Dist. Comp. in Image, Video, and Multimedia { Workshop on High-Level Parallel Prog. Models and Supportive Env. { Workshop on High Performance Data Mining { Workshop on Solving Irregularly Structured Problems in Parallel { Workshop on Java for Parallel and Distributed Computing { WorkshoponBiologicallyInspiredSolutionsto ParallelProcessingProblems { Workshop on Parallel and Distributed Real-Time Systems { Workshop on Embedded HPC Systems and Applications { Recon gurable Architectures Workshop { Workshop on Formal Methods for Parallel Programming { Workshop on Optics and Computer Science { Workshop on Run-Time Systems for Parallel Programming { Workshop on Fault-Tolerant Parallel and Distributed Systems All papers published in the workshops proceedings were selected by the p- gram committee on the basis of referee reports. Each paper was reviewed by independent referees who judged the papers for originality, quality, and cons- tency with the themes of the workshops.

3rd Workshop on Personal Computer based Networks Of Workstations (PC-NOW 2000).- Memory Management in a combined VIA/SCI Hardware.- ATOLL, a new switched, high speed Interconnect in Comparison to Myrinet and SCI.- ClusterNet: An Object-Oriented Cluster Network.- GigaBit Performance under NT.- MPI Collective Operations over IP Multicast.- An Open Market-Based Architecture for Distributed Computing.- The MultiCluster Model to the Integrated Use of Multiple Workstation Clusters.- Parallel Information Retrieval on an SCI-Based PC-NOW.- A PC-NOW Based Parallel Extension for a Sequential DBMS.- Workshop on Advances in Parallel and Distributed Computational Models.- The Heterogeneous Bulk Synchronous Parallel Model.- On stalling in LogP.- Parallelizability of some P-complete problems.- A New Computation of Shape Moments via Quadtree Decomposition.- The Fuzzy Philosophers.- A Java Applet to Visualize Algorithms on Reconfigurable Mesh.- A Hardware Implementation of PRAM and its Performance Evaluation.- A Non-Binary Parallel Arithmetic Architecture.- Multithreaded Parallel Computer Model with Performance Evaluation.- Workshop on Parallel and Distributed Computing in Image Processing, Video Processing, and Multimedia (PDIVM 2000).- MAJC-5200: A High Performance Microprocessor for Multimedia Computing.- A Novel Superscalar Architecture for Fast DCT Implementation.- Computing Distance Maps Efficiently Using An Optical Bus.- Advanced Data Layout Optimization for Multimedia Applications.- Parallel Parsing of MPEG Video in a Multi-threaded Multiprocessor Environment.- Parallelization Techniques for Spatial-Temporal Occupancy Maps from Multiple Video Streams.- Heuristic Solutions for a Mapping Problem in a TV-Anytime Server Network.- RPV: A Programming Environment for Real-time Parallel Vision —Specification and programming methodology—.- Parallel low-level image processing on a distributed-memory system.- Congestion-free Routing of Streaming Multimedia Content in BMIN-based Parallel Systems.- Performance of On-Chip Multiprocessors for Vision Tasks (Summary).- Parallel Hardware-Software Architecture for computation of Discrete Wavelet Transform using the Recursive Merge Filtering algorithm.- Fifth International Workshop on High-level Parallel Programming Models and Supportive Environments HIPS 2000.- Pipelining Wavefront Computations: Experiences and Performance.- Specification Techniques for Automatic Performance Analysis Tools.- PDRS: A Performance Data Representation System.- Clix — A Hybrid Programming Environment for Distributed Objects and Distributed Shared Memory.- Controlling Distributed Shared Memory Consistency from High Level Programming Languages.- Online Computation of Critical Paths for Multithreaded Languages.- Problem Solving Environment Infrastructure for High Performance Computer Systems.- Combining Fusion Optimizations and Piecewise Execution of Nested Data-Parallel Programs.- Declarative concurrency in Java.- Scalable Monitoring Technique for Detecting Races in Parallel Programs.- 3rd IPDPS Workshop on High Performance Data Mining.- Implementation Issues in the Design of I/O Intensive Data Mining Applications on Clusters of Workstations.- A Requirements Analysis for Parallel KDD Systems.- Parallel Data Mining on ATM-Connected PC Cluster and Optimization of its Execution Environments.- The Parallelization of a Knowledge Discovery System with Hypergraph Representation.- Parallelisation of C4.5 as a Particular Divide and Conquer Computation.- Scalable Parallel Clustering for Data Mining on Multicomputers.- Exploiting Dataset Similarity for Distributed Mining.- Scalable Model for Extensional and Intensional Descriptions of Unclassified Data.- Parallel Data Mining of Bayesian Networks from Telecommunications Network Data.- Irregular’00 Seventh International Workshop on Solving Irregularly Structured Problems in Parallel.- Load Balancing and Continuous Quadratic Programming.- Parallel Management of Large Dynamic Shared Memory Space: A Hierarchical FEM Application.- Efficient Parallelization of Unstructured Reductions on Shared Memory Parallel Architectures.- Parallel FEM Simulation of Crack Propagation — Challenges, Status, and Perspectives.- Support for Irregular Computations in Massively Parallel PIM Arrays, Using an Object-Based Execution Model.- Executing Communication-Intensive Irregular Programs Efficiently.- Non-Memory-Based and Real-Time Zerotree Building for Wavelet Zerotree Coding Systems.- Graph Partitioning for Dynamic, Adaptive and Multi-phase Computations.- A Multilevel Algorithm for Spectral Partitioning with Extended Eigen-Models.- An Integrated Decomposition and Partitioning Approach for Irregular Block-Structured Applications.- Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel Systems.- A GRASP for computing approximate solutions for the Three-Index Assignment Problem.- On Identifying Strongly Connected Components in Parallel.- A Parallel, Adaptive Refinement Scheme for Tetrahedral and Triangular Grids.- PaStiX: A Parallel Sparse Direct Solver Based on a Static Scheduling for Mixed 1D/2D Block Distributions.- Workshop on Java for Parallel and Distributed Computing.- An IP Next Generation Compliant Java™ Virtual Machine.- An Approach to Asynchronous Object-Oriented Parallel and Distributed Computing on Wide-Area Systems.- Performance Issues for Multi-language Java Applications.- MPJ: A Proposed Java Message Passing API and Environment for High Performance Computing.- Implementing Java consistency using a generic, multithreaded DSM runtime system.- Third Workshop on Bio-Inspired Solutions to Parallel Processing Problems (BioSP3).- Take Advantage of the Computing Power of DNA Computers.- Agent surgery: The case for mutable agents.- Was Collective Intelligence1 before Life on Earth?.- Solving Problems on Parallel Computers by Cellular Programming.- Multiprocessor Scheduling with Support by Genetic Algorithms - based Learning Classifier System.- Viewing Scheduling Problems through Genetic and Evolutionary Algorithms.- Dynamic Load Balancing Model: Preliminary Assessment of a Biological Model for a Pseudo-Search Engine.- A Parallel Co-evolutionary Metaheuristic.- Neural Fraud Detection in Mobile Phone Operations.- Information Exchange in Multi Colony Ant Algorithms.- A Surface-Based DNA Algorithm for the Expansion of Symbolic Determinants.- Hardware Support for Simulated Annealing and Tabu Search.- Eighth International Workshop on Parallel and Distributed Real-Time Systems.- A Distributed Real Time Coordination Protocol.- A Segmented Backup Scheme for Dependable Real Time Communication in Multihop Networks.- Real-Time Coordination in Distributed Multimedia Systems.- Supporting Fault-Tolerant Real-Time Applications using the RED-Linux General Scheduling Framework.- Are COTS suitable for building distributed fault-tolerant hard real-time systems?.- Autonomous Consistency Technique in Distributed Database with Heterogeneous Requirements.- Real-time Transaction Processing Using Two-stage Validation in Broadcast Disks.- Using Logs to Increase Availability in Real-Time Main-Memory Database.- Components are from Mars.- 2 + 10 ? 1 + 50 !.- A Framework for Embedded Real-time System Design.- Best-effort Scheduling of (m,k)-firm Real-time Streams in Multihop Networks.- Predictability and Resource Management in Distributed Multimedia Presentations.- Quality of Service Negotiation for Distributed, Dynamic Real-time Systems.- An Open Framework for Real-Time Scheduling Simulation.- 5th International Workshop on Embedded/Distributed HPC Systems and Applications (EHPC 2000).- A Probabilistic Power Prediction Tool for the Xilinx 4000-Series FPGA.- Application Challenges: System Health Management for Complex Systems.- Accommodating QoS Prediction in an Adaptive Resource Management Framework.- Network Load Monitoring in Distributed Systems.- A Novel Specification and Design Methodology Of Embedded Multiprocessor Signal Processing Systems Using High-Performance Middleware.- Auto Source Code Generation and Run-Time Infrastructure and Environment for High Performance, Distributed Computing Systems.- Developing an Open Architecture for Performance Data Mining.- A 90k gate “CLB” for Parallel Distributed Computing.- Power-Aware Replication of Data Structures in Distributed Embedded Real-Time Systems.- Comparison of MPI Implementations on a Shared Memory Machine.- A Genetic Algorithm Approach to Scheduling Communications for a Class of Parallel Space-Time Adaptive Processing Algorithms.- Reconfigurable Parallel Sorting and Load Balancing on a Beowulf Cluster: HeteroSort.- 7th Reconfigurable Architectures Workshop (RAW 2000).- Run-Time Reconfiguration at Xilinx (invited talk).- JRoute: A Run-Time Routing API for FPGA Hardware.- A Reconfigurable Content Addressable Memory.- ATLANTIS — A Hybrid FPGA/RISC Based Re-configurable System.- The Cellular Processor Architecture CEPRA-1X and its Configuration by CDL.- Loop Pipelining and Optimization for Run Time Reconfiguration.- Compiling Process Algebraic Descriptions into Reconfigurable Logic.- Behavioral Partitioning with Synthesis for Multi-FPGA Architectures under Interconnect, Area, and Latency Constraints.- Module Allocation for Dynamically Reconfigurable Systems.- Augmenting Modern Superscalar Architectures with Configurable Extended Instructions.- Complexity Bounds for Lookup Table Implementation of Factored Forms in FPGA Technology Mapping.- Optimization of Motion Estimator for Run-Time-Reconfiguration Implementation.- Constan t-Time Hough Transform On A 3D Reconfigurable Mesh Using Fewer Processors.- Fifth International Workshop on Formal Methods for Parallel Programming: Theory and Applications FMPPTA 2000.- A Method for Automatic Cryptographic Protocol Verification.- Verification Methods for Weaker Shared Memory Consistency Models.- Models Supporting Nondeterminism and Probabilistic Choice.- Concurrent Specification And Timing Analysis of Digital Hardware using SDL.- Incorporating Non-functional Requirements into Software Architectures.- Automatic Implementation of Distributed Systems Formal Specifications.- Refinement based validation of an algorithm for detecting distributed termination.- Tutorial 1: Abstraction and Refinement of Concurrent Programs and Formal Specification A Practical View.- A Foundation for Composing Concurrent Objects.- Workshop on Optics and Computer Science (WOCS 2000).- Fault Tolerant Algorithms for a Linear Array with a Reconfigurable Pipelined Bus System.- Fast and Scalable Parallel Matrix Computations with Optical Buses.- Pulse-Modulated Vision Chips with Versatile-Interconnected Pixels.- Connectivity Models for Optoelectronic Computing Systems.- Optoelectronic-VLSI Technology: Terabit/s I/O to a VLSI Chip.- Three Dimensional VLSI-Scale Interconnects.- Present and Future Needs of Free-Space Optical Interconnects.- Fast Sorting on a Linear Array with a Reconfigurable Pipelined Bus System.- Architecture description and prototype demonstration of optoelectronic parallel-matching architecture.- A Distributed Computing Demonstration System Using FSOI Inter-Processor Communication.- Optoelectronic Multi-Chip Modules Based on Imaging Fiber Bundle Structures.- VCSEL based smart pixel array technology enables chip-to-chip optical interconnect.- Run-Time Systems for Parallel Programming.- A Portable and Adaptative Multi-Protocol Communication Library for Multithreaded Runtime Systems.- CORBA Based Runtime Support for Load Distribution and Fault Tolerance.- Run-time Support for Adaptive Load Balancing.- Integrating Kernel Activations in a Multithreaded Runtime System on top of Linux.- DyRecT: Software Support for Adaptive Parallelism on NOWs.- Fast Measurement of LogP Parameters for Message Passing Platforms.- Supporting flexible safety and sharing in multi-threaded environments.- A Runtime System for Dynamic DAG Programming.- Workshop on Fault-Tolerant Parallel and Distributed Systems (FTPDS’ 00).- Certification of system architecture dependability.- Computing in the RAIN: A Reliable Array of Independent Nodes.- Fault Tolerant Wide-Area Parallel Computing.- Transient Analysis of Dependability/Performability Models by Regenerativ e Randomization with Laplace Transform In version.- FANTOMAS Fault Tolerance for Mobile Agents in Clusters.- Metrics, Methodologies, and Tools for Analyzing Network Fault Recovery Performance in Real-Time Distributed Systems.- Consensus Based on Strong Failure Detectors: A Time and Message-Efficient Protocol.- Implementation of Finite Lattices in VLSI for Fault-State Encoding in High-Speed Networks.- Building a Reliable Message Delivery System Using the CORBA Event Service.- Network Survivability Simulation of a Commercially Deployed Dynamic Routing System Protocol.- Fault-tolerant Distributed-Shared-Memory on a Broadcast-based Interconnection Network.- An Efficient Backup-Overloading for Fault-Tolerant Scheduling of Real-Time Tasks.- Mobile Agents to Automate Fault Management in Wireless and Mobile Networks.- 9th Heterogeneous Computing Workshop (HCW 2000).