본문 바로가기

My Study/Programming&Theory

CPU의 파이프라인 실행의 원리

"프로세서를 지탱하는 기술" 이라는 책을 보면서 정리하는 것입니다. 이하 "참고책"


여기 글에서는 파이프라인 실행 원리를 중심으로 파이프라인의 실행에 있어서 열쇠가 되는 '버블 사이클' 이 무엇인지

파이프라인에서 문제가 되는 세 가지 해저드인 '구조적 해저드', '데이터 해저드', '제어 해저드' 를 알아보겠습니다.

파이프라인은 병렬처리에서 기본이므로 꼭 알도록 합시다.


먼저 기본적인 프로세서의 명령 실행에 대해서 알아보도록 하겠습니다.


( 참고책 그림 3.1 : 파이프라인 실행을 수행하는 프로세서의 구조 )


1. 메모리

2. 페치 유닛 : 다음에 실행할 명령을 읽는다.

3. 디코드 유닛 : 명령을 해석한다.

4. 레지스터 파일 : 오퍼랜드를 읽는다.

5. 연산 유닛 : 연산을 수행한다.

6. 로드/스토어 유닛 : 메모리 액세스를 수행한다.


그리고 다음의 전제를 가지고 진행하겠습니다.

 - 프로세서는 RISC형이며, 명령의 길이는 일정합니다.

 - 연산에 사용하는 오퍼랜드는 레지스터 파일에서 읽습니다.

 - 메모리 액세스는 로드 명령과 스토어 명령으로 수행됩니다.

 - 이상적인 메모리가 있어서 1사이클에 메모리 읽고 쓰기가 가능하다고 가정합니다.



그림 3.1의 프로세서가 명령을 처리하는 일련의 동작을 그림 3.2에 나타냈습니다.


( 참고책 그림 3.2 : 프로세서의 명령처리 )


1. 제 1사이클에서 페치 유닛이 다음에 실행할 명령을 메모리에서 읽고 이를 디코드 유닛으로 보냅니다.

2. 제 2사이클에서 디코드 유닛은 명령을 해석해서 몇 번 레지스터에서 오퍼랜드를 읽어낼지, 어떤 처리를 수행할지, 결과는 몇 번 레지스터에 써넣을지 등의 정보를 추출해서 그 아래 각 유닛에게 지시를 내립니다.

3. 제 3사이클에서 레지스터 파일은 디코드 유닛에서 내려진 지시에 따라 오퍼랜드를 읽어서 연산 유닛이나 로드/스토어 유닛에 보냅니다.

(연산유닛에 보낸 경우)

4. 제 4사이클에서 연산 유닛은 명령에서 지시된 연산을 처리합니다.

5. 제 5사이클에서 연산결과를 반환해서 레지스터 파일 중에 지시된 번호의 레지스터에 씁니다.


이렇게 결과를 반환해서 쓰는 동작을 Write Back 이라고 합니다. 결과를 반환함으로써 하나의 명령 처리가 끝납니다.


(로드/스토어 유닛에 보낸 경우)

4. 제 4사이클에서 로드/스토어 유닛은 3번으로부터 온 메모리 어드레스를 메모리로 보내 메모리로부터 데이터를 읽습니다.

5. 제 5사이클에서 메모리로부터 읽은 데이터를 레지스터 파일에 씁니다.


스토어 명령인 경우는 오퍼랜드로서 저장될 테이터가 추가되며, 로드/스토어 유닛은 메모리 어드레스와 스토어 데이터를 메모리로 보내서 쓰기작업을 수행합니다.


이제 파이프라인의 동작을 제대로 알아보도록 하겠습니다.


페치유닛, 디코드 유닛, 레지스터 파일, 연산 유닛이 연이어서 명령을 처리할 경우 각 유닛의 동작은 그림 3.3과 같이 됩니다.


( 참고책 그림3.3 : 4개의 명령을 연속 실행할 경우 파이프라인 동작 )


그림 3.3의 제 4사이클을 예로 살펴보면, 페치 유닛은 4번째인 스토어 명령을 메모리에서 읽고 있고 동시에 로드/스토어 유닛은 메모리에서 1번째인 로드 명령어의 데이터를 읽고 있습니다. 또한 제 5사이클에서 디코드 유닛은 4번째인 스토어 명령을 디코드하고, 레지스터 파일은 3번째인 연산 명령의 오퍼랜드를 읽어내고, 연산 유닛은 2번째 명령의 연산을 실행하고, 또 다시 최초 로드 명령의 결과가 레지스터 파일에 Write Back 되고 있습니다.


이처럼 명령을 처리하는데 몇 가지 유닛이 필요하더라도 파이프라인 처리를 수행하면, 이상적으로는 하나의 유닛이 명령을 처리하는 시간간격으로 연달아서 명령을 처리해갈 수 있게 되는 것입니다.



구조적 해저드

이러한 파이프라인엔 문제가 있습니다. 예들 들면, 제 4사이클에서 메모리는 4번째 스토어 명령 읽기와 1번째 로드 명령의 데이터 읽기 처럼 두 곳에서 사용되고 있습니다. 또한 제 5사이클에서는 레지스터 파일이 3번째 명령의 오퍼랜드 읽기와 1번째 명령인 로드 데이터 쓰기에 사용되고 있습니다.


이와 같이 동시에 다수의 명령이 메모리나 레지스터 파일, 연산 유닛 등 하나밖에 없는 자원을 필요로 해서 쟁탈하게 되는 문제를 파이프라인 처리의 구조적 해저드라고 합니다. 이러한 구조적 해저드를 해소하기 위한 접근방법 두 가지를 살펴보도록 하겠습니다.


 - 파이프라인 버블, 파이프라인 스톨


구조적 해저드에 대한 대처는 프로세서의 하드웨어 레벨에서 수행합니다.


( 참고책 그림 3.4 : 구조적 해저드를 해소하기 위해 버블을 넣은 경우의 파이프라인 실행 )


그림 3.4에서 X표시가 된 박스로 표시된 사이클은 3번째, 4번째 명령의 처리를 진행하지 않으므로, 파이프라인에 버블이 낀 듯한 상태라는 의미에서 이를 파이프라인 버플이라고 합니다. 또한 이와 같이 파이프라인 처리가 중도에 끊어지는 것을 파이프라인 스톨이라고 합니다.


 - 자원 추가


구조적 해저드에 대처하는 또 하나의 방법은 구조적 해저드를 해소하기 위해 '자원을 추가' 하는 방법입니다.


( 참고책 그림 3.5 : 명령용 메모리와 레지스터 파일 쓰기용 포트를 추가해서 구조적 해저드 해소하기 )


그림 3.5에서는 명령용 메모리와 레지스터 파일의 쓰기용 포트를 추가하고 있습니다.

명령용과 데이터용 메인 메모리를 갖추기란 어렵지만, 프로세서 칩에 탑재하는 소용량 캐시 메모리의 경우는 별도로 갖추더라도 큰 부담이 되지 않으므로 고성능 프로세서는 명령 캐시와 데이터 캐시를 가지고 있으며, 양쪽으로의 액세스를 병행해서 실행할 수 있는 구조가 사용되고 있습니다.


또한 레지스터 파일에 관해서는 2개의 오퍼랜드 읽기와 결과 쓰기를 동시에 수행할 수 있는 회로구성을 갖는 레지스터를 만들었습니다.



데이터 해저드

이어서 파이프라인에서 문제가 되는 두 번째 해저드인 데이터 해저드에 대해 설명하겠습니다.

프로그램 내에서는 다음과 같이 이전 명령의 연산결과인 c를 그 다음 명령의 입력 데이터로 사용하는 경우가 빈번히 발생합니다.


c = a+b;

e = c+d;



( 참고책 그림 3.6 : 데이터 의존성이 있는 명령을 연속 실행한 경우 파이프라인 동작 )


그러나 그림 3.6을 잘 보면 최초 명령의 연산결과는 제 4사이클이 끝나면서 구해진다. 이를 레지스터 파일을 경유하지 않고 직접 다음 명령의 오퍼랜드로서 넘기게 되면, 다음 명령은 제 5사이클에서 연산을 수행할 수 있게 되므로 2개의 버블 사이클을 줄일 수 있습니다.

 현재의 프로세서에서는 이처럼 레지스터 파일을 바이패스해서 연산결과를 전달 할 수 있는 레지스터 바이패스 구조로 되어 있으므로, 1사이클에서 연산할 수 있는 정수 덧뺄셈이나 AND, OR 등의 논리연산의 경우에는 데이터 해저드를 신경 쓸 필요는 없습니다.


 - 소프트웨어 파이프라인 처리


데이터 해저드에는 소프트웨어를 이용한 대처방법이 있습니다.


c = 0.0;

for ( i = 0; i < N; i++ )

c = c+a[i];


c+a[1]의 c는 이전의 c+a[0]의 결과이므로 이전의 부동소수점 덧셈 명령의 결과에 의존하게 되는 데이터 해저드가 발생합니다.

( 일반적인 덧셈, 뺄샘은 데이터 해저드가 발생 안하지만 부동소수점 연산을 발생됩니다. 설명은 생략 )

이를


c1 = c2 = ... = c8 = 0.0;

for( i = 0; i < N; i+=8 )

{

c1 = c1+a[i];

c2 = c2+a[i+1];

...

}

c = c1+c2+...+c8;


로 작성하면 푸르 내에서 c1이 다시 사용되는 것은 c2, ... c8 계산이 끝난 다음이 되며, 그림 3.8과 같이 처리가 수행됩니다.


( 참고책 그림 3.8 : 소프트웨어 파이프라인 처리를 수행한 경우의 실행상태 )


최초에는 c1계산, 다음은 c2 계산과 같이 각각의 계산이 부동소수점 연산기 내를 흘러가므로 이 처리방법을 소프트웨어 파이프라인 처리라고 합니다.


 - 데이터 해저드 해소와 제반 문제


이번 예와 같은 8계열 계산에서 데이터 해저드가 완전하게 해소되는지 여부는 사용하는 프로세서의 부동소수점 덧셈 연산 사이클 수가 슈퍼스칼라로 여러 명령을 병렬로 실행할 수 있는지 등에 의존합니다. 또한 앞의 예에서는 매번 갱신되는 c1~c8을 기억해두기 위해 8개의 레지스터가 필요하며, a[i]~a[i+7] 을 넣기 위해서도 8개의 레지스터가 필요해집니다.

 이번 예는 매우 간단한 예였지만, 보다 많은 변수가 사용되는 실제 프로그램에서는 계산에 필요한 레지스터의 수는 훨씬 많아집니다. 그러나 x64 프로세서에서는 레지스터가 16개, RISC에서도 32개밖에 없으므로 이와 같은 분할 횟수는 레지스터 수로 제한되며, 버블 사이클을 완전하게 메우기는 곤란합니다. 그렇지만 거의 같은 시간에 복수의 계열을 병렬로 처리할 수 있으므로 2~4계열의 분할이라도 소프트웨어 파이프라인화함에 따라 데이터 해저드에 의한 손실을 줄여서 성능을 높일 수 있습니다.


 - 컴파일러에 의한 최적화와 그 한계


위와 같은 소프트웨어 파이프라인을 의식한 프로그램을 사람이 직접 작성하지 않더라도 가능한 범위에서 자동적으로 소프트웨어 파이프라인 처리를 수행하는 코드를 생성하는 컴파일러도 존재합니다.

 또한 메모리를 액세스하는 로드 명령도 1사이클로는 실행할 수 없으므로 컴파일러는 로드 명령을 가능한 한 명령열의 전방으로 이동해서 이와 같은 로드,사용 관계가 있는 명령을 갈라놓는 최적화를 하는데 부작용이 발생할 가능성이 있는 조건분기 명령이나 함수호출을 넘어서 로드 명령을 앞으로 이동시킬 수는 없으므로 최적화에는 한계가 있습니다.

 이와 같은 경우에는 처리내용을 이해하고 있는 프로그래머가 명시적으로 로드 명령이나 프리페치 명령을 먼저 실행해서 프로세서에 데이터를 미리 저장하게 해두는 프로그램을 작성하는 편이 좋은 결과를 얻을 수 있을 것입니다.



제어 해저드

 파이프라인에서 문제가 되는 세 번째 해저드인 제어 해저드를 살펴보겠습니다.

IF~ELSE 구문의 경우 IF의 조건을 판정하여 조건이 성립하는 경우는 IF측의 명령을 실행하고, 성립하지 않는 경우는 ELSE측 명령을 실행합니다. 프로세서는 통상 연속한 어드레스의 명령을 실행해가는데, IF문의 경우는 조건을 계산하는 명령이 있고 그것이 성립하면 IF 다음 주소 명령을 실행하고 성립하지 않는 경우는 ELSE측 명령이 있는 주소로 점프할 필요가 있습니다.

 조건의 성립/불성립으로 처리가 나뉘어 점프하는 것을 분기라고하고, 조건을 판정해서 점프를 하는 명령을 조건분기 명령이라고 합니다.

 이와 같은 점프를 수행하는 경우는 점프할 주소가 확정되기까지 다음 명령의 페치를 시작할 없으므로 버블 사이클이 발생합니다. 이를 파이프라인 처리의 '제어 해저드' 라고 합니다.

 조건분기명령 직전에 조건을 계산하는 연산 명령이 있는 경우 파이프라인의 동작은 그림 3.9와 같이 됩니다.


( 참고책 그림 3.9 : 조건분기명령을 실행하는 경우 파이프라인의 동작 )


조건분기명령은 제 4사이클에 오퍼랜드로서 ELSE측 명령의 어드레스를 읽어두고, 제 4사이클의 종료 시 얻을 수 있는 이전 연산 명령의 계산결과를 바탕으로 제 5사이클에서 IF 의 조건이 성립하는지 아닌지를 판정합니다. 그리고나서 조건이 정립하지 않을 경우는 ELSE측 명령 주소를 다음 명령 주소로서 페치 유닛에 통지합니다.


 그러나 조건이 성립하지 않음을 알게되는 것은 제 5사이클이 끝날 때이므로 조건분기명령의 바로 다음 3개의 명령의 페치나 디코드가 진행되어 버립니다. 이 때문에 점프할 곳이 판명되면 파이프라인은 이러한 명령의 실행을 중지합니다. 그리고나서 제 6사이클에서 ELSE 측 명령 주소가 통지되므로 제 7사이클에서 ELSE 측 명령이 페치되고 그 후에는 통상의 파이프라인 실행이 계속 됩니다.

 분기가 없다면 다음 명령어 페치는 제 3사이클에 존재하는데 비해, 분기가 수행되는 경우에는 다음 명령의 페치는 7사이클로, 4 사이클만큼 버블이 들어가게 됩니다. 


 - 조건분기명령과 프로그램


프로그램에서 조건분기명령을 사용하지 않을 수는 없지만, 다음과 같이 프로그래밍을 하면 성능이 개선되는 경우가 있습니다.

1. 함수를 인라인 전개하여 루프 내에 포함시켜서 점프를 필요로 하는 호출과 리턴을 없앤다

2. 실행횟수가 많은 루프 내에서는 프로그램의 행수를 늘리더라도 가능한 한 조건분기를 사용하지 않도록 한다.


일반적으로 함수의 인라인 전개는 컴파일러 옵션으로 지정할 수 있으므로 실행횟수가 많은 루프 내에서 작은 함수 호출이 있는 경우에는 시도해보기 바랍니다.


 - Loop unrolling


루프는 처음 혹은 마지막에 루프횟수의 끝을 판정하는 조건분기명령이 있습니다. 이 조건분기명령은 루프의 마지막회 이외의 경우에는 계속하는 방향으로 분기를 하게 됩니다.


c = 0.0;

for( i = 0; i < N; i++ )    c = c+a[i];


위 코드를


c = 0.0;

for( i = 0; i < N; i+=4 ) {

c = c+a[i];

c = c+a[i+1];

c = c+a[i+2];

c = c+a[i+3];

}


와 같이 루프의 내부를 나열함으로서 루프를 돌 때마다 i에 4를 더해가면 루프의 횟수는 1/4이 되고 루프를 돌기 위한 조건분기명령의 실행횟수가 1/4가 됩니다. 정확히 말하면, 루프 횟수가 꼭 4의 배수라고는 할 수 없으므로 4의 배수의 횟수만큼은 이와같이 하고 남은 횟수는 별도로 처리하면 됩니다.

 이와 같이 루프의 내부를 여러 번 써서 루프 횟수를 줄이는 방법을 Loop unrolling 이라고 합니다.

-----------------------------------------------------------------------

마지막으로 이번 글을 짧게 요약해 보도록 하겠습니다.


파이프라인은 

1. 메모리

2. 페치 유닛 : 다음에 실행할 명령을 읽는다.

3. 디코드 유닛 : 명령을 해석한다.

4. 레지스터 파일 : 오퍼랜드를 읽는다.

5. 연산 유닛 : 연산을 수행한다.

6. 로드/스토어 유닛 : 메모리 액세스를 수행한다.


위 6가지가 각각 사이클마다 수행이 됩니다. 즉 일정 사이클이 넘어서면 1사이클 마다 명령어 1개씩 처리가 된다고 보죠..


하지만 이러한 파이프라인의 장애물이 있으니..


구조적 해저드

동시에 다수의 명령이 메모리나 레지스터 파일, 연산 유닛 등 하나밖에 없는 자원을 필요로 해서 쟁탈하게 되는 문제


해결 방안 ( 프로그래머가 어떻게 할 수 있는게 아님 )

파이프라인 버블 : 첫번째 명령어 끝날 때까지 아에 기다리는게 아닌 두번째 명령어도 페치, 디코드 같은 것은 하고 중간에 버블을 넣어서 잠시 대기하였다가 레지스터 파일, 연산 유닛.. 진행하는 방식(파이프라인 스톨)


자원 추가 : 명령용 메모리와 레지스터 파일의 쓰기용 포트를 추가


데이터 해저드

데이터 의존성이 있는 명령을 연속 실행한 경우 발생

1사이클에서 연산할 수 있는 정수 덧뺄셈이나 AND, OR 등의 논리연산의 경우에는 데이터 해저드를 신경 쓸 필요 없음 )


해결 방안

소프트웨어 처리

c = 0.0;

for ( i = 0; i < N; i++ )

c = c+a[i];


c1 = c2 = ... = c8 = 0.0;

for( i = 0; i < N; i+=8 )

{

c1 = c1+a[i];

c2 = c2+a[i+1];

...

}

c = c1+c2+...+c8;


각각의 변수를 둠으로서 데이터 의존성을 떨침


또한


프로그래머가 명시적으로 로드 명령이나 프리페치 명령을 먼저 실행해서 프로세서에 데이터를 미리 저장하게 해두는 프로그램을 작성하는 편이 좋은 결과를 얻을 수 있을 것


제어 해저드

점프를 수행하는 경우 점프할 주소가 확정되기까지 다음 명령의 페치를 시작할 없으므로 버블 사이클이 발생하는 것


해결 방안

소프트웨어 처리( Loop unrolling )

c = 0.0;

for( i = 0; i < N; i++ )    c = c+a[i];


c = 0.0;

for( i = 0; i < N; i+=4 ) {

c = c+a[i];

c = c+a[i+1];

c = c+a[i+2];

c = c+a[i+3];

}


조건 분기 횟수 줄어듬


규칙

1. 함수를 인라인 전개하여 루프 내에 포함시켜서 점프를 필요로 하는 호출과 리턴을 없앤다

2. 실행횟수가 많은 루프 내에서는 프로그램의 행수를 늘리더라도 가능한 한 조건분기를 사용하지 않도록 한다



일단 공부는 했으니 조금이라도 적용시켜보도록 노력은 해봐야겠네요.

-----------------------------------------------------------------------

아래는 테스트 해본 코드입니다. ( 코드는 더러우므로 보실분만 보세요 )

데이터 의존성 & 조건분기 횟수 줄이기 둘다 적용했습니다.

( 컴파일러 최적화 옵션은 전부다 껐습니다. )


돌려보면 결과는 다음과 같습니다.

[파이프라인 비최적화]   B8C40000 , 159FDAEE3

[파이프라인 최적화]      B8C40000 , 35A424A0


[파이프라인 비최적화]   B8C40000 , 5D046494

[파이프라인 최적화]      B8C40000 , 3641EB6D


[파이프라인 비최적화]   B8C40000 , 1566B0177

[파이프라인 최적화]      B8C40000 , 2FCF6CD1


[파이프라인 비최적화]   B8C40000 , 502111E3

[파이프라인 최적화]      B8C40000 , 30256A89


[파이프라인 비최적화]   B8C40000 , 14E65F464

[파이프라인 최적화]      B8C40000 , 2F0A02FD


[파이프라인 비최적화]   B8C40000 , 4E961D54

[파이프라인 최적화]      B8C40000 , 2F0DF45D


[파이프라인 비최적화]   B8C40000 , 14E477957

[파이프라인 최적화]      B8C40000 , 301B9D78


[파이프라인 비최적화]   B8C40000 , 4F4DD778

[파이프라인 최적화]      B8C40000 , 2F21FF00


[파이프라인 비최적화]   B8C40000 , 14E4D16B1

[파이프라인 최적화]      B8C40000 , 2EEA6EDA


[파이프라인 비최적화]   B8C40000 , 4FCC2620

[파이프라인 최적화]      B8C40000 , 2ED9896A


[파이프라인 비최적화]   B8C40000 , 14E86285A

[파이프라인 최적화]      B8C40000 , 2EDCB8B9


[파이프라인 비최적화]   B8C40000 , 4F8C4E7C

[파이프라인 최적화]      B8C40000 , 2F24178C


[파이프라인 비최적화]   B8C40000 , 14EC30B2E

[파이프라인 최적화]      B8C40000 , 2F49B481


[파이프라인 비최적화]   B8C40000 , 4E8954B2

[파이프라인 최적화]      B8C40000 , 2FA51959


[파이프라인 비최적화]   B8C40000 , 14F95DF5E

[파이프라인 최적화]      B8C40000 , 2F31C6F4


[파이프라인 비최적화]   B8C40000 , 4F7FCC38

[파이프라인 최적화]      B8C40000 , 2EFE119B


[파이프라인 비최적화]   B8C40000 , 14EEC5E1F

[파이프라인 최적화]      B8C40000 , 2F20AF44


[파이프라인 비최적화]   B8C40000 , 4EB8C646

[파이프라인 최적화]      B8C40000 , 2EF2CBB2


[파이프라인 비최적화]   B8C40000 , 14ED13FE3

[파이프라인 최적화]      B8C40000 , 2F37EF80


[파이프라인 비최적화]   B8C40000 , 4F3FA4A6

[파이프라인 최적화]      B8C40000 , 2F57AFC4


[파이프라인 비최적화]   B8C40000 , 14F849A72

[파이프라인 최적화]      B8C40000 , 3054DA12


[파이프라인 비최적화]   B8C40000 , 4EFCFAF3

[파이프라인 최적화]      B8C40000 , 2EC6A34B


[파이프라인 비최적화]   B8C40000 , 14E7E5758

[파이프라인 최적화]      B8C40000 , 2F988217


[파이프라인 비최적화]   B8C40000 , 4E664240

[파이프라인 최적화]      B8C40000 , 2F5E5145


[파이프라인 비최적화]   B8C40000 , 15013A02F

[파이프라인 최적화]      B8C40000 , 31646470


[파이프라인 비최적화]   B8C40000 , 507A1476

[파이프라인 최적화]      B8C40000 , 2F1EAB0C


.....


결과는 똑같이 나오는 두 코드를 각각 돌려 나온 사이클 값들을 비교해보면 ( CPU 사이클 값 )

심하게는 7배까지 차이가 나기도 하고 평균적으로 4배 정도의 속도 차이가 있습니다.

그리고 최적화 옵션을 전부 키게 되는 경우 파이프라인 최적화 부분은 조건문을 쓰지 않았기 때문에 더욱 많이 최적화됩니다.
즉, 최적화를 하게되면 더욱 그 차이는 심해집니다.

또한 위 코드를 가지고 컴파일되서 나온 바이너리를 어셈코드로 봐보니 실행되는 코드 양의 차이는 거의 없습니다.
코드 양의 차이는 없는데 속도가 7배 이렇게 차이가 난다는 것은 
CPU 내 파이프라인이 명령어 배치로 인한 해저드 발생 정도의 차이겠지요.

하지만 돌아가는 코드수가 적으면... 차이가 없다고 보면 됩니다..;


'My Study > Programming&Theory' 카테고리의 다른 글

Time based Keystroke Password  (4) 2013.08.15
CPU 캐시의 원리  (1) 2013.08.11
Windows x64 binary 모듈 단위 이동  (7) 2013.07.27
ZwProtectVirtualMemory 의 악몽 2  (0) 2013.07.25
Windows Hang Dump 분석  (3) 2013.07.24