가장 효율적인 동시 알고리즘을 구축하려면 컴퓨터 시스템의 하드웨어를 가장 잘 활용하는 유형의 연산을 선택해야 하는데, 그러려면 각 하드웨어 아키텍처의 능력을 이해할 필요가 있다.
3.1 프로세서
중앙 처리 장치(Central Processing Unit, CPU)
•
옛날엔 프린터, 카드 리더기, 자기 드럼이나 디스크 같은 저장 장치에 대한 연산까지 모두 담당
•
현대에는 기계어를 실행하는 데 집중하는 역할
◦
기계어를 해석하는 제어 장치(Control Unit, CU)
◦
산술 연산 및 비트 단위 연산을 담당하는 산술 논리 장치(Arithmetic Logic Unit, ALU)로 구성
◦
두 장치를 활용해 일반적인 계산기보다 더 많은 일을 할 수 있다.
3.1.1 캐시
캐시의 목적은 통신 비용을 줄이는 것이다.
CPU에 연결된 주 메모리(Random Access Memory, RAM)
•
데이터와 명령이 보관된다. 프로그램 실행이 끝날 때까지 유지된다.
•
CPU는 RAM에 직접 접근하지는 않는데, RAM 데이터가 CPU에 전송되는 속도보다 CPU의 연산 속도가 훨씬 빠르기 때문에, 여러 계층으로 된 캐시 메모리를 둔다.
캐시 메모리(cache memory)는 CPU에 포함된 임시 메모리
•
이 메모리를 이용해 CPU는 주 메모리보다 정보에 더 빨리 접근할 수 있다.
•
캐시 메모리는 RAM보다 속도가 훨씬 빠르다. (CPU 칩 안에 함께 있기 때문에 거리상으로도 훨씬 가깝다.)
•
데이터가 필요하면, 캐시에 있는지 캐시 컨트롤러가 확인하고 데이터를 프로세서로 전달한다. 없다면 RAM에서 데이터를 읽어와 캐시에 저장한다.
프로세서에서는 L1, L2, L3의 세가지 레벨의 캐시가 존재
•
L2 & L3 캐시는 다음에 필요한 데이터와 명령이 무엇인지 예측하고, 이를 RAM에서 L1 캐시로 읽어와 프로세서가 바로 사용할 수 있도록 한다.
•
캐시 레벨의 숫자가 클수록 저장 용량은 커지고, 전송 속도는 느리다.
•
L1 캐시는 프로세서와 가장 가까이 있는 캐시다.
1 CPU 사이클을 1초라고 가정(실제로 0.4ns)한다면, 캐시 접근은 2초(L1) ~ 1분(L3), RAM 접근은 4분, 네트워크 요청은 5년이라고 한다.
3.1.2 CPU 실행 사이클
CPU (실행) 사이클은 네 단계를 거친다.
sequenceDiagram participant CACHE participant CU participant ALU participant RAM CACHE ->> RAM: 읽어오기 CACHE ->> CU: 1. 명령 인출 CU ->> CU: 2. 명령 해석 CU ->> ALU: ALU ->> ALU: 3. 실행 ALU ->> CACHE: 4. 결과 저장 CACHE ->> RAM: 저장
Mermaid
복사
프로세서는 명령을 읽어오고, 해석하고, 실행하고, 결과를 저장하는 과정을 끝없이 반복
1.
명령 인출(fetch): 제어 장치가 주 메모리 또는 캐시에서 명령을 읽어와 CPU에 복사
•
이 과정에서 제어 장치는 다양한 카운터를 이용해 어떤 명령을 어디서 읽어와야 하는지 결정
2.
명령 해석(decode): CU; 명령 인출 단계에서 읽어온 명령을 처리할 수 있도록 해석
•
명령은 종류마다 처리가 다름
•
명령의 연산 코드에 따라 정해진 처리 장치로 명령이 전달
3.
실행(execute): ALU; 명령이 ALU로 전달돼 실행
4.
결과 저장: CACHE/RAM; 명령의 수행이 끝나면 결과를 RAM에 저장하고 다음 명령을 실행할 준비를 하며 1단계(명령 인출)로 돌아감. 이 과정을 명령이 없을 때까지 반복
3.2 런타임 시스템
CPU를 다루는 일은 간단하지 않다.
•
그때그때 필요한 기능을 제어하거나 충돌에 대비해 프로그램을 서로 격리하고, 공유 자원에 대한 접근 등의 모든 일을 직접 처리
시스템의 다목적성과 복잡함 때문에, 결국 애플리케이션과 시스템 사이에 새로이 삽입된 추상화 계층의 형태로 진화했는데, 이것이 런타임 시스템(runtime system)이다. 그리고 런타임 시스템 중 우리가 가장 흔하게 볼 수 있는 것이 바로 운영체제(Operating System, OS)다.
•
운영체제는 관리자와 같은 역할을 한다.
◦
컴퓨터 시스템의 하드웨어 구성 요소와 개발자 사이를 이어주는 저수준 시스템 인터페이스(=시스템 콜(system call))
flowchart BT Hardware <-- 복잡한 저수준 시스템 콜 --> OperatingSystem OperatingSystem <-- 쉬운 인터페이스 --> UserApplication
Mermaid
복사
예를 들어 프로그램이 디스크에 데이터를 기록해야 한다면, 프로그램은 이 작업을 운영체제에 맡긴다. 운영체제는 디스크에 적합한 신호를 보낸다. 고로 프로그램은 디스크를 사용하기 위해 종류나 사용법을 알 필요가 없다. 운영체제가 필요한 세부 사항을 처리해주고, 프로그램이 비정상적으로 사용되더라도 하드웨어와 자원을 보호해준다. (시스템 콜을 사용하지 않아도 된다.)
•
운영체제는 프로그램을 실행하는 첫 단계는 실행 파일과 정적 데이터(초기 변수 등)를 메모리로 읽어들이고, 시작점(main())부터 프로그램을 실행한다. 그러면 프로세서의 제어권이 프로그램으로 이전된다. 이때부터는 운영체제의 보호 아래 프로그램이 실행된다.
3.3 컴퓨터 시스템의 구조
구성을 보면 하나 이상의 프로세서, 프로세서가 사용할 RAM, 여러 주변 기기(프린터, 카드리더기, 하드디스크, 모니터 등), 프로세서와 RAM이 이들 주변 기기를 다루거나 통신할 때 사용하는 컨트롤러 혹은 드라이버(driver)를 볼 수 있다. 그리고 이들을 모두 연결하는, 통로 역할을 하는 시스템 버스(system bus)가 있다.
3.4 동시 하드웨어의 여러 수준
CPU는 기본적인 산술 연산(덧셈 or 곱셈)을 수행하는 여러 개의 회로(ALU)로 구성
•
명령어 수준 병렬성(instruction-level parallelism)
◦
복잡한 연산을 여러 부분 쪼개어 각기 다른 회로에서 동시에 수행 가능
•
비트 수준 병렬성(bit-level parallelism)
◦
명령어 수준 병렬성보다 더 낮은 레벨
◦
프로세서의 입장에서 실행이 가장 편리하게끔 인스트럭션을 배치하는 작업은 컴파일러가 해줌
병렬적 하드웨어를 만들 수 있는 가장 간단한 방법은, 한 시스템에 프로세서를 두 개 이상 설치하는 것이다.
•
멀티 프로세서(multiprocessor)
◦
모든 프로세서가 칩 하나에 올라간 형태
◦
각 코어는 독립적으로 동작하며 운영체제는 각 코어를 별개의 프로세서로 다룬다.
3.4.1 대칭형 다중 처리 구조(SMP)
컴퓨터 메모리는 대개 프로세서보다 훨씬 느리다. 그렇기에 대칭형 다중 처리(Symmetric Multiprocessing, SMP) 구조가 채용되었다. SMP는 동일한 프로세서 여러 개가 단일 주소 공간을 가진 공유 메모리에 연결돼 같은 운영체제에서 동작하는 구조를 말한다.
SMP 구조에 포함된 프로세서는 시스템 버스를 통해 상호 연결된 네트워크로 엮여있어 네트워크의 속도는 빠르지만, 자원의 수가 많아지고 이들 간의 거리가 증가하면 지연 시간을 증가시킨다. 따라서 SMP 구조에서는 모든 프로세서가 전용 캐시를 따로 갖고 있어 시스템 버스의 트래픽을 억제하고 지연 시간을 줄인다.
캐시 일관성(cache coherence)을 유지하다가 시스템 버스의 병목이 더욱 심각해진다. (1980년대 MESI 프로토콜이 개발되면서 해결)
SMP 구조를 넘어 더 큰 규모의 병렬 컴퓨터를 구성하려면 공유 메모리 구조를 포기하고, 컴퓨터 클러스터(computer cluster)라는 분산 메모리 시스템으로 전환해야 한다.
•
각자 CPU를 가진 여러 대의 컴퓨터를 네트워크로 연결한 것
•
통신 비용이 많이 드는 네트워크로 분산 메모리를 가져 훨씬 느릴 수 밖에 없음
•
클러스터는 느슨하게 결합된(loosely coupled) 문제(프로세서 간에 잦은 통신이 필요하지 않지만 컴퓨팅 성능은 많이 필요한)를 푸는 데 적합
◦
확장성이 뛰어남
•
강하게 결합된(tightly coupled) 문제를 해결하는 데는 단일 컴퓨터 시스템이 더 적합
3.4.2 병렬 컴퓨터의 유형
멀티 프로세서 아키텍처를 분류하는 데 가장 널리 쓰이는 기준은 플린 분류(Flynn’s taxonomy)다.
•
명령어(instruction)와 데이터 흐름(data flow)이라는 두 가지 기준에 따라 컴퓨터 시스템을 네 가지로 분류
1.
단일 명령-단일 데이터(Single Instruction Single Data, SISD)
a.
병렬성 결여
2.
다중 명령-단일 데이터(Multi Instruction Single Data, MISD)
a.
병렬성 결여
3.
단일 명령-다중 데이터(Single Instruction Multiple Data, SIMD)
a.
코어 여러 개를 걸쳐 제어 장치를 가진 것이 특징
b.
모든 처리 자원을 통틀어 동시에 한 가지 명령만 실행
c.
많은 양의 데이터 요소를 대상으로 같은 연산을 동시에 실행하는 것이 가능
d.
높은 컴퓨팅 성능이 필요하지만 다양한 연산이 필요하지 않은 문제에 적합
e.
ex) 그래픽 처리 장치(GPU)
4.
다중 명령-다중 데이터(Multiple Instruction Multiple Data, MIMD)
a.
처리 자원마다 독립적인 제어 장치가 있음
b.
서로 다른 데이터 블록에서 서로 다른 연산을 독립적으로 수행할 수 있음
c.
플린 분류에서 가장 널리 쓰이는 부류
d.
멀티코어 PC부터 분산 클러스터까지 모두 MIMD가 사용됨
3.4.3 CPU vs. GPU
CPU와 GPU는 매우 비슷하다. 두 가지 장치 모두 트랜지스터를 수백만 개 갖고 있으며, 1초에 매우 많은 명령을 처리할 수 있다.
일반적인 CPU는 MIMD 구조를 따른다.
•
복잡하고 선형적인 작업에 적합
GPU는 SIMD 구조에 가까운 특별한 유형의 프로세서로, 몇 가지 소수의 인스트럭션에 최적화되어 있다.
•
반복적이고 고도의 병렬적인 계산 작업
◦
영상, 이미지처리, 머신러닝, 금융 시뮬레이션, 과학적인 계산 등
GPU의 클록 속도는 CPU보다 느리지만, 코어 수에서는 CPU를 압도한다. 수백 내지 수천 개의 코어가 동시에 동작할 수 있다. 이런 대규모 병렬성 덕분에 GPU는 많은 양의 단순한 연산을 매우 빠르게 처리한다.
다양한 인스트럭션이 있고 클록 속도가 빠른 만큼 각 코어는 CPU가 더 빠르지만, GPU의 코어 숫자에서 오는 대규모 병렬성의 힘이 인스트럭션의 단순성과 부족한 클록 속도를 메우고도 남는다.
