MSc by Research in Computer Science

Back to MSc by Research in Computer Science Home Page

Programming Languages and Compilers Strand

Aims

The taught part of this strand provides an overview of current technologies in the design of translators in the widest sense, as transducers from specifications to behaviour. We cover both traditional compilation of computer languages to machine code for conventional processors and approaches to the direct synthesis of digital hardware. At the end of this course the student will have a basic familiarity with the use of generally available industrial toolkits such as the Synopsis silicon compiler and research tools developed within this group and elsewhere. In addition we shall provide an insight into the algorithms and formalisms used internally by these tools which will form a platform for independent research in the project phase.

The course comprises a directed reading schedule and structured assignments which students must present during weekly tutorials with their supervisors. The provisional syllabus lists the material with which the student must have become familiar by the end of the course: in general some students may have covered some parts of the material at undergraduate level particularly that involving classical compiler technology. There is considerable scope to tune the schedule to suit the experience of students.

Sessions of Provisional syllabus

1. The theory and design of programming languages.
   • Historical overview of the development of programming languages. Impact of formalisms on the syntax and semantics of programming languages. Development of control and data abstractions. Static and dynamic aspects of programming languages. Future architectural constraints on programming language expressiveness.
2. Machine translation and compiler technology.
   • Parsing of general context free grammars. Constraints on linear time parsers: follow determinism. Construction of reduced derivation trees. Parser generators: a survey. Attribute grammars and the interdependence of language syntax and semantics. Tree walk based output routines.
3. Optimising code generation.
   • The shape of typical Von Neumann processors. Control and data flow analysis. Alias analysis. Register allocation. Classical optimisations. Bit-serial specific optimisations. The impact of unconstrained pointer access on optimisation.
4. The impact of compiler technology on computer architecture.
   • The CISC and RISC debate. RISC as the limiting case of a pipelined approach to processor implementation. VLIW and scheduling. Architectural support for compile time speculation. Register structures for high performance code scheduling. The effects of classical optimisations on superscalar architectural design.
5. VLSI implementation and approaches to hardware synthesis
   • An overview of gate level CMOS design. A simple synthesis model for combinational logic. Register and memory elements. Power distribution and clocking. The use of fine-grain programmable logic devices. Trends in chip density. Specifying and simulating large systems. Silicon compilation. The semantics of hardware.
     

Provisional Coursework

In addition to the weekly reading and worksheet assignments which will form the basis of the tutorial sessions, there will be two substantial pieces of assessed coursework as follows:

• The implementation of a source-to-source translator using the tools developed within the languages and architectures research group.
• The specification and simulation of a substantial digital system such as a complete processor using VHDL synthesis tools.

Supervisors

Adrian Johnstone and Elizabeth Scott

Main References

1. David Lilja and Peter Bird (Eds), The interaction of compilation technology and computer architecture, Kluwer Academic Publishers
2. Kenneth Slonneger and Barry L. Kurtz, Formal syntax and semantics of programming languages, Addison Wesley
3. Michael Smith, Application-Specific Integrated Circuits, Addison Wesley

Further references

1. Klaas Sikkel, Parsing schemata, Springer
2. S Sippu and E Soisalon-Sioninen, Parsing theory, Vols I and II, Springer-Verlag
3. Robert Morgan, Building an optimising compiler, Digital Press
4. Mads Tofte, Compiler Generators, what they can do, what they might do and what they will probably never do, Springer Verlag
5. Sadiq M Sait and Habib Youssef, VLSI physical design automation, IEEE Press