It is always exciting and fruitful when two disparate scientific fields are found to have much in common. Each field is enriched by the different perspective and insights of the other. This has happened recently with category theory and theoretical computer science.

The relations between category theory and computer science constitute an extremely active area of research at the moment. Some evidence of this is given in the short list of references at the end of the book. Among the many places where research is being done are: Aarhus, Carnegie-Mellon, Cambridge, Edinburgh, Glasgow, London, Milan, Oxford, Paris, Pennsylvania, Pisa, Stanford, and Sydney. Topics of current interest include the connections between category theory and functional programming, polymorphism, concurrency, abstract data structures, object-oriented programming, and hardware design.

This book is an introduction to category theory in which several of the connections with computer science are discussed in sufficient detail to give the reader some technical expertise and a feeling for the rich possibilities arising from the happy connection between these two subjects.

What is category theory?

The notion of function is one of the most fundamental in mathematics and science. Functions are used to model variation — for example, the motion of a particle in space; the variation of a quantity like temperature over a space; the symmetries of a geometric object, or of physical laws; the variation of the state of a system over time.

In the previous chapter we introduced the notion of a sequential process (agreeing that where no confusion would arise, the term process would be sufficient) in an informal way. Now we need to formalise this concept, and to provide some concrete examples of the representation of a process which will enable us to clarify the basic ideas behind systems of concurrent processes. We begin, however, by considering some of the issues concerning the nature of concurrent activity, and describing some of the notations which have been proposed whereby concurrency may be introduced into a program.

Specification of Concurrent Activity

There are a variety of ways of talking about concurrency, some of which have found their way into programming languages in various guises, and some of which are merely notational mechanisms for describing parallel activity.

When discussing the ways in which parallel activity can be specified within a programming language or system, it is useful to consider two orthogonal features of any proposed method. The first is the specification of where in a program a separate process may be started, and where, if at all, it terminates. The specification of where a new process may begin and end provides some synchronisation points within the concurrent program. We assume that it is possible to specify that two processes may execute in parallel, and it is at that point that the two processes are assumed to be synchronised.

Concurrency has been with us for a long time. The idea of different tasks being carried out at the same time, in order to achieve a particular end result more quickly, has been with us from time immemorial. Sometimes the tasks may be regarded as independent of one another. Two gardeners, one planting potatoes and the other cutting the lawn (provided the potatoes are not to be planted on the lawn!) will complete the two tasks in the time it takes to do just one of them. Sometimes the tasks are dependent upon each other, as in a team activity such as is found in a well-run hospital operating theatre. Here, each member of the team has to co-operate fully with the other members, but each member has his/her own well-defined task to carry out.

Concurrency has also been present in computers for almost as long as computers themselves have existed. Early on in the development of the electronic digital computer it was realised that there was an enormous discrepancy in the speeds of operation of electro-mechanical peripheral devices and the purely electronic central processing unit. The logical resolution of this discrepancy was to allow the peripheral device to operate independently of the central processor, making it feasible for the processor to make productive use of the time that the peripheral device is operating, rather than have to wait until a slow operation has been completed.

As long as all of the concurrent processes are proceeding completely independently of each other, we would expect them all to continue at their own speed until they terminate (if they do). If this does not happen, that is if the results of a process are affected by the presence or absence of another supposedly independent process, then we have to investigate the underlying mechanism to find the reason for this problem. For the purposes of the discussion of the concurrent processes themselves, they will have an effect on one another only if they are required to communicate with each other.

We have already seen one example of inter-process communication as manifested in one of the process creation and deletion methods. This entailed the parent process calling the fork operation to initiate the child process, and the subsequent join operation (if there is one) as a way of resynchronising the parent and child. These two operations are very restrictive, allowing as they do the parent and child to synchronise with each other only when the child begins and ends its execution. What is required is a more general mechanism (or mechanisms) by which two processes may communicate with each other, not just at the beginning and end of the lives of the processes. A discussion of several possible methods is the subject of this chapter.

For a number of years, Concurrent Programming was considered only to arise as a component in the study of Operating Systems. To some extent this attitude is understandable, in that matters concerning the scheduling of concurrent activity on a limited number (often one!) of processing units, and the detection/prevention of deadlock, are still regarded as the responsibility of an operating system. Historically, it is also the case that concurrent activity within a computing system was provided exclusively by the operating system for its own purposes, such as supporting multiple concurrent users.

It has become clear in recent years, however, that concurrent programming is a subject of study in its own right, primarily because it is now recognised that the use of parallelism can be beneficial as much to the applications programmer as it is to the systems programmer. It is also now clear that the principles governing the design, and the techniques employed in the implementation of concurrent programs belong more to the study of programming than to the management of the resources of a computer system.

This book is based on a course of lectures given over a number of years initially to third, and more recently to second year undergraduates in Computing Science. True to the origins of the subject, the course began as the first part of a course in operating systems, but was later separated off and has now become part of a course in advanced programming techniques.

We introduce here a simple concurrency kernel, showing how it may be used to provide pseudo-concurrency on a single processor, and also in the chapter we shall show how some of the concurrency constructs introduced in chapters 4 and 5 may be implemented.

We assume that the machine on which the kernel is to be implemented consists of a single processor of the conventional type with a single monolithic address space. A simple Motorola M68000 based system would be an appropriate type of system on which to run the kernel. To make the kernel more useful, it would be possible to consider hardware which provides a virtual address translation capability, in which case the various processes could be provided with distinct address spaces in which to operate. This, however, not only makes the kernel more complicated, but also makes sharing of memory more difficult. For the purposes of the simple kernel which we are considering here, we shall assume a single (shared) address space.

The implementation language will be Pascal, and for simplicity we shall assume that a hypothetical Pascal machine has been implemented on top of the basic hardware. Apart from the ability to run Pascal programs, we shall also require some additional features to support the concurrency kernel to be constructed. It is clear that much of the underlying support, both for Pascal itself and for the concurrency kernel, will have to be provided through a small amount of assembly code.

Before embarking upon a discussion of the concurrency facilities provided by various programming languages, it is necessary to issue an apology and a warning. The set of languages discussed in this chapter is intended to be a representative selection of languages available at the present time, which between them illustrate a number of different approaches to concurrency. It is hoped that no reader will feel offended at not finding his favourite concurrent language in the discussion. Examples are chosen to demonstrate a variety of treatments of controlled access to shared data, usually in the form of a shared data structure with limited access to the operations on the data structure (i.e. variations on the ‘monitor’ theme), and also languages supporting some form of message passing or mailbox handling are considered.

It should be clear that beneath each of the mechanisms to be found in any of the languages discussed in this chapter, some lower level code (or hardware) must be supplied to provide, if not the reality, then the illusion of concurrency. Beneath any successful concurrent language there is a system which manages the concurrency, schedules processes onto processors, provides the fundamental operations to implement process creation and deletion, and to provide communication facilities.

When any new language is designed, the designer attempts to correct many of the inadequacies (as he sees them) of one or more existing languages.

In the previous chapter we considered the basic problem of communication between processes, and reduced it to the problem of preventing two processes from accessing the same shared resources simultaneously. It should be clear that from such mechanisms it is possible to construct a large number of different methods for communication. It is also clear that the relationship between the lowlevel mechanisms described in the previous chapter and the higherlevel constructs is similar to the relationship between a low-level assembly language program and the corresponding program in a highlevel language; the first provides a basic mechanism, which clearly is sufficient, if inconvenient, to implement all the necessary synchronisation. The second expresses the solution to the problem in a much more “problem oriented” fashion.

In this chapter we shall consider a number of high-level constructs which have been proposed which allow a more structured approach to many inter-process communication/synchronisation problems. In the same way that the use of high-level languages allows the programmer to express his algorithms in a more natural way, and hence will make the inclusion of simple logical errors less likely, so the use of high-level synchronisation constructs in concurrent programs will also tend to reduce the incidence of elementary concurrent programming errors.

To take a small example, consider program 4.1, which uses binary semaphores to provide an implementation of the critical section problem (c.f. program 3.12).

All the high-level constructs discussed in the previous chapter have been of the “shared data” form. By this we mean that processes wishing to communicate with each other do so not by addressing one another directly, but by accessing data which is known and available to them all. The constructs also provide ways of accessing the shared data which ensure that the data itself is not compromised by undesirable simultaneous accesses by competing processes by offering operations in the form of procedures and functions to control the manipulation of the data. The data structure itself is purely passive, and changes are made to the structure by allowing procedures and functions to be called by the active elements in the system, namely the processes. As these procedures are called, they in a sense become part of the process which calls them, and the data itself temporarily becomes part of the address space of the calling process. We could also use the term “procedure oriented” to describe this view. We observe that the competing processes are not required to have any knowledge of the identities of their competitors, but merely to know the name of the object(s) they wish to access, and which operation(s) they wish to apply to the data.

By contrast, we shall now discuss a different class of techniques for allowing concurrent processes to communicate with each other.

Overview

Aims

This chapter describes a set of preliminary layout experiments using the system of three-dimensional abutment just described. The experiments are designed to configure the system and prepare the way for the experiments described in the next chapter. Specifically, the following questions are addressed:

• What are the important components of the merit functions?

• How should the components of the merit functions be weighted?

• What are the best algorithm control strategies?

• Is the system behaving sensibly?

The system is deliberately designed to operate in a highly flexible manner, and a primary goal of this first set of experiments is to determine those settings of the system parameters which produce the best layouts according to metrics which are discussed. This involves the postulation and evaluation of merit function components to control both placement and routing. In addition, the effect of different algorithm control strategies on layout is investigated, particularly the effect of the cluster shape and routing space controls. Finally, the system is used on circuits which are known to have optimal embeddings in the three-dimensional framework, and the results are used to indicate that the system exhibits appropriate behaviour and that the chosen system parameters are suitable.

Methods

The general experimental method used to determine the effect of some parameter or algorithm control is now described. First, a set of circuits for which layouts are constructed is defined. A variety of mainly random logic circuits is chosen in order to measure the layout system behaviour for a range of circuits. Each circuit is described in terms of simple NAND gates.

The configuration file of the Qudos Layout Editor describes routable layers such as metal and polysilicon and via layers which describe the relationship between routable layers. For three-dimensional CMOS SOI design rules, a vertical connection is described by a metal layer with no contact overlap. The contact overlap will be provided on the planar metal layer to which the vertical metal layer connects. The structure of the layers is shown in Figure A.1. The layer ‘Dummy’ avoids a limitation of the system, and is introduced to maintain full design rule checking. The corresponding configuration file is included below.