Mode :
Check : XHTML 1.0 Strict

Parallel Programs for the Transputer

Published 1991 by Prentice Hall International (UK) Ltd
ISBN-10: 0-13-651480-4
254 Pages


frontcover 0-13-651480-4

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



Chapter 0 - Introduction

	Parallel Computer Efficiency
		Replicated Structures
		Control Structures
	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
		Irregular Networks
		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
	Expanding Data Sets
		One-Dimensional Expansion
		Two-Dimensional Expansion
		Performance Issues
	Communicating Data Sets
		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



arrow upBack to the top

Last modification: 6/14/2023 3:57:10 PM