전산 작업 부하 나누기 : 가능하거나 불가능한 곳

Question

컴퓨터 과학자는 아니지만 프로그램입니다. 따라서 워크로드 분할 문제를 올바르게 이해했는지 확인하고 싶습니다. 이것에 대해 생각하는 올바른 방법 아래에 있습니까?

특히 다음 문장 (1)이 맞습니까?

(1)의 경우 A (X_a) + A (X_b) + A (X_c) + ... = B (X_a, X_b, X_c, ...)은 Y

을 산출되는 식이다 =

A (X_n)이 바뀌면 X_m이 바뀌면 컴퓨터가 동시에 계산할 수있는 방정식의 부분을 할당하여 컴퓨터의 관점에서 더 빠르게 계산할 수 있는지 여부는 다음에 따라 다릅니다.

m이 n과 같지 않으면 특정 계산에 대한 작업 부하를 나누는 것이 성능 이득을 줄이고 시스템의 m과 n의 모든 조합에 해당되는 경우 단일 스레드를 통한 다중 스레드의 성능 향상은 불가능합니다 .

다른 말로하면, X_b와 X_c가 A (X_a)에 의존하고 프로세스 병목 현상을 일으키기 때문에 링크 된 변수가 멀티 스레드에 대한 능력을 저하 시킨다는 것을 올바르게 이해합니까? 다른 스레드는 A를 알고 있지만 기다려야합니다. 첫 번째 스레드는 명령을 실행하기 전에 출력을 제공하므로 부분으로 쉽게 분해되는 명령의 부분에 대한 동시 작업을 수행 할 수 없으며 계산은 각 계산의 각 부분을 하나의 스레드가 처리하는 데 많은 시간이 걸립니다. 다른 스레드가 동시에 작업하는 둘 이상의 스레드에서 수행하고 다른 스레드에서 즉석에서 완료되도록 결과를 합산하는 것입니다.

(2) 아니면 위의 병목 현상을 해결할 수있는 방법이 있습니까? 예를 들어이 병목 현상이 미리 알려진 경우 첫 번째 스레드가 초기에 작업을 병목 현상을 일으키는 모든 n에 대해 결과를 A (X_n)에 메모리에 저장 한 다음 작업 부하를 효율적으로 분할하여 A (X_i)를 i (X_a, X_b, X_c, ...)가 실행되기 전에 B (X_a, X_b, X_c, ...) 계산을 수행해야 할 때 어떤 방법으로 먼저 예측해야합니다. 실제로 실행됩니다. 그렇지 않으면 병목 현상이 발생합니다.

[편집 : NWP의 답변 맥락에서 명확하게하기 위해. 설명이 너무 길거나 명확하지 않은 경우에는 코멘트를 남겨주세요. LaTeX에서 몇 가지 그래픽을 작성하여 질문 글쓰기를 단축하십시오.]

"계산 I"프로그램에서 가장 긴 경로가 5 단위 이 예에서 시간. 이 가장 긴 경로를 알고 있고 실행중인 시스템이이 프로그램 "컴퓨팅 I"이 미래에 실행될 때 (실행 빈도를 기반으로) 예상 할 수있는 경우, 서브 프로그램 "컴퓨 트 B-> E"(어떤 것에도 의존하지 않음) else하지만 프로그램 "compute I"의 가장 긴 경로의 적절한 하위 집합 임)가 미리 실행될 수 있습니다. 결과는 사용자가 "컴퓨팅 I"을 요청하기 전에 메모리에 저장됩니다.

그렇다면 최대 속도가 9/4로 간주됩니까? B-> E가 준비되었으므로 다른 스레드가 기다릴 필요가 없습니다. 또는 "계산 I"의 최대 속도가 여전히 9/5로 간주됩니까?

이전에 실행 한 예상 프로그램에는 비용이 있지만이 비용은 "계산 I"실행의 각 인스턴스에 분산 될 수 있습니다. 예상 프로그램에 15 단계가 있지만 프로그램 "계산"이 예상 프로그램 실행마다 일반적으로 100 번 실행되고 모든 단계의 비용이 똑같다면 "계산 I"에서 가능한 최대 속도가 9라고 간단하게 말합니까?/(5 - 1 + 15/100)?

속도 향상은 이제 스레드 수와 가장 긴 경로뿐만 아니라 미리 계산을 저장할 수있는 메모리와 다른 프로그램이 "계산하기"를 예상 할 수있는 정도에 따라 달라집니다. 적절한 서브 프로그램을 미리 계산하십시오. 다른 프로그램 인 "compute X"는 "compute I"과 같은 가장 긴 경로의 길이를 가질 수 있지만 시스템은 "compute X"가 "compute I"과 동등하게 사전에 실행될 것으로 예상 할 수 없습니다. 사전 계산을 저장하기위한 메모리 증가를 희생시키면서 (i) 달성 한 속도 향상을 어떻게 높이는가? (ii) 일부 프로그램의 실행 타이밍은 다른 프로그램보다 사전에 예상 할 수 있으므로 병목 현상을 미리 계산할 수 있으므로이 방법은 최장 경로를 줄입니다. ?

그러나 가장 긴 경로가 서브 프로그램의 예측 사전 계산을 향상시키고 사전 계산 결과를 저장하는 데 더 많은 메모리를 동적으로 줄일 수 있다면 병목 현상은 계산상의 분할로 인해 속도 향상의 궁극적 인 상위 경계를 결정하는 것으로 간주 될 수 있습니다 작업량?

링크 된 변수 종속성 병목 관점/그래프 병의 관점에서 프로그램 "계산 I"의 멀티 스레딩 속도가 궁극적으로 상위 경계는 가장 긴 서브 프로그램 (다른 서브 프로그램은 그것에 의존/대기)에 의해 결정되는 것처럼 보입니다. 그러나 역학 관점에서 전체 시스템이 프로그램 전후에 실행되는 "프로그램"은 프로그램의 일부로 실행되며 "컴퓨팅 I"의 향후 실행 타이밍에 대한 충분한 예측 가능성과 더 많은 사전 계산을 저장할 수 있습니다. 독립 서브 프로그램은 "계산 I"의 모든 서브 프로그램의 길이를 1 단위로 완전히 줄일 수 있습니다. 즉, 충분한 예측 가능성과 메모리를 사용할 수 있다면 9/1 = 9의 속도 향상을 달성 할 수 있습니다.

멀티 스레딩을 통해 속도를 높이기위한 상한을 예측하는 데 올바른 관점은 무엇입니까? 충분한 메모리가있는 시스템에서 실행되는 프로그램은 멀티 스레딩에 제한이없는 것 같지만 자체적으로 보면 속도 제한에 대한 고정 제한이 있습니다.

또는 예상과 부분적인 사전 계산에 의해 가장 긴 경로를 줄이는 기능에 대한 질문은 속도가 빠르기 때문에 예측이 가능하고 예측할 수있는 방법으로 프로그램을 실행하기 때문에 사용자의 기대에 따라 멀티 스레딩 속도가 향상되지 않을 수 있으므로 프로그램 작성자 또는 시스템 디자이너에게 알려야하며 무시되어야하며/존재하지 않아야 만 하는가?

Answer 1

나는 어떤 것들이 당신의 설명에 달려 있는지 이해하지 못하지만, 나는 당신에게 어떤 이론을 줄 수 있습니다. Ahmdal's law이 있습니다. 주어진 알고리즘이 충분한 프로세서를 가지고 있다고 가정 할 때 병렬화 할 수있는 속도에 기반하여 달성 할 수있는 속도의 상한선을 제공합니다. 계산의 50 %를 병렬 처리 할 수 ​​있다면 최대 속도 2 배를 얻을 수 있습니다. 95 % 병렬 처리는 최대 20 배의 속도 향상을 제공합니다. 얼마만큼의 속도 향상을 얻을 수 있는지 알아 보려면 문제의 양을 병렬 처리 할 수 ​​있어야합니다. 이것은 당신이해야 할 일들의 그래프를 그리거나 무엇에 의존하고 가장 긴 길을 찾아 내서 할 수 있습니다. 예 :이 예에서는 가장 긴 경로 B-> E-> F-> H- 것> I에서

. 모든 블록은 동일한 시간을 실행하는 것으로 간주됩니다. 따라서 9 개의 블록이 있으며 가장 긴 경로는 5 블록이므로 달성 가능한 최대 속도는 9/5 = 1.8x입니다. 실제로 컴퓨터는 제한된 수의 스레드 만 병렬로 실행할 수 있으며 일부 블록은 다른 스레드보다 오래 걸리고 스레드 생성과 적절한 잠금 메커니즘을 사용하여 데이터 경합을 막는 데 드는 비용이 발생한다는 점을 고려해야합니다. 각 블록에 비용을 부여하고 스레드 메커니즘의 비용을 포함하여 비용을 추가하여 가장 긴 경로를 찾아 그래프에 추가 할 수 있습니다. 이 방법은 상한을 줄지 만 매우 겸손한 경향이 있습니다. 나는 이것이 당신이 그래프를 그리고 대답을 찾을 수 있기를 바랍니다.

EDIT : Ahmdal의 법칙은 코드를 단일 스레드로 실행하는 것이 오버 헤드가없는 무한 스레드로 코드를 실행하는 것과 비교한다는 것을 잊어 버렸습니다. 다중 스레드 버전이 단일 스레드 버전과 다른 코드를 실행하도록 만들면 더 이상 Ahmdal의 법칙에 구속되지 않습니다.

충분한 메모리와 시간을 사용하여 가능한 모든 입력에 대한 결과를 계산 한 다음 주어진 입력을 기반으로 조회를 수행하여 결과를 찾을 수 있습니다. 그러한 시스템은 실제로 아무 것도 계산하지 않고 Ahmdal의 법칙에 구속되지 않기 때문에 더 빨라진다. B-> E를 최적화하여 시간 단위를 0으로하면 가장 긴 경로는 3이되고 최대 속도가 8/3 = 2.66x가되는 노드가 8 개 밖에 없으므로 이전 1.8x보다 낫습니다. 이것은 멀티 스레딩에 의한 빠른 속도 향상 일뿐입니다. 실제로 첫 번째 버전은 4 시간 단위를 사용하고 두 번째 버전은 3 시간 단위를 사용합니다. 코드를 최적화하면 멀티 스레딩보다 속도가 향상됩니다. 그래프는 여전히 유용 할 수 있습니다. 코어가 부족하다고 가정하면 그래프는 프로그램의 어느 부분이 최적화 할 가치가 있고 그렇지 않은지를 알려줍니다. 코어가 부족하다고 가정하면 그래프를 통해 어떤 경로의 우선 순위를 결정해야하는지 알 수 있습니다. 예제에서는 A, B, C 및 D를 동시에 계산하므로 쿼드 코어가 필요합니다. E와 병행하여 C 실행 시간을 줄이고 D를 H와 평행하게 실행하면 1.8 배의 속도 향상을 위해 듀얼 코어로 충분합니다.