Parallel programming

  week3 부터는 Scala에서 쓰이는 다양한 Data-Parallel Programming 을 알려준다. 기존 Collection에서 .par 함수를 호출하면 바로 Parallel한 Collection을 얻을 수 있다. 그리고 FoldLeft 는 Parallel 하게 동작할 수 없다는 것을 설명한다.

  foldLeft의 정의는 다음과 같다.

foldLeft[B](z: B)(f: (B, A) => B): B

  foldLeft를 진행 중, f 함수의 리턴 타입 A가 B와 같지 않다면, foldLeft의 다음번 차례에서 함수 매개변수 인자인 B의 위치에 들어갈 수 없다. 이러한 특성 때문에 foldLeft는 Palallel하게 사용할 수 없다.

  foldLeft 대신, fold와 foldLeft를 조합한 aggregate 함수를 제공한다. aggregate 함수는 재귀함수를 통해 Parallel 하게 fold 함수를 진행하다가 특정 threshold보다 낮을 경우에 foldLeft를 수행한 뒤, 다시 합치는 모습을 보여준다.

  그리고, week 3에서 K-means 알고리즘을 토대로한 연습문제를 제공하는데, 이런 심도있는 연습문제를 통해 Parallel Programming이나 Scala 등의 Functional Programming이 어떤 방식으로 쓰일 수 있는지 알려준다.

  마지막 week4에서는 Combinator이라는 trait와(Java에서의 Interface와 비슷한 개념) Conc-tree라는 듣도 보도 못한 새로운 자료구조를 알려준다. Scala의 Collection 들은 Combinator trait의 combine() 함수를 통하여 Parallel 하게 동작하기 위해 쪼개졌던 작은 sub-collection 들을 다시 합치는 동작을 제공한다. Array, Set, Tree 등을 combine할 때 최적화 하기 위한 동작이 서로 다르기 때문에, combine() 함수를 통하여 추상화를 제공한다고 볼 수 있다.

  week4 의 마지막으로 가면서 Conc-Tree 자료구조와 이를 Parallel하게 동작시키기 위한 Combiners 를 소개한다. Conc-Tree 에 특정 element를 추가할 때 걸리는 시간 O(1) 과 Conc-Tree 에 다른 Conc-Tree를 Concatenation을 할 때 O(log N) 을 보장하기 위해 Binary Count System을 사용한다. Concatenation을 할 때 트리의 노드 균형을 맞추기 위해 AVL tree나 Red-Black Tree에서 볼 수 있는 회전 동작도 구현하고 있다. 연습문제를 풀 때, Conc-Tree를 직접 구현하지 않기 때문에 자세하게 살펴보지는 않았지만, 이런 자료구조가 있다는 것을 알고 나중에 사용하면 될 것 같다는 생각이 들었다.

  Parallel Programming 수업을 들었을 때 중요하게 생각한 점은, Associativity 와 Commutativity 같은 수학 개념이 사용되었다는 것이다. 고 수준의 프로그래밍을 할 때, 항상 나의 발목을 잡는 것이 수학 이론이다. 알고리즘에서만 수학이 사용되는줄 알았지만, 다양한 분야에서 수학을 기본으로 프로그래밍을 하고 있다. 처음부터 수학을 다시 공부할 수는 없으니, 문제를 해결하려고 할 때 수학이 등장한다면, 대충 넘어가지 말고 머리 속에 꾸겨 넣어서 다음 task로 넘어가야 겠다.