Parallel Computing Technologies: 9th International Conference, PaCT 2007, Pereslavl-Zalessky, Russia, September 3-7, 2007, Proceedings (Lecture Notes in Computer Science, 4671)

This book constitutes the refereed proceedings of the 9th International Conference on Parallel Computing Technologies, PaCT 2007, held in conjunction with the Russian-Taiwan symposium on Methods and Tools of Parallel Programming of Multicomputers. It covers models and languages, applications, techniques for parallel programming supporting, cellular automata, as well as methods and tools of parallel programming of multicomputers. Title Page Preface Organization Table of Contents Looking for a Definition of Dynamic Distributed Systems Introduction Elements for Defining a Dynamic Distributed System Modeling the Dynamic Size of the System in Terms of Number of Entities Modeling the Dynamic Size of the System in Terms of Geography Dynamic Models Definition An illustrating Example: One-Time Query The One-Time Query Problem The WILDFIRE Algorithm The One-Time Query Problem for Dynamic Models The DEPTHSEARCH Algorithm Conclusion Adaptive Workflow Nets for Grid Computing Introduction Preliminaries Adaptive Grid Workflow Nets Conclusion A Stochastic Semantics for BioAmbients Introduction Background The Gillespie’s Algorithm Stochastic Process Calculi Stochastic BioAmbients AnExample Conclusions A Categorical Observation of Timed Testing Equivalence Introduction Timed Transition Systems A Category of Timed Transition Systems \mathcal{P}$_\sigma$-Open Morphisms Conclusion Appendix: Introduction to Open Maps From Unreliable Objects to Reliable Objects: The Case of Atomic Registers and Consensus Introduction Computation Model Processes, Registers and Consensus Objects Responsive and Nonresponsive Crash Failures Notion of $t$-Resilience Registers and Consensus Objects with Responsive Failures Reliable Register When Failures Are Responsive: An Unbounded Construction Reliable Register When Failures Are Responsive: A Bounded Construction Consensus When Failures Are Responsive: A Bounded Construction Registers and Consensus Objects with Nonresponsive Failures Reliable Register When Failures Are Not Responsive: An Unbounded Construction Consensus When Failures Are Not Responsive: An Impossibility A Functional Programming System SFP: Sisal 3.1 Language Structures Decomposition The Introduction The Sisal 3.1 Language The IR1 Internal Representation Decomposition of Case, Where and Vector Expressions Decomposition of the Multidimensional Loops Decomposition of the Array Element Selection Decomposition of the Array Element Replacement Conclusion Towards a Computing Model for Open Distributed Systems Introduction Computing Model The Distributed MergeQueue About Termination Open Systems Concluding Remarks References Enhancing Online Computer Games for Grids Introduction Parallelisation Approaches to Scaling Online Games Scalability Dimensions Game World Zoning Game World Replication Grid Computing for Online Games Dynamic Scaling of Game Environments Case Study: Rokkatan Rokkatan: The Game Processing of User Actions Rokkatan Implementation and Scalability Experiments Conclusion and Related Work References Optimized Parallel Approach for 3D Modelling of Forest Fire Behaviour Introduction Mathematical Model and Numerical Method OpenMP Parallelization on NuMA Computers Parallelization Approach and Results Conclusion References A High-Level Toolkit for Development of Distributed Scientific Applications* Introduction IARnet Toolkit Integration of Software Resources Information Service Workflow Management Service BNB-Grid: Using IARnet for Solving Large Scale Discrete Optimization Problems Conclusions References Orthogonal Organized Finite State Machine Application to Sensor Acquired Information Introduction Review[3] Approach and Methodology Applications to Sensor Acquired Data Gradient Contouring Temperature System Cellular Automata Discussion Technological Aspects Conclusion References Parallel Broadband Finite Element Time Domain Algorithm Implemented to Dispersive Electromagnetic Problem Introduction Problem Formulation Distributed Formulation of the Problem Numerical Performance Conclusions References Strategies for Development of a Parallel Program for Protoplanetary Disc Simulation Introduction Protoplanetary Disc Model Basic Equations Numerical Implementation of the Model Parallel Implementation of the Protoplanetary Disc Model Necessity of Parallelization Goals of Parallelization Strategies of Parallelization Parallel Program for Quasi-3D Disc Model Parallel Program Based on the Fundamental Solution of Poisson Equation 3D Parallel Program in Cylindrical Coordinate System 3D Parallel Program Based on Decomposition of the Computation Domain Summary References Generation of SMACA and Its Application in Web Services Introduction Cellular Automata (CA) Preliminaries Definitions Generation of SMACA and Its Application in Indexing Synthesis of SMACA Experimental Results Conclusion References Enhancing Fault-Tolerance of Large-Scale MPI Scientific Applications Introduction Checkpointing and Recovery of Parallel Applications: The CPPC Tool Global Consistency Portability Memory Requirements Transparency The Applications Experimental Results Conclusions References Study of 3D Dynamics of Gravitating Systems Using Supercomputers: Methods and Applications Introduction Mathematical Model of 3D Dynamics of Gravitating Systems NumericalMethods Vlasov Equation Poisson Equation Parallelization Techniques Poisson Equation Vlasov Equation Applications Influence of Central Body on the Vertical Motions of Thin Disk Approach to the Investigation of the Equilibrium States of Gravitating System Conclusion References Transient Mechanical Wave Propagation in Semi-infinite Porous Media Using a Finite Element Approach with Domain Decomposition Technology Introduction Mechanical and Numerical Works Spatial Scales and Macroscopic Approach Finite Element Formulation and Numerical Resolution Structure of the Code and Parallelization Algebraic Decomposition (Grid Partitioning) Domain Decomposition Results Test 1 Test 2 Conclusion References The Location of the Gene Regions Under Selective Pressure: Plato Algorithm Parallelization Introduction Methods and Algorithms Results References Object Serialization and Remote Exception Pattern for Distributed C++/MPI Application Introduction Design Goals Architecture of Application Pattern Implementation Basic Classes Serialization Remote Exceptions Application Examples Assertions Exceptions Thrown in a Slave Node Test Results Serialization’s Overhead Comparison to Java Conclusions References Improving Job Scheduling Performance with Dynamic Replication Strategy in Data Grids Introduction Motivation Related Works Scheduling Strategy Dynamic Replication Replica Decision Replica Placement Performance Studies Replica Placement Strategy Evaluation Dynamic Replication Strategy Evaluation Conclusion References Address-Free All-to-All Routing in Sparse Torus Introduction Sparse Torus $ST(n,d)$ Scheduled Routing of $h$-Relations Conclusions References On the Parallel Technologies of Conjugate and Semi-conjugate Gradient Methods for Solving Very Large Sparse SLAEs Introduction Conjugate and Semi-conjugate Iterative Methods The Parallel Technologies of Algorithms Implementation Results of Numerical Experiments References TRES-CORE: Content-Based Retrieval Based on the Balanced Tree in Peer to Peer Systems Introduction Related Work TRES-CORE Scheme Model Definitions and Properties of Doc-Tree Construction of a Hierarchical Tree Query Processing Extension to the TRES-CORE Scheme Load Balancing Fault Tolerance Improvement of the Efficiency Simulation Experiment Setup Experiment Results Conclusion and Future Work References Efficient Race Verification for Debugging Programs with OpenMP Directives Introduction Background The Data Race in OpenMP Program The Previous Tool Efficient Race Verification The Verification Schemes The Efficient Tool Experimentation Synthetic Programs Race Verification and Its Efficiency Conclusions References Adaptive Scheduling and Resource Assessment in GRID Introduction Scheduling of Computations Cost Function Definition Cost Function Motivation Resources Assessment Problem Problem Description Problem Statement SPSA Algorithm Conclusion References Dynamic Load Balancing of $Black-Box$ Applications with a Resource Selection Mechanism on Heterogeneous Resources of the Grid Introduction and Motivation Background: Automated Load Balancing on the Grid Generalized Automated Load Balancing with Resource Selection The Basic Algorithm of the Automated Load Balancing Adaptive Load Balancing on Heterogeneous Resources: Theoretical Approach Performance Results Synthetic Application and Experimental Setup Load Balancing Speedup for Different Applications Load Balancing for Master-Worker Model: Heuristic Versus Analytically Derived Load Distribution Influence of the Resource Heterogeneity on the Load Balancing Efficiency Conclusions and Future Work References A Novel Algorithm of Optimal Matrix Partitioning for Parallel Dense Factorization on Heterogeneous Processors Introduction LU Factorization on Homogeneous Multiprocessors LU Factorization on Heterogeneous Platforms with a Constant Performance Model of Processors Experimental Results Conclusions and Future Work References Parallel Pseudorandom Number Generator for Large-Scale Monte Carlo Simulations Introduction Generating Pseudorandom Numbers on Single Computer Generating Pseudorandom Numbers in Parallel Choice of Parameters for the Parallel Generator Statistical Test of Parallel Generator ReviewofSystemMONC References Dynamic Job Scheduling on the Grid Environment Using the Great Deluge Algorithm Introduction The Scheduling Problem Scheduling Algorithms Great Deluge Algorithm Extended Great Deluge with Reheat Experimentation and Results Conclusions and Future Work References Parallelism Granules Aggregation with the T-System Introduction Related Work OpenTS: T-System Implementation Granule Aggregation in Recursive Programs Granules Aggregation in “Map” Parallel Programming Template Future Work Conclusion References Toward a Distributed Implementation of OpenMP Using CAPE Introduction CAPE Proof of Concept Distributed Implementation of OpenMP Using CAPE Performances Related Works Conclusion References Multicriteria Scheduling Strategies in Scalable Computing Systems Introduction Assumptions and Statement of the Problem Strategy Synthesis by the Totality of Criteria and Models Conclusions References Latencies of Conflicting Writes on Contemporary Multicore Architectures Introduction False Sharing Related Work Benchmark Results Conclusions and Outlook References A Novel Self-Similar ( $S^2$ ) Traffic Filter to Enhance E-Business Success by Improving Internet Communication Channel Fault Tolerance Introduction Related Work The Self-Similarity ($ S^ 2$ ) Filter Experimental Results Results with the FLC Dynamic Buffer Tuner Conclusion References Accelerating the Singular Value Decomposition of Rectangular Matrices with the CSX600 and the Integrable SVD Introduction The Rectangular SVD Algorithm and Its Optimization for the CSX600 QR Decomposition and Back-Transformation by Q SVD of the Intermediate Bidiagonal Matrix PerformanceResults Conclusion References Parallel Dynamic SPT Update Algorithm in OSPF Introduction Background Parallel SPT Algorithms in Static Method Dynamic SPT Update Algorithms Parallel Analysis Parallel SPT Update Algorithm Framework Complexity Computation Time Communication Time Idle Time Complexity Analysis Task Distribution Algorithm Simulation Conclusion References Pedestrian and Crowd Dynamics Simulation: Testing SCA on Paradigmatic Cases of Emerging Coordination in Negative Interaction Conditions Introduction SCA Model and Crowd Simulation Situated Cellular Agent Model SCA–Based Model of Pedestrian Crowds: Overview Experimenting SCA on Phenomena Emerging from Negative Interaction for Space Sharing Freezing by Heating Lane Formation Concluding Remarks and Future Works References Coarse-Grained Parallelization of Cellular-Automata Simulation Algorithms Introduction Correctness Conditions for CA Domain Decomposition Formal Definitions Correctness Conditions of CA Algorithms Correctness Conditions of CA Decomposition Parallelization of CA Algorithms Synchronous CA Parallelization Asynchronous CA Parallelization Parallelization of Composed CA Conclusion References Cellular Automata Models for Complex Matter Introduction Sandpile Models Self-organized Criticality in the Sandpile Stratification and Segregation in a Binary Sandpile Self-organization and Stratigraphy in Aerolian Sand Ripples Lattice-Gas Models Pure Lattice-Gas Models Lattice-Boltzmann Models Extended Lattice-Boltzmann Models Lattice-Grain Models Cellular Automata for Granular Flow Lattice-Gas Related Models Force Chains in Granular Packing Traffic-Flow Related Models HybridModels Cellular-Neural Models of Reaction-Diffusion Cellular Automata for Hydration of Cement-Based Materials Movable Cellular Automata Discussion From Fine-Grain to Coarse-Grain CACM Synchronous or Asynchronous Time Evolution Topology and Scalability of the Network Consistency of the Models References Hysteresis in Oscillatory Behaviour in CO Oxidation Reaction over Pd(110) Revealed by Asynchronous Cellular Automata Simulation Introduction Formulation of the Reaction Mechanism Algorithm of Simulation Results and Discussions Conclusion References CAOS: A Domain-Specific Language for the Parallel Simulation of Cellular Automata Introduction Cells Agents Observers Implementation and Evaluation Related Work Conclusion References Parallel Hardware Architecture to Simulate Movable Creatures in the CA Model Introduction Formal Description of the Problem Alternative Architectures Conclusion References Comparison of Evolving Uniform, Non-uniform Cellular Automaton, and Genetic Programming for Centroid Detection with Hardware Agents Introduction Evolving Uniform Rules Encoding the Rule Table Details of the Evolutionary Algorithm and the Applied Fitness Function Results for the Uniform Case Extension to Non-uniformity Short Introduction of Non-uniformism and Related Work Investigating Non-uniform CAs in Detail A Third Approach: Genetic Programming Conclusions References Associative Version of Italiano’s Decremental Algorithm for the Transitive Closure Problem Introduction A Model of Associative Parallel Machine Preliminaries Italiano’s Decremental Algorithm for the Transitive Closure An Associative Version of Italiano’s Decremental Algorithm Implementation of the Associative Version of Italiano’s Decremental Algorithm on the STAR-Machine Conclusions References Support for Fine-Grained Synchronization in Shared-Memory Multiprocessors Introduction Related Work Synchronizing Memory Operations Memory Architecture Cache Coherence with Support for Fine-Grain Synchronization Fine-Grain Synchronization with a Snoopy Cache Coherency Protocol Conclusions References Self-organised Criticality in a Model of the Rat Somatosensory Cortex Introduction Model and Method of Parallelisation Simulations and Results Conclusions References Control of Fuzzy Cellular Automata: The Case of Rule 90 Introduction Basic Definitions Cellular Automata Approach Fuzzy Cellular Automata Control of Fuzzy Rule 90 The Case of a Single Controlled Cell in Zero Backgrounds Case of a Controlled Cell with a Single Seed in a Zero Background Concluding Remarks References Intensive Atmospheric Vortices Modeling Using High Performance Cluster Systems Inroduction ParJava Mathematical Model and Computational Implementation Parallel Algorithm Results of Numerical Modeling of 3D Tornado Conclusion References Dynamic Strategy of Placement of the Replicas in Data Grid Introduction Related Works Cost Model and Replicas Placement Grid Topology A Cost Model Placement Algorithm Simulation Simulated Grid Model Experimentations and Results Conclusion and Future Works References ISO: Comprehensive Techniques Toward Efficient GEN_BLOCK Redistribution with Multidimensional Arrays Introduction Related Work Communication Sets Identification Single Dimensional Array Multi-dimensional Array Communication Scheduling Local Message Reduction Optimization Performance Evaluation Conclusions References A New Memory Slowdown Model for the Characterization of Computing Systems Introduction The Model Validation Conclusions and Future Work References SCRF – A Hybrid Register File Architecture Introduction Related Work The Architecture Models The Clustered RF Architecture The $SCRF$ Architecture The $SCRF$ Register Allocation Algorithm Phase 1 Phase 2 Phase 3 Phase 4 An Example to Illustrate the SCRF Register Allocation Macro Register Allocation Performance Comparisons Conclusions References Model Based Performance Evaluation for MPI Programs Introduction Model of a Parallel Java Program Interpretation of the Model Conclusions References Runtime System for Parallel Execution of Fragmented Subroutines Introduction Related Work Parallel Libraries Complex Projects Fragments Creation and Execution Implementation of a Fragment Creation of Fragments The Outline of the Runtime System Architecture The Runtime System Functions Execution of Ready Fragments Data Exchanges and Implementation of Information Dependencies Fragment Lookup Service Fragment Migration Support Experiments Hardware Measurement Program Overhead Costs Speedup and Efficiency Load Balancing Possibility Tests Conclusions and Future Work References Application of Simulation Approaches to Creation of Decision Support System for IT Service Management Problem Statement Proposed Approach Application Example Further Development and Application Area Conclusion References Using Analytical Models to Load Balancing in a Heterogeneous Network of Computers Introduction Workload Distribution Developed Strategy Case Studies Computational Environment Workload Balancing Comparing the PEMPIs VRP with SS Strategy Some Related Works Conclusions References Block-Based Allocation Algorithms for FLASH Memory in Embedded Systems Introduction Flash Memory Allocation Model Page Access Sequence Flash Memory Allocation Algorithms The Online Problem The Offline Problem Experimental Results Implementation Issues Experimental Settings Effect of the Length of Page Access Sequence The Effects of Cell Number Conclusion References Variable Reassignment in the T++ Parallel Programming Language Introduction OpenTS Programming Model T++ Language Implementation of Variable Reassignment Distributed Shared Memory in OpenTS POV Ray Parallelization with OpenTS Related Work Conclusion References Parallel Construction of Moving Adaptive Meshes Based on Self-organization Introduction Moving Mesh Construction Based on Self-organization Parallel Adaptive Mesh Construction Conclusion References Data Transfer in Advance on Cluster Introduction Related Work Mechanism of Data Transfer in Advance Selecting the Destination Node to the Data Transfer Ensuring the Data-Intensive Job Execution Integrated Scheduling System - “ISS” Architecture of ISS Evaluation Conclusions and Future Works References A Trust-Oriented Heuristic Scheduling Algorithm for Grid Computing Introduction Definition of Trust EigenTrust Algorithm Trust-Oriented Scheduling Algorithm Experiments and Results Analysis Conclusions References 3-Points Relationship Based Parallel Algorithm for Minimum Ultrametric Tree Construction Introduction Preliminaries Sequential Branch-and-Bound Algorithm for MUT 3-Point Relationship ($3PR$) The Proposed Parallel Branch-and-Bound Algorithm Experimental Results Conclusions References Load Balancing Approach Parallel Algorithm for Frequent Pattern Mining Introduction Related Work Frequent Pattern Growth (FP-Growth) Parallel FP-Tree Algorithm (PFP-Tree) Load Balancing Frequent Pattern Tree (LFP-Tree) Global Header Table Construction Step FP-Tree Construction Step The Load Degree Evaluation and Item Distribution Step Data Exchanging and Result Collection Step Experimental Results Conclusions References Author Index This book constitutes the proceedings of the 12th International Conference on Parallel Computing Technologies, PaCT 2013, held in St. Petersburg, Russia, during September 30-October 4, 2013. The 41 full papers presented together with 2 invited papers were carefully reviewed and selected from 83 submissions. The papers are organized in topical sections on all technological aspects of the applications of parallel computer systems High level parallel programming languages and systems, methods and tools for parallel solution of large-scale problems, languages, environments and software tools supporting parallel processing, operating systems, scheduling, mapping, load balancing, general architectural concepts, cellular automata, performance measurement and analysis tools, teaching parallel processing, software for grid and cloud computing, scalable computing, fragmentation and aggregation of algorithms and programs as well as programs assembling and reuse.