짧은 대답

풀의 청크 크기 알고리즘은 휴리스틱입니다. 풀의 방법에 채우려는 상상할 수있는 모든 문제 시나리오에 대한 간단한 솔루션을 제공합니다. 결과적으로 특정 시나리오에 대해 최적화 할 수 없습니다 .

알고리즘은 순진한 접근 방식보다 약 4 배 더 많은 청크로 반복 가능 항목을 임의로 분할합니다. 더 많은 청크는 더 많은 오버 헤드를 의미하지만 스케줄링 유연성이 증가합니다. 이 답변이 어떻게 표시되는지는 평균적으로 작업자 활용도가 높아지지만 모든 경우에 대한 전체 계산 시간이 단축 된다는 보장은 없습니다 .

“알아서 반갑습니다”라고 생각할 수 있습니다. “하지만이를 아는 것이 구체적인 다중 처리 문제에 어떻게 도움이됩니까?” 글쎄, 그렇지 않습니다. 더 정직한 짧은 대답은 “단순한 대답은 없다”, “다중 처리는 복잡하다”, “따라 다릅니다”입니다. 관찰 된 증상은 유사한 시나리오에서도 다른 뿌리를 가질 수 있습니다.

이 답변은 풀의 스케줄링 블랙 박스에 대한 명확한 그림을 얻는 데 도움이되는 기본 개념을 제공하려고합니다. 또한 청크 크기와 관련하여 잠재적 인 절벽을 인식하고 방지 할 수있는 몇 가지 기본 도구를 제공하려고합니다.

---

목차

파트 I

1. 정의
2. 병렬화 목표
3. 병렬화 시나리오
4. 청크 크기의 위험> 1
5. 풀의 청크 크기 알고리즘

6. 알고리즘 효율성 정량화

   6.1 모델

   6.2 병렬 일정

   6.3 효율성

   6.3.1 절대 분배 효율성 (ADE)

   6.3.2 상대 분배 효율성 (RDE)

파트 II

7. Naive vs. Pool의 청크 크기 알고리즘
8. 현실 점검
9. 결론

먼저 몇 가지 중요한 용어를 명확히 할 필요가 있습니다.

---

1. 정의

큰 덩어리

여기서 청크 iterable는 풀 메서드 호출에 지정된 -argument 의 공유입니다 . 청크 크기가 계산되는 방법과 이것이 미칠 수있는 영향은이 답변의 주제입니다.

직무

데이터 측면에서 작업자 프로세스에서 작업의 물리적 표현은 아래 그림에서 볼 수 있습니다.

그림은에서 읽은 작업 이 압축 해제 되는 함수 pool.map()에서 가져온 코드 줄을 따라 표시된에 대한 호출의 예를 보여줍니다 . 풀-노동자-프로세스 의 기본 기능입니다 . 풀 – 메소드로 지정된 -argument 만 일치합니다 -variable 내부에게 같은 단일 통화 방법에 대한 α- 함수 와에 대한 과를 . – 매개 변수 가있는 나머지 풀 메소드의 경우 처리 함수 는 매퍼 함수 ( 또는 )가됩니다. 이 함수는 이터 러블 (-> “map-tasks”)의 전송 된 청크의 모든 요소 에서 사용자 지정 매개 변수를 매핑합니다 . 걸리는 시간은 작업을 정의합니다.multiprocessing.pool.workerinqueueworkerMainThreadfuncfuncworkerapply_asyncimapchunksize=1chunksizefuncmapstarstarmapstarfunc또한 작업 단위로 .

Taskel

한 청크 의 전체 처리를 위한 “작업”이라는 단어의 사용은 내의 코드와 일치 하지만 청크의 한 요소를 인수 로 사용하여 사용자 지정에 multiprocessing.pool대한 단일 호출 이 어떻게되어야 하는지를 표시하지 않습니다 func. 참조. 충돌이 (생각 이름에서 신흥 혼동을 피하기 위해 maxtasksperchild풀의에 대한 -parameter __init__-method),이 답변은 작업 내에서 작품의 하나의 단위로 참조 할 taskel .

taskel (에서 작업 + 엘 장담)는 내 작업의 가장 작은 단위입니다 작업 . 전송 된 chunk 의 단일 요소 에서 얻은 인수로 호출 func되는 Pool-method 의 -parameter로 지정된 함수의 단일 실행입니다 . 작업은 구성 taskels .chunksize

병렬화 오버 헤드 (PO)

PO 는 Python 내부 오버 헤드와 프로세스 간 통신 (IPC)을위한 오버 헤드로 구성됩니다. Python 내의 작업 별 오버 헤드는 작업과 그 결과를 패키징하고 풀기 위해 필요한 코드와 함께 제공됩니다. IPC-overhead는 스레드의 필요한 동기화와 서로 다른 주소 공간 간의 데이터 복사와 함께 제공됩니다 (2 개의 복사 단계 필요 : 상위-> 대기열-> 하위). IPC 오버 헤드의 양은 OS, 하드웨어 및 데이터 크기에 따라 달라 지므로 영향에 대한 일반화가 어렵습니다.

---

2. 병렬화 목표

다중 처리를 사용할 때 우리의 전반적인 목표는 (분명히) 모든 작업에 대한 총 처리 시간을 최소화하는 것입니다. 이 전반적인 목표에 도달하기 위해, 우리의 기술 목표는 될 필요가 하드웨어 자원의 활용을 최적화 .

기술적 목표를 달성하기위한 몇 가지 중요한 하위 목표는 다음과 같습니다.

• 병렬화 오버 헤드 최소화 (가장 유명하지만 단독은 아님 : IPC )
• 모든 CPU 코어에서 높은 활용도
• OS가 과도한 페이징 ( 쓰레기 ) 을 방지하기 위해 메모리 사용량을 제한합니다.

처음에는 병렬화에 대해 지불해야하는 PO를 회수 하기 위해 작업이 충분히 계산적으로 무거워 야합니다 (집약적) . 태스크 당 절대 계산 시간이 증가하면 PO의 관련성이 감소합니다. 또는 반대로 말하면 문제에 대한 태스크 당 절대 계산 시간이 클수록 PO를 줄여야 할 필요성이 줄어 듭니다. 계산에 태스크 당 몇 시간이 걸리면 IPC 오버 헤드는 비교해 볼 때 무시할 수있을 것입니다. 여기서 주요 관심사는 모든 작업이 배포 된 후 유휴 작업자 프로세스를 방지하는 것입니다. 모든 코어를로드 된 상태로 유지한다는 것은 가능한 한 많이 병렬화한다는 의미입니다.

---

3. 병렬화 시나리오

multiprocessing.Pool.map ()과 같은 메소드에 대한 최적의 청크 크기 인수를 결정하는 요인은 무엇입니까?

문제의 주요 요인은 단일 작업에 따라 계산 시간이 얼마나 달라질 수 있는지입니다. 이름을 지정하면 최적의 청크 크기 선택은 태스크 당 계산 시간에 대한 변동 계수 ( CV )에 의해 결정됩니다 .

이 변동의 범위에 따라 규모에 따른 두 가지 극단적 인 시나리오는 다음과 같습니다.

1. 모든 태스크에는 정확히 동일한 계산 시간이 필요합니다.
2. 태스크를 완료하는 데 몇 초 또는 며칠이 걸릴 수 있습니다.

더 나은 기억력을 위해 이러한 시나리오를 다음과 같이 언급하겠습니다.

1. 조밀 한 시나리오
2. 넓은 시나리오

조밀 한 시나리오

조밀 한 시나리오 에서는 필요한 IPC 및 컨텍스트 전환을 최소한으로 유지하기 위해 모든 태스크를 한 번에 배포하는 것이 바람직합니다. 즉, 작업자 프로세스가 많은만큼만 청크를 생성하려고합니다. 위에서 이미 언급했듯이 작업 당 계산 시간이 짧아지면 PO의 가중치가 증가합니다.

최대 처리량을 위해 모든 작업이 처리 될 때까지 모든 작업자 프로세스가 사용되기를 원합니다 (유휴 작업자 없음). 이 목표를 위해 분산 된 청크는 크기가 같거나 비슷해야합니다.

넓은 시나리오

Wide Scenario 의 대표적인 예는 결과가 빠르게 수렴되거나 계산에 며칠이 아닌 몇 시간이 걸릴 수있는 최적화 문제입니다. 일반적으로 이러한 경우 작업에 “가벼운 작업”과 “무거운 작업”의 혼합이 무엇인지 예측할 수 없으므로 작업 일괄 처리에 너무 많은 작업을 한 번에 배포하는 것은 바람직하지 않습니다. 가능한 것보다 적은 태스크를 한 번에 배포하면 스케줄링 유연성이 증가합니다. 이는 모든 코어의 높은 활용도라는 하위 목표에 도달하기 위해 필요합니다.

경우 Pool방법은 기본적으로 완전히 조밀 한 시나리오에 최적화 될 것이다, 그들은 점점 더 가까이 와이드 시나리오에 위치한 모든 문제에 대한 최적 타이밍을 만들 것입니다.

---

4. 청크 크기의 위험> 1

풀 메서드에 전달하려는 Wide Scenario -iterable 의 단순화 된 의사 코드 예제를 고려하십시오 .

good_luck_iterable = [60, 60, 86400, 60, 86400, 60, 60, 84600]

실제 값 대신 1 분 또는 1 일의 단순성을 위해 필요한 계산 시간을 초 단위로 보는 척합니다. 풀에 4 개의 작업자 프로세스 (4 개의 코어)가 있고 chunksize로 설정되어 있다고 가정합니다 2. 주문이 유지되기 때문에 작업자에게 보내는 청크는 다음과 같습니다.

[(60, 60), (86400, 60), (86400, 60), (60, 84600)]

워커가 충분하고 계산 시간이 충분히 높기 때문에 모든 워커 프로세스가 처음에 작업 할 청크를 얻을 것이라고 말할 수 있습니다. (빠른 완료 작업의 경우에는 그렇지 않아도됩니다.) 또한 전체 처리에는 약 86400 + 60 초가 소요됩니다. 이는이 인공 시나리오에서 청크에 대한 가장 높은 총 계산 시간이고 청크를 한 번만 배포하기 때문입니다.

이제 이전 iterable과 비교하여 위치를 전환하는 요소가 하나 뿐인이 iterable을 고려하십시오.

bad_luck_iterable = [60, 60, 86400, 86400, 60, 60, 60, 84600]

… 및 해당 청크 :

[(60, 60), (86400, 86400), (60, 60), (60, 84600)]

이터 러블을 정렬하면 총 처리 시간이 거의 두 배 (86400 + 86400) 늘어났습니다. 악의적 인 (86400, 86400) 덩어리를 얻는 작업자는 작업에서 두 ​​번째 무거운 작업이 이미 (60, 60) 덩어리로 완료된 유휴 작업자 중 한 명에게 분배되는 것을 차단하고 있습니다. 우리가 설정한다면 분명히 그러한 불쾌한 결과를 위험에 빠뜨리지 않을 것입니다 chunksize=1.

이것은 더 큰 청크 크기의 위험입니다. 청크 크기가 높을수록 오버 헤드를 줄이면서 스케줄링 유연성을 거래하며 위와 같은 경우에는 나쁜 거래입니다.

6 장에서 볼 수있는 방법 . 알고리즘 효율성 정량화 , 더 큰 청크 크기는 밀도가 높은 시나리오에 대해 차선의 결과로 이어질 수 있습니다 .

---

5. 풀의 청크 크기 알고리즘

아래에서 소스 코드 내에서 약간 수정 된 알고리즘 버전을 찾을 수 있습니다. 보시다시피 아래 부분을 잘라내어 chunksize외부 에서 인수 를 계산하는 함수로 감쌌습니다 . 또한 대체 4로모그래퍼 factor매개 변수와 아웃소싱 len()전화를.

# mp_utils.py

def calc_chunksize(n_workers, len_iterable, factor=4):
    """Calculate chunksize argument for Pool-methods.

    Resembles source-code within `multiprocessing.pool.Pool._map_async`.
    """
    chunksize, extra = divmod(len_iterable, n_workers * factor)
    if extra:
        chunksize += 1
    return chunksize

우리 모두가 같은 페이지에 있는지 확인하기 위해 다음과 같은 작업을 divmod수행합니다.

divmod(x, y)을 반환하는 내장 함수입니다 (x//y, x%y).
x // y로부터 내림 몫 복귀 바닥 부문 인 x / y동안
x % y의 나머지를 반환하는 모듈로 연산이다 x / y. 따라서 예를 들어 divmod(10, 3)반환합니다 (3, 1).

당신이 볼 때 지금 chunksize, extra = divmod(len_iterable, n_workers * 4), 당신은 알 n_workers여기에 제수 인 y의 x / y와로 곱셈 4을 통해 추가 조정하지 않고 if extra: chunksize +=1, 초기 chunksize 영역을 리드 이후에 적어도 네 번 작은 (를 들어 len_iterable >= n_workers * 4이 다른 것보다).

4중간 청크 크기 결과에 대한 곱셈의 효과를 보려면 다음 함수를 고려하십시오.

def compare_chunksizes(len_iterable, n_workers=4):
    """Calculate naive chunksize, Pool's stage-1 chunksize and the chunksize
    for Pool's complete algorithm. Return chunksizes and the real factors by
    which naive chunksizes are bigger.
    """
    cs_naive = len_iterable // n_workers or 1  # naive approach
    cs_pool1 = len_iterable // (n_workers * 4) or 1  # incomplete pool algo.
    cs_pool2 = calc_chunksize(n_workers, len_iterable)

    real_factor_pool1 = cs_naive / cs_pool1
    real_factor_pool2 = cs_naive / cs_pool2

    return cs_naive, cs_pool1, cs_pool2, real_factor_pool1, real_factor_pool2

위의 함수 cs_naive는 풀의 청크 크기 알고리즘 ( cs_pool1) 의 순진한 청크 크기 ( )와 첫 번째 단계 청크 크기 뿐만 아니라 완전한 풀 알고리즘 ( cs_pool2)에 대한 청크 크기를 계산합니다 . 또한 그것은 계산 실제 요인 rf_pool1 = cs_naive / cs_pool1 과 rf_pool2 = cs_naive / cs_pool2순진 계산 chunksizes이 풀의 내부 버전 (들)보다 더 얼마나 많은 시간을 알려주십시오.

아래에는이 함수의 출력으로 생성 된 두 개의 그림이 있습니다. 왼쪽 그림 n_workers=4은 반복 가능한 길이가 될 때까지의 청크 크기를 보여줍니다 500. 오른쪽 그림은의 값을 보여줍니다 rf_pool1. 반복 가능한 길이 16의 경우 실수 인자는 >=4(for len_iterable >= n_workers * 4)가되고 최대 값은 7반복 가능한 길이 28-31입니다. 그것은 4더 긴 반복을 위해 알고리즘이 수렴 하는 원래 요소 와 의 엄청난 편차입니다 . 여기서 ‘Longer’는 상대적이며 지정된 작업자 수에 따라 다릅니다.

chunksize는 cs_pool1여전히 완전한 알고리즘에 포함 된 extra나머지 조정 이 부족 하다는 것을 기억하십시오 .divmodcs_pool2

알고리즘은 다음과 함께 계속됩니다.

if extra:
    chunksize += 1

이제 나머지 ( divmod-operation에서 가져온 것) 가 있는 경우 extra청크 크기를 1 씩 늘리면 분명히 모든 작업에 대해 해결할 수 없습니다. 결국, 만약 그렇다면, 시작할 나머지는 없을 것입니다.

아래 그림에서 알 수 있듯이 ” 추가 처리 “는 현재 실제 요인 이 아래 에서 rf_pool2수렴 하고 편차가 다소 부드럽다는 효과가 있습니다. 표준 편차 와 의 방울 에 에 에 .4 4n_workers=4len_iterable=5000.5233rf_pool10.4115rf_pool2

결국 chunksize1 씩 증가 하면 전송 된 마지막 작업의 크기 만 len_iterable % chunksize or chunksize.

더 재미 있고 우리가 나중에 더 많은 결과적 볼 방법의 효과를 추가 처리는 그러나 관찰 할 수있다 생성 덩어리의 수 ( n_chunks). 이터 러블이 충분히 긴 경우 풀의 완성 된 n_pool2청크 크기 알고리즘 ( 아래 그림 참조)은에서 청크 수를 안정화합니다 n_chunks == n_workers * 4. 대조적으로, (초기 트림 후) 순 알고리즘 번갈아 유지 n_chunks == n_workers하고 n_chunks == n_workers + 1반복 가능한 성장의 길이로.

아래에는 풀과 순진한 청크 크기 알고리즘에 대한 두 가지 향상된 정보 함수가 있습니다. 이러한 함수의 출력은 다음 장에서 필요합니다.

# mp_utils.py

from collections import namedtuple


Chunkinfo = namedtuple(
    'Chunkinfo', ['n_workers', 'len_iterable', 'n_chunks',
                  'chunksize', 'last_chunk']
)

def calc_chunksize_info(n_workers, len_iterable, factor=4):
    """Calculate chunksize numbers."""
    chunksize, extra = divmod(len_iterable, n_workers * factor)
    if extra:
        chunksize += 1
    # `+ (len_iterable % chunksize > 0)` exploits that `True == 1`
    n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
    # exploit `0 == False`
    last_chunk = len_iterable % chunksize or chunksize

    return Chunkinfo(
        n_workers, len_iterable, n_chunks, chunksize, last_chunk
    )

의 예상치 못한 모양에 혼동하지 마십시오 calc_naive_chunksize_info. extra로부터는 divmodchunksize 영역을 계산하기 위해 사용되지 않는다.

def calc_naive_chunksize_info(n_workers, len_iterable):
    """Calculate naive chunksize numbers."""
    chunksize, extra = divmod(len_iterable, n_workers)
    if chunksize == 0:
        chunksize = 1
        n_chunks = extra
        last_chunk = chunksize
    else:
        n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0)
        last_chunk = len_iterable % chunksize or chunksize

    return Chunkinfo(
        n_workers, len_iterable, n_chunks, chunksize, last_chunk
    )

---

6. 알고리즘 효율성 정량화

이제 Pool의 청크 크기 알고리즘의 출력이 순진한 알고리즘 의 출력과 어떻게 다른지 확인한 후 …

• Pool의 접근 방식이 실제로 무언가를 개선 하는지 어떻게 알 수 있습니까?
• 그리고 이것이 정확히 무엇 일까요?

이전 장에서 볼 수 있듯이, 더 긴 반복 가능 (더 많은 태스크 수)의 경우 풀의 청크 크기 알고리즘 은 순진한 방법보다 반복 가능을 대략 4 배 더 많은 청크 로 나눕니다 . 작은 청크는 더 많은 작업을 의미하고 더 많은 작업은 더 많은 병렬화 오버 헤드 (PO)를 의미 합니다. 비용은 증가 된 스케줄링 유연성의 이점과 비교해 가중되어야합니다 ( “Risks of Chunksize> 1” ).

분명한 이유 때문에 풀의 기본 청크 크기 알고리즘은 PO 에 비해 스케줄링 유연성을 평가할 수 없습니다 . IPC 오버 헤드는 OS, 하드웨어 및 데이터 크기에 따라 다릅니다. 알고리즘은 우리가 코드를 실행하는 하드웨어를 알 수 없으며 태스크를 완료하는 데 걸리는 시간도 알 수 없습니다. 가능한 모든 시나리오에 대한 기본 기능을 제공하는 휴리스틱 입니다. 이는 특히 어떤 시나리오에도 최적화 할 수 없음을 의미합니다. 앞서 언급했듯이 PO 는 태스크 당 계산 시간 (음의 상관 관계)이 증가함에 따라 점점 더 중요해집니다.

2 장의 병렬화 목표 를 떠 올릴 때 한 가지 요점은 다음과 같습니다.

• 모든 CPU 코어에서 높은 활용도

이전에 언급 한 것 , Pool의 청크 크기 알고리즘 은 개선 노력은이다 노동자 프로세스 공회전 최소화 , 각각 의 CPU 코어의 활용도를 .

multiprocessing.Pool모든 작업자 프로세스가 바쁠 것으로 예상되는 상황에서 사용되지 않는 코어 / 유휴 작업자 프로세스에 대해 궁금해하는 사람들이 SO에 관한 반복 질문을 던집니다 . 여기에는 여러 가지 이유가있을 수 있지만 계산이 끝날 때까지 유휴 작업자 프로세스는 조밀 한 시나리오 에서도 종종 관찰 할 수있는 관찰입니다. 근로자 수는없는 곳의 경우 (taskel 당 동일한 계산 시간) 제수 수의 청크 수 ( n_chunks % n_workers > 0).

이제 질문은 다음과 같습니다.

청크 크기에 대한 이해를 관찰 된 작업자 활용도를 설명하거나 그와 관련하여 다른 알고리즘의 효율성을 비교할 수있는 것으로 어떻게 실질적으로 변환 할 수 있습니까?

---

6.1 모델

여기에서 더 깊은 통찰력을 얻으려면 정의 된 경계 내에서 중요성을 유지하면서 지나치게 복잡한 현실을 관리 가능한 수준으로 단순화하는 병렬 계산의 추상화 형태가 필요합니다. 이러한 추상화를 모델 이라고합니다 . 이러한 ” 병렬화 모델”(PM) 의 구현은 데이터가 수집되는 경우 실제 계산이 수행하는 것처럼 작업자 매핑 된 메타 데이터 (타임 스탬프)를 생성합니다. 모델 생성 메타 데이터를 사용하면 특정 제약 조건에서 병렬 계산의 메트릭을 예측할 수 있습니다.

여기에 정의 내에서 두 개의 하위 모델 중 하나 오후 는 IS 유통 모델 (DM)를 . DM이 분산되는지 원자 작업 단위 (taskels) 설명 평행 노동자 및 시간 , 다른 각 chunksize 영역 알고리즘보다 요인 노동자의 수, 입력 반복 가능한 (taskels 수) 및 그 계산 시간이 고려되지 않을 때 . 이것은 모든 형태의 오버 헤드가 포함 되지 않음을 .

완전한 PM을 얻기 위해 DM 은 다양한 형태의 병렬화 오버 헤드 (PO)를 나타내는 오버 헤드 모델 (OM) 로 확장됩니다 . 이러한 모델은 각 노드에 대해 개별적으로 보정해야합니다 (하드웨어, OS 의존성). OM 에 얼마나 많은 형태의 오버 헤드가 표시되는지 는 개방되어 있으므로 다양한 정도의 복잡성을 가진 여러 OM 이 존재할 수 있습니다. 구현 된 OM에 필요한 정확도 수준은 특정 계산에 대한 PO 의 전체 가중치에 의해 결정됩니다 . 태스크가 짧을수록 PE (병렬화 효율성) 를 예측 하려는 경우 가중치가 높아집니다. PO의 더 정확한 OM이 필요합니다. .

---

6.2 병렬 일정 (PS)

병렬 일정 x 축은 시간을 나타내고, 병렬 계산하고 y 축은 2 차원 표현 평행 노동자의 풀을 나타낸다. 작업자 수와 총 계산 시간은 더 작은 직사각형이 그려지는 직사각형의 확장을 표시합니다.이 작은 직사각형은 작업의 원자 단위 (태스크)를 나타냅니다.

아래 는 Dense Scenario에 대한 Pool의 chunksize-algorithm의 DM 데이터로 그려진 PS 의 시각화입니다 .

• x 축은 동일한 시간 단위로 구분되며 각 단위는 태스크에 필요한 계산 시간을 나타냅니다.
• y 축은 풀이 사용하는 작업자 프로세스 수로 나뉩니다.
• 여기서 taskel은 가장 작은 청록색 사각형으로 표시되며 익명화 된 작업자 프로세스의 타임 라인 (일정)에 배치됩니다.
• 작업은 동일한 색상으로 지속적으로 강조 표시된 작업자 타임 라인의 하나 또는 여러 작업입니다.
• 유휴 시간 단위는 빨간색 타일로 표시됩니다.
• 병렬 일정은 섹션으로 분할됩니다. 마지막 섹션은 꼬리 섹션입니다.

구성 부품의 이름은 아래 그림에서 볼 수 있습니다.

OM을 포함 하는 완전한 PM 에서 Idling Share 는 꼬리에 국한되지 않고 작업 사이의 공간과 심지어 작업 사이의 공간도 포함합니다.

---

6.3 효율성

위에서 소개 한 모델을 통해 근로자 활용률을 정량화 할 수 있습니다. 우리는 다음을 구별 할 수 있습니다.

• 배포 효율성 (DE) -DM (또는 고밀도 시나리오 의 단순화 된 방법)을 사용하여 계산됩니다 .
• 병렬화 효율성 (PE) -보정 된 PM (예측)을 사용하여 계산하거나 실제 계산의 메타 데이터에서 계산합니다.

계산 된 효율성 은 주어진 병렬화 문제에 대해 더 빠른 전체 계산 과 자동으로 연관 되지 않는다는 점에 유의 해야 합니다. 이 맥락에서 작업자 활용은 시작되었지만 완료되지 않은 작업이있는 작업자와 그러한 “개방 된”작업이없는 작업자를 구별 할뿐입니다. 즉, taskel의 시간 범위 동안 가능한 유휴 상태 가 등록 되지 않습니다 .

위에서 언급 한 모든 효율성은 기본적으로 Busy Share / Parallel Schedule 분할의 몫을 계산하여 얻을 수 있습니다 . DE 와 PE 의 차이점 은 오버 헤드 확장 PM에 대한 전체 병렬 일정에서 더 작은 부분을 차지하는 바쁜 공유에 있습니다.

이 답변은 밀도가 높은 시나리오에 대한 DE 를 계산하는 간단한 방법에 대해서만 설명 합니다. 이것은 다른 청크 크기 알고리즘을 비교하기에 충분합니다.

1. … DM 은 PM 의 일부이며, 사용되는 청크 크기 알고리즘에 따라 변경됩니다.
2. … taskel 당 계산 기간이 동일한 고밀도 시나리오 는 이러한 시간 범위가 방정식에서 벗어나는 “안정 상태”를 나타냅니다. 태스크의 순서가 중요하기 때문에 다른 시나리오는 무작위 결과로 이어질 것입니다.

---

6.3.1 절대 분배 효율성 (ADE)

이 기본 효율성은 일반적으로 Busy Share 를 Parallel Schedule 의 전체 잠재력으로 나누어 계산할 수 있습니다 .

절대 배포 효율성 (ADE) = 바쁜 공유 / 병렬 일정

를 위해 조밀 한 시나리오 , 단순화 된 계산 코드는 다음과 같습니다 :

# mp_utils.py

def calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
    """Calculate Absolute Distribution Efficiency (ADE).

    `len_iterable` is not used, but contained to keep a consistent signature
    with `calc_rde`.
    """
    if n_workers == 1:
        return 1

    potential = (
        ((n_chunks // n_workers + (n_chunks % n_workers > 1)) * chunksize)
        + (n_chunks % n_workers == 1) * last_chunk
    ) * n_workers

    n_full_chunks = n_chunks - (chunksize > last_chunk)
    taskels_in_regular_chunks = n_full_chunks * chunksize
    real = taskels_in_regular_chunks + (chunksize > last_chunk) * last_chunk
    ade = real / potential

    return ade

어떤이없는 경우 공회전 공유 , 바쁜 친구들과 공유 될 것입니다 동일 할 일정을 병렬 따라서 우리가 얻을, ADE 100 %입니다. 단순화 된 모델에서 이것은 모든 작업을 처리하는 데 필요한 전체 시간 동안 사용 가능한 모든 프로세스가 바쁜 시나리오입니다. 즉, 전체 작업이 효과적으로 100 % 병렬화됩니다.

하지만 여기서 PE 를 절대 PE 로 계속 언급하는 이유는 무엇입니까?

이를 이해하려면 최대한의 스케줄링 유연성을 보장하는 청크 크기 (cs)에 대한 가능한 경우를 고려해야합니다 (또한 하이랜더 수가있을 수 있습니다. 우연?).

__________________________________ ~ 하나 ~ __________________________________

예를 들어 4 개의 작업자 프로세스와 37 개의 태스크가있는 경우 chunksize=1, n_workers=437의 제수가 아니기 때문에를 사용 하더라도 유휴 작업자가있을 것입니다. 37/4 을 나눈 나머지는 1입니다.이 단일 나머지 태스크는 다음과 같아야합니다. 나머지 세 명은 유휴 상태입니다.

마찬가지로, 아래 그림과 같이 39 개의 태스크를 가진 유휴 작업자가 여전히 존재합니다.

당신은 상단 비교하면 병렬 일정을 위해 chunksize=1의 아래 버전으로 chunksize=3, 당신은 위 것을 알 수 병렬 일정 작은, 온 타임 라인 짧은 X는 축. 조밀 한 시나리오 에서도 예상치 않게 더 큰 청크 크기 가 전체 계산 시간을 증가시킬 수 있다는 것이 이제 분명 해져야 합니다.

그러나 효율성 계산을 위해 x 축의 길이를 사용하지 않는 이유는 무엇입니까?

이 모델에는 오버 헤드가 포함되어 있지 않기 때문입니다. 두 청크 크기에 따라 다르므로 x 축은 실제로 직접 비교할 수 없습니다. 오버 헤드로 인해 아래 그림의 사례 2 와 같이 총 계산 시간이 더 길어질 수 있습니다.

---

6.3.2 상대 분배 효율성 (RDE)

ADE의 경우 값은 정보를 포함하지 않는 더 나은 taskels의 분포가 1로 chunksize 영역 설정 가능합니다 더 나은 아직 여기 작은 의미 공회전 공유 .

의 GET에 드 가능한 최대 조정 값 DE을 , 우리는 고려 나눌 필요가 ADE를 관통 ADE 우리가 얻을 chunksize=1.

RDE (상대적 분배 효율성) = ADE_cs_x / ADE_cs_1

다음은 코드에서 어떻게 보이는지입니다.

# mp_utils.py

def calc_rde(n_workers, len_iterable, n_chunks, chunksize, last_chunk):
    """Calculate Relative Distribution Efficiency (RDE)."""
    ade_cs1 = calc_ade(
        n_workers, len_iterable, n_chunks=len_iterable,
        chunksize=1, last_chunk=1
    )
    ade = calc_ade(n_workers, len_iterable, n_chunks, chunksize, last_chunk)
    rde = ade / ade_cs1

    return rde

여기서 정의 된 RDE 는 본질적으로 Parallel Schedule 의 꼬리에 대한 이야기입니다 . RDE 는 꼬리에 포함 된 최대 유효 청크 크기의 영향을받습니다. (이 꼬리는 x 축 길이 chunksize또는 last_chunk.) 결과적 으로 아래 그림과 같이 모든 종류의 “꼬리 모양”에 대해 RDE가 자연스럽게 100 % (짝수)로 수렴됩니다.

낮은 RDE …

• 최적화 가능성에 대한 강력한 힌트입니다.
• 전체 병렬 일정 의 상대적인 꼬리 부분이 줄어들 기 때문에 자연스럽게 더 긴 반복 가능 항목에 대한 가능성이 낮아집니다 .

---

여기 에서이 답변의 파트 II를 찾으 십시오 .