Task Scheduling for Parallel Systems
Oliver Sinnen
- 出版商: Wiley
- 出版日期: 2007-05-04
- 定價: $2,998
- 售價: 8.5 折 $2,548
- 語言: 英文
- 頁數: 296
- 裝訂: Hardcover
- ISBN: 0471735760
- ISBN-13: 9780471735762
-
相關分類:
Operating-system
立即出貨 (庫存 < 3)
買這商品的人也買了...
-
$1,400Configuring SAP R/3 FI/CO -
建構嵌入式 Linux 系統$780$616 -
專案管理策略精論：專案管理的策略規劃與實施 (Project Management: Strategic Design and Implementation, 4/e)$780$702 -
GNU Make 專案開發工具 (Managing Projects with GNU Make, 3/e)$620$490 -
深入淺出 Java 程式設計, 2/e (Head First Java, 2/e)$880$581 -
Java 認證 SCJP 5.0 猛虎出閘$650$514 -
PMP Exam Prep: Rita's Course in a Book for Passing the PMP Exam, 5/e$3,026$2,875 -
SQL 語法範例辭典$550$468 -
CSS、HTML、XHTML 精緻範例辭典$450$383 -
Linux 驅動程式, 3/e (Linux Device Drivers, 3/e)$980$774 -
Head First 深入淺出 HTML、CSS 與 XHTML (Head First HTML with CSS & XHTML)$800$680 -
碼上就會：Rails敏捷開發網站 (Agile Web Development with Rails, 2/e)$600$474 -
深入淺出物件導向分析與設計 (Head First Object-Oriented Analysis and Design)$880$695 -
ActionScript 3.0 精緻範例辭典$550$468 -
C++ Primer, 4/e (中文版)$990$891 -
JavaScript 大全 (JavaScript: The Definitive Guide, 5/e)$1,200$948 -
現代嵌入式系統開發專案實務－菜鳥成長日誌與專案經理的私房菜$600$480 -
深入淺出 PMP (Head First PMP)$880$695 -
SQL Server 2005 Transact-SQL 達人養成手冊$520$442 -
深入淺出 C# (Head First C#)$980$774 -
網頁設計 愛上 jQuery$550$435 -
Oracle 資料庫管理與維護$620$527 -
大話設計模式$620$527 -
全球最強 VMware vSphere 4 企業環境建構$860$774 -
Google Android SDK 開發範例大全$750$638
商品描述
Description
A new model for task scheduling that dramatically improves the efficiency of parallel systemsTask scheduling for parallel systems can become a quagmire of heuristics, models, and methods that have been developed over the past decades. The author of this innovative text cuts through the confusion and complexity by presenting a consistent and comprehensive theoretical framework along with realistic parallel system models. These new models, based on an investigation of the concepts and principles underlying task scheduling, take into account heterogeneity, contention for communication resources, and the involvement of the processor in communications.
For readers who may be new to task scheduling, the first chapters are essential. They serve as an excellent introduction to programming parallel systems, and they place task scheduling within the context of the program parallelization process. The author then reviews the basics of graph theory, discussing the major graph models used to represent parallel programs. Next, the author introduces his task scheduling framework. He carefully explains the theoretical background of this framework and provides several examples to enable readers to fully understand how it greatly simplifies and, at the same time, enhances the ability to schedule.
The second half of the text examines both basic and advanced scheduling techniques, offering readers a thorough understanding of the principles underlying scheduling algorithms. The final two chapters address communication contention in scheduling and processor involvement in communications.
Each chapter features exercises that help readers put their new skills into practice. An extensive bibliography leads to additional information for further research. Finally, the use of figures and examples helps readers better visualize and understand complex concepts and processes.
Researchers and students in distributed and parallel computer systems will find that this text dramatically improves their ability to schedule tasks accurately and efficiently.
Table of Contents
Preface.Acknowledgments.
1. Introduction.
1.1 Overview.
1.2 Organization.
2. Parallel Systems and Programming.
2.1 Parallel Architectures.
2.1.1 Flynn’s Taxonomy.
2.1.2 Memory Architectures.
2.1.3 Programming Paradigms and Models.
2.2 Communication Networks.
2.2.1 Static Networks.
2.2.2 Dynamic Networks.
2.3 Parallelization.
2.4 Subtask Decomposition.
2.4.1 Concurrency and Granularity.
2.4.2 Decomposition Techniques.
2.4.3 Computation Type and Program Formulation.
2.4.4 Parallelization Techniques.
2.4.5 Target Parallel System.
2.5 Dependence Analysis.
2.5.1 Data Dependence.
2.5.2 Data Dependence in Loops.
2.5.3 Control Dependence.
2.6 Concluding Remarks.
2.7 Exercises.
3. Graph Representations.
3.1 Basic Graph Concepts.
3.1.1 Computer Representation of Graphs.
3.1.2 Elementary Graph Algorithms.
3.2 Graph as a Program Model.
3.2.1 Computation and Communication Costs.
3.2.2 Comparison Criteria.
3.3 Dependence Graph (DG).
3.3.1 Iteration Dependence Graph.
3.3.2 Summary.
3.4 Flow Graph (FG).
3.4.1 Data-Driven Execution Model.
3.4.2 Summary.
3.5 Task Graph (DAG).
3.5.1 Graph Transformations and Conversions.
3.5.2 Motivations and Limitations.
3.5.3 Summary.
3.6 Concluding Remarks.
3.7 Exercises.
4. Task Scheduling.
4.1 Fundamentals.
4.2 With Communication Costs.
4.2.1 Schedule Example.
4.2.2 Scheduling Complexity.
4.3 Without Communication Costs.
4.3.1 Schedule Example.
4.3.2 Scheduling Complexity.
4.4 Task Graph Properties.
4.4.1 Critical Path.
4.4.2 Node Levels.
4.4.3 Granularity.
4.5 Concluding Remarks.
4.6 Exercises.
5. Fundamental Heuristics.
5.1 List Scheduling.
5.1.1 Start Time Minimization.
5.1.2 With Dynamic Priorities.
5.1.3 Node Priorities.
5.2 Scheduling with Given Processor Allocation.
5.2.1 Phase Two.
5.3 Clustering.
5.3.1 Clustering Algorithms.
5.3.2 Linear Clustering.
5.3.3 Single Edge Clustering.
5.3.4 List Scheduling as Clustering.
5.3.5 Other Algorithms.
5.4 From Clustering to Scheduling.
5.4.1 Assigning Clusters to Processors.
5.4.2 Scheduling on Processors.
5.5 Concluding Remarks.
5.6 Exercises.
6. Advanced Task Scheduling.
6.1 Insertion Technique.
6.1.1 List Scheduling with Node Insertion.
6.2 Node Duplication.
6.2.1 Node Duplication Heuristics.
6.3 Heterogeneous Processors.
6.3.1 Scheduling.
6.4 Complexity Results.
6.4.1 α|β|γ Classification.
6.4.2 Without Communication Costs.
6.4.3 With Communication Costs.
6.4.4 With Node Duplication.
6.4.5 Heterogeneous Processors.
6.5 Genetic Algorithms.
6.5.1 Basics.
6.5.2 Chromosomes.
6.5.3 Reproduction.
6.5.4 Selection, Complexity, and Flexibility.
6.6 Concluding Remarks.
6.7 Exercises.
7. Communication Contention in Scheduling.
7.1 Contention Awareness.
7.1.1 End-Point Contention.
7.1.2 Network Contention.
7.1.3 Integrating End-Point and Network Contention.
7.2 Network Model.
7.2.1 Topology Graph.
7.2.2 Routing.
7.2.3 Scheduling Network Model.
7.3 Edge Scheduling.
7.3.1 Scheduling Edge on Route.
7.3.2 The Edge Scheduling.
7.4 Contention Aware Scheduling.
7.4.1 Basics.
7.4.2 NP-Completeness.
7.5 Heuristics.
7.5.1 List Scheduling.
7.5.2 Priority Schemes—Task Graph Properties.
7.5.3 Clustering.
7.5.4 Experimental Results.
7.6 Concluding Remarks.
7.7 Exercises.
8. Processor Involvement in Communication.
8.1 Processor Involvement—Types and Characteristics.
8.1.1 Involvement Types.
8.1.2 Involvement Characteristics.
8.1.3 Relation to LogP and Its Variants.
8.2 Involvement Scheduling.
8.2.1 Scheduling Edges on the Processors.
8.2.2 Node and Edge Scheduling.
8.2.3 Task Graph.
8.2.4 NP-Completeness.
8.3 Algorithmic Approaches.
8.3.1 Direct Scheduling.
8.3.2 Scheduling with Given Processor Allocation.
8.4 Heuristics.
8.4.1 List Scheduling.
8.4.2 Two-Phase Heuristics.
8.4.3 Experimental Results.
8.5 Concluding Remarks.
8.6 Exercises.
Bibliography.
Author Index.
Subject Index.
商品描述(中文翻譯)
這本創新的書籍提出了一種新的任務排程模型，大大提高了並行系統的效率。
對於並行系統的任務排程來說，過去幾十年來已經發展出了許多啟發式、模型和方法，使得這個領域變得非常複雜。本書的作者通過提出一個一致且全面的理論框架以及現實的並行系統模型，消除了混亂和複雜性。這些新模型基於對任務排程背後的概念和原則的研究，考慮到異質性、通信資源的競爭以及處理器在通信中的參與。
對於對任務排程可能還不熟悉的讀者來說，前幾章是必不可少的。它們作為並行系統編程的優秀入門，並將任務排程置於程序並行化過程的背景下。作者隨後回顧了圖論的基礎，討論了用於表示並行程序的主要圖模型。接下來，作者介紹了他的任務排程框架。他仔細解釋了這個框架的理論背景，並提供了幾個例子，使讀者完全理解它如何大大簡化和增強排程能力。
本書的後半部分介紹了基本和高級排程技術，為讀者提供了對排程算法背後原則的全面理解。最後兩章討論了排程中的通信競爭和處理器在通信中的參與。
每一章都包含練習題，幫助讀者將新的技能付諸實踐。廣泛的參考文獻提供了進一步研究的資訊。此外，圖片和例子的使用有助於讀者更好地視覺化和理解複雜的概念和過程。
分佈式和並行計算系統的研究人員和學生將發現，這本書大大提高了他們準確且高效地排程任務的能力。
目錄:
前言
致謝
1. 簡介
1.1 概述
1.2 組織
2. 並行系統和編程
2.1 並行架構
2.1.1 弗林分類
2.1.2 記憶體架構
2.1.3 編程範式和模型
2.2 通信網絡
2.2.1 靜態網絡
