Parallel computing (Dynamic Programming) - 2 / Serial Monadic DP
Serial Monadic DP : next solution의 최적 해를 구하기 위해 바로 이전 level의 subproblem의 최적 해의 값이 사용되고, 이러한 DP 식에서 재귀식이 한 개인 경우.
예제 1) The Shortest-Path Problem (최단 경로 문제)
: 시작 노드(S)에서 끝 노드(R) 까지의 최단 경로를 구하는 문제이다.
문제설명 :
- weighted multistage graph(다단계 그래프) 이고 r + 1 개의 levels로 구성되었다.
예시 그림)
- level i의 모든 노드들은 level i + 1 의 모든 노드들과 연결되어 있다. (그림과는 다름)
- level 0 은 시작 노드(S), level r 은 끝 노드(R)로 노드가 1개 뿐이다.
functional equation
>> level r 부터(끝 노드 부터) local optimal 값을 저장해 나가면서 시작점 까지 계산해 나간다.
- 좌항은 level l 인 i 번째 노드부터 끝 노드(R) 까지의 cost
- C0(시작 노드) 최종값을 계산하기 위해서 사용됨.
- level r - 1 에서 끝 노드(R) 까지 가는 cost는 끝 노드가 1개이기 때문에, 우항과 같이 간선의 cost 벡터(n x 1)로 표현 가능
해당 행렬을 level l 에서 level l + 1 까지의 (n x n)개의 노드들의 간선 cost들을 나타냄.
- level l 의 벡터를 구하기 위해서 matrix-vector multiplication이 사용됨.
즉, 각 레벨의 각 노드에서 끝 노드(R) 까지의 최소 거리를 계산하고 저장하면서 시작 노드까지 계산해 나가게 된다.
Parallel
>> n개의 precessing elements 각각이 Cl 벡터 계산을 위해 matrix(n x n) * vector(n x 1) = vetor 에서 결과 벡터의 원소 하나 계산을 담당한다. 한 레벨의 계산에 필요한 시간은 O(n) time에 계산하고 r개의 level을 계산하기 때문에 total time complexity는 O(rn)이다.
PS. serial 하게 처리하는 경우 각 레벨에 필요한 연산량은 행렬 x 벡터 이기 때문에 n^2, 그리고 레벨의 개수가 r 개이기 때문에 O(r * n^2) 이다.
예제 2) 0/1 knapsack problem (배낭 문제)
문제 설명 : 배낭의 용량 c, 배낭에 넣을 수 있는 아이템 i 개 존재
각 아이템은 w(무게)와 p(이익)을 갖는다.
- 용량 x를 초과하지 않는 최대 이익을 내는 아이템 조합을 찾는 문제.
F[i, c] : i번째 아이템 까지, c 의 용량인 경우 이익.
functional equation
max{F [i - 1, x], (F [i - 1, x - wi] + pi)} : i번째 아이템을 선택하거나 선택하지 않는 경우를 식 표현.
F[i, j]를 계산하기 위해 F[i - 1, j] 와 F[i - 1, j - wi]가 필요. >> 이전 level의 row 값이 필요.
* Filling entries in subsequent rows requires two entries from previous row: one from the same column and one from the column offset by the weight of the object.
>> F[i, j]를 계산하기 위해서 이전 level의 값이 필요 (serial), 또한 F[i, j] 계산하기 위한 두개의 subproblems이 하나의 subproblem에만 의존 (monadic)
Parallel
병렬 처리 시 c(capacity)개의 processing elements를 사용하고, 각 row(아이템 개수)의 loop를 돈다면 parallel time complexity는 O(n)이다. -->> PRAM 사용 시
PS. PRAM : P개의 프로세서가 큰 M 공유 메모리를 사용하는 구조.
각 Processing elements들이 분산된 경우
- 모든 Process elements는 아이템의 정보 (무게, 이익)은 가지고 있다.
Distributed Memory Machines 사용 시 각 Processor는 한 column 처리를 담당하는데, F[i - 1, j - wi]를 위해서 다른 Processor의 memory에서 fetch가 필요.
circular shift operation time이 든다.