Jump Over Left Menu
DCS Projects: University of Manchester Institute of Science and Technology (UMIST)
D COLEMAN and J W HUGHES
DEVELOPING A PROGRAM METHODOLOGY FOR MULTIPROGRAMS
Oct 78 - Sept 80
The aim is to develop programming methods applicable to the construction of multiprograms (a program consisting of a set of time independent concurrent processes) and to discover when they should be used. The work is aimed at developing design methods in which parallelism is used to simplify the programming process This is possible as very many programs are unnecessarily complex when expressed in a strictly sequential fashion The intention is to produce efficient methods for developing correct and readable multiprograms. The group is interested in commercial applications and mapping these onto low cost microprocessor networks. They see their research as leading to the reduction of software costs, improvement of programmer performance and more cost effective use of hardware. They hope to achieve this by using a systematic design process which leads to modular programs exhibiting a structure related to the problem. These programs would be implemented in a high level language, with a high degree of compile time protection for modules and it should be possible, using a rigorous and checkable design process, to aim for some degree of proving program correctness.
The design methodology is an extension of the Michael Jackson Method which considers programs from the viewpoint of the translations they perform between input and output data. The structure of such programs should parallel the transformations applied to their data. Whereas the Michael Jackson Method uses diagrams applicable only to data expressible as regular expressions, Coleman and Hughes use translation grammars applicable to data expressible as context-free languages. This is more rigorous and more powerful than the informal Jackson Method For example, the standard stock update problem in commercial data processing has several inputs (master file, transactions etc) and several outputs (new master file, lineprinter record of transactions etc) and this is decomposed into about 12 processes forming several pipelines of cooperating sequential processes A decomposition into multiple processes becomes appropriate if the translations are inherently complex, concern complex input/output structures, or involve multiple input/output streams.
Progress to Sept 79
Programs consisting of pipelines of simple processes are characteristic of the method and reflect the use of processes to implement abstract data types and data access mechanisms. The use of processes is complementary to the use of classes (subroutines) to achieve structuring The group have already implemented a number of small programs using these methods (for example, stock control, critical path, an assembler) These programs, each consisting of about a dozen processes, are written in Concurrent Pascal and developed under the Brinch Hansen SOLO System which has been transported on to the Department's single processor Modular One computer.
This work showed the limitations of hand coding translation grammars and of using Concurrent Pascal as the implementation language. Consequently a translator writing system has been constructed as a tool for their future software development. The work also highlighted:
- the advantages of translations for identifying the processes suitable for pipelining (LL(i) grammars. L-attributed translations);
- the weakness of translation grammars in expressing semantic information;
- their limitations for describing processes with more than one input or output, or those which do not perform an L-attributed translation between streams (eg PERT, symbol table handling)
progress to Sept 80
Simultaneously with the practical work, an investigation was mounted into the problems of verifying the correctness of pipeline programs. This led to a study of program transformations, functional programming languages and their relation to attributed translation grammars. The investigators are hopeful that this approach will produce a powerful method of verifying multiprograms, but much will have to be done before this is a practical possibility. Functional languages also overcome the limitations of attributed translations described above and could therefore prove useful in the design methodology as a supplement to attributed translations for specification. They are maintaining contact with people working in this area, eg John Darlington (IC), Martin Feather (Edinburgh).
The arrival of CYBA-M at UMIST has meant that the investigators have access to a multiprocessor computer. They are currently in the initial stages of applying this methodology to design a software system for the machine. This will provide the necessary practical experience to evaluate their design methodology.
The group sees the result of their research as the development of a practical methodology for the design of multiprograms with the necessary theoretical foundations to allow constructive proofs for multiprograms. A high level language in support of the methodology is being developed based on the translator writing notation.
Work stemming from the use of attributed translations led to a design notation which maintains their advantages whilst overcoming the weaknesses found. It was realised that this design notation was consistent enough to be directly executable and could therefore be used as a language in its own right This language, DTL (Distributed Translation Language), allows the function of a program to be decomposed into a concurrent network of sequential processes. Each process is a translation from one or more input streams to one or more output streams. A network is formed by composing processes in series, in parallel or cyclically. An informal definition of the language has been produced. An initial investigation into proving the function of programs written in DTL has shown the need for a more rigorous formal definition of the language and indicated that the structure of DTL facilitates the production of correctness proofs.
The semantics of DTL are being formalised and plans are being made for the implementation of the language on both uniprocessor (LSI-11) and multiprocessor (CYBA-M and Cambridge Ring) hardware. Designs for a runtime system and a DTL compiler (possibly written in DTL) are being investigated.
DTL is currently being used for the design of a realistic applications program namely a generalised order/entry goods received system typical of that used by small engineering firms. The work started in this grant is being continued in a subsequent grant awarded to UMIST (see the following project description).
Malcolm Powell resigned his post of research assistant in October 1979 to take up a lectureship in the Department. He has continued to work part-time on the project. The post was vacant until February 1980 when Jim Spencer was appointed for the remainder of the grant. Mr Spencer had previously worked in industry and is currently applying DTL to the order system described above.
The authors have had contact with a number of groups in the field of theoretical aspects of distributed computing. The investigators have given seminars at the universities of Stirling, St Andrews, Belfast, Aarhus and Copenhagen. Visitors to the group have included researchers from the universities of East Anglia, Reading, Oxford, Kent and Belfast along with researchers from Sweden and Czechoslovakia.
Visits to the group to discuss Concurrent Pascal have been made by ASWE, British Aerospace and Salford University. Contact has been maintained with Belfast regarding Pascal Plus. Close contact is maintained with Prof Aspinall, Dr Dagless and Dr Dowsing regarding software for CYBA-M.
1. D. Coleman, J. W. Hughes, M. S. Powell, Developing a Programming Methodology for Multiprograms, Computation Departmental Report 218, March 1978.
2. J. W. Hughes, A Formalisation and Explication of the Michael Jackson Method of Program Design, Software - Practice and Experience, vol 9, pp 191-202.
3. D. Coleman, J. W. Hughes, M. Powell, A Method for the Syntax Directed Design of Multiprograms, IEEE Transactions on Software Engineering, January 1981.
4. D. Coleman, J. W. Hughes, M. Powell, ' Engineering Data Processing Programs for Multiple Microprocessors, Microprocessors and Microsystems, vol 3, no 2, March 1979, pp 83-85.
5. D. Coleman, R. M. Gallimore, J. W. Hughes and M. S. Powell, An Assessment of Concurrent Pascal, Software Practice and Experience, Vol 9, pp 827-837, 1979.
6. D. Coleman, J. W. Hughes and M. S. Powell, A Method for the Syntax Directed Design of Multiprograms, IEEE Trans on Software Engineering, Vol 7 No 2 March 1981.
7. J. W. Hughes and M. S. Powell, DTL: A Language for the Design and Implementation of Concurrent Programs as Structured Networks, Software, Practice and Experience 13(12): 1099-1112 (1983)
PROFESSOR D ASPINALL
THE USE OF MICROPROCESSORS IN INFORMATION SYSTEMS
April 82 - Sept 85
Background and Nature of Research
Many information processing tasks involve several concurrent processes. The low cost of microprocessor technology suggests that these may be active simultaneously on several processing elements or microcomputers, with a benefit in terms of cost and resilience over a time-shared mono-processor. This project has been concerned with the design and construction of a multi-microprocessor system; CYBA-M, which specifically uses low cost, commercially available microprocessors as the processing elements. In this system there are 16 processing elements which communicate through a Direct Shared Memory. This phase of the project is now complete and the CYBA-M is being used as a research vehicle in a variety of studies which are aimed at establishing the role of this type of computer system in industry and commerce.
The initial goals were the identification of firstly, the hardware and software design methodologies for this particular multi-microprocessor and secondly, the requirements of a software development environment for this type of system in general. These goals have now been achieved. The current long-term goal is to determine the architecture of the next generation of multi-processor systems using VLSI technology (Drs Edwards and Ritchings). The shorter term goals are concerned with the identification of the optimum machine architecture for a variety of application studies.
The CYBA-M hardware and software development environment (EMU) are now operational and form a completely integrated multiprocessor development environment for the research community at UMIST. Links to remote users at British Telecom are also installed. The CYBA-M system can be used to demonstrate a variety of image processing algorithms and performance models of different multi-processor interconnection structures. The capabilities of a system such as CYBA-M for the control of complex industrial machinery has also been demonstrated for the case of a commercial print cutter. The print cutter was loaned for the duration of the study from ECM Engineering Design Ltd. of Bristol.
Work in Hand
Several members of the research team are involved with measuring the performance of various models, programming languages and image processing algorithms that have been implemented on CYBA-M. In addition a study is taking place to provide a better understanding of maintenance and fault finding techniques on a multi-processor. The connection with this work and the recent developments in IKBS technology are being examined and a prototype expert system has been developed that will assist in hardware fault finding activities on CYBA-M. The parallel implementation of an applicative programming language (SASL) is complete and is being used in this study. An investigation of algorithms and architectures for dynamic pattern matching applications in image and speech processing is also taking place.
CYBA-M has also been used remotely by colleagues at Bristol University for the further investigation of design methodologies (Prof Dagless) and interconnection structures (Dr Barton) with particular reference to telecomms systems. In another study involving British Telecom (Mr Porteous), CYBA-M was used to model message passing in a small telephone exchange for performance measurements.
Several other research workers who are not part of this SERC funded team are currently using CYBA-M as a research vehicle. One group (Mrs Hughes and Dr Powell) is currently investigating the problems associated with implementing the language Pascal Plus on the machine. CYBA-M is also being used to evaluate ring message passing protocols in collaboration with the USAF. Finally, the Building Department at UMIST are using CYBA-M to model activities on a building site (Prof Pilcher).
The results and knowledge that has been obtained can be applied to the design of any multi-processor system where each processing element is devoted to a specific task. Industry has been involved with the project through discussions and direct funding. Preliminary discussions have been held with INMOS in connection with simulations of new multi-processor systems while informal meetings have taken place with UKAEA and British Aerospace with regard to using multi-processors in their respective image processing applications. Industry has been responsible for funding the collaborative studies with the USAF, BT and ECM Engineering Ltd.
The two key references to the project are Overview of Multi-Microprocessor Development Environment. (D.Aspinall and E.L.Dagless. in Microprocessors and Microsystems. Vol 3. No.7 pp 301-305 1979) and EMU: a Multiprocessor Debugging Tool (P.C. Burkimsher in Software and Microsystems, Vol 1, pp 41-47, 1982). Further information. including a complete CYBA-M documentation kit can be obtained from Prof D Aspinall.
J W HUGHES and M S POWELL
MULTIPROCESSOR SOFTWARE ENGINEERING
Oct 80 -Sept 83
The research stems from an investigation into the role of parallelism in the simplification of program designs. A language notation. DTL    has been developed for expressing a program design as a hierarchically structured concurrent network of sequential processes. Application of DTL to a major realistic problem is now the subject of a co-operative award made to the investigators in collaboration with BL systems Ltd . Programs designed using DTL are capable of direct compilation or alternatively the DTL description may be used as a guide to implementation in a conventional programming language. The work on program implementation is investigating both the direct implementation of DTL programs and their indirect implementation in more conventional concurrent languages. In support of this work compilers and virtual machines for both languages are being implemented on loosely coupled and closely coupled multiprocessors as well as a uniprocessor system. A third aspect of this work is the formalisation of the semantics of DTL to facilitate reasoning about designs and verification of implementations.
Achievements to Date
Two versions of the DTL virtual machine are now operational and allow DTL programs to be executed in the UCSD development environment. The first of these employs conventional multiprocessing techniques and executes the tree structured code produced by the DTL compiler. The second version, is essentially an expression evaluator which copes with the concurrent features of DTL by supporting pipeline. parallel composition and cyclic composition operators. Programs are represented to the system in an abstract DTL syntax which resembles CCS . This provides a very flexible implementation which can produce informative traces as an aid to reasoning about the behaviour of DTL programs. The DTL compiler has been modified to generate code in the required format.
Two Pascal based language implementations have been produced for the Cambridge Ring system. A distributed implementation of Concurrent Pascal  which allows unmodified Concurrent Pascal programs to be developed under the Solo operating system and executed with true concurrency on a variable number of processors connected to the ring. Process to processor allocation is performed using an interactive loader. Interprocess communication is achieved using the normal monitor mechanism and therefore no language extensions were required. A complementary Pascal Plus implementation for the ring  is based on an extended version of the Belfast portable Pascal Plus system  for the LSI-11. Again no language modifications were required and process to processor allocation is an interactive procedure.
Based on these experiments and the lack of a suitable development environment for Pascal Plus programs, an extended UCSD virtual machine was produced  with the intention of modifying the compiler correspondingly to allow Pascal Plus programs to be developed and executed in the UCSD environment. Similarly. in preparation for implementing Pascal Plus on CYBA-M, a UCSD virtual machine was implemented on CYBA-M and a means of controlling CYBA-M from a UCSD system running on the PDP-11/34 front end was provided. However since the last progress report, work described in the following section has indicated that a more radical redesign of the Pascal Plus virtual machine is necessary in order for it to be truly portable to distributed architectures. In particular the Belfast portable virtual machine makes a number of simplifying assumptions, which renders it insufficiently general to cope in a multiprocessor environment with, for example, heterogeneous processors, word sizes etc. Some of the work in hand described in the previous report has therefore been postponed pending major redesign of the Pascal Plus virtual machine.
An abstract specification of the DTL virtual machine has been designed . This work has been based on the practical implementations described in the previous section supported by the more formal approaches taken in . It is intended to be used as the basis of a clean architecture intensive implementation of DTL which is configurable to single or multiprocessor, closely or loosely coupled architectures. It will also form a suitable vehicle for evaluation of process to processor allocation strategies being investigated by Ioannis Samaras for his PhD thesis.
Work on architecture insensitive virtual machine design is also being pursued in the Pascal Plus context by PhD student Tony Tye. This has led to the conclusion that the Belfast portable Pascal Plus virtual machine is not sufficiently general to form the basis of a fully distributed virtual machine. As a result, the work on the UCSD extended Pascal Plus has been reorganised. An architecture insensitive UCSD Pascal Plus virtual machine is being designed and implemented in Pascal. This obviously runs extremely slowly when the Pascal is itself interpreted but provides a suitable experimental vehicle for the incorporation and evaluation of the sort of parameterisation necessary for machine insensitivity. It will be used to generate assembly coded versions when the design if finalised. At the same time the problems of compatible compiler development are being tackled in a number of stages, the first of which is nearing completion and the remainder are expected to be completed during the remainder of the grant period. The first problem is the difficulty of recompiling the compiler because of its size. The short and longer term solutions to this are respectively cross compilation and compiler segmentation. The development using cross compilation, of a compiler which will compile segmented programs is already well advanced. This will then run on the virtual machine described above and recompile itself.
It is planned that further stages providing a Pascal Plus coded operating system and compiler will occupy the remainder of the grant period and will also form a sound basis for research to be undertaken on the recently awarded contract A Cross Development Environment for Distributed Program Development .
Delivery of the UMIST provided four LSI-11/23 processors with a large disc and fast printer in support of this project was delayed until mid-June. This equipment will be complementary to CYBA-M. The combination of these two multiprocessors will provide a powerful, heterogeneous multiprocessor which will be an ideal testbed for further work on architecture insensitive virtual machines . The development of an equally flexible development environment for distributed programs will be continued under the new grant .
1. J. W. Hughes and M. S. Powell, Program Specification using DTL, Proceedings of the 1981 Aarhus Workshop on Program Specification in Springer-Verlag lecture notes on Computer Science, 134 Program Specification.
2. D. Coleman, J. W. Hughes and M. S. Powell, A Method for the Syntax Directed Design of Multiprograms, IEEE Trans on Software Engineering. March 1981.
3. J. W. Hughes and M. S. Powell, A Distributed Line Monitoring System, SERC Cooperative research proposal, April 1981.
4. J. W. Hughes and M. S. Powell. A Reduction Specification for DTL, Proceedings of the 1981 Aarhus Workshop on Program Specification in the Springer-Verlag lecture notes on Computer Science, 134 Program Specification.
5. J. W. Hughes and M. S. Powell, A Cross Development System for Distributed Computing Systems', SERC research proposal. September 1982.
6. P. Jones. Joint UCSD/Pascal Plus Virtual Machine', UMIST Computation internal report. November 1982.
7. D. W. Bustard, The Pascal Plus Pseudo Machine, Department of Computer Science. The Queens University of Belfast, version 2.
8. J. W. Hughes and M. S. Powell, A General Multiprocessor Pascal Virtual Machine, UMIST Computation Internal report
9. J. W. Hughes and M. S. Powell, A Programmers Requirements for Parallel Languages, Loughborough Closely Coupled Systems SIG, April 1982.
10. S. Karimi, Implementation of Concurrent Pascal on the Cambridge Ring, UMIST Computation Department report, May 1982.
11. F. R. A. Al-Mendhry. A Distributed Pascal Plus Implementation, UMIST Computation Department report, April 1982.
12. A. J. R. G. Milner, A Calculus of Communicating Systems, Springer-Verlag Lecture Notes on Computer Science, Vol. 92, 1980.
13. K. C. B. Tan, An Adaptable Pascal Plus Virtual Machine Architecture for Multiprocessor Environments, UMIST Computation Department M.Sc. Thesis, 1982.
14. K. Hosokawa, A Formal Semantics of a Language for the Description of Communicating Systems, UMIST Computation Department PhD Thesis, 1983.
15. J. W. Hughes and M. S. Powell. The Implementation of DTL, Software - Practice and Experience. June 1983.
16. J. W. Hughes and M. S. Powell. A Language for the Design and Implementation of Concurrent Programs as Structured Networks, Software - Practice and Experience, June 1983.