Korea Digital Contents Society

Journal Archive

Journal of Digital Contents Society - Vol. 22 , No. 1

[ Article ]
Journal of Digital Contents Society - Vol. 22, No. 1, pp.183-190
Abbreviation: J. DCS
ISSN: 1598-2009 (Print) 2287-738X (Online)
Print publication date 31 Jan 2021
Received 25 Nov 2020 Revised 22 Jan 2021 Accepted 22 Jan 2021
DOI: https://doi.org/10.9728/dcs.2021.22.1.183

배치 작업의 자원 가용성 최대화를 위한 스케줄링 기법
윤준원1 ; 송의성2, *
1한국과학기술정보연구원 슈퍼컴퓨팅본부 선임연구원
2부산교육대학교 컴퓨터교육과 교수

Scheduling Methods for Maximizing Resource Availability of Batch Jobs
Jun-Weon Yoon1 ; Ui-Sung Song2, *
1Senior Researcher, Department of Supercomputing Center, KISTI, Daejeon 34141, Korea
2Professor, Department of Computer Education, Busan National University of Education, Busan 47503, Korea
Correspondence to : *Ui-Sung Song Tel: +82-51-500-7326 E-mail: ussong@bnue.ac.kr


Copyright ⓒ 2021 The Digital Contents Society
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-CommercialLicense(http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Funding Information ▼

초록

수많은 계산 노드로 구성된 클러스터 환경에서 배치 작업 스케줄러는 계산 자원의 상태를 인지하여 순서에 맞게 효율적으로 작업을 할당하는 역할을 수행한다. 클러스터 내의 계산 자원에 작업을 할당하는 방법은 제출된 시간의 순서를 따르는 것이 공평한 방법이다. 그러나 한정된 가용 자원을 효율적으로 사용하기 위해서는 작업의 규모와 수행 시간을 고려한 스케줄링 알고리즘이 필요하며 다양한 연구들이 진행되어 왔다.

본 연구는 클러스터 환경에서 배치 작업 스케줄러의 수행 환경을 분석하고 작업 회수시간(Turn-around Time) 최소화하기 위해 고려할 요인들을 검토하였다. 나아가 자원의 가용성을 높이기 위한 스케줄링 알고리즘 기법을 연구하고 각 기법에 대한 시뮬레이션을 수행을 통해 성능을 평가했다. 이로써 클러스터의 유휴 계산자원의 활용성을 높임으로써 사용자는 작업 수행에 필요한 자원을 빠르게 확보할 수 있다. 향후 실제 클러스터 환경에 접목함으로써 자원의 활용률과 최적화에 기여할 수 있다.

Abstract

In a cluster environment composed of numerous computational nodes, the batch job scheduler recognizes the resource status and efficiently allocates the job in order. It is fair to follow the order of submission times to allocate jobs to compute resources in the cluster. However, in order to efficiently use limited available resources, a scheduling algorithm that considers the size and execution time of the job is required, and various studies have been conducted.

This study analyzes the execution method of the batch job scheduler in a cluster environment and looks at the factors to consider in order to minimize the job turn-around time. Furthermore, it studies scheduling algorithm techniques to increase resource availability and evaluates the performance through simulations for each method. As a result, the utilization of idle computational resources of the cluster is increased, so that users can quickly obtain resources required for job execution. In the future, it can contribute to resource utilization and optimization by applying it to an actual cluster environment.


Keywords: Cluster computing, Batch Job, Scheduling, Algorithm, Backfilling
키워드: 클러스터 컴퓨팅, 배치작업, 스케줄링, 알고리즘, 백필링

Ⅰ. 서 론

최근 LHC(대형 강입자 충돌기: Large Hadron Collider), LSST(대형 시놉틱 관측 망원경: Large Synoptic Survey Telescope, SKA(Square Kilometer Array)와 같은 대형 관측 장비 및 다양한 센서 장비에서 수집되는 데이터의 규모가 기하급수적으로 불어나고 있다[1]. 이런 대규모의 데이터들을 신속하게 분석·처리하기 위한 도구 가령, 머신러닝, 딥러닝과 같은 AI 연구도 접목되고 있으며 더불어 계산 자원의 요구사항도 높아지고 있다. 국내에서도 이런 경향에 따라 중대규모의 클러스터 시스템 환경 구축이 점차 확대되고 있다[2].

일반적으로 클러스터 환경은 수많은 계산 노드로 구성되며 자원들을 사용자들은 서로 경쟁하며 사용하게 된다[3]. 한정된 계산 자원을 여러 사용자들이 효율적으로 사용하기 위해서는 실시간으로 자원상태를 파악하여 작업 수행에 맞는 시스템을 할당해야 한다. 배치 작업 스케줄러는 클러스터 환경에서 계산 자원을 인지하여 순서에 맞게 효율적으로 작업을 할당하는 역할을 수행한다[4]. 스케줄러의 자원으로는 클러스터 내에 구축된 다양한 리소스 가령, CPU, 메모리, 디스크 그리고 최근 많이 사용되는 계산 가속기 기반의 아키텍처인 GPU, FPGA, Xeon Phi(Intel MIC: Many Integrated Core) 뿐만 아니라 라이선스와 같은 HW 및 SW의 리소스를 인지하고 제어해야 한다. 클러스터내의 자원은 한정되어 있어 여러 사용자의 작업은 서로 경쟁을 통해 자원을 할당받게 된다. 그러나 가용 자원이 효율적으로 배분되지 않으면 자원의 단편화로 유휴 자원이 증가한다. 결국 수행하고자 하는 사용자의 작업은 오랜 대기시간이 발생하여 늦은 결과를 얻게 된다. 이를 해결하기 위해서는 작업의 규모와 수행 시간을 고려한 스케줄링 알고리즘을 적용해야 한다.

본 연구에서는 클러스터 환경에서의 배치 작업 스케줄러의 수행 환경을 분석하고 작업 회수시간(Turn-around Time) 최소화하기 위해 고려할 요인들을 제시한다[5]. 나아가 자원의 가용성을 확보하기 위한 스케줄링 알고리즘 기법을 제시하고 시뮬레이션을 수행하여 각 기법에 대한 성능을 평가, 제시한다. 향후 실제 클러스터 환경에 접목함으로써 자원의 활용률을 높이고 최적화할 수 있다.


Ⅱ. 관련 연구
2-1 배치 스케줄러

스케줄러는 클러스터 환경에서 대규모 병렬 처리(MPP; Massively Parallel Processing)를 위한 계산 자원 관리 프로그램으로 PBS(Portable Batch System), SGE(Sun Grid Engine), Slurm(Simple Linux Utility for Resource Management), LSF(Platform Load Sharing Facility ) 등 다양한 솔루션들이 있다[6][7]. 사용자는 이런 스케줄러를 통해 작업이 어떤 자원에 할당되어 수행될지에 고려하지 않고 작업을 제출할 수 있으며, 또한 여러 작업을 한 번에 실행 순서를 정하여 실행되도록 일괄처리 요청도 할 수 있다

작업(J) 수행을 위한 중요한 두 가지 속성은 (그림 1)과 같이 자원의 요구사항(R)과 실행시간(T)이다. 이 두 가지의 요구 사항을 받아 스케줄러는 작업간의 우선순위를 부여하는 스케줄링 정책을 적용하여 가용 자원이 확보되면 작업을 할당한다[8].


Fig 1. 
Properties of batch job

스케줄러에 배치 작업을 제출하기 위해서는 작업의 명세가 포함된 스크립트 파일을 작성한 후 스케줄러의 제출 명령을 사용하면 되는데 이 명세에는 위의 두 가지의 속성을 정의해야 한다. <표 2>는 PBS에서 스케줄러에 작업을 제출하기 위한 스크립트이다.

Table 1. 
Scheduler script for submitting the job
Batch Job Script
#!/bin/bash Shell definition
#PBS –V Export environment variables
#PBS –N Serial_Job Job naming
#PBS –q normal Specify the name of the server or queue
#PBS –l walltime=00:10:00 Job execution time requirements
#PBS –l select=1:ncpus=1 Job resource requirements
#PBS –A etc Application type
cd $PBS_O_WORKDIR Absolute path location on submission
./user_application User application

PBS에서는 qsub(Queue submission) 명령을 사용하여 작업을 제출하며 큐(Queue)의 대기 과정을 거쳐 계산자원이 확보되면 작업이 수행된다[9]. 본 클러스터 환경에서는 배타적 노드 할당 정책을 적용하여 한 노드에 하나의 작업만이 실행될 수 있게 설정되어있다. 이는 단일노드에 복수개 작업이 동시에 수행되어 발생할 수 있는 작업간의 혼선 및 성능 저하를 제거할 수 있다.

클러스터의 배치 작업 수행 환경에서 사용자의 어플리케이션 실행은 스케줄러를 통해 처리된다. 스케줄러는 자원 상태를 지속적으로 모니터링하며 작업을 할당하고 비정상 자원은 제외시킨다. 본 시스템에서는 작업은 스케줄러에 제출되어 실행이 완료 될 때까지 다른 작업에 의해 선점되지 않는다.

2-2 스케줄링

스케줄링은 사용자가 제출한 작업을 클러스터 내의 계산 자원에 할당하기 위한 메커니즘으로 클러스터 환경에 설정한 작업수행 시간(wall-time limit) 설정이나 작업 수행 및 실행 개수의 제한, 선점/비선점 방식, 공유 노드 사용 등의 정책을 반영하여 동작하게 된다[10].

배치 스케줄러를 통한 작업 실행의 각 프로세스의 단계는 (그림 2)와 같이 나타낼 수 있다. 사용자가 처음 작업을 제출하면 큐에 우선 대기하게 되며 순서와 가용 자원이 확보되면 비로소 작업을 수행하게 된다. 여기서 작업의 회수시간(Job Turn-around Time)은 사용자가 작업을 제출하고 결과를 얻을 때까지 클러스터에 작업이 할당되어 있는 시간으로 스케줄링 알고리즘에 따라 최적화 할 수 있다 [11]. 따라서 다양한 스케줄링 알고리즘에 대한 수행 방식과 자원의 활용성에 대해 검증할 필요가 있다.


Fig 2. 
Batch job processing procedure using scheduler

(그림 3)은 스케줄러를 통해서 배치 작업이 어떻게 할당되고 실행하는지를 보여주고 있다. (그림 1)과 같이 배치 작업이 요구하는 두 가지 속성에 따라 사용자가 작업을 제출하면 스케줄러는 현시점(t0)에서 가용 자원 (At0)이 충분한지 확인한다. 가용 자원은 클러스터 전체 자원(R)에서 작업이 할당된 자원(Ot0)을 제외(R-Ot0)한 유휴자원이다. 다음으로 가용 자원이 해당 작업 수행 시간동안 끝까지 확보되는지를 파악한다. 이 두 조건이 만족하면 해당 작업은 바로 수행이 된다.


Fig 3. 
Batch job execution and queued jobs in the scheduler

스케줄러에 제출되는 모든 작업은 정책과 알고리즘에 따라 실행 순서를 부여 받는데 스케줄러의 가장 기본적인 스케줄링 기법은 FCFS(First-Come First-Served)로 시간상으로 먼저 도착하는 작업을 우선 실행하게 하는 것이다. FCFS는 작업 순서의 공정성을 보장하는 가장 좋은 방법이지만 요구하는 계산 자원의 크기가 증가할수록 가용 자원의 조각화가 발생하여 리소스의 효율적인 사용에 제한 있다[12].

자원 조각화로 인해 발생하는 유휴자원을 줄이는 가장 극단적인 방법은 작은 작업을 먼저 할당하는 SJF (Shortest Job First) 알고리즘이다. 이 기법은 리소스 활용도를 높이고 전반적인 성능을 향상시킬 수 있지만 작업 순서의 공정성을 보장하지는 않으며 최악의 경우 대규모 작업이 수행되지 못하고 계속 대기해야하는 기아(starvation) 문제가 발생할 수 있다[13]. 따라서 스케줄링 정책은 자원 크기와 작업 특성을 고려하여 자원의 공정성(FCFS)과 자원의 효율성(SJF)을 결합하는 형태로 적용 되어야 한다[24]. 백필링 기법은 FCFS를 보장하면서 작은 작업 우선 할당하여 단편화된 자원을 보다 효율적으로 사용할 수 있는 기법이다.

스케줄러는 주기적으로 자원의 상태를 갱신하고 위와 같은 스케줄링 정책에 따라 작업을 배치하게 되는데 이 이벤트를 스케줄링 주기(Scheduling Cycle)라고 한다. 스케줄링 주기는 스케줄링 서버 또는 데몬이 구동될 때, 작업을 제출하거나 종료될 때, 스케줄러의 새 구성이 적용될 때 등에서 발생한다[15].


Ⅲ. 알고리즘
3-1 FCFS

FCFS 스케줄링의 기본 정책으로 단순히 먼저 도착한 작업을 가용한 자원에 시간 순서대로 할당한다. (그림 3)의 대기 작업은 (그림 4)에서와 같이 할당되며 우선순위가 높은 작업의 자원 확보량이 많은 경우 해당 작업보다 시간상으로 우선하는 가용 자원에서 수행될 수 있는 작업일지라도 후순위에 있다면 점유 될 수 없다. <표 2>는 FCFS 기법의 수행 절차를 나타내며 대기 작업(Wj)은 시간 순서(ti)에 따라 단순히 배치된다.


Fig 4. 
Job arrangement according to FCFS scheduling

Table 2. 
FCFS Algorithm


3-2 Backfilling

백필링은 FCFS 스케줄링에서 단순히 시간 순서대로 작업을 할당할 시 발생할 수 있는 단편화된 자원을 보다 효율적으로 사용할 수 있는 기법이다. 즉, 시간상으로 늦게 도착한 작업이라도 상대적으로 자원의 요구사항이 큰 우선순위 높은 작업에 의해 사용되지 않은 작은 규모의 가용 자원을 후순위 작업에 우선 할당하는 기법이다 [15]. (그림 1)에서와 같이 스케줄러에 제출 된 배치 작업에는 요구하는 리소스 및 실행 시간에 대한 속성이 있다. 백필링 알고리즘도 두 가지 속성의 데이터 구조를 사용해서 작업을 배치하는데 첫 번째는 요구 자원(프로세서) 프로필과 두 번째는 작업이 요구하는 실행 시간을 저장하는 목록을 갖는다.

1) Conservative Backfilling

Conservative Backfilling은 가장 기본이 되는 백필링 알고리즘으로 스케줄링의 기본 원칙인 FCFS 방식을 준수하며 후순위 작업이라도 가용 리소스에 작업 수행이 가능하다면 우선 실행된다. (그림 5)는 백필링 알고리즘에 따른 작업의 배치를 보여주고 있다. 작업 B2는 B1보다 우선순위가 낮지만 선행 작업을 지연시키지 않고 비어 있는 가용 자원에서 우선 처리될 수 있다. 작업 B4의 경우 t2 시점에 배치될 수 있지만 작업 수행 시간 선행 작업인 B1을 지연(t3-t2 < t5-t4)시키게 된다. 이는 FCFS를 위배되기 때문에 백필링이 될 수 없다.


Fig 5. 
Job arrangement of Conservative Backfilling

FCFS의 경우 후순위 작업은 선행 작업이 배치된 이후부터 수행 가능한 가용 자원을 찾아 배치되지만 <표 3>을 보면 Conservative backfilling 기법은 선행 작업과 상관없이 처음(t0)부터 자원의 크기와 수행 시간을 맞출 수 있다면 배치가 된다.

Table 3. 
Conservative Backfilling Algorithm


여기서 고려할 점은 <표 1>과 같이 자원의 요구사항(R)과 실행시간(T)을 사용자가 직접 작업 스크립트에 작성하여 제출하게 되며 스케줄러는 이것을 바탕으로 작업 수행 시간을 예측하여 스케줄링하게 된다. 그러나 대부분의 작업 수행 시간과 실제 수행 시간은 일치하지 않으며 스케줄링 주기(Scheduling Cycle)마다 전체 자원의 상태를 스캔하고 작업을 배치하게 된다.

만약 (그림 6)과 같이 예측된 시간보다 일찍 종료된 경우 가용 자원이 변경되어 Conservative backfilling 정책에 따라 작업 B1이 다시 우선 배치되어야 한다[16].


Fig 6. 
Scheduling rearrangement due to shortened job execution time

이 알고리즘은 하위 작업으로 인해 이전 작업에 대해 대기 시간이 필요하지 않지만 이전 작업이 예상 시간보다 일찍 종료되는 경우 계획된 작업 순서를 보장 할 수 없다.

2) Easy Backfilling

Easy(Extensible Argonne Scheduling System) Backfilling은 좀 더 공격적인(aggressive) 알고리즘으로 각 작업의 수행 시간을 완벽하게 보장하기 보다는 약간의 지연이 있더라도 가용 자원을 사용할 수 있다면 후순위 작업을 먼저 배치하여 전체 자원 사용의 효율성을 높이고자 하는 것이 목적이다[17]. (그림 6)에서는 작업 B2의 수행 시간이 B1의 지연을 발생시켜 후순위로 다시 배치되었으나 (그림 7)의 경우는 B1이 지연(t2-t1) 되더라도 B2 작업을 먼저 배치함으로서 자원의 활용성을 높이고 작업 회수시간(Turn-around Time)을 줄일 수 있다(t3-t2 < t2-t0).


Fig 7. 
Job optimization according to Easy Backfilling

<표 4>와 같이 Easy Backfilling은 사용 가능한 최소 노드가 확보되면 선작업이 지연되더라도 후작업이 먼저 배치될 수 있다. Easy Backfilling은 큐에 대기하는 작업 수가 많은 경우 백필링이 될 수 있는 더 많은 기회가 제공된다. 그러나 만약 (그림 7)에서 B2 작업의 실행시간이 길어지면 B1작업은 계획보다 오래 지연될 수 있다. 가용 자원을 좀 더 적극적으로 사용할 수 있는 알고리즘이지만 작업량과 작업의 패턴에 따라 작업 수행에 차이가 날 수 있다.

Table 4. 
Easy Backfilling Algorithm



Ⅳ. 작업 부하 분석

본 장에서는 다양한 스케줄링 알고리즘과 수행 환경에 따른 작업의 배치와 자원의 효율성 및 작업 회수시간을 분석하고자 한다. 이 클러스터 환경에서는 계산자원에 할당된 작업은 시작부터 종료까지 다른 작업에 의해서 선점(preemptive) 되지 않으며 하나의 작업만 하나의 계산자원에서 수행된다[18]. 또한 정해진 배치 작업을 선정하는 정적 워크로드(Static workload) 환경을 가정하므로 배치 작업은 추가적으로 제출되지 않는다고 정한다. 큐에 배치 작업이 <표 5>와 같이 할당 되어있고 클러스터 전체의 가용 자원(Process)은 10이라고 한다. 작업 ID (JobID)는 사용자가 작업을 제출할 때 할당되는 고유한 식별자이며 작업의 인덱스가 낮을수록 시간상으로 먼저 제출된 작업으로 우선순위(Priority P, P(Ji) >P(Ji+1))를 갖는다. 각 작업마다 요구하는 자원과 실행시간을 가지고 있으며 마지막 줄의 작업 상태(Job status)는 작업이 현재 실행(R) 또는 대기(W)중인지를 나태난다. 전체 가용 자원이 10이므로 J1, J2, J3 작업은 바로 실행이 된다. J4는 요구 자원이 8이므로 가용 자원이 발생하기 전까지 대기해야 한다.

Table 5. 
Parallel jobs attribute of scheduler queue
JobID J1 J2 J3 J4 J5 J6 J7
Process 2 1 2 8 3 10 5
Execution Time 9 5 3 2 4 1 3
Job Status R R R W W W W

<표 6>은 FCFS 스케줄링 정책을 적용했을 때 자원의 배치 상황을 나타낸다. J1~J7까지 작업은 시간의 순서(타임스탬프)대로 배치되며 요구 자원(작업별 표시된 숫자)이 부족한 작업들은 선 작업이 종료된 후 가용 자원이 확보되면 수행 된다. 전체 작업은 타임스탬프 15에서 종료된다.

Table 6. 
Job arrangement according to FCFS scheduling
Time
Stamp
Available Resources JOB ID
Previous Current J1 J2 J3 J4 J5 J6 J7
1 10 5 2 1 2        
2   5        
3   5        
4 5 7          
5   7          
6 8 0     8      
7   0          
8 8 5       3    
9   5          
10 5 7            
11   7            
12 10 0           10  
13 10 5             5
14   5            
15   5            

<표 7>은 기본 백필링 알고리즘인 Conservative Backfilling을 적용했을 때의 작업 배치이다. 후순위 작업인 J5는 선순위 작업의 실행시간을 보장하면서 작업이 수행될 수 있는 가용 자원에 우선 배치된다. 그러므로 전체 작업은 FCFS 보다 빠른 타임스탬프 13에 종료된다.

Table 7. 
Job arrangement according to Conservative Backfilling
Time
Stamp
Available Resources JOB ID
Previous Current J1 J2 J3 J4 J5 J6 J7
1 10 2 2 1 2   3     
2   2      
3   2      
4 2 4        
5 4 7          
6 8 0     8      
7   0          
8 0 8          
9   8          
10 10 0         10  
11 10 5           5 
12 5        
13 5          

<표 8>은 기본 백필링 알고리즘인 Easy Backfilling을 적용했을 때의 작업 배치이다. 여기서 작업 J7의 선작업인 J6이 약간 지연이 발생하더라도 작업 J7은 수행 가능한 자원이 확보된 타임스탬프 8 시점에 먼저 백필링이 된다. 이로써 자원의 사용량을 더 확보할 수 있어 전체 작업은 Conservative Backfilling 보다 빠른 타임스탬프 11에 종료된다.

Table 8. 
Job arrangement according to Easy Backfilling
Time
Stamp
Available Resources JOB ID
Previous Current J1 J2 J3 J4 J5 J6 J7
1 10 2 2 1 2   3     
2   2      
3   2      
4 4        
5 7          
6 8 0     8      
7   0          
8 8 3         5
9   3        
10 5         Delay
11 10 0         10

백필링의 기본 메커니즘은 사용자가 작성한 작업의 런타임 예상치를 이용하여 작업이 대기열의 뒤쪽에 있더라도 가능한 한 더 빨리 실행하게 할 수 있다. 그러나 대부분의 사용자는 충분한 작업 시간을 확보하기 위해 실제 작업 수행 시간 보다 과대 추정하여 작업 시간을 정하는 경향이 있다[19]. 따라서 2-2절에서 언급한 스케줄링 주기(Scheduling Cycle)마다 전체 작업을 알고리즘 정책에 따라 재배치하고 가용 자원을 할당한다.

<표 9>와 <표 10>은 제출한 작업이 실제 수행 시간 보다 일찍 종료되어 각 스케줄링 알고리즘 정책에 따라 작업이 재배치된 경우이다. 언급하였듯이 Conservative Backfilling은 선 작업의 수행 시간을 보장하면 가용 자원의 발생하면 후순위 작업을 먼저 배치하고 Easy Backfilling은 선 작업이 약간 지연되더라도 후순위 작업의 가용 자원이 확보되면 먼저 작업을 배치하여 전체 자원의 활용성을 높이는 좀 더 공격적인 알고리즘이다[20]. 여기서 전체 작업은 Conservative Backfilling 타임스탬프 11에 Easy Backfilling 타임스탬프 10에 종료된다.

Table 9. 
Conservative backfilling due to early termination
Time
Stamp
Available Resources JOB ID
Previous Current J1 J2 J3 J4 J5 J6 J7
1 10 2 2 1 2   3     
2   2      
3   2      
4 2 4        
5 4 7          
6 8 2 Early
Termination
    8      
7   2          
8 10 0       10  
9 10  5         5 
10 5        
11 5        

Table 10. 
Easy Backfilling due to early termination
Time
Stamp
Available Resources JOB ID
Previous Current J1 J2 J3 J4 J5 J6 J7
1 10 2 2 1 2   3     
2   2      
3   2      
4 4        
5 7 2         5
6 5 5 Early
Termination
    Delay    
7   5        
8 10 2     8 Delay
9   2    
10 10 0         10


Ⅴ. 결론 및 향후 연구

최근 기하학적으로 불어나는 데이터의 양에 따라 이것을 분석하기 위한 컴퓨팅 자원의 요구사항이 점차 증가하고 있다. 이에 국내외 산학연 기관들은 중대규모의 클러스터 환경을 구축하고 병렬환경을 이용하여 거대규모의 문제들을 풀어가고 있는 실정이다. 클러스터 환경이 구축되고 그 안에 구성된 계산 자원을 최대한 효율적으로 활용하기 위해 스케줄러라는 시스템 소프트웨어를 사용하게 되는데 스케줄러는 클러스터 내의 한정된 계산 자원을 동시에 여러 사용자들이 다양한 요구사항(라이선스 정책, 작업의 의존성, 이기종 HW 지원, 작업 예약 등)과 자원정책(작업의 수행 시간 및 개수 제한, 공유 및 배타적 노드 정책 등)을 적용하여 사용할 수 있도록 제공한다. 특히 스케줄러는 클러스터 내에 구축된 다양한 리소스를 인지하고 스케줄링 알고리즘에 따라 가용 자원에 작업을 배분하는데 스케줄링 알고리즘에 따라 클러스터의 계산 자원 효율성은 크게 달라진다. 따라서 스케줄링 알고리즘에 대한 충분한 이해와 분석이 필요하다.

본 논문에서는 스케줄링 알고리즘에 대한 연구와 가용 자원을 최대한 효율적으로 사용할 수 있는 백필링 알고리즘에 대해 언급하였다. 또한 각 알고리즘을 클러스터 환경에 배치되는 작업과 유사하게 설정하고 자원의 활용성과 전체 작업의 수행 시간을 실험하였다. Conservative Backfilling은 선 작업의 수행 시간을 보장하는 반면 Easy Backfilling은 선 작업이 약간 지연되더라도 후순위 작업의 가용 자원이 확보되면 우선 배치하는 자원 활용에 보다 적극적인 알고리즘이다. 실제 클러스터의 규모가 커지고 수행되는 배치 작업의 개수가 증가하면 Easy Backfilling의 자원 활용성은 훨씬 증가하게 되고 소규모 작업들은 빠른 시간 안에 처리될 수 있어 전체 작업의 회수시간(Turn-around Time)이 줄어들게 된다. 그러나 Easy Backfilling에서 수용하는 선작업의 지연시간은 작업의 규모에 따라 크게 차이가 날 수 있어 대규모의 작업들은 실제 수행되는 시간보다 오랫동안 지연될 수 있다. 이를 위해 백필링이 되는 작업의 개수 제한(backfill_depth), 지연시간의 제한 등 추가적인 기법들이 알고리즘에 포함된다면 자원 활용성과 공평성을 동시에 가져갈 수 있다. 향후 이런 기법들을 알고리즘에 적용하여 추가적인 실험이 요구되며 실제 클러스터 스케줄링 정책에 반영하여 전체적인 자원 효율성을 검증할 필요가 있다.


Acknowledgments

본 연구는 2020년도 부산교육대학교 학술연구과제로 지원을 받아 수행되었음.


References
1. Quinn P, Axelrod T, Bird I, Dodson R, Szalay A, Wicenec A, "Delivering SKA science," preprint arXiv: 1501.05367, 2015.
2. Parashar M, “Big data challenges in simulation-based science,” In DICT@ HPDC, pp. 1-2, June 2014.
3. Buyya, Rajkumar, "High performance cluster computing: Architectures and systems," Prentice Hall, Upper SaddleRiver, NJ, USA 1.999:29, Vol 1, 1999.
4. He, Libo, et al., "A Review of Resource Scheduling in Large-Scale Server Cluster", International Conference on Knowledge Management in Organizations. Springer, Cham, pp. 494-505, 2017.
5. JW Yoon, TY Hong, CY Park, SY Noh, HC Yu, “Log Analysis-Based Resource and Execution Time Improvement in HPC: A Case Study,” Applied Sciences, Vol. 10, No. 77, 2002.
6. Templeton, D, “A Beginner’s Guide to Sun Grid Engine 6.2”, Whitepaper of Sun Microsystems, July 2009.
7. SchedMD, L. L. C, “Slurm workload manager,” Retrieved May, 12, 2018.
8. Feitelson D.G, Weil A.M.A, “Utilization and predictability in scheduling the IBM SP2 with backfilling,” In Proceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, Orlando, FL, USA, 30, pp. 542–546. April 1998.
9. Henderson R. L, “Job scheduling under the portable batch system,” In Workshop on Job Scheduling Strategies for Parallel Processing, Springer, Berlin, Heidelberg, pp. 279-294, April, 1995.
10. He, Li, Jarvis S. A, Spooner D. P, Chen X, Nudd G. R, “Dynamic scheduling of parallel jobs with QoS demands in multiclusters and grids,” In Fifth IEEE/ACM International Workshop on Grid Computing IEEE, pp. 402-409, November 2004.
11. Sabin G, Kochhar G, Sadayappan P, “Job fairness in non-preemptive job scheduling,” In Proceedings of the International Conference on Parallel Processing, ICPP 2004, Montreal, QC, Canada, pp. 186–194, 15–18 August 2004.
12. Schwiegelshohn U, Yahyapour R, “Analysis of first-come-first-serve parallel job scheduling,” In Proceedings of the SODA, San Francisco, CA, USA, 25–27 Vol. 98, pp. 629-638, January 1998.
13. Hovestadt M, Kao O, Keller A, Streit A, “Scheduling in HPC resource management systems: Queuing vs. planning,” In Workshop on Job Scheduling Strategies for Parallel Processing; Springer: Berlin, Germany, pp. 1–20, 2003.
14. Etsion Y, Tsafrir D. A, “Short Survey of Commercial Cluster Batch Schedulers,” School of Computer Science and Engineering, The Hebrew University of Jerusalem: Jerusalem, Israel, 44221, pp. 2005–2013, 2005.
15. Pascual J. A, Navaridas J, Miguel-Alonso J, “Effects of topology-aware allocation policies on scheduling performance,” In Workshop on Job Scheduling Strategies for Parallel Processing,. Springer, Berlin, Heidelberg, pp. 138-156, May 2009.
16. Wong A. K, Goscinski A. M, “Evaluating the easy-backfill job scheduling of static workloads on clusters,” In 2007 IEEE International Conference on Cluster Computing, pp. 64-73, September 2007.
17. Srinivasan S, Kettimuthu R, Subramani V, Sadayappan P, “Characterization of backfilling strategies for parallel job scheduling,” In Proceedings of the International Conference on Parallel Processing Workshop, Vancouver, BC, Canada, pp. 514–519, 21 August 2002.
18. JW Yoon, US Song, “Study of Scheduling Optimization through the Batch Job Logs Analysis,” Journal of Digital Contents Society, Vol. 18, No. 7, pp. 1411-1418, 2017.
19. Parallel Workload Archive by Dror Feitelson. URL: http://www.cs.huji.ac.il/labs/parallel/workload/, last access: November 2020.
20. Klusacek D, Chlumsky V, “Planning and metaheuristic optimization in production job scheduler,” In Job Scheduling Strategies for Parallel Processing, Springer, Cham, Switzerland, pp. 198–216, 2015.

저자소개

윤준원(JunWeon Yoon)

2002년~2004년 : 고려대학교 대학원 컴퓨터학과(이학석사)

2010년~2018년 : 고려대학교 대학원 컴퓨터학과(공학박사)

2005년~현 재 : KISTI 국가슈퍼컴퓨팅본부 선임연구원

※관심분야: 분산컴퓨팅, 결함포용시스템, 슈퍼컴퓨팅, 병렬파일시스템, 배치스케줄링, 벤치마크(BMT)

송의성(Ui-Sung Song)

1990년~1997년 : 고려대학교 컴퓨터학과(학사)

1998년~1999년: 고려대학교 대학원 컴퓨터학과(이학석사)

2000년~2005년: 고려대학교 대학원 컴퓨터학과(이학박사)

2006년~현 재: 부산교육대학교 컴퓨터교육과 교수

※관심분야: 컴퓨터교육, 교육용로봇교육, 컴퓨터네트워크, 스마트러닝, 분산컴퓨팅