So far we have discussed the properties that a model of parallel computation ought to have and have claimed that models built from categorical data types have these properties. In this chapter we show how to build a simple but useful categorical data type, the type of join or concatenation lists, and illustrate its use as a model. We show how such a model satisfies the requirements, although some of the details are postponed to later chapters.

The language we construct for programming with lists is not different from other parallel list languages in major ways in the sense that most of the list operations are familiar maps, reductions, and prefixes. The differences are in the infrastructure that comes from the categorical data type construction: an equational transformation system, a deeper view of what operations on lists are, and a style of program development. When we develop more complex types, the construction suggests new operations that are not obvious from first principles.

For the next few chapters we concentrate on aspects of parallel computation on lists. We describe the categorical data type construction in more detail in Chapter 9 and move on to more complex types. The next few sections explain how to build lists in a categorical setting. They may be skipped by those who are not interested in the construction itself. The results of the construction and its implications are summarised in Section 5.5.

We have already discussed why a set of cost measures is important for a model of parallel computation. In this chapter we develop something stronger, a cost calculus. A cost calculus integrates cost information with equational rules, so that it becomes possible to decide the direction in which an equational substitution is cost-reducing. Unfortunately, a perfect cost calculus is not possible for any parallel programming system, so some compromises are necessary. It turns out that the simplicity of the mapping problem for lists, thanks to the standard topology, is just enough to permit a workable solution.

Cost Systems and Their Properties

Ways of measuring the cost of a partially developed program are critical to making informed decisions during the development. An ideal cost system has the following two properties:

1. It is compositional, so that the cost of a program depends in some straightforward way on the cost of its pieces. This is a difficult requirement in a parallel setting since it amounts to saying that the cost of a program piece depends only on its internal structure and behaviour and not on its context. However, parallel operations have to be concerned about the external properties of how their arguments and results are mapped to processors since there are costs associated with rearranging them. So, for parallel computing, contexts are critically important.

2. It is related to the calculational transformation system, so that the cost of a transformation can be associated with its rule.

In this chapter we define the categorical data types of graphs. Graphs are ubiquitous in computation, but they are subtly difficult to work with. This is partly because there are many divergent representations for graphs and it is hard to see past the representations to the essential properties of the data type.

We follow the now familiar strategy of defining constructors and building graphs as the limit of the resulting polynomial functor.

Graphs have a long history as data structures. Several specialised graph languages have been built (see, for example, [69]), but they all manipulate graphs using operations that alter single vertices and edges, rather than the monolithic operations we have been advocating.

An important approach to manipulating graphs is graph grammars. Graph grammars [71] are analogues of grammars for formal languages and build graphs by giving a set of production rules. Each left hand side denotes a graph template, while each right hand side denotes a replacement. The application of a rule occurs on a subgraph that matches the left hand side of some rule. The matching subgraph is removed from the graph (really a graph form) and replaced by the right hand side of the rule. Various different conventions are used to add edges connecting the new graph to the rest of the original graph. Graph grammars are primarily used for capturing structural information about the construction and transformation of graphs. They do not directly give rise to computations on graphs.

The second substantially technical issue in the design of parallel computers concerns the complexity of each of the processing elements. To a very significant extent this will reflect the target functionality of the system under consideration. If a parallel computer is intended for use in scientific calculations, then in all likelihood floating-point operations will be a sine qua non and appropriate units will be incorporated. On the other hand, a neural network might be most efficiently implemented with threshold logic units which don't compute normal arithmetic functions at all. Often, the only modifier on such a natural relationship will be an economic or technological one. Some desirable configurations may be too expensive for a particular application, and the performance penalty involved in a non-optimum solution may be acceptable. Alternatively, the benefits of a particularly compact implementation may outweigh those of optimum performance. There may even be cases where the generality of application of the system may not permit an optimum solution to be calculated at all. In such cases, a variety of solutions may be supportable.

We will begin our analysis of processor complexity by considering the variables which are involved, and the boundaries of those variables.

Analogue or digital?

Although almost all modern computers are built from digital circuits, this was not always, and need not necessarily be, so. The original, overwhelming reason for using digital circuits was because of the vastly improved noise immunity which could be obtained, particularly important when using highprecision numbers.

In order to make sense of the way in which users control parallel computers, we shall have to adopt a rather wider definition of the idea of programming than that which is usually taken. This is principally because of the existence of systems which are trained rather than programmed. Later in this chapter I shall attempt to show the equivalence between the two approaches but it is probably best to begin by considering how the conventional idea of programming is applied to parallel systems.

Parallel programming

There are three factors which we should take into account in order to arrive at a proper understanding of the differences between one type of parallel language and another and to appreciate where the use of each type is appropriate. These are whether the parallelism is hidden or explicit, which paradigm is employed and the level of the language. Although there is, inevitably, a certain amount of overlap between these factors, I shall treat them as though they were independent.

The embodiment of parallelism

There is really only one fundamental choice to be made here – should the parallelism embodied in a language be implicit or explicit? That is, should the parallelism be hidden from the programmers, or should it be specified by them? The first alternative is usually achieved by allowing the use of data types, in a program, which themselves comprise multiple data entities.

The purpose of this book has been to introduce the reader to the subject of parallel computing. In attempting to make the subject digestible, it is inevitable that a great deal of advanced material has been omitted. The reader whose interest has been kindled is directed to the bibliography, which follows this chapter, as a starting point for continued studies. In particular, a more rigorous treatment of advanced computer architectures is available in Advanced Computer Architectures by Hwang.

It should also be noted that parallel computing is a field in which progress occurs at a prodigious rate. So much work is being done that some startling new insight or technique is sure to be announced just after this book goes to press. In what follows, the reader should bear in mind the developing nature of the field. Nevertheless, a great deal of material has been presented here, and it is worthwhile making some attempt to summarise it in a structured manner.

I have attempted to make clear in the preceding chapters that understanding parallel computing is an hierarchical process. A valuable degree of insight into the subject can be obtained even at the level considered in the first chapter, where three basic classes or types of approach were identified. Thereafter, each stage of the process should augment the understanding already achieved. It is up to each reader to decide on the level of detail required.

As was indicated in Chapter 1, there is a prima facie case for supposing that parallel computers can be both more powerful and more cost-effective than serial machines. The case rests upon the twin supports of increased amount of computing power and, just as importantly, improved structure in terms of mapping to specific classes of problems and in terms of such parameters as processor-to-memory bandwidth.

This chapter concerns what is probably the most contentious area of the field of parallel computing – how to quantify the performance of these allegedly superior machines. There are at least two significant reasons why this should be difficult. First, parallel computers, of whatever sort, are attempts to map structures more closely to some particular type of data or problem. This immediately invites the question – on what set of data and problems should their performance be measured? Should it be only the set for which a particular system was designed, in which case how can one machine be compared with another, or should a wider range of tasks be used, with the immediate corollary – which set? Contrast this with the accepted view of the general-purpose serial computer, where a few convenient acronyms such as MIPS and MFLOPS (see Section 6.1.3) purport to tell the whole story. (That they evidently do not do so casts an interesting sidelight on our own problem.)

The second reason concerns the economic performance, or cost-effectiveness, of parallel systems.

Up to this point we have considered the subject of parallel computing as a series of almost separated facets – paradigms, languages, processor design, etc. – each of which can be examined in isolation. Of course, in arriving at the design of any real system, be it commercial or prototype, this approach is very far from the true manner of proceeding. In real system design, the watchword is usually compromise – compromise between specific and general applicability, compromise between user friendliness and efficiency in programming, compromise between the demands of high performance and low cost. No imaginary design exercise can do justice to the complexity or difficulty of this process, because the constraints in imaginary exercises are too flexible. In order to see how the various design facets interact, we need to examine real cases. This is the purpose of this chapter.

In it, I present a series of short articles concerning specific machines, each of which has been contributed by an author intimately concerned with the system in question. The brevity has been occasioned by the limited space available in a book of this sort, but it has had the beneficial effect of ensuring that the authors have concentrated on those areas which they consider to be important. Again, because of limited space I have curtailed the number of these contributions, although this has meant that some aspects of the subject remain unconsidered.

The Shorter Oxford English Dictionary defines the word paradigm as meaning pattern or example, but it is used here in its generally accepted sense in this field, where it is taken to imply a fundamental technique or key idea. This chapter, therefore, is concerned with describing the fundamental ideas behind the implementation of parallel computation.

Two matters need to be dealt with before we begin. First, the reader should avoid confusion between the basic approaches set out in Chapter 1 and the paradigms described here. In the final chapter of this book, I develop a taxonomy of parallel computing systems, i.e. a structured analysis of systems in which each succeeding stage is based on increasingly detailed properties. In this taxonomy, the first two levels of differentiation are on the basis of the three approaches of the first chapter, whereas the third level is based on the paradigms described here. This is shown in Figure 2.1.

Next, there is the whole subject of optical computing. In one sense, an optical component, such as a lens, is a data parallel computer of dedicated functionality (and formidable power). There is certainly an overlap in the functions of such components and those of, say, an image processing parallel computer of the conventional sort. A lens can perform a fourier transform (a kind of frequency analysis) on an image, literally at the speed of light, whereas a conventional computer requires many cycles of operation to achieve the same result.

Before attempting to understand the complexities of the subject of parallel computing, the intending user or student ought, perhaps, to ask why such an exotic approach is necessary. After all, ordinary, serial, computers are in successful and widespread use in every area of society in industrially developed nations, and obtaining a sufficient understanding of their use and operation is no simple task. It might even be argued that, since the only reason for using two computers in place of one is because the single device is insufficiently powerful, a better approach is to increase the power (presumably by technological improvements) of the single machine.

As is usually the case, such a simplistic approach to the problem conceals a number of significant points. There are many application areas where the available power of ‘ordinary’ computers is insufficient to obtain the desired results. In the area of computer vision, for example, this insufficiency is related to the amount of time available for computation, results being required at a rate suitable for, perhaps, autonomous vehicle guidance. In the case of weather forecasting, existing models, running on single computers, are certainly able to produce results. Unfortunately, these are somewhat lacking in accuracy, and improvements here depend on significant extensions to the scope of the computer modelling involved.

Whilst the two issues of control (what are all these parallel processors going to do?) and programming (how is the user to tell them all what to do?) are perhaps the most difficult conceptual aspects of parallel computing, the question of the connections between all the many system components is probably the hardest technical problem. There are two main levels at which the problem must be considered. At the first level, the connections between major system components, such as CPU, controller, data input and output devices, must be given careful consideration to avoid introducing bottlenecks which might destroy hoped-for performance. At the second level, connections within these major components, particularly between processing units and their associated memories, will be the major controlling factor of overall system performance. Within this area, an important conceptual difference exists between two alternative approaches to inter-processor communication. Individual pairs of elements may be either externally synchronised, in which case a controller ensures that if data is input at one end of a line it is simultaneously accepted at the other, or unsynchronised. In this latter case, the donating element signals that data is available, but the data is not transferred until the receiving element is ready to accept it.

In addition to this, technical problems are present. The first is the position and purpose of memory in the general structure.

The study of parallel computing is just about as old as that of computing itself. Indeed, the early machine architects and programmers (neither category would have described themselves in these terms) recognised no such delineations in their work, although the natural human predilection for describing any process as a sequence of operations on a series of variables soon entrenched this philosophy as the basis of all normal systems.

Once this basis had become firmly established, it required a definite effort of will to perceive that alternative approaches might be worthwhile, especially as the proliferation of potential techniques made understanding more difficult. Thus, today, newcomers to the field might be told, according to their informer's inclination, that parallel computing means the use of transputers, or neural networks, or systolic arrays, or any one of a seemingly endless number of possibilities. At this point, students have the alternatives of accepting that a single facet comprises the whole, or attempting their own processes of analysis and evaluation. The potential users of a system are as likely to be set on the wrong path as the right one toward fulfilling their own set of practical aims.

This book is an attempt to set out the general principles of parallel computing in a way which will be useful to student and user alike. The approach I adopt to the subject is top-down – the simplest and most fundamental principles are enunciated first, with each important area being subsequently treated in greater depth.