Parallel Algorithms for Regular Architectures.pdf

(1354 KB) Pobierz
Page iii
Parallel Algorithms for Regular Architectures: Meshes and Pyramids
Russ Miller
Quentin F. Stout
The MIT Press
Cambridge, Massachusetts
London, England
Page iv
©
1996 by The Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical
means (including photocopying, recording, or information storage and retrieval) without permission in
writing from the publisher.
Library of Congress Cataloging-in-Publication Data
Miller, Russ.
Parallel algorithms for regular architectures: meshes and pyramids.
Bibliography: p.
1. Parallel programming (Computer science) 2. Algorithms.
3. Computer architecture. I. Stout, Quentin F. II. Title. III. Series
QA76.6.M5226 1996 005.1 87-35360
ISBN 0-262-13233-8
Page vii
Contents
List of Figures
Preface
1 Overview
1.1 Introduction
1.2 Models of Computation
1.3 Forms of Input
1.4 Problems
1.5 Data Movement Operations
1.6 Sample Algorithms
1.7 Further Remarks
2 Fundamental Mesh Algorithms
2.1 Introduction
2.2 Definitions
2.3 Lower Bounds
2.4 Primitive Mesh Algorithms
ix
xiii
1
1
3
14
16
22
29
44
45
45
45
46
48
2.5 Matrix Algorithms
2.6 Algorithms Involving Ordered Data
2.7 Further Remarks
3 Mesh Algorithms for Images and Graphs
3.1 Introduction
3.2 Fundamental Graph Algorithms
3.3 Connected Components
3.4 Internal Distances
3.5 Convexity
3.6 External Distances
3.7 Further Remarks
4 Mesh Algorithms for Computational Geometry
4.1 Introduction
4.2 Preliminaries
4.3 The Convex Hull
4.4 Smallest Enclosing Figures
50
68
87
89
89
90
103
111
121
131
141
147
147
149
154
162
Page viii
4.5 Nearest Point Problems
4.6 Line Segments and Simple Polygons
4.7 Intersection of Convex Sets
166
175
184
4.8 Diameter
4.9 Iso-oriented Rectangles and Polygons
4.10 Voronoi Diagram
4.11 Further Remarks
5 Tree-like Pyramid Algorithms
5.1 Introduction
5.2 Definitions
5.3 Lower Bounds
5.4 Fundamental Algorithms
5.5 Image Algorithms
5.6 Further Remarks
6 Hybrid Pyramid Algorithms
6.1 Introduction
6.2 Graphs as Unordered Edges
6.3 Graphs as Adjacency Matrices
6.4 Digitized Pictures
6.5 Convexity
6.6 Data Movement Operations
6.7 Optimality
6.8 Further Remarks
187
188
194
209
213
213
214
214
216
222
239
241
241
243
250
253
261
267
276
280
A Order Notation
B Recurrence Equations
Bibliography
285
287
289
Page ix
List of Figures
1.1 A mesh computer of size
n.
1.2 Indexing schemes for the processors of a mesh.
1.3 A pyramid computer of size 16.
1.4 A mesh-of-trees of base size
n
= 16.
1.5 A hypercube of size
n
= 16.
1.6 Convex hull of
S.
1.7 Angles of incidence and angles of support.
1.8 Searching to find interval for points.
1.9 A picture containing 'blob-like' figures.
1.10 Pictures consisting of non-'blob-like' figures.
1.11 Sample labeling after recursively labeling each quadrant.
1.12 Upper and lower tangent lines.
1.13 Using
p
l
and
p
r
to determine extreme points.
7
8
10
12
13
19
20
28
31
32
33
37
43
2.1 A mesh computer of size
n
2
.
46

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin