Knowledge-based adaptive self-scheduling

Yizhuo Wang; Weixing Ji; Feng Shi; Qi Zuo; Ning Deng

doi:10.1007/978-3-642-35606-3_3

Knowledge-based adaptive self-scheduling

Yizhuo Wang^*, Weixing Ji, Feng Shi, Qi Zuo, Ning Deng

^*Corresponding author for this work

School of Computer Science and Technology

Beijing Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Citations (Scopus)

Abstract

Loop scheduling scheme plays a critical role in the efficient execution of programs, especially loop dominated applications. This paper presents KASS, a knowledge-based adaptive loop scheduling scheme. KASS consists of two phases: static partitioning and dynamic scheduling. To balance the workload, the knowledge of loop features and the capabilities of processors are both taken into account using a heuristic approach in static partitioning phase. In dynamic scheduling phase, an adaptive self-scheduling algorithm is applied, in which two tuning parameters are set to control chunk sizes, aiming at load balancing and minimizing synchronization overhead. In addition, we extend KASS to apply on loop nests and adjust the chunk sizes at runtime. The experimental results show that KASS performs 4.8% to 16.9% better than the existing self- scheduling schemes, and up to 21% better than the affinity scheduling scheme.

Original language	English
Title of host publication	Network and Parallel Computing - 9th IFIP International Conference, NPC 2012, Proceedings
Pages	22-32
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-35606-3_3
Publication status	Published - 2012
Event	9th IFIP International Conference on Network and Parallel Computing, NPC 2012 - Gwangju, Korea, Republic of Duration: 6 Sept 2012 → 8 Sept 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7513 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th IFIP International Conference on Network and Parallel Computing, NPC 2012
Country/Territory	Korea, Republic of
City	Gwangju
Period	6/09/12 → 8/09/12

Keywords

Loop scheduling
Multiprocessor system
Self-scheduling

Access to Document

10.1007/978-3-642-35606-3_3

Cite this

Wang, Y., Ji, W., Shi, F., Zuo, Q., & Deng, N. (2012). Knowledge-based adaptive self-scheduling. In Network and Parallel Computing - 9th IFIP International Conference, NPC 2012, Proceedings (pp. 22-32). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7513 LNCS). https://doi.org/10.1007/978-3-642-35606-3_3

@inproceedings{70f0bf535e724a4bb752bc1098ff2004,

title = "Knowledge-based adaptive self-scheduling",

abstract = "Loop scheduling scheme plays a critical role in the efficient execution of programs, especially loop dominated applications. This paper presents KASS, a knowledge-based adaptive loop scheduling scheme. KASS consists of two phases: static partitioning and dynamic scheduling. To balance the workload, the knowledge of loop features and the capabilities of processors are both taken into account using a heuristic approach in static partitioning phase. In dynamic scheduling phase, an adaptive self-scheduling algorithm is applied, in which two tuning parameters are set to control chunk sizes, aiming at load balancing and minimizing synchronization overhead. In addition, we extend KASS to apply on loop nests and adjust the chunk sizes at runtime. The experimental results show that KASS performs 4.8% to 16.9% better than the existing self- scheduling schemes, and up to 21% better than the affinity scheduling scheme.",

keywords = "Loop scheduling, Multiprocessor system, Self-scheduling",

author = "Yizhuo Wang and Weixing Ji and Feng Shi and Qi Zuo and Ning Deng",

year = "2012",

doi = "10.1007/978-3-642-35606-3_3",

language = "English",

isbn = "9783642356056",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "22--32",

booktitle = "Network and Parallel Computing - 9th IFIP International Conference, NPC 2012, Proceedings",

note = "9th IFIP International Conference on Network and Parallel Computing, NPC 2012 ; Conference date: 06-09-2012 Through 08-09-2012",

}

Wang, Y, Ji, W, Shi, F, Zuo, Q & Deng, N 2012, Knowledge-based adaptive self-scheduling. in Network and Parallel Computing - 9th IFIP International Conference, NPC 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7513 LNCS, pp. 22-32, 9th IFIP International Conference on Network and Parallel Computing, NPC 2012, Gwangju, Korea, Republic of, 6/09/12. https://doi.org/10.1007/978-3-642-35606-3_3

Knowledge-based adaptive self-scheduling. / Wang, Yizhuo; Ji, Weixing; Shi, Feng et al.
Network and Parallel Computing - 9th IFIP International Conference, NPC 2012, Proceedings. 2012. p. 22-32 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7513 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Knowledge-based adaptive self-scheduling

AU - Wang, Yizhuo

AU - Ji, Weixing

AU - Shi, Feng

AU - Zuo, Qi

AU - Deng, Ning

PY - 2012

Y1 - 2012

N2 - Loop scheduling scheme plays a critical role in the efficient execution of programs, especially loop dominated applications. This paper presents KASS, a knowledge-based adaptive loop scheduling scheme. KASS consists of two phases: static partitioning and dynamic scheduling. To balance the workload, the knowledge of loop features and the capabilities of processors are both taken into account using a heuristic approach in static partitioning phase. In dynamic scheduling phase, an adaptive self-scheduling algorithm is applied, in which two tuning parameters are set to control chunk sizes, aiming at load balancing and minimizing synchronization overhead. In addition, we extend KASS to apply on loop nests and adjust the chunk sizes at runtime. The experimental results show that KASS performs 4.8% to 16.9% better than the existing self- scheduling schemes, and up to 21% better than the affinity scheduling scheme.

AB - Loop scheduling scheme plays a critical role in the efficient execution of programs, especially loop dominated applications. This paper presents KASS, a knowledge-based adaptive loop scheduling scheme. KASS consists of two phases: static partitioning and dynamic scheduling. To balance the workload, the knowledge of loop features and the capabilities of processors are both taken into account using a heuristic approach in static partitioning phase. In dynamic scheduling phase, an adaptive self-scheduling algorithm is applied, in which two tuning parameters are set to control chunk sizes, aiming at load balancing and minimizing synchronization overhead. In addition, we extend KASS to apply on loop nests and adjust the chunk sizes at runtime. The experimental results show that KASS performs 4.8% to 16.9% better than the existing self- scheduling schemes, and up to 21% better than the affinity scheduling scheme.

KW - Loop scheduling

KW - Multiprocessor system

KW - Self-scheduling

UR - http://www.scopus.com/inward/record.url?scp=84871593823&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-35606-3_3

DO - 10.1007/978-3-642-35606-3_3

M3 - Conference contribution

AN - SCOPUS:84871593823

SN - 9783642356056

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 22

EP - 32

BT - Network and Parallel Computing - 9th IFIP International Conference, NPC 2012, Proceedings

T2 - 9th IFIP International Conference on Network and Parallel Computing, NPC 2012

Y2 - 6 September 2012 through 8 September 2012

ER -

Knowledge-based adaptive self-scheduling

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this