정보과학회 논문지 A : 시스템 및 이론
Current Result Document :
| 한글제목(Korean Title) |
분산 시스템에서의 유전자 스케쥴링 알고리즘 |
| 영문제목(English Title) |
Genetic Scheduling Algorithms in Distributed Computing Systems |
| 저자(Author) |
우성호
양성봉
김신덕
한탁돈
Sungho Woo
Sungbong Yang
Shindug Kim
Tackdon Han
|
| 원문수록처(Citation) |
VOL 24 NO. 12 PP. 1247 ~ 1256 (1997. 12) |
한글내용
(Korean Abstract) |
분산 시스템에서 작업들간의 우선 순위(precedence relation)를 위해 방향성 비순환 그래프(Directed Acyclic Graph)로 표현된 병렬 프로그램을 스케쥴하는 문제는 제한된 경우를 제외하고는 NP-complete 문제로 알려져 있다[1]. 따라서 실제 시스템에서의 작업 스케쥴링을 위해 다양한 모델과 가정 하에서 휴리스틱에 기반을 둔 알고리즘들이 제안되어 왔다[2,3,4,5,6,7,8]. 분산 시스템은 프로세서들과 네트워크의 성질에 따라 크게 동기종 분산 시스템(Distributed Homogeneous System)과 이기종 분산 시스템(Distributed Heterogeneous System)으로 구분 될 수 있다. 본 논문에서는 분산 시스템의 일반적인 모델을 동기종 분산 시스템과 이기종 분산 시스템에 대해 정의하고, 정의된 분산 시스템들에서 작업 스케줄링을 수행하는 유전자 스케쥴링 알고리즘(Genetic Scheduling Algorithms, GSA)을 제안한다. 동기종 분산 시스템과 이기종 분산 시스템에서의 작업 스케쥴링은 각 시스템의 상이한 성질 때문에 다른 문제로 간주되고 있다. 그러나 GSA는 유전자 알고리즘이 지닌 견고(robust)한 성질을 통해 분산 시스템의 변화에 따라 스케쥴링의 수행시에 고려해야 할 요인이 변하는 영향을 극복할 수 있다. 본 논문에서 제안된 GSA는 모의 실험을 통해서 동기종 시스템에서는 리스트 스케쥴링 알고리즘[5]과, 이기종 분산 시스템에서는 OLROG(One-Level Reach-Out Greedy) 알고리즘[7]과 성능을 비교 및 분석하였다. GSA는 다양한 환경에서 뛰어난 성능의 향상을 보여 주었다.
|
영문내용
(English Abstract) |
Scheduling a directed acyclic graph (DAG) which represents the precedence relations of the tasks of a parallel program in a distributed computing system (DCS) is known as an NP-complete problem except for some special cases[1]. Many heuristic-based methods have been proposed under various models and assumptions[2,3,4,5,6,7,8].
A DCS can be classified into two types according to the characteristics of the processors on a network: a distributed homogeneous system(DHOS) and a distributed heterogeneous system(DHES). This paper defines a general model for a DHOS and a DHES and presents genetic scheduling algorithms(GSA) to solve the task scheduling problem in the defined distributed computing systems. Task scheduling problems in DHOS and DHES are regarded as different problems due to their different factors in the scheduling. But the innate robustness of GSA can overcome the different factors. The performances of our GSA are compared with the list scheduling algorithm [3,5] in a DHOS and with the one-level reach-out greedy algorithm (OLROG) [7] in a DHES. The GSA presented in this paper have shown better performance in most cases than other scheduling methods.
|
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
