Statistical measures for quantifying task and machine heterogeneities

被引：13

作者：

Al-Qawasmeh, Abdulla M. ^{[1
]}

Maciejewski, Anthony A. ^{[1
]}

Wang, Haonan ^{[3
]}

Smith, Jay ^{[1
,4
]}

Siegel, Howard Jay ^{[1
,2
]}

Potter, Jerry ^{[1
]}

机构：

[1] Colorado State Univ, Dept Elect & Comp Engn, Ft Collins, CO 80523 USA

[2] Colorado State Univ, Dept Comp Sci, Ft Collins, CO 80523 USA

[3] Colorado State Univ, Dept Stat, Ft Collins, CO 80523 USA

[4] DigitalGlobe Inc, Longmont, CO USA

来源：

JOURNAL OF SUPERCOMPUTING | 2011年 / 57卷 / 01期

基金：

美国国家科学基金会;

关键词：

Distributed systems; Heterogeneity; Heterogeneous systems; Mapping heuristics; Task allocation; Regression trees; RESOURCE-ALLOCATION HEURISTICS; DISTRIBUTED COMPUTING SYSTEMS; INDEPENDENT TASKS; STATIC HEURISTICS; PROCESSORS; ROBUSTNESS;

D O I：

10.1007/s11227-011-0572-x

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study heterogeneous computing (HC) systems that consist of a set of different machines that have varying capabilities. These machines are used to execute a set of heterogeneous tasks that vary in their computational complexity. Finding the optimal mapping of tasks to machines in an HC system has been shown to be, in general, an NP-complete problem. Therefore, heuristics have been used to find near-optimal mappings. The performance of allocation heuristics can be affected significantly by factors such as task and machine heterogeneities. In this paper, we identify different statistical measures used to quantify the heterogeneity of HC systems, and show the correlation between the performance of the heuristics and these measures through simple mapping examples and synthetic data analysis. In addition, we illustrate how regression trees can be used to predict the most appropriate heuristic for an HC system based on its heterogeneity.

引用

页码：34 / 50

页数：17

共 39 条

[1] Characterizing resource allocation heuristics for heterogeneous computing systems [J].

Ali, S ;

Braun, TD ;

Siegel, HJ ;

Maciejewski, AA ;

Beck, N ;

Bölöni, L ;

Maheswaran, M ;

Reuther, AI ;

Robertson, JP ;

Theys, MD ;

Yao, B .

ADVANCES IN COMPUTERS, VOL 63: PARALLEL, DISTRIBUTED, AND PERVASIVE COMPUTING, 2005, 63 :91-128

[2]

ALI S, 2000, Journal of Applied Science and Engineering, V3, P195

[3] Static heuristics for robust resource allocation of continuously executing applications [J].

Ali, Shoukat ;

Kim, Jong-Kook ;

Siegel, Howard Jay ;

Maciejewski, Anthony A. .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2008, 68 (08) :1070-1080

[4]

ALQAWASMEH AM, 2010, 19 HET COMP WORKSH H

[5]

[Anonymous], 2006, Probability and random processes for electrical and computer engineers, DOI DOI 10.1017/CBO9780511813610

[6]

[Anonymous], 1976, Computer and job-shop scheduling theory

[7]

[Anonymous], 1984, OLSHEN STONE CLASSIF, DOI 10.2307/2530946

[8] The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions [J].

Armstrong, R ;

Hensgen, D ;

Kidd, T .

SEVENTH HETEROGENEOUS COMPUTING WORKSHOP (HCW '98), 1998, :79-87

[9]

BANICESCU I, 2001, 10 HET COMP WORKSH H

[10]

BARADA H, 2001, 10 HET COMP WORKSH H

← 1 2 3 4 →