Parallel Processing and Applied Mathematics

Name: Parallel Processing and Applied Mathematics | 9th International Conference, PPAM 2011, Torun, Poland, September 11-14, 2011. Revised Selected Papers, Part I
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

9th International Conference, PPAM 2011, Torun, Poland, September 11-14, 2011. Revised Selected Papers, Part I

Roman Wyrzykowski Jack Dongarra Konrad Karczewski Jerzy Wasniewski(Editor)

Springer (Publisher)

Published on 3. July 2012

XXVII, 765 pages

E-Book

PDF with digital watermarking

System requirements

978-3-642-31464-3 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Title
Preface
Organization
Table of Contents
A Look Back: 57 Years of Scientific Computing
Parallel/Distributed Architectures and Mobile Computing
Modeling a Leadership-Scale Storage System
Introduction
The ALCF Computing Environment
Modeling the ALCF Computing Environment
Model Validation and Discussion
Related Work
Conclusions and Future Work
References
Combining Optimistic and Pessimistic Replication
Introduction
Assumptions and System Model
The Concept
Related Work
Conclusions
References
K-Resilient Session Guarantees Synchronization Protocol for Mobile Ad-Hoc Networks
Introduction
The Session Guarantees Environment
The SGASP Protocol
Environment Assumptions
Data Structures
General Idea
Protocol Description and Examples
Simulation Evaluation of SGASP
Simulation Parameters
Basic Simulation Results
Conclusions
References
On Time Constraints of Reliable Broadcast Protocols for Ad Hoc Networks with the Liveness Property
Introduction
System Model
Nodes and Communication
Network Liveness Requirement
Crash-Tolerant Broadcast Protocols
Analysis of Time Constraints of the Broadcast Protocols
Conclusions
References
Data Transfers on the Fly for Hierarchical Systems of Chip Multi-Processors
Introduction
System Architecture and Reads on the Fly in Local CMP Networks
Reads on the Fly on L2-Memory Busses
Data Reads on the Fly during Global Inter-CMP Transfers
Experimental Results
Conclusions
References
Numerical Algorithms
New Level-3 BLAS Kernels for Cholesky Factorization
Introduction
Introduction to BPF
The _POTF3 Routines
_POTF3 Routines Can Use a Larger Block Size nb
Experimental Results
Conclusions
References
Parallel Preconditioner for Nonconforming Adini Discretization of a Plate Problem on Nonconforming Meshes
Introduction
Discrete Problem
Additive Schwarz Method Preconditioner
Implementation
Condition Number Estimates
References
Incomplete Cyclic Reduction of Banded and Strictly Diagonally Dominant Linear Systems
Introduction
The Algorithm
The Main Result
Numerical Experiments
References
Fast and Small Nonlinear Pseudorandom Number Generators for Computer Simulation
Introduction
Related Work
Tyche
Initialization
The Algorithm
The MIX Function
Analysis of Tyche
Design
Period
Parallelization
A Faster Variant
Experimental Evaluation
Performance
Statistical Quality Tests
Conclusion
References
Parallel Quantum Algorithm for Finding the Consistency of Saaty's Matrices
Introduction
Vector Variants for Saaty's Matrices
Eigenvalues of Relative Judgements Operator and Assumption for Correction of Consistency
The Physical Interpretation of Quantum Conversion
Parallel Superposition of Quantum Matrix Characteristics in Simulation Variant
Conclusions
References
A Numerical Approach to the Determination of 3D Stokes Flow in Polygonal Domains Using PIES
Introduction
PIES for the Stokes Equation on Polygonal Domains
Approximation of the Boundary Functions over the Surface Patches
Solutions in the Domain
Numerical Examples
Example 1
Example 2
Conclusions
References
Parallel Numerics
Cache Blocking for Linear Algebra Algorithms
Introduction
Dimension Theory and Its Relation to Standard CM and RM Arrays of Fortran and C
Submatrices Aij of A in Fortran and C
Generalization of Standard Format to RB format
Changes to RB Format Have Happened
Tutorial on the Essence of Dimension
Converting Standard Format to RB Format In-Place via Vector Transposition
Dense Linear Algebra Algorithms for MC Use RB or SB Format
The VIPX Vector Transpose Algorithm
Interpretation of Vector Transposition as a Form of Cache Blocking for MC
Some Early IBM History on Cache Blocking
Conclusions and Summary
References
Reducing the Amount of Pivoting in Symmetric Indefinite Systems
Introduction
Tile-Wise Pivoting
An Alternative to Pivoting in Symmetric Systems
Numerical Experiments
Conclusion and Future Work
References
A High Performance Dual Revised Simplex Solver
Introduction
Background
Suboptimization
Parallelising the Simplex Method
A Parallel Scheme and Its Implementation
Results
Conclusions
References
TFETI Coarse Space Projectors Parallelization Strategies
Introduction
FETI-1 and TFETI
Coarse Problem Parallelization Strategies
Data Distribution
Implementation of the Dual Actions
Numerical Experiments
Conclusion and Further Work
References
FFTs and Multiple Collective Communication on Multiprocessor-Node Architectures
Introduction
Bruck's Algorithm
Sparse Bruck Algorithm
FFTs Using 2D Decomposition
Experimental Results
Conclusions
References
Performance Analysis of Parallel Alternating Directions Algorithm for Time Dependent Problems
Introduction
Stokes Equation
Parallel Alternating Directions Algorithm
Formulation of the Scheme
Parallel Algorithm
Experimental Results
Conclusions and Future Work
References
A Novel Parallel Algorithm for Gaussian Elimination of Sparse Unsymmetric Matrices
Introduction
Description of the ``Rheinfall'' Algorithm
Variant: Computation of Matrix Rank
Variant: LUP Factorization
Pivoting
Sample Implementation
Sequential Performance
Integer Performance
Floating-Point Performance
Parallel Performance and Scalability
Experimental Results
Conclusions and Future Work
References
Parallel FEM Adaptation on Hierarchical Architectures
Introduction
Parallel FEM Adaptation
Mesh Decomposition in NuscaS
Parallel Algorithm for Mesh Adaptation
Performance Results
Hybrid Approach
Adapting Pure MPI Approach to Hardware Topology of Clusters
Conclusion and Future Work
References
Solving Systems of Interval Linear Equations in Parallel Using Multithreaded Model and "Interval Extended Zero" Method
Introduction
Efficient Implementation of Interval Arithmetic
Solving Interval Linear Systems Using ``Interval Extended Zero'' Method
Parallel Implementation of the Interval Block Gaussian Elimination Algorithm
OpenMP and SMP Superscalar Parallel Environments
Interval Block Gaussian Elimination Algorithm Implementation Using OpenMP and SMP Superscalar
Conclusions
References
GPU-Based Parallel Algorithms for Transformations of Quantum States Expressed as Vectors and Density Matrices
Introduction
Basic Information about Quantum Computing Model
Algorithms for Parallel Processing of Quantum States
The Measurement of Quantum States as Parallel Reduction Primitive
Unitary Transformations for States Vectors and Density Matrices
Performance of Proposed Methods
Conclusions and Further Work
References
Generalizing Matrix Multiplication for Efficient Computations on Modern Computers
Introduction
Algebraic Semirings in Scientific Calculations
Matrix Operations and Computer Hardware: Today and in the Near Future
Proposed Generalized Multiply-Add Operation
Data Manipulation by Matrix Multiplication
Relating BLAS to the Generalized MMA
Concluding Remarks
References
Distributed QR Factorization Based on Randomized Algorithms
Introduction
Methodology
Distributed QR Factorization (dmGS)
Evaluation of dmGS
Reliability and Scalability
Theoretical Analyses and Comparison with Parallel Algorithms
Conclusions
References
Static Load Balancing for Multi-level Monte Carlo Finite Volume Solvers
Introduction
Highly Scalable Implementation of MLMC-FVM
Robust Pseudo Random Number Generation
A Priori Estimates for Computational Work
Static Load Balancing
Implementation Using C++ and MPI
Variance Computation for Parallel Runs
Efficiency and Linear Scaling in Numerical Simulations
Conclusion
References
Parallel Non-numerical Algorithms
A Parallel Algorithm for Minimizing the Number of Routes in the Vehicle Routing Problem with Time Windows
Introduction
Parallel Algorithm
The MPI Implementation
Experimental Results
Conclusions
References
Towards Parallel Direct SAT-Based Cryptanalysis
Introduction
Feistel Network and DES Cipher
Feistel Network
DES Cipher
Boolean Encoding for Cryptanalysis
Encoding Feistel Network
Encoding DES
Cryptanalysis Procedure
Optimisation and Parallel Computation
Conclusion and Future Directions
References
Parallel Version of Image Segmentation Algorithm Using Polygonal Markov Fields
Introduction
Polygonal Markov Fields
Segmentation Using Polygonal Markov Fields
Parallel Simulated Annealing Method
Exchange Scenarios and Results
Results for Different Synchronization Scenarios
Results for Different Number of Threads
Conclusions
References
Parallel Community Detection for Massive Graphs
Communities in Graphs
Agglomerative Community Detection
Defining the Algorithm
Local Optimization Metrics
Mapping Our Algorithm to the Cray XMT
Evaluating Parallel Community Detection
Parallel Performance
Community Quality
Related Work
Observations
References
Is Your Permutation Algorithm Unbiased for n = 2m?
Introduction
Related Work
Critical Analysis of the Butterfly Permutation Network
Unbiasedness for n=2m
Bias for n=2m
Consistency
Convergence
Convergence Speed
Improvement for the Butterfly Permutation Network
Experimental Results
Conclusions and Future Work
References
Tools and Environments for Parallel/Distributed/Grid Computing
Extracting Coarse-Grained Parallelism for Affine Perfectly Nested Quasi-uniform Loops
Introduction
Background
Approach to Extracting Parallelism
Algorithm Extracting Equivalence Classes for Both Uniform and Quasi-uniform Loops
Degree of Parallelism
Time Complexity
Example
Experiments
Conclusions
References
Polish Computational Research Space for International Scientific Collaborations
Introduction
Goals and Platform Overview
Innovation in International Context
Efficient Resource Allocation
Experimental Workbench
Overview of Selected Tools and Middleware
Users, Software Packages and Their Applications
Software Packages
Helpdesk System and Training Courses
Applications
PL-Grid Platform as Part of European Infrastructure
Conclusions
References
Request Distribution Toolkit for Virtual Resources Allocation
Introduction
Design Issues and Related Works
The Differences between RDM and Other Approaches
Request Distribution Manager
The General Architecture of Request Distribution Manager
Request Distribution Manager Components
Request Handling and Resource Management
Preliminary Tests
Conclusions and Future Work
References
Vitrall: Web-Based Distributed Visualization System for Creation of Collaborative Working Environments
Introduction
Evolution of the Vitrall System
Initial Approach
Second Iteration
Current Approach
Management and Execution of Rendering
Communication Abstraction
Vitrall Clients
User Input Processing and Handling
Data Providers
Competitive Solutions
Current and Future Work
References
Applications of Parallel/Distributed Computing
CUDA Accelerated Blobby Molecular Surface Generation
Introduction
Related Work
Blobby Surface Definition
CUDA Accelerated Blobby Surface Generation
Scalar Field Generation
Isosurface Extraction
Experimental Results
Conclusions and Future Works
References
GPU Accelerated Image Processing for Lip Segmentation
Introduction
Previous Work
Lip Segmentation
CUDA Implementation
Performance Results
Conclusions
References
Material Parameter Identification with Parallel Processing and Geo-applications
Introduction, Framework for Parameter Identification
Optimization Techniques
Nelder-Mead Method
Gradient Gauss-Newton Type Methods
Genetic Algorithms
Geo-applications
APSE - Heat Conduction Problem
Geocomposites - Local Elastic Properties
Parallel Processing
Parallelization of the Forward Problem Solution
Straightforward Parallelization of the Optimization Techniques
Numerical Experiments
Conclusions
References
Hierarchical Parallel Approach in Vascular Network Modeling - Hybrid MPI+OpenMP Implementation
Introduction
Vascular Model Description
Vascular Network
Sequential Algorithm of Vascular Network Development
Hybrid Parallel Algorithm of Vascular Development
Two-Level Hybrid Parallel Perfusion Algorithm
Two-Level Hybrid Parallel Retraction Algorithm
Experimental Results
Conclusion
References
Runtime Optimisation Approaches for a Real-Time Evacuation Assistant
Introduction
Modelling
The Generalized Centrifugal Force Model
Event Driven Routing
Runtime Optimisation
Simulation Area
Linked-Cells
Parallelisation
Load Balancing
Results
Conclusion
References
A Parallel Genetic Algorithm Based on Global Program State Monitoring
Introduction
FDTD Method Overview
Computation Partitioning Using a Genetic Algorithm
Parallelization of a Genetic Algorithm Based on Global Program State Monitoring
Conclusions
References
Applied Mathematics, Neural Networks and Evolutionary Computing
Parallel Approach to the Functional Decomposition of Logical Functions Using Developmental Genetic Programming
Introduction
Functional Decomposition
Developmental Genetic Programming
Evolution of the Multilevel Decomposition Strategy
Genotypes and Phenotypes
Genetic Operators
Parallel DGP Model
Experimental Results
Conclusions
References
The Nine Neighbor Extrapolated Diffusion Method for Weighted Torus Graphs
Introduction
The Nine Neighbor Extrapolated Diffusion (NEDF) Method
Quasi Optimum i
Determination of Optimum ci(1) and cj(2)
The Stretched Torus
Numerical Experiments
Conclusions and Future Work
References
On the Weak Convergence of the Recursive Orthogonal Series-Type Kernel Probabilistic Neural Networks in a Time-Varying Environment
Introduction
Main Result
Experimental Results
Conclusions
References
On the Cesaro Orthogonal Series-Type Kernel Probabilistic Neural Networks Handling Non-stationary Noise
Introduction
Main Result
Experimental Results
Conclusions
References
On the Weak Convergence of the Orthogonal Series-Type Kernel Regresion Neural Networks in a Non-stationary Environment
Introduction
Main Result
Experimental Results
Conclusions
References
A Graph-Based Generation of Virtual Grids
Introduction
Hierarchical Graphs
Grid Representation
Graph Generation
Conclusions
References
On General Regression Neural Network in a Nonstationary Environment
Introduction
Algorithm
Experimental Results
Conclusion and Future Work
References
Determination of the Heat Transfer Coefficient by Using the Ant Colony Optimization Algorithm
Introduction
Ant Colony Optimization Algorithm for Finding the Global Minimum
Formulation of the Problem
Numerical Example
Conclusions
References
Learning in a Non-stationary Environment Using the Recursive Least Squares Method and Orthogonal-Series Type Regression Neural Network
Introduction
Algorithm
Convergence of the Algorithm
Upgrading Procedure for Estimator n()
Simulations
Final Remarks
References
On the Application of the Parzen-Type Kernel Probabilistic Neural Network and Recursive Least Squares Method for Learning in a Time-Varying Environment
Introduction
Algorithm for Learning of Parameter a
Probabilistic Neural Network for Estimation of Regression Function
MainResult
Experimental Results
Conclusions
References
Learning in Rough-Neuro-Fuzzy System for Data with Missing Values
Introduction
Rough-Neuro-Fuzzy Systems
Rough-Neuro-Fuzzy Classifier
Learning Algorithm
Back-Propagation Algorithm
Starting Values and Learning Parameters
Testing Procedure and Results
Method of Generation Lacks in Database
Algorithm of Performance Calculation
Final Remarks
References
Diameter of the Spike-Flow Graphsof Geometrical Neural Networks
Introduction
Simulation Model
Path Length Distribution Results
Numerical Details
Conclusion and Future Work
References
Weak Convergence of the Recursive Parzen-Type Probabilistic Neural Network in a Non-stationary Environment
Introduction
Probabilistic Neural Network
Simulation Results
Conclusion and Future Work
References
Strong Convergence of the Parzen-Type Probabilistic Neural Network in a Time-Varying Environment
Introduction
Algorithm and Main Result
Simulation Results
Conclusion and Future Work
References
Learning in a Time-Varying Environmentby Making Use of the Stochastic Approximation and Orthogonal Series-Type Kernel Probabilistic Neural Network
Introduction
Algorithm
Main Result
Experimental Results
Final Remarks
References
Minisymposium on GPU Computing
Accelerating BST Methods for Model Reduction with Graphics Processors
Introduction
Model Reduction Methods Based on SVD
Solution of the Lyapunov Equation
Solution of the Riccati Equation
High Performance Implementation on a Hybrid Architecture
Hybrid Implementation of the Lyapunov Solver
Hybrid Implementation of the Riccati Solver
Remaining Stages of the BST Method
Numerical Experiments
Concluding Remarks
References
Reducing Thread Divergence in GPU-Based B&B Applied to the Flow-Shop Problem
Introduction
GPU-Based Parallel B&B: Issues and Challenges
Thread Divergence in the Flow-Shop Lower Bound
Thread-Data Reordering
Branch Refactoring
Conclusion and Future Work
References
A GPU-Based Approximate SVD Algorithm
Introduction
Algorithm
Overview
GPU Implementation
Partitioned Version
Results
Conclusions and Future Work
References
Automatic CUDA Code Synthesis Framework for Multicore CPU and GPU Architectures
Introduction
Related Work
Motivation: CUDA Programming
The Proposed CUDA Code Synthesis Framework
Code Generation for CPU and GPU Communication
Synchronous/Asynchronous Communication
Bypass/Clustering Communication
Experiments
Matrix Multiplication
Lane Detection Algorithm
Conclusions
References
Accelerating the Red/Black SOR Method Using GPUs with CUDA
Introduction
Related Work
Red/Black SOR Method
Implementations
GPU Implementations
Common Optimization Strategies
Performance Results
Conclusion
References
Dense Affinity Propagation on Clusters of GPUs
Introduction
Related Work
Affinity Propagation on Clusters of GPUs
Performance Evaluation
Conclusions
References
High-Performance Pseudo-Random Number Generation on Graphics Processing Units
Introduction
The NVIDIA Compute Unified Device Architecture (CUDA) and the Graphics Processing Unit (GPU)
Statistical Testing: TestU01
The Mersenne Twister for Graphic Processors
CURAND
Xorgens
XorgensGP
Results
Discussion
References
Auto-tuning Dense Vector and Matrix-Vector Operations for Fermi GPUs
Introduction
Performance Considerations
Memory Bound Kernels
Coalesced Memory Access
Registers
Loop Unrolling
Vector and Matrix-Vector Operations on Fermi GPUs
Operations on a Vector
Operations on a Matrix
Operations on a Transposed Matrix
Auto-tuning
Using C++ Templates
Tuning Parameters
Results
Euclidian Norm (SNRM2) on Fermi GPU
Matrix-Vector Multiplication (SGEMV) on Fermi GPU
Conclusion
References
GPGPU Implementation of Cellular Automata Model of Water Flow
Introduction
Model
Migrating from CPU to GPU
Results
Conclusions
References
Workshop on Memory and Data Parallelism on Multi- and Manycore Platforms
A Multi-GPU Implementation of a D2Q37 Lattice Boltzmann Code
Introduction
Lattice Boltzmann Methods
Single GPU Implementation
Multi-GPU Implementation
Performance Results and Conclusions
References
Combining Smoother and Residual Calculation in v-cycle AMG for Symmetric Problems
Introduction
AMG and Its Implementation
Simultaneous Application of Smoother and Matrix
Benchmark
Conclusions and Outlook
References
Enhancing Parallelism of Tile Bidiagonal Transformation on Multicore Architectures Using Tree Reduction
Introduction
LAPACK Bidiagonal Transformation
PLASMA Bidiagonal Transformation Using Two-Stage Approach
Related Work and Relevant Contributions
Tile Bidiagonal Transformation Using Tree Reduction
Methodology
Description of the Computational Kernels
DAG Analysis
Experimental Results
Environment Setting
Performance Comparisons
Conclusions and Future Work
References
Autotuning of Adaptive Mesh Refinement PDE Solvers on Shared Memory Architectures
Introduction
Performance Observations and Model
Grain-Size Oracle
Oscillating Search
Interval Search
Results
Summary and Outlook
References
GPU Acceleration of the Matrix-Free Interior Point Method
Introduction
The Matrix-Free Interior Point Method
Accelerating Sparse Matrix-Vector Products
GPU Kernels
Results
Conclusions
References
Workshop on Models, Algorithms and Methodologies for Hierarchical Parallelism in New HPC Systems
Deconvolution of 3D Fluorescence Microscopy Images Using Graphics Processing Units
Introduction
Inverse Problem and Numerical Approach
The Problem and Its Discretization
The FFT-ARL Algorithm
The GPU Algorithm
Experiments
Performance Analysis Considerations
Conclusions
References
HADAB: Enabling Fault Tolerance in Parallel Applications Running in Distributed Environments
Introduction
Fault Tolerance and Checkpointing: State of the Art
HADAB: The Hybrid, Adaptive, Distributed, Algorithm-Based Checkpointing
HADAB Deployment on the PETSc Conjugate Gradient (CG)
Tests and Remarks
Conclusion and Future Works
References
Increasing the Efficiency of the DaCS Programming Model for Heterogeneous Systems
Introduction
Data Communication and Synchronization Library
Overview
Performance Benchmarking
Optimized Byte Swapping
Key Optimization Steps
Result and Usage Details
Usage Scenario: FFTW Library
Computational Model
Performance Measurements
Summary
References
A Software Architecture for Parallel List Processing on Grids
Introduction
DLML
DLML-Grid Architecture
DLML-Grid Load Balancing Algorithm
Experimental Evaluation
Platform Setting and Applications
Response Time and Load Distribution under N-Queens
Response Time and Load Distribution under MM
Related Work
Conclusions and Future Work
References
Reducing the Time to Tune Parallel Dense LinearAlgebra Routines with Partial Execution and Performance Modeling
Introduction
Related Work
Performance Prediction by Correlation
Execution Model of HPL
Modeling ScaLAPACK: A Generic Linear Algebra Library
Quality of Prediction for Extrapolation
Combined Application of Modeling and Sampled Factorization
Conclusions and Future Work
References
A General-Purpose Virtualization Service for HPC on Cloud Computing: An Application to GPUs
Introduction
GVirtuS: General Virtualization Service
Frontends
Backends
Communicators
Implementing the GPU Virtualization Plug-in
Experimental Results
GVirtuS/CUDA Performance Analysis
Analyzing GVirtuS/CUDA in a Virtual Cluster Environment
Related Works
Conclusions and Future Directions
References
A Simulated Annealing Algorithm for GPU Clusters
Introduction
Basic Concepts of the Processing Platform
The Proposed Algorithm
The Lower Level
The Upper Level
Experiments and Results
Conclusion
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Parallel Processing and Applied Mathematics

Description

More details

Other editions

Additional editions

Content

System requirements