Energy Aware Scheduling

1. Introduction

에너지 인식 스케줄링(Energy Aware Scheduling, 또는 EAS)을 통해 스케줄러는 자신의 결정이 CPU가 소비하는 에너지에 미치는 영향을 예측할 수 있습니다. EAS는 CPU의 에너지 모델(EM)을 통해 각 작업에 필요한 에너지 효율적인 CPU를 선택하고 처리량에 미치는 영향을 최소화합니다. 이 문서는 EAS의 작동 방식과 그 배경에 있는 주요 설계 결정 사항 및 실행에 필요한 세부 사항에 대한 소개를 제공하는 것을 목표로 합니다.

더 이상 진행하기 전에 작성 시 다음 사항에 유의하시기 바랍니다:

/!\ EAS does not support platforms with symmetric CPU topologies /!\

 

EAS는 이기종 CPU 토폴로지(예: Arm big.Little)에서만 작동합니다. 스케줄링을 통해 에너지를 절약할 수 있는 잠재력이 가장 크기 때문입니다.

EAS에서 사용하는 실제 전자파는 스케줄러에 의해서가 아니라 전용 프레임워크에 의해서 관리됩니다. 이 프레임워크와 그것이 제공하는 것에 대한 자세한 내용은 그 문서를 참조하기 바랍니다  (see Energy Model of devices).

 

2. Background and Terminology

처음부터 확실히 하기 위해서:

• energy = [joule] (resource like a battery on powered devices)
• power = energy/time = [joule/second] = [watt]

EAS의 목표는 에너지를 최소화하는 동시에 작업을 수행하는 것입니다. 즉, 우리는 다음을 극대화하고자 합니다:

performance [inst/s]
--------------------
    power [W]

이는 다음을 최소화하는 것과 같습니다:

energy [J]
-----------
instruction

그래도 '좋은' 성능을 얻으면서 말입니다. 이는 근본적으로 스케줄러의 현재 성능 전용 목표에 대한 대안적 최적화 목표입니다. 이 대안은 에너지 효율과 성능이라는 두 가지 목표를 고려합니다.

EM을 도입하는 배경에는 일부 플랫폼에만 긍정적인 영향을 미칠 수 있는 에너지 절약 기술을 맹목적으로 적용하지 않고 스케줄러가 결정의 영향을 평가할 수 있도록 하는 것이 있습니다. 동시에 EM은 스케줄러 지연 시간에 미치는 영향을 최소화하기 위해 가능한 한 단순해야 합니다.

간단히 말해서, EAS는 CFS 작업이 CPU에 할당되는 방식을 바꿉니다. 스케줄러가 작업을 실행할 위치를 결정할 때가 되면, EM은 여러 훌륭한 CPU 후보들 사이의 관계를 끊고 시스템의 처리량을 손상시키지 않으면서 최고의 에너지 소비를 할 것으로 예측되는 것을 고르는 데 사용됩니다. EAS가 예측하는 것은 플랫폼의 토폴로지에 대한 지식의 특정 요소에 의존하는데, 여기에는 CPU의 '용량'과 각각의 에너지 비용이 포함됩니다.

 

3. Topology information

EAS는 'capacity'라는 개념을 사용하여 계산 처리량이 다른 CPU를 구분합니다. CPU의 'capacity'는 시스템에서 가장 성능이 뛰어난 CPU와 비교하여 최고 주파수로 실행할 때 흡수할 수 있는 작업량을 나타냅니다. capacity 값은 1024 범위에서 정규화되며 PELT(Per-Entity Load Tracking) 메커니즘으로 계산된 작업 및 CPU의 활용 신호와 유사합니다. EAS는 capacity와 활용도 값 덕분에 작업/CPU의 크기를 추정하고 성능 대 에너지 트레이드오프를 평가할 때 이를 고려할 수 있습니다. CPU의 용량은 arch_scale_cpu_capacity() 콜백을 통해 arch-specific 코드를 통해 제공됩니다.

EAS가 사용하는 나머지 플랫폼 지식은 EM(Energy Model) 프레임워크에서 직접 읽습니다. 플랫폼의 EM은 시스템의 '성능 도메인'당 전력 비용 테이블로 구성됩니다(성능 도메인에 대한 자세한 내용은 디바이스의 에너지 모델 참조).

스케줄러는 스케줄링 도메인이 구축되거나 재구축될 때 토폴로지 코드의 EM 개체에 대한 참조를 관리합니다. 각 루트 도메인(rd)에 대해 스케줄러는 현재 rd->span과 교차하는 모든 성능 도메인의 단일 링크된 목록을 유지합니다. 목록의 각 노드는 EM 프레임워크에서 제공하는 구조 em_perf_domain에 대한 포인터를 포함합니다.

배타적인 CPU 집합 구성에 대응하기 위해 목록은 루트 도메인에 첨부됩니다. 배타적인 CPU 집합의 경계가 성능 도메인의 경계와 반드시 일치하는 것은 아니기 때문에, 다른 루트 도메인의 목록은 중복 요소를 포함할 수 있습니다.

 

Example 1.

Let us consider a platform with 12 CPUs, split in 3 performance domains (pd0, pd4 and pd8), organized as follows:

 

예 1.
다음과 같이 구성된 3개의 성능 도메인(pd0, pd4 및 pd8)으로 분할된 12개의 CPU가 있는 플랫폼을 생각해 보겠습니다:

CPUs:   0 1 2 3 4 5 6 7 8 9 10 11
PDs:   |--pd0--|--pd4--|---pd8---|
RDs:   |----rd1----|-----rd2-----|

이제 userspace가 두 개의 배타적인 CPU 집합으로 시스템을 분할하기로 결정했기 때문에 각각 6개의 CPU를 포함하는 두 개의 독립적인 루트 도메인이 생성되었다고 생각해 보십시오. 위 그림에서 두 루트 도메인은 rd1과 rd2로 표시됩니다. pd4는 rd1과 rd2와 모두 교차하므로, 이들 각각에 연결된 링크된 목록 '->pd'에 표시됩니다:

• rd1->pd: pd0 -> pd4
• rd2->pd: pd4 -> pd8

스케줄러는 pd4에 대해 중복 리스트 노드를 2개씩 생성합니다(각각의 리스트에 대해 하나씩). 하지만 둘 다 EM 프레임워크의 동일한 공유 데이터 구조에 대한 포인터를 보유할 뿐입니다.

 

이러한 목록에 대한 액세스는 핫플러그 및 기타 항목과 동시에 발생할 수 있으므로 스케줄러에 의해 조작되는 나머지 토폴로지 구조와 마찬가지로 RCU에 의해 보호됩니다.

또한 EAS는 정적 키(sched_energy_present)를 유지하며, 이 키는 적어도 하나의 루트 도메인이 EAS가 시작할 모든 조건을 충족할 때 활성화됩니다. 이러한 조건은 6절에 요약되어 있습니다.

 

4. Energy-Aware task placement

EAS는 CFS Task Wake-up Balancing 코드를 재정의합니다. 이것은 플랫폼의 EM과 PELT 신호를 사용하여 Wake-up Balancing 중에 에너지 효율적인 대상 CPU를 선택합니다. EAS가 활성화되면 select_task_rq_fair()가 find_energy_efficient_cpu()를 호출하여 배치 결정을 수행합니다. 이 함수는 주파수를 가장 낮게 유지할 수 있는 CPU이기 때문에 각 성능 도메인에서 가장 높은 예비 용량(CPU capacity - CPU 사용률)을 가진 CPU를 찾습니다. 그런 다음, 이 함수는 작업을 수행할 때 prev_cpu에 두는 것보다 작업을 수행할 때 에너지를 절약할 수 있는지 확인합니다.

 

find_energy_efficient_cpu()는 comput_energy()를 사용하여 웨이크업 작업이 마이그레이션된 경우 시스템에서 소비되는 에너지를 추정합니다. comput_energy()는 CPU의 현재 사용 환경을 살펴보고 작업 마이그레이션을 '시뮬레이션'하도록 조정합니다. EM 프레임워크는 주어진 사용 환경에 대해 각 성능 도메인의 예상 에너지 소비를 계산하는 em_pd_energy() API를 제공합니다.

 

에너지 최적화 작업 배치 결정의 예는 아래에 자세히 나와 있습니다.

 

예 2.
두 개의 CPU로 구성된 독립적인 성능 도메인이 두 개인 (가짜) 플랫폼을 생각해 보겠습니다. CPU0와 CPU1은 작은 CPU이고 CPU2와 CPU3는 큽니다.

스케줄러는 util_avg = 200이고 prev_cpu = 0인 작업 P를 배치할 위치를 결정해야 합니다.

CPU의 현재 사용 환경은 아래 그래프에 나와 있습니다. CPU 0-3의 util_avg는 각각 400, 100, 600 및 500입니다. 각 성능 도메인에는 3개의 OPP(Operating Performance Point)가 있습니다. 각 OPP와 관련된 CPU 용량과 전력 비용은 에너지 모델 테이블에 나열되어 있습니다. P의 util_avg는 아래 그림에서 'PP'로 표시됩니다:

CPU util.
 1024                 - - - - - - -              Energy Model
                                          +-----------+-------------+
                                          |  Little   |     Big     |
  768                 =============       +-----+-----+------+------+
                                          | Cap | Pwr | Cap  | Pwr  |
                                          +-----+-----+------+------+
  512  ===========    - ##- - - - -       | 170 | 50  | 512  | 400  |
                        ##     ##         | 341 | 150 | 768  | 800  |
  341  -PP - - - -      ##     ##         | 512 | 300 | 1024 | 1700 |
        PP              ##     ##         +-----+-----+------+------+
  170  -## - - - -      ##     ##
        ##     ##       ##     ##
      ------------    -------------
       CPU0   CPU1     CPU2   CPU3

 Current OPP: =====       Other OPP: - - -     util_avg (100 each): ##

find_energy_efficient_cpu()는 먼저 두 성능 도메인에서 최대 예비 용량을 가진 CPU를 찾습니다. 이 예에서는 CPU1과 CPU3입니다. 그런 다음 P가 두 시스템 중 하나에 배치되어 있으면 시스템의 에너지를 추정하고 CPU0에 P를 두는 것보다 에너지를 절약할 수 있는지 확인합니다. EAS는 OPP가 활용률을 따른다고 가정합니다(이 항목에 대한 자세한 내용은 6절 참조).

 

Case 1. P is migrated to CPU1:

1024                 - - - - - - -

                                      Energy calculation:
 768                 =============     * CPU0: 200 / 341 * 150 = 88
                                       * CPU1: 300 / 341 * 150 = 131
                                       * CPU2: 600 / 768 * 800 = 625
 512  - - - - - -    - ##- - - - -     * CPU3: 500 / 768 * 800 = 520
                       ##     ##          => total_energy = 1364
 341  ===========      ##     ##
              PP       ##     ##
 170  -## - - PP-      ##     ##
       ##     ##       ##     ##
     ------------    -------------
      CPU0   CPU1     CPU2   CPU3

 

Case 2. P is migrated to CPU3:

1024                 - - - - - - -

                                      Energy calculation:
 768                 =============     * CPU0: 200 / 341 * 150 = 88
                                       * CPU1: 100 / 341 * 150 = 43
                              PP       * CPU2: 600 / 768 * 800 = 625
 512  - - - - - -    - ##- - -PP -     * CPU3: 700 / 768 * 800 = 729
                       ##     ##          => total_energy = 1485
 341  ===========      ##     ##
                       ##     ##
 170  -## - - - -      ##     ##
       ##     ##       ##     ##
     ------------    -------------
      CPU0   CPU1     CPU2   CPU3

Case 3. P stays on prev_cpu / CPU 0:

1024                 - - - - - - -

                                      Energy calculation:
 768                 =============     * CPU0: 400 / 512 * 300 = 234
                                       * CPU1: 100 / 512 * 300 = 58
                                       * CPU2: 600 / 768 * 800 = 625
 512  ===========    - ##- - - - -     * CPU3: 500 / 768 * 800 = 520
                       ##     ##          => total_energy = 1437
 341  -PP - - - -      ##     ##
       PP              ##     ##
 170  -## - - - -      ##     ##
       ##     ##       ##     ##
     ------------    -------------
      CPU0   CPU1     CPU2   CPU3

이 계산으로 볼 때 Case 1의 총 에너지가 가장 낮습니다. 그래서 CPU 1이 에너지 효율적인 관점에서 가장 적합한 후보입니다.

 

큰 CPU는 일반적으로 작은 CPU보다 더 많은 전력을 필요로 하기 때문에 작업이 작은 CPU에 맞지 않을 때 주로 사용됩니다. 그러나 작은 CPU가 큰 CPU보다 항상 더 에너지 효율적인 것은 아닙니다. 예를 들어 어떤 시스템에서는 작은 CPU의 높은 OPP가 큰 CPU의 낮은 OPP보다 에너지 효율이 낮을 수 있습니다. 따라서 작은 CPU가 특정 시점에 충분한 활용도를 갖게 된다면, 비록 작은 쪽에 맞더라도 에너지를 절약하기 위해 그 순간 깨우는 작은 작업이 큰 쪽에서 실행하는 것이 더 나을 수 있습니다.

 

그리고 큰 CPU의 모든 OPP가 작은 CPU의 OPP보다 에너지 효율이 낮더라도 작은 작업에 큰 CPU를 사용하면 특정 조건에서는 여전히 에너지를 절약할 수 있습니다. 실제로 작은 CPU에 작업을 할당하면 전체 성능 도메인의 OPP가 증가할 수 있으며, 이로 인해 이미 실행 중인 작업의 비용이 증가합니다. 웨이크업 작업을 큰 CPU에 할당하면 작은 CPU에서 실행하는 경우보다 자체 실행 비용이 더 높지만 OPP가 낮은 상태로 계속 실행되는 작은 CPU의 다른 작업에는 영향을 미치지 않습니다. 따라서 CPU가 소모하는 총 에너지를 고려할 때 큰 코어에서 한 작업을 실행하는 추가 비용은 다른 모든 작업의 작은 CPU에서 OPP를 높이는 비용보다 작을 수 있습니다.

 

위의 예들은 시스템의 모든 CPU에서 서로 다른 OPP에서 실행되는 비용을 모른 채 일반적인 방법으로 그리고 모든 플랫폼에서 올바르게 실행하는 것은 거의 불가능할 것입니다. EAS는 EM 기반 설계 덕분에 많은 문제 없이 올바르게 대처해야 합니다. 그러나 활용도가 높은 시나리오의 경우 처리량에 미치는 영향을 최소화하기 위해 EAS는 '과다 활용도'라는 또 다른 메커니즘도 구현합니다.

 

5. Over-utilization

일반적인 관점에서 EAS가 가장 도움이 되는 사용 사례는 가벼운/중간 CPU 사용률과 관련된 사용 사례입니다. 긴 CPU 바인딩 작업을 실행할 때마다 사용 가능한 모든 CPU 용량이 필요하며, 처리량을 크게 손상시키지 않으면서 에너지를 절약할 수 있는 스케줄러가 할 수 있는 일은 많지 않습니다. CPU는 EAS로 인해 성능이 저하되는 것을 방지하기 위해 컴퓨팅 용량의 80% 이상에서 사용되는 즉시 '과다 사용'으로 플래그가 지정됩니다. 루트 도메인에서 초과 사용되는 CPU가 없는 한 로드 밸런싱이 비활성화되고 EAS는 웨이크업 밸런싱 코드를 재정의합니다. 처리량을 손상시키지 않고 수행할 수 있다면 EAS는 다른 시스템보다 에너지 효율이 가장 높은 CPU를 더 많이 로드할 가능성이 높습니다. 따라서 로드 밸런싱 장치가 비활성화되어 EAS가 발견한 에너지 효율적인 작업 배치를 중단하지 않도록 합니다. 80% 티핑포인트 미만이면 시스템이 초과 사용되지 않을 때 안전하게 실행할 수 있습니다:

 

a. 모든 CPU에서 'idle' 시간이 발생하므로 EAS가 사용하는 활용 신호는 시스템의 다양한 작업의 '크기'를 정확하게 나타낼 가능성이 높습니다;

b. 모든 작업은 좋은 값과 상관없이 이미 충분한 CPU 용량을 제공해야 합니다;

c. 여유 용량이 있으므로 모든 작업을 정기적으로 차단/sleeping해야 하며 기상 시 균형을 유지하는 것으로 충분합니다.

 

하나의 CPU가 80% 티핑 포인트를 넘어서는 순간 위의 세 가지 가정 중 적어도 하나는 잘못된 것이 됩니다. 이 시나리오에서는 전체 루트 도메인에 대해 '과다 활용' 플래그가 올라가고 EAS가 비활성화되며 로드 밸런싱이 다시 활성화됩니다. 이렇게 하면 스케줄러는 CPU 바인딩 조건에서 웨이크업 및 로드 밸런싱을 위해 로드 기반 알고리즘에 다시 적용됩니다. 이를 통해 작업의 좋은 값을 더 잘 이해할 수 있습니다.

 

과잉 사용의 개념은 주로 시스템에 유휴 시간이 있는지 여부를 감지하는 것에 달려 있기 때문에 (IRQ뿐만 아니라) 더 높은 (CFS보다) 스케줄링 클래스에 의해 '도용된' CPU 용량을 고려해야 합니다. 따라서 과잉 사용의 감지는 CFS 작업뿐만 아니라 다른 스케줄링 클래스 및 IRQ에서도 사용되는 용량을 설명합니다.

 

6. Dependencies and requirements for EAS

Energy Aware Scheduling은 특정 하드웨어 속성을 가진 시스템의 CPU와 활성화되는 커널의 다른 기능에 따라 달라집니다. 이 섹션에서는 이러한 종속성을 나열하고 종속성을 충족하는 방법에 대한 힌트를 제공합니다.

 

6.1 - Asymmetric CPU topology

서론에서 언급한 것처럼 EAS는 현재 비대칭 CPU 토폴로지를 가진 플랫폼에서만 지원됩니다. 이 요구 사항은 스케줄링 도메인이 구축될 때 SD_ASYM_CPUCAPACITY_FULL 플래그가 있는지 찾아 런타임에 확인합니다

 

sched_domain 계층에서 이 플래그를 설정하려면 용량 인식 스케줄링을 참조하십시오

 

EAS는 SMP와 근본적으로 호환되지 않지만 SMP 플랫폼에 대한 상당한 비용 절감은 아직 관찰되지 않았습니다. 이 제한은 추후에 다른 방법으로 입증될 경우 수정될 수 있습니다.

 

6.2 - Energy Model presence

EAS는 플랫폼의 EM을 사용하여 스케줄링 결정이 에너지에 미치는 영향을 추정합니다. 따라서 EAS를 시작하려면 플랫폼에서 EM 프레임워크에 전력 비용 테이블을 제공해야 합니다. 이를 위해서는 장치의 에너지 모델에 있는 독립적인 EM 프레임워크의 문서를 참조하십시오.

또한 EAS를 시작하기 위해서는 EM이 등록된 후에 스케줄링 도메인을 다시 구축해야 합니다.

EAS는 EM을 사용하여 에너지 사용량을 예측하기 때문에 작업 배치에 대한 가능한 옵션을 확인할 때 차이에 더 중점을 둡니다. EAS의 경우 EM 전력 값이 밀리와트로 표시되는지 '추상적인 척도'로 표시되는지는 중요하지 않습니다.

 

6.3 - Energy Model complexity

EAS는 PD/OPP/CPU 수에 복잡도 제한을 두지 않고 에너지 추정 중 오버플로를 방지하기 위해 CPU 수를 EM_MAX_NUM_CPUS로 제한합니다.

 

6.4 - Schedutil governor

EAS는 CPU의 에너지 사용량을 추정하기 위해 가까운 미래에 어떤 OPP가 실행될지 예측하려고 합니다. 이를 위해서는 CPU의 OPP가 사용률을 따른다고 가정합니다.

실제로 이 가정의 정확성에 대해 확실한 보장을 제공하는 것은 매우 어렵지만(예를 들어 하드웨어가 지시한 대로 하지 않을 수 있기 때문에), 다른 CPUFreq 지사와 달리 적어도 활용 신호를 사용하여 계산된 주파수는 스케쥴틸입니다. 결과적으로 EAS와 함께 사용할 수 있는 유일한 정상적인 지사는 스케쥴틸인데, 왜냐하면 EAS는 주파수 요청과 에너지 예측 사이에 어느 정도의 일관성을 제공하는 유일한 지사이기 때문입니다.

EAS를 스케줄 이외의 다른 governor와 함께 사용하는 것은 지원되지 않습니다.

 

6.5 Scale-invariant utilization signals

CPU와 모든 성능 상태에 대해 정확한 예측을 하기 위해 EAS는 주파수 불변 및 CPU 불변 PELT 신호가 필요합니다. 이들은 아키텍처 정의 arch_scale {cpu,freq}_capacity() 콜백을 사용하여 얻을 수 있습니다.

이 두 가지 콜백을 구현하지 않는 플랫폼에서 EAS를 사용하는 것은 지원되지 않습니다.

 

6.6 Multithreading (SMT)

현재 형태의 EAS는 SMT 인식 기능이 없으며 멀티쓰레드 하드웨어를 활용하여 에너지를 절약할 수 없습니다. EAS는 스레드를 독립적인 CPU로 간주하므로 실제로 성능과 에너지 모두에 역효과를 낼 수 있습니다.

SMT의 EAS는 지원되지 않습니다.