Parallel computing (Dynamic Programming) - 4 / Serial Polyadic DP

Serial Polyadic DP : next level의 optimal solution 계산을 위해 이전 level의 optimal subsolution을 사용하고, functional equation에 여러 재귀 함수가 필요한 경우.

 

예제 문제1) Floyd's All-Pairs Shortest-Paths Algorithm

문제 설명 : 모든 노드 간의 쌍에 대해서 최단 거리를 구하는 문제. 

 >> 결과는 행렬로 나오고 0번 노드부터 n번 노드까지 각 노드까지 경유를 고려했을 때 최단거리를 계산해 나가면서 계산한다.

 

functional equation

좌항 : k는 노드 번호, 0번 노드 부터 k - 1 노드 까지 고려해서 경유한 경우 최단 거리를 저장하고 있다. (각 level 마다 n^2 계산이 필요)

 >> 우항의 min은 k번째 도시까지 고려할 때, 0번 노드부터 ... k-1번 노드까지 경유 할 수 있다고 고려하고 최단 거리를 저장한다.

k level을 계산 할 때 k - 1 level의 값이 사용 (serial), 좌항 계산을 위해 이전 단계의 두 개의 재귀 식이 필요한 경우가 있기 때문에 (polyadic)이다.

즉, 각 level l 은 l 노드 까지 경유가능 하다고 생각했을 때 각 노드간 최단 거리를 계산한다.

 

 

---

Parallel

n^2 개의 Processing elements를 사용한다. 각 Processing elements들이 x  0 <= x <= n 까지 노드 경유를 고려했을 때의 행렬의 각 원소를 계산한다. PRAM의 경우 이는 상수 시간에 계산능.

0번 노드 부터 n번 노드 까지 고려하기 때문에 병렬 알고리즘의 loop는 n번이기 때문에 총 시간 복잡도는 O(n)이다.

 >> 이 O(n) 총 Processing elements 개수는 n^2 곱하면 n^3인데 이는 serial 알고리즘의 시간 복잡도와 같기 때문에 cost optimal을 보장한다.