Hypercube Algorithms
with Applications to Image Processing and Pattern Recognition
Published on 14. December 2011
Book
Paperback/Softback
IX, 237 pages
978-1-4613-9694-9 (ISBN)
Description
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.
More details
Series
Edition
Softcover reprint of the original 1st ed. 1990
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Research
Illustrations
IX, 237 p.
Dimensions
Height: 244 mm
Width: 170 mm
Thickness: 14 mm
Weight
435 gr
ISBN-13
978-1-4613-9694-9 (9781461396949)
DOI
10.1007/978-1-4613-9692-5
Schweitzer Classification
Other editions
Additional editions
Sanjay Ranka | Sartaj Sahni
Hypercube Algorithms
with Applications to Image Processing and Pattern Recognition
Book
10/1990
Springer
€85.55
Article exhausted; check different version
Persons
WeixunWang is a software engineer in Amazon.com, Seattle,WA. He received his B.E. degree in software engineering from the Software Institute, Nanjing University, China, in 2007, and a Ph.D. degree in computer engineering from the University of Florida in 2011. His research interests include energy-aware computing, design automation of embedded systems, computer architecture, reconfigurable architectures and real-time scheduling. He has published more than 10 papers in these fields. He is a member of IEEE.
Prabhat Mishra is an Associate Professor in the Department of Computer and Information Science and Engineering (CISE) at the University of Florida. His research interests include design automation of embedded systems, hardware/software verification, VLSI CAD, and low-power reconfigurable architectures. He received his B.E. from Jadavpur University, Kolkata, in 1994, M.Tech. from the Indian Institute of Technology, Kharagpur in 1996, and Ph.D. from the University of California, Irvine, in 2004 - all in Computer Science. Prior to joining University of Florida, he spent several years in various semiconductor and design automation companies, including Intel, Motorola, Synopsys and Texas Instruments. He has published two books (Springer 2005 and MK 2008), nine book chapters and more than 80 research articles in premier journals and conferences. His research has been recognized by several awards including the NSF CAREER Award from the National Science Foundation, two best paper awards (VLSI Design 2011 and CODES+ISSS 2003), several best paper award nominations, and 2004 EDAA Outstanding Dissertation Award from the European Design Automation Association. He has also received the 2007 International Educator of the Year Award from the UF College of Engineering for his significant international research and teaching contributions. He currently serves as an Associate Editor of IEEE Design & Test of Computers (D&T), Guest Editor of IEEE Transactionson Computers (TC), the Information Director of ACM Transactions on Design Automation of Electronic Systems (TODAES), and as a program/organizing committee member of several ACM and IEEE conferences including ICCAD, DATE, ASPDAC, CODES+ISSS, and VLSI Design. He has also served as General Chair of IEEE High Level Design Validation and Test (HLDVT) 2010, Program Chair of HLDVT 2009, and Guest Editor of IEEE Design & Test of Computers (D&T), Journal of Electronic Testing (JETTA) and International Journal of Parallel Programming (IJPP). He is a senior member of ACM and a senior member of IEEE.
Sanjay Ranka is a Professor in the Department of Computer Information Science and Engineering at University of Florida. His current research interests are energy efficient computing, high performance computing, data mining and informatics. Most recently he was the Chief Technology Officer at Paramark where he developed real-time optimization software for optimizing marketing campaigns. Sanjay has also held positions as a tenured faculty member at Syracuse University and as a researcher/visitor at IBM T.J. Watson Research Labs and Hitachi America Limited. Sanjay earned his Ph.D. (Computer Science) from the University of Minnesota and a B. Tech. in Computer Science from IIT, Kanpur, India. He has coauthored two books: Elements of Neural Networks (MIT Press) and Hypercube Algorithm (Springer Verlag), 75 journal articles and 125 refereed conference articles. His recent work has received a student best paper award at ACM-BCB 2010, best paper runner up award at KDD-2009, a nomination for the Robbins Prize for the best paper in journal of Physics in Medicine and Biology for 2008, and a best paper award at ICN 2007. He is a fellow of the IEEE and AAAS and a member of IFIP Committee on System Modeling and Optimization. He is the associate Editor-in-Chief of the Journal of Parallel and Distributed Computing and an associate editor for IEEE Transactions onParallel and Distributed Computing, IEEE Transac
Content
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.