김 용묵의 절대공간 - 블로그

* 세이무어 크레이(Seymour Cray 1925-1996).
슈퍼컴퓨터의 선구자로, 오로지 더 빠른 컴퓨터를 만드는 데에만 미쳐 있었던 최적화 덕후이자 뼛속까지 공돌이. 외곬수 외길 인생의 대표주자이다. 요즘으로 치면 오버클럭에 목숨 건 컴덕후와도 비슷한 듯.

그는 어린 시절부터 전기 공학 덕후였고, 나중엔 하드웨어 회로 및 컴퓨터 아키텍처 설계와 소프트웨어 디자인까지 통달한 기술자가 되었다. 그는 크고 연산 능력도 뛰어난 슈퍼컴이라는 물건을 머리에 떠올리고, 그 복잡한 기계를 장인 정신으로 수제로 일일이 설계하여 만들었다.;; 보통 능력이 아니다.

왕년에 잘 나가던 슈퍼컴의 대명사이던 '크레이'는 응당 그의 이름에서 유래된 명칭이다. 자동차뿐만 아니라 컴퓨터계에도 이런 장인이 있었다니! 물론, 1960년대에 개발된 슈퍼컴은 오늘날의 PC AT/286 수준이었고, 1980년대의 슈퍼컴이 오늘날의 펜티엄 4 정도의 성능이었다만, 그 성능을 그 옛날에 트랜지스터 배선으로 실현해 낸 것만 해도 어디냐. (마이크로프로세서 기반인 오늘날의 PC보다 대략 20년 정도 앞선 사양?) 일기예보, 탄도 계산, 핵실험 시뮬레이션을 그 기계로 다 했다.

그러나 그는 반도체의 집적도가 인간의 장인 정신과 근성으로 커버 가능한 수준을 넘어간 뒤에도, 재래식 생산 공정을 끝까지 고수하였고 시대의 흐름을 따르지 못했다. 또한, 느리고 저렴한 컴퓨터라도 다수를 병렬로 연결하면 작업의 throughput을 충분히 올릴 수 있고 그게 실용성이 뛰어남에도 불구하고 그는 그런 타협적인(?) 발상을 인정하지 않았다. 그러니 그의 고집만이 반영된 슈퍼컴은 시간이 흐르면서 시장에서 시장성과 상업성을 얻을 수 없었다.

그는 병렬 프로그래밍의 가능성에 대해, 내가 살아 있는 동안은 그게 지금 수준 이상으로 더 발전하는 일이 없을 거라고 부정적으로 일축했다. 그러나 그가 70대 초반의 나이로 1996년에 교통사고로 급사한 뒤, 그때부터 묘하게도 병렬 구조 슈퍼컴퓨팅은 초고속으로 발전하기 시작했다. 그의 예상은 빗나가지 않았다.;;

오늘날의 슈퍼컴퓨터 시장엔 슈퍼컴용 전용 CPU가 달린 물건은 없다. 과거에 IA64 아키텍처가 완전히 망한 것과도 비슷한 맥락. 그 대신 역시 Xeon 인텔/AMD 양산형 CPU와 GPGPU가 무수히 많은 코어들을 이루고, 이것들이 신경망 같은 bus들로 촘촘히 연결되어 병렬 연산을 수행한다. 규모의 경제학에 따르면 닥치고 x86이 영원할 수밖에~ 슈퍼컴은 크레이가 바라던 것과는 완전히 다른 양상으로 바뀌었다.

196, 70년대에는 슈퍼컴퓨터라 해도 병렬, 멀티스레드 같은 개념이 오늘날처럼 흔하지 않았으며 듀얼코어 같은 개념도 없었기 때문에, 그 시절의 유물인 C언어조차도 라이브러리가 멀티스레드를 고려하지 않고 설계되었다고 볼 수 있겠다.
예나 지금이나 슈퍼컴퓨터는 가격이 억 소리 나게 방대하며, 한번 돌리면 정말 전기 먹는 하마이다. 열도 장난이 아니게 많이 나온다.

Posted by 사무엘

※ 들어가는 말

정렬은 검색과 더불어 컴퓨터가 인간에게 유용한 결과물을 내놓기 위해 내부적으로 가장 빈번히 수행하는 계산 동작에 속한다. 다른 알고리즘의 내부 과정으로 즐겨 쓰이기도 하고 말이다. 전산학 내지 컴퓨터 과학에서 정렬 문제가 얼마나 중요한지에 대해서는 더 말이 필요하지 않다.

정렬은 문제의 목표가 너무나 명확하고 실용적이며, 다양한 관점에서 문제의 접근이 가능하고 좋은 알고리즘과 나쁜 알고리즘의 차이도 아주 드라마틱하게 알 수 있기 때문에... 예로부터 그 특성과 해법이 연구될 대로 연구되어 왔다. 시간 복잡도 관념이 없던 초짜 프로그래머가 O(n^2)와 O(n log n)의 어마어마한 차이를 깨우치는 계기도 대체로 정렬 알고리즘을 공부하고부터이다.

n개의 원소에 대한 정렬 작업은 n개의 원소를 임의의 방식으로 늘어놓는 n!가지의 순열 중에, 원소들의 값 순서가 오름차순이나 내림차순이 유지되는 순열을 선택하는 작업이라고 볼 수 있다. 그리고 일반적인 정렬 알고리즘은 임의의 두 원소와의 비교를 통해 거기서 가능한 선택의 범위를 좁혀 나간다.

이런 원론적인 분석을 통해, 비교 연산 기반 정렬 알고리즘의 시간 복잡도는 아무리 기가 막힌 알고리즘을 고안하더라도 O(n log n)보다는 결코 더 좋을 수가 없다는 것이 증명되어 있다. 그리고 정렬 알고리즘 중, 제자리(in-place)라는 특성을 지닌 알고리즘은 교환(swap)이라는 동작도 공통적으로 사용하게 된다.

정렬 문제는 NP 완전 문제라고 알려져 있는 외판원 문제(TSP)에서 정점(vertex)들이 일렬로 쭉 나열되어 있는 특수한 경우라고 볼 수도 있다. 가까운 순서대로 순서대로 방문하는 게 정답일 테니 결국 정점들이 정렬된 것이나 마찬가지이다. 비록 domain이 1차원이 아닌 2차원 이상으로 가면 난이도가 곧바로 안드로메다 급으로 치솟지만 말이다.

※ O(n^2) 또는 O(n log n)인 비교 기반 알고리즘

역사적으로 굉장히 많은 수의 정렬 알고리즘이 고안되었으며 이들은 제각기 장단점과 특성이 있다. 알고리즘을 평가하는 주 잣대로는 자료 개수 n에 대한 시간 복잡도와 공간 복잡도가 있으며, 이들도 평균적일 때와 최악의 상황일 때를 따로 평가한다. 이 외에도 자료의 상태에 성능이 민감하게 달라지는지, 그리고 값이 같은 원소의 상대적인 순서가 보존되는지를 나타내는 순서 안정성(stability)을 따지기도 한다.

시간 복잡도가 O(n^2)에 속하는 정렬 알고리즘은 일명 '발로 짠 알고리즘'에 속한다. 직관적이고 구현하기 매우 쉬우나 성능이 쥐약이라는 뜻.
거품 정렬, 선택 정렬, 삽입 정렬이 대표적인데, 거품의 경우 배열이 아니라 아예 random access가 불가능한 연결 리스트 같은 컨테이너에다가 적용해도 좋을 정도로 바로 옆 원소와의 비교와 교환밖에 하지 않는다. 그 때문에 성능이 대단히 나쁘다.

선택 정렬은 비교에 비해 대입 연산이 적고 자료의 상태에 그리 민감하지 않은 게 특징이다. 그에 반해 삽입 정렬은 자료 상태에 따른 성능 편차가 크고 O(n^2) 알고리즘 중에서는 성능이 나은 편이기 때문에, 작은 범위의 입력에 한해서 종종 쓰이는 경우가 있다. 실제로 비주얼 C++의 qsort 함수 구현을 보면, 퀵 정렬을 쓰다가 구간이 8개 이하의 원소로 감소하면 거기는 삽입 정렬로 때운다.

O(n^2) 알고리즘들은 원리가 간단하기 때문에 공간 복잡도는 대체로 O(1)인 in-place이다. 한 쌍의 원소를 그때 그때 교환하기 위한 고정된 크기의 메모리밖에 쓰지 않는다는 뜻 되겠다. 시간이 비효율이면 공간 오버헤드라도 없어야 하지 않겠는가.

이론적인 시간 복잡도에 부합하는 O(n log n)급 알고리즘으로는 힙, 병합, 퀵 등이 있다. 이들은 시간 복잡도만 동일할 뿐 내부적인 특징은 정말 제각각이다.

일단 힙 정렬은 위의 세 알고리즘 중에서 유일하게 메모리 복잡도가 O(1)인 검소한 녀석이다. 그 대신 한 배열 안에서 왔다 갔다 하는 작업이 많아서 그런지 속도는 미세하게 다른 알고리즘보다 더 느린 편. 한 배열 안에서 heap 자료구조를 만든 뒤, 이것으로부터 정렬된 형태의 배열을 역순으로 만드는 두 단계의 과정이 무척 기발하며, 인간의 머리로 어째 이런 걸 생각해 낼 수 있는지 놀라움을 느낀다.

병합 정렬은 동급 시간 복잡도 알고리즘 중에서는 꽤 직관적인 편이고 또 유일하게 안정성도 있어서 좋다. 그러나 FM대로 구현한 녀석은 배열 복사본이 하나 더 필요하기 때문에 메모리 복잡도가 O(n)이나 되며, 대입에 대한 비용이 큰 자료구조에 대해서는 성능 하락의 폭이 큰 게 흠이다.

※ 퀵 정렬

한편, Tony Hoare이라는 영국의 전산학자가 1960년대에 20대 중반의 나이에 고안한 퀵 정렬은 정렬 알고리즘계의 종결자, 야생마, 이단아 같은 존재이다. pivot이라 불리는 중간값을 설정하여, 주어진 구간을 “pivot보다 작은 값, pivot, pivot보다 큰 값” 조건을 만족하게 swap 연산을 통해 바꾼다. 그 뒤, pivot을 기준으로 구간을 양분하여 양 구간도 재귀적으로 똑같은 작업을 한다. 알고리즘도 너무 명쾌하고 깔끔하지 않은가?

이 알고리즘은 대충 부분적으로 정렬되었거나 아예 완전히 무작위인 데이터에 대해서 매우 대단히 좋은 성능을 자랑한다. 그러나 pivot을 어떻게 정하느냐에 따라서 알고리즘의 성능이 크게 좌지우지되며, 자료의 상태에도 매우 민감해진다는 점이 간과될 수 없는 특성이다.

pivot이 데이터의 적당한 중간값으로 설정되지 못하고 하필이면 최소값이나 최대값으로 설정된 경우, 알고리즘 수행 후에도 구간은 깔끔하게 양분되지 못하고 하나씩만 줄어들게 된다. 이 경우 알고리즘의 수행 시간은 O(n log n)이 아니라 O(n^2)에 가까워진다! 역순으로 정렬된 데이터를 정렬하는데 구간의 맨 앞이나 맨 뒤의 값을 pivot으로 쓴다고 생각해 보자.

문제는 이때 시간 복잡도만 늘어나는 게 아니라는 것이다. 분할 정복법을 쓴다는 특성상 퀵 정렬은 재귀호출을 써서 구현되는데, 구간이 반씩 시원하게 안 쪼개지고 하나씩만 쪼개지면 재귀호출의 깊이도 자칫 n회가 될 수 있다는 뜻이다. 이 경우 프로그램은 stack overflow 오류가 발생하며, 이는 프로그램의 보안에도 악영향을 끼치게 된다.

다만, 쪼개진 구간 중에 원소 수가 많은 구간이 아니라 의도적으로 적은 구간부터 골라서 재귀적으로 처리하는 경우, 메모리 복잡도는 O(log n)으로 원천적으로 줄일 수 있다. 퀵 정렬 함수의 구현체 자체에 딱히 동적 배열 같은 게 없더라도 재귀호출 때문에 메모리 복잡도가 올라가며, 원소들이 정확하게 반씩 분할될 경우에 log n에 해당하는 깊이까지 간다는 뜻이다.

일반적으로 퀵 정렬의 구현체는 그냥 구간의 정중앙에 있는 원소만 pivot으로 지정하는 게 보통이다. 이렇게만 하더라도 O(n^2)의 최악 시간 복잡도를 만드는 입력 데이터를 일부러 만들기란 대단히 어려우며, 수학적으로 발생하기도 불가능에 가까운 건 사실이다.

하지만 공격자가 퀵 정렬 구현체의 알고리즘을 알고 있는 경우, 의도적으로 해당 알고리즘이 pivot을 요청할 만한 위치에 일부러 구간의 최대값이나 최소값을 집어넣어서 매 단계별로 퀵 정렬을 엿먹이는 게 불가능하지는 않다! 세상엔 그것만 전문적으로 연구한 사람도 있다. anti quick sort라고 검색해 보셈.. 이것이 퀵 정렬의 진정 오묘하고 이상한 면모라 하겠다.

이걸 이용하여 비주얼 C++의 qsort 함수로 테스트하면, 평소 같으면 인텔 i5 기준 눈 깜짝할 사이에 끝나는 정수 10만 개의 정렬이 수 초 대로 떡실신하는 기현상이 벌어지는 걸 볼 수 있다. 그런데 xcode의 C 라이브러리가 제공하는 qsort는 퀵 정렬을 쓰지 않는지 그런 것의 영향을 받지 않더라..

※ C/C++ 언어에서의 지원

C 라이브러리에 있는 qsort 함수는 콜백 함수에 전달해 줄 사용자 데이터--가령, 비교 옵션 같은 것--를 받는 부분이 없어서 무척 불편하다. 그래서 별도의 사용자 데이터는 전역 변수나 TLS(thread local storage)를 통해 얻어 와야 하는 번거로움이 있다. 이것이 비주얼 C++ 2005부터 도입된 qsort_s에서는 개선되었다.

한편, C++ 라이브러리에도 잘 알다시피 std::sort라는 함수가 있다. C 함수보다 type-safe할뿐만 아니라 iterator를 통해 포인터보다 더 추상적인 자료형도 정렬할 수 있으며, 비교도 직관적인 비교 연산자 아니면 functor로 편리하게 지정할 수 있어서 좋다. 또한 이건 템플릿 형태이기 때문에 정렬 코드가 해당 프로그램의 번역 단위에 최적화된 형태로 embed된다는 것도 더욱 좋다.

C의 경우 비교 연산 함수의 리턴값은 뺄셈 연산을 모델로 삼아서 '음수, 0, 양수' 중 하나를 되돌리게 되어 있다. 그러나 C++ 버전은 < 연산을 모델로 삼아서 그냥 true/false boolean값만 되돌리면 된다는 차이가 있다. 사실, 그것만 있어도 정렬이 되니까 말이다.

C++ 라이브러리에는 sort뿐만이 아니라 stable_sort도 있다. 하지만 실생활에서 꼭 stable_sort를 써야만 할 상황이 있는지는 모르겠다. 실제로 정렬 성능은 굳이 안정성이 지켜지지 않아도 되는 sort가 더욱 뛰어나다.

※ 기타 정렬 알고리즘

정렬 알고리즘의 시간 복잡도는 굳이 O(n^2) 아니면 O(n log n) 중 하나로만 떨어지는 게 아니다. 그 범주에 속하지 않는 대표적인 알고리즘은 셸 정렬이다. 고안자의 이름을 따서 명명된 이 알고리즘은 삽입 정렬이 대충 정렬된 자료에 대한 성능이 뛰어나다는 점을 응용하여, 삽입 정렬을 일정 구간별로 띄엄띄엄 반복해서 적용해 준 뒤 최종적으로 삽입 정렬을 full scale로 한번 돌려서 정렬을 끝낸다.

퀵 정렬이 pivot을 정하는 것이 판타지라면, 셸 정렬은 그 구간을 정하는 방식이 판타지이다. 셸은 분명 O(n^2)보다는 훨씬 더 뛰어난 성능을 보이지만 그렇다고 O(n log n)급은 아니다. 사실, 셸은 구간을 어떻게 설정하느냐에 따라서 시간 복잡도를 계산하기가 대단히 chaotic하고 어렵다.

구간을 두 배씩 좁히는 게 제일 나쁜 방법이이기 때문에 최악의 경우 도로 O(n^2)까지 떨어져 버리나, 약간 머리를 쓰면 O(n^1.5) 정도는 된다. 구간을 가장 잘 잡았을 때 최대 O(n (log n)^2)까지는 갈 수 있다는 것이 알려져 있다. 그래도 셸은 메모리 복잡도가 깔끔한 O(1)이고, 코딩이 상당히 짧고 간결하면서도 O(n^2)보다는 성능이 확실히 낫다는 데 의의가 있다.

앞서 말했듯이 정렬 알고리즘의 시간 복잡도의 한계가 O(n log n)이라는 것은 비교 연산을 사용하는 일반적인 알고리즘이 그렇다는 소리이다. 그런 방식으로 정렬을 하지 않는 알고리즘의 경우, O(n)짜리 알고리즘도 충분히 존재할 수 있다.

가령, 데이터의 도메인이 메달이어서 '금, 은, 동'이라는 세 종류밖에 없는 경우, 자료를 일일이 뒤져 볼 필요 없이, 각 메달의 개수를 세어서 금 a개, 은 b개, 동 c개라고 써 주기만 하면 될 것이다. 부동소숫점이나 문자열처럼 도메인이 굉장히 넓은 자료형은 그런 식으로 정렬할 수 없겠지만, 좁은 범위의 정수 정도면 그런 식으로 발상을 전환하여 비교 연산을 요청하지 않는 정렬 알고리즘을 쓸 수도 있다.

여기에 속하는 대표적인 알고리즘은 기수(radix) 정렬이며, 이 외에도 유사한 전략을 사용하는 알고리즘이 더 있다.

정렬 알고리즘에 대해서는 메아리 풉에도 수학적으로 더 엄밀한 개념 기술이 있으므로 참고하시고, 또 이 홈페이지에는 이미 아시는 분도 있겠지만 본인이 학부 시절에 정렬 알고리즘 모음집이라는 간단한 프로그램을 짜서 올려 놓은 게 있다. 일부 검색엔진에서는 '사이트'로도 등록되어 있다. ㅎㅎ 관심 있으신 분은 거기 소스도 참고하시기 바란다.

* 여담이지만, 전산학 덕후와 해커들의 머리 싸움 덕질에는 끝이 없는지라, 퀵 정렬뿐만 아니라 hash 알고리즘을 엿먹이는 연구도 이미 될 대로 돼 있다.. 특정 해싱 알고리즘에 대해서 충돌만 골라서 일으키는 입력을 생성하는 것 말이다.

Posted by 사무엘

굳이 전산학이나 컴퓨터과학· 공학의 전공자가 아니어도, 그리고 현업 프로그래머가 아니더라도 조금만 기계 다루는 것에 조예가 있는 컴덕후라면 요즘 컴퓨터의 발전 추세가 어떤지는 다들 알 것이다. 사실은 <날개셋> 한글 입력기의 개발자인 본인보다도 더 잘 알 것이다.

튜링 완전하며 메모리로부터 프로그램을 읽어 와서 구동하는(프로그램 내장 방식) 범용 컴퓨터가 발명된 지가 아직 100년은커녕 반세기 남짓밖에 지나지 않았다. 그러나 컴퓨터의 속도와 메모리 용량은 가히 넘사벽급으로 발달했다. 컴퓨터는 지난 수십 년 동안 자연이 아니라 인간의 발명한 물건의 내부에서, 시간에 따른 지수함수 스케일의 발전을 볼 수 있던 얼마 안 되는 엄청난 분야였다.

그러나 그것도 한계는 있어서 컴퓨터 성능의 대표적인 지표이던 클럭 속도가 2003년 즈음에 놀랍게도 지수함수적인 성장이 멈췄다. 10년까지는 아닌 거 같다만 8, 9년 전의 PC나 지금의 PC나 다 3GHz대이다. 오늘날과 같은 반도체 회로라는 근본적인 패러다임이 바뀌지 않는 한, 전력 소모와 발열 때문에 컴퓨터의 기본 동작 자체만의 속도가 더 빨라질 수는 없다.

우리가 다루는 컴퓨터는 생각보다 굉장히 정밀하고 빡세게 만들어져 있다. 예전부터 파이프라인, pre-fetching 등 온갖 있는 테크닉, 없는 꼼수를 다 동원해서, 어떻게든 낭비되는 자원이 없이 모든 자원이 계산에 동원되고, 1ms라도 속도를 더 올리려고 공돌이들의 온갖 공밀레 연구가 동원되었다. 이런 수직적인 성장이 한계에 달하니 요즘 컴퓨터는 코어 수를 늘려서 분업이라는 수평적인 성장을 추구하고 있다.

100이라는 일이 있어서 이게 2GHz짜리 컴으로 다 처리하는 데 10이라는 시간이 걸린다면, 1GHz짜리 컴으로는 20만큼의 시간이 걸릴 것이다. 그러나 1GHz 짜리 컴이 2개 있어서 그 일을 정확히 50씩 분담할 수 있다면, 각각의 컴퓨터의 최대 속도는 비록 1GHz밖에 안 되더라도 10에 가까운 시간 만에 일을 끝마칠 수 있어서 2GHz에 준하는 효과를 낼 수 있다. 이것이 기본적인 아이디어이다.

물론, 딱 10으로 줄이지는 못한다. 일을 분할하고 두 대의 컴퓨터를 세팅하고 굴린 후, 두 컴퓨터(코어)가 내놓은 결과를 취합하는 오버헤드가 역시 결코 작지 않기 때문이다. 그리고 세상에 상호 의존성이 없이 역할을 저렇게 딱 분담할 수 있는 작업이란 흔치 않다.

방대한 계산이 필요한 작업을 다수의 컴퓨터 기계들을 여러 대 동원해서 수행하는 건, 분산 컴퓨팅이라 하여 예전부터 그리 생소한 개념이 아니었다. 3D 그래픽으로 영화를 만드는 업계에서는 rendering farm이라 하여 수많은 컴퓨터들을 농장에다 비유할 정도로 열나게 굴려서 영상을 만들어 낸다. 빌드 속도가 느린 걸로 악명 높은 C++ 언어를 위해서 Incredibuild라는 이스라엘산 분산 빌드 시스템도 있다.

그런 것처럼 개개의 컴퓨터도 이제 코어가 여러 개 돌아가고 멀티스레딩 능력이 충분히 뛰어나니, 이제는 프로그램 차원에서 멀티코어-aware한 개발이 필요해졌다. 왜냐하면 분산 처리 시스템을 설계하는 건 정말 머리가 뽀개질 정도로 복잡하기 때문에 컴퓨터나 컴파일러가 자동화를 해 줄 수 없다. 예전 계산 결과에 의존적인 다음 계산을 병렬로 동시 수행시킬 수는 없는 노릇이니까 말이다.

그렇기 때문에 멀티코어-aware하지 않은 옛날 프로그램은 컴퓨터가 언제나 최악의 case로 가정하고 보수적으로 돌려서 코어를 하나만 할당하여 돌아가게 된다. 한 프로그램이 while(1); 만 하고 가만히 있다 해도 CPU 사용률이 100%로 치솟지 않는다.

특히 C/C++의 포인터는 그야말로 아무 메모리 주소나 가리킬 수 있고, *a, *b가 있으면 둘이 가리키는 주소가 같을지 아닐지 등 최적화나 병렬화를 할 여지가 없을 정도로 너무 generic하기 때문에 오히려 처리가 어렵다고 한다. 파스칼이나 포트란처럼 언어 표현력이 C/C++보다 부족한 대신에 컴파일러가 소스 코드만 보고서 그 복잡도를 어느 정도 파악할 수 있는 언어가 병렬화에는 오히려 더 유리하다고.

그래서 소스 코드의 특정 구간에 대해서 컴파일러나 CPU가 안심하고 병렬화를 할 수 있게 중간 중간에 부가정보를 인위적으로 넣어 줄 필요가 생겼는데, 이런 부가정보를 기술하는 표준 규격 중 하나가 그 이름도 유명한 OpenMP이다. #pragma omp 같은 컴파일러 지시자도 있고, OpenMP 라이브러리보부터 호출해서 쓰는 함수도 있다.

옛날에 C언어가 처음 발명되던 시절엔 최적화를 위해서 변수를 가능한 한 레지스터에 올려라고 지시하던 register라는 카워드가 있었는데, 앞으로 C/C++ 같은 네이티브 코드 언어는 멀티코어를 언어 차원에서 수용하는 규격이 덩달아 생겨야 할 것이다.

물론, CreateThread 같은 함수를 써서 코드의 로직 차원에서 대놓고 여러 작업 스레드를 만들었다면, 단일 프로세스가 여러 개의 코어를 자연스럽게 점유하는 게 응당 가능하다. 그러나 디자인의 성격상, 멀티스레딩은 보통 일하는 스레드, 사용자 UI 스레드, 입출력 신호를 기다리는 스레드처럼 용도별로 달리 배당하는 게 바람직하지, 동일한 일을 하는 코드 내부에서 굳이 다중 코어 활용을 위해 스레드를 분할하기에는 동기화를 비롯해 일이 너무 복잡해진다. 서버 같은 게 아니라면, 제각기 CPU를 full로 사용하는 여러 작업 스레드를 만들 일 자체가 매우 드물다.

이때 멀티코어 프로그래밍을 잘 하면 이런 단일 코드가 명시적인 스레드 생성을 하지 않고도 CPU의 자원을 골고루 전부 활용해서 고성능으로 돌아가게 된다. 다만 앞서 말했듯이 이렇게 작업을 분할하는 오버헤드부터가 큰 편이기 때문에, 소규모 작업보다는 동영상 인코딩이나 대용량 파일 압축이나 컴파일 같은 진짜 방대한 작업에서 멀티코어의 진가는 더욱 두드러질 것이다.
일례로, 비주얼 C++은 2005부터 빌드할 때 병렬 컴파일이 수행된 경우, 빌드 로그에 해당 빌드를 수행한 코어의 번호가 뜬다.

O(n^3)짜리 행렬 곱셈은 워낙 단순 무식하고 복잡한 의존도 따위도 없는 순수 노가다이다 보니, “나 병렬화 해 주세요”라고 온몸으로 외치는 문제라고 볼 수 있다. 퀵 정렬이나 병합 정렬처럼 구간이 딱딱 나뉘는 알고리즘이 병렬화에도 적합한 구조일 것 같긴 하다만, 요즘 컴퓨터의 성능이라면 겨우 internal sort 규모의 정렬 작업은 굳이 멀티코어를 쓸 필요도 없을 정도로 금방 끝날 듯.

요컨대 이제는 고성능 컴퓨터를 쓰는 것만으로 프로그램의 수행 속도가 저절로 올라가는 시대는 끝났다. 그 다음으로 레지스터 배당이라든가 캐시나 파이프라인 적중률 같은 건 CPU 설계에 맞춰 컴파일러가 더 똑똑해야 하는 영역인데, 이 역시 튜닝의 수준은 예술의 경지에 도달해 있다. 그리고 그 다음으로 필요해진 것이 코드에 등재되어 있는 병렬화 가능성 정보라고 생각하면 되겠다. 멀티코어는 프로그래머가 잘 숙지하고 있어야 하는 프로그래밍 패러다임이 되었음이 틀림없다.

Posted by 사무엘

전산학 전공자 내지 IT 분야 종사자에게는 상식으로 통용되는 당연한 개념이다만..
오늘날 범용(generic-purpose) 컴퓨터에서 돌아가는 소프트웨어는 크게 세 가지 형태로 나뉜다.

1. 로컬

흔히들 PC로 대표되는 컴퓨터에서 stand-alone으로 동작하는 전통적인 프로그램이다. Windows야 그렇다 치더라도 오피스, 비주얼 스튜디오 같은 업무용 프로그램은 아직 로컬 프로그램의 아성을 무너뜨릴 영역이 없다.
가장 역사가 길고, 가장 빠르고 효율적으로 동작하며, 특정 컴퓨터 아키텍처(기계어)와 운영체제의 실행 파일 포맷에 종속적이다. 그래서 이쪽 개발 환경은 전통적으로 C/C++ 같은 저수준 최적화 언어가 강세이다.

물론 클라이언트가 아닌 서버 프로그램은 성격이 약간 다르긴 하나, 서버 프로그램 자체는 역시 서버라는 로컬 컴퓨터 자신의 자원만을 이용하여 동작한다. 여객 운송과 화물 수송의 차이와 비슷한 맥락이다. 그리고 사실은, 다음에 설명할 2.웹 프로그램을 돌려 주는 기반도, 클라이언트든 서버든 1.로컬 프로그램들이 다 마련해 주고 있다. 그러니 로컬 프로그램은 앞으로도 없어질 수는 없다. 단지 전체 소프트웨어에서 차지하는 비중이 줄어들 뿐이다.

옛날에는 불특정 개인 사용자를 대상으로 하는 상업용 제품은 패키지 형태로 발매되곤 했지만, 오늘날은 인터넷의 발달과 극심한 불법 복제로 인해 이런 전통적인 형태의 배포의 비중이 굉장히 줄어들었다. 오늘날 국산 패키지 소프트웨어는 아래아한글과 V3 말고 있나? -_-;; 또한 보안 위협으로 인해 이런 프로그램 역시 한번 설치하고 끝이 아니라 끊임없는 보안 패치와 업데이트의 필요성이 커져 있기도 하다.

2. 웹

개인용 컴퓨터의 성능이 굉장히 향상되고 그에 따라 웹 표준이 발달하면서 웹브라우저, 정확히 말해 WWW는 단순히 그림과 하이퍼링크가 동원된 문서라기보다는 거의 프로그래밍 플랫폼처럼 오래 전부터 바뀌었다.

웹 프로그래밍의 최대 매력은 로컬을 월등히 능가하는 범용성과 기계 독립성, 생산성이다. 브라우저에서 사이트 접속만 하면 바로 실행..;; 마치 게임처럼, 클라이언트와 서버, 코딩과 디자인 등을 두루 아우르는 종합 예술처럼 보이기도 한다. 가령, 옛날에는 GWBASIC이나 LOGO로 어린 학생들에게 그래픽 프로그래밍 교육을 시켰다면, 지금은 그냥 HTML5만 써도 될 것이다.

물론, 로컬 개발에 비해서는 혼자 독립적인 작품을 만든다는 느낌이 좀 덜 들며-_-, 기술이 아직까지 안정화해있지 않은 면모가 있고, 로컬 컴퓨터 자체를 세밀하게 제어할 수 없으며 성능이 떨어진다는 한계도 있다. 가령, 오피스 제품군이 웹 애플리케이션으로 완전히 대체될 날은 과연 글쎄?
그러나 앞으로 웹 프로그래밍의 비중은 절대 무시 못 할 것이고 수요도 없어지지 않을 것이다.

3. 앱

스마트폰에서 동작하는 '로컬' 프로그램이라고 볼 수 있지만, 그 성격이 역시 1과는 사뭇 다르다.
스마트폰 자체는 PC보다 성능이 떨어지기 때문에, 로컬에서 모든 처리를 마친다기보다는 서버에다 input을 보내서 받은 output을 보여주는 형태의 앱이 많다. 또한 스마트폰은 화면이 작고 PC 같은 빠른 문자 입력을 할 수 없기 때문에, PC와는 다른 독자적인 GUI가 필요하다. 터치스크린은 마우스와 완전히 동일한 포인팅 UI가 아니다. (대표적으로 hovering이란 게 없다) 다만, PC에는 없는 기울임, 흔들림, 방향, 현재 위치 같은 특수한 입력을 받아들일 수 있다.

스마트폰은 PC만치 사용자가 컴퓨터 내부를 완전히 손쉽게 제어할 수 있는 물건은 아니다. 그래서 PC용 프로그램보다는 더 엄격한 과금 체계를 갖추고 프로그램을 배포하여 수익을 낼 수 있다.
스마트폰 앱은 역사가 짧기 때문에 PC 같은 지저분한 호환성 잔재 같은 게 덜하고, 일찍부터 자바든 C#이든 객체지향 언어와 가상 기계 바이트코드 기반의 프로그래밍 환경이 잘 구축돼 있다. 깔끔한 최신 프로그래밍 인프라가 기본으로 제공된다는 뜻이다.

오늘날 스마트폰 CPU는 ARM 아키텍처밖에 없지만, 그래도 커널 말고 다른 응용 프로그램들은 네이티브 코드가 아니다. 그런 .NET이나 자바 같은 가상 기계 자체가, 1~3(로컬, 웹, 앱) 사이의 이질감을 낮추고자 만들어진 것이기도 하고 말이다.
아울러, CPU의 성능이 좋아졌을 뿐만 아니라 LCD 디스플레이 소자가 보편화하고 통신 기술이 발달하면서 스마트폰 같은 물건도 대중화될 수 있었다.

20세기 중반까지만 해도 컴퓨터는 곧 메인프레임-단말기 모델이었다.
컴퓨터라는 게 무진장 비싼 물건이고 자원이 귀하다 보니, 모든 처리는 중앙 컴퓨터에다 맡기고 각 사용자는 단말기로 서버에 접속해서 명령 프롬프트에서 서버의 기능을 사용하곤 했다. 그때는 컴퓨터는 대학, 연구소, 정부 기관, 군대의 전유물이었고, 개인용 컴퓨터라는 개념을 감히 떠올리기조차 쉽지 않았었다. (알파넷이 미국이 아닌 소련에서 발명되었다고 생각해 보자. 그게 오늘날의 인터넷으로 발전할 수 있었을까? -_-)

그러다가 20세기 말에는 PC가 대세가 되었다. 개인용 컴퓨터 하나만으로 어지간한 일은 다 할 수 있게 되었다. 비유하자면, 만원버스에 시달리면서 출퇴근하다가 번듯한 자가용이 생긴 셈.
PC의 사고방식으로는 소위 PC 통신은 어쩌다 한 번씩만 다른 컴퓨터에 접속하는 특별한 작업이며, 웹브라우저 역시 오피스 패키지처럼 별도로 구입해서 사용하는 특수한 프로그램일 뿐이다.

그 후 오늘날 대세라고 회자되고 있는 건 일명 클라우드 컴퓨팅이다. 개인용 컴퓨터가 무진장 작아지고 통신 인프라가 발달한 덕분에, 예전처럼 부족한 자원을 공유하려고 컴퓨터들을 연결하는 게 아니라 진짜 유비쿼터스 세상이 돼서 컴퓨터들을 연결한다. PC 통신 시절에만 해도 하이텔 단말기가 있었는데 오늘날의 스마트폰에 비하면 얼마나 격세지감인가!

전세계 컴퓨터가 다 인터넷에 연결되고 클라이언트와 서버의 구분이 무의미해지고, 궁극적으로는 (거의) 모든 작업이 웹 프로그램만으로 해결되고 모든 자료가 웹에 저장되는 세상이 온다. 예전에는 PC끼리 자료 전송을 위해서 플로피 디스켓이나 USB 메모리를 썼는데, 이제는 사용자의 로컬 컴퓨터나 스마트폰 그 자체가 플로피 디스켓이나 USB 메모리와 마찬가지가 된다는 뜻.

이걸 역시 자동차에다 비유하자면 이렇다. 사람이 직접 자가운전을 하니까 교통사고가 발생하고 도로가 막히고 여러 문제가 생기다 보니, 전세계 도로가 한데 통제되고 지능형 임대 자가용이나 궤도 교통수단이 생겨서 모든 사람들이 그걸 간단히 이용하는 형태가 된 셈이다.
물론 이게 온전히 실현되려면 시스템적으로나, 보안 쪽으로나 해결해야 할 문제가 많다.

Posted by 사무엘

아래 코드를 실행하면 놀랍게도..
입력된 숫자에 대한 팩토리얼 값이 출력된다. 단, 플랫폼은 x86 한정으로..;;
(뭐, 컴퓨터가 돌아가는 원리를 아는 사람이라거나 맨날 기계어 코드 들여다보는 게 직업인 사람이라면 전혀 새삼스러운 일이 아니겠지만)

비주얼 C++뿐만이 아니라 도스용 DJGPP로도 프로그램이 잘 동작하는 걸 확인했다. 둘 다 IA32 아키텍처인 건 동일하니까 이는 당연한 귀결.

int main(int argc, char* argv[])
{
 BYTE instrs[]={
  0x55,
  0x8B,0xEC,
  0x83,0xEC,0x08,
  0xC7,0x45,0xFC,0x01,0x00,0x00,0x00,
  0x8B,0x45,0xFC,
  0x89,0x45,0xF8,
  0xEB,0x09,
  0x8B,0x4D,0xF8,
  0x83,0xC1,0x01,
  0x89,0x4D,0xF8,
  0x8B,0x55,0xF8,
  0x3B,0x55,0x08,
  0x7F,0x0C,
  0x8B,0x45,0xFC,
  0x0F,0xAF,0x45,0xF8,
  0x89,0x45,0xFC,
  0xEB,0xE3,
  0x8B,0x45,0xFC,
  0x8B,0xE5,
  0x5D,
  0xC3
 };

 PVOID pv = instrs;
 int (*pfn)(int) = reinterpret_cast<int (*)(int)>(pv), y;
 while(1) {
  printf("? "); scanf("%d", &y); if(y<1) break;
  printf("%d\n", pfn(y));
 }
 return 0;
}

프로그래밍 언어의 인터프리터 내지 just-in-time 컴파일러를 만든다거나,
가상 기계 에뮬레이터를 만드는 것은 어렵지 않다.
결국 핵심이 뭐냐 하면 컴퓨터가 직통으로 실행하는 코드 자체를 실행 시간에 메모리에다 생성하는 건데,
함수 포인터가 가리키고 있는 게 바로 저런 것들이다.

물론, 위에서처럼 실행해야 할 코드가 완전히 고정돼 있는 경우라면
소스 코드에다 인라인 어셈블리를 집어넣으면 되겠지만, 그 코드는 데이터 영역에 들어가는 게 아니라 소스 코드(text) 영역에 그대로 포함되어 버리게 될 것이다.

위의 팩토리얼 함수는 물론 컴파일러가 생성해 준 코드를 복사한 것이다.
최적화를 안 한지라, 간단한 for 루프 하나밖에 없는 함수가 코드 길이가 꽤 길다.
최적화를 하고 나면 정상적인 함수 입출력 껍데기에 해당하는 코드조차도 거추장스러운지 생성되지 않아서
그걸 저렇게 따로 떼어내서 쓸 수가 없었다.

Posted by 사무엘

오늘날, 어떤 데이터(개념상 Document라고 불리는)를 메모리에 완전히 읽어들여서 사용자가 그 데이터를 편집할 수 있는 업무용 프로그램에는... 거의 필수로 undo 기능이 있다.
이건 우리가 잘 실감을 못 해서 그렇지 사용자에게 심리적으로 굉장한 안정감을 주는 편리한 기능이다. 뭘 잘못해서 망쳐 놓더라도, '미리 저장 -> 지금 문서를 저장 안 하고 예전 문서를 다시 불러오기' 같은 뻘짓을 안 해도 Ctrl+Z만 누르면 만사 OK.

소프트웨어 GUI 가이드라인 교과서를 보면, 소프트웨어는 사용자에게 '용서'(forgiveness)라는 덕목을 발휘해야 한다는 말이 나온다. 사용자가 아무리 바보짓을 하더라도 이를 최대한 추스리고 수습하고 원상복귀 할 수 있어야 한다는 뜻.
컴퓨터 프로그램은 기독교의 하나님 같은 존재가 아니다. “자유 의지가 있으니, 하늘나라든 지옥이든 선택에 따른 책임도 전적으로 네 몫이다” 주의가 아니다. 그러니 인간의 삶에도 Undo가 있으면 참 좋을 텐데 현실은 그렇지 못하니 참으로 안습이다. 오히려 '말은 하고 못 줍는다', '엎질러진 물', '소 잃고 외양간 고친다' 같은 냉정한 속담만이 있을 뿐이다.

잡설이 길어졌다만,
역사적으로 Undo라는 개념이 허접하게나마 가장 일찍부터 존재한 분야는 그래픽 프로그램이었다.
걔네들은 원래부터 문화가 좀 독특해서 마우스의 비중이 매우 높으며, 우클릭이 Context menu의 의미로 쓰이지도 않을 정도이다.
그리고 근본적으로 마우스라는 게 키보드보다 실수를 훨씬 더 하기 쉬운 입력 장비이고, 한 번의 동작으로 수백· 수천 개의 픽셀이 한꺼번이 바뀔 수 있기 때문에 Undo가 없으면 안 된다.

문득 든 생각: 그래픽 프로그램을 이용해서 마우스로 Freehand drawing을 하는 도중에 bksp 키를 누르면.. 직전의 수 픽셀 단위로 곡선을 철회하는 기능이 있으면 좋을 것 같다. 정교한 도트 노가다 할 때 유용할 것 같다. 보통 Ctrl+Z 누르면 그렸던 선 전체가 한 방에 날아가 버리잖아?

물론 Undo라는 건 그렇게 쉽게 구현할 수 있는 기능이 아니며 메모리 오버헤드가 크다.
더구나, 과거에 Undo 기능이 있던 프로그램은 딱 한 단계밖에 취소가 되지 않았었다. Ctrl+Z를 누르면 직전 작업을 취소했다가, 다시 살렸다가 하기만을 반복할 뿐이었다. (메모장.. 정확히 말하면 윈도우 운영체제의 에디트 컨트롤도 딱 그 수준의 1단계 Undo를 지원한다.)
수십, 수백 단계의 작업을 고스란히 취소하고 취소 내역을 다시 철회(redo)까지 하는 command history 수준의 multi-level undo 기능은 1990년대까지만 해도 MS 워드 같은 소수의 상업용 대형 프로그램에서나 볼 수 있었다.

이런 프로그램은 Document의 내용을 변형하는 모든 명령들이 체계적으로 분류가 돼 있다. 그래서 편집 메뉴를 열어 보면 단순히 '실행 취소 / 재실행'이라고만 돼 있는 게 아니라 '삭제 취소 / 취소된 자동 완성 재실행'처럼, 무슨 명령이 직전에 취소되었고 무엇을 재실행할지 명령의 이름까지 메뉴에 친절하게 표시돼 있기도 한다.
그 반면, Undo/redo를 염두에 두지 않고 Document를 고치는 코드가 제멋대로 섞여 있던 프로그램에다가 어느덧 갑자기 multi-level Undo/redo 기능을 최초로 추가할 일이 생겼다면 아마 십중팔구 코드를 다 갈아엎는 대공사를 해야 할 것이다.

컴퓨터의 성능이 열악하던 도스 시절엔, Undo와 Redo가 모두 존재하는 프로그램은 매우 드물었다.
아래아한글 1.x는 좀 특이한 경우인데, 줄 끝까지 지우기· 단어 지우기 같은 몇몇 지우기 명령으로 인해 지워진 텍스트만을 1회에 한해 되살리는 Undo 기능이 있었다.
그 후 아래아한글 2.0에서 97은 그 Undo의 단계가 3회로 늘었을 뿐이었다. 내 기억이 맞다면, 이 기능은 최근 3회의 주요 지우기 단축키(메뉴에 등재되지 않은)에 의해 지워졌던 텍스트 중 하나를 골라서 커서가 있는 곳에다 삽입해 주는 기능에 불과했다. 원래 있던 위치에 되돌려 놓는 것도 아니고... -_-

Ctrl+X(오려두기)야 본문이 클립보드에 고스란히 들어가 있으니 별도의 Undo 버퍼에다 저장할 필요가 없고,
Ctrl+E(지우기)로 지워진 텍스트는 의도적으로 되살리기가 전혀 되지 않는다고 도움말에 친절하게 안내까지 돼 있었다. ^^;;
그것 말고 문서나 표 레이아웃을 잘못 건드려서 망쳤다거나 하는 더 중요한 기능에 Undo 따위는.. “Undo 뭥미? 그거 먹는겅미? 우걱우걱...”이었다. 그냥 이전 문서를 새로 불러오는 수밖에..
이런 불편한 프로그램을 옛날 사람들은 어떻게 쓰고 지냈을까?

그래서 아래아한글 2002는 256단계 undo가 지원된다고 잔뜩 광고를 하고 다녔었다. MS 제품들은 진작부터 지원한 기능인데도 말이다. 하긴, 그것 말고도 글자 크기 제한이 드디어 없어지고 글자색 제한이 없어진 것도 개인적으로 무척 마음에 들긴 했다. better late than never이다.

<날개셋> 한글 입력기의 편집기 프로그램은 1.x와 2.x 시절에는 Undo 비슷한 기능도 전혀 없었다. 3.0에 가서야 32단계의 multi-level undo가 추가되기는 했으나... 글자 하나, 한글 낱자 하나 입력되는 모든 단계가 histroy에 기록된지라 실용성이 시원찮았다.
그것이 지금의 형태로 개선되 것이 4.2 버전부터이다. 연속된 에디팅 동작뿐만이 아니라 불연속적인 에디팅 동작을 한 history로 통합하는 기능까지 추가되어, 여러 블록을 동시에 삭제한 것이나 Replace All 명령을 내린 것도 한 번에 취소가 가능해졌다.

사실 <날개셋> 편집기의 에디팅 엔진은 아직 좀 효율적이지 못한 구석이 있다. Undo/redo 명령을 내리면 그 부분이 아무리 사소하더라도 문서 전체의 레이아웃을 싹 다시 하고, 화면 전체를 새로 그린다. 그렇기 때문에 수~수십 MB짜리 텍스트를 연 뒤에 Ctrl+Z를 꾹 누르고 있기가 겁난다. 본인은 이 프로그램을 만든 사람이고 프로그램의 내부 디테일이 어떤지를 잘 알기 때문에 그러기가 더욱 꺼려진다.

2004년에 만든 3.0 이래로 그냥 brute-force 알고리즘을 그 부분만은 아직까지 최적화를 못 했다. 한글 입력 부분과 직접적인 관계가 없고, 딱히 크게 티가 나는 부분이 아니다 보니 지금까지 방치되어 온 것이다. <날개셋> 한글 입력기 6.0의 다음 버전은 이 부분을 개선하여, 이제 안심하고 Ctrl+Z를 꾹 누를 수 있는 프로그램이 될 것이다.

Undo 기능과 관련된 얘깃거리를 두 가지만 더 꺼내고 글을 맺겠다.

첫째, 예전에 한번 언급한 적이 있듯이, 프로그램들이 Undo는 거의 예외 없이 Ctrl+Z로 정착해 있는 반면 Redo는 단축키가 프로그램마다 일치하지 않는 경우가 있다. MS의 관행은 Ctrl+Y인 듯하지만 Ctrl+Shift+Z인 프로그램도 있다.
아래아한글은 도스 시절에 Ctrl+Y가 지우기 명령의 일종이기 때문에 주의해야 한다. Redo를 생각하고 눌렀다가는 Redo는커녕 텍스트를 지우면서 후폭풍으로 기존 Undo history까지 모두 날려 버리기 때문이다!

둘째, Multi-level undo를 잘 구현한 프로그램이라면, 문서의 modified 플래그 처리도 잘 되어야 한다. 무슨 말이냐 하면, 문서를 저장했다가 어딘가를 건드린 후(= modified 플래그 켜짐), Ctrl+Z를 눌러 그 작업을 철회한다면 문서는 당연히 다시 unmodified 상태로 바뀌어야 한다.
그리고 반대로, 저장한 문서에 대해서 Undo를 해서 modified 상태가 됐더라도, 그걸 다시 Redo로 철회했다면 문서는 unmodified로 되돌아가야 한다. 논리적으로 당연한 얘기이다. <날개셋> 편집기는 multi-level undo가 처음으로 지원되기 시작한 3.0 때 이거 하나는 아주 철저하게 잘 구현해 뒀다.

비주얼 C++ 에디터, 그리고 국산 에디터인 EditPlus는 이 플래그 처리가 잘 된다. MS 오피스 제품도 마찬가지.
그러나 AcroEdit는 이게 되지 않아서 불편하며, 아래아한글도 2007은 처리가 되지 않는다. WordPad 역시 지원 안 함.

Undo나 Redo 같은 Command history 기능은 문서의 modified 상태까지 예전으로 되돌리는 명령이기 때문에 문서를 건드리는(modified 플래그를 언제나 켜는) 동작보다 상위에서 돌아가야 할 텐데, 이 점을 미처 고려를 못 한 것 같다. Undo나 Redo나 문서를 고치는 기능인 건 매한가지이기 때문에 무조건 modified 상태로. ^^

Posted by 사무엘

칠레처럼 아주 길쭉한 국가가 있다고 치자. 이 국가에는 지형을 따라 거대한 간선 철도가 놓여 있고 n개의 역이 있으며, n개의 역에 모두 정차하는 완행 열차가 일정 간격으로 다닌다.

이 설정을 좀 극단적으로 확장하여 역 수가 수백, 수천, 수만-_-개에 달한다고 가정하자. 그렇다면 급행 열차를 운행할 필요가 응당 생긴다. 2000개역쯤 떨어진 지역에 가려고 하는데 전역정차 열차를 탈 수는 없는 노릇 아닌가. 그렇게 여행 거리가 길어지면, 급행 열차가 서는 곳까지 가서 환승하는 불편 정도는 급행의 빠른 속도가 충분히 보상하고도 남게 된다.

자, 이를 일반화하면.. 급행도 등급이 필요해서 특급, 쾌특 등 n차원의 급행을 생각할 수 있게 된다. 등급이 올라갈수록, 서는 역 수가 무척 적어서 타기 힘든 대신에 일단 타기만 하면 엄청난 이동성이 보장된다. 급행과 완행은 배차 간격은 모두 동일하다고 치자.

여기서 문제가 생긴다.
각 등급의 급행 열차들은 정차역 수를 얼마로 설정하는 게 좋을까?
또한, 철도역 수 n에 대해서, 최대 몇 등급의 급행이 존재하는 게 적당할까?

n개의 역이 모두 똑같이 중요하고 이용객 수가 균일하다고 가정할 때,
어떻게 급행을 운영하는 게 승객의 평균 표정속도를 최대화하고 반대로 평균 환승 대기 시간을 최소화할 수 있을까?
선로 수는 충분하기 때문에, 완급 결합으로 인한 대피 대기 오버헤드라든가 선로 용량 걱정은 할 필요 없다고 가정하겠다. ^^

역 수가 10개 남짓이라면 급행이 있을 필요가 없겠지만, 역 수가 100개쯤 된다면 3~4개역을 건너뛰는 1차 급행에 이어서 한 10~12개쯤 역을 쉬엄쉬엄 건너뛰는 2차 급행이 있어도 좋을 것 같다.

전산학을 전공한 친구라면, 이런 부류의 문제를 생각하면서 비슷한 형태의 아주 유명한 알고리즘을 하나 떠올리게 될 것이다.
바로 '쉘 정렬'이다!

쉘 정렬은 삽입 정렬을 원소별로 띄엄띄엄 적용하되 나중에 그 간격을 촘촘히 좁히는 방식이다.
삽입 정렬은 시간 복잡도가 O(n^2)이지만, n의 크기가 작아서 띄엄띄엄일 때는 오버헤드가 크지 않으며, 또 편차가 커서 리스트가 상당수 정렬되어 있을 때는 매우 빠르게 수행되기 때문에 그 특성을 이용한 것이다.
쉘 정렬은 알고리즘의 특성상 실제로 코딩해 보면 루프가 3중, 4중으로 들어가기 때문에 무거울 것 같지만 돌려 보면 성능이 매우 좋다. 프로그래밍 언어라고는 아직 어셈블리밖에 없던 1950년대에 고안된 알고리즘이다.

여타 정렬 알고리즘들이 O(n^2), O(n log n) 아니면 심지어 O(n) 같은 식으로 시간 복잡도가 딱 파악되는 반면, 이 쉘 정렬은 비록 O(n^2)보다야 훨씬 빠르긴 하지만 시간 복잡도가 제대로 분석되어 있지 않다.
삽입 간격을 설정해서 좁히는 방식을 어떻게 설정하냐에 따라서 성능이 크게 달라지기 때문이다.

완행 다음으로 급행을 겨우 1역 균일 통과, 특급을 2역 균일 통과처럼 정말 무식하기 짝이 없게 운행하지는 않는다. 급행 등급이 하나 올라갈 때마다 급행은 최소한 기하급수적으로 통과역 수가 늘어야 이치에 맞다.
쉘 정렬도 그와 마찬가지이다. 23, 10, 4, 1 같은 급으로 큼직하게 수가 바뀌고, 이 수들이 가능한 한 서로소가 되게 하는 게 정렬 효율에 좋다고 알려져 있다. 16, 8, 4, 2, 1처럼 정확하게 컴퓨터스럽게 배수· 약수 관계로 포개지는 간격은 매우 비효율적이며, 그런 나쁜 수열을 쓰면 쉘 정렬의 시간 복잡도가 최악의 경우 도로 O(n^2)로 치솟는다고 한다.

우리나라의 급행 전철이 정차역 수가 여전히 너무 많다는 지적이 있긴 하지만, 이것은 환승을 싫어하는 국민 정서 내지 환승이 불편한 구조, 급행도 어차피 최대 속도는 동일하고 완행보다 그렇게 많이 빠르지 않은 것, 역마다 weight가 현실적으로 차이가 나는 것, 급행의 소극적인 운행(긴 배차 간격) 같은 다른 환경적인 요인 때문에 그런 것이다. (현실에서는 환승역이냐 그렇지 않느냐의 여부 하나만으로도 역별 weight가 크게 벌어질 수밖에 없다)

이상, 철도와 전산학을 융합한 뻘글이었다.
쉘 정렬의 수열 설정 방식이 철도 운영에서도 이론상 효율적이라 말할 수 있을까? ^^;; (급행은 4역씩 건너뛰고 특급은 10개역, 쾌특은 23개역.. ㄲㄲ)
참고로 쉘 정렬은 수열을 제일 잘 설정했을 때 시간 복잡도가 O(n (log n)^2) 까지는 떨어진다고 한다.


* 덧붙이는 말:
어제는 KTX 열차가 개통 사상 처음으로 탈선 사고를 일으켰다고 한다.
여기에 대해 철도 덕후 사무엘 님의 공식 입장을 말하자면, 이건 두말 할 나위도 없이 선로 시설 문제이지 차량 문제가 아니라는 것이다.
차량이 떼제베가 아닌 산천이었다고 하는데, 지금까지 늘 말썽을 일으켜 온 것처럼 차량이 고장을 일으킨 거라면, 그대로 차가 멈춰서는 걸로 끝나지 지가 무슨 능력으로 탈선까지 하겠는가?

더구나 이 차는 보기 드문 광명 시종착 KTX였다. 광명이 단순 경유역이 아닌 종착역이기 때문에 여타 열차와는 다른 선로로 건너가야만 했다. 그래서 선로 분기기가 열차를 새 선로로 유도하고 있었는데, 열차가 다 건너기 전에 선로 분기기가 전산 착오 내지 추위로 인해 오작동한 것 같다. 그래서 뒷부분 객차의 진로를 막았고, 이것 때문에 찌이이이익 소음+타는 냄새+탈선이 야기된 것으로 추정된다.

열차가 고속으로 쌩쌩 달리다가 교량이 붕괴했다거나 차량이 자폭이라도 한 것과는 전혀 다른 부류의 사고이다. 오히려 열차는 종착역 진입을 앞두고 위와 같은 이유로 인해서 아주 천천히 달리면서 신호를 기다리고 있는 상태였을 것이다. 그리고 그 사고도 그런 특수한 상황에서나 발생한 사고이다. 이 사고가 KTX 차량 시스템 전반에 대한 불신풍조로 이어지기는 않기를 본인은 바란다.

이 사고로 인해 이 열차를 바로 뒤따라오던 상행 KTX는 평택쯤에서 다시 천안아산-_- 역으로 역주행하여 돌아가야만 했고, 대전-서울 구간의 고속선이 폐쇄되는 바람에 다른 KTX들은 아예 경부선 기존선으로 우회해서 다녀야 했다. 주말 임시 열차는 아예 선로 용량 부족으로 인해 운행 중단. 코레일의 입장에서는 손해가 그야말로 막심했을 것이다. 이로 인해 수원-천안 구간에서 KTX 산천이 보이는 진풍경이 연출되기도 했다.

Posted by 사무엘

컴퓨터는 배열로 표현된 직사각형 형태의 데이터를 처리하는 걸 좋아하며, 이는 그래픽에서도 예외가 아니다.
그러나 사람이 생각하는 개념을 그래픽 개체의 형태로 표현하다 보면 직사각형이 아닌 임의의 모양의 그래픽을 찍어야 할 일이 생긴다.
게임에서는 스프라이트가 좋은 예이고, 굳이 게임이 아니더라도 GUI 환경에서는 아이콘이라든가 심지어 customized 마우스 포인터도 그런 부류에 속하는 그래픽이다.

이런 그래픽은 결국 큰 직사각형 안에서 투명색을 제외한 나머지 색상을 찍는 방법으로 처리하는데, 그 구체적인 테크닉은 역사적으로 아래와 같은 세 양상을 거치며 바뀌어 왔다.

1. 모노크롬이나 그에 준하는 저색상: 비트 연산

그림을 두 장 준비한다. 그리고 그 두 장을 화면에다 그냥 copy만 하는 게 아니라, 화면에 이미 있는 픽셀과 비트 연산을 하여 그 결과를 찍는다. 이것을 raster operation이라고 하는데, 비트 연산은 CPU-friendly한 작업이기 때문에 컴퓨터가 나름 빠르게 수행할 수 있다.

준비해야 하는 그림은,
찍어야 할 내용이 그려져 있고 배경은 '검은색'(0)으로 처리되어 있는 '원래 비트맵'과,
원래 비트맵하고는 정반대로 배경은 무조건 '흰색'(1)이고 내가 차지하는 스프라이트 영역은 '검은색'(0)으로 처리되어 있는 '마스크 비트맵' 이렇게 둘이다. 마스크 비트맵은 1 아니면 0만 있는 모노크롬이다.
(따라서 '원래 비트맵'만으로는 검은색이 배경인지 아니면 스프라이트가 실제로 차지하는 검은색인지 알 수 없다.)

화면에다가는 먼저 마스크 비트맵을 AND 연산으로 그린다. 원래 화면에 있던 픽셀이 X라면, 마스크에서 배경으로 처리된 픽셀은 X AND 1이므로 X가 그대로 남고, 0이면 0이 되어 검은색이 된다.
즉, 마스크 비트맵에 대한 AND 연산은, 스프라이트가 칠해져야 할 영역만 시꺼멓게 만드는 효과를 낸다.

그리고 다음으로 이 자리에다가 원래 비트맵을 XOR 연산으로 그린다.
0 XOR X = X이므로, 이 연산을 수행해 주면 화면이 0으로(특히 마스크 비트맵 AND 연산으로 인해 0이 된) 시꺼먼 곳은 원래 비트맵이 그대로 그려지고, 원래 비트맵이 0인 배경은 아무 변화가 생기지 않는다.

그림의 출처는 위키백과.
이로써 스프라이트가 멋있게 그려졌다.
도스용 게임 중에 <위험한 데이브>는 이런 초보적인 XOR 방식으로 스프라이트를 찍었기 때문에, 검은 배경이 아니라 두 스프라이트가 겹치면 화면에 잔상이 남곤 했다.

옛날 윈도우 9x 시절에.. 컴퓨터 메모리가 많이 부족해서 하드디스크 스와핑/thrashing이 일어나고 프로그램의 각종 아이콘들이 그려지는 게 눈에 보일 때는... 아이콘이 차지하는 영역이 먼저 시꺼매지거나 반대로 잠깐 하얗게 번쩍이는 걸 볼 수 있었다. 흠, 프로토스 건물도 소환이 끝났을 때 실루엣이 허옇게 번쩍이다가 원래 형태가 드러나는데...;; raster 연산을 더블버퍼링 없이 화면에다 바로 그리다 보니, 컴퓨터 속도가 느려졌을 때 그 중간 과정이 눈에 띄는 것이다.

검정에다가 원래 비트맵의 색을 합성할 때는 이론적으로 OR을 써도 되는데 XOR이 의도적으로 쓰이고 있다.
이는 XOR이 유용하기 때문이다. XOR 1은 비트를 반전시켜 준다는 특성상, XOR 연산으로 그린 그림은 거기에다 XOR을 한번 더 해 주면, 다른 곳에 영향을 주지 않고 자기가 차지하고 있던 영역에서만 완전히 지워진다.

XOR 연산은 컴퓨터의 입장에서는 매우 부담이 가볍기 때문에, 마우스 선택 영역을 나타내는 점선 사각형이라든가 창 크기를 조절하는 작대기처럼 수시로 업데이트를 해 줘야 하는 비주얼 효과를 나타낼 때 즐겨 쓰인다.
아니, 텍스트 블록이라든가 깜빡이는 커서(캐럿)조차도 반전 사각형이니까 XOR이다.

마우스 포인터도 XOR 연산이다. 텍스트 입력란을 뜻하는 I자(beam) 모양의 마우스 포인터는 검은색이 아니라 배경색에 대한 반전색이다. 마스크 비트맵 값을 0이 아닌 1로 둬서 배경을 지우지 않은 상태에서 XOR 비트맵도 1로 해 주면 배경색이 반전되는 효과가 난다. ^^;;

XOR 연산은 디지털 컴퓨터가 존재하는 한 그래픽에서 언제까지나 없어지지 않고 쓰일 방식이긴 하지만... 오늘날은 다소 촌스러운(?) 것으로 간주되고 있기도 한다. GPU님이 계시니 화면 비주얼을 굳이 CPU 친화적인 방법만 고집할 필요는 없는 듯. 그래서 요즘은 뭔가 선택 영역을 나타낼 때 알파 블렌딩을 동원하여 다 옅은 파란 배경 + 더블버퍼링으로 대체되는 추세이다. 화면 전체의 DC를 얻어와서 XOR 연산을 시키는 건 Aero 환경에서는 오히려 성능을 더욱 떨어뜨리는 짓이기도 하니 말이다.

2. 모노크롬 이상 16~256색 사이: 컬러 키(color key)

그 후 컴퓨터의 그래픽 카드의 성능이 향상되면서, 256색 시대가 열렸다. 256색은 팔레트 조작이라는 과도기적인 괴악한 개념을 도입한 걸로도 유명하다.
색깔이 적당히 많아졌기 때문에, 비트맵에서 256색 중 하나만 투명색으로 예약하여 쓰지 않고 나머지 색은 그대로 찍게 하는 방식이 유리하다. 마스크 비트맵 따위를 번거롭게 구비할 필요가 없다. 또한 256색은 RGB 값이 아니라 인덱스 기반 컬러를 쓰기 때문에, xor 반전 연산이 어차피 그렇게 큰 의미를 지니지도 않는다. (실제 색깔값이 반전되는 게 아니라 팔레트 인덱스 번호가 반전되기 때문)

256색 전용으로 유명한 gif 그래픽 파일이 이런 컬러 키를 지정하여 투명색을 지정할 수 있다.
윈도우 API에도 비트맵이나 아이콘의 (0, 0) 위치 픽셀을 투명색으로 간주하고 그려 주는 함수가 있으며, SetLayeredWindowAttributes 함수는 컬러 키를 지정하여 해당색을 투명하게 처리함으로써 non-rectangular 윈도우를 만드는 효과를 내어 준다. region을 만들지 않고도 동일한 일을 할 수 있다는 뜻이다.

3. 트루컬러: 알파 채널

투명색 처리의 최종 완전체는 바로 알파 채널이다. 이건 과거의 픽셀 raster operation과는 차원이 다르며, 컴퓨터가 빨라진 정도를 넘어 그래픽 가속을 위한 별도의 GPU까지 등장하면서 가능해진 궁극의 기술이다.
매 픽셀에다가 이분법적인 투명 여부가 아니라, 이 픽셀이 배경과 얼마나 짙게 오버랩될지 반투명 등급 자체가 추가로 들어간다. RGB에 이어 A까지, 가히 색깔의 4차원화인데, 기계 입장에서는 한 픽셀당 딱 정확히 32비트이니 처리하기에는 다행히 좋다.

256색을 초월한 천연색 그래픽에는 워낙 많은 개수의 색상이 쓰이기 때문에.. 그 중 딱 한 색깔에다가만 컬러 키를 부여하는 게 무의미하다. 그리고 마치 글꼴에도 안티앨리어싱을 하듯, 스프라이트도 경계가 배경색과 부드럽게 융합해야 트루컬러의 진정한 의미가 살아난다. 그래서 알파 채널이 필요한 것이다.

윈도우 98에서 알파 채널을 적용한 비트맵 찍기라든가 그러데이션을 한번에 처리하는 API가 처음으로 추가됐다. 프로그램의 제목 표시줄에 그러데이션 효과가 윈도우 98에서 처음 추가되었는데, 바로 이 API를 쓴 것이다.
그리고 윈도우 XP에서는 알파 채널이 적용된 확장 아이콘이 처음으로 도입되었고, GDI+는 그리기 기능에 전반적으로 알파 채널을 염두에 두고 설계되었다. 하지만 GDI의 기본적인 벡터 드로잉 함수는 그런 새로운 기술로부터 소외되어 있으니 안타까울 뿐.

윈도우 비스타는 48*48도 모자라서 아예 256*256 크기의 아이콘을 지원한다. XP 때부터 이제 아이콘 하나가 2~3만 바이트에 달하는 시대가 됐는데(윈도우 3.1 시절에는 1~2천 바이트.. -_-), 전통적인 ico는 bmp와 같은 '무압축 포맷'인지라 256*256 크기의 32비트 픽셀을 저장했다간 크기를 감당할 수가 없기 때문에, ico 포맷은 내부적으로 png 파일도 포함할 수 있게 구조가 확장되었다.
gif를 대체하는 새로운 이미지 포맷인 png는 알파 채널을 지원한다. 그 자그마한 아이콘 하나도 전문 그래픽 디자이너가 포토샵으로 만들어야 하는 시대가 도래한 지 오래이다.

윈도우 내부적으로는 아이콘과 마우스 포인터 파일은 거의 동일한 포맷으로 간주된다. 아이콘은 이미지 이미지 비트맵과 마스크 비트맵 이렇게 둘 들어있는 형태이며, 마우스 커서는 거기에다 센터 위치가 추가되고.. 애니메이션 포인터는 gif스럽게 프레임이 더 추가되겠구나.
알파 채널이 등장하면서 마스크 비트맵은 존재 가치가 상당수 퇴색하긴 했으나, 오늘날에도 고전 테마(XP의 Luna, 비스타의 Aero 따위가 없는)에서 아이콘을 찍을 때라든가 disabled 상태 같은 변형 상태를 찍을 때 참고 정보로 쓰이기 때문에, 완전히 필요가 없어진 것은 아니다.

요컨대 오늘날은 기술 발전의 정도에 따라 최소한 세 가지 형태의 투명색 표현 기법이 쓰이고 있는 셈이다. 흥미로운 사실이다.

Posted by 사무엘

오랜만에 알고리즘 얘기.
정보 올림피아드 공부를 한 적이 있는 분이라면, 제목에 등장한 용어가 아주 친숙할 것이다. 앞으로 LIS라고 줄여 일컫겠다.

어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 것이 목표이다.
가령, {3, 2, 1, 4, 5, 2, 3, 5, 3, 6, 4} 같은 수열이 있으면
1, 2, 3, 5, 6이 가장 긴 solution이 된다. {3, 2, 1, 4, 5, 2, 3, 5, 3, 6,  4} OK?
정렬만큼이나 알고리즘 기초를 다지는 데 도움이 되는 흥미로운 문제이다.

이 문제는 간단하게 생각하면 다이나믹 프로그래밍(동적 계획법)을 적용한 O(n^2)의 시간 복잡도로 풀 수 있다. 작은 set에 대한 답을 구한 뒤 그 결과를 저장해 놓고, 그 set의 크기를 차츰 키우면서 작은 solution들을 종합하여 최종 solution을 구하는 방식.

매 원소에 대해서 자기까지 왔을 때 존재 가능한 subsequence의 최대 길이와, 그 subsequence 상에서 자기 앞 원소의 위치를 적어 놓는다. 그러면 다음 원소 차례가 됐을 때는 자기 앞 원소들을 일일이 탐색하여, 자기보다 값이 작으면서 잠재적 subsequence 길이가 최장으로 설정되어 있는 원소에다 자기를 연결해 놓는다. 물론 자기의 subsequence 길이는 1 증가시켜 놓고 말이다.

위와 같은 표가 완성되고 나면, 그 후 개수가 5로 가장 큰 9번 오프셋부터 시작하여 이전 참고 위치를 따라 역추적을 하면 LIS가 구해진다.

그런데 이걸 구하기 위해서 꼭 O(n^2)이나 되는 계산량이 필요할까? 더 효율적인 알고리즘은 없을까?
답은 ‘있다’이다. 물론 메모리 복잡도도 아까처럼 O(n)으로 완전히 동일하고 말이다.
이 새로운 알고리즘은 역시 길이가 n인 버퍼에다가 작업을 하는데, 버퍼의 용도가 아까와는 살짝 다르다.

이 버퍼 A[i](1<=i<=n)의 의미는, 길이가 i인 LIS를 구한다고 쳤을 때 존재 가능한 가장 작은 LIS 마지막 원소(와 그 원소의 위치)이다. 즉, 이 버퍼는 구해진 LIS의 길이만큼만 사용된다.

위의 예제 수열에서 매 원소가 들어올 때마다 버퍼는 다음과 같이 바뀌게 된다. 뒤에 새로운 원소가 추가되거나 이미 있는 값의 업데이트만 발생하지(O(1)), 배열 원소들을 전부 하나씩 밀어야 하는 삽입이나 삭제(O(n))가 발생하지는 않음을 염두에 두기 바란다.
3: 3
2: 2
1: 1
4: 1 4
5: 1 4 5
2: 1 2 5
3: 1 2 3
5: 1 2 3 5
3: 변화 없음
6: 1 2 3 5 6
4: 1 2 3 4 6

즉, 버퍼가 가리키고 있는 것은 각 길이별로 가장 작은 수일 뿐이다. 그러나 버퍼가 가리키는 순서대로 배열을 참조하면 수열이 언제나 오름차순, 즉 정렬이 돼 있다는 게 보장된다.
최소값을 갱신할 위치를 찾는 것은 이분 검색(binary search)으로 할 수 있다. 이 덕분에 작업이 O(n^2)에서 O(n log n)으로 줄어들 수 있게 된다. 정확하게 말하면 O(n log k)(k는 LIS 길이)이니 더욱 빠르다. worst case로 증가 수열을 만들 수가 없는 내림차순 수열을 던져 주면, 거의 O(n)이나 다름없는 속도로 금방 실행이 끝난다는 뜻이다.

물론, 이 버퍼에는 각 길이별로 가장 작은 증가 수열을 구하는 힌트만 들어있을 뿐, 가장 긴 LIS를 추적하는 정보는 전혀 들어있지 않다. 그렇기 때문에 추적 순서는 역시 별도의 배열에다 따로 보관해 놔야 하며 이 역시 그리 어렵지 않게 구현할 수 있다. 심심하신 분은 이 알고리즘을 직접 코딩해 보기 바란다.

정보 올림피아드를 공부하던 시절엔 이런 유형의 문제도 재미있었다. 뭐, 본인은 머리싸움에 쥐약인 타입인지라 경시 부문에서는 별 재미를 못 보고, 대박은 공모 부문에서 다 냈지만 말이다.

- 양수와 음수가 뒤섞인 n개의 수열이 있을 때 합이 가장 큰 구간을 O(n) 시간 만에 구하기
- 위와 비슷한 예로, 0.x와 n.x가 뒤섞인 n개의 수열이 있을 때 곱이 가장 큰 구간을 역시 O(n) 시간 만에 구하기
- x*y 2차원 배열이 있을 때, 이런 조건을 만족하는 가장 넓은 면적을 구하기 (1999년도 IOI의 공항 건설 부지 찾기 같은)

알고리즘이라는 게 OR(operations research)과 밀접한 관계가 있는 것 같다. 선형 계획법, 동적 계획법 같은 개념도 원래는 그 분야에서 유래되었기 때문에 용어에서 그다지 전산학적인 어원은 찾을 수 없다.
덧. algorithm인데 왜 다들 알고리듬이라고 적지 않고 알고리즘(=algorism?)이 보편화해 있는 걸까?

Posted by 사무엘

동일한 기능을 하는 프로그램이 여러 CPU 아키텍처로 포팅된 실행 파일을 살펴보면...
우리에게 아주 친숙한 x86 아키텍처용 EXE는 크기가 가장 작다고 단정적으로 말할 수는 없지만 상당히 작은 편이다.
이보다 코드 사이즈가 더 작게 컴파일되는 아키텍처는 본인이 보기엔 찾기가 어렵다.
EXE 파일의 기계어 코드 부분을 헥사 에디터로 들여다봐도 코드 바이트가 좀 조밀조밀 있는 편이다. 그 반면 IA64나 MIPS 같은 아키텍처 EXE의 기계어 코드를 들여다보면, 4~8바이트 단위로 패턴이 느껴진다.

물론 인텔 아키텍처도 그나마 32비트와 64비트로 가면서 인스트럭션의 평균적인 크기가 길어져 오긴 했다. 그런데 초기의 16비트 명령 체계는 정말 아담했으며, 어셈블리 튜닝을 쓰면 오늘날의 컴퓨터 아키텍처로는 상상도 할 수 없는 작은 크기의 프로그램으로 온갖 큼직한 기능을 넣을 수 있었다. ^^;;
인텔 아키텍처는 하위 호환성을 최대한 존중하고 있으니, 옛날에 정한 1바이트짜리 코드 바이트가 다 선점되었으면 32비트나 64비트 때 추가된 명령은 탈출문자 접두사를 붙여서 5바이트~6바이트... 이런 식으로... 근본적으로 길어질 수밖에 없는 셈이다.

컴퓨터 아키텍처에 대해서 배운 전산 전공자라면, CISC 방식과 RISC 방식의 차이에 대해서는 익히 들어 봤을 것이며, 오늘날엔 이런 식의 단편적인 구분이 별 의미가 없어졌다는 것까지도 알고 있을 것이다.

옛날은 메모리가 아주 귀한 자원이던 시절이었다. 그래서 인텔 x86은 코드를 적재하는 데 필요한 기억장소의 크기를 최대한 아끼는 방향으로 설계되었다. 기계어 코드의 크기가 1바이트부터 시작해 아주 가변적이고, 각 명령 하나하나에 꽤 함축적으로 많은 뜻을 포함시킬 수 있다.

많은 뜻이라 함은, 명령을 내릴 때 상대 주소라든가 절대 주소라든가 실제 상수 같은 개념을 한 인스트럭션에다가 바로 표현할 수 있음을 의미한다. 다른 아키텍처라면 임시값을 또 레지스터에다 먼저 저장하고 전처리를 해서 여러 인스트럭션을 거쳐 표현해야 할 명령을, 한 인스트럭션만으로 표현할 수 있다는 뜻이다. 이것을 CISC 방식이라고 하며, 앞의 C는 complex를 뜻한다. 인텔 x86은 CISC 방식 아키텍처의 대표적인 예이다.

CISC 방식는 상술했듯이 코드 길이가 짧아진다는 장점이 있지만 이를 하드웨어적으로 해석하는 회로가 필연적으로 복잡해지고 만들기 어려워진다는 단점이 있다. 이는 전력 소모의 증가로까지 이어진다. CPU에서 실제로 명령을 실행하는 부분이 아니라 이게 무슨 명령인지 파악하는 부분부터가 오버헤드가 커진다는 뜻이다.

그래서 CISC 방식은 근본적으로 임베디드나 모바일 환경에는 적합하지 않다. 이런 이유로 인해, 오늘날 전세계적인 각광을 받고 있는 스마트폰에서는 ARM이라는 RISC (Reduced) 방식 아키텍처가 쓰이고 있다. ARM이 스마트폰 세계에서 거의 인텔 x86 같은 본좌 인지도를 차지한 것이다.

RISC는 설계 철학이 CISC와는 반대이다. 인스트럭션의 크기는 기계가 한 번에 인식하는 machine word 크기와 일대일 대응하거나 최소한 배수 단위이다. 인스트럭션을 fetch, decode하고 의미를 파악하는 절차가 아주 간편하다. 최소 의미 단위가 작은 대신에 임시 작업용으로 범용 레지스터를 CISC 방식 CPU보다 꽤 많이 준다.

이런 CPU는 심지어 구조체 멤버를 인식하는 단위에도 제약이 있다. 포인터의 오프셋이 machine word의 배수 단위로 딱 떨어지지 않고 사이에 걸쳐 있는데 그 주소를 참조시키면 CPU가 에러를 일으킨다. 성능과 효율을 위해, 이런 복잡한 상황은 과감하게 처리를 거부하는 방법을 택한 것이다.

인텔 x86은 그렇지 않다. 명령어의 실행부터가 워낙 지저분한 바이트 단위 fetching에 익숙한지라, 오프셋이 저런 경우에도 한 사이클만에 참조를 못 하더라도 여러 사이클로 나눠서 사용자가 원하는 데이터를 얻어 준다.

RISC 아키텍처에서 돌아가는 실행 파일을 들여다보면 기계어 코드가 진짜로 4바이트나 8바이트 패턴으로 쫘르륵 나열되어 있는 걸 볼 수 있다. 그리고 동일한 코드를 컴파일한 실행 파일 크기가 x86 같은 아키텍처의 것보다 더 크고, 실행 파일의 압축률도 더욱 높다(듬성듬성하다는 뜻). 다만 한 기능을 수행하는 데 드는 CPU 명령 수가 증가하고 그럴 수록 side effect라든가 복잡도도 더 증가하는 만큼, RISC 아키텍처 코드를 컴파일러가 최적화하기는 더욱 어려울 것이다.

이렇듯, 컴퓨터 아키텍처에서 CISC냐 RISC냐 하는 케케묵은 논쟁은 자동차로 치면 전륜 구동이냐 후륜 구동이냐, 철도 차량으로 치면 동력 분산식이냐 동력 집중식이냐 하는 차원의 재미있는 주제이다. 요즘은 x86 같은 CISC 방식 CPU도 내부적으로는 복잡하고 함축적인 명령을 다시 RISC 식 명령으로 나눠서 파이프라인을 수행함으로써 RISC의 장점을 취하려고 하고 있다.

그리고 문득 든 생각:
어느 기계에서나 이식 가능한 평범한 C/C++ 코드는 자연어로 치면 "나는 철수입니다" 같은 평이한 문장에다 대응시킬 수 있다.
그렇다면 도저히 포팅이 불가능한 인라인 어셈블리 코드는, 자연어로 치면 특정 언어의 음운 특성이나 특정 문화 배경에 대한 이해 없이는 도저히 이해할 수도, 문자 그대로 번역할 수도 없는 함축적인 유머나 언어 유희에다 비유할 수 있겠다.

Posted by 사무엘