Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Processor scheduling and allocation for 3D torus multicomputer systems
Autore:
Choo, H; Yoo, SM; Youn, HY;
Indirizzi:
Sung Kyun Kwan Univ, Dept Elect & Comp Engn, Suwon, South Korea Sung Kyun Kwan Univ Suwon South Korea t & Comp Engn, Suwon, South Korea Columbus State Univ, Dept Comp Sci, Columbus, GA 31907 USA Columbus State Univ Columbus GA USA 31907 omp Sci, Columbus, GA 31907 USA Informat & Commun Univ, Sch Engn, Taejon, South Korea Informat & Commun Univ Taejon South Korea Sch Engn, Taejon, South Korea
Titolo Testata:
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
fascicolo: 5, volume: 11, anno: 2000,
pagine: 475 - 484
SICI:
1045-9219(200005)11:5<475:PSAAF3>2.0.ZU;2-Y
Fonte:
ISI
Lingua:
ENG
Keywords:
best-fit and first-fit approach; multicomputer; processor scheduling and allocation; 3D torus;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
16
Recensione:
Indirizzi per estratti:
Indirizzo: Choo, H Sung Kyun Kwan Univ, Dept Elect & Comp Engn, Suwon, South Korea Sung Kyun Kwan Univ Suwon South Korea Engn, Suwon, South Korea
Citazione:
H. Choo et al., "Processor scheduling and allocation for 3D torus multicomputer systems", IEEE PARALL, 11(5), 2000, pp. 475-484

Abstract

Multicomputer systems achieve high performance by utilizing a number of computing nodes. Recently, by achieving significant reductions in communication delay, the three-dimensional (3D) torus has emerged as a new candidate interconnection topology for message-passing multicomputer systems. In this paper, we propose an efficient processor allocation scheme-scan search scheme-for the 3D torus based on a first-fit approach. The scan search scheme minimizes the average allocation time for an incoming task by effectively manipulating the 3D information on a torus as 2D information using a data structure called the CST (Coverage Status Table). Comprehensive computer simulation reveals that the allocation time of the scan search scheme is always smaller than that of the earlier scheme based on a best-fit approach. The difference gets larger as the input load increases, and it is as much a factor of 3 for high load. To investigate the performance of the proposed scheme in different scheduling environments, we also consider a non-FCFS scheduling policy along with the typical FCFS policy. The allocation time complexity of the scan search scheme is O((LWH2)-H-2). This is significantly smaller than that of the existing scheme which is O((LWH4)-W-4-H-4). Here, L, W, and H represent the length, width, and height of 3D torus, respectively.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 24/10/20 alle ore 14:17:46