This workpackage is concerned with parallel computer systems. Its objective may be stated as development of new models for scheduling tasks in contemporary parallel computer systems and construction of scheduling algorithms best suited for the particular architectures. The models to be considered are:

• the model of a divisible job,
• the model of explicit communication delays for networks of heterogeneous processors,
• two-layered communication model for the two-tier systems,
• a model of processors available in limited intervals of time.

2. Background

Problems of allocating limited resources (processors, machines, manpower, money, memory, etc.) required to perform activities in time arise in a variety of real world applications. Managing resources of this kind is called scheduling. Deterministic models of scheduling were examined. More information on scheduling can be found e.g. in [BEPSW96, Bru98, CCLL95, C76, P95] .
Deterministic formulation of an optimisation problem imposes tight connection with discrete mathematics, and with combinatorial optimisation in particular. Computational complexity theory is a fundamental tool for the analysis of combinatorial optimisation problems. The complexity analysis determines the computational complexity class of the considered problem. Then, it gives directions for dealing with problems computationally easy and computationally hard. A comprehensive treatment of computational complexity can be found e.g. in [GJ79].
In the earlier works a unified model for deterministic scheduling of tasks in computer and manufacturing systems has been elaborated (cf. [BEPSW96, Bru98, CCLL95, C76, P95]). However, it appeared that not in all cases the above unified approach may be used successfully. This is especially true if one considers parallel computer systems, as for example massively parallel processing systems, two layered parallel systems (two-tier systems) or networks of workstations.

In this project deterministic scheduling problems were considered with a focus on parallel computer systems. Four scheduling models were proposed and studied:

• divisible job model,
• the model of explicit communication delays
• two-layered communication model,
• processors available in limited intervals of time.

Computational complexity of the problems arising in the above models has been studied. Algorithms have been proposed and their performance has been evaluated. New communication algorithms for scattering in meshes have been proposed and evaluated. A series of practical experiments confirmed viability of the divisible job model and the applied methodology.

4. Achievements

This project is a continuation of a long-term research activities of the team involved, in the area of deterministic task scheduling. Four new scheduling models for parallel computer systems have been proposed and analysed. These were: divisible job model, the model of explicit communication delays, two-layered communication model, and the model of processors available in limited intervals of time. The results obtained in the four fields will be described in the following.

In this study a divisible task model has been considered. The divisible task is a model of a computation which can be continuously divided into parts of arbitrary size. These parts can be processed in parallel and independently of each other, on different computers. Examples of divisible tasks include processing big measurement data files, processing big databases, some problems related to linear algebra and simulation. The divisible task model takes into account the underlying communication hardware and software. The goal is to find the distribution of the load such that total communication and computation times are minimal.
In the earlier periods of the CRIT-2 project, linear dependence of the communication time on the volume of transferred data was assumed. Yet, another important element of communication time is start-up time, necessary to set up a network connection or to prepare the message. In the preceding periods the impact of the communication start-up time on the divisible computations has been studied (cf. publication [4]) for various architectures (chains, loops, trees and hypercube). The problem turned out to be computationally hard in general (NP-hard). It was also observed that all processors take part in computation only if the volume of work is sufficiently large and the network is sufficiently fast.
Divisible task model was also used to analyse the distribution of the load on a square 2D-torus and 3D-torus of processors [9,10]. Data scattering algorithms based on circuit-switching and wormhole routing were proposed. The communication and computation processes were modelled by use of linear equations. The linear equation model was solved numerically [9] and analytically [10]. The results from the model were also used in the performance analysis of the 2D- and 3D- meshes of processors.
The divisible task model has been extensively tested in two Transputer parallel processing systems. One of them, Meganode system with 64 Transputers, has been donated to the Institute of Computing Science, Poznań University of Technology by the Laboratoire de Modélisation et de Calcul-IMAG in Grenoble, France. (This is a nice example of the cooperation within CRIT project). The idea of a divisible task and the results of the practical computational experiments are presented in publication [8]. The objective of the experiment was a comparison of the real and the theoretically predicted execution time for a distributed application. The experiments were conducted on various numbers of processors and for changing volume of work. The difference between the model and the measured execution time was below 10%, and 1.5%, depending on the setting. Hence, the experiments confirmed applicability of the model in real-life situations.
Next, the more challenging task was posed to implement and verify the divisible job model on the networks of workstations - the parallel environments available for the masses. Though, the success could not be complete here due to the inherent complexity and unpredictability of general-purpose computer systems, the results obtained confirm vaibility and correctness of the model. The results for the networks of workstations are summarised in paper [17]. The experiments are described in more detail in section 6.3. The results of the investigation in this field were presented at the meetings listed in section 6.2, positions: 6, 7, 10, 12, 14, 15, 18.

Explicit communication delays model

Uniform processors (i.e. having different speeds) are more and more important to consider because of the huge amount of computations done on networks of workstations. Another model of processing considered in [6] assumes set T of tasks which is partially ordered by a precedence relation, to be processed on a set of parallel uniform processors. It was also assumed that each task must be processed without preemption on one processor. The problem of scheduling precedence task graphs which have the structure of complete in-trees, where all the tasks have unit execution time (UET) has been studied in [6]. Moreover, communication delays have been taken into account if the results of some task are used by another task processed on a different processor. The main result of this paper is the analysis of the problem of scheduling complete UET in-trees on two uniform processors with any integer speed ratio in the presence of unit communication delays (UCT). A linear time algorithm has been proposed and its optimality has been proved in [6]. The results of the investigation in this field were presented at the meetings listed in section 6.2, position 19.

Two-layered communication model

A different set of scheduling rules is needed in two-layered parallel computer architectures (also called two-tier systems). The lower layer processing element (PE) is formed by small number of processors (e.g. two, four) sharing memory. Therefore, the communication delay between processors is small in the PE. Interrupting, suspending, and migration of task execution can be implemented with negligible overhead. The upper layer involves communication and distribution of the tasks between the processing elements. The communication delay in the upper layer is much bigger and must be taken into account when distributing work. Since the communication delay in the two layers is qualitatively different, also task behaviour is different. Hence, different scheduling policies must be used for different layers. A system with a central distributor of the work has been proposed [5,11] for the upper layer. This is common a situation in the contemporary computer systems that a queue of work is managed centrally. It has been shown that most of deterministic scheduling problems in this case are computationally hard even for two PEs, independently of the number of buffers for holding work incoming to PEs, and independently of pre-allocating (or not) the tasks to the processors. On the other hand, when processing times and communication times of all tasks are identical, which is the case of homogeneous computer systems processing grains of divisible tasks, then the optimal schedule has a known pattern structure and can be constructed in low order polynomial time. Furthermore, the worst case behaviour of greedy heuristics has been analysed. It was shown that in the case of dedicated processors any greedy heuristic builds schedules at most twice as long as the optimal schedule. In the case of not-dedicated processors any heuristic builds schedules at most three times as long as the optimal schedule. For the lower tier consisting of two processors low-order polynomial time scheduling algorithms have been proposed in [12]. In particular, the problem of scheduling preemptable multiprocessor tasks with precedence constraints and schedule length criterion, and the problem of scheduling multiprocessor tasks with ready times and due-dates for maximum lateness optimality criterion were solved. This problem becomes even more involved when tasks have internal structure: sequential startup and completion. This problem has been analysed in [13]. Its computational hardness has been demonstrated, exact and approximation scheduling algorithms have been proposed. The investigation in this field was presented at the meetings listed in section 6.2, positions: 1, 2, 4, 13.

In computer systems urgent real time tasks are usually pre-scheduled on processors and executed in fixed time periods. Thus, free time windows are created for lower priority tasks.
It is well known that in the majority of cases the problem of preemptive task scheduling on m parallel identical processors with the objective of minimising the makespan can be solved in polynomial time. For example, for tree-like like precedence constraints the algorithm of Muntz and Coffman can be applied. In paper [15], this problem is generalised to cover the case of parallel processors available in certain time intervals only. It was shown that this problem is NP-hard in the strong sense in case of trees and identical processors. If tasks form chains and are processed by identical processors with a staircase pattern of availability, the problem can be solved in low-order polynomial time for schedule length (C_max) criterion. A linear programming approach is proposed for the maximum lateness (L_max) criterion. Network flow and linear programming approaches were applied for independent tasks scheduled on, respectively, uniform and unrelated processors with arbitrary patterns of availability for both C_max and L_max criteria. In work [3] the same problem was investigated in the case of parallel (or multiprocessor) tasks which require several processors in parallel. Scheduling algorithms based on linear programming model were proposed.
The idea of scheduling on machines available in restricted intervals of time was further extended to other environments in works [7, 14, 18, 19], and summarised in [2]. The case of single-processor and dedicated two-processor flow-shop, open-shop and general shop production systems have been analysed. The behaviour of the tasks in the presence of the holes may be different here. Hence, two more classes of tasks have been distinguished beyond preemptable and nonpreemptable tasks [2]: resumable tasks which can be resumed on the same processor after non-availability period without additional costs, and semiresumable tasks which can be resumed at some cost on the same processor after non-availability period. It has been shown that the scheduling in these systems is computationally hard. Among the other, an approximation algorithm for the problem with one non-availability period on the first machine of the two-machine flow-shop has been proposed. However, when the non-availability appears on the second machine, then the problem is not approximatble (unless P=NP). The investigation in this field was presented at the meetings listed in section 6.2, positions: 3, 5, 8, 9, 11, 17, 20.

A visible sign of an international cooperation conducted within CRIT-2 Project was an editorial work on a special issue of Parallel Computing (deliverable [1]) carried on by J.Błażewicz (Technical University of Poznań), E.Bampis (Université d'Evry, France), and K.Ecker (Technische Universität Clausthal-Zellerfeld, Germany). This issue was devoted to problems of task scheduling in parallel and distributed systems. Several leading scientists from Europe contributed to the volume making it a current state of the art review of modern strategies used in the above field. Among the contributions the first three papers consider scheduling tasks subject to explicit communication delays. The fourth paper deals with multiprocessor tasks where communication delays are taken into account implicitly, and the last two papers are based on models that take the processor interconnection topology into account.

Our investigation conducted in the field of deterministic scheduling in parallel computer systems has been summarised in work [16]. In this chapter we discuss the parallel processing context of scheduling in computer systems. Only deterministic models of scheduling were examined. Basic classical scheduling approaches were recalled and then a special attention was be paid to three new models of scheduling in parallel systems: scheduling multiprocessor tasks, scheduling with communication delays and scheduling divisible tasks.

An evident indication of CRIT-2 project achievement was preparation of the "Handbook on Parallel and Distributed Processing" [1]. This book is the third of a running series of volumes dedicated to information systems theory and application. The first two volumes were "Handbook on Architectures of Information Systems", and "Handbook on Electronic Commerce". The objective of the series is to provide a reference source for problem solvers in business, industry, government, and professional researchers and graduate students. The present volume is a joint venture of an international board of editors, gathering prominent authors of academia and practice, who are well known specialists in the area of parallel and distributed processing. The intention of the Handbook is to provide practitioners, scientists and graduate students with a good overview of basic methods and paradigms, as well as important issues and trends across the broad spectrum of the above area. In particular, the book covers fundamental topics such as efficient parallel algorithms, languages for parallel processing, parallel operating systems, architecture of parallel and distributed systems, management of resources in parallel systems, tools for parallel computing, parallel database systems and multimedia object servers, and networking aspects of distributed computing. Three chapters are dedicated to applications: parallel and distributed scientific computing, high-performance computing in molecular sciences, and multimedia applications for parallel and distributed systems.

5. Concluding remarks and future plans

The support granted by the EU helped us to carry on the research through the time of financial deficiency. Four interesting scientific problems have been in-depth studied. 19 publications were prepared, including a book and a special volume of the well-known international journal, and a Ph.D. thesis. Two M.Sc. theses has been completed. A number of presentations at the seminars and conferences have been given. New scientific contacts have been established. Thus, we believe that this project can be considered a success.

We believe that the scientific results have practical merit. Therefore, dissemination of the results to the practice may be profitable. Design and implementation of an Internet-accessible program for computer system performance prediction can be a further step toward the dissemination of the results obtained. Still, the area we researched has unexploited potential both scientifically and practically.

6.List of Project’s:

1. E.Bamips, J.Błażewicz, K.Ecker, Task Scheduling for Parallel and Distributed Systems, special issue of Parallel Computing 25 (1), 1999.
2. J.Błażewicz, K. Ecker, B. Plateau, D. Trystram, Handbook on Parallel and Distributed Processing, Springer, Heidelberg - Berlin, 2000

1. J.Błażewicz, K. Ecker, B. Plateau, D. Trystram, Handbook on Parallel and Distributed Processing, Springer, Heidelberg - Berlin, 2000, 263-341.
2. P.Formanowicz, Scheduling tasks in systems with limited availability (in Polish), Ph.D. thesis, Institute of Computing Science, Poznań University of Technology, 2000.

3. L.Bianco, J.Błażewicz, P.Dell'Olmo, M.Drozdowski, Preemptive multiprocessor task scheduling with release times and time windows, Annals of Operations Research 70, 1997, 43-55.
4. J.Błażewicz, M.Drozdowski, Distributed processing of divisible jobs with communication startup costs, Discrete Applied Mathematics 76 (1), 1997, 21-41.
5. J.Błażewicz, M.Drozdowski, Scheduling tasks in master-slave parallel processing systems, Proc. of IFAC/IFIP Conference on Management and Control of Production and Logistics, Aug 31- Sept. 3, 1997, Campinas Brazil, 297-302.
6. J.Błażewicz, F.Guinand, B.Penz, D.Trystram, Scheduling complete tree on two uniform processors with arbitrary speed ratios and communication delays, Institute of Computing Science, Poznań University of Technology, Technical Report RA-015/98, 1998.
7. J.Błażewicz, M.Drozdowski, P.Formanowicz, W.Kubiak, Szeregowanie zadań w systemach z ograniczoną dostępnością, Zeszyty naukowe Politechniki Śląskiej, Seria: Automatyka, z.123, Nr kol. 1389, 1998, 55-63.
8. J.Błażewicz, M.Drozdowski, M.Markiewicz, Divisible task scheduling - concept and verification, Parallel Computing 25 (1), 1999, 87-98
9. J.Błażewicz, M.Drozdowski, F.Guinand, D.Trystram, Scheduling a divisible task in a 2-dimensional toroidal mesh, Discrete Applied Mathematics 94 (1-3), 1999, 35-50.
10. M.Drozdowski, W.Głazek, Scheduling divisible jobs in a three-dimensional mesh of processors, Parallel Computing 25(4), 1999, 405-416.
11. J.Błażewicz, M.Drozdowski, P.Dell'Olmo, Scheduling of client-server applications, International Transactions in Operational Research 6(4), 1999, 345-363.
12. J.Błażewicz, P.Dell'Olmo, M.Drozdowski, Scheduling preemptable multiprocessor tasks on two parallel processors, Proceedings of the 2^nd International Conference Parallel Computing Systems 99, Ensenada, Mexico, 1999, 165-170.
13. M.Drozdowski, W.Kubiak, Scheduling parallel tasks with sequential heads and tails, Annals of Operations Research 90, 1999, 221-246.
14. M.L.Espinouse, P.Formanowicz, B.Penz, Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability, Computers and Industrial Engineering 37, 1999, 497-500.
15. J.Błażewicz, M.Drozdowski, P.Formanowicz, W.Kubiak, G.Schmidt, Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing 26, 2000, 1195-1211.
16. J.Błażewicz, M.Drozdowski, K.Ecker, Management of Resources in Parallel Systems, in: J.Błażewicz, K. Ecker, B. Plateau, D. Trystram, Handbook on Parallel and Distributed Processing, Springer, Heidelberg - Berlin, 2000, 263-341.
17. M.Drozdowski, P.Wolniewicz, Experiments with Scheduling Divisible Tasks in Clusters of Workstations, in: A.Bode, T.Ludwig, W.Karl, R.Wsmüler (eds.): EURO-Par 2000, LNCS 1900, Springer-Verlag, 2000, 311-319
18. J.Błażewicz, P.Formanowicz, W.Kubiak, M.Przysucha, G.Schmidt, Parallel branch and bound algorithms for the two-machine flow shop problem with limited machine availability, Bulletin of the Polish Academy of Sciences - Technical Sciences, 48, 2000, 105-115.
19. J.Błażewicz, P.Formanowicz, M.Kasprzak, Scheduling resumable jobs in two-machine flow shop system with limited machine availability - a constraint programming approach, Proceedings of the 2nd Workshop on Constraint Programming for Decision and Control, J. Figwer (ed.), June 27th 2000, Gliwice, Poland, 17-20.

Practical experiments confirming viability of the divisible task model have been performed in dedicated Transputer systems, and networks of workstations. The purpose of the experiments was to compare the real and the theoretically predicted execution time of a distributed application.
The first group of experiments was performed on two different dedicated transputer systems with various numbers of processors and for changing volume of work. The difference between the model and the measured execution time was in the range of 10%, and 1.5%, depending on the setting. Thus, the empirical verification successfully confirmed the model. The results of the tests are reported in publication [8].
The practical experiments of the second series were performed on various clusters of workstations. The platforms included Sun workstations, IBM-SP2, clusters of PCs with PVM, MPI, Java with Windows or Linux operating systems. In this case verifying correctness of the model was more challenging because the clusters could not be completely isolated from the external interference, and the computer systems are more complex than the dedicated Transputer networks. The results obtained confirm correctness of divisible job model. In many cases difference between the model and the reality was approximately 10% and less. Yet, the success could not be complete here due to the inherent complexity and unpredictability of general-purpose computer systems and the necessary simplifications in the model. The results of the experiments are summarised in paper [17].

See the list of scientific contacts and collaborators is given in the point "List of participants and national/international collaboration ..."

Ph.D.
P.Formanowicz, thesis: Scheduling tasks in systems with limited availability (in Polish), Ph.D. thesis, Institute of Computing Science, Poznań University of Technology, 2000.

M.Sc.
A.Piotrowski, thesis: Divisible job model in distributed computer systems (in Polish), Institute of Computing Science, Poznań University of Technology, 1999.
M.Kemp, thesis: Processing divisible loads in the Internet (in Polish), Institute of Computing Science, Poznań University of Technology, 1999.

Professional degrees:
Professor positions of J.Nawrocki, and M.Drozdowski

Title: Multimedia integrated system for training in process and production design and planning for SME

Coordinator: Prof. Zenobia Weiss

Status: rejected

Partners:

• Poznań University of Technology, Institute of Computing Science
• Poznań University of Technology, Institute of Mechanical Technology
• Poznań Supercomputing and Networking Centre
• Poznań University of Technology, Institute of Electronics and Telecommunication
• University of Koszyce (dept. in Pesov), Department of Production Technology Slovakia
• Ośrodek Badawcz-Rozwojowy Obrabiarek i Urządzeń Specjalnych, Poznań, Poland
• P.A. Transtech, Presov, Slovakia
• Infonova EDV, Informationstechnologie und Systementwicklung Gesellschaft mbH, Graz
• Aachener Demonstrationslabor für inegrierte Produktionstechnik GmbH, Aachen, Germany

International collaboration:

The following researchers contributed to the publication of deliverable [2]:

The Meganode Transputer parallel processing systems with 64 Transputers, donated to the Institute of Computing Science, Poznań University of Technology by the Laboratoire de Modélisation et de Calcul-IMAG in Grenoble, France currently is also used to teach parallel processing of computer science students. We see it as a good sign of the transfer of knowledge and ideas from the research to the experience of the future practitioners.

Get a file with this presentation (zip, approx. 4MB).