Hypercube Algorithms

With Applications to Image Processing and Pattern Recognition

Sanjay Ranka, Sartaj Sahni (Autoren)

Buch | Hardcover

237 Seiten

1990 | 1990 ed.
Springer-Verlag New York Inc.
978-0-387-97322-7 (ISBN)

Titel ist leider vergriffen;
keine Neuauflage

Artikel merken

Fundamentals algorithms for SIMD and MIMD hypercubes are developed. These include algorithms for such problems as data broadcasting, data sum, prefix sum, shift, data circulation, data accumulation, sorting, random access reads and writes and data permutation. The fundamental algorithms are then used to obtain efficient hypercube algorithms for matrix multiplication, image processing problems such as convolution, template matching, hough transform, clustering and image processing transformation, and string editing. Most of the algorithms in this book are for hypercubes with the number of processors being a function of problems size. However, for image processing problems, the book also includes algorithms for and MIMD hypercube with a small number of processes. Experimental results on an NCUBE/77 MIMD hypercube are also presented. The book is suitable for use in a one-semester or one-quarter course on hypercube algorithms. For students with no prior exposure to parallel algorithms, it is recommended that one week will be spent on the material in chapter 1, about six weeks on chapter 2 and one week on chapter 3. The remainder of the term can be spent covering topics from the rest of the book.

1 Introduction.- 1.1 Parallel Architectures.- 1.2 Embedding In A Hypercube.- 1.3 Performance Measures.- 2 Fundamental Operations.- 2.1 Data Broadcasting.- 2.2 Window Broadcast.- 2.3 Data Sum.- 2.4 Prefix Sum.- 2.5 Shift.- 2.6 Data Circulation.- 2.7 Even, Odd, And All Shifts.- 2.8 Consecutive Sum.- 2.9 Adjacent Sum.- 2.10 Data Accumulation.- 2.11 Rank.- 2.12 Concentrate.- 2.13 Distribute.- 2.14 Generalize.- 2.15 Sorting.- 2.16 Random Access Read.- 2.17 Random Access Write.- 2.18 BPC Permutations.- 2.19 Summary.- 3 SIMD Matrix Multiplication.- 3.1 n3 Processors.- 3.2 n2 Processors.- 3.3 n2r, 1? r ? n Processors.- 3.4 r2, 1? r ? n Processors.- 3.5 Summary.- 4 One Dimensional Convolution.- 4.1 The Problem.- 4.2 O(M) Memory Algorithms.- 4.3 O(1) Memory MIMD Algorithm.- 4.4 O(l) Memory SIMD Algorithm.- 5 Template Matching.- 5.1 The Problem.- 5.2 General Square Templates.- 5.3 Kirsch Motivated Templates.- 5.4 Medium Grain Template Matching.- 6 Hough Transform.- 6.1 Introduction.- 6.2 MIMD Algorithm.- 6.3 SIMD Algorithms.- 6.4 NCUBE Algorithms.- 7 Clustering.- 7.1 Introduction.- 7.2 NM Processor Algorithms.- 7.3 Clustering On An NCUBE Hypercube.- 8 Image Transformations.- 8.1 Introduction.- 8.2 Shrinking and Expanding.- 8.3 Translation.- 8.4 Rotation.- 8.5 Scaling.- 9 SIMD String Editing.- 9.1 Introduction.- 9.2 Dynamic Programming Formulation.- 9.3 Shared Memory Parallel Algorithm.- 9.4 SIMD Hypercube Mapping.- References.

Erscheint lt. Verlag	18.10.1990
Reihe/Serie	Bilkent University Lecture Series
Zusatzinfo	Bibliography
Verlagsort	New York, NY
Sprache	englisch
Gewicht	620 g
Themenwelt	Mathematik / Informatik ► Informatik ► Grafik / Design
	Mathematik / Informatik ► Informatik ► Software Entwicklung
	Informatik ► Theorie / Studium ► Algorithmen
	Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
	Technik ► Elektrotechnik / Energietechnik
	Technik ► Nachrichtentechnik
Schlagworte	Bilkent University Lecture Series; vol. 1
ISBN-10	0-387-97322-2 / 0387973222
ISBN-13	978-0-387-97322-7 / 9780387973227
Zustand	Neuware