Scheduling for Parallel Processing (eBook)

Maciej Drozdowski (Autor)

eBook Download: PDF

2010 | 2009
XIV, 386 Seiten
Springer London (Verlag)
978-1-84882-310-5 (ISBN)

Infos

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.

Inhalt

Preface 6
Contents 10
Introduction 15
1.1 Field of Scheduling for Parallel Processing 15
1.2 Basic Scheduling Notions 16
1.3 Why We Need Scheduling 18
1.4 Problems, Models, Algorithms, and Schedules 19
References 21
Basics 22
2.1 Selected Definitions Form Graph Theory 22
2.2 Methodology of Complexity Theory 26
2.3 Solving Hard Combinatorial Problems 32
2.4 Parallel Performance Metrics 38
References 41
Vision of Scheduling in Parallel Systems 43
3.1 Hardware 43
3.2 Programming Environments 49
3.3 Runtime Environments 54
References 63
Classic Scheduling Theory 67
4.1 Definitions 67
4.2 a/ß/y Notation and Complexity Inference 71
4.3 Scheduling Parallel Processors 73
4.4 Beyond the Classics 86
4.5 Remarks on the Classic Scheduling Theory 94
References 95
Parallel Tasks 99
5.1 Parallel Tasks in Practice 99
5.2 Assumptions and Definitions 104
5.3 Rigid Tasks 110
5.4 Moldable Tasks 129
5.5 Malleable Tasks 142
5.6 Tasks with Hypercube Shape 151
5.7 Tasks with Mesh Shape 168
5.8 Multiprocessor Tasks 192
5.9 Concluding Remarks on Parallel Task Model 208
References 209
Scheduling with Communication Delays 221
6.1 Scheduling with Communication Delays in Practice 222
6.2 Formulation of the Problem 225
6.3 Extension of a/ß/y Notation 230
6.4 Limited Processor Number and No Duplication 231
6.5 Limited Processor Number and Duplication 258
6.6 Unlimited Processor Number and No Duplication 262
6.7 Unlimited Processor Number and Duplication 277
6.8 Scheduling in Processor Networks 285
6.9 Scheduling in LogP Model 287
6.10 Scheduling with Hierarchical Communication 298
6.11 Further Reading and Conclusions 303
References 305
Divisible Loads 312
7.1 Star - Basic Formulation 313
7.2 Interconnection Topologies 318
7.3 Multi-installment Processing 326
7.4 Memory Constraints 328
7.5 Processing Cost Optimization 336
7.6 Multiple Tasks 338
7.7 Time-Varying Environment 344
7.8 Expected Search Time 347
7.9 Steady-State Divisible Load Scheduling 348
7.10 Online Scheduling 351
7.11 Toward Discrete Load Granularity 357
7.12 DLT and Performance Evaluation 360
7.13 Divisible Loads in Practice 364
7.14 Concluding Remarks on DLT 370
References 371
Back to Scheduling Models 377
8.1 On Scheduling Models 377
8.2 On Scheduling Algorithms 382
8.3 It Is a Matter of Time 385
8.4 Toward Scheduling Problem Taxonomy Anyway? 386
References 387
Summary of the Notation 388
Index 390

Produkt-Details

• Erscheint lt. Verlag: 14.3.2010
• Reihe/Serie: Computer Communications and Networks
• Reihe/Serie: Computer Communications and Networks
• Zusatzinfo: XIV, 386 p. 100 illus.
• Verlagsort: London
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Betriebssysteme / Server
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Wirtschaftsinformatik
• Schlagworte: Algorithm analysis and problem complexity • algorithms • Complexity • Complexity theory • linear optimization • Management • Notation • operating system • Parallel Computing • Parallel Processing • Performance • Processing • Resource Management • Scheduling • Scheduling Models
• ISBN-10: 1-84882-310-X / 184882310X
• ISBN-13: 978-1-84882-310-5 / 9781848823105