Parallel Computing Technologies
11th International Conference, PaCT 2011, Kazan, Russia, September 19-23, 2011, Proceedings
Published on 10. September 2011
XIV, 500 pages
978-3-642-23178-0 (ISBN)
Description
This book constitutes the proceedings of the 11th International Conference on Parallel Computing Technologies, PaCT 2011, held in Kazan, Russia on September 19-23, 2011.
The 44 full papers presented together with 2 invited papers were carefully reviewed and selected from 68 submissions. The papers are organized in topical sections on models and languages, cellular automata, parallel programming tools and support, and applications.
More details
Other editions
Additional editions
Victor Malyshkin
Parallel Computing Technologies
11th International Conference, PaCT 2011, Kazan, Russia, September 19-23, 2011, Proceedings
Book
09/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Models and Languages
- Classical and Quantum Parallelism in the Quantum Fingerprinting Method\
- Introduction
- Preliminaries
- Algorithms for QBPs Based on Fingerprinting
- Basic Idea
- Quantum Algorithms Based on Fingerprinting
- Fingerprinting Technique
- Computing Functions with Nonlinear Characteristics
- References
- OpenMP Parallelization of a CFD Code for Multicore Computers: Analysis and Comparison
- Introduction
- Numerical Method
- Solving the Pressure Poisson Equation
- Parallelization Method
- Results and Analysis
- Conclusion
- References
- On Quantitative Security Policies
- Preliminaries
- Stochastic History Expressions
- Syntax
- Structural Equivalence
- Semantics
- Rate Bisimulation
- Stochastic Security Policies
- Abstracting Executions
- Actual and Potential Checks of Quantitative Policies
- A Working Example
- Conclusions
- References
- A Formal Programming Model of Orl´eans Skeleton Library
- Introduction
- An Overview of Orléans Skeleton Library
- Bulk Synchronous Parallelism
- OSL Skeletons
- Related Work
- OSL Mechanised Semantics: Programming Model
- Distributed Arrays
- Syntax and Typing
- Big-Step Semantics
- Conclusion and Future Work
- References
- LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem
- Introduction
- Introductory Definitions
- General Model Definition
- Interpretation
- Correct Interpretation
- The LuNA Fragmented Programming System
- Model Modifications
- Scheme of the LuNA Implementation
- LuNA Input Language
- Testing
- Conclusion
- References
- Grid Computing for Sensitivity Analysis of Stochastic Biological Models
- Introduction
- Sensitivity Analysis of Stochastic Models
- Elementary Effects and Optimized Sampling of the Input Space
- Comparison of Stochastic Models Output: The Histogram Distance
- The Bacterial Chemotaxis Case Study
- The European Grid Infrastructure
- Performance Indexes
- Results
- Conclusions
- References
- Looking for Efficient Implementations of Concurrent Objects
- Introduction
- Concurrent Objects
- Content of the Paper
- Computation Model
- System Model
- Compare and Swap Operation
- Implementing an Abortable Stack and a Non-blocking Stack
- A Contention-Sensitive Implementation of Stack
- Data Structures
- The Algorithm
- Proof
- From a Non-blocking Lock to a Starvation-Free Lock
- Concluding Remarks
- References
- Cache Efficiency and Scalability on Multi-core Architectures
- Introduction
- Software and Hardware Environment
- Investigated Applications
- Investigated Hardware and System Libraries
- Results
- Scalability
- Thread-To-Core Assignment Issues
- Impact of Sequential Portions
- Cache Behavior
- Conclusion and Future Work
- References
- Symbolic Algorithm for Generation B¨uchi Automata from LTL Formulas
- Introduction
- Background
- Alternating Automata on Infinite Words
- Symbolic Realization of LTL to Büchi Automaton Translation
- Generation an Alternating Automaton from LTL Formula
- From Alternating Automata to Generalized Büchi Automata with Transition-Based Acceptance
- From Generalized Büchi Automata with Accepting Transitions to Büchi Automata
- Results and Related Works
- Conclusion
- References
- Sisal 3.2 Language Features Overview
- Introduction
- Sisal Language Overview
- Program Structure
- Types
- Functions
- Expressions
- Control by Selection
- Control by Distribution and Iteration
- Errors
- Multidimensional Arrays
- New Language Abstractions
- Reusable User-Defined Reductions
- Improved Interoperability with Other Languages
- Optimizing Annotations
- Conclusion
- References
- Cellular Automata
- A Cellular Automata Based Model for Pedestrian and Group Dynamics: Motivations and First Experiments
- Introduction
- Definition of the GA-Ped Model
- Space and Environment
- Time and Update Type
- Pedestrians
- Simulation Scenario
- Large Group vs. Small Group Counterflow
- Conclusions and Future Developments
- References
- Using Multi Core Computers for Implementing Cellular Automata Systems
- Introduction
- Formal Definition of a Cellular Automata System
- Correctness of CA System Functioning
- CA-System Simulating a Single Reaction-Diffusion Process
- CA System Simulating Many Interacting Processes
- Conclusion
- References
- Efficient Minimal Routing in the Triangular Grid with Six Channels
- Introduction
- Topology and Routing in the CA Network
- Topology of the T-grid
- Routing Scheme in the T-Grid
- The Agents' Routing Task
- CA Modeling of the Multi-agent System
- Cellular Automata Modeling
- Computing the Minimal Route
- Router Efficiency and Deadlocks
- Efficiency of Non-adaptive Routing
- Efficiency of Adaptive Routing
- Deadlocks
- Conclusion
- References
- Domain Specific Language and Translator for Cellular Automata Models of Physico-Chemical Processes
- Introduction
- A Cellular Automaton Definition
- Formal Representation of CA
- Formal Representation of Local Transition Rule
- CACHE Language
- Iteration Mode
- Type of Cell State
- Parameters
- Elementary Substitution
- Composed Substitution
- Local Transition Rule
- Counters
- Translator
- Conclusion
- References
- Dynamic Load Balancing for Lattice Gas Simulations on a Cluster*
- Introduction
- Describing of the LGA Models
- Features of the Multi-particle Models
- Parallel Program Implementation
- Load Balancing Algorithm
- Initial Balancing
- Dynamic Balancing
- Results of Testing
- An Example of Explosion Simulation. Dynamics of Distribution of the Cellular Array among Cores
- An Example of a Quiet Flow. Comparison of the Efficiency
- Comparison of the Implementation Efficiency for the LGA and the PIC Method
- Conclusion and Future Work
- References
- Efficient Associative Algorithm for Finding the Second Simple Shortest Paths in a Digraph
- Introduction
- Model of Associative Parallel Machine
- Preliminaries
- Data Structure
- Finding the Second Simple Shortest Paths
- Implementing the Algorithm for Finding the Second Simple Shortest Paths
- Conclusions
- References
- The Construction of Simulation Models of Algorithms and Structures with Fine-Grain Parallelism in WinALT
- Introduction
- Custom Features of WinALT System
- Adequacy of the System's Language to the Problem Domain
- The Architecture of WinALT System
- Samples of WinALT Models
- A Simulation Model of Associative Device
- A Simulation Model of Algebraic Fractal "Julia Set"
- Collection of Models at the System's Web Site
- Conclusion
- References
- Simulation of Heterogeneous Catalytic Reaction by Asynchronous Cellular Automata on Multicomputer
- Introduction
- Carbon Monoxide Oxidation Reaction over Platinum Surface
- CA Model of CO Oxidation Reaction over Pt
- Results of ACA Sequential Implementation Simulating CO Oxidation Reaction
- Parallel Implementation of ACA-Model Simulating the CO Oxidation Reaction over Pt(100)
- Approximation of ACA by a Block-Synchronous CA
- ACA and BSCA Evolutions Comparison
- Results of BSCA Parallel Implementation
- Conclusion
- References
- Smallest Implementations of Optimum-Time Firing Squad Synchronization Algorithms for One-Bit-Communication Cellular Automata
- Introduction
- One-Bit-Communication Cellular Automata
- Firing Squad Synchronization Problem
- An Optimum-Time FSSP Algorithm on 1-D CA1-bit
- A 3n-Step Non-optimum-Time FSSP Algorithm on 1-D CA$_1-bit$
- Firing Squad Synchronization Problem on Two-Dimensional Square Arrays
- Conclusions
- References
- Parallel Programming Tools and Support
- Distributed Genetic Process Mining Using Sampling
- Introduction
- Process Mining and Event Logs Characteristics
- Distributed Sample-Based Genetic Mining Algorithm (DSGMA)
- Island Sample Based Genetic Process Mining Algorithm (SGMA)
- Distribution Architecture
- Implementation
- Experimental Results
- Conclusions and Future Work
- References
- FaDe: RESTful Service for Failure Detection in SOA Environment
- Introduction
- FADE General Concept
- FADE Node Architecture
- Failure Monitoring
- Internal Communication
- Related Work
- Conclusion
- References
- ReServE Service: An Approach to Increase Reliability in Service Oriented Systems
- Introduction
- Related Work
- System Model and Basic Definitions
- Reliability Service Environment
- ReServE Service Architecture
- ReServE Service Requirements
- Business Process Execution with the Use of the ReServE Service
- Simulation Experiments and Performance Evaluation
- Conclusions and the Future Work
- References
- Hypergraph Partitioning for the Parallel Computation of Continuous Petri Nets
- Introduction
- ODE Representation of Concurrent Systems
- Parallel Computing of Differential Equations
- Moving from Petri Net To Hypergraph
- Partitioning Hypergraph
- Parallel Computing
- Case Study (I): The Gas Station Program
- From Petri Net to Hypergraph
- Partition of the Hypergraph of Gas Station
- Regrouping Differential Equations
- Parallel Computing
- Static Analysis
- Case Study (II): The Dining Philosopher Problem
- Related Work
- Conclusion
- References
- High-Performance Reconfigurable Computer Systems
- Introduction
- Examples of the RCS Implementation
- Reconfigurable Computer Systems Programming
- Conclusions
- References
- CacheVisor: A Toolset for Visualizing Shared Caches in Multicore and Multithreaded Processors
- Introduction
- CacheVisor Implementation
- Using CacheVisor in Research and Education
- Concluding Remarks
- References
- The LuNA Library of Parallel Numerical Fragmented Subroutines
- Introduction
- Introduction to Fragmented Programming
- The LuNA Subroutines
- Matrices Multiplication
- LU-Factorization
- Computations on Regular Meshes
- Concluding Remarks
- References
- PARMONC - A Software Library for Massively Parallel Stochastic Simulation
- Introduction
- Background
- Estimators of Interest in Stochastic Simulation
- Parallelization of Stochastic Simulation
- Implementation of Stochastic Simulation
- A Parallel RNG
- Overview of the Library PARMONC
- Contents of the Library
- Subroutines 'parmoncf' and 'parmoncc'
- Function 'rnd128'
- Command 'manaver'
- Command 'genparam'
- Description of Files with Results of Simulation
- Performance Test
- Conclusion
- References
- On Performance Analysis of a Multithreaded Application Parallelized by Different Programming Models Using Intel VTune
- Introduction
- Overview of TBB and OpenMP
- Threading Building Blocks (TBB)
- OpenMP Programming Model
- A Low-Level Analysis
- Case Study: Substring Finder
- Experimental Results
- Hardware Events
- Discussion
- Related Works
- Conclusions
- References
- Using Multidimensional Solvers for Optimal Data Partitioning on Dedicated Heterogeneous HPC Platforms
- Introduction
- Traditional Piecewise Linear Approximation of Speed Functions and Geometrical Data Partitioning Algorithm
- Data Partitioning Algorithm Based on Geometrical Solution
- Piecewise Linear Approximation of Speed Functions
- New Data Partitioning Algorithm Based on Multidimensional Root-Finding
- Data Partitioning Algorithm Based on Nonlinear Multidimensional Root Finding
- New Approximation of Partial Speed Functions Based on the Akima Splines
- Convergence and Complexity Analysis
- Dynamic Load Balancing of Parallel Computational Iterative Routines
- Conclusion
- References
- An Efficient Evolutionary Scheduling Algorithm for Parallel Job Model in Grid Environment
- Introduction
- Grid Model and Scheduling
- Model
- Two-Stage Scheduling
- Global Scheduling with Generalized Extremal Optimization Algorithm
- The Bak-Sneppen Model and Its Representation in Job Allocation
- The GEO-Based Scheduling Algorithm
- Global Scheduling with GA
- Local Scheduling Algorithm
- Experimental Results
- Conclusions
- References
- On Mapping Graphs of Parallel Programs onto Graphs of Distributed Computer Systems by Recurrent Neural Networks
- Introduction
- Hopfield Network for the Mapping Problem
- Mapping by the Hopfield Network
- Splitting Method
- Mapping by the Wang Network
- Conclusion
- References
- Slot Selection and Co-allocation for Economic Scheduling in Distributed Computing
- Introduction
- Scheduling Scheme
- Slot Search Algorithms
- AMP Search Example
- Simulation Studies
- Experimental Results Analysis
- Conclusion and Future Work
- References
- An Initial Approximation to the Resource-Optimal Checkpoint Interval
- Introduction
- Model Formulation
- Related Work
- First Order Approximation
- Calculation of Optimal Interval by Examples
- Model Limitations
- Conclusions and Future Work
- References
- Applications
- Performance Characteristics of Global High-Resolution Ocean (MPIOM) and Atmosphere (ECHAM6) Models on Large-Scale Multicore Cluster
- Introduction
- Model Description
- Performance Analysis
- MPIOM Code Optimizations
- Improving Computation
- Reducing Communication
- Summary and Outlook
- References
- Performances of Navier-Stokes Solver on a Hybrid CPU/GPU Computing System
- Introduction
- CPU/GPU Hybrid Architectures
- Numerical Technique
- GPU Implementation of Navier-Stokes Solver
- Computing System
- Code Performances
- Concluding Remarks
- References
- Optimal Design of Multi-product Batch Plants Using a Parallel Branch-and-Bound Method
- Motivation and Related Work
- Problem Formulation
- Sequential Implementation and Its Optimization
- Parallel Implementation
- Shared-Memory Approach
- Distributed-Memory Approach
- Experimental Results
- Conclusion
- References
- Virtual Path Implementation of Multi-stream Routing in Network on Chip
- Introduction
- Tapeworm Routing
- Experimental Results
- Conclusion
- References
- Web Service of Access to Computing Resources of BOINC Based Desktop Grid
- Introduction
- Software Platform
- The System Architecture
- Implementation
- Conclusion, Results and Further Work
- References
- Solution of Assimilation Observation Data Problem for Shallow Water Equations for SMP-Nodes Cluster
- Introduction
- The Differential Formulation of a Problem
- Parallel Implementation. An Estimate of Potential Acceleration of a Parallel Algorithm
- Comparison of Two MPI Implementations and of Memory Management Strategies
- References
- A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices
- Introduction
- The GaussSieve Algorithm
- Parallel GaussSieve
- Experimental Results
- Conclusion and Further Work
- References
- Graphical Algorithm for the Knapsack Problems
- Introduction
- Basic Idea of the Graphical Algorithm
- Graphical Algorithm for the Knapsack Problem
- Parallel Implementation
- Column Parallelization
- Interval Parallelization
- Experiments
- Concluding Remarks
- References
- SSCCIP - A Framework for Building Distributed High-Performance Image Processing Technologies
- Introduction
- Requirements
- Composition
- Client-Server Interaction
- Client Component
- Server Component
- SSCC_PIPL Library
- Example of Concrete Technology Implementation
- Conclusion
- References
- Parallel Logical Cryptanalysis of the Generator A5/1 in BNB-Grid System
- Introduction
- Reducing Cryptanalysis of the Generator A5/1 to SAT
- Coarse-Grained Parallelization of the Problem of Logical Cryptanalysis of the Generator A5/1
- Modification of a SAT Solver for Solving the Problem of Logical Cryptanalysis of the Generator A5/1
- Implementation of Parallel Logical Cryptanalysis of the Generator A5/1 in BNB-Grid System
- Conclusion and Future Work
- References
- High Performance Computing of MSSG with Ultra High Resolution
- Introduction
- Model Description
- The Atmospheric Component: MSSG-A
- The Ocean Component: MSSG-O
- Grid Configuration
- Differencing Schemes
- Algebraic Multigrid Method in a Poisson Solver
- Implementation of MSSG on the Earth Simulator
- Coding Style
- Distribution Architecture and Communications
- Inter-/Intra-node Parallel Architectures and Vector Processing
- Memory and Ccost Reductions for Land Area in MSSG-O
- Overlapped Computations in MSSG-O
- Coupling Scheme with High Computational Performance
- Computational Performance on the Earth Simulator
- Cost Balance and Communication Cost of MSSG-A
- Efficiency of Overlapped Computation in MSSG-O
- Simulation Results
- Results from MSSG-A
- Results from MSSG-O
- Urban Scale Simulations
- Conclusions and Perspectives
- References
- Author Index
