Mesh-connected computer partial sum(부분합)

MCC에서의 부분합 구하기

  저번 글에서 Bitonic Sort에 대해서 알아보았었는데, 이번에는 좀 더 구체적인 예인 Mesh-connected computer에서의 알고리즘인 Partial sum 대해서 알아보도록 하자. 조금 주제가 뛰어넘는 것 같은데 어찌되었든 병렬컴퓨팅이라는 주제 안에서 저번 글의 연장선상에서 바라보았으면 좋겠다. Mesh-connected computer란 하나의 Node가 최대 4개까지의 연결을 가지는 병렬컴퓨팅의 한 종류이다. 이 글에서는 Distributed Memory를 가정한다.

Mesh-Connected Computer(MCC)의 Critical Path

  빨간색으로 된 경로가 나온 이유는 Partial Sum이 완료되는 1번에 있는 Data는 결국 16번으로 가야하기 때문이다. 1번에서 16번으로 이동하는 경로만 보아도 적어도 Time Complexity는 두 변의 합인 O(n^(1/2))이 됨을 알 수 있다. 

Step 1. Row끼리 데이터 이동

  먼저 Row에서의 데이터 이동은 아래와 같다.

  최종적인 모습은 A1, A1+A2, A1+A2+A3.. 이런 식으로 저장되어야 할 것이다. 그러려면 우선 Row끼리 데이터를 이동해야 한다. 첫 번째 Row에 있는 데이터는 두 번째, 세 번째, 네 번째 Row에도 있어야 한다. 두 번째 Row에 있는 데이터는 세 번째, 네 번째 Row에도 있어야 한다. 세 번째 Row에 있는 데이터는 네 번째 Row에도 있어야 한다. 그렇게 하려면, 아래처럼 단계가 3번 진행되어야 한다.

  Row가 4개 이므로 총 이동은 4-1=3번 일어나게 되는 것이다. 이동할 때마다 Arithmetic 연산인 Sum 연산을 해야한다. 즉 수행해야할 총 명령어는 3×2=6개이다. 다음은 Column에 대해 같은 식으로 이동하면 된다는게 직관적으로 보일 것이다.

Step 2. Column끼리 데이터 이동

  더하는 양이 Row에서 이미 한번 더했기 때문에 많아져서 복잡해보일 뿐이지 사실 Row에서 한 연산과 똑같다. 이 역시 데이터의 Routing과 Sum을 반복한다. Step1과 똑같이 수행해야할 총 명령어는 3×2=6개이다.

Time Complexity in Mesh

  총 데이터 개수를 N개라고 하고, 한 변을 루트N=n이라고 하면, Step 1에서 n-1번의 Data Routing과 Arithmetic Sum이 일어난다. 또한 Step 2에서도 역시 마찬가지로 n-1번의 Data Routing과 Arithmetic Sum이 일어난다. 따라서,

  위 수식이 Mesh에서의 Time Complexity이다.