병렬컴퓨터의 분류 – Flynn의 분류

컴퓨터시스템을 분류하는 방식은 여럿 존재한다. 가장 널리 사용되는 방식이 바로 Flynn의 분류(Flynn’s classificaation) 방식이다. 방식 이름은 어색할 지 모르겠지만, 내용을 보면 아마 금방 “아, 그거!”할 것이다. 이 분류 방식에서는 프로세서들이 처리하는 명령어와 데이터의 스트림의 수에 따라 디지털 컴퓨터를 네 가지로 분류하고 있다. 여기서 맘ㄹ하는 스트림이란 하나의 프로세서에 의하여 순서대로 처리되는 일련의 명령어들과 데이터들의 흐름을 말한다. 즉, 명령어 스트림이란 프로세서에 의해 실행되기 위하여 순서대로 나열된 명령어 코드들의 집합을 의미하고, 데이터 스트림이란 그 명령어들을 실행하는 데 필요한 순서대로 나열된 데이터 집합을 의미한다.

명령어와 데이터 스트림을 처리하기 위한 하드웨어 구조에 따른 Flynn의 분류와 간략한 설명은 다음과 같다.

  • SISD 조직(Single Instruction stream Single Data stream): 한 번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일프로세서 시스템에 해당한다. 이러헌 시스템에서는 명령어가 순서대로 실행되지만, 실행 과정은 여러 개의 단계들로 나누어 시간적으로 중첩시킴으로써 실행 속도를 높이도록 파이프라이닝되어 잇는 것이 일반적이다. 또한 SISD 시스템에서 하나의 프로세서 내에 여러 개의 명령어 실행 유니트들이나 ALU 들을 포함함으로써, 동시에 두 개 혹은 그 이상의 명령어들을 동시에 실행하는 슈퍼스칼라(superscalar) 구조도 많이 사용되고 있다. 파이프라이닝과 슈퍼스칼라는 프로세서 내부에서 병렬처리를 이용하는 구조라고 할 수 있다.
  • SIMD 조직(Single Instruction stream Multiple Data stream): 배열 프로세서(Array Processor)라고도 불린다. 이러한 시스템은 여러 개의 프로세싱 유니트(PU)들로 구성되고, 프로세싱 유니트들의 동작은 모두 하나의 제어 유니트에 의해 통제된다. 모든 PU들은 하나의 제어 유니트로부터 동일한 명령어를 받지만, 명령어 실행은 서로 다른 데이터에 대하여 이루어진다. 또한 모든 PU들이 기억장치를 공유하는 경우도 있고, 각 PU가 기억장치 모듈을 독립적으로 가지는 분산 기억장치 구조도 가능하다.
  • MISD 조직(Multiple Instruction stream Single Data stream): 한 시스템 내에 n개의 프로세서들이 있고, 각 프로세서들은 서로 다른 명령어들을 실행하지만, 처리하는 데이터들은 하나의 스트림이다. 다시 설명하면, 프로세서들이 파이프라인 형태로 연결되어서, 한 프로세서가 처리한 결과를 다음 프로세서로 보내는 방식이다. 그러나 이 조직은 컴퓨터 구조 설계자들이 관심을 끌지 못하고 있으며, 실제로 이러한 시스템은 이론으로만 존재한다.
  • MIMD 조직(Multiple Instruction stream Multiple Data stream): 대부분의 다중프로세서 시스템(multiprocessor system)과 다중컴퓨터 시스템(multiple-computer system)이 이 분류에 속한다. 이 조직에서는 n개의 프로세서들이 서로 다른 명령어와 데이터를 처리한다. MIMD 시스템은 프로세서들간의 상호작용 정도에 따라 두 가지로 나뉘는데, 그 정도가 높은 구조를 밀결합 시스템(tightly-coupled system)이라 하고, 그 정도가 낮은 구조를 소결합 시스템(loosely-coupled system)이라고 한다. 밀결합 시스템의 전형적인 구조는 기억장치가 모든 프로세서들에 의하여 공통으로 사용되는 공유 기억장치(shared-memory architecture) 구조이다. 소결합 시스템은 각 프로세서들이 자신의 지역 기억장치(local memory)를 가진, 독립적인 컴퓨터 모듈로 구성되고, 프로세서들간의 통신은 메시지 패싱(message-passing) 방식에 의해 이루어지는 구조를 가지고 있다.

병렬 프로그래밍을 배울 때, 혹은 멀티코어 CPU에 대한 자료를 봤을 때 봤던 내용들이 많이 있을 것이다. 병렬컴퓨터는 프로그램 코드와 데이터를 병렬로 처리하는 시스템이므로, Flynn의 컴퓨터 분류들 중에서 SIMD와 MIMD 조직이 그에 해당하는 조직이다.

그리고 최근에는 SISD 조직에 해당하는 단일프로세서 시스템도 프로세서 내부에 파이프라이닝과 슈퍼스칼라 구조를 이용하기 때문에 병렬처리를 구현하는 시스템으로 볼 수 있다. 이러한 SISD 구조의 프로세서들을 다이에 여렷 구성하고 내부에서 병렬로 제어 가능하도록 연결함으로써 병렬처리만을 위한 프로세서를 연구하기도 한다.

병렬처리의 단위

병렬처리란 여러 개의 프로그램들 혹은 한 프로그램의 분할된 부분들을 다수의 프로세서들을 이용하여 동시에 처리하는 것이라고 하였다. 그런데 병렬처리에 참여하는 각 프로세서(혹은 독립적인 컴퓨터 노드)에 분담되는 단위 프로그램의 크기에 따라 다양한 수준의 병렬성들이 존재할 수 있다. 그 단위 프로그램은 각각 독립적인 작업일 수도 있고, 더 작게 분할된 프로그램 세그먼트도 될 수 있다. 다만 그들이 서로 독립적으로 처리될 수만 있으면 된다. (이 부분을 원자성이라고 한다.)

  • 작업 단위(job level): 서로 다른 사용자들에 의해 제출된 작업 프로그램들 혹은 한 사용자에 의해 제출된 여러 개의 독립적인 작업 프로그램 단위로 병렬처리 되는 것을 의미한다. 예를 들어, 어느 교수가 강의와 연구를 동시에 수행하는 과정에서 성적관리 프로그램과 실험 데이터를 처리하는 프로그램을 동시에 처리하려고 한다면, 그 프로그램들은 서로 독립적으로 처리될 수 있다. 만약 컴퓨터 시스템 내에 두 개 이상의 프로세서들이 있다면, 이 두 작업 프로그램들은 병렬로 처리될 수 있다.
  • 태스크 단위(task level): 하나의 큰 작업은 내부적으로 서로 다른 기능을 수행하는 더 작은 프로그램들로 분리될 수 있다. 예를 들어, 팔과 다리를 가진 로봇이 있다고 하였을 때, 이 로봇을 움직이기 위해서는 부착된 여러 개의 센서들로부터 정보를 입력받아서 팔과 다리를 적절히 제어하도록 명령하는 컴퓨터 프로그램이 필요하다. 전체 프로그램은 하나의 작업 프로그램이지만, 그것은 여러 개의 태스크들로 분할 될 수 있다. 예시와 같이 보면, 각 팔을 제어하기 위한 태스크들과 각 다리를 제어하기 위한 태스크들로 나누어질 수 있으며, 그들은 병렬로 처리될 수 있다. 물로 ㄴ그들은 처리되는 도중에 상호 연관되는 정보를 교활할 필요도 있을 것이다.
  • 프로세스 단위(process level): 각 태스크는 다시 여러 개의 프로세스들로 나누어 질 수 있다. 여기서 각 프로세스는 특정 함수를 계산하는 정도의 크기이다. 분할은 사용자에 의해 임의로 이루어질 수도 있고, 컴파일에 의해 자동적으로 이루어지도록 할 수도 있다. 프로세스 단위에 대해서는 예시를 보면서 이해하는 것이 좋기 때문에 별도로 글을 작성하도록 하자.
  • 변수 단위(variable level): 프로세스 단위 병렬처리에서 각 프로세스는 여러 개의 프로그램 코드들로 이루어져 있는데, 각 코드(명령어)는 어떤 입력 변수를 받아서 연산을 수행한 후에 출력 변수를 생성한다. 그런데 한 프로세스 내의 여러 변수들을 동시에 계산하는 것이 가능할 수 있기 때문에 프로세스 내에도 병렬성이 존재한다. 그 이유는 변수들이 이전의 반복 루프에서 계산된 변수들을 이용하여 계산되기 때문이다.
  • 비트 단위(bit level): 대부분의 컴퓨터에서는 비트 단위의 병렬 계산이 허용된다. 즉, 하나의 데이터 단위를 구성하고 있는 각 비트들에 대한 독립적인 연산들을 병렬로 처리할 수 있다. 이것은 가장 낮은 수준의 병렬성이라고 할 수 있다.

병렬 컴퓨터의 성능과 효율을 높이기 위해서는 이와 같은 다양한 수준의 병렬성을 최대한 이용할 수 있어야 하며, 그를 위해서는 시스템 구조와 프로세서 구조가 적절히 설계되어야 한다.

C언어의 inline 키워드

C언어로 함수 좀 짜다보면 inline이라는 키워드를 써서 만들어 보여주면 “이건 뭐임?”이라면서 신기하게 쳐다보는 사람이 있어서 혹시나 해서 올려봄…

#define같은 선행 처리자들은 매크로가 pre-processor에서 단순 치환되는 형태이다. 그러나, inline은 컴파일러가 함수 인수등의 type을 체크해 보고 안전하다고 판단되는 경우에 처리를 해준다.

그냥 보이는 결과적으로는 #define이나 inline이나 큰 차이는 없어보임. 그러나 그 차이는 요즘은 문제가 된다.

기본적으로, 함수를 이용하면 호출과 반환으로 인한 메모리 할당 등에 대해서 오버헤드가 발생한다. 그러나, 근래에 코드 작성하는 요령에 권장되는 사항들은 짦은 길이의 함수를 만들어서 가독성 및 오류가 적은 수준의 단위로 만들어서 구현하는 것이 추세이다.

이런 면에서, 짧은 길이의 C함수를 이용하는 것은 장점보다 비효율적인 면이 많이 생긴다. 이러한 경우에 매크로 함수를 이용하는 것이 바람직하다. 매크로 함수를 이용하면 전처리기에 의해 해당 부분이 정의된 내용으로 대체되어 함수 호출 과정이 사라지게 된다. 따라서 함수 이용으로 인한 오버헤드가 발생하지 않는다.

반면, 매크로 함수의 정의 부분이 길면 프로그램의 크기가 커지게 되는 문제점이 있다. 이 부분은 의도치 않게 커지는 부분이 된다. 게다가 매크로 함ㅁ수를 정의하는 것은 일반적인 함수를 정의하는 것보다는 구현이 까다로운 점도 있다.

그래서 일반적인 함수를 정의하는 것처럼 쉽게 구현할 수 있고 매크로 함수처럼 동작하는 기능을 가진 함수가 있는데 이걸 C에서 이용하는 inline 함수이다.

inline 키워드는 inline 함수를 만들기 위한 키워드이다.  C언어 책에도 나와있는 것이라서 솔직히 다 알고있을 줄 알았는데, C를 그냥 함수랑 포인터까지만 배우고 나서 OOP 한답시고 바로 자바로 넘어가서 더 이상 깊게 안보게 되면 잘 모르는 경우가 많은 듯 해서 적어봤다.

병럴처리의 한계와 가능성 – Amdahl의 법칙

병렬 프로그래밍이 여러곳에서 말 나오면서 제일 많이 들어봤을 법칙이다. 병렬 처리를 이용하여 얻을 수 있는 속도 향상에 대한 한계를 제시한 법칙이다.

20160603_165519

직렬 알고리즘 중에서 반드시 순차적으로 처리되어야 하는(= 병렬화 할 수 없는) 부분의 비율을 Amdahl의 비율이라 하는데, 여기서는 a라고 정하고 이야기를 진행한다. 실제 시스템에서 병렬화 할 수 없는 부분에 해당하는 예를 보면, 프로그램이나 데이터를 다운로드 하는 데 걸리는 시간, 운영체제의 커널 실행 시간 혹은 연산들 간에 선행 관계가 존재하는 경우 등등이 있다. a를 고려하면 Tp는 아래와 같은 식이 된다.

20160603_165552

그를 통해 속도 향상은 아래 식으로 표현된다.

20160603_165622

그런데, 만약 사용 가능한 프로세서의 수가 무한대라고 가정하면, 속도 향상의 비율값은 아래와 같아진다.

20160603_165627

즉, 병렬처리를 이용하여 얻을 수 있는 최대 속도 향상은 a값의 역수가 된다. 예를 들어, 계산할 알고리즘 중에 반드시 순차적으로 처리해야 할 부분이 5%가 있다면, 프로세서가 무한히 많이 사용되더라도 속도 향상은 최대 1/0.05 = 20배 밖에 되지 못한다는 것이다. a값이 큰 경우에는 프로세서의 수가 증가하더라도 속도 향상은 거의 얻지 못하고 포화되며, 결과적으로 시스템 효율이 크게 떨어진다는 것을 알 수 있다.

그러나, Amdahl의 법칙도 처리할 응용의 특성에 따라 해석이 달라질 수 있다. 예를 들어, 대부분의 공학 및 과학 계산 문제들에서 Amdahl의 비율 a는 문제의 크기 n에 따라 값이 달라지게 된다. 여기서 문제의 크기란 선형방정식의 차수, 즉 변수의 개수에 해당한다. 그 크기가 증가하면 그만큼 계산량이 증가하게 되는 반면에, 순차적으로 처리되어야 하는 부분은 거의 일정하게 고정되기 때문에 a값은 상대적으로 감소한다. 이렇게 되면 즉.

20160603_165633

이 될 수 있다. 따라서 그러한 응용들을 처리하는 경우에 문제의 크기가 무한대로 커진다고 가정하면, 속도 향상은 아래의 식과 같이 정의될 수 있다.

20160603_171139

이러한 예는 실제로 미국의 Sandia 국립연구소에서 몇 가지 응용들을 1024개의 프로세서들로 구성된 하이퍼큐브시스템에서 처리한 결과, 거의 선행적인 성능 향상을 얻을 수 있다는 것을 입증하였다. (유명한 논문이다. 단, 작성날짜가….ㅠㅠ J.L.Gustafson, “Reevaluating Amdahl’s Law”, Communications of the ACM, Vol31, No. 5, Maay 1988, pp 532-533)

결론적으로, 큰 응용 문제가 효율적인 방법으로 처리되는 이상적인 경우에는 Amdahl의 법칙과는 달리, 프로세서의 수에 비례하는 선형적인 속도 향상을 얻을 수 있다는 것이다. 여기서 주의해야 할 사항은 문제의 크기가 증가하면 기억장치의 용량도 증가해야 하며, 그렇지 않은 경우에는 속도 향상이 프로세서의 수보다 기억장치 용량에 의해 더 큰 영향을 받을 수 있다는 점이다. 이 부분은 이후에도 지속적으로 설명하겠다.

병렬 컴퓨터의 성능 한계에 대한 초기의 비관적인 내용들을 확인해보았다. 이런 예측들은 응용 문제의 크기가 증가하고 효율적인 통신 매커니즘이 설계되면 충분히 개선될 수 있는 것이 입증되고 있었고, 그에 대해서도 현재 실제로 입증되고 있다. 그래서 최근의 개발된 거의 모든 고성능컴퓨터시스템들은 병렬처리 기술을 사용하고 있다.