Hypercube Algorithms

1. Front Matter

   Pages i-ix

   PDF

2. Introduction

   • Sanjay Ranka, Sartaj Sahni

   Pages 1-22

3. Fundamental Operations

   • Sanjay Ranka, Sartaj Sahni

   Pages 23-93

4. SIMD Matrix Multiplication

   • Sanjay Ranka, Sartaj Sahni

   Pages 95-110

5. One Dimensional Convolution

   • Sanjay Ranka, Sartaj Sahni

   Pages 111-125

6. Template Matching

   • Sanjay Ranka, Sartaj Sahni

   Pages 127-143

7. Hough Transform

   • Sanjay Ranka, Sartaj Sahni

   Pages 145-166

8. Clustering

   • Sanjay Ranka, Sartaj Sahni

   Pages 167-184

9. Image Transformations

   • Sanjay Ranka, Sartaj Sahni

   Pages 185-199

10. SIMD String Editing

    • Sanjay Ranka, Sartaj Sahni

    Pages 201-229

11. Back Matter

    Pages 231-237

    PDF

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.

• algorithm
• algorithms
• clustering
• image processing
• pattern
• pattern recognition
• programming
• template
• algorithm analysis and problem complexity

• School of Computer and Information Science, Syracuse University, Syracuse, USA

  Sanjay Ranka

• Computer Science Department, University of Minnesota, Minneapolis, USA

  Sartaj Sahni

Policies and ethics