Mesh-connected computer partial sum(부분합)

Posted by Readiz
2014.04.27 18:31 Creation/Programming

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이다.


저작자 표시 비영리 변경 금지
신고
이 댓글을 비밀 댓글로
  1. 워 -0-
    머리아프다 ㅎㅎ
  2. 댓글 올리기 정말 힘든글을 적어 주셨네요.~ㅋ 역시 이공계의 스멜이....
    • 이건 뭐 이쪽에서는 기초에 해당하는 내용이라서요..
      적고보니 저것보다 더 효율적인 알고리즘이 있네요. ㅠㅠ
    • 2014.04.30 01:55
    비밀댓글입니다
      • 2014.04.30 18:56
      비밀댓글입니다
    • 2014.04.30 02:15
    비밀댓글입니다
    • 답변이 늦어질 것 같아 일단 답변드리면 head에서 주소를 체크하여 기존 body요소를 안보이게 하고 새로운 내용을 넣을 수 있긴 합니다. 물론 티스토리 기존 요소들을 전혀 활용하지는 못하겠지만, 다른 페이지를 로딩시키는게 불가능한건 아닙니다.
      현재 제 블로그 메인을 적용한 것과 비슷하다고 보시면 됩니다. 현재 RSS에서 끌어오고 있는 메인이거든요..
    • 시간 되실때 자세한 설명좀 부탁드릴게요.
  3. 이미지안나오는건 어떻게 해결해야될

티스토리 툴바