Newsgroups: comp.parallel From: Chris Nevison Subject: BOOK: Laboratories for Parallel Computing Date: Thu, 11 Aug 1994 19:32:36 GMT Following is a contents listing of "Laboratories for Parallel Computing." I have included it here, because the book was developed on transputer-based hardware, save 1 module developed on an N-Cube. Lyle W. Bingham 100 Library Plaza csa@infonaut.com Transputer Product Manager 15 North 100 East (801) 374-2300 tel Computer System Architects Provo UT 84606-3100 (801) 374-2306 fax ---------- This book is the combined result of work from the UParCC (Undergraduate Parallel Computing Curriculum) workshops conducted by Chris Nevison and others under the NSF UFE (Undergraduate Faculty Enhancement) and UCCD (Undergraduate Course and Curriculum Development) grant programs. The workshop participants developed modules for teaching parallel computing and continued to develop the course materials through follow-on workshops. All laboratories were tested in the classroom, in fact, the draft set of laboratories was distributed for use and feedback to more than 100 colleges and universities world wide. An instructors guide is available by ftp. The fifteen author names and addresses are included in the text. Laboratories for Parallel Computing is published by Jones and Bartlett of Boston. Information on world-wide sources for the book are found at the end of the following table of contents. Library of Congress Information: Laboratories for parallel computing / edited by Chris Nevison p. cm. Includes bibliographical references ISBN 0-86720-470-2 1. Parallel processing (Computer Science)-Study and teaching. I. Nevison, Christopher QA76.58.L33 1994 93-46893 004'.35'078-dc20 CIP Contents: Part I Introductory Modules Module 1 A First Occam Program for Multiple Transputers Daniel C. Hyde Introduction References Lab 1.1 Practicing the Occam Programming Language Lab 1.2 An Experiment in Timing on Multiple Transputers Appendix 1.A A Methodology for Developing Occam Programs Appendix 1.B Random Numbers Appendix 1.C Timing Occam Programs Appendix 1.D Example of an Occam Program on Multiple Transputers Appendix 1.E Example of an Occam Program on Multiple Transputers D7205 Version Module 2 A First Logical Systems C Program for Multiple Transputers Daniel C. Hyde Introduction References Lab 2.1 Programming in a Parallel C Lab 2.2 An Experiment in Timing on Multiple Transputers Appendix 1.A Random Numbers Appendix 1.B Timing Programs Appendix 1.C How to Make and Use .nif Files Module 3 Using the Occam Toolset Debugger Paul T. Tymann Introduction Debugging Transputer Programs Hints for Debugging Occam Programs References Part II Concepts of Parallel Computing Module 4 Deadlock and Deadlock-Free Routing Daniel C. Hyde Introduction Deadlock in Message Passing Systems Avoiding Communication Deadlock Avoiding Cyclic Deadlock References Lab 4.1 Deadlock Lab 4.2 Deadlock-Free Routing Module 5 Starvation and Fairness Daniel C. Hyde Introduction References Lab 5.1 Starvation and Fairness Module 6 Load Balancing for Matrix Vector Multiplication Steve Hurley Introduction Dense Matrix Vector Multiplication Sparse Matrix Vector Multiplication Conclusion References Lab 6.1 Dense Matrix Vector Multiplication Speedup and Efficiency Lab 6.2 Matrix Vector Multiplication for Arbitrary Size Matrices Lab 6.3 Simulated Annealing for Load Balancing Sparse Matrix Multiplication Lab 6.4 Sparse Matrix Vector Multiplication with Load Balancing Module 7 The Parallel Producer/Consumer Problem Scott R. Cannon Introduction References Lab 7.1 One Producer, One Consumer in a Shared Memory Model Lab 7.2 Hiding I/O in the Producer/Consumer Problem Lab 7.3 The Producer/Consumer Problem in Message Passing Systems Lab 7.4 Many Producers and Many Consumers in Parallel Using Linda Lab 7.5 Voice Processing Appendix 7.A Library Routine Resources Appendix 7.B Audio System Implementation Module 8 The Odd-Even Transposition Sort: An Example of Program Development Nan C. Schaller Introduction The Algorithm SIMD Implementation Conversion from SIMD to MIMD MIMD Implementation Using N Processors for N Items MIMD Implementation Using Fewer Processors than Items Optimization Questions and Problems References Lab 8.1 SIMD Implementation of Odd-Even Sort Lab 8.2 MIMD Implementation, N Items, N Processors Lab 8.3 MIMD Implementation, Fewer Processors than Items Lab 8.4 Optimization Part III Applications of Parallel Computing Module 9 Parallel Merge Sort G. Michael Schneider Introduction 2-Way Parallel Merge Sort 2-Way Merge Sort on a Hypercube Analysis of 2-Way Parallel Merge Sort 4-Way Parallel Merge Sort Ternary Tree 4-Way Merge Summary References Lab 9.1 Efficiency of 2-Way Parallel Merge Sort Lab 9.2 2-Way Parallel Merge Sort on a Hypercube Lab 9.3 Efficiency of 3-Way Parallel Merge Sort Appendix 9.A Quicksort Module 10 Searching in Parallel: A Case Study with the Single-Source, Shortest Path Algorithm Robert M. Harlan Introduction The Problem The Sequential Algorithm Potential Parallelism Synchronous, Shared-Memory Implementation Asynchronous, Shared-Memory Implementation Distributed Memory Implementation Cases Where P is Greater than N Conclusion Acknowledgments References Lab 10.1 Speedup and Efficiency for the Parallel Search Lab 10.2 Varying the Number of Processors Lab 10.3 A SIMD Implementation Module 11 Parallel Connectivity and Bridge Algorithms David A. Hastings Introduction Definitions Problem Definition Potential Parallelism Implementation of the Parallel Bridge Algorithm Summary References Lab 11.1 The Parallel Bridge Algorithm Lab 11.2 The Parallel Connectivity Algorithm Lab 11.3 The Combined Parallel Bridge and Connectivity Algorithm Module 12 Computing Optimal Binary Search Trees Using Dynamic Programming Patricia Prather Pineo Introduction Dynamic Programming A Parallel Implementation Mapping the Parallel Algorithm to Processors References Lab 12.1 A Sequential Algorithm Lab 12.2 A Parallel Minimal Binary Search Tree Algorithm Module 13 Converting a Sequential Parsing Algorithm to a Parallel Algorithm Using a Pipeline Jane C. Hill Introduction The Problem Defined A Parallel Algorithm Using n processors Algorithm 2: A Parallel-by-Column Algorithm Load Balancing for Parallel-by-Column Algorithm 3: A Parallel-by-Cell Algorithm Efficiency of the Parallel Algorithms Conclusion Questions and Exercises References Lab 13.1 Load Balancing Lab 13.2 Implementing a Parallel CYK Algorithm Module 14 Simpson's Rule for Integration Richard Nau Introduction Pascal Program Two Processors A Pipeline of Processors On Timing Lab 14.1 Implementation of Simpson's Rule in Parallel Lab 14.2 Timing of Simpson's Rule in Parallel Module 15 A Parallel Cubic Spline Algorithm Rodney S. Tosten and L. Carl Leinbach Introduction Statement of the Problem Constructing Cubic Splines Sequential Algorithm for Establishing the cis Fundamental Parallel Approach The Naive Stopping Approach The Efficient Stopping Approach Calculating the Remaining Coefficients and x, y Spline Points Timing Studies on Algorithms References Lab 15.1 A Parallel Cubic Spline Algorithm: Generating the Cis Lab 15.2 A Parallel Cubic Spline Algorithm: Implementing the Efficient Algorithm and Generating the x, y Spline Points Lab 15.3 A Parallel Cubic Spline Algorithm: Timing and Message Studies Module 16 Numerical Solution of the Wave Equation: An Example of Data Parallel Computing Christopher H. Nevison Introduction Physics Numerical Analysis A Sequential Algorithm Data Dependencies The SIMD Approach The MIMD Approach Problem Size and Granularity References Lab 16.1 A SIMD Implementation of the Wave Equation Program Lab 16.2 A MIMD Implementation of the Wave Equation Program Lab 16.3 Granularity Part IV Case Studies Module 17 A Parallel Prime Number Sieve: A Case Study Christopher H. Nevison Introduction The Problem Abstract Parallelism The Pipeline Load Balancing Speedup and Efficiency Reducing On-Processor Parallelism Communication Issues Amdahl's Law Summary Questions and Problems References Lab 17.1 Speedup and Buffering Lab 17.2 Overlapping Communications with Computation Lab 17.3 Dynamic Load Balancing Module 18 Performance Modeling of Parallel Processing Systems Alois Ferscha Introduction Performance Modeling with PRM-Nets Exercises Technical Information References ---------- "Laboratories for Parallel Computing" may be purchased for $39.95 plus shipping from: Computer System Architects 100 Library Plaza (801) 374-2300 /(800) 753-4CSA telephone 15 North 100 East (801) 374-2306 fax Provo, Utah 84606-3100 csa@infonaut.com Computer System Architects manufactures the Transputer Education Kit, SuperSetPlus.64 and SuperSetUltra.16 multi-transputer systems and other transputer-based hardware used for teaching parallel computing. Information and quotations are available upon request. ---------- Worldwide pricing and availability information on "Laboratories for Parallel Computing" is available from Jones & Bartlett or their distributors: Jones and Bartlett Publishers, Inc. International Marketing Department One Exeter Plaza Boston, MA 02116 Phone 617-859-3900 800-832-0034 (Order desk only) Fax 617-859-7675 Canada Copp Clark Longman, Ltd. 2775 Matheson Blvd, East Mississauga, ON L4W 4P7 Canada Phone 905-238-6074 800-263-4374 (Order desk only) Fax: 905-238-6075 United Kingdom, Scandinavia, Europe Sales and Marketing Richard Warner Jones and Bartlett Publishers, Int'l 7 Melrose Terrace London W6 7RS, England Phone: 071-371-2119 Fax: 071-371-2878 Place Orders with: Plymbridge Distributors, Ltd. Plymbridge House, Estover Road Plymouth Devon PL6 7PZ, England Phone: 0752 695745 Fax: 0752 695699 Middle East Anthony Rudkin Associates PO Box 15 51 Commarket Street Oxford OX1 3EB, England Phone: 0865 724627 Fax: 0865 792309 Iran Farhad Maftoon Anthony Rudkin Associates PO Box 15115-133 Tehran, Iran Phone: 21 851 363 Fax: 21 851 362 Hong Kong, Taiwan, Korea Benjamin Ho 43-G Joo Chiat Lane Singapore 1542 Republic of Singapore Phone: 4409536 Fax: 3461126 Southeast Asia (Not covered by Benjamin Ho above) Topan Company (S) Pte, Ltd. No 38, Liu Fang Road Box 22 Jurong Town Post Office Jurong, Singapore 2262 Phone: 65 265 6666 Fax: 65 261 7875 Australia, New Zealand Thomas Nelson Australia 102 Dodds Street South Melbourne Victoria 3205 Australia Phone: 03 685 4111 Fax: 03 685 4199 Japan Toppan Company, Ltd. Froebel-Kan Building 3-1 Kanda Ogawamachi Chiyoda-ku Tokyo 101 Japan Phone: 03-32953461 Fax: 03 3293 5963 South Africa Marian De Wet Marketing Services PO Box 12122 Cape Topwn 8010 Union of South Africa Phone: 021 686 6356 Fax: 021 686 4590