Parallel Programming in C for the Transputer

© D. Thiébaut, 1995

Parallel Programming in C For The Transputer is made available here by permission of the author as a service to the community. The content available here may be accessed freely via Web browsers, but may not be archived or reproduced without permission of the author.

This document covers primarily Parallel Programming and the application of parallel algorithms to a specific machine. Its target is the Inmos transputer, a RISC processor with networking capabilities which has gained a good reputation in Europe and is now becoming increasingly popular in the United States. It has been thoroughly reviewed by Kirk Bailey of Logical Systems who is responsible for the implementation of the Parallel-C compiler on which my book is based.

I chose the transputer because it offers good cost/performance trade-offs, making it attractive for small computer science or computer engineering departments, as well as for individual and/or engineers interested in faster processing speed for their PC, MacIntosh, or work station. Computer Systems Architects (CSA) currently sells a University Kit which allows multi-transputer systems to be added to Personal Computers for less than $500 per transputer. CSA also makes more sophisticated systems of up to 64 transputers with software configurable networks, offering a flexible support for the study of interconnection networks. I have experience with both of these systems and have used them in my classes.

The examples in this document are all written for the MS-DOS environment, on an IBM compatible. This makes this book unique as it provides the readers with a clear view of the many details involved in the interaction between the host and the parallel machine. Too frequently, such details are not covered in text books and are left to the users to discover on their own. This document makes it possible to design, program and integrate a sophisticated parallel program on a multiprocessor attached to an IBM PC or compatible.

The great majority of the books currently published in the field of parallel computation covers parallel algorithms. A drawback of such an approach is that the implementation of a simple algorithm may require radically different solutions depending on the target machine. For example, the efficient implementation of a histogram algorithm on a shared memory machine, on a message-passing machine, or on a data-parallel machine requires altogether different solutions. For this reason, learning parallel algorithms without the support of a specific machine is not sufficient to introduce someone to the challenges of parallel computation. Balancing the teaching of parallel algorithms with the programming of a parallel machine is paramount. Just as most computer science departments start first with a class on programming and data structures before studying algorithms, this html document takes the approach of first teaching how to program a message-passing parallel machine as an introduction to parallel algorithms. The ability to learn and understand parallel algorithms is greatly improved once one is already familiar with a multiprocessor machine. This freely-available web document, therefore, can be the perfect companion to a more abstract coverage of parallel algorithms in a class where the instructor will mix theory and general concepts along with a study of how they can be applied (successfully or not) in a message-passing environment.

The book is organized as follows:

Chapters 1 and 2: First I introduce the transputer and justify its use in the academic setting, and in the engineering lab (Chapter 1). This is followed by a presentation of the architecture of the transputer, a RISC processor augmented with on-chip memory and four ports, allowing various network topologies (Chapter 2).
Chapter 3: The reader is presented with a first program written in C. The actions necessary for compiling, linking, loading and running the program are explained, along with a clear description of how parallelism works in this environment.
Chapter 4: Once the reader is familiar with both the hardware and software environments, the communication primitives which form the backbone of all parallel programs running in a message-passing environment are presented. This introduces the user to the concepts of parallelism where two or more processor work in parallel and exchange information by sending each other messages.
Chapter 5: Building on the parallel C constructs just presented, Chapter 5 presents the library functions that support multitasking. In this chapter the user learns how to implements parallelism within a transputer, creating several tasks that run in parallel, sharing the same processor.
Chapter 6: This chapter is devoted to debugging. Debugger features and debugging techniques, with an emphasis on good programming practice are presented.
Chapter 7: What are deadlocks? How do they occur? Why? How likely are they? This chapter covers the sole subject of deadlocks, and answers these questions while addressing the issues associated with deadlocks.
Chapter 8: This chapter deals with performance and introduces standard definitions such as speedup and processor utilization, efficiency, and efficacy. Using execution-time measurements, and numerous examples, the influence of communication overhead, of granularity of communication as well as that of task-decomposition is evaluated.
Chapter 9: In this chapter I tackle the problem of program decomposition and use examples to illustrate code-driven and data-driven approaches.
Chapter 10: This last chapter builds up on the knowledge and skills acquired by the reader throughout the previous chapters and presents techniques for balancing the load of parallel programs. Using the N-queen puzzle as an example, I build up a complete dynamic load-balancing scheme and explore several important issues associated with this technique.

(Statistics of accesses to different parts of the book are available here!)

The audience for this Web document on parallel programming

This book is intended primarily for two audiences: undergraduate computer science or computer engineering majors, and engineers or computer enthusiasts looking at effective and economical ways to boost the performance of their personal computer or workstations, or to learn the principles of parallel programming with a modest investment.

A place in the Computer Science curriculum

This document is written as the support for a one semester or one trimester course on parallel programming. Because the book assumes a background in C and an understanding of elementary algorithms, the readers should have taken a Computer Science I (high level language programming in Pascal or C) and Computer Science II (Data structures) courses, as well as a course on (single-processor) algorithms. A background in assembly language is not necessary, although the section detailing the hardware of the transputer would be more beneficial for readers familiar with Intel or Motorola microprocessors.

It is also conceivable to use this html text as the support for a course covering parallel programming and parallel algorithms. In this case, the instructor would most likely start with this book and familiarize the students with the transputer and parallel programming. As the level of programming sophistication increases, the instructor could use some of the applications of parallel algorithms introduced in this document as a starting point to a theoretical coverage of similar algorithms, their complexity, and range of application.

Click here to see the Table of Contents, or get the accompanying software (R EADME file, and zip-compressed archive)

This article has been translated to Serbo-Croatian by Jovana Milutinovich (jovanam@webhostinggeeks.com) at Web Geeks .

Please send suggestions, comments, or requests to thiebaut@cs.smith.edu