ALLOCATING AND SCHEDULING HARD REAL-TIME
TASKS ON A PARALLEL PROCESSING PLATFORM

A. Burns
M. Nicholson
K. Tindell
N. Zhang

Department of Computer Science,
University of York, UK
email: [email protected]

ABSTRACT

This paper addresses the issues of scheduling and allocation/configuration of a point-topoint parallel system, for safety-critical hard real-time systems. Three specific topics are considered: an analysable computational model that has sufficient expressive power whilst retaining flexibility for allocation; a scheduling approach that allows the worst case response times for each system's transactions to be calculated; and an allocation algorithm, based on the use of simulated annealing, that allow system level configuration to be undertaken. The DIA (Data Interaction Architecture) is used as an example parallel processing platform. A sizable case study is analysed to show the applicability of the techniques proposed.

1. INTRODUCTION

Point-to-point architectures have a number of advantages over other forms of distribution: there is no physically shared communication media to schedule and they re-scale (off-line) with the minimum of disturbance. In this paper we consider the problems involved in running hard real-time safety-critical applications on point-to-point networks.

An example of a point-to-point network is the DIA (Data Interaction Architecture)22. This model has been designed specifically to support real-time applications. In DIA, nodes are linked via dual port memories; the network is not fully connected and hence message routing needs to be considered. Each node consists of a processor and a KEC (Kernel Executive Chip); the role of the KEC is to manage the scheduling of work on the processor. This work is composed of processes that have assigned priorities. Dispatching is cooperative: a process will continue executing until it either blocks or executes a "voluntary suspend". When such a suspend is executed the KEC will undertake a process switch if there is a runnable process of greater or equal priority. Interrupts are handled by the KEC ? the node processor is not interrupted.

The dual port memories that link adjacent nodes implement (with the help of the two nodes) Simpson's Algorithms21. These protocols allow read and write operations to occur concurrently without interference or blocking. In essence, the protocols ensure that a read operation can immediately receive the most recent fully written data item. The use of these algorithms (which do not need a common time frame) decouples the temporal behaviour of each node from its neighbours, removing the need for synchronisation algorithms.

In this paper we address the issues of scheduling and allocation/configuration in a point-to-point distributed system. The DIA architecture is used as an exemplar; the analysis presented is however applicable to other point-to-point systems. We are concerned with the production of systems that will guarantee end-to-end timing deadlines. To achieve this we restrict our considerations to systems that do not perform process migration. Allocation is thus a pre-run-time activity. We do however consider the use of techniques, such as replication, to give fault tolerance.

The paper is structured as follows. In the next section a general computational model is presented. Section 3 then covers the schedulability analysis. Allocation is addressed in section 4. A case study is described in section 5, and our conclusions are outlined in section 6.