Hierarchical Scheduling in Parallel and Cluster Systems

Pirmais vāks
Springer Science & Business Media, 2003. gada 30. jūn. - 251 lappuses
Multiple processor systems are an important class of parallel systems. Over the years, several architectures have been proposed to build such systems to satisfy the requirements of high performance computing. These architectures span a wide variety of system types. At the low end of the spectrum, we can build a small, shared-memory parallel system with tens of processors. These systems typically use a bus to interconnect the processors and memory. Such systems, for example, are becoming commonplace in high-performance graph ics workstations. These systems are called uniform memory access (UMA) multiprocessors because they provide uniform access of memory to all pro cessors. These systems provide a single address space, which is preferred by programmers. This architecture, however, cannot be extended even to medium systems with hundreds of processors due to bus bandwidth limitations. To scale systems to medium range i. e. , to hundreds of processors, non-bus interconnection networks have been proposed. These systems, for example, use a multistage dynamic interconnection network. Such systems also provide global, shared memory like the UMA systems. However, they introduce local and remote memories, which lead to non-uniform memory access (NUMA) architecture. Distributed-memory architecture is used for systems with thousands of pro cessors. These systems differ from the shared-memory architectures in that there is no globally accessible shared memory. Instead, they use message pass ing to facilitate communication among the processors. As a result, they do not provide single address space.

No grāmatas satura

Lietotāju komentāri - Rakstīt atsauksmi

Ierastajās vietās neesam atraduši nevienu atsauksmi.

Saturs

INTRODUCTION
12 Parallel Architectures
121 SIMD Systems
122 MIMD Systems
15 Overview of the Monograph
1
PARALLEL AND CLUSTER SYSTEMS
3
22 Parallel Architectures
5
222 NUMA Systems
6
532 Results and Discussion
121
5321 Principal Comparison
122
5322 Impact of Variance in Task Service Time
123
5323 Impact of Variance in Task Distribution
124
5324 Effect of Window Size
125
5325 Sensitivity to Other Parameters
127
54 Conclusions
128
PERFORMANCE WITH SYNCHRONIZATION WORKLOADS
131

224 Distributed Shared Memory
8
23 Example Parallel Systems
9
232 Stanford DASH System
11
24 Interconnection Networks
14
241 Dynamic Interconnection Networks
16
242 Static Interconnection Networks
19
25 Interprocess Communication
26
252 MPI
30
253 TreadMarks
33
26 Cluster Systems
35
261 Beowulf
36
27 Summary
38
PARALLEL JOB SCHEDULING
39
32 Parallel Program Structures
41
322 DivideandConquer Programs
42
323 Matrix Factorization Programs
43
33 Task Queue Organizations
45
3311 Improving Centralized Organization
47
3312 Improving Distributed Organization
49
34 Scheduling Policies
53
3412 Dynamic Policies
54
342 An Example SpaceSharing Policy
55
3421 Adaptive SpaceSharing Policy
56
3422 A Modification
57
3424 Performance Comparison
58
3425 Performance Comparison
59
3426 Handling Heterogeneity
65
343 TimeSharing Policies
68
344 Hybrid Policies
70
35 Example Policies
71
352 ASCI BluePacific
72
353 Portable Batch System
73
36 Summary
74
HIERARCHICAL TASK QUEUE ORGANIZATION
75
HIERARCHICAL TASK QUEUE ORGANIZATION
77
42 Hierarchical Organization2
79
43 Workload and System Models
83
442 Utilization Analysis
87
4421 Centralized Organization
88
4423 Hierarchical Organization
89
4432 Distributed Organization
90
45 Performance Comparison
91
451 Impact of Access Contention
92
452 Effect of Number of Tasks
94
453 Sensitivity to Service Time Variance
97
454 Impact of System Size
99
455 Influence of Branching and Transfer Factors
101
46 Performance of Dynamic Task Removal Policies
104
47 Summary
107
PERFORMANCE OF SCHEDULING POLICIES
111
52 Performance of Job Scheduling Policies
112
522 Results
113
5222 Sensitivity to Task Service Time Variance
114
5223 Sensitivity to Variance in Task Distribution
115
53 Performance of Task Scheduling Policies
116
62 Related Work
132
63 System and Workload Models
135
64 Spinning and Blocking Policies
137
642 Blocking Policies
138
651 Workload Model
139
6521 Principal Comparison
140
6522 Sensitivity to Service Time Variance
143
6523 Impact of Granularity
144
6524 Impact of Queue Access Time
145
66 Barrier Synchronization Workload Results
146
662 Simulation Results
147
6622 Sensitivity to Service Time Variance
150
6624 Impact of Queue Access Time
151
67 Cache Effects
152
68 Summary
153
HIERARCHICAL SCHEDULING POLICIES
155
SCHEDULING IN SHAREDMEMORY MULTIPROCESSORS
157
72 SpaceSharing and TimeSharing Policies2
158
722 Modified RRJob
160
74 Performance Evaluation
164
7421 Effect of Scheduling Overhead
168
7422 Impact of Variance in Service Demand
171
7423 Effect of Task Granularity
173
7424 Effect of the ERF Factor
174
7425 Effect of Quantum Size
176
75 Performance with Lock Accessing Workload
177
752 Results
178
76 Conclusions
180
SCHEDULING IN DISTRIBUTEDMEMORY MULTICOMPUTERS
183
82 Hierarchical Scheduling Policy2
185
83 Scheduling Policies for Performance Comparison
190
84 Workload Model
191
85 Performance Comparison
193
852 Performance with NonUniform Workload
194
8521 Performance with 5050 distribution
195
8522 Sensitivity to variance in job service demand
196
8523 Performance under 5025 distribution
198
8524 Performance under 5075 distribution
199
853 Discussion
200
86 Conclusions
201
SCHEDULING IN CLUSTER SYSTEMS
203
92 Hierarchical Scheduling Policy
205
921 Job Placement Policy
206
922 Dynamic Load Balancing Algorithm
208
93 SpaceSharing and TimeSharing Policies
210
931 SpaceSharing Policy
211
941 Workload Model
214
943 NonUniform Workload Results
217
95 Summary
219
EPILOG
221
CONCLUSIONS
223
102 Concluding Remarks
226
References
229
Index
239
Autortiesības

Citi izdevumi - Skatīt visu

Bieži izmantoti vārdi un frāzes

Bibliogrāfiskā informācija