[Coursera] Parallel programming

Parallel programming

  Coursera mooc 중 Functional Programming in Scala 의 3번째 강의이다. 1,2번째 강의에서 배운 Scala 기본, 심화 과정을 이용해 Parallel Programming을 주로 다루는 강의이다. 1,2의 강의를 듣지 않더라도, Scala에서 제공하는 Collection을 어느 정도 다룰 줄 안다면, 이 강의만 수강해도 무방할 듯 하다.

  week1에서는 Parallel Programming 이론 및 Java, JVM에서 다루는 Parallel Programming 방법 등을 다룬다. Java 언어를 가지고 Multi-Thread 프로그램을 작성했다면, 빠르게 이해하며 넘어갈 수 있다. 그리고 앞으로 진행할 수업 과정에서 Parallel Program에 대하여 어떻게 성능을 측정하는 지를 다룬다.

  week2 부터 본격적으로 Parallel Programming에 대하여 다룬다. 기본적인 내용으로 merge sort를 parallel 하게 구현하는 방법을 알려준다. 그리고 Fold(Reduce) 에 관한 내용에 대해 설명한다. 이 때, Fold를 수행하기 위한 Iterable[T] 객체가 있을 때, type T가 Associative 해야 Parallel Fold 작업이 항상 같은 값을 리턴한다는게 주 내용이다. 여기서 말하는 Associative는 다음과 같다.

연산 + 가 있을 때,

A + (B + C) = (A + B) + C 를 만족하면

+ 연산은 Associative 하다는 것이다. (흔히 말하는 결합법칙)

  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로 넘어가야 겠다.