문제 설명 :이그래프 문제에 병렬 처리 프로그래밍을 적용하는 방법은 무엇입니까?
n tasks이, 그리고이 완료되기 전에 A가 B에 의존하는 경우 의미 이러한 작업, one might be dependent on the others에, 다음 B 완료해야합니다.
1. 가능한 빨리 이러한 작업을 완료하는 방법을 찾았습니까?
2.if take parallelism into account, 어떻게 이러한 작업을 완료 할 수있는 프로그램을 설계합니까?
질문 :
분명히, 첫 번째 질문에 대한 대답은, 위상 - 종류의 이러한 작업은, 그 순서대로 완료합니다.
하지만 병렬 처리를 고려할 때 어떻게해야할까요?
내 대답은 다음 독립적 그 작업을 선택하고 먼저 완료, 첫번째 위상-종류의 이러한 작업을했다, 다음 ... 선택하고 나머지 그 독립적 인 사람을 완료
내가 맞죠?토폴로지 정렬 알고리즘은 다양한 결과 순서를 제공 할 수 있으므로 처음 몇 가지 요소를 가져 와서 독립적 인 것으로 가정 할 수는 없습니다.
토폴로지 정렬 대신 들어오는 종속 에지의 수로 작업을 정렬하는 것이 좋습니다. 예를 들어 그래프에 A → B, A → C, B → C, D → C가 있으면 A [0], D [0], B [1] , C [3] 여기서 [i]는 들어오는 가장자리의 수입니다.
토폴로지 정렬을 사용하면 A, B, D, C도 가질 수 있습니다. 이 경우 A와 D를 동시에 실행할 수 있음을 알기가 쉽지 않습니다.
작업이 완전히 처리 된 후에는 나머지 작업, 특히 완료된 작업에 종속 된 작업을 업데이트해야합니다. 그러나 작업에 들어가는 종속성의 수가 비교적 적은 경우 (예 : 수백 개), radix/bucket-sort와 같은 것에 의존하고 일정한 시간에 정렬 구조를 업데이트 할 수 있습니다.
이 방법을 사용하면 단일 병렬 작업이 완료된 후에도 새 작업을 쉽게 시작할 수 있습니다. 종속성 개수를 업데이트하고 들어오는 종속성이 0 인 모든 작업을 시작하십시오.
이 방법은 동시에 종속성이없는 모든 작업을 처리 할 수있는 충분한 처리 능력이 있다고 가정합니다. 리소스가 부족하고 처리 시간면에서 최적의 솔루션을 고려한다면 문제는 NP 하드 (arne 이미 언급 한 바와 같이)가되므로 더 많은 노력을 기울여야합니다.
원래 질문에 답하기 : 네, 기본적으로 옳습니다. 그러나, 당신은 그러한 독립적 인 작업을 효율적으로 결정하는 방법을 설명하지 못했습니다 (위의 예 참조).
감사합니다. 프랭크, 나는 파헤 치려고합니다. – Alcott
Critical Path Method을 살펴보고 project management에서 가져 왔습니다. 그것은 기본적으로 당신이 필요로하는 것을합니다 : 의존성과 지속 시간을 가진 주어진 태스크는, 그것이 소요될 시간과 각 태스크를 언제 활성화 할 것인지를 생성합니다.
(*)이 기술은 최적의 솔루션을 위해 무한한 수의 리소스가 있다고 가정합니다. 제한된 리소스의 경우 GPRW [현재 + 다음 작업 시간] 또는 MSLK [최소 total slack 시간]과 같은 탐욕적인 알고리즘에 대한 경험적 방법이 있습니다.
(*) 또한 각 작업에 소요되는 시간을 아는 것이 필요합니다.
종속 작업을 실행하기 전에 각 종속성을 병렬로 재귀 적으로 실행하는 것은 어떻습니까? 각 작업이 한 번만 실행되도록하려면 부기가 필요하지만 그렇지 않으면 간단하고 효율적으로 보입니다. –