[system programming] Parallel Architectures (ILP, DLP, TLP)
본 게시글은
서울대학교 데이터사이언스대학원 성효진 교수님의
데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를
학습을 목적으로 재구성하였습니다
이번 시간에 배운 주된 내용은
병렬 처리에 관한 내용이다
하지만 그 전에 원래 os에서
exception을 어떻게 처리하는지가 나오는데
사실 이전 시간에 다 배웠던 내용이라
간단히만 설명하고 넘어가셨다
exception handling에 대해서 잠깐만 살펴보자
우리 컴퓨터가 프로세스를 실행하는 도중에
exception이 발생하면 이를 어떻게 처리할까?
실제로 각 exception ID가 있고
이를 이용해서 kernel안에 있는 exception table에 들어간다
그럼 예상하지 않았던 exception branch로 이동하게되고
control flow hazard를 발생시킨다
에러 상황에선 어떤 일이 발생할까?
에러 상황에도 여러 종류가 있는데
잘못된 memory에 접근했을 때는
IF 단계에서 에러가 발생하고
ISA에서 정의된 Instruction이 아니거나
그런 illegal instruction이 들어왔을 때는
RF 단계에서 에러가 발생한다
또한 0으로 나눈다거나 하는
연산 과정에서 에러가 발생하면
ALU 단계에서 에러가 발생하고
마지막으로 메모리에 접근 하는 단계에서
권한이 없는 메모리 주소에 접근을 하거나 하면
다시 Memory fault가 발생할 수 있다
exception을 처리 하는 방식은 여러 가지가 있다
위 ppt에서는 BNE에 대한 설명인데
컴퓨터는 만약 에러 상황이 발생했다고 하면
instruction을 BNE로 변경하고
다음 instruction의 주소인 PC+4를 미리 저장해둔다
이는 exception 전용 handler이다
지금까지 배운 내용들을 정리해보자
프로세스가 한 개 있는 경우에
어떻게 성능을 최적화 시키는지를 확인했다
하나의 프로세스로 구성된 시스템의 퍼포먼스는
instruction의 개수, CPI, cycle time에 의해서 결정된다
또한 성능 향상을 위해서
instruction의 병렬성을 활용가능하다
또한 병렬로 실행할 수 있게 하기 위해서
하드웨어적인 장치들을 추가해야한다
하지만 이러한 방법은 당연히 근본적으로 한계가 있었다
우선 우리가 보고 있는 프로그램이
한 개의 스레드 안에서만 실행된다는 점이다
우리가 지금까지 주로 배운 ILP는
하나의 스레드 안에서 최대한의 병렬성을 뽑아내는 방식이다
따라서 로직이 굉장히 복잡하고
디자인도 굉장히 복잡해진다
또한 이렇게 로직이 복잡해질수록
power측면에서도 불안정해진다
그래서 ILP를 넘어 점점 더 큰 병렬성을 활용하도록 발전했는데
그게 바로 이번 시간에 본격적으로 배울
Data Level Parallelism (DLP)
Thread Level Parallelism (TLP)이다
이제 Parallel Architecture에 대해 자세히 배워보자
parallelism은 크게 3가지가 있다
첫 번째는 우리가 지금까지 배운 ILP
하드웨어가 실제로 명시적으로 드러나있지 않은 병렬성을 찾아서
하드웨어 단계에서 실행하는 것을 말한다
하지만 TLP와 DLP가 갖는 ILP와의 가장 큰 차이점은
TLP와 DLP는 일반적으로
사용자가 직접 병렬하는 코드를 작성한다는 점이다
혹시나 우리가 병렬 코드를 작성하지 않더라도
컴파일러 단에서 병렬하는 코드를 생성해서
어쨌든 코드의 형태로 병렬이 하드웨어에 들어간다는 점이
ILP와의 가장 큰 차이점이다
TLP는 일을 하는 코드를 함수 혹은 task단위로 작성하는 것인데
우리가 이미 무엇은 병렬로 실행할지 결정해서
코드 단에서 작성해서 실행시킨다
ILP, TLP, DLP를 그림으로 비교해보자
ILP는 dependency에 의해
병렬이 가능한 코드만 병렬을 하기 때문에
매번 꼭 병렬로 실행되지 않을 수가 있다
TLP의 경우 하나의 열이 한개의 스레드를 의미한다
조금씩 다른 instruction을 한 번에 수행한다
마지막 DLP는 같은 cycle에서는
같은 instruction을 실행한다는 점이 가장 큰 차이점이다
instruction은 같지만 내부에 들어가는 데이터는 다르다
이게 사용자 입장에서는 어떻게 보일까?
ILP는 사용자 입장에서는 병렬로 보인다
또한 TLP의 경우는 명시적으로 병렬성을 드러내서
코드를 작성해야한다
그럼 그게 실제로 스레드와 매핑이 되어서 병렬이 실행된다
DLP는 위 도식처럼
동시에 표현(?)할 수 있다고 한다
실행의 방식을 위 처럼 4가지로 구분할 수 있는데
instruction이 1개인지 여러개인지
혹은 데이터가 1개인지 여러개인지로 구분한다고한다
이를 Flynn's Taxonomy라고 부른다
가장 단순한게 SISD인데
single instruction single data로
1개의 instruction과 1개의 data이다
가장 단순한 구조이고
register를 한 개씩 읽어오고
실행한 instruction stream도 한개여서
한 번에 하나씩 수행한다
두 번째는 SIMD인데
single instruction multiple data이다
instruction stream이 1개라서
그게 모든 PU로 들어간다 (CPU같은 것)
하지만 각 PU마다 데이터가 들어오는 선은 여러개인데
데이터가 다 다르다는 의미이다
이를 통해 벡터 연산을 수행하는데
그럼 벡터 레지스터의 다른 값이 PU로 들어가고
하지만 실행하는 instruction은 한개가 되는 것인데
이게 SIMD 방식의 병렬성이다
이러한 방식을 사용하는 가장 대표적인게
CPU에 같이 있는 SIMD 엔진인 vector processor이고
GPU가 바로 이런방식으로 연산을 수행한다
정확하게 SIMD 방식은 아니고
이를 변형한 방식으로 실행한다
MIMD는 PU들이 각각 다 다른 instruction을 받아서 실행한다
데이터도 각자 PU가 각자 다른 데이터를 읽어고고
보통 이런 형태는 multicore CPU에서 많이 사용된다
만약 코어가 4개라고 한다면
각각 4개의 코어를 동시에 돌면서
다 다른 일을 하고 다른 데이터를 처리하는 형태이다
MISD는 상대적으로 덜 쓰이는 방식인데
같은 연산을 두 번 이상하는 그런 형태이다
안전성이 중요한 그런 프로그램들에서
똑같은 코드를 redundant하게 사용하는 경우가 있는데
그럴때 MISD 방식이 사용된다
하드웨어 측면에서 병렬성을 어떻게 뽑아낼까
다른건 상대적으로 덜 중요하기 때문에
가장 밑에 2개에 대해서만 설명해주신다고 한다
앞에서도 계속 나왔던 말인데
ILP의 최대 단점은 모든 병렬성을
한 개의 스레드 안에서만 찾는다는 점이다
하드웨어가 두 개 이상의 스레드를 처리할 수 있다면
ILP의 제약은 훨씬 줄어드는데
왜냐하면 두개의 스레드는 서로 dependency가 있을 가능성이
거의 없기 때문이다
프로세스를 실행하기 위해 필요한 것은
앞에서도 배웠지만
코드 주소, stack pointer, 그리고 레지스터 주소이다
이 세개는 프로세스의 정의와도 같다
그런데 이러한 프로세스를 변경하는
context switching을 오직 운영체제만이 관리하게 되면
overhead가 너무 심해지는데
이걸 하드웨어적으로 빠르게 수행하기 위해서
코어가 저 프로세스 state를 하드웨어 적으로 2개씩 들고있다
2개의 하드웨어에서 프로세스 state를 들고있어
빠르게 왔다갔다 변경이 가능하게 되는 것이다
또한 요즘은 대부분 멀티코어 프로세서인데
예전에만 하더라도 프로세서에는 코어가 1개만 있었다
따라서 예전에는 칩과 칩을 연결해야
병렬적으로 사용이 가능했는데
이제는 대부분 칩 한개 안에 여러개의 코어가 들어있다
우리의 칩은 따라서 코어 안에 여러개의 SMT를 갖고있고
그렇게 코어도 여러개 갖게 되는 것이다
Data level에서는 아까 봤던 vector processor가 있다
instruction은 한 개인데
이걸 여러개의 다른 데이터들을 넣어서 처리한다
ppt가 뭔가 이상하다 ㅋㅋ
아무튼 single thread 구조에서
아키텍처의 트렌드를 설명하는데
예전에는 CISC의 형태에서
RISC의 형태의 instruction으로 변해왔다
CISC와 RISC는 수업 가장 처음에 한 번 나왔는데
CISC는 1개의 instruction에 많은 연산을 하는 것이고
RISC는 그 반대로 instruction 한 개에
한 개의 연산만 수행하는것이다
그래서 single thread 환경에서는
superscalar로 ILP에서
overlap을 하는 방식으로 처리한다
이제 하드웨어 단위에서 더 큰 병렬성을 처리하는
방법을 한 번 살펴보자
multi-thread processor로
fine-grained multithreading이 있는데
register, PC, stack pointer가 항상 세트인데
이 3개를 추가적으로 하드웨어에 넣어서
스레드적으로 관리하는 것이다
앞에서 말했다시피 context switching이 매우 빨라진다
SMT는 좀 더 aggressive한 방식이다
한 cycle 안에서도 여러 스레드의 instruction을 같이 실행하는 것이다
같은 사이클에서도 여러 스레드의 코드를 보면서
지금 실행할 수 있는 것이 있다면 가져온다
ILP를 극대화 할 수 있는 것이다
intel이 사용하고 있는 하이퍼 스레딩이
이러한 방식을 사용한다
CMP는 칩 안에 코어가 여러개 있는 것을 말한다
VLIW는 그냥 이런게 있다고 생각하면 좋은데
병렬실행을 하는데 하드웨어가 동적으로 실행하는 것이 아니고
컴파일러가 코드를 분석해서 코드에서 병렬로 실행할 수 있는
독립적인 instruction을 묶어서 그걸 길게 만들어 실행하는 방식이다
이렇게 하면 하드웨어 적으로는 굉장히 단순해지지만
compiler가 굉장히 일을 잘해야 성능을 최대한으로 끌어올릴 수 있다
마지막으로 벡터 프로세서에 대해서 조금 더 알아보자
멀티 스레드인것처럼 실행이 되는데
앞에서 말했던 것처럼
한개의 instruction에 여러 개의 데이터를 넣어서
실행하는 방식이다
GPU는 DLP와 TLP를 결합한 형태의
병렬성을 사용한다
concurrent와 parallelism의 차이를 알아보자
많은 사람들이 착각하는 개념인데
concurrency는 사실 parallelism(병렬)이 아니다
concurrency는 우리가 앞에서 배웠던
os의 context switching의 개념이다
우리의 CPU는 코어가 1개만 있다면
어떤 프로세스를 수행하다가 잠깐 멈추고
또 다른 프로세스를 수행하고
그러다가 또 멈추고 다른 프로세스를 수행하고를 반복한다
이 번갈아가면서 하는 과정을 매우 빠르게 수행하는 것이지
이건 사실상 병렬이 아니다
하지만 parallelism은 멀티코어 CPU에서
한 개의 코어가 실제로 각각의 프로세스들을
동시에 처리하는 것이다
아무튼 현대의 CPU들은
parallelism과 concurrency를 모두 사용한다
그래서 하드웨어의 병렬성도 중요하지만
우리 코드가 concurrent한가도 중요하다
concurrency를 찾아낸다는 것은
어떤 연산들은 서로 간의 dependency가 있는지 확인하고
그게 없는 instruction들을 최대화하는 것이다
앞에서 봤던 CMP에 대한 내용이다
superscalar에만 전적으로 의존하는 것이
사실상 한계가 있기 때문에
여러 개의 코어를 두어서
TLP를 가능하게 한다
superscalar도 굉장히 aggressive하게 수행할 수는 있는데
ILP 자체에 한계가 있다고 한다
지금까지 왜 CMP구조가 될 수밖에 없었는지에 대한 내용이다
간단하게만 살펴보자면
application 측면에서는 수십 수백개의
instruction도 수행해야할 때가 있는데
FP의 경우에는 40개의 instruction들이
동시에 실행되어야하는 그런 코드들이 존재한다
따라서 superscalar의 한계 때문에
코어를 여러 개를 두는 형태로 발전한 것이다
정말 간략하게 superscalar와 CMP를 비교한 그림이다
왼쪽이 6개의 instruction을 동시에 수행할 수 있는
superscalar microarchitecture이고
오른쪽이 코어가 4개가 있는 CMP 구조이다
왼쪽 superscalar에서는 rename하는 공간이 있는데
이는 앞에서 나왔든 dependency를 없애기 위함이고
ooo 방식으로 instruction들을 처리하지만
결국 마지막에는 순서대로 reorder 되어서
reorder buffer에 저장된다
오른쪽은 코어가 4개가 있는데
L2를 공유하는 형태로 구성되어 있다
이 L2를 공유하기 위해서 comunication bar를 두고있다
정말 대략적으로 마이크로 아키텍처를 표현한
그림이라고 한다
벡터 엔진에 대해서 아주 간단하게 살펴보자
data parallelism이 스레드 병렬과 다른 이유는
데이터가 다르다는 점을 활용하는 병렬성이기 때문이다
아까 앞에서 봤던 SIMD 방식이다
그렇다면 이런 벡터 연산을
우리 컴퓨터는 어떤 연산에 활용할까?
가장 대표적으로는 loop level parallelism이 있는데
쉽게 생각해서 반복문에 활용한다고 보면 된다
우리 반복문을 보통 짤 때에는
똑같은 Instruction인데 데이터만 다르게해서 루프를 돌린다
그래서 이걸 보통 SIMD한 형태로 표현한다고 한다
그렇게 되면 반복문이 매우 빠르게 수행되는 것이다
loop level parallelism의 예시이다
위와같이 4개의 vector instruction이 있는데
X, X, Y Add 연산을 한 번에 해서
그 값을 다시 쓴다고 한다..
뭐 그래서 벡터 연산의 방식으로 하면
2번만 수행해도 1000개를 다 커버할 수가 있다고한다
하지만 중요한 점은
위 예시에서는 iteration간에 아무런 dependency가 없다는 점이다
실제로 이런 벡터 연산을 하는 processor는
우리 컴퓨터 안에 하드웨어적으로 존재하고
이걸로 벡터 연산을 수행하게 된다
위 ppt slide에 있는 예시 코드 같은 경우도
병렬화를 해서 여러 개를 묶어서
vector instruction으로 만들어 수행하면
성능이 굉장히 좋아진다고 한다
하지만 하나의 vector instruction안에는
데이터 간 dependency가 전혀 없어야한다
vector 연산을 할 때는
어떤 control flow가 있는 것이 아니다
벡터 간의 각 instruction은 의존성이 없어서
독립적으로 수행이 가능하다
또한 vector는 instruction을 읽어 올 때
연속된 공간을 읽어올 수 있다
stride는 메모리에서 다음 요소까지 떨어진 거리를 말하는데
우리가 벡터연산을 할 때는 stride만큼 떨어져있는
값에서 가져와서 메모리에 넣어준다
맨 처음에 배운 single issue scalar와
vector 프로세서를 비교해보자
single issue scalar는
한 번에 하나씩 instructio을 가져오는데
vector는 한 번에 vector 단위로 instruction을 가져온다
또 single issue scalar의 경우
register를 아무데나 access할 수 있지만
vector의 경우 고정된 access만 가능하다
마지막으로 single issue scalar는
instruction 개수가 너무 많아지면 문제가 될 수 있어서
i cache같은 방법으로 해결을 하는데
vector같은 경우는 그런 부분에서는 최적화가 되어있다고한다
이제 superscalar와 vector를 비교해보자
또한 벡터는 병렬 수행에 유리하고
병렬성에 관계없이 superscalar는
control logic에서의 오버헤드가 큰데
오른쪽은 그냥 벡터 유닛이 없으면
쓰지 않는다
superscalar는 성능 예측이 어려운데
vector는 그에 비해 성능 예측이 쉽다
이번 ppt는 다 그림들이 이상하게 들어가있다 ㅎ..
아무튼 이건 되게 예전의
고전 vector processor의 그림이라고 한다
main memory의 vector load store에서
데이터를 가져온다
vector functional units라는 것이 있는데
중요한 것은 벡터 레지스터에서 값을 가져온다는 것이다
scalar 레지스터는 값을 한 개씩 저장하는데
벡터는 여러 개의 값을 하나에 저장해서
한개가 매우 길다
그래서 한 번에 여러 개의 값을 읽어서
파이프라인에서 한 번에 실행이 가능하다
이번 수업 내용은 여기까지가 끝이다
또 여기까지가 프로세서 아키텍처와 관련된 내용이라고한다
그럼 이번 수업 정리도 끝-!