< Prev Next >
118
NATO SOFTWARE ENGINEERING CONFERENCE 1968
9. Working Papers

TOWARDS A METHODOLOGY OF COMPUTING SYSTEM DESIGN
by
B. Randell
Introduction
Three independent, but related, projects concerned with the methodology of computing system design have recently been reported. The work described by Dijkstra [1] concerns the design of a multiprogramming system for the X8 computer, at the Technological University, Eindhoven. Parnas and Darringer [2] have described their work on a language SODAS and demonstrated its use in the design of a fairly complex hardware system. Finally F. Zurcher and the present author [3] have given a short discussion of ‘iterative multilevel modelling’, the methodology being investigated to aid the design of an experimental multi-processing system [4] at the T. J. Watson Research Center. The purpose of the present note is to compare and contrast these three projects very briefly, and to attempt an identification of major problems still to be faced in achieving an effective methodology of computer system design.
Structuring the Design Process
The author’s belief is that the most important aspect of all three projects is the stress they put on achieving a structuring of the design process, and on making the system being designed reflect this structure.
Computing systems are undeniably extremely complex. They are notoriously difficult to design successfully, and when complete are difficult to understand or to modify. A system can be thought of as being the embodiment of a set of solutions to a set of distinct although related problems. All three projects lay stress on a careful consideration of the order in which the various problems should be tackled, and of the consequences of each design decision, both on those decisions which have already been taken, and on those problem areas which remain to be addressed.  Most important however, they make the system that they are designing contain explicit traces of the design process — in other words, the system is structured to demonstrate the way in which it was designed, and the designers’ views as to how the various problem areas are related to each other.
The papers by Dijkstra and by Zurcher and Randell both use the term ‘level of abstraction’. Their systems are constructed as a sequence of levels of abstraction, each consisting of a set of co-operating sequential processes [5]. In general, the primitives used to construct the programs which define processes on one level are provided by the processes of the immediately lower level. Each level therefore is in essence a set of solutions, specified directly in terms of appropriate quantities, to a set of problem areas which the designers have chosen to regard as being closely related. Less related problem areas are dealt with on other levels. For example, the lowest of Dijkstra’s levels is one which contains solutions to problems caused by timing constraints, and the fact that there is only a single processor in his computing system. The levels above this can ignore these problems, and assume, for example, the existence of a multiplicity of processors. By such means Dijkstra and his colleagues have retained control of the complexity of their system to such a degree that they could convince themselves, a priori, as to its logical correctness.
The Ordering of Design Decisions
There is probably no single ‘correct’ order in which to take a series of design decisions, though some orderings can usually be agreed to be better than others. Almost invariably some early decisions, thought at the time to have been clearly correct, will turn out to have been premature. The design structuring described above is an attempt to mitigate the effects of such occurrences.
There are two rather distinct approaches to the problem of deciding in what order to make design decisions. The ‘top-down’ approach involves starting at the outside limits of the proposed system, and gradually working down, at each stage attempting to define what a given component should do, before getting involved in decisions as to how the component should provide this function. Conversely the ‘bottom-up’ approach proceeds  by a gradually increasing complexity of combinations of buildingblocks. The top-down approach is for the designer who has faith in his