Parallel computing (Dynamic Programming) - 5 / Nonserial Polyadic DP

Nonserial Polyadic DP : next level의 optimal solution 계산을 위해 바로 이전 level의 optimal subsolution 이외에 다른 것도 필요할 수 있으며 + functional equation에 재귀 식이 여러 개 인 경우.

 

예제 문제1) Optimal Matrix-Parenthesization Problem (Matrix Chain Multiplication)

문제 설명 :

 - A1, A2 ... Ai matrix 가 존재하고 순서대로 곱했을 때 행렬 곱 연산이 가능 (row와 columm 크기가 매칭된다는 의미)

   이 때 행렬 곱을 위해 행렬을 괄호로 묶었을 때 최소 연산 횟수를 찾는다.

 

functional equation

C[i, j] : A i 행렬부터 A j 행렬까지 행렬 곱 연산을 했을 때, 최소 cost

 >>  A i 행렬부터 k 까지 묶고, A (k + 1) 행렬부터 A j 행렬 까지 묶었을 때를 비교해서 최솟 값 저장

- C[i, j] 계산을 위해서 C[i, k], C[k + 1, j]값이 필요한데 이 재귀식의 level은 바로 이전이 아니라 모두 다르고, 값이 두개 필요하기 때문에 nonserial polyadic이다.

- 각 대각선이 level을 나타낸다.

- 각 level에서 C[i, j]를 계산하는데 min{C [i, k] + C [k + 1, j] + ri-1*rk*rj} 비교가 (j - i) 횟수 만큼 필요하고 이는 level l 과 같다.

serial 하게 구현 한 경우 시간복잡도는 O(n^3) 이다.

---

Parallel

n개의 processing elements 가 사용되가 각 processing elements는 하나의 column을 계산한다.

 

추후 내용 update