nach oben

2009 | Buch

Kapitel lesen Erstes Kapitel lesen

Scheduling for Parallel Processing

verfasst von: Maciej Drozdowski

Verlag: Springer London

Buchreihe : Computer Communications and Networks

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Overview and Goals This book is dedicated to scheduling for parallel processing. Presenting a research ?eld as broad as this one poses considerable dif?culties. Scheduling for parallel computing is an interdisciplinary subject joining many ?elds of science and te- nology. Thus, to understand the scheduling problems and the methods of solving them it is necessary to know the limitations in related areas. Another dif?culty is that the subject of scheduling parallel computations is immense. Even simple search in bibliographical databases reveals thousands of publications on this topic. The - versity in understanding scheduling problems is so great that it seems impossible to juxtapose them in one scheduling taxonomy. Therefore, most of the papers on scheduling for parallel processing refer to one scheduling problem resulting from one way of perceiving the reality. Only a few publications attempt to arrange this ?eld of knowledge systematically. In this book we will follow two guidelines. One guideline is a distinction - tween scheduling models which comprise a set of scheduling problems solved by dedicated algorithms. Thus, the aim of this book is to present scheduling models for parallel processing, problems de?ned on the grounds of certain scheduling models, and algorithms solving the scheduling problems. Most of the scheduling problems are combinatorial in nature. Therefore, the second guideline is the methodology of computational complexity theory. Inthisbookwepresentfourexamplesofschedulingmodels. Wewillgodeepinto the models, problems, and algorithms so that after acquiring some understanding of them we will attempt to draw conclusions on their mutual relationships.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

In this chapter, we introduce scheduling for parallel processing as a field of knowledge. We define and distinguish abstract scheduling concepts and their real implementations. General descriptions are given here because details of many scheduling notions differ in various scheduling paradigms. Examples of scheduling problems are given to demonstrate that scheduling is essential for efficient use of parallel computers. Finally, we introduce the concept of a scheduling model which is crucial to the structure of this book.

Maciej Drozdowski

Chapter 2. Basics

Abstract

In this chapter, we present notions shared across the book. The purpose of this chapter is not only to define terms and notions, which may be known to the reader, but also to disambiguate some of them. Graph theory models are often used in scheduling. Therefore, we will introduce basic definitions of the graph theory. Most of the scheduling problems have combinatorial nature. Hence, elements of the computational complexity theory providing guidelines in analyzing combinatorial optimization problems are outlined. Then, selected methods solving hard combinatorial problems are discussed. Finally, basic metrics of parallel performance are presented.

Maciej Drozdowski

Chapter 3. Vision of Scheduling in Parallel Systems

Abstract

In this chapter, we examine vision of scheduling parallel applications which exist at various levels of computer systems. In other words this chapter is dedicated to the technical foundations of scheduling in parallel computing. We will study three elements of a parallel system: hardware, programming environment, i.e. programmer abstraction of the parallel system, and runtime environments. The purpose of this study is to find clues on scheduling problems that need to be solved, the approaches that may be viable, and limitations imposed on scheduling models. The following issues may be interesting: Is there any particular support for scheduling parallel applications? How much scheduling flexibility is left to a user of the application? Can the application be suspended, assigned to a selected processor, or migrated to a different processor? Are there any guarantees of executing parts of the application in parallel in real time? What data can be practically collected for the scheduling algorithms?

Maciej Drozdowski

Chapter 4. Classic Scheduling Theory

Abstract

In this chapter, we outline the terminology of the classic deterministic scheduling theory. Examples of algorithms for basic problems of scheduling on parallel systems will be presented. Finally, we discuss advantages and disadvantages of this scheduling model. Classic deterministic scheduling theory collected a great body of knowledge which is comprehensively presented in many books, e.g. see [11, 13, 19, 42, 57]. It is neither intended nor possible to cover all this information here. The goal of this chapter is to present basic concepts of the classic deterministic scheduling theory which are shared in the later scheduling models.

Maciej Drozdowski

Chapter 5. Parallel Tasks

Abstract

In this chapter, we study the scheduling model of parallel tasks. It is assumed that a parallel task may use more than one processor at the same time. This relaxation departs from one of the classic scheduling assumptions (Sect. 4.1). Before proceeding with the further presentation let us comment on the naming conventions. Different names have been used for the parallel tasks and their special cases. These were concurrent, multiprocessor, multiversion, malleable, moldable, rigid, and parallel tasks [29, 86, 100, 175]. One name often denotes different things. We adopt, and slightly extend, the naming convention of [100]. Reviews of parallel task scheduling can be found, e.g., in [32, 39, 81, 82, 100, 227]. Some results on the complexity of parallel task scheduling problems are collected in [42]. Proceedings of JSSPP workshop [92] are a rich source of knowledge on parallel task scheduling.

This chapter is organized as follows. In the next section, we present practical reasons for introducing parallel task model. In Sect. 5.2 we formally define variants of the model, which are studied in the following sections. In the last section, we discuss odds against, and in favor of the parallel task model.

Maciej Drozdowski

Chapter 6. Scheduling with Communication Delays

Abstract

In this chapter, we consider scheduling with communication delays. This model assumes that a parallel application is a set of sequential communicating processes (or threads) which can be represented as a directed acyclic graph (DAG). Execution of the tasks in a distributed system causes communication delays if the predecessor and the successor tasks are executed on different processors. Beyond introducing the communication delays, classic scheduling theory assumptions are generally accepted here.

The rest of this chapter is organized in the following way. In Sect. 6.1 motivation for scheduling with communication delays is given with examples of task graphs for parallel algorithms. The scheduling problem is formulated in Sect. 6.2, where variants of the communication delay models are also discussed. A shorthand notation of the scheduling problems is introduced in Sect. 6.3. In Sects. 6.4–6.7 the examined body of knowledge is partitioned according to the limited or unlimited number of processors, and allowed or disallowed task duplication. Scheduling problems are examined along the lines of computational complexity theory. The complexity results and polynomially solvable special cases are presented first. Then, heuristics are discussed. For selected special cases heuristics with performance guarantees exist. Other heuristics have no performance quality guarantees, but provide good solutions on average or solve to optimality certain special cases of the scheduling problem. In Sect. 6.8 we present selected methods of scheduling with communication delays in known interconnection networks. In the following two sections we give examples of scheduling with communication delays under different distributed system models. Thus, in Sect. 6.9 we present scheduling with communication delays in LogP model and in Sect. 6.10 hierarchical delay model. Not all branches of scheduling with communication delays are discussed here. Some approaches not covered in this chapter are mentioned in Sect. 6.11. We conclude this chapter with some general observations in Sect. 6.11.

Other surveys of scheduling with communication delays can be found, e.g., in [29, 35, 76, 110].

Maciej Drozdowski

Chapter 7. Divisible Loads

Abstract

In this chapter, we study scheduling of divisible loads (DL). This model of parallel processing assumes that the computation can be divided into parts of arbitrary sizes, and these parts can be independently processed in parallel. The two assumptions on arbitrary divisibility and independence of execution are in fact very strong. The grains of parallelism determine possible partitions of the parallel computations. Consequently, in divisible computations the grains of parallelism are negligibly small. The nature of the algorithm executed in a distributed manner determines how often the distributed threads must communicate, and hence synchronize. Here the need for communication between remote processors can be ignored. The above assumptions match easily data parallel computations which are processing great amounts of similar data units. In the following sections examples of data parallel applications conforming with divisible load model will be presented. The data are commonly called load. The area of parallel processing dedicated to the analysis of divisible applications is called divisible load theory (DLT).

In a simple form divisible applications can be performed in the following way: Initially, some amount of load resides on a processor called an originator. The originator divides the load and sends it to its neighbors for remote processing. The originator’s neighbors intercept some part of the load for local processing, and relay the rest of the load to the still inactive processors for remote execution. This load scattering procedure is continued until activating all the processors taking part in the computation. After completion of the computations, the results may be returned to the originator. The goal is to scatter the load so that communications and computations finished in the shortest time. Thus, in the DLT communication delays are explicitly taken into account. This generic organization of a distributed divisible computation will be detailed in the following sections.

DLT originated in the late 1980s with publications [2,36]. In the first paper an effective distribution of parallel computation on a network of workstations was sought for. A general mathematical programming formulation was the tool for solving the problem. It could be reduced to a linear program in a special case. In the second paper a chain of intelligent sensors was considered, and the practical question was how to distribute processing of the arriving measurements. The authors faced a dilemma: Parallel computations may be finished earlier, but distributing data costs time. How much load should be distributed, and how much processed locally? The mathematical model was reduced to a set of linear equations. This mathematical simplicity may have contributed to the initial interest in the DLT model. Later DLT developed in many new directions. At the time of writing these words, DLT comprises over 160 scientific publications and two patents [96]. Unfortunately, not all of them can be mentioned here. Surveys of divisible load theory can be found in [21, 22, 39, 94, 95].

In this chapter, we depart from the framework of the classic scheduling theory, because in majority of DLT publications only single load is considered. Consequently, beyond schedule length (C _max), the classic optimality criteria have little applicability. Moreover, the research did not follow the framework of the classic scheduling theory. Instead, DLT has been expanded and generalized in many other ways. In the following sections, we present the orthogonal directions in which the DLT developed. We start with the basic model of processing divisible load in a star network where terminology and notations are introduced. The following sections consider using DLT in diversified settings. Examples of applying DLT in practice are given in the penultimate section, when the DLT concepts and terminology are already known.

Maciej Drozdowski

Chapter 8. Back to Scheduling Models

Abstract

In the preceding chapters we presented some technical background of scheduling in parallel systems. This included both the “technology” of mathematical analysis tools and the technology of parallel processing. Four different views of scheduling for parallel processing were analyzed in the form of four different scheduling models. In this chapter, we will make some remarks on the models and algorithms for scheduling parallel computations. We will use previous chapters as the basis for our considerations. The goal of this chapter is not to criticize the results presented earlier in the book, but to draw conclusions and generalize the knowledge beyond the limits of particular scheduling models. Probably these conclusions cannot be called enlightening, but we believe that it is worthwhile to present them so that the previous discussions are put into a wider context. We also hope that these observations may be helpful in future considerations on scheduling models, problems, and algorithms.

Let us return to Fig. 1.2. It illustrates the relation between real scheduling problems, their models, theoretical scheduling problems, algorithms, and schedules. Figure 1.2 also corresponds with the process of transforming knowledge on real scheduling problem into a schedule. All the steps in the development of a schedule have their peculiarities. In the rest of this chapter we will discuss some pitfalls in the above process of developing schedules for parallel applications.

Maciej Drozdowski

Backmatter

Titel: Scheduling for Parallel Processing
verfasst von: Maciej Drozdowski
Verlag: Springer London
Electronic ISBN: 978-1-84882-310-5
Print ISBN: 978-1-84882-309-9
DOI: https://doi.org/10.1007/978-1-84882-310-5

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Chapter 2. Basics

Chapter 3. Vision of Scheduling in Parallel Systems

Chapter 4. Classic Scheduling Theory

Chapter 5. Parallel Tasks

Chapter 6. Scheduling with Communication Delays

Chapter 7. Divisible Loads

Chapter 8. Back to Scheduling Models

Backmatter

Premium Partner