The design principles of Pascal-m and the justification for its existence are described in [1]. The language uses type-secure messages as a framework for the construction of concurrent program systems such as exist in loosely coupled computer networks. By eliminating both shared variables and interprocess pointers and by using mailboxes to hide the implementation of a service from its users, the language is particularly suited to the construction of the operating system components of such a network. At present the construction and maintenance of operating systems, even on single-processor machines, is a mystery to most programmers and is largely undertaken by self-appointed wizards. This is unlike the situation in some other branches of systems programming, for example compiler-writing, in which well-established mechanisms of program design and construction have been devised.
Pascal-m is designed to provide a framework within which the non-wizard can build wizard programs. Pascal was chosen as a base language for the sake of convenience (there happened to be a Pascal compiler, suitable for modification, on the UNIX system on which the development. commenced) and for its simplicity of design. The important areas of research are the message-sending mechanism (both in its linguistic expression and in its implementation aspects) and the extension of the ideas, for example to allow more precise specification of module interfaces so as to facilitate reasoning about the behaviour of programs. The desire to build a message-sending language derives from experience with the use and modification of UNIX at QMC; the design of Pascal-m derives from the languages CSP (developed by CAR Hoare) and LIMP (developed at QMC by J G Hunt) and from the design and construction of the operating system of the GEC 4080.
In order to test the efficacy of Pascal-m as a language with which to construct system programs, a test problem has been chosen: the problem is to construct a network of single-user machines which provide the user with program development aids and simple text-processing facilities at least as flexible as those which are provided under the UNIX operating system. The solution will be demonstrated by first constructing a single-user, single-machine operating system on a micro-processor, then by extending this into a simple network of communicating machines.
The construction of a UNIX-like operating system, which is user-extensible and user-modifiable, on a more-or-less conventional machine which does not directly support the message operation on which Pascal-m is based, is a useful challenge which requires attention both to the design of the language and to its implementation: the speed and ease with which it can be accomplished will show whether Pascal-m does indeed offer any significant advantages over existing approaches. The construction of an operating system which more thoroughly exploits the advantages of secure inter-process communication is a further challenge. The extension of Pascal-m to the case of message-communication over a network of machines (which should be amenable to machine additions and removals without interruption of other work) seems at the moment mostly to challenge the details of the implementation of the network-wide message-communication operation.
The investigators will be collaborating with Prof Coulouris at QMC. Hardware for the project will be supplied from the DCS Equipment Pool.
In the past twelve months there has been close cooperation between the PascaI-m project and the EMMI project (Coulouris). Effort this year has been mainly directed to the implementation of an operating system and a useful human/computer interface on a single workstation, as the first stage of a distributed implementation involving several workstations linked by a Cambridge Ring. A demonstration system has been implemented which has several on-screen windows (virtual terminals) providing concurrent interaction with a number of application-processes, running on an 8086 with 512k of memory (not all used yet) with Winchester disc and memory-mapped display. The demonstration system includes 26 concurrently-executing separate processes.
Seminars on the Pascal-m language and the initial implementation have been delivered at the Universities of Warwick, Essex, Newcastle, Kent and Oxford, at University and Imperial Colleges, London University, and at the DCS Workshop on Distributed Operating Systems held at Queen Mary College in April 1981.
In the past year the problems of implementing a machine code kernel which supports the process-process, process-device and device-process message passing within a single machine have been confronted and solved. It also supports simple store allocation (for stack and heap expansion). In the near future it will support run-time process-creation.
Communication between processes and devices takes the same form as Pascal-m process-process communication - a message is sent via a mailbox. Device mailboxes are normally created on a device to register, and are recognisable to the kernel. The kernel allows interrupt-controlled communications (e.g. with a keyboard or screen), simple i/o registers not connected with interrupts (e.g. for disc control blocks) and, with some ingenuity, even DMA transfers (we have a character-mapped display and a DMA disc). The kernel is still relatively small and surprisingly small - still less than 4k bytes of 8086 machine code.
The influence of cooperation with the EMMI project has been to focus on the problems of implementing a stand-alone system on a powerful workstation, of the type envisaged in that project. Most of the year has been occupied in building the language-support tools needed to compile, load and run such a system. At present programs are compiled and core images are constructed on an 11/34 (provided by SERC for the EMMI project) and loaded down a 9.6kb serial line into the 8086 (provided by Nexos, also for the EMMI project). An off-line Pascal-m has been provided by modifying the Amsterdam UNIX Pascal compiler, that produces a version of the Amsterdam intermediate language EM-1 called em-m. At present em-m is translated into 8086 machine code, so that the entire demonstration system runs as native code All the system-support programs, with the exception of the compiler, are at present written in C.
The Mark-2 implementation, which QMC have been developing since the autumn and which is almost ready for demonstration, includes a modified kernel which supports process creation. This implementation will enable a filing system (to each open file there corresponds a process, therefore file opens and closes correspond to process creation and destruction) to be written. As well as the new kernel, the new implementation means modifications to em-m, the compiler, and all the loaders. These have been written in Pascal.
An aim of the project was to investigate the potential of synchronised-message-sending constructs as a programming tool. To that end as few changes to Pascal as possible have been made in developing tools in Pascal-m. The design of the language has changed very little since first proposed but there have been some detailed changes [2] and a run-time type checking facility has been proposed [3] (but not yet implemented) to permit directory-processes to contain information of whose types they may remain ignorant.
1. S. Abramsky and R. Bornat, Pascal-m: A Language for Distributed Systems, QMC 1979
2. S. Abramsky, R. Bornat S.Cook and Shephard, The Pascal-m Language, QMC CSL report.
3. S. Cook, "Any" : A New Data Type for Pascal-m, QMC CSL report.
4. G. F. Coulouris, EMMI Progress Report, SERC DCS Annual Report 1981
5. S. Abramsky, R. Bornat and G. F. Coulouris, Progress Report on Development of a Pascal-m System, SERC DCS Annual Report 1981
Powerful personal computers (eg ICL PERQ, Stanford SUN, etc.) have become affordable, and can be connected to form a computer network. If such networks are to become generally useful, they must offer more than just communication facilities. For example, the user sitting at the computer may wish to access shared information resources, use shared services such as printers, communicate with other users, and so on. As the tasks performed by computers, and networks of computers, become more complicated traditional styles of human/computer interaction become inadequate. New forms of information display and highly interactive control must therefore be developed to permit the most effective and natural human/computer interfaces.
This requires software which can manage resources, control access to services and handle the necessary communications both between computers in a network and between human and computer. Such software has tasks similar to, but more complicated than, the operating system software of a conventional time-shared machine: the complexity of its construction puts it at the limit of current programming technology. Novel programming methods therefore need to be developed together with a methodology for the design of internally consistent and practically effective user interfaces.
The software of a network can be viewed as a system of communicating but independent processes. This view of software simplifies the design of the operating systems of computer networks, and also those portions of the software concerned with highly interactive user interfaces. Pascal-m is a language which permits the construction of systems of communicating processes with these three properties. It is an extension of Pascal, intended to aid the design and construction of programs as collections of communicating processes. The main feature of the language is synchronised (unbuffered) typed communication over channels called mailboxes: mailboxes have identifications which may themselves be communicated in messages to alter the pattern of process interconnection. Non-determinism is provided primarily by the use of guarded commands. The current Pascal-m implementation is being used for programming user-oriented applications which have been the subject of design studies carried out by the EMMI project.
The language has been implemented on a personal computer based on an 8086 micro-processor (using a cross-compiler running on a PDP-11 UNIX). It has been used to construct several experimental systems, including a demonstration of a model user interface based on a window display which was used to test the use of colour, sound and the visual display of multiple work-contexts in human/computer interaction. Another experimental system contained a hierarchical tiling system which it is intended will eventually form the basis of a stand-alone Pascal-m development system. A message-protocol has been developed and implemented, which provides reliable communication between computers in a network and between processors within a personal computer. The demonstration systems have been developed into a complete applications environment (called QDOS), which includes a tile system similar to that of UNIX, an input/output system supporting teletype, screen editing and menu styles of interaction, and supports several activities concurrently using multiple screen windows.
The EMMI project has been concerned with the design of powerful user-oriented integrated systems, with particular reference to office systems. The collaboration of the two projects has been intended to provide, via Pascal-m, a suitable programming system, and to use it to program user-oriented applications systems, in a system demonstrating a user interface designed around a clearly defined user's model has recently been implemented.
During the next three months, up to the end of the project, we plan complete translation of the compilation system to the QDOS environment, and to demonstrate a distributed implementation of Pascal-m using the Cambridge Ring. This will complete the current project. Several projects to continue and extend are being planned.
Obvious areas of the application include office automation, educational use of microprocessors, software for multi-processor workstations. The concepts and techniques developed in the research are directly useful to industry in constructing these types of systems. Industrial concerns which have already expressed positive interest and offered financial support or equipment for the work include ICL, Texas Instruments, GEC and Hewlett Packard.
(These are internal publications available from QMC)
1. S. Abramsky and R. Bornat, Pascal-m, a Language for Distributed Systems, Report No. 245
2. S. Cook, ANY: A New Primitive Type for Pascal-m, Report No. 299.
3. S. Abramsky, A Network Implementation for Remote Communication in Pascal-m, Report No. 275.
4. S. Abramsky, A Pascal-m Filing System, Report No. 298.
5. R. Bornat, Formal Description of Pascal-m, Report No. 274.
6. S. Cook, Research into Distributed Information Systems at Queen Mary College, Report No. 296.
7. R. Bornat, The 30-year Truthfulness Problem, Report No. 304.
8. S. Abramsky, R. Bornat and G. Coulouris, Research into Distributed Software Systems and Applications at QMC, Report No. 314.
9. S. Cook and S. Abramsky, Proceedings of the 2nd International Workshop on Office Information Systems, Couvent Royal de St. Maximin, North-Holland, Amsterdam, 1982.
10. S. J. Cook, Playing Cards on the PERQ, an Algorithm for Overlapping Rectangles, Software Practice and Experience 13(11): 1043-1053 (1983).
11. S. J. Cook, Pascal-m Primer, QMC Report No. 335, June 1983.
12. S. J. Cook, The Distributed Implementation of Pascal-m, QMC Report No. 339, June 1983.
13. R. Bornat, Programming Styles in Pascal-m, QMC Lab Report.
14. K. M. Clarke, Another Pascal-m Filing System, QMC Report No. 329.
15. R. M. Newman, User Interface Design for a Cut and Paste Editor, new QMC Lab Report.
The purpose of this research is to investigate the design and application of a new computer offering very high reliability, flexibility, and potentially high speed. It can be viewed as an extension and integration of ideas found in current machines such as ICL DAP, Intel iAPX 432, and ICL PERQ. However it seeks to avoid the systematic shortcomings of such machines.
The SERC support is for one RA for 12 months and up to 9000 pounds in costs for a feasibility study. The effective starting date was March 1983. The intention is to produce detailed logic design and costings for a prototype machine.
Initial design of a planar arithmetic unit, bus structure, memory control and instruction coding have been completed. The design of a scalar arithmetic unit is now in hand. The initial design. including I/O and interrupt system, should be complete by November 1983.
Possible construction methods are being investigated as design progresses, with a view to evaluating components at board level in the final stage of the study. As the result of work carried out so far some useful economies have been made in the design. These will be reported in due course.
The PN machine has been interpreted at instruction level on the PDP-11 for some years. A simple operating system and programming language have been developed. The interpreter has been rewritten to use the Motorola MC68000 processor, for which basic support software has been written. Included in the interpreter are counters to assist in the evaluation of different logic design options.
A Ph.D student (M Burton) has undertaken redesign of the operating system to take advantage of the parallel arithmetic and logic functions and to refine the program protection mechanisms.
The intended application areas include image analysis and transformation, high integrity systems, language-oriented interpretive systems, support for database access and for program management, eg in compiling, debugging, error control. Separate funding will be sought for demonstrations in one or more of these areas.
PN System: Users Manual. available from Department of Computer Science, Queen Mary College.
Disarray is a 256 processor machine for the execution of the RasterOp graphics primitive at high speed. It is constructed out of conventional (Schottky) TTL components but has an extremely regular architecture well suited to a later implementation in VLSI.
The basic architecture of the machine is similar to the ICL DAP in that it consists of a square array of 16 × 16 single-bit processing elements (PE's) each with their own local memory. The PEs have a four-nearest-neighbour connective with additional row-wise and column-wise input buses and column-wise (open collector) output bus. The processor array operates as an SIMD machine with a 16 × 16 square word which corresponds to a similar sized square patch of pixels. Such a square word is ideal for the RasterOp function and its size allows a high computational bandwidth for this (and other) graphics algorithms.
The major differences between DisArray and the DAP type of architecture can be listed as follows:
As of August 1983 the array processor is functioning with only a few minor problems outstanding. Pixel data can be shifted at over 7 Giga Bits/sec. memory-register computations can be performed at around 500 Mbits/sec. and some test programs have been written which produce simple animated displays on the integral 512 × 512 screen.
The generation of the instruction stream for the array processor is currently being carried out by the PDP 11 host itself, which severely limits the throughput of the system. The real DisArray controller has been constructed and is in the process of being integrated into the system. The controller is a micro-programmed AMD-29116 which runs at about 7MIPs and will allow DisArray to run at its full speed. It is hoped to have the complete system running by December 1983.
Despite delays, DisArray is still a novel and significant advance in the area of high performance display systems. By integrating DisArray into a more powerful host an advanced fifth-generation single user workstation is obtained. Further, by improving its arithmetic capabilities the array would also be able to support a large amount of numerical vector/array processing for graphics, modelling, simulation etc. Coupled with the high graphics speed that DisArray gives would make the resulting machine a really exciting research vehicle. Without even going to specially designed chips it is possible for the next version of DisArray to offer about an order of magnitude speed-up over the current hardware. 4 Mbytes of memory and also over 300 MIPs of vector processing (add, subtract, logical and shift operations on 16 bit quantities) together with some content addressable memory features such as 32 simultaneous 16 bit comparisons or 512 1-bit comparisons.
