1. 서론

이질 프로세서를 위한 정적인 스케줄링 휴리스틱

(A Static Scheduling Heuristic for Heterogeneous Processors)

오 현 옥	하 순 회

(Hyunok Oh)	(Soonhoi Ha)

요  약    본 논문에서는 이질 수행 시간을 가지는 다중 프로세서를 대상으로 한 Best Imaginary Level (BIL) 스케줄링이라는 정적인 비선점 스케줄링 휴리스틱을 제안하였다. 스케줄링의 대상이 되는 입력 그래프는  선후 관계의 제약 조건을 가지는 비순환 그래프이며, 그래프 상의 각 노드는 각각의 프로세서에서 다른 수행 시간을 가진다. 노드의 정적인 레벨(BIL)은 프로세서간의 통신(IPC)을 고려하고 프로세서의 이질성도 고려한다. 제안된 스케줄링 기법이 입력 그래프의 모양이 선형인 경우 최적의 스케줄링 결과를 생성해 내는 것을 증명하였다. BIL 스케줄링은 현존하는 스케줄링 기법인 general dynamic level (GDL) 스케줄링 기법과 비교해서 다양한 형태의 무작위로 만들어낸 입력 그래프에 대해 약 20%의 성능 향상을 가져왔다.

Abstract  This paper presents a static scheduling heuristic called Best Imaginary Level (BIL) scheduling for heterogeneous processors. The input graph is an acyclic precedence graph, where a node has different execution times on different processors. The static level of a node, or BIL, incorporates the effect of interprocessor communication (IPC) overhead and processor heterogeneity. The proposed scheduling technique is proven to produce the optimal scheduling result if the topology of the input task graph is linear. The performance of the BIL scheduling is compared with an existing technique called the general dynamic level (GDL) scheduling with various classes of randomly generated input graphs, resulting in about 20% performance improvement.

네트워크의 빠른 발전에 힘입어 다양한 워크스테이션과 매인 컴퓨터 그리고 심지어 슈퍼컴퓨터 등으로 구성된 분산 시스템이 점차로 계산 능력을 향상시키기 위한 하나의 대안으로 대두되고 있다. 이러한 시스템은 대체로 상당한 프로세서간의 통신 시간(IPC)을 가지는 이질 시스템이다.

이질 시스템의 다른 예는 내장형 시스템에서 찾을 수 있다. 내장형 시스템은 어떤 특수한 응용에 알맞게 특화된 것으로 특정한 작업에 맞도록 설계된 하드웨어나 소프트웨어를 포함하고 있다. 범용 프로세서, 특수 목적을 위한 프로세서, 프로그램이 가능한 신호 처리용 프로세서 그리고 ASIC등이 많은 경우 내장형 시스템의 일부분으로 들어간다. 이러한 시스템에서 이질의 프로세서들은 프로세서간에 서로 밀접하게 연계되어 낮은 통신 시간을 가지지만 대신 자원에 상당한 제약을 받는다.

그림 . 스케줄링 입력 예

그래서 프로세서간의 통신 시간을 고려하여 프로세서의 이질성-하나의 작업은 각각의 프로세서에서 다른 수행 시간을 가짐-을 가진 이질 시스템을 위한 스케줄러의 개발이 필요하다. 동질의 프로세서로 이루어진 시스템을 위한 스케줄링 개발의 많은 연구를 통해서, 동질의 프로세서를 스케줄하는 문제가 매우 어려운 문제임이 밝혀졌다[1,2]. 동질의 프로세서로 이루어진 시스템은 이질의 프로세서로 구성된 시스템의 특별한 경우이므로 이질의 프로세서로 구성된 시스템을 위한 스케줄링 기법의 개발은 더욱 더 어려운 일이다. 그래서 본 논문에서는 Best Imaginary Level (BIL) 스케줄링이라 부르는 정적인 비선점 스케줄링 방법을 제안한다.

제안된 스케줄링은 비순환 선행 그래프(acyclic precedence graph : APG)를 입력으로 받는다. APG의 노드는 프로세서에서 수행되는 작업을 나타낸다. 그리고 각 간선은 두 노드 사이의 선후 관계를 나타낸다. 각 간선에 대응되어 있는 숫자는 프로세서간 통신(interprocessor communication : IPC) 시간을 나타낸 것이다. 만일 두 노드가 서로 다른 프로세서에 스케줄링 된다면 이 IPC만큼 후에 다음 노드가 스케줄될 수 있는 것이다. 이 스케줄링 방법에서 각 노드 [eqn: N_i]가 프로세서 [eqn: P_j]에서 수행되는 시간 [eqn: E(N_i , P_j )]는 각 노드-프로세서 쌍에 대해 컴파일 시에 이미 알려져 있다고 가정한다. 이때, 노드 [eqn: N_i]가 프로세서 [eqn: P_j]에서 수행될 수 없다면 수행시간 [eqn: E(N_i , P_j )]는 무한대이다. 이것은 프로세서 [eqn: P_j]가 노드 [eqn: N_i]를 위한 자원이나 명령어가 없는 경우에 발생한다. APG와 노드들의 수행 시간의 예가 그림 1에 나타나 있다. 여기서 대상이 되는 시스템의 구조는 IPC를 위한 별도의 하드웨어가 있어서 프로세서간의 통신 시간과 계산 시간이 서로 겹쳐질 수 있다고 가정한다.

본 논문에서 스케줄링의 목적은 입력 그래프에 대한 스케줄 결과의 길이- makespan-를 최소화하는데 있다. 이러한 스케줄링 문제는 강한 NP-hard 문제[1,2,3]이므로 휴리스틱으로 해결한다. 이질 프로세서를 위한 스케줄링 문제에 대한 연구는 알려진 것이 매우 적으며, 본 논문에서는 비교적 잘 알려진 스케줄링 방법인 G.C. Sih와 E.A. Lee의 General Dynamic Level (GDL)[8] 스케줄링에 대해 알아볼 것이다. 그리고 무작위로 생성된 그래프에 대해 제안된 스케줄링 기법인 BIL을 GDL과 비교할 것이다.

GDL과 BIL 스케줄러는 둘다 리스트 스케줄링[4,5]에 기초를 두고 있다. 즉 각 노드에 우선순위가 부여되어 있다. 노드의 부모가 모두 스케줄이 되어 있으면 그 노드는 스케줄 가능하다고 부른다. 리스트 스케줄링은  스케줄할 가장 높은 우선 순위의 노드를 선택한 다음 그 노드에 가장 적절한 프로세서를 선택하는 두 단계로 이루어지는 것이 보통이다. 이러한 리스트 스케줄에 기반해서 노드에 우선 순위를 어떻게 부여하는지, 선택된 노드를 어느 프로세서에 스케줄하는지에 따라 여러 다른 변형된 스케줄링 방법이 나타났다[6,7,8,9]. 다음절에서 GDL 스케줄링 기법을 알아보고 그것의 한계에 대해 알아보겠다. 3절에서는 제안된 BIL 스케줄링 기법에 대해 설명하도록 하겠다. 4, 5절에 실험 결과와 결론이 나타나 있다.

2. General Dynamic Level Scheduling Technique

스케줄 길이는 노드에서부터 마지막 노드까지의 최대길이 즉 임계 경로 길이보다 작을 수 없다. 그래서 스케줄 길이를 줄이기 위해서는 최대 임계 경로상의 노드에 가장 높은 우선 순위를 주어야하는 것이 당연하다. 노드의 임계 경로의 길이는 임계 경로상의 노드들의 수행 시간의 합으로 주어지며, 이때 이 노드들이 다른 프로세서에 스케줄된다면 프로세서간 통신 시간도 고려되어야 한다. 그런데 동질의 프로세서를 위한 전형적인 리스트 스케줄링 기법에서는 노드의 우선 순위를 임계 경로상의 노드들의 수행 시간의 합으로 계산한다. 이것은 동질의 프로세서에 임계 경로상의 노드들이 스케줄될때는 같은 프로세서에 스케줄되는 것이 최상의 결과를 낳기 때문이다. 이러한 우선 순위를 노드의 정적 레벨 [eqn: SL(N_i )]이라 부른다.

그러나 이질 시스템에서는 노드들이 각각의 프로세서에 대해 서로 다른 수행 시간을 가지므로, 정적 레벨을 단지 노드 수행시간 최소값의 합으로 계산한다면 노드들의 정적 레벨과 최적의 스케줄과는 차이가 생기게 된다. 즉 동질 시스템을 위한 스케줄에서 정적인 레벨 계산 방법은 이질 시스템에는 더 이상 적합하지 않다. 그래서 GDL 스케줄러는 노드 [eqn: N_i]의 가상 수행시간을 모든 프로세서에 대해 노드 [eqn: N_i]의 수행 시간 중간값인 [eqn: E^* (N_i )]로 정의한다. 만약 이 수행 시간 중간값이 무한대라면 가장 큰 유한한 값으로 [eqn: E^* (N_i )]를 재정의한다. GDL은 이 [eqn: E^* (N_i )]값으로 정적 레벨 [eqn: SL(N_i )]를 동질의 프로세서를 위한 스케줄과 같은 방법으로 계산한다.

GDL 스케줄러는 노드가 스케줄 가능했졌을 때 통신 시간을 고려하여 레벨값을 바꾼다. 노드 [eqn: N_i]에 필요한 모든 데이타가 프로세서 [eqn: P_j]에 도착하는 가장 이른 시각- 프로세서간 통신 시간을 고려했을 때 노드 [eqn: N_i]가 스케줄 가능한 시각-을 [eqn: DA(N_i , P_j )]로 정의하고, 프로세서 [eqn: P_j]에 스케줄 가능한 시각을 [eqn: TF(P_j )]로 정의한다. 그러면 노드 [eqn: N_i]를  [eqn: DA(N_i , P_j )]와 [eqn: TF(P_j )] 중 큰값인 [eqn: T(N_i , P_j )]후에 [eqn: P_j]에 스케줄할 수 있다. 즉 [eqn: T(N_i , P_j )]값은 노드가 프로세서에 스케줄 가능한 가장 작은 값이다. 그리고 프로세서의 성능을 고려하기 위해서 다음과 같은 정의를 한다.

[eqn: Delta (N_i , P_j ) = E^* (N_i ) - E(N_i , P_j ).]

[eqn: Delta(N_i , P_j )]가 클수록 프로세서 [eqn: P_j]가 노드 [eqn: N_i]를 다른 프로세서에서보다 빨리 수행할 수 있다는 의미이다. 이상의 정의로부터 다음과 같은 동적 레벨 DL1(Ni,Pj)를 계산한다.

[eqn: DL_1 (N_i ,P_j ) = &SL(N_i ) - T(N_i ,P_j ) #& + Delta(N_i , P_j ).]

이 동적 레벨을 이용하여 임계 경로가 길고, 수행가능한 노드에서 프로세서 [eqn: P_j]에서 먼저 스케줄될 수 있으며, 그 프로세서에서의 수행시간이 빠른 노드에 높은 우선 순위를 부여한다. DL1(Ni,Pj)는 노드 [eqn: N_i]가 프로세서 [eqn: P_j]에서 얼마나 잘 어울리는 지에 대한 척도이긴 하지만, 노드 [eqn: N_i]의 자손을 고려한 상태에서 [eqn: P_j]에 스케줄되는 것이 얼마나 좋은 지에 대해서는 알 수 없다. 만일 노드 [eqn: N_i]의 자손 중 하나가 프로세서 [eqn: P_j]의 자원의 부족 때문에 프로세서 [eqn: P_j]에는 스케줄될 수 없다면 노드 [eqn: N_i]와 그 자손사이에는 프로세서간 통신 시간이 필요하게 되므로 노드 [eqn: N_i]를 프로세서 [eqn: P_j]에 스케줄할 때 그 노드의 자손에 대한 고려도 필요하다. 이러한 관찰에 기초해서 GDL 스케줄러는 노드 [eqn: N_i]의 자식중 가장 큰 프로세서간 통신 시간을 가지는 노드 [eqn: D(N_i )]를 선택한 후, 노드 [eqn: N_i]가 프로세서 [eqn: P_j]에서 수행된다면 [eqn: D(N_i )]가 얼마나 빨리 다른 프로세서에서 수행이 끝날 수 있는 지를 알려주는 F[Ni,D(Ni),Pj]를 정의한다. 노드 [eqn: N_i]의 동적 레벨은 그 자손의 영향을 고려하여 다음과 같이 개선한다.

[eqn: &DC(N_i , P_j ) = E^* [D(N_i )] - #&min (E[D(N_i ),P_j ],F[N_i ,D(N_i ),Pj])]

[eqn: DL_2 (N_i ,P_j ) = DL_1 (N_i , P_j )+DC(N_i , P_j )]

끝으로 이질 시스템에서는 자손의 고려뿐만 아니라, 노드가 어떤 프로세서에서는 수행될 수 없는 경우도 고려해야 한다. 이러한 자원의 부족을 고려하기 위해서 DL2(Ni,Pj) 값이 가장 크게 되는 최적의 프로세서 [eqn: P_j]*와 그 다음으로 크게 되는 프로세서를 선택한다. 그러면 일반적인 동적 레벨(generalized dynamic level)은 다음과 같이 정의된다.

[eqn: C(N_i ) = DL( N_i , P _j^* ) - max atop { scale 80 k != j^*} DL ( N_i, P_k )# GDL(N_i , P) = DL_2 (N_i , P_{j^*} ) +C(N_i )]

C(Ni)는 노드가 두번째로 최적인 프로세서로 스케줄되기를 원한다면 레벨의 값을 증가시킨다. GDL 스케줄링 기법은 가장 우선 순위가 높은 스케줄 가능한 노드를 선택한 후 이미 결정된 최적의 프로세서에 스케줄하게 된다.

이러한 GDL 스케줄러는 몇가지 단점을 가진다. 첫째로 정적 레벨 SL*(Ni)의 정의가 무작위적이다. 정적 레벨은 수행시간 중간값으로 계산하는데 그렇게 하는 이유가 미약하다. 다른 종류의 수행시간, 예를 들어 가장 짧은 수행시간이나 가장 긴 수행시간을 이용하는 것이 더 좋을 수도 있다. 그리고 GDL의 정적 레벨은 동질 시스템을 위한 스케줄에서의 정적 레벨처럼 가장 최적의 임계 경로 길이를 나타내고 있는 것도 아니다. 둘째로 자손 노드에 대한 고려가 부족하다. 국지적인 정보 즉 자식 노드만을 고려한 정보로 최적인 프로세서에 노드를 스케줄하는데 이는 그림 1의 예를 스케줄했을 때 그림 2 (a)와 같이 나쁜 결과를 생성한다. 그림 1의 예를 살펴보면 노드 A가 프로세서 P1에 스케줄되는 것이 당연하지만, GDL은 노드 A를 스케줄할 때 자식 노드 B만을 고려하여 프로세서 P0에 스케줄하게 된다. 자손 노드에 대한 충분한 정보를 가지기 위해서는 정적 레벨에 이러한 정보를 포함하도록 하는 것이 바람직하다. 그래서 정적 레벨이 무작위적인 것이 아니라 자손 노드에 대한 정보를 포함하도록 정의하는 새로운 스케줄링 방법에 대해서 앞으로 설명하도록 하겠다.

그림 . 현재의 스케줄링 결정이 노드의 영향을 고려하지 못한 (a) GDL 스케줄러와  이를 고려한 (b) BIL 스케줄러의 성능 비교

3. Best Imaginary Level Scheduling

3.1 정적인 레벨 계산

동질 시스템에서 노드의 정적 레벨은 그 노드에서부터 마지막 노드까지의 가장 긴 수행 경로 길이로 정의되는 것이 흔히 알려진 방법이다. 이것은 가장 긴 경로상의 모든 노드들이 동일한 프로세서에 스케줄되는 경우 실제 수행시간과 일치할 수 있다. 그러나, 이질 시스템의 경우에는 가장 긴 경로를 최소화하기 위하여 각 노드의 수행 시간의 최소값을 가지고 계산할 수 없다. 왜냐하면, 가장 긴 경로 상의 모든 노드들이 최소값을 갖는 프로세서가 동일한 프로세서가 아닌 경우에는 프로세서간 통신이 고려되어야 하기 때문이다. 프로세서간 통신을 고려하지 않기 위하여 GDL에서는 노드 수행시간 중간값으로 정적 레벨을 계산한다. 그러나, 제안하는 스케줄링 기법에서는 시스템이 동질인 경우와 마찬가지로 이질 시스템에서 이상적인 경우에 실제스케줄과 일치할 수 있도록 노드의 정적 레벨을 정의한다. 이러한 정적 레벨은 BIL(Best Imaginary Level)이라 부르며, 동질 시스템에서 노드의 정적 레벨은 BIL의 특별한 경우로 여길 수 있다. 노드의 BIL은 다음과 같은 가정에 기초한다.

가정 : 모든 자손 노드들은 가장 이른 순간에 스케줄된다.

물론 이 가정은 항상 실현 가능한 것은 아니다. 즉 둘 이상의 노드들이 동시에 같은 프로세서에 스케줄될 수가 있다. 그래서 최적 가상(Best Imaginary)이라는 말은 이러한 가정이 항상 실제적이지는 않다는 점을 강조하는 것이다.

위의 가정에 따라 노드의 BIL은 다음과 같은 재귀적인 형태로 정의한다.

그림 . 그림 1의 BIL값

[eqn: &BIL( N_i ,P_j ) = E(N_i , P_j ) + max atop { scale 70 d in D(N_i ) } #& [ min (BIL(d_l , P_j ), min atop { scale 70 k not = j } (BIL(d_l , P_k ) #&+ d(N_i , d_l ))]]정의 1.

단, [eqn: D(N_i )]는 [eqn: N_i]의 자식 노드 집합을, [eqn: d(N_i , d_l )]은 노드 [eqn: N_i]와 노드 [eqn: d_l] 사이의 통신시간을 나타낸다.

그림 1의 예에 대해서 BIL값을 계산해 보도록 하자. 먼저 재귀적인 정의에 따라서 가장 마지막 노드인 C의 BIL값을 구한다. 노드 C는 자손 노드를 가지지 않은 가장 마지막 노드이므로 BIL값은 수행 시간값과 같다. 노드 B와 A의 BIL값은 다음과 같다.

[eqn: BIL&(B,P0) = E(B,P0) + #&max[ min (BIL(C,P0), #&BIL(C,P1)+d(B,C)) ] #&= 2 + max[ min( INF , 1 + 12 ) ] = 15. #BIL&(B,P1) = E(B,P1) + #&max [ min (BIL(C,P1), #&BIL(C,P0) + d(B,C)) ] #&= 2 + max[ min(INF+12) ] = 3. #BIL&(A,P0) = E(A,P0) + #&max [ min (BIL(B,P0), #&BIL(B,P1) + d(A,B)) ] #&= 1 + max[ min( 15, 3+10) ] = 14. #BIL&(A,P1) = E(A,P1) + #&max [ min (BIL(B,P1), #&BIL(B,P0) + d(A,B)) ] #&= 2 + max[ min( 3, 15+10) ] = 5.]

노드 [eqn: N_i]가 프로세서 [eqn: P_j]에 스케줄된다고 가정할 때의 [eqn: BIL(N_i , P_j )]는  통신시간을 포함한 가장 긴 수행 경로 길이의 최소값을 나타낸다. BIL은 계산하는 중에 통신시간을 고려하기 때문에 노드의 BIL은 낙관적인 가정 하에서 모든 자손 노드들을 고려한 전역적인 정보로 생각할 수 있다. 그래서 BIL 스케줄러는 전역적인 정보를 가지고 있지 않은 GDL 스케줄러에 비해서 그림 1의 예에서 매우 뛰어난 성능을 나타낸다. 그 결과가 그림 2에 나타나 있다. 스케줄러는 손자 노드인 C를 노드 A의 BIL 계산에서 고려했기 때문에, 노드 A는 프로세서 P1에 스케줄된다. 실제로 BIL 스케줄러는 입력 그래프가 선형일 경우에 항상 최적의 결과를 생성한다.

정리 : BIL 스케줄러는 입력 그래프가 선형일 경우 최적의 결과를 생성한다.

[증명] 먼저 수학적 귀납법으로 노드 [eqn: N_i]가 프로세서 [eqn: P_j]에 스케줄된다고 가정하면 BIL(Ni,Pj)가 노드 [eqn: N_i]에서부터 마지막 노드까지의 가장 짧은 종료 시간을 나타낸다는 것을 증명한다.

(i) 노드가 하나인 경우

정의에 의해 BIL(N1,Pj) = E(N1,Pj)이다. 따라서 BIL이 가장 짧은 종료 시간을 나타낸다는 것은 자명하다.

(ii) BIL(N2,Pj)는 노드 N2가 [eqn: P_j]에 스케줄될 때 마지막 노드까지의 가장 짧은 종료 시간을 나타낸다고 가정하자.

(iii) 이 선형 그래프의 선두에 노드 N1을 추가한다.

[eqn: &E(N_1 ,P_j ) + min_k ~ (BIL(N_2 , P_k ) + #&d(N_1, N_2 )) < E(N_1 , P_j ) + BIL(N_2 , P_j )]이면 노드 N1이 프로세서 [eqn: P_j]에 스케줄될 때 가장 짧은 종료 시간은 노드 N2가(BIL(N2,Pk) + d(N1,N2))를 최소가 되도록 하는 프로세서 Pk에 스케줄될 때이다.

[eqn: &E(N_1, P_j ) + min_k (BIL(N_2 , P_k ) + #&d(N_1 , N_2 )) >= E(N_1 , P_j ) + BIL(N_2 , P_j )]이면 노드 N1이 프로세서 [eqn: P_j]에 스케줄될 때 가장 짧은 종료 시간은 노드 N2가 프로세서 [eqn: P_j]에 스케줄될 때이다. 이것은 BIL의 정의와 같으므로 BIL(Ni,Pj)는 노드 [eqn: N_i]의 [eqn: P_j]에 스케줄될 때 마지막 노드까지의 가장 짧은 종료 시간을 나타낸다.

다음으로 BIL스케줄러는 시작 노드 N1의 BIL값들 중 최소값이 되도록 하는 프로세서 Pk를 선택하면, 최적으로 스케줄되었을 때의 수행 경로 길이를 나타낸다. 다시 말하면, [eqn: min_k ~BIL(N_1 , P_k )]가 최적으로 스케줄된 수행 경로 길이이다. BIL(N1,Pk)는 자식 노드가 어느 프로세서에 스케줄되어야 하는지에 대한 정보를 가지고 있기 때문에 BIL 스케줄러는 노드 N1의 BIL 값 중 최소값을 일단 결정하면 최적의 스케줄을 만들어 낸다. 결국 BIL 스케줄러는 입력 그래프가 선형일 경우 최적의 스케줄 결과를 생성한다. [증명끝]

앞에서의 그림 1의 예는 각 노드가 스케줄될 수 있는 상황과 BIL값이 일치하는 경우이다. 즉 BIL값이 가상의 값을 나타내는 것이 아니라 실제 스케줄 길이를 나타낸다. 그림 4의 다른 예를 살펴보자. 이 예에서 노드 B, C, D의 BIL값은 앞의 예처럼 쉽게 계산할 수 있으므로 자식 노드가 둘 이상인  노드 A에 대해서 살펴보자.

그림 . BIL가정을 만족할 수 없는 예

[eqn: #BIL(A,P0)& = E(A,P0) + #max [&min (BIL(B,P0), #&BIL(B,P1) + d(A,B)), #&min (BIL(C,P0), #&BIL(C,P1) + d(A,C)) ] #= 3 + &max[ min(9,16+2), #&min(7,12+4) ] = 12.]

[eqn: #BIL(A,P1)& = E(A,P1) + #max [&min (BIL(B,P1), #&BIL(B,P0) + d(A,B)), #&min (BIL(C,P1), #&BIL(C,P0) + d(A,C)) ] #= 7 + &max[ min( 9+2, 16),#&min(7+4,12) ] = 18.]

노드 A의 BIL값은 각각 12와 18이므로 가정에 의하면 노드 A는 프로세서 P0에 스케줄될 때 스케줄 길이가 12이고, 프로세서 P1에 스케줄될 때 스케줄 길이가 18이다. 그러나 이 값은 노드 A의 자식 노드인 노드 B와 노드 C 둘 다 가장 이른 시각에 최적의 프로세서인 P0에 스케줄될 것을 상정하고 계산한 값이므로, 실제 스케줄 시에는 불가능한 수행시간이다. 즉 BIL값이 항상 최단 스케줄 길이를 나타내는 것은 아니라, 최단 스케줄 길이보다 더 짧은 값을 나타내는 경우도 있다.

3.2 노드 선택

스케줄이 진행됨에 따라 GDL과 마찬가지로 스케줄 가능한 노드들의 우선순위를 상황에 따라 바뀌는 동적인 레벨로 정의하도록 한다. 따라서 프로세서 [eqn: P_j]에 대한 노드 [eqn: N_i]의 동적인 레벨 BIM (Best Imaginary Makespan)을 정의한다.

정의 2.

[eqn: BIM(N_i , P_j ) = T(N_i , P_j ) + BIL(N_i , P_j )]

T(Ni ,Pj)는 노드 [eqn: N_i]가 프로세서 [eqn: P_j]에 스케줄 가능한 가장 이른 시각이다.

전체 프로세서 개수가 N개이면 현 시점에서 스케줄 가능한 노드들은 각각의 프로세서마다 하나씩의 총 N개의 BIM값들을 가진다. 현 시점에서 스케줄 가능한 노드들 중에서 스케줄이 최악으로 되는 경우에 성능이 나빠지는 것을 최대한 줄이기 위해서 가장 비관적인 가정 하에서 스케줄될 노드를 선택한다. 스케줄 단계에서 스케줄 가능한 노드의 개수를 k라 하면, 다음과 같은 노드 선택 정책을 취한다.

(i) k<N 인 경우

노드는 최악의 경우에도 k-1번 다른 노드들이 스케줄된 다음 자신이 스케줄될 수 있을 것으로 예상할 수 있다. 그래서 노드의 BIM값을 오름차순으로 정렬한 후 노드 내에서 k번째 BIM값을 각각의 노드끼리 비교하여 가장 큰 BIM값을 가지는 노드를 선택한다. 만일 이때 노드의 k번째 BIM값이 무한대인 경우 가장 큰 유한한 BIM값이 k번째 BIM값으로 대신 사용된다. 왜냐하면 그 노드는 무한대의 BIM값을 가지는 프로세서에는 스케줄이 되지 않을 것이기 때문이다. 그렇기 때문에 유한한 값을 가지고 서로 비교해야 한다.

(ii) k[eqn: >=]N 인 경우

노드는 단지 N개의 BIM값을 가질 수 있으므로, 오름차순으로 정렬했을 때 N번째 BIM값(가장 큰 BIM값)을 가지고 스케줄 가능한 노드들끼리 비교한다. 물론 앞의 경우와 마찬가지로 N번째 값이 무한대인 경우에는 가장 큰 유한한 BIM값이 대신 사용된다.

(i)(ii)의 경우에 만일 두개 이상의 노드들이 같은 BIM값을 가진다면 동점 제거 정책을 재귀적으로 수행한다. 즉 노드들의 i번째 BIM값이 같았다면 같은 노드들의 (i-1)번째 BIM값을 서로 비교한다.

3.3 프로세서 선택

노드 선택 단계 후 다음 단계로 행해야 하는 것은 그 노드에 맞는 최적의 프로세서를 선택하는 것이다. 가장 작은 BIM 값을 가지는 프로세서로 노드를 스케줄하는 것이 당연하지만, 이러한 선택이 최선은 아니다. 왜냐하면, BIM을 계산할 때에 노드의 통신 시간이 전혀 감추어지지 않는 것으로 가정하였기 때문이다. 현 시점에서 스케줄 가능한 노드의 개수가 충분히 많다고 하면 노드와 그 자식 노드 사이의 통신 시간은 다른 스케줄 가능한 노드들에 의해 감춰질 수 있다. 그래서 입력 그래프의 병렬성이 높은 경우, 즉 현 시점에서 스케줄 가능한 노드의 개수가 많은 경우에는 프로세서가 노드를 수행하는데 걸리는 수행시간이 통신 시간보다 더 중요한 요소가 된다.

그림 . 그래프 병렬성의 효과를 나타내는 예

그림 5 (a)의 예를 생각해 보자. 첫 단계에서 노드 A가 선택된 후 BIM 값이 가장 작은 프로세서 P0에 스케줄된다. 그러나 이러한 결정은 그림 5 (b)에서 보듯 좋은 스케줄 결과가 아니다. 노드 A가 선택되었을 때, 현 시점에서 스케줄 가능한 노드의 개수는 4개이고, 프로세서 개수는 2개이다. 그러므로 노드 A의 자식 노드가 선택되기 전에, 현 시점에서 스케줄 가능한 노드들의 BIM값이 크게 다르지 않다는 가정 하에서, 각 프로세서당 평균 2개의 노드가 스케줄될 것이다. 이것은 BIL의 계산에서 고려한 노드 A와 노드 E사이의 통신 시간이 사라지는 효과를 낸다. 다시 말하면 BIL 스케줄러는 그래프 병렬성에 대해 비관적이다. 그래서 입력 그래프의 병렬성을 고려한 BIM을 다시 정의해야 한다.

정의 3.

[eqn: &BIM^* (N_i , P_j ) = T(N_i ,P_j ) + BIL(N_i , P_j )#&+ E(N_i , P_j )* max [ k over N - 1 , 0 ]]

개선된 BIM값은 기존의 BIM값에 새로운 요소인 [eqn: E(N_i , P_j ) * max [ k over N -1, 0]]가 추가되었다. 이 요소는 프로세서를 선택할 때 수행 시간에 더 큰 비중을 주겠다는 의미인데, 병렬성이 증가할수록 더 큰 비중을 주기 위해서 [eqn: max[ k over N -1, 0]]값을 곱했다. 여기서 k는 현 상황에서 스케줄 가능한 노드의 개수를 나타내고, [eqn: N]은 프로세서 개수를 나타낸다. [eqn: k over N]는 프로세서당 노드가 스케줄되는 평균 개수이므로, 현재 스케줄되는 노드와 그 노드의 자식 노드 사이에는 평균 [eqn: k over N -1]개의 다른 노드들이 들어갈 수 있다. 따라서 이 만큼 수행 시간에 더 큰 비중을 주도록 한 것이다.

개선된 BIM 값을 사용하여 그림 5 (c)에서 보듯이 더 나은 스케줄 결과를 얻을 수 있다.

두개 이상의 프로세서가 같은 BIM* 값을 가진다면, BIL 스케줄러는 동점 제거 정책을 사용해야 한다. 이 경우 다른 노드들의 그 프로세서에서  BIM 값의 합이 가장 크게 되도록 하는 프로세서를 선택한다. 왜냐하면 그 프로세서에서 다른 노드들의 BIM 값이 크다고 하는 것은 다른 노드들은 그 프로세서에 스케줄되지 않는 것을 선호한다는 것을 나타내기 때문이다.

3.4 알고리즘의 복잡도

이 BIL 스케줄러의 전체적인 알고리즘이 그림 6에 나타나 있다. 각 단계별 시간 복잡도를 계산하면 다음과 같다. 단 전체 노드의 개수를 n, 프로세서 개수를 p라 한다.

그림 . BIL 스케줄 알고리즘

1. 모든 노드, 모든 프로세서에 대해 BIL값을 계산한다. 자식 노드의 가장 작은 BIL값을 가지는 프로세서는 이미 계산되어 있다. 최대값을 찾기 위해 n번 계산이 필요하다.  [ [eqn: O( n^2 * p)] ]

2. 스케줄 가능한 노드에 대해서 BIM값을 계산한다. [ [eqn: O(n*p)] ]

3. 노드 선택 정책을 통해서 노드를 선택한다. 이 단계에서 정렬이 필요하다.      [ [eqn: O(n*p log p)] ]

4. 선택된 노드의 BIM*값을 계산한다.    [ [eqn: O(1)] ]

5. 프로세서를 선택한다. 동점 제거 정책이 필요하다. [ [eqn: O(n*p + p log p)] ]

6. 선택된 노드를 선택한 프로세서로 스케줄한다. [ [eqn: O(1)] ]

단계 2에서 단계 6까지는 각 노드에 대해서 수행되는 것이므로, 전제 시간 복잡도는 다음과 같다.

[eqn: &O(n^2 p + n(np + np log p + np + p log p +2 ) ) #&= O(n^2 p log p )]

이것은 GDL의 O([eqn: n^3 p])보다 낮은 시간 복잡도를 가진다. 그러나 실제 실험을 통해서는 GDL과 BIL이 비슷한 수행 시간을 나타내는데 이것은 BIL의 시간 복잡도의 차수는 GDL의 시간 복잡도의 차수보다 낮지만, BIL의 시간 복잡도의 계수가 GDL에 비해 크기 때문이다. 그리고, 시간 복잡도 분석에서는 최악의 상황을 가정하지만, 실제 입력 그래프에서는 그렇지 않기 때문이다. 예를 들어, 시간 복잡도 분석에서는 자식 노드 수를 [eqn: n]으로, 노드 선택 시에 스케줄 가능한 노드 수를 [eqn: n]으로 가정했지만, 실제 그래프에서는 이보다 훨씬 작은 값을 가지기 때문에 GDL과 BIL의 수행 시간이 비슷하게 나타나는 것이다.

4. 모의 실험

BIL 스케줄러의 성능을 측정하기 위해서 다양한 개수의 노드와 프로세서에 대해 다양한 정도의 병렬성을 가지는 APG를 무작위로 만들었다. 즉 30, 50, 100, 150, 200, 250, 300, 350, 400, 500개의 노드를 2, 3, 5, 7, 10, 12, 15, 20, 25, 30개의 프로세서 상에  스케줄하였다. 여기서 각 노드와 프로세서의 쌍에 대해 서로 다른 10개의 그래프를 무작위로 만들어 모의 실험을 진행하며 그의 평균값을 취하였다. 또한, 통신 시간과 노드들의 평균 수행 시간의 비를 0.5, 1, 2로 변화시키면서 실험을 한 결과 그림 7에 보듯이 GDL과 비교하여 개선된 스케줄 결과를 얻었다. 단[eqn: rm bar C]는 통신 시간의 평균값을 의미하고, [eqn: rm bar E]는 노드의 수행 시간의 평균값을 의미한다. 예를 들어 [eqn: bar C = 0.5 bar E]는 통신 시간이 평균 수행 시간의 반이라는 것을 나타낸다.

그림 7. GDL 스케줄러에 대한 BIL 스케줄러의 성능 개선

[eqn: rm (a) it bar C = 0.5 bar E ~ rm (b) it bar C = bar E ~ rm (c) it bar C = 2 Bar E]

BIL 스케줄러의 성능은 노드의 수가 많은 경우, 프로세서의 개수가 2보다 큰 경우에 좋다. 노드의 수가 증가할 수록 성능이 좋아지는 것은, 노드의 수가 증가하면 그래프의 깊이도 깊어지기 때문에 전체적인 정보가 매우 중요한데, BIL 스케줄러가 전체적인 정보를 가지고 매우 멀리 떨어져 있는 노드도 고려하여 스케줄 하기 때문이다. 그리고 프로세서가 2보다 큰 경우에 좋은 성능을 내는 것은 GDL은 스케줄하는데 있어서 전체적인 제약(즉 자원이 없는 경우)을 고려하기 위해 단지 노드당 두개의 프로세서만을 검사하기 때문이다.

5. 결론

본 논문에서는 이질 수행 시간을 가지는 프로세서를 위한 Best-Imaginary-Level (BIL) 스케줄링이라 일컫는 비선점 정적 스케줄링 휴리스틱을 제안하였다. 제안된 스케줄링 방법은 입력 그래프의 모양이 직선이 경우 최적의 스케줄링 결과를 생성함을 증명하였다. BIL 스케줄링은 general dynamic level (GDL) 스케줄링이라 불리는 현존하는 스케줄링 방법에 비해 다양한 형태의 무작위로 생성된 입력 그래프에 대해 약 20%의 성능 향상을 보였다.

이로써 제안된 스케줄링은 네트워크 컴퓨팅에서부터 하드웨어/소프트웨어 통합 설계(codesign)에 이르기까지 다양한 응용에 적용될 수 있을 것으로 기대한다. 그리고 더 일반적인 문제에 이러한 스케줄링 기법을 적용하기 위해 반복문을 고려한 스케줄링 방법으로 확장하려고 한다. 마지막으로 이러한 스케줄링 기법은 현재 구축 중에 있는 이질 시스템에서 입력 프로그램 그래프를 수행하는 환경에 구현하였다.

참고문헌

[1] M.R. Gary and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., 1979.

[2] W.H. Kohler and K. Steiglitz, "Characterization and Theorectical Comparison of Branch-and-Bound Algorithms for Permutation Problems," J. ACM, vol.21, no. 1, pp. 140-156, Jan. 1974.

[3] T.G. Lewis and H. El-Rewini, Introduction to Parallel Computing, New York: Prentice Hall, 1992.

[4] T.L. Adam, K. Chandy and J. Dickson, □Comparison of List Scheduling for Parallel Processing Systems," Comm. ACM, vol. 17, no. 12, pp.685-690, Dec.1974.

[5] E.G. Coffman, Computer and Job-Shop Scheduling Theory. New York: Wiley, 1976.

[6] M.Y. Wu and D.D. Gajski, "Hypertool: A Programming Aid for Message-Passing Systems," IEEE Trans. Parallel and Distributed Systems, vol. 1, no. 3, pp. 330-343, July 1990.

[7] J.J. Hwang, Y.C. Chow, F.D. Anger, and C.Y. Lee, "Scheduling Precedence Graphs in Systems with Interprocessor Communication Times," SIAM J. Computing, vol. 18, no. 2, pp. 244-257, Apr. 1989.

[8] G.C. Sih and E.A. Lee, "A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures," IEEE Trans. parallel and distributed systems, vol 4, no.2, pp. 175-187, Feb. 1993.

[9] Y.-K. Kwok and I. Ahmad, "Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors," IEEE Trans. parallel and distributed systems, vol 7, no. 5, pp.506-521, May. 1996.

부록

그림 1에 대한 GDL스케줄링 과정

	P0	P1	E*	SL	[eqn: Delta_P0]	[eqn: Delta_P1]
A	1	2	1	4	0	-1
B	2	2	2	3	0	0
C	[eqn: Inf]	1	1	1	-[eqn: Inf]	0

먼저 표와 같이 정적인 값을 계산한다.

스케줄 가능한 노드는 A이므로 A에 대해서 동적인 레벨을 계산한다.

[eqn: DL_1 (A,P0) &= 4 - 0 + 0 = 4# DL_1 (A, P1) &= 4 - 0 - 1 = 3]

[eqn: F(A,B,P0) &= 10 + 2 = 12 # F(A,B,P1) &= 10 + 2 = 12]

[eqn: DC(A,P0) &= 2 - min(2, 12) = 0# DC(A,P1) &= 2 - min(2, 12) = 0]

[eqn: DL_2 (A, P0) &= 4 + 0 = 4 # DL_2 (A, P1) &= 3 + 0 = 3]

[eqn: C(A) &= max_j DL(A,P_j ) - max _{j != k} DL(A,P_k )# &=4 - 3 = 1]

[eqn: GDL(A) = 4 +1 = 5]

노드 A가 선택된 다음[eqn: DL_2]값을 살펴보면 A가 P0에 스케줄된다.

다음으로 노드 B가 스케줄 가능해서 B의 동적 레벨을 구한다.

[eqn: DL_1 (B,P0) &= 3 - 1 + 0 &= 2# DL_1 (B, P1) &= 3 - 11 + 0 &=-8]

[eqn: F(B,C,P0) &= 12 + 2 = 14 # F(B,C,P1) &= 12 + inf = INF]

[eqn: DC(B,P0) &= 1 - min(inf, 14) &= -12# DC(B,P1) &= 1 - min(1, inf) &= 0]

[eqn: DL_2 (B, P0) &= 2 + (-12) = -10 # DL_2 (B, P1) &= -8 + 0 = -8]

[eqn: E(B,P0) = E(B,P1)]이므로 [eqn: C(B) = 0]이다.

노드 B는 프로세서 P1에 스케줄된다.

노드 C에 대한 동적인 레벨은 다음과 같다.

[eqn: DL_1 (C,P0) &= 1 - 25 + (-inf) &= -inf# DL_1 (C, P1) &= 1 - 13 + 0 &=-12]

노드 C는 자식 노드를 가지고 있지 않으므로 [eqn: DL_2 = DL_1]이다.  노드 C는 프로세서 P1에 스케줄된다. 최종적으로 그림 2와 같은 스케줄 결과를 얻을 수 있다.