Ebook: Parallel Algorithms for Irregular Problems: State of the Art

Efficient parallel solutions have been found to many problems. Some of them can be obtained automatically from sequential programs, using compilers. However, there is a large class of problems - irregular problems - that lack efficient solutions. IRREGULAR 94 - a workshop and summer school organized in Geneva - addressed the problems associated with the derivation of efficient solutions to irregular problems. This book, which is based on the workshop, draws on the contributions of outstanding scientists to present the state of the art in irregular problems, covering aspects ranging from scientific computing, discrete optimization, and automatic extraction of parallelism.
Audience: This first book on parallel algorithms for irregular problems is of interest to advanced graduate students and researchers in parallel computer science.

---

Efficient parallel solutions have been found to many problems. Some of them can be obtained automatically from sequential programs, using compilers. However, there is a large class of problems - irregular problems - that lack efficient solutions. IRREGULAR 94 - a workshop and summer school organized in Geneva - addressed the problems associated with the derivation of efficient solutions to irregular problems. This book, which is based on the workshop, draws on the contributions of outstanding scientists to present the state of the art in irregular problems, covering aspects ranging from scientific computing, discrete optimization, and automatic extraction of parallelism.
Audience: This first book on parallel algorithms for irregular problems is of interest to advanced graduate students and researchers in parallel computer science.

---

Efficient parallel solutions have been found to many problems. Some of them can be obtained automatically from sequential programs, using compilers. However, there is a large class of problems - irregular problems - that lack efficient solutions. IRREGULAR 94 - a workshop and summer school organized in Geneva - addressed the problems associated with the derivation of efficient solutions to irregular problems. This book, which is based on the workshop, draws on the contributions of outstanding scientists to present the state of the art in irregular problems, covering aspects ranging from scientific computing, discrete optimization, and automatic extraction of parallelism.
Audience: This first book on parallel algorithms for irregular problems is of interest to advanced graduate students and researchers in parallel computer science.

Content:
Front Matter....Pages i-xii
Front Matter....Pages 1-1
Parallelization Strategies for Matrix Assembly in Finite Element Methods....Pages 3-24
A Parallelisable Algorithm for Partitioning Unstructured Meshes....Pages 25-46
Plump: Parallel Library for Unstructured Mesh Problems....Pages 47-71
Parallelizing Vision Computations on CM-5: Algorithms and Experiences....Pages 73-95
Front Matter....Pages 97-97
Scalable Parallel Algorithms for Unstructured Problems....Pages 99-113
A Parallel Grasp Implementation for the Quadratic Assignment Problem....Pages 115-133
Concurrent Data Structures for Tree Search Algorithms....Pages 135-155
A Distributed Implementation of Asynchronous Parallel Branch and Bound....Pages 157-176
Experiments with a Parallel Synchronized Branch and Bound Algorithm....Pages 177-193
Parallel Local Search and Job Shop Scheduling....Pages 195-212
A Randomized Parallel Search Strategy....Pages 213-227
A Parallel Approximation Schema for Symmetric Linear Assignment Problem....Pages 229-242
Front Matter....Pages 243-243
Applications of Graph Scheduling Techniques in Parallelizing Irregular Scientific Computation....Pages 245-267
Atredia: A Mapping Environment for Dynamic Tree-Structured Problems....Pages 269-296
Regularising Transformations for Integral Dependencies....Pages 297-322
Some Strategies for Load Balancing....Pages 323-338

---

Efficient parallel solutions have been found to many problems. Some of them can be obtained automatically from sequential programs, using compilers. However, there is a large class of problems - irregular problems - that lack efficient solutions. IRREGULAR 94 - a workshop and summer school organized in Geneva - addressed the problems associated with the derivation of efficient solutions to irregular problems. This book, which is based on the workshop, draws on the contributions of outstanding scientists to present the state of the art in irregular problems, covering aspects ranging from scientific computing, discrete optimization, and automatic extraction of parallelism.
Audience: This first book on parallel algorithms for irregular problems is of interest to advanced graduate students and researchers in parallel computer science.

Content:
Front Matter....Pages i-xii
Front Matter....Pages 1-1
Parallelization Strategies for Matrix Assembly in Finite Element Methods....Pages 3-24
A Parallelisable Algorithm for Partitioning Unstructured Meshes....Pages 25-46
Plump: Parallel Library for Unstructured Mesh Problems....Pages 47-71
Parallelizing Vision Computations on CM-5: Algorithms and Experiences....Pages 73-95
Front Matter....Pages 97-97
Scalable Parallel Algorithms for Unstructured Problems....Pages 99-113
A Parallel Grasp Implementation for the Quadratic Assignment Problem....Pages 115-133
Concurrent Data Structures for Tree Search Algorithms....Pages 135-155
A Distributed Implementation of Asynchronous Parallel Branch and Bound....Pages 157-176
Experiments with a Parallel Synchronized Branch and Bound Algorithm....Pages 177-193
Parallel Local Search and Job Shop Scheduling....Pages 195-212
A Randomized Parallel Search Strategy....Pages 213-227
A Parallel Approximation Schema for Symmetric Linear Assignment Problem....Pages 229-242
Front Matter....Pages 243-243
Applications of Graph Scheduling Techniques in Parallelizing Irregular Scientific Computation....Pages 245-267
Atredia: A Mapping Environment for Dynamic Tree-Structured Problems....Pages 269-296
Regularising Transformations for Integral Dependencies....Pages 297-322
Some Strategies for Load Balancing....Pages 323-338
....