PhD applications

This page describes the type of research work for which the Real-Time Systems group academic staff would be interested in supervising PhD students. Please consult our News and jobs page for details of funded PhD studentship opportunities currently available.

Research opportunities

For full details of the Department's PhD programme can be found on the Graduate Study web page. The following members of the Real-Time Systems Group supervise PhD students.

1 Neil Audsley
2 Iain Bate
3 Alan Burns
4 Rob Davis
5 Leandro Soares Indrusiak
6 Andy Wellings

1  Neil Audsley

My research involves the design, implementation and analysis of resource restricted embedded real-time systems.

Programming Embedded Systems

The integration of hardware programming languages (eg. VHDL) and software programming languages (e.g., Ada, Java), particularly from a real-time perspective. Integration is considered at the semantic and implementation levels, including issues regarding run-time systems and virtual machines. Current research is looking at the implementation of Real-Time Java on hardware platforms (not CPUs).

Direct Compilation of Software Languages to FPGAs

One approach to embedded systems is to implement in hardware, rather than software running on a CPU. If the system functionality is expressed using a software language, this raises the issue of how to compile (or synthesise) hardware from that software language. For example, current research is examining the compilation of Ada to reconfigurable hardware (i.e., FPGAs), and appropriate optimisations that can be made.

Kernels for Embedded Systems

Embedded systems are low resource, requiring extremely small footprint kernels. Current research is focusing on the specialisation of kernels for particular applications ensuring that only the functionality that is required is actually part of the kernel. Other research is looking at implementing parts of the kernel in hardware, to enable the CPU (often low-powered) to concentrate upon the application.

Timing Analysis and Scheduling Algorithms

Traditional timing analysis for real-time systems has assumed that functionality is performed upon the CPU. When hardware is used to implement part of the application, then the usual models do not apply. Current research is looking at timing analysis for systems where part of the application is software and part hardware.

Advanced Embedded Systems

Future embedded systems will be demanding to design and implement. For example, dynamic embedded systems which reconfigure during operation; portable embedded systems, particularly using Java technologies; advanced hardware platforms, e.g., Network-on-Chip (NoC) technologies. All these embedded systems pose new challenges in each of the research areas given above, e.g., timing analysis for complex NoC systems (with multiple processors and interconnection network all on a single chip).

2  Iain Bate

My main research interests include scheduling and timing analysis, real-time systems engineering, and the real-time aspects of dealing with emergent behaviour. The work features strong influences from real application issues especially in relation to critical systems.

Real-Time Systems Engineering

Systems engineering is a complex activity often involving multiple objectives, multiple properties and multiple paradigms. This results in difficult design trade-offs that need to be made across a number of design choices and assessment criteria. Previous work has established a trade-off analysis approach that has been applied to control scheduling problems [8], task allocation [2], the logical design of systems [7] and introducing flexibility into systems [6]. A key component is the use of Search-Based Software Engineering to help solve the problems. Future research could look deeper into the issues of scenario-based assessment, model-based development approaches and their incorporation of timing, co-design (especially hardware software co-design, control scheduling issues and low power computing), hierarchical optimisation approaches or the application of parallel computing to solve the problems.

Scheduling and Timing Analysis

My PhD looked at how to adapt the popular scheduling scheme fixed priority scheduling for industrial applications [3] and later work looked at how to perform Worst-Case Execution Time (WCET) for software [9]. The scheduling work concentrated on how to tailor the timing analysis for specific computational models (e.g., non-preemptive systems), performing timing analysis for systems with offsets and performing the timing analysis of distributed systems. There is still scope for considerable work to be performed in these areas, especially with respect to enhancing the flexibility of approaches.

Processor Design

Significant work has been performed on the difficulty in using current microprocessors in real-time and critical systems [5]. The key issues that have been established as WCET analysis (see above), showing the source code intent of the software has been carried out and identifying/avoiding systematic design errors in the processor. These issues are underpinned by the need to have a suitable processor model and being able to validate it. Further research could be performed on what makes a suitable processor, how to tailor and use the processor to make it more suitable, and how to establish and validate a processor model.

Energy/Power-Aware Computing

There has been significant work on scheduling approaches for system where time is the dominant non-functional property. In recent years, researchers have expanded the problem to consider energy and power. However, there are three key weaknesses in this work. Firstly, many of the approaches have considerable overheads and yet the processing requirements of these have not been accounted for. Secondly, the work has not allowed for other peripheral devices such as disk drives and graphics controllers. Finally the issue of power/energy management needs to be addressed across the whole system. A particular interest would be research that addresses some of these issues.

Real-Time Aspects of Emergent Behaviour

Any failed or troubled project incurs significant cost. It has been recognised that a chief reason for the problems with projects is that of emergent behaviour. Emergent behaviour is behaviour that is difficult to predict which emerges when component(s) are integrated. In recent years emergent behaviour has gained more attention from researchers, however there is a great deal of work still to be done. In particular most of this has been for general purpose computer-based systems, not embedded real-time systems. There are a number of tactics for managing emergent behaviour for embedded real-time systems including addressing the issues through appropriate models [4] or parameterising components [1]. I would be interested in taking on students to progress this work.

3  Alan Burns

My main field of research is the design, implementation, modelling and analysis of real-time systems. I am most interested in scheduling analysis and the assessment of languages, particularly Ada and Real-Time Java, and reflective programming languages.

My current research revolves around scheduling analysis for safety-critical systems such as those found in aircraft and cars, and mission-critical systems such as multi-media systems. All these systems have the need to deliver the appropriate quality of service (known as QoS) in an environment where resources are in some sense limited. The main resources of interest are processors and communication networks and busses. Work is currently been carried out on single processors, multiprocessors, distributed systems and new silicon architectures such as SoC (Systems on Chips).

A major focus of the scheduling work (of which over 10 people have obtained PhDs in the past) is to undertake multi-level budget control over all resources of importance in a system. The allocation of resources, even in a static system, is a NP-hard problem; and hence sub-optimal but effective schemes are needed. In more open and dynamic systems this problem is even more challenging. The allocation of power in battery driven systems is also an active research area in mobile systems.

To undertake research in this area requires a good mathematical background and an appreciation of concurrency. I am happy to supervise research students on any issue related to this area.

My main area of research is the schedulability analysis of real-time systems, including multiprocessor, single processor, network communication, and distributed systems. Over the past 12 years, I have been involved in a number of start-up companies, transferring real-time systems research into commercial products that are of value to industry. Building on this experience, a key motivator for my research is to progress the state-of-the-art forward in terms of the techniques available for analysing and developing commercial real-time systems. Much of my research is therefore aimed at providing solutions with a clear practical benefit. My current research is focussed on schedulability analysis for multiprocessor real-time systems [11], where I am particularly interested in scheduling techniques that combined high performance with low overheads [12], [13].

To undertake research into the analysis of real-time systems requires a good mathematical background. I am happy to supervise students on any area related to the scheduling of real-time systems and multiprocessor scheduling.

Potential PhD students should contact Rob via email to discuss possible PhD studies prior to completion of University application forms.

PhD Topics

• Real-time scheduling
  • multiprocessor / multicore
  • single processor
  • hierarchical
  • communications [10]

My research interests cover a large part of the embedded systems design flow from specification to implementation, addressing specific aspects of the hardware platform, the application software and the interface between both. I follow a model-driven approach, using simulation and/or formal methods to validate a model, and transformation rules (such as model synthesis or code generation) to bring it step-wise closer to its final implementation. This approach aims to support software developers to properly express concurrency at the application level, and to investigate techniques that can more efficiently explore all the parallelism that will be made available by future multiprocessor hardware platforms.
Specific research topics include:

Application modelling and mapping onto multiprocessor platforms

Multiprocessor platforms can explore concurrency at the application level and increase performance by parallelising the execution. However, the application-level concurrency must be as explicit as possible, because one can't write purely sequential code and expect compilers to do the magic. My aim here is to investigate better languages and language combinations that could provide suitable constructs to better enable the specification of concurrent behaviour for a specific application domain (embedded systems must explore as much as possible the specificities of the domain they are embedded in, so that they can be more efficient regarding cost, performance and energy).

Possible PhD topics:
For detailed information, check my open proposals webpage.

• application modelling using actors and UML
• dynamic mapping application models onto platforms

Multiprocessor platforms for embedded systems

Chips with multiple processing cores are already a reality in embedded systems, but there are many open issues on how to maximize system performance through parallelism while complying with constraints on power consumption and heat dissipation. In order to find the best trade-off for each embedded application, developers must be able to validate the software functionality and performance over different alternatives of the hardware platform, and due to short time-to-market this is expected to be done even before the actual hardware is available.

Possible PhD topics:
For detailed information, check my open proposals webpage.

• modelling and evaluation of time-predictable on-chip interconnect structures
• estimation of power consumption in multiprocessor platforms

6  Andy Wellings

My main field of research is the design, implementation and analysis of real-time systems. I am most interested in design methods for hard real-time systems; operating kernels for safety-critical and real-time systems; generic architectures; and assessment of languages, particularly Ada95 and Real-Time Java, object-oriented programming languages and reflective programming languages.

My current research revolves around architecture-neutral real-time systems. These are real-time systems whose target architectures are unknown at the design time. Architecture-neutral real-time systems are typically intended for embedded systems or hand-held devices; however, they are also applicable to Internet applications. The target architecture is unknown because: (1) They have to be executable on the widest range of architectures possible in order to increase their portability; (2) Their lifetime is expected to be greater than ten years and, therefore, they have to be immune to technology obsolescence; (3) Their site of execution may vary.

Architecture-neutral real-time systems are at odds with traditional real-time systems because traditional systems typically need: (1) known (or bounded) processing resource demand - by definition the resources needed by an architecture-neutral system will depend on the power of the site hosting its execution; (2) efficient and predictable execution - most architecture-neutral systems are interpreted where efficiency is often a secondary concern; techniques such as Just-In-Time compilation lead to better average-case executions but have less predictability and poorer worst-case behaviour; (3) static allocation - predictability in a real-time multiprocessor or distributed environment is often achieved by sacrificing flexibility; e.g., statically allocating threads to processors in order to avoid scheduling anomalies (such as Graham's and Dhall's anomaly); by definition static allocation is not possible in an architecture-neutral system.

Current software technologies that can be used as a basis for architecture-neutral computing include: Microsoft's .Net framework, Sun's Java, Bell Labs' Inferno, and OSF's ANDF. Of these, only Java (with the Real-Time Specification) addresses real-time behaviour. I am happy to supervise research students on any issue related to this area.

References

[1]	I. Bate. Dealing with emergent properties in embedded systems. In 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. IEEE Computer Society, 2005.
[2]	I. Bate and N. Audsley. Flexible design of complex high-integrity systems using trade offs. In 8th IEEE International Symposium on High Assurance Systems Engineering, pages 22-31, 2004.
[3]	I. Bate and A. Burns. An integrated approach to scheduling in safety-critical embedded control systems. Real-Time Systems Journal, 25(1):5-37, 2003.
[4]	I. Bate, A. Cervin, and P. Nightingale. Establishing timing requirements and control attributes for control loops in real-time systems. In 15th Euromicro Conference on Real-Time Systems, pages 121-128. IEEE Computer Society, 2003.
[5]	I. Bate, P. Conmy, T. Kelly, and J. McDermid. Use of modern processors in safety-critical applications. The Computer Journal, 44(6):531-543, 2001.
[6]	I. Bate and P. Emberson. Design for flexible and scalable avionics systems. In IEEE Aerospace Conference. IEEE Computer Society, 2005.
[7]	I. Bate and T. Kelly. Architectural considerations in the certification of modular systems. Reliability Engineering and System Safety, 81:303-324, 2003.
[8]	I. Bate, J. McDermid, and P. Nightingale. Establishing timing requirements for control loops in real-time systems. Microprocessors and Microsystems, 27(4):159-169, 2003.
[9]	I. Bate and R. Reutemann. Worst-case execution time analysis for dynamic branch predictors. In 16th Euromicro Conference on Real-Time Systems, pages 215-222. IEEE Computer Society, 2004.
[10]	R.I. Davis, A. Burns, R.J. Bril, and J.J. Lukkien. Controller Area Network (CAN) Schedulability Analysis: Refuted, Revisited and Revised. Real-Time Systems, 35(3):239-272 April 2007.
[11]	R.I. Davis and A. Burns. A Survey of Hard Real-Time Scheduling for Multiprocessor Systems. In ACM Computing Surveys to appear.
[12]	R.I. Davis and A. Burns. University of York, Department of Computer Science Technical Report, YCS-2010-452, April 2010.
[13]	R.I. Davis and A. Burns. Priority Assignment for Global Fixed Priority Pre-emptive Scheduling in Multiprocessor Real-Time Systems. In proceedings 30th IEEE Real-Time Systems Symposium (RTSS'09), pages 398-409, December 1-4th, 2009.

Legal note

The use of registered names, trademarks etc. in this document does not imply, even in the absence of a specific statement, that such names are exempt from relevant laws and regulations and therefore free for general use. Although care has been taken in preparing the information supplied in this document, the University of York and the Department of Computer Science do not and cannot guarantee the accuracy of it. The University and the Department cannot be held responsible for any errors or omissions and accepts no liability whatsoever for any loss or damage howsoever arising.