읽기 : The Hitchhiker's Guide to Concurrency, 더 구체적으로는 약 Amdahl's Law 섹션 - 병렬 프로그램은 가장 느린 부분만큼 빠르게 진행되며 프로그램이 병렬 일수록 시작 단계부터 소개가 빠를수록 빠릅니다. 더 많은 코어를 사용하고 싶습니다. 처음부터 가능한 한 병렬 코드를 작성하려면 어떻게해야합니까? 코드가 다중 코어를 추가 할 때 얻을 수있는 최대 이점을 얻을 수 있도록하려면 어떻게해야합니까? 또한 어떤 종류의 작업으로 인해 코드가 병렬이 아니거나 병렬 코드가 느려지 게됩니까? 코드 예제는 물론 이해할 수 있습니다.어떤 작업으로 인해 병렬 코드가 느리게 실행됩니까?
모든 코드가 본질적으로 병렬로 실행될 수있는 것은 아닙니다.
병렬 실행이란 동시에 동시에 의미합니다. 코드는 최종 결과에 의존하지 않고 동시에 실행되는 다른 코드의 경우에만 동시에 실행할 수 있습니다. 이 같은 방정식을 수행하는 경우 :
((((x+y)+z)+a)*b)
각 브래킷은 다음 단계 전에 일을해야하기 때문에 작업이 순차적으로 수행 할 수 없습니다. 프로그램을 병렬로 만들려면 동시에 할 수있는 조각으로 분해 될 수있는 큰 작업이 언제 있는지를 식별하는 것이 중요합니다.
합계를 고려해 볼 때 100,000 개의 숫자를 더해야합니다. 추가
sum = 0;
for (i = 0; i < 100000; i++) {
sum += numbers[i];
}
는 a + b + c + d 절반, 다른 하나 브래킷, 반, 마지막 경우는 작품의도 분포 (a + b + c) + d, a + (b + c) + d, (a + b) + (c + d) 등에 분할 할 수 있습니다, 교환 법칙이 성립 및 이행이다. 우리가 마지막에 재결합 할 수 있고, 두 개의 루프가 같은 답변을 얻을 여전히 같은 시간에 실행 및 수, 두
sumA = 0;
for (i = 0; i < 100000/2; i++) {
sumA += numbers[i];
}
sumB = 0;
for (i = 100000/2; i < 100000; i++) {
sumB += numbers[i];
}
sum = sumA + sumB;
분할 :
그래서 우리는이 같은 큰 작업을했다 가정합니다.이것은 병렬 프로그래밍에서 각 작업자 (cpu/노드/기계)의 섹션으로 작업을 분할 한 다음 결과를 수집하고 최종 결과를 조합하는 열쇠입니다. 우리는 이것을 산란과 모으기라고 부릅니다.
많은 컴퓨팅 작업이 분할 될 수 있지만 일부 작업은 분할 될 수 없습니다. 분열에 잘 적응하는 프로그램은 평행을 이루는 것이 이상적이며 그렇지 않은 프로그램은 이상적입니다. 분산 및 수집, 데이터 분할, 재조합 (가능하면 전송)에 상당한 오버 헤드가 있다는 점도 고려하십시오. 작업을 분할하는 것이 항상 가치있는 것은 아닙니다.
귀하의 질문에 대한 답변입니다. 프로그램이 자연스럽게 그렇게 할 수 있는지 여부와 같이 프로그램을 평행하게 만들기 위해 할 수있는 일은 그리 많지 않습니다. 불변 클래스 때 쓰기,
좀 더 OO 환경의 경우 : (부작용이없는) 순수하게 기능적인 언어를 사용는
물론, ((((x + y) + z) + a) * b)는 병렬화 될 수 있으며, b * (a + x) + b * (y + z)와 동일합니다. 필자는 첫 번째 문장에 동의하지 않기 때문에가 아니라, 선택한 여러 예제가 적절히 분석된다면 여러 병렬 계산을 병렬 처리 할 수 있다는 점을 잘 보여주기 때문에이 점을 지적합니다. –
@Mark : 음, 예, 공정한 플레이, 재 배열 할 수 있습니다. 본질적으로 순차적 인 괄호 안에 임의의 것을 원하는 것이었고 연산자 나 다른 것에 대해 생각하지 않고 썼습니다. 괄호가 중요한 부분이었습니다. 일반 연산자 기호 나 함수를 사용해야하지만 예제를 * look *을 필요한 것보다 더 복잡하게 만들고 싶지는 않았습니다. 따라서 간단한 간단한 예입니다. – Orbling
강제 직렬 계산의 가장 중요한 예는 일반적으로 값을 반복적으로 근사하는 수치 알고리즘에 있습니다. 다음 단계를 계산하려면 앞의 단계가 필요하며 앞 단계가 완료 될 때까지 기다려야합니다. 단지 몇 가지 가능한 결과 만 존재하는 것이 중요합니다. 말하자면 2 가지 결과가 나오기 때문에 결과가 정확하다는 것을 알 때 두 가지를 모두 추측하고 올바른 것을 선택하면됩니다. –
좋은 시작 (하스켈, 리스프 등 예)입니다 당신은 (자바에서 : 최종 필드를 사용하고 그 필드가 불변 타입이기 때문에) 변경 가능한 필드를 캡슐화하여 다른 스레드에서 실행중인 코드에 의해 변경되는 것에 대해 걱정할 필요가 없습니다.
마지막으로 코드가 매우 병렬화 가능하더라도 느리게 실행될 수 있습니다! 프로젝트가 끝나면 앱을 프로파일 링하고 가장 느린 부분을 먼저 작업하십시오.
행운을 빈다.
+1 병렬 처리가 모든 불황을 해결하지 못한다는 것을 지적하고, 알고리즘 병목 현상의 프로파일 링 및 설계 단계 분석이 가장 먼저 중단되고 대체됩니다. – Orbling
"순전히 기능적 언어를 사용하는 것이 좋은 출발입니다." 실제로 Lisp은 불순하며 Haskell은 멀티 코어 병렬 처리의 맥락에서 농담이다. –
아마도 Erlang이 더 나은 선택일까요? 나는 Lisp이 불순하다는 것을 깨닫지 못했다. –
컴퓨터 과학에서 많은 대답 개념으로, 그것은 달려있다.
우선 병렬 응용 프로그램을 만드는 Erlang의 방법은 EVM 경량 프로세스를 사용하는 것입니다. EVM 스케줄러는 프로세스마다 다른 코어에서 실행 시간을 할당합니다. 프로세스가 많을수록 프로세스가 병렬로 실행될 수있는 더 많은 가능성이 있습니다. 그러나 이것은 응용 프로그램의 이점을 의미하지 않습니다. 기본적으로
: http://www.erlang.org/doc/efficiency_guide/processes.html
는 SMP 에뮬레이터를 사용하여 성능을 얻기 위해, 응용 프로그램은 대부분의 시간을 하나 개 이상의 실행 가능한 얼랑 과정이 있어야합니다. 그렇지 않으면 Erlang 에뮬레이터는 여전히 한 번만 Erlang 프로세스를 실행할 수 있지만 여전히 잠금을 위해 오버 헤드를 지불해야합니다. 잠금 오버 헤드를 가능한 한 줄이기 위해 노력하지만 결코 정확하게 0이되지는 않습니다.
응용 프로그램의 다른 속성도 고려해야합니다. Erlang/OTP의 주요 이점 중 하나는 프로세스간에 사용할 수있는 격리입니다. 예를 들어, 웹 서버 또는 원격 통신 노드는 스폰 프로세스에 의해 들어오는 요청/호출마다 병렬적일 수 있습니다. 그러나 다른 주요 이점은 프로세스 (수신 요청) 격리, 감독 및 "무상으로 제공되는"내결함성 동작입니다. Erlang/OTP는 이러한 상황에서 잘 작동하도록 만들어졌습니다.
반면에 순차적 조작 (목록 : foldl/3) 만있는 애플리케이션은 프로세스를 생성하여 아무런 이점을 얻지 못할 수 있습니다. 대신 프로세스 오버 헤드로 인해 성능이 저하 될 수 있습니다.
시스템 병렬 실행의 다른 부분이 어떤 영향을 미칠지 생각해보십시오. 모두가 동일한 리소스 (예 : IO 문제)에 액세스하는 많은 프로세스를 생성합니다. 나는 초고속으로 작동하지만 병렬 리소스를 외부 리소스에 액세스하는 것이 한계가되어 버리므로 병렬 코드를 작성했습니다.
약간의 산책 후에 나는 당신의 질문에 대답하려고 노력할 것입니다.
일반적으로 응용 프로그램의 직렬화 된 부분은 문제의 크기에 따라 달라집니다. 또한 일반적으로 직렬화 부분은 고정되어 있거나 문제 크기에 따라 서서히 증가하므로 전체적으로 문제 크기를 늘리면 직렬 부분의 영향이 줄어 듭니다. Gustafson's law을 참조하십시오.
일반적으로 애플리케이션의 직렬화 된 부분은 분명합니다. 일반적인 패턴 중 하나는 요청을 처리하는 단일 서버 프로세스입니다 (예 : 작업을 작업자 프로세스에 배포하는 네트워크 소켓에서. 전체 시스템은 단일 프로세스가 네트워크에서 읽고 작업을 작업자에게 배포 할 수있는 것보다 빨리 진행될 수 없습니다. 병렬 처리를 높이려면 여러 서버를 병렬로 구성해야합니다.
또 다른 유사한 예는 단일 프로세스가 공유 리소스를 제어하도록하는 것입니다. 이 공유 리소스의 하위 리소스를 요청하려면 여러 소스의 모든 요청을 직렬화해야합니다. 여기서 병렬 처리를 증가시키는 한 가지 방법은 전체 자원의 일부 하위 섹션 인 각각 여러 개의 컨트롤러를 갖는 것입니다. 액세스를 요청할 때 소스는 무작위로 요청할 컨트롤러를 선택합니다 (또는 요청을 반듯이 균등하게 분산시키는 다른 방법). 본질적으로 자원 인 Sharding입니다.
+1 대규모 작업은 낙태를위한 범위가 더 커지는 경향이 있습니다. – Orbling
가능한 한 처음부터 가능한 한 병렬 코드를 작성하려면 어떻게해야합니까?
일반적으로이 문제는 데이터 종속성과 관련이 있습니다. 자체 실행을 시작하기 위해 데이터가 필요한 경우 작업은 에 종속적입니다. 여기에 몇 가지 중요한 트릭이 있습니다. 작업에 가능한 결과가 2 개 밖에 없다는 것을 알고 있다고 가정합니다. 그런 다음 두 계산을 모두 시작한 다음 나중에 나중에 올바른 "선택"을 수행 할 수 있습니다. 사실, CPU 설계는 종종 계산 단위로이 아이디어를 활용합니다 (예를 들어 Carry Select Adders에 대한 위키피디아 기사 참조). 또 다른 트릭은 결과가 특정 값, 예를 들어 99 %의 확실성이 될 것이라는 것을 알 때입니다. 그런 다음 당신은 추측 적으로 다음 작업을 실행할 수 있으며 귀하의 예측이 참되기를 바랍니다. 실패하면 항상 계산을 롤백하고 다시 실행할 수 있습니다. 이는 최신 CPU에서도 수행됩니다. 예를 들어 추측 실행 및 재주문 버퍼링을 사용하는 분기 예측 (Branch Prediction)을 참조하십시오.
이 시점에서, 현대 CPU 아키텍처는 이미 병렬 처리 트릭 인을 사용하고 있음을 분명히해야합니다. 문제는 그들이 우리가 얻을 수있는 모든 로컬 병렬 처리를 짜내었고, 이제 우리는 아이디어를 "한 단계 업"하여 프로그램에 적용해야한다는 것입니다.
어떻게하면 여러 코드를 추가 할 때 최대의 이점을 누릴 수 있습니까?
무엇이 병렬 계산을 죽입니까? 계산의 다른 부분에 의존한다면 은 병렬 실행 스레드간에 사이에 통신해야합니다. 이것은 으로 이어집니다. 메시지를 보내기 위해 다른 부분을 기다리고 있기 때문에을 기다립니다. 자주 사용되는 트릭은 대기 시간 숨기기입니다. : 메시지가 도착할 때까지 기다리지 않고 필요할 때 데이터가 완전히 전송되기를 바라며 다른 작업을 수행합니다. 그러나 코드가 전혀 통신 할 필요가 없도록 코드를 정렬 할 수 있다면 더 좋습니다.
이것은 함수형 프로그래밍이 병렬 처리를위한 강력한 도구로 간주되는 이유입니다. FP에서는 공유 상태가 없으므로 코드가 이미 작은 CPU 번들을 다른 CPU로 분기하기 쉽습니다.Haskell은 키워드로 par으로 인해이 아이디어에 가장 성숙한 언어입니다.
일반적으로 프로그램의 데이터 흐름에 대한 종속성이 거의없는 경우 여러 코어를 추가 할 때 빠르게 만들 수 있습니다. 가능한 한 데이터 흐름에서 직렬화 초크 포인트를 피하려고합니다.
얼랑 (Erlang) 얼랑 (Erlang)에 대한 망설이는 얼랭 (Erlang)이 간접적으로 병렬성을 얻는다는 것입니다. Erlang에서는 프로그램을 동시 액티비티, 즉 개의 프로세스 집합으로 설명합니다.이 프로세스는 문제를 해결하기 위해 함께 작동합니다 (). 프로세스는 격리되어 있으며 메시징으로 서로 통신합니다. Erlangs의 주요 강점은 내결함성입니다. 한 프로세스의 오류가 격리로 인해 다른 프로세스에 영향을 줄 수 없으므로 단일 프로세스의 경우 복구 된 소프트웨어를 빌드하여 죽은 보행 좀비 상태로 만들 수 있습니다.
이 모델은 명백한 병렬 평가 전략에 크게 의존합니다. 하나의 코어가 하나의 프로세스를 처리 할 때 초과 코어가 처리를 위해 다른 프로세스를 점유하게 할 수 있습니다. 다시 말하지만 프로세스가 서로 의존하지 않으면 메시지 도착을 기다린 다음 더 많은 코어를 추가하면 속도가 향상됩니다.
그래도 마법의 은색 총알이 아닙니다. 단일 프로세스를 통해 모든 메시지를 "초크 포인트"로 직렬화하면 코드가 병렬이되지 않습니다. Amdahl 또는 Gustafsson이 재생되고 직렬 프로그램이 남아 있습니다.
이 질문은 프로그래머가 더 잘 이해할 수 있습니다. – Orbling
Erlang을 태그로 사용하는 이유는 무엇입니까? 그 언어로 질문을 제한 할 이유가 전혀 없습니다. –