알고리즘과 자료구조에 대한 제 열정을 이야기하면 사람들은 어리둥절한 표정을 짓습니다. 대부분 프로그래머가 무슨 일을 하는지는 어렴풋이 알고 있지만, 컴퓨터 과학이 어디에 쓰이는지는 잘 모릅니다. 설령 안다고 해도 실생활과는 관련이 없다고 생각합니다. 간단한 예시 하나로 응용 컴퓨터 과학이 사실 우리 주변 어디에나 존재한다는 것을 보여드리겠습니다.

양말 더미를 정리해야 한다고 상상해 보십시오. 그다지 신나는 취미는 아닙니다. 이 일을 너무 오래 미뤄온 탓에 끝내는 데 족히 한 시간은 걸릴 것입니다.

여러 선택지를 고민하다 결국 도움을 받기로 합니다. 친구와 함께 작업에 들어가니 대략 절반의 시간 만에 끝납니다.

컴퓨터 과학자라면 이 양말 더미를 자원이라고 부를 것입니다. 당신과 친구는 가차 없이 워커로 격하됩니다. 두 사람은 같은 문제를 동시에, 즉 병렬로 작업할 수 있습니다. 이것이 바로 병렬 컴퓨팅의 핵심입니다.

양말 정리가 병렬 처리에 특히 잘 맞는 데에는 몇 가지 이유가 있습니다.

• 작업이 깔끔하게 나누어집니다. 어떤 워커든 양말 한 켤레를 찾는 데 걸리는 시간은 대략 비슷합니다.
• 다른 켤레를 찾는 일은 완전히 독립적인 작업이라 동시에 진행할 수 있습니다.

이 작업에 투입하는 워커가 많을수록 더 빨리 끝납니다.

• 워커 1명이면 60분이 걸립니다.
• 워커 2명이면 30분이 걸립니다.

그렇다면 워커 3명이면 얼마나 걸릴까요? 맞습니다. 약 20분입니다. 이 관계를 간단한 공식으로 나타낼 수 있습니다.

물론 이 공식은 정확하지 않습니다. 오버헤드를 빼먹었기 때문입니다. Mary가 양말 하나를 집으려 할 때 Stephen도 같은 양말에 손을 뻗을 수 있습니다. 두 사람은 서로 웃으며 한 명이 다른 양말을 집습니다. 컴퓨팅에서도 워커가 마찬가지입니다. 웃지는 않지만 다른 작업을 집는다는 점은 같습니다. 많은 워커가 자원을 공유하면 이런 상황이 꽤 자주 발생합니다. 그리고 상황을 해결하는 데는 언제나 약간의 추가 시간이 듭니다. 그래서 최적의 정리 속도에는 조금 못 미치게 됩니다.

하지만 상황은 더 나빠질 수도 있습니다. 양말 100개에 워커가 100명 있다고 가정해 보겠습니다. 처음에 모든 워커가 양말을 하나씩 집어 짝을 찾으려 합니다. 문제는 바로 여기에 있습니다. 각자 하나씩 집는 순간 양말이 하나도 남지 않습니다. 모든 워커가 대기 상태에 빠집니다. 정리는 영원히 끝나지 않습니다. 이것이 바로 교착 상태(deadlock)이며, 병렬 컴퓨팅에서 가장 두려운 시나리오 중 하나입니다.

이 경우 간단한 해결책은 양말을 다시 내려놓고 잠시 기다렸다가 다시 집어 보는 것입니다. 딜레마를 벗어나는 또 다른 방법은 정리를 위한 일종의 ‘프로토콜’을 강제하는 것입니다. 프로토콜을 공동의 목표를 달성하기 위한 워커들 사이의 암묵적인 합의라고 생각하면 됩니다.

예를 들어 각 워커가 한 가지 색상의 양말만 맡는 것입니다. 워커 1은 초록색 양말을, 워커 2는 회색 양말을 맡는 식입니다. 이 간단한 방법으로 교착 상태를 피할 수 있습니다. 완전히 분리된 작업을 하게 되기 때문입니다.

하지만 여전히 문제가 남습니다. 만약 초록색 양말은 네 개뿐이고 회색 양말은 4000개라면 어떻게 될까요? 워커 1은 금방 할 일이 없어질 것입니다. 양말 두 켤레를 순식간에 정리하고는 워커 2가 나머지를 정리하는 모습만 지켜봐야 합니다. 그것이 과연 팀워크라고 할 수 있습니까?

이런 식으로 작업을 나누는 것은 색상별로 양말 수가 대략 비슷하다고 가정할 수 있을 때 가장 합리적입니다. 그래야 모두가 비슷한 양의 작업을 나누어 가질 수 있습니다.

다음 히스토그램을 보면 제가 말하는 바를 쉽게 이해할 수 있습니다.

이 경우에는 색상별로 더미 크기가 거의 비슷합니다. 모든 워커에게 공평한 작업량처럼 보입니다.

두 번째 경우에는 분포가 고르지 않습니다. 이 예시에서 회색 양말 더미는 정말 정리하고 싶지 않습니다. 조금 더 깊이 고민해야 합니다.

어떻게 하면 좋을까요?

대부분의 경우 작업을 나누는 다른 방법을 생각해 보면 도움이 됩니다. 예를 들어 큰 회색 더미를 두 명이 함께 정리하게 할 수도 있습니다. 한 명은 큰 양말을, 다른 한 명은 작은 양말을 맡는 식입니다. 하지만 여기서 또 다른 문제가 생깁니다. 누가 ‘큼’과 ‘작음’의 기준을 정합니까?

그래서 더 영리한 방법을 깊게 고민하는 대신, 여기서는 실용적으로 접근하기로 합니다. 모두가 색상이나 크기에 상관없이 그냥 같은 크기의 더미를 하나씩 집어 작업을 시작하는 것입니다.

대부분 각 더미에는 짝을 찾지 못한 양말이 몇 개 남게 됩니다. 괜찮습니다. 그냥 남은 양말을 모두 한데 모아 섞은 뒤 다시 새로운 더미를 만들어 정리하면 됩니다. 끝날 때까지 이 과정을 반복합니다. 이를 작업 큐(task queue)라고 부릅니다. 두 가지 장점이 있습니다. 첫째, 워커들 사이에 추가적인 합의가 필요 없고, 둘째, 문제 영역에 대해 깊게 고민하지 않아도 워커 수에 따라 꽤 잘 확장됩니다.

분산 시스템의 까다로운 점은 언뜻 간단해 보이는 해결책이 실제로는 처참하게 실패할 수 있다는 데 있습니다.

만약 우리의 작은 더미들이 이렇게 생겼다면 어떨까요?

각 더미 안에서 찾을 수 있는 짝의 수는… 참담한 수준입니다. 우리가 할 수 있는 일 중 하나는 아주 간단한 사전 정리 단계를 거쳐 짝의 수를 늘리는 것입니다. 혹은 여러분이 더 나은 아이디어를 떠올릴지도 모릅니다.
멋진 점은, 일단 더 빠른 방법을 찾고 나면 비슷한 다른 작업에도 그대로 적용할 수 있다는 것입니다.

이런 문제들은 컴퓨터 과학에 뿌리를 두고 있으며 어디에서나 찾아볼 수 있습니다. 개인적으로 저는 ‘Computer Science’라는 용어를 그다지 좋아하지 않습니다. 저는 독일어인 “Informatik”이라는 말을 더 선호하는데, 굳이 번역하자면 ‘정보 과학’ 정도가 될 것입니다. 우리가 여기서 진정으로 하는 일의 본질은 한 부류의 문제 전체를 해결하는 일반적인 방법을 찾는 것이기 때문입니다. 우리는 객체의 본질과 그 속성에 대해 고민합니다. 우리는 양말을 정리하는 것이 아니라 정보의 근본적인 질문에 답하려 하는 것입니다. 이제는 제가 왜 이 주제에 그토록 열정적인지 이해하실 수 있을 것입니다.

아, 그리고 제가 프로그래밍을 사랑하는 이유에 대한 관련 글도 있습니다.