알고리즘을 병렬 처리해야한다는 힌트는 무엇입니까?

Question

지금까지 경험 한 바에 따르면 멀티 코어 프로세서를 사용해도 알고리즘을 병렬 처리해도 속도가 빨라지지는 않습니다. 실제로 때로는 상황을 늦출 수 있습니다. 알고리즘을 병렬 처리하여 속도를 크게 높일 수 있다는 좋은 힌트는 무엇입니까? 독립적 비슷한 크기의 과정 곡물 덩어리로 분리 할 수 ​​

는

Answer 1

이 parallelisation 가장 혜택 작업을 할 수 있어야한다을 얻기 위해 (물론 조기 최적화주의 악에 자신의 상관 관계를 주어진) (또는 대부분 그렇게), 청크 간의 데이터 통신이나 동기화가 거의 필요하지 않습니다.

미세 입자 병렬화는 거의 항상 오버 헤드가 증가하고 사용 가능한 물리적 코어 수에 관계없이 유한 속도가 향상됩니다.

[주의해야 할 점은 매우 큰 번호의 아키텍처입니다. (연결 기계 64,000 개의 코어와 같은) '코어'로 구성됩니다. 이들은 특정 토폴로지 (직사각형 메쉬와 같이)에 할당 된 상대적으로 단순한 작업으로 분해 될 수있는 계산에 매우 적합합니다.]

Answer 2

자물쇠가 많이 필요하면 그 중 하나 일 것입니다. 어려운 알고리즘은 잘 병렬 처리되지 않습니다. 서로 접촉 할 필요가없는 별도의 파트로 분해 될 수있는 알고리즘의 부분이 있습니까?

Answer 3

먼저, 후반 짐 그레이에 의해이 문서를 체크 아웃 :

Distributed Computing Economics

사실, 이것은 당신이 질문에 쓴 내용에 따라 몇 가지 오해를 정리합니다. 분명히, 당신의 문제 집합이 이산화되는 것이 덜 바람직하다면, 더 어려워 질 것입니다.

Answer 4

작업을 독립적 인 파트로 나눌 수 있으면 잘 병렬 처리 될 수 있습니다.

또한 Amdahl's Law를 기억하십시오. 이는 대부분의 프로그램에 더 많은 코어를 추가하여 성능면에서 기대할 수있는 것이 얼마나 적은지를 상기시켜줍니다.

Answer 5

이전 계산에 의존하는 계산을 할 때마다 병렬 문제가 아닙니다. 선형 이미지 처리, 무차별 방식, 유전 알고리즘 등은 모두 쉽게 병렬화됩니다.

좋은 유추는 여러 파트를 한꺼번에 처리 할 수있는 친구를 얻을 수 있다는 것입니다. 예를 들어, 서로 다른 사람들이 다른 섹션에서 작업 할 수 있다면 ikea 가구를 함께 배치하면 병렬 처리가 잘 될 수 있지만 벽을 연속적으로 수행해야하기 때문에 롤링 벽지가 아닐 수도 있습니다.

Answer 6

유한 요소 모델과 관련된 시뮬레이션과 같이 거대한 행렬 계산을 수행하는 경우에는 직선적 인 방식으로 작은 조각으로 나눌 수 있습니다. 행렬 - 벡터 곱셈은 매우 큰 행렬을 처리한다고 가정 할 때 병렬 처리의 이점을 얻을 수 있습니다. 실제 성능 병목 현상으로 인해 코드가 느리게 실행되는 경우가 아니라면 병렬 처리로 번거롭게 할 필요가 없을 것입니다.