Parallel Programs for the Transputer
Published 1991 by Prentice Hall International (UK) Ltd
ISBN-10: 0-13-651480-4
254 Pages
Preface
Parallel computing has come of age and is moving into the mainstream of the computing world. As this technology matures, the variety and number of parallel computers are growing rapidly. Multiple-instruction, multiple-data machines, which use many communicating processors, are one of the several types of parallel computers available today and are becoming increasingly popular. The transputer, a single-chip microcomputer developed by the Inmos Corp., was the first of these communicating processors to be built into a single, integrated circuit, and to be supported within a complete parallel computing environment. This environment includes not only internal hardware support for parallelism within the transputer itself, but also a parallel programming language, occam, and a supporting development system.
One of the truly enjoyable aspects of parallel computing with transputers is the variety of ways, and the ease with which, transputers can be used to build different parallel computers. In this book, I explore and illustrate this diversity. In addition to a discussion of parallel computing approaches and examples of a variety of computer architectures, six programming methodologies for parallel computing are presented. Each of these methodologies is developed with numerous programs illustrating techniques ranging from the simple to the complex. The techniques are compared, the various practical trade-offs between them examined, and their relative performance and efficiency measured. Every complete program presented is taken directly from a working example.
My goal is to illustrate and educate, not to create performance benchmarks. None of the example programs are optimized for execution speed, and any performance measures are presented solely for comparison with other examples. Indeed, the programs are all compiled with the error checking compiler switches turned on. This may increase one's confidence in a program but certainly does not enhance the program's performance.
It is most definitely not my expectation that these programming examples are "perfect," or even unique. Programs can often be written in a half dozen different ways, and the examples in this book are no exception. The programs presented here are used to illustrate, explain, analyze, and compare methods that many people can readily program themselves.
This book will be useful to both the novice and the experienced parallel programmer for the transputer, although a rudimentary knowledge of occam and transputers will be very helpful. Novice users will benefit from the introduction of programming approaches and their illustration. Experienced programmers will find the more complex examples and their comparisons with simpler routines useful and enlightening. In addition, readers familiar with some of the topics may not have explored all of the different methodologies presented. After a careful study of this book, any reader will be thoroughly familiar with a broad variety of parallel programming techniques for transputers, and will understand the system trade-offs involved in using them.
Although some readers may study chapters selectively, the topics do follow a logical developmental order, with the more difficult programming techniques presented later in the book. This developmental order is found within each chapter as well as in the progression of chapters. Experienced programmers may wish to proceed directly to the more advanced material.
The first two chapters, 0 and 1, are primarily introductory in nature. In these chapters is presented an overview of parallel computing efficiency, transputer systems, occam, and of general classes of parallel computers. The first part of Chapter 2 is also introductory and contains a discussion of configuration descriptions; in the second part, a variety of architectures is described and configured. The remaining chapters continue with the actual presentation of various programming methods, together with an analysis of the efficiency of the techniques illustrated.
A good book is never written in isolation, and this book is no exception. I wish to express my appreciation to those colleagues whose suggestions or ideas contributed to the many examples in this book. Thanks are also due to my patient grammarian and wife, Sueanne, and to the editors and reviewers, especially David Cok, whose corrections, additions, and deletions did so much to improve and clarify the writing. Any remaining faults are my own.
Ronald S. Cok
Contents
Preface Chapter 0 - Introduction Parallel Computer Efficiency Transputers occam SEQ PAR CHAN ALT Replicated Structures Control Structures Debugging Miscellaneous In Summary Chapter 1 - SISD, SIMD, MIMD, and All That Multiple Data Paths Multiple Instruction Paths Shared Memory Distributed Memory Architectural Issues In Summary Chapter 2 - Architectures Configuration Descriptions Networks Irregular Networks Rings Toroids Hypercubes Ternary Trees In Summary Chapter 3 - Processor Farms A Simple Processor Farm Efficiency Concerns Large Processor Farms Storage and Communication Issues A Real-World Example Efficiency Measurements In Summary Chapter 4 - Pipeline Processing Program Issues Pipeline Efficiency A Pipeline Example Communication Methods Single Buffering Double Buffering Triple Buffering A Buffered Pipeline Test Multidimensional Pipelines In Summary Chapter 5 - Data Parallelism Program Issues Data Distribution Loading Data A Simple Load Routine A Fast Load Routine Bidirectional Loading Performance Measures Sampling Expanding Data Sets One-Dimensional Expansion Two-Dimensional Expansion Performance Issues Communicating Data Sets Shifting Performance Issues An Efficiency Comparison In Summary Chapter 6 - Deadlock-Free Routing Program Issues One-Way Virtual Channels A One-Way Ring Router Two-Way Virtual Channels A Two-Way Ring Router A Four-Way Toroidal Router Performance Comparisons In Summary Chapter 7 - Worms Searching Strategies Bootstrapping a Processor A Simple, Sequential Worm A Simple, Parallel Worm A Robust, Exploratory Worm In Summary Chapter 8 - Real-Time Processing Interrupt Handlers A Simple Handler A Buffered Handler A FIFO Handler Performance Comparisons In Summary Bibliography Index
Back to the top