Conditionally Optimal Task Parallelization for Global EDF on Multi-core Systems

1. 서론: 병렬화 자유도가 있는 RTOS의 새로운 문제 정의

최근의 OpenCL이나 OpenMP와 같은 병렬 프로그래밍 프레임워크는 하나의 작업(task)을 여러 방식으로 병렬화할 수 있는 "parallelization freedom"을 제공합니다. 그러나 G-EDF(Global Earliest Deadline First) 스케줄링 하에서는 어떤 병렬화 수준이 가장 좋을지 결정하기가 매우 어렵습니다. 이 논문은 각 작업의 병렬화 수준을 최적으로 설정하여 전체 작업 집합이 마감 시간(deadline)을 지킬 수 있도록 만드는 문제를 정의하고, 이를 효율적으로 해결하는 알고리즘을 제안합니다.

---

2. 관련 연구: G-EDF와 Fluid Scheduling 간의 현실성 차이

이전 연구들에서는 PD2, LLREF 같은 fluid scheduling 기반에서 병렬화 자유도를 다뤘지만, 이는 실제 시스템에서 스케줄링 호출 횟수가 너무 많아 비현실적입니다. 반면 G-EDF는 실제 산업 시스템에서 더 널리 쓰이지만, 병렬화 자유도에 대한 연구는 거의 없습니다. 본 논문은 이러한 틈을 메우는 첫 시도입니다.

---

3. 시스템 모델 및 문제 정의: 병렬화 옵션 선택이란?

논문에서는 각 작업을 (Tₖ, Dₖ, Eₖ)로 정의합니다:

• Tₖ: 최소 작업 간 간격
• Dₖ: 상대 마감시간
• Eₖ: 병렬화 수준(Ok)에 따른 각 스레드의 실행 시간 테이블

문제는 다음과 같습니다:

"모든 작업이 마감시간을 지킬 수 있도록 각 작업의 병렬화 옵션 Ok를 어떻게 설정할 것인가?"

---

4. BCL 기반 스케줄러 해석 확장

기존 BCL(Bertogna-Cirinei-Lipari) 해석은 단일 스레드 기준이었는데, 논문은 이를 다중 스레드 병렬화 작업에 맞게 확장합니다.

• Interference: 타 작업으로 인해 실행 못하는 시간
• Tolerance: 해당 작업이 견딜 수 있는 최대 간섭량

BCL 조건은 다음과 같은 형태로 요약됩니다:

Σ interference ≤ m × (Dₖ - 실행시간)

그리고 이를 병렬화된 스레드들에 맞게 일반화합니다.

---

5. 병렬화 자유도의 수학적 성질

병렬화 자유도를 가진 작업 $\tau_k$는 병렬화 옵션 $O_k \in [1, O_{\text{max}}]$에 따라 스레드 수와 실행 시간이 달라지며, 이로 인해 다음 두 가지 값이 변화합니다:

1. Tolerance $W_{\text{tolerance}, \tau_k}(O_k)$
   → 자신이 감당할 수 있는 외부 간섭의 양
2. Interference $W_{\text{interference}, \tau_k,\tau_i}(O_k)$
   → 자신이 다른 작업에게 유발하는 간섭의 양

---

Tolerance

$\tau_k$의 첫 번째 스레드가 마감시간을 지키기 위해 외부로부터 감당할 수 있는 최대 간섭량은 다음과 같이 정의됩니다:

• $e_1^k(O_k)$: 병렬화 옵션 $O_k$ 하에서 가장 긴 스레드 실행 시간
• 나머지 스레드들이 자기 형제에게 주는 bounded workload를 제외한 여유량

병렬화하면 $e_1$이 줄어들고, tolerance는 올라간다.

---

Interference

작업 $\tau_k$가 다른 작업 $\tau_i$의 첫 스레드에 유발하는 간섭량은 다음과 같다:

• 각 스레드가 $\tau_i$의 일정 기간 내에 유발할 수 있는 최악의 간섭량을 합한 값입니다.

병렬화하면 스레드 수가 늘어나므로, interference도 커진다.

---

Properties

Property 1: 대표 스레드만 보면 된다

• Lemma 1: $\tau_k$의 가장 긴 스레드 $\tau_k^1$만 schedulability를 만족하면 모든 형제 스레드도 만족한다.

Property 2: Tolerance는 $O_{k}$에 대해 단조 증가

• Lemma 2:

  $W_{\text{tolerance}, \tau_k}(O_k) < W_{\text{tolerance}, \tau_k}(O_k + 1)$

• 단, 병렬화 오버헤드가 크지 않을 경우. 정확히는 다음 조건이 성립할 때:

  $\alpha(O_k, O_k + 1) = \frac{C_k(O_k+1) - C_k(O_k)}{e_1^k(O_k) - e_1^k(O_k+1)} < m - O_k$

  → 이 조건이면 tolerance는 항상 증가한다.

병렬화하면 실행시간이 작아지고, sibling interference는 상대적으로 작게 증가하므로 net 효과는 tolerance 증가!

---

Property 3: Interference는 Ok에 대해 단조 증가

• Lemma 3:

  $W_{\text{interference}, \tau_k,\tau_i}(O_k) < W_{\text{interference}, \tau_k,\tau_i}(O_k + 1)$

• 이유:

  • 더 많은 스레드가 더 자주 스케줄되어 $\tau_i$의 실행을 막을 수 있음
  • 이로 인해 bounded interference도 증가함

병렬화는 자신에게는 유리하지만, 다른 작업에게는 더 많은 간섭을 유발한다.

---

6. 병렬화 최적 할당 알고리즘: OPOA

이 논문은 이론적 성질을 활용하여 O(n³) 시간에 동작하는 최적 알고리즘 OPOA를 제안합니다. 핵심 아이디어는 다음과 같습니다:

• 초기에는 모든 작업을 단일 스레드로 시작
• 각 작업에 대해 Tolerance ≥ Interference가 될 때까지 병렬화 수준을 1씩 증가
• 최대 병렬화 수준에서도 조건을 못 만족하면 해당 작업은 unschedulable

이러한 단방향적 one-way search 방식은 기존의 조합적 백트래킹보다 훨씬 빠릅니다.

---

7. 실험 결과

• 다양한 병렬화 오버헤드 α 하에서 실험

• Ours는 Max, Single, Random보다 항상 더 좋은 schedulability를 보임

• 특히 Utilization이 높거나 Deadline이 타이트할수록 효과가 더 큼

• Autoware와 Apollo 기반의 자율주행 태스크 구성

• PREEMPT_RT, G-EDF 환경에서 실시간 측정

• Single은 긴 작업들에서 deadline miss가 많고,

• Max는 짧은 작업들이 간섭으로 인해 deadline miss

• Ours만 모든 작업에서 deadline 만족

---

8. 결론 및 향후 연구 방향

이 논문은 병렬화 자유도와 G-EDF 스케줄링을 결합한 최초의 최적화 연구로, 이론과 실험 모두에서 효과를 증명합니다. 향후에는 다음과 같은 확장이 계획되어 있습니다:

• DAG 기반 Task 모델로의 확장
• 다른 schedulability analysis (RTA 등)로의 확장
• 온라인 시스템에서의 적용