Static Process Allocation Using Information

about Program Behaviour

Lars Lundberg

Department of Computer Engineering, Lund University

P.O. Box 118, S-221 00 Lund, Sweden

Abstract

Efficient allocation of processes to processors is important in multiprocessors. Some systems cannot tolerate the overhead enforced by process migration; such systems have to use static allocation. In order to perform well static allocation strategies require some knowledge about the behaviour of the parallel program. If the behaviour of the parallel program does not change from one execution to another then recordings from previous executions could facilitate efficient allocation.

Here, a way of using recordings from previous executions is explored. A static allocation algorithm using such information is compared to a static algorithm lacking this information and to a dynamic algorithm. Measurements show that the allocation strategy using information about program behaviour yields a better speed-up then the algorithms lacking this information.

1 Introduction

Parallelism is one of the most promising ways to improve computer system performance, and commercial multiprocessor computers are now available [5, 2]. In order to match the parallelism in the hardware, new parallel programming languages and programming environments have emerged [9, 6]. Many of these languages use the notion of processes to express parallel execution.

Efficient allocation of processes to processors is a major issue in multiprocessor systems. Ideally one would like to find an allocation which minimizes the total execution time for the parallel program. However, this is a non-trivial problem particularly if the processes in the parallel program synchronize with each other.

Process allocation can be static, i.e. a process is executed by the same processor during the entire program, or dynamic, i.e. a process may migrate from one processor to another at run-time. Ideally, dynamic allocation provides the best throughput [13]. However,

dynamic resource allocation algorithms tend to generate excessive run-time overhead which is intolerable in many systems, especially real-time systems. For static allocation algorithms to perform well some information about the behaviour of the parallel program is needed. If the program is executed more than once, and if its behaviour does not change very much from one execution to another, then this information could be recorded during previous executions. Information about program behaviour may then be used by the allocation algorithm. Unfortunately, finding the optimal allocation is NP-hard [10]. Therefore, one has to resort to heuristic algorithms which do not guarantee the optimal result. In this paper one such algorithm is presented and its performance experimentally evaluated.

The idea of using information about program behaviour in multiprocessor scheduling has been used previously [7, 16, 17]. However, all of these studies have a very simple process model where a process is able to run to completion once it has been activated. Using such simple process models makes it possible to view a parallel program as a directed graph where each process is represented by one node, and the allocation of one node (process) to a processor does not cause any restrictions of the allocation of any other node. Here, a more general process model is considered; a process may be suspended many times before it is completed, e.g. communicating Ada tasks. In the graph model this generalization means that one process may consist of a number of nodes, and if static allocation is used then all the nodes representing a process must be allocated to the same processor. This more general process model makes the task of finding an optimal allocation harder, and it reduces the usefulness of existing graphtheoretical methods.

Section 2 defines the restrictions and aim of this study. In section 3 we discuss and exemplify how a description of parallel program behaviour can be used to predict the execution time. Three different alloca-