Parallel Algorithms for Irregularly Structured Problems: Third International Workshop, IRREGULAR '96 Santa Barbara, CA, USA, August 19–21, 1996 Proceedings

✍ Scribed by Torben Hagerup (auth.), Alfonso Ferreira, José Rolim, Yousef Saad, Tao Yang (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1996
• Tongue: English
• Leaves: 359
• Series: Lecture Notes in Computer Science 1117
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems, IRREGULAR '96, held in Santa Barbara, California, in August 1996.
The volume presents 28 revised full papers selected from 51 submissions; also included are one full invited paper by Torben Hagerup and abstracts of four other invited talks. The papers are organized in topical sections on sparse matrix problems, partitioning and domain composition, irregular applications, communication and synchronization, systems support, and mapping and load balancing.

✦ Table of Contents

Allocating independent tasks to parallel processors: An experimental study....Pages 1-33
Parallel implementation of an adaptive scheme for 3D unstructured grids on the SP2....Pages 35-47
Solution of large, sparse, irregular systems on a massively parallel computer....Pages 49-62
Parallel implementation of a sparse approximate inverse preconditioner....Pages 63-74
Decomposing irregularly sparse matrices for parallel matrix-vector multiplication....Pages 75-86
Dynamic spectral partitioning....Pages 87-87
Fast distributed genetic algorithms for partitioning uniform grids....Pages 89-103
Toward efficient unstructured multigrid preprocessing (extended abstract)....Pages 105-118
Domain decomposition for particle methods on the sphere....Pages 119-130
Coordination of distributed/parallel multiple-grid domain decomposition....Pages 131-144
Systems support for irregular parallel applications....Pages 145-145
Distributed object oriented data structures and algorithms for VLSI CAD....Pages 147-158
Parallel progressive radiosity with adaptive meshing....Pages 159-170
Lineal feature extraction by parallel stick growing....Pages 171-182
A simple parallel algorithm for the single-source shortest path problem on planar digraphs....Pages 183-194
A regular VLSI array for an irregular algorithm....Pages 195-200
Digital librarires and spatial information processing....Pages 201-201
Flexible communication mechanisms for dynamic structured applications....Pages 203-215
Multi-Message Multicasting....Pages 217-228
Synchronization as a strategy for designing efficient parallel algorithms....Pages 229-236
Supporting dynamic data and processor repartitioning for irregular applications....Pages 237-248
Simple quantitative experiments with a sparse compiler....Pages 249-262
Using algorithmic skeletons with dynamic data structures....Pages 263-276
An interface design for general parallel branch-and-bound algorithms....Pages 277-284
Support for irregular computation in high performance Fortran....Pages 285-285
Efficient dynamic embedding of arbitrary binary trees into hypercubes....Pages 287-298
Practical dynamic load balancing for irregular problems....Pages 299-306
The module allocation problem: An average case analysis....Pages 307-312
Dynamically adapting the degree of parallelism with reflexive programs....Pages 313-318
On the complexity of the generalized block distribution....Pages 319-326
Adaptive load balancing of irregular applications a case study: IDA * applied to the 15-puzzle problem....Pages 327-338
Manufacturing progressive addition lenses using distributed parallel processing....Pages 339-350
The parallel complexity of randomized fractals....Pages 351-356

✦ Subjects

Computation by Abstract Devices; Programming Techniques; Processor Architectures; Operating Systems; Computational Mathematics and Numerical Analysis; Combinatorics