[컴퓨터구조] OOO, OoOE, 토마슬로 알고리즘을 통한 비순차적 명령어 처리 + 혼공컴구 독서 #6 - CPU 성능향상

아니 열람실에서 공부중인데 6시 이후로 급격하게 추워짐 뭐야이거 개추워

---

https://dev-dx2d2y-log.tistory.com/191

[컴퓨터구조] 혼공컴구 독서 #5 - 명령어 사이클과 인터럽트

암튼 저번에는 CPU의 명령어 사이클과 인터럽트에 대해서 알아보았다. 이번에는 빠른 CPU를 만드는 기법, 코어, 클럭, 스레드라는 개념을 알아본다고하는데.. 솔직히 코어와 스레드는 이전에 한 번 다룬 적이 있어서 짧게 하고 넘어갈 듯 하다.

---

클럭

https://dev-dx2d2y-log.tistory.com/188

[컴퓨터구조] 혼공컴구 독서 #3 - CPU - ALU, 플래그, 제어장치

 

이전에 클럭에 대해서 다룬 적이 있다. 더 빠른 CPU를 만들기 위해서는 클럭속도를 높일 수 있다. 그러면 컴퓨터가 더 자주 명령어를 수행하게 되기 때문이다.

 

클럭 속도의 단위는 헤르츠(hZ)로, 1초에 클럭이 몇 번 반복되는지 측정한다.

지금 노트북에 사용 중인 CPU가 클럭 속도 (기본 속도)가 1.30GHz이므로 1초당 클럭이 1.3 x 10^9 번만큼 반복되는 것을 알 수 있다.

 

이외에도 몇몇 CPU들은 기본 속도와 최대 속도로 나뉘어져있는 경우가 있는데, 이런 경우 CPU는 일정한 클럭 속도를 계속유지하기보단 작업량이 많을 때 최대 속도로, 작업량이 적을 때는 보다 클럭속도를 느리게 조절해서 유연한 클럭속도를 가지는 경우도 있다.

 

암튼 이렇게 클럭 값을 만지면 컴퓨터가 초당 명령어를 수행하는 빈도가 높아져서 CPU가 빨라진다. 다만 너무 빨리 올리면 발열문제가 심해지고 회로가 타버리기 때문에 근본적인 해결책은 되지 못한다.

---

코어

클럭 속도 이외의 CPU의 성능을 높이는 방법으로는 CPU의 코어를 늘리는 방법이 있다.

 

코어란 명령어를 실행하는 주체다. 이전까지는 CPU가 명령어를 실행하는 주체였지만, 기술이 발전함에 따라서 CPU 내에 ALU - 제어장치 - 레지스터로 이루어진 장치를 여러 개 사용할 수 있게되면서 코어라는 용어가 등장했다. 따라서 기존에 배웠던 ALU - 제어장치 - 레지스터로 이루어진 부품 한 개를 코어, 코어들이 여러 개 모인 것이 CPU라고 칭한다.

 

코어가 여러 개 있다면 멀티코어CPU 또는 멀티코어 프로세서라고 칭한다. 코어 한 개는 한 번에 하나의 일만 수행할 수 있지만, 여러 개의 코어가 있다면 동시에 여러 작업을 수행할 수 있다. 그래서 클럭속도가 낮더라도 코어 수가 더 많다면 성능이 더 좋을 수 있다.

 

이 사진을 보면 내가 쓰는 노트북은 10개의 코어를 가진 멀티코어CPU라는 것을 알 수 있다.

 

다만 코어도 무작정 코어를 많이 단다고해서 성능이 좋아지지는 않는다. 코어가 많이 생기더라도 한 코어에만 테스크가 집중된다면 코어를 많이 단 의미가 없어지기 때문이다. 멀티코어 환경에서 중요한 것은 테스크가 얼마나 고르게 분배되었나라는 것이 중요하고, 코어 수가 지나치게 많은 경우에도 특별히 성능이 좋아지지는 않는다.

---

스레드

하드웨어적 스레드

하드웨어적 스레드의 정의는 하나의 코어가 동시에 처리하는 명령어 단위를 의미한다. 위 사진을 보면 "논리 프로세서"라는 것이 등장하는데, 이것이 스레드이다. 위 사진은 논리 프로세서가 12이므로 한 개의 코어가 동시에 12개의 명령어를 처리할 수 있다는 뜻이다.

 

하나의 코어로 여러 명령어를 동시에 처리하는 CPU를 멀티스레드 프로세서 또는 멀티스레드 CPU라고 칭한다.

즉 다시말해서 내가 사용하는 CPU는 10코어 12스레드로, 동시에 12개의 명령을 처리할 수 있는 코어가 10개가 들어있는 CPU라고 보면 된다.

---

소프트웨어적 스레드

소프트웨어적 스레드는 하나의 프로그램에서 독립적으로 실행되는 단위를 뜻한다. 일반적인 프로그래밍 언어에서 다루는 스레드가 소프트웨어적 스레드에 해당한다. 비동기처리를 실행 중이라면 서로 다른 여러 테스크가 서로 다른 스레드에서 독립적으로 실행된다.

 

그래서 하드웨어적 스레드와 소프트웨어적 스레드를 구분할 필요가 있다. 소프트웨어적 스레드에서는 코어가 한 번에 한 스레드만 처리할 수 있어서 여러 스레드를 아주 짧은 시간동안만 번갈아서 실행시키는 형태로 마치 동시에 작업이 수행 중인 것처럼 보이게하지만, 하드웨어적 스레드에서는 그냥 하나의 코어가 여러 작업을 동시에 실행시킬 수 있기 때문이다.

 

코어가 아무리 많은 양의 작업을 수행하더라도 성능의 100%를 한 테스크에 사용하지는 못하는데, (이는 코어 연산 속도와 메모리를 읽어오는 속도에 차이가 있는 것으로, 코어에서 연산이 끝나더라도 메모리에서 값을 읽어오기 위해서 대기해야하는 경우가 생기기 때문이다.) 이 남은 부분을 다른 스레드의 연산에 사용한다. 즉, 스레드A가 메모리에서 값을 읽어오기 위해 기다리는 동안 스레드B의 작업을 대신 수행해준다.

 

소프트웨어적 스레드에서는 스레드를 바꾸는 것에 많은 비용이 들지만 하드웨어적 스레드에서는 보다 저수준이기 때문에 명령어만 미세하게 바꾸면 된다. 따라서 자원소모가 거의 없이 병렬처리가 가능한 것이다.

---

멀티스레드 프로세서

보다 자세히 하나의 코어로 여러 명령어를 처리하는 과정에 대해서 알아보자면, 가장 핵심이 되는 부품은 레지스터다. 왜냐하면 명령어 처리를 위해서는 가장 기본이 되는 레지스터만 이미 여러 개이기 때문이다.

 

이렇게 가장 기본이 되는 레지스터 세트가 관건이 되는데, 위에서 말했듯이 코어의 ALU와 제어장치는 메모리에서 값이 올라오기를 기다릴 때 다른 코어의 일을 대신 수행해주는 형식으로 사용할 수 있지만, 레지스터 세트는 반드시 독립적이어야한다. 서로 다른 스레드마다 값이 엉키면 안되기 때문.

 

그래서 2코어더라도 레지스터 세트가 각 코어별로 2개씩 총 4개가 들어있다면 동시에 4개의 테스크를 기억할 수 있다. 즉, 작업은 4개를 동시에, 명령어 수행은 2개를 동시에 실행할 수 있다.

---

명령어의 병렬처리

명령어 병렬 처리 기법은 CPU를 쉬지 않고 가동시키는 것을 말한다. 앞서 말한 하나의 코어가 시간이 비면 다른 코어의 일을 대신 수행하는 경우가 이에 해당한다. 병렬처리법에는 여러 종류가 있는데,

---

명령어 파이프라인

명령어 처리 과정은 명령어 인출 - 해석 - 실행 - 결과저장의 단계로 나눌 수 있다. 그리고 CPU는 정보가 꼬일 수 있는 같은 단계가 아니라면 각 단계를 동시에 실행할 수 있다. 즉, 인출하면서 해석, 해석하면서 실행 등이 가능하다.

 

그러면 책 157쪽의 그림처럼 서로 다른 명령어 4개의 인출-해석-실행-저장을 동시에 진행할 수 있다. 이처럼 컨베이어벨트처럼 명령어를 컨베이어벨트 위에 올리고 기계적으로 인출, 해석, 실행, 결과저장 과정을 반복하는 것을 명령어 파이프라이닝이라고 한다. 명령어들을 명령어 파이프라인에 넣고 동시에 처리하는 기법을 의미한다.

 

그래서 명령어들의 실행이 끝난 후에야 다른 명령어를 실행하는 것보다 훨씬 더 빠르고, 효율적이다. 최대 4개의 명령어를 동시에 수행할 수 있기 때문이다.

 

이처럼 높은 효율성을 지니긴하지만, 반대로 특정 상황에서는 성능 향상에 실패하는 경우가 있다. 이를 파이프라인 위험이라고하며, 여러 종류가 있다.

---

데이터 위험

모든 명령어는 동시에 처리할 수 없다. 만약 이전 명령어가 반드시 실행되었을 때 실행할 수 있는 명령어가 있다고 치자. 예를 들면 a = 2 + 3 명령어와 c = a * 2 명령어가 있다고치자.

 

만약 명령어를 동시에 실행하고 있는데, c = a * 2 명령어가 막 인출될 때 a = 2 + 3 명령어가 해석되고 있다면 아직 a가 메모리에 저장되지 않았으므로 오류가 발생하거나 이상한 값이 a에 대입된다. 이처럼 어느 한 데이터가 다른 데이터와 의존적인 관계를 지닐 때, 이 데이터가 속한 명령어를 무작정 실행시키려하면 파이프라인에 오류가 발생할 수 있는데, 이를 데이터 위험이라고 칭한다.

 

데이터 위험을 막기 위해서는 기존에는 명령어 실행 후 레지스터에 저장이 필수였지만, 명령어 실행 후 그 다음 명령어의 입력값으로 곧바로 대입할 수 있는 새로운 통로를 만들거나 (데이터 포워딩)

제어장치가 데이터 위험을 감지하고 다음명령어들을 강제로 잠깐 멈춰세워서 시간을 버는 방식 (파이프라인 스톨) 등의 방식이 있다.

 

데이터 위험에는 몇 가지 하위 위험들이 존재한다.

 

https://velog.io/@phantom5087/Computer-ArchitectureCS%ED%8C%8C%EC%9D%B4%ED%94%84%EB%9D%BC%EC%9D%B4%EB%8B%9D-Out-of-order-pipeliningOOO

[Computer Architecture/CS/파이프라이닝] Out of order pipelining(OOO)과 WAR,WAW Hazard

참고

 

1. RAW (Read After Write | 쓰기 후 읽기)

앞서 말한 경우가 RAW hazard에 속한다. 의존성이 있는 명령어 간 일어나는 위험

 

2. WAR (Write After Read | 읽기 후 쓰기)

병렬연산에서 주로 발생하는데

1: R1 <- R2 + R3
2: R2 <- R4 + R5

Rn은 n번째 레지스터에 저장된 값을 사용하라는 뜻

 

이런 연산이 동시에 발생한다고하자. 1번연산은 2번 레지스터와 3번 레지스터 값을 더하라는 뜻이다. 문제는, 동시에 연산이 수행되어 2번째 연산이 먼저 끝난 경우, 기존 2번 레지스터에 1번연산에서 사용해야할 값이 아니라 이상한 값이 들어있게되는 것이다. 즉, 1번연산이 끝난 뒤에 사용해야할 데이터가 이미 저장된다는 뜻이다. 

 

3. WAW (Write After Write | 쓰기 후 쓰기)

1: R1 <- R2 + R3
2: R1 <- R4 + R5

마찬가지로 병렬연산에서 발생한다. 위 상황이 끝나면 R1에는 무슨 값이 저장될까? 답은 알수없다이다.

이렇게 병렬연산에서 데이터 덮어쓰기가 발생할 수 있는 상황을 뜻한다.

---

제어 위험

전에도 한 번 다뤘지만 기본적으로 PC레지스터는 현재 명령어의 메모리주소 +1을 해가며 다음 메모리주소를 찾는다. 파이프라인에서도 마찬가지로, 현재 명령어를 처리하고, 그 명령어 주소의 +1 한 주소에 있는 명령어를 순차적으로 파이프라인에 넣어서 처리한다.

 

그런데 만약 JUMP나 분기가 일어나서 기존 명령어 주소의 +1한 부분이 아니라 완전히 다른 특정부분으로 이동해야한다면? 기존에 파이프라인에 넣었던 명령어들은 실행될 필요가 없어지므로 괜히 실행한 것이 된다. 이를 제어 위험이라고 칭하며 이를 막기 위해서는 프로그램이 어디로 분기할지 미리 예측한 후 그 주소를 인출하는 분기 예측을 사용한다.

---

구조적 위험

앞서 말했듯이 2코어 4스레드와 같은 환경에서는 4개의 스레드들이 2개의 코어를 나눠써야하는데, 이 때 서로 다른 명령어가 동시에 ALU나 레지스터 등에 접근하려할 때 발생한다. 자원 위험이라고도 부른다.

 

가장 효과적인 방법은 부품을 추가하는 것이고, 여의치 않을 때에는 제어장치가 구조적 위험을 감지해 충돌이 우려되는 명령어를 잠깐동안 멈춰세운다. (파이프라인 스톨) 만약에 한 개의 코어의 자원이 놀고 있는 경우에는 명령어가 다른 코어의 자원을 사용하도록 할 수 있다.

---

슈퍼스칼라

슈퍼스칼라란 파이프라인을 여러 개 사용하는 방식이다. 오늘날 대부분의 CPU에서 이 방식을 사용한다. 한 클럭마다 여러 명령어의 인출, 실행, 해석, 저장이 이루어진다. 예시로는 한 클럭마다 동시에 여러 명령어를 인출, 실행, 저장할 수 있는 멀티스레드 프로세서를 들 수 있다.

 

다만 슈퍼스칼라 역시 파이프라인을 여러 개 사용하는만큼 파이프라인의 위험에 대응하기 위해서 아주 고도로 설계되어야한다. 일반적인 파이프라인 한 개보다 위험을 피하긱 어렵기 때문이다.

---

비순차적 명령어 처리

OoOE; Out-of-order execution

오늘날 CPU성능 향상에 크게 기여하기도했고 대부분의 CPU가 사용하기 때문에 알아두는 것이 좋다고한다. OOO라고도 한다.

 

파이프라이닝과 슈퍼스칼라 기법은 모두 "명령어를 순차적으로, 동시에 실시한다"였다. 하지만 이런 기법은 파이프라이닝의 의존적인 데이터 간 발생하는 데이터 위험과 같은 문제가 발생할 수 있었다.

 

OoOE는 "명령어를 굳이 순차적으로 실행할 필요가 없고, 의존적이지 않은 명령어를 먼저 실행시키자"라는 생각에서 출발한 기법이다. 즉, 의존성이 있는 명령어를 처리하기 위해서는 명령어가 의존하고 있는 명령어의 실행이 완전히 종료되어야하기 때문에, 기존 파이프라이닝에서는 명령어가 다 끝나기를 기다릴 뿐이었지만, OoOE는 의존성이 있는 명령어의 처리를 나중에 처리하고 우선은 의존성이 없는 명령어부터 처리하는 기법이다. 명령어 파이프라인이 멈추지 않는다.

 

이렇게 두 명령어를 바꿀 때에는 서로 의존성이 전혀 없는 명령어를 바꿔야한다. 이를 위해서는 CPU가 명령어들의 의존관계를 가지고있는지 판단하고, 순서를 바꿔 실행가능한지 판단할 수 있어야한다.

---

의존성 검사하기 - Instruction window

In-order 과정에서는 그냥 들어온 명령어들을 순차적으로 실행하면 됐지만 Out-of-order 과정에서는 몇 가지 처리가 필요하다. 아래 나오겠지만, OOO과정에서도 데이터 위험이 발생할 수 있다. 따라서 의존성 검사 등을 위해서 명령어들을 멈춰세우고 검사를 진행해야한다.

 

https://cyber0946.tistory.com/90#google_vignette

Out-of-order Processor Pipeline 이란

https://cyber0946.tistory.com/90#google_vignette / 문제시 삭제

명령어 윈도우의 간단한 그림이다. 프로그램이 시작되면, 여러 명령어들(명령어의 수는 OS마다 다름)을 명령어 윈도우에 넣고, 의존성 검사를 진행하고, 명령어 한 개를 추가하고 가장 처음 추가된 명령어 한 개는 빼고...하는 식으로 의존성 검사를 이어간다.

 

---

가짜 의존성 제거하기 - Register Renaming

파이프라인의 데이터 위험은 제대로 관리되지 않은 OOO에서도 얼마든지 발생할 수 있다. WAW나 WAR이 이에 해당한다.

 

위에서 말한 WAW나 WAR은 얼핏보면 의존성이 있는 것처럼 보인다. 하지만 실제로는 서로 독립적으로 값을 저장하는 것에 불과할 뿐이므로 진짜 의존성은 아니다.

 

따라서 제대로 OOO를 구현하려면 이런 가짜 의존성을 가려내고 실제 의존성을 찾는 몇 가지 기능들이 필요하다. 대표적인 방법이 Register Renaming으로, CPU가 명령어에 표현할 수 있는 레지스터의 수는 적으나 실제로 컴퓨터가 가지는 물리적인 레지스터는 엄청나게 많다. 따라서 CPU가 내부적으로 각기 다른 주소에 값을 저장하게한다. 이러면 데이터 덮어쓰기 같은 문제는 발생되지 않으므로 WAR나 WAW는 발생하지 않는다. 명령어 윈도우 내부에서 일어난다.

 

Register Renaming은 맵테이블이라는 자료구조를 사용하는데, 특정 레지스터에 값을 저장하면 CPU가 저장된 레지스터 번호와 실제로 저장된 레지스터의 번호를 매핑한 후, 이를 맵테이블에 매핑된 정보를 기록한다. 가령 R3에 값이 저장되었고, 실제로는 시스템의 P50번에 값이 저장되었다면, 맵테이블에 R3 - P50이라고 매핑 정보를 저장한다.

 

이후 다른 명령어가 들어와서 R3의 값을 원하면 맵테이블에 저장된 P50으로 레지스터의 주소를 바꾸는, Rename 과정이 일어난다. 또한 맵테이블은 새 값이 들어오면 기존 값은 사용하지 않기 때문에, Rename 과정은 순차적으로 일어난다. 따라서 맵테이블이 갱신되었는데 갱신 이전의 값을 원하는 일은 일어나지 않는다.

 

 

명령어 A, B가 있고 명령어 A가 R3에 값을 저장하고 CPU가 P50에 값을 저장하려했으나 의존성 때문에 시간이 걸린다고할 때, 명령어 B가 먼저 실행된 후, R3에 값을 저장하고 CPU는 P51에 값을 저장했다고 치자.

 

명령어 A가 실행되기 직전에 맵테이블의 정보가 R3 -> P50으로 바뀐다. 그리고 의존성 때문에 작업이 잠시 멈추면 명령어 B가 실행되고, B가 실행되기 직전에 그즉시 맵테이블의 정보가 R3 - P51로 바뀐다(Rename). B에 의존적인 명령어들 때문. 그리고 명령어 B가 실행되고 그 정보를 ROB에 저장, 명령어 A도 오래걸리긴했지만 실행이 끝나고 실행된 정보를 ROB에 저장한다. 그리고 ROB가 명령어 A와 B를 순차적으로 커밋시키면서 최종적으로는 R3 -> P51 로 맵테이블에 저장된다.

 

만약 A와 B 사이에 P50의 정보를 원하는 명령어 C가 있다고할 때, Rename 과정은 순차적으로 일어나므로 명령어가 실행되기 전에 맵테이블을 보고 R3 -> P50으로 명령어의 수정이 일어난다.

 

그래서 만약 명령어 A, B, C가 있고, 명령어가 A - B - C 순으로 실행되고, A와 B는 위의 상황을 거쳤는데 C가 P50의 값을 필요로한다면, C는 P50에 접근할 수 없고, 애초에 이런 상황은 모순적 상황이다. 왜냐하면 이미 맵테이블에서 P51로 매핑이 바뀌었는데 P50을 필요로하는 명령어가 발생할 수 없기 때문이다. 마치 R3에 데이터를 저장하고 R3에 새 데이터를 저장한 다음에 R3에서 이전에 저장한 데이터를 찾는 것과 같이 때문이다.

 

아무튼 설명이 길어졌는데, OOO에서 일어날 수 있는 데이터 위험을 해결하는 방안으로 대표적인 것이 Register Renaming으로,

 

WAR 상황에 대입해보면..

1: R1 <- R2 + R3
2: R2 <- R4 + R5

P30 <- P2 + P3

MapTable: R1 - P30, R2 - P2, R3 - P3

 

P31 <- P4 + P5

MapTable: R1 - P30, R2 - P31, R3 - P3, R4 - P4, R5 - P5

 

로, 실제로는 세부적인 레지스터 번호를 저장하고, 맵테이블에 레지스터 번호와 세부 레지스터 번호를 매핑한다. 그리고, 기존에 1번연산과 2번연산 사이에 명령어가 생기면, 명령어는 그 때의 맵테이블에 따라서 R2 - P2로 매핑하게되는 것이다.

 

WAW 상황에 대입해보면..

1: R1 <- R2 + R3
2: R1 <- R4 + R5

P40 <- P2 + P3

MapTable: R1 - P40, R2 - P2, R3 - P3

 

P45 <- P4 + P5

MapTable: R1 - P45, R2 - P2, R3 - P3, R4 - P4, R5 - P5

 

로, WAR 상황과 비슷하게 진행된다. 1번연산과 2번연산 사이에 명령어가 생기면 그 시점의 맵테이블에 따라서 정보를 확인한다. 이로써 WAR와 WAR를 해결할 수 있게되는 것이다.

 

그리고 만약, P40 값을 원하는 명령어가 1번연산과 2번연산 사이에 생기면 C의 R1 값은 P40으로 바뀐다. 왜냐하면, Register Renaming 과정은 순차적으로 일어나기 때문이다.

---

대기열 - Reservation Station

Renaming을 거친 명령어는 이제 가짜의존성의 가능성을 걷어냈고, Reservation Station으로 이동한다.

모든 명령어들은 오퍼랜드가 제대로 구비되었는지 조사해야한다. 그래야 의존성이 있는 명령어들이 제대로 실행되기 때문이다.

 

오퍼랜드가 모두 준비되지 않았다면, 즉 의존성이 있는 데이터가 아직 준비되지 않았다면 여기서 대기한다. 그리고 CDB(Common Data Bus)에서 Result 값이 오는지를 조사한다.

 

오퍼랜드가 준비되었다면 그 연산을 수행한다. 메모리 저장용이라면 관련된 버퍼에 보낸다거나.. ALU에 보낸다거하는 등

만약 ALU로 이동되었다면 ALU result 값이 다시 메모리 저장명령어로 변환되어 위의 과정을 거치고, CDB에 태워서 다른 Reservation Station으로 이동시킨다.

 

여기 내용은 극히 간략화시킨 것으로,

https://cyber0946.tistory.com/90#google_vignette

Out-of-order Processor Pipeline 이란

https://velog.io/@phantom5087/Computer-ArchitectureCS%ED%8C%8C%EC%9D%B4%ED%94%84%EB%9D%BC%EC%9D%B4%EB%8B%9D-Out-of-order-pipeliningOOO

[Computer Architecture/CS/파이프라이닝] Out of order pipelining(OOO)과 WAR,WAW Hazard

https://blog.naver.com/khhh12333/221460590891

[컴구조] Tomasulo algorithm

https://deep-math.tistory.com/33

[컴퓨터구조] Tomasulo Algorithm

여기 블로그들을 참고하면 좋을것이다. 물론 나중에 나도 컴구 공부하면 해야함 그 때 글 올려서 링크 하나 끼워둘게요

---

이렇게 비순차적명령어 처리기법은 OOO를 사용할 때, 비순차적으로 명령어를 처리하는 과정에 대해서 알아보았다.

위 과정을 Tomasulo 알고리즘이라고도 칭하고, (진짜 Tomasulo 알고리즘은 부동소수점 연산에서 고안된 것이기에 위의 과정에서 FP 작업큐를 추가하는 경우가 있다.) 이전보다 성능도 좋고 효율적이라고.

 

암튼 천년만년 이 글에 매달릴 수는 없어서 이정도로 줄여보려한다. 더 깊은 내용이 필요하면 재미나이와 구글링을 통해서 더 깊은 정보를 알아보도록 하는걸로. 나중에 컴구 전공을 들어보면 또 다를 듯하다.

 

그리고 이 글의 반이 책 내용이 아닌데 이거 책 독서로 쳐도 되나