Contents of Report
[Data of Report]
Report Number:
TR0813
Date of Registration:
1992.11
English Title:
Isoefficiency Analysis of Hierarchical On-Demand Load Distribution
Japanese Title:
***
English Author:
K.Kimura,Nobuyuki Ichiyoshi
Japanese:
木村 宏一,市吉 伸行
Name of Organization to which author belongs:
ICOT,COT
PDF:
tr0813.pdf
[Contents]
Abstract
.... 2
Keywords
.... 2
Notations and Conventions
.... 3
1
Introduction
.... 4
2
Single-Level and Multi-Level Load Balancing Schemes
.... 5
2.1
Assumptions for problems
.... 5
2.2
On-demand distribution(single-level load balancing scheme)
.... 6
2.3
Tuning the granularity
.... 6
2.4
Bottleneck in speedup
.... 6
2.5
Multi-level load balancing scheme
.... 7
3
Model of On-Demand Load Distribution
.... 7
3.1
Expression for parallel execution time
.... 7
3.2
Probabilistic assumptions
.... 9
3.3
Performance measures and other technical notions
.... 12
4
Deterministic Case
.... 13
5
Exponential Case
.... 14
5.1
Lower estimate of the efficiency
.... 15
5.2
Upper estimate of the efficiency
.... 18
6
General Case
.... 21
6.1
Additional assumption for the general case
.... 21
6.2
Lower estimate of the efficiency
.... 22
7
Inheritance of the Moderate Diversity
.... 29
7.1
Assumption on the distribution of the number of subtasks
.... 29
7.2
Moderate diversity of the task size
.... 30
7.3
Moderate diversity of the parallel execution time
.... 31
8
Multi-Level Dynamic Load Balancing Scheme
.... 39
8.1
Definitions of the Model
.... 39
8.2
Isoefficiency Analysis
.... 41
8.3
Asymptotic analysis of the processor configuration
.... 44
9
Conclusions
.... 45
Acknowledgments
.... 46
Appendix : NBU Model
.... 46
References
.... 48
目次をクリックすると、PDFファイルが表示されます。
ICOT研究論文（TR）一覧に戻る / Back to the list of ICOT Technical Reports