벡터 요소가 n 개 있다고 가정하고이를 p 프로세스에 배포하려고합니다. 여기서 n은 p의 배수 일 필요는 없습니다. 각 프로세스는 0에서 p-1까지의 순위를가집니다. 데이터가보다 균등하게 분산되도록하기 위해 각 프로세스에 얼마나 많은 요소가 있을지 결정하는 방법은 무엇입니까?p 프로세서에서 n 요소의 벡터를 분산하는 방법
예를 들어 n = 14이고 p = 4 인 경우 [3, 3, 4, 4] 또는 [3, 4, 3, 4]와 같은 분포가 필요하지만 [3, 3, 3, 5] 또는 [4, 4, 4, 2]가 아니다.
순위 r 인 프로세스의 요소 수를 반환하는 함수 f (n, p, r)가 필요합니다.
당신을 위해
(n + r)/p
사용할 수 있습니까?
와우! 심지어 내가 예상했던 것보다 단순합니다. –
이것은 Stack Overflow를 읽음으로써 배웠던 유일한 단점입니다. 나는 전에 이것을 보지 못했음에 놀랐다. –
이것은 Bin Packing 문제의 특수한 경우입니다. 몇 가지 아주 좋은 근사 알고리즘이 있지만, 이론적으로 NP 하드입니다.
위키 페이지를 읽지 않아도된다면 몇 줄로 요약 해 보겠습니다. 더 나은 해결책을 찾거나 근사 체계가 얼마나 잘 작동하는지 분석하고 싶다면 꼭보십시오.
1 단계 : 우선 순위별로 요소를 정렬하십시오.
2 단계 : 우선 순위가 가장 높은 요소를 잡고 가장 부담이 적은 프로세스에서 밀어냅니다.
3 단계 : 요소가 더 많은 경우 1 단계로 이동하고 그렇지 않으면 돌아갑니다.
아니요, 제 문제에 대한 해결책이 있음을 압니다. 나는 그것이 무엇인지를 기억하지 못한다. –
클래식 농부/근로자 접근 방법은 어떻습니까? MPI 예 : http://www.inf.ed.ac.uk/teaching/courses/ppls/farm.c – matcheek
제 경우는 아닙니다. 처리를 위해 이미지의 행을 배포해야하므로 농민/작업자 접근 방식이 해결책이되지 않습니다. –
위의 문제 설명에서 데이터를 사용하기 때문에 실행 시간을 미리 알 수 없기 때문에 한 명의 농부, 많은 작업자 (일명 가방) 접근 방식이 이상적인 솔루션 인 것 같습니다. 그렇습니다. 행렬에서 각 행을 가져 와서 별도의 프로세서에서 실행하십시오. 코드 예제를 통해 문제에 대해 더 많은 정보를 얻을 수 있습니다. – matcheek