8. Pipeline이란

Multy Cycle Design을 이용해 pipeline을 통해 processor의 성능을 개선시키는 방법에 대해 정리하겠습니다.

 

Pipelining

(1) Pipelining이란

동시에 여려개의 명령어를 overlapped하여 실행하는 방법을 말합니다.

프로세스에서 pipeline은 전체 프로세스를 여러 stage로 나누어 동시에 여러개의 명령어가 서로 다른 stage상에 위치하게 함으로써 동시에 여러 명령어를 처리하는 방식을 말합니다.

 

● 장점

단위 시간당 처리되는 명령어의 수를 높힙니다. 이는 instructino throghput을 높이는 것과 같은 의미입니다.

그리고 datapath 상에 resource인 functional unit의 사용역시 개선 시킬 수 있습니다.

 

● 단점

stage를 나누기 위한 레지스터와 동시에 여러 명령어를 처리하기 위한 control 신호르 제어하는 stage machine 등 추가적인 하드 웨어가 필요해서 하드웨어가 복잡해진다는 단점이 있습니다.

 

(2) Pipeline divisions

명령어가 처리 되는 과정은 아래와 같이 5단계로 나뉘어집니다.

각 단계별로 사용되는 하드웨어 장치가 모두 다르기 때문에 최대 5개의 명령어가 overlapped하여 실행될 수 있습니다.

각 단계는 단게와 단계사이에 레지스터를 추가해 1clock cycle에 소요되도록 설계됩니다.

 

 

(3) Load instruction execution in 5 stages

Load 명령어는 메모리로부터 데이터를 읽어와 레지스터에 저장하므로 5개의 stage가 모두 사용 됩니다.

 

① Instruction Fetch

첫 번째 clock cycle에서 instrution fetch가 이루어지게 됩니다.

소프트웨어 프로그램 명령어를 가리키고 있는 즉 PC 값이 가리키고 명령어의 메모리 주소를 하나 읽어들이는 과정이 됩니다.

 

② Register Fetch and Instruction Decode (RF/ID)

명령어를 CPU로 fetch (읽기)를 했다면 두 번째 clock cycle에서 이 명렁어를 Instruction decode 과정을 거치게 되는데 이 과정에서 op코드가 무엇인지 피연산자가 무엇인지 어떤 레지스터를 사용하는지 immediate 값이 무엇인지를 분석하게 됩니다.

그리고 R-format의 add 명령어를 보면 rd, rs, rt 3개의 레지스터를 사용하는데 먼저 두 피연산자를 저장한 rs와 rt 레지스터를 연산을 위해 읽어오는 작업을 합니다. 이 과정이 operand fetch라고 합니다.

 

③ Execute

세 번째 clock cycle에서 add, sub와 같은 ALU 연산이 레지스터에 fetch된 값을 통해 ALU가 수행하게 됩니다.

 

④ Memory Access

네 번째 clock cycle에서 메모리 접근이 일어날 수 있습니다.

 

⑤ Write Back

다섯 번째 clock cycle에서는 write back이 일어납니다.
연산이 수행된 후 연산의 결과가 레지스터 rd 또는 메모리에 저장됩니다.

PC값이 다음 명령어를 가리키도록 합니다.

위와 같은 5가지 step이 반복적으로 진행되면서 프로그램이 실행되게 되는 것입니다

 

(4) 여러 개의 Load 명령어가 pipeline에서 실행되는 과정

3개의 load 명령어(load1, load2, load3)가 각 5단계에서 어떻게 Multy cycle로 동작하는지 설명 드리겠습니다.

 

과정1)

첫 번째 load 명령어가 Cycle1에서 Instruction Fetch(IF)됩니다.

그리고 두 번쨰 clock cycle에서는 load1의 RF/ID 작업이 이루어지고 두 번째 load 명령어인 load2의 IF 작업이 실행됩니다.

두 번째 clock cycle에서는 load1의 RF/ID가 실행되고 load2의 IF 가 실행되므로

한 clock cycle에서 여러 명령어의 서로 다른 stage가 동시에 실행됨을 알 수 있습니다.

 

과정2)

clock cycle3에서는 load1은 EX 과정을 수행하고 load2sms RF/ID 그리고 load3는 IF stage를 수행하면서 clock cycle3에서는 3개의 load 명령어의 각기 다른 stage가 실행되게 됩니다.

 

과정3)

위 과정으로 Clock cycle5 까지 3개의 load 명령어의 각기다른 stage가 실행되고

Clock cycle6에서는 load1의 명령어가 종료되고 load2는 WB stage를 load3는 MEM stage를 수행하게 되면서 두 load 명령어의 실행이 계속 됩니다.

 

과정4)

Clock cycle7에서는 load1, load2 명령어의 실행이 끝나고 load3의 WB stage가 남아 있게 됩니다.

 

이렇게 pipeline을 구성하여 명령어를 실행하면 단위 시간당 처리하는 명령어를 의미하는 throughput의 성능이 향상되게 됩니다.

single cycle 과 비교했을 때 pipeline이 계속해서 실행한다고 했을 때 매 clock cycle 마다 한 명령어가 종료되므로 CPI는 1에 가까워집니다.

 

 

(5) Multy cycle에서 Load 명령어 예시

Load 명령어의 각 stage에서 어떤 funcitonal unit이 사용되는지 정리하겠습니다.

 

● stage1: Instruction Fetch

우선 첫 번째로 clock cycle에서 instrution fetch가 이루어지게 됩니다.

소프트웨어 프로그램 명령어를 가리키고 있는 즉 PC 값이 가리키고 명령어의 메모리 주소를 하나 읽어들이는 과정이 됩니다.

이 단계가 진행 된 후 RF/ID 레지스터에 현재 실행 될 명령어와 다음에 실행될 명령어의 주소 값이 저장되게 됩니다.

 

● stage2: Register Fetch and Instruction Decode

두 번째 clock cycle이 되면 lw 명령은 stage2를 진행합니다.

이 단계에서는 명령어 decode롤 통해 control 신호를 결정하고 피연산자를 fetch하게 됩니다. R-format 명령어는 레지스터 파일로부터 피연산자를 읽어 들이고 I-format명령어는 imm 16bit의 값을 sing-extended 하여 32bit로 하여 다음 stage3로 전달하게 됩니다.

 

● stage3: Execute

세 번째 clock cycle이 되면 lw 명령은 stage3를 진행합니다.

ALU 연산을 통해 load 명령어가 요구하는 동작을 수행합니다.

레지스터 파일로부터 읽어들이 base address를 singn-extend된 offset과 더해서 데이터 메모리에 주소를 결정하게 되며 그리고 다음 clock falling edge의 연산결과를 다음 stage로 저달하기 위해 EX/MEM 레지스터에 값을 저장하게 됩니다.

 

● stage4: Memory Access

네 번째 clock cycle이 되면 lw 명령은 stage4를 진행합니다.

execute 단계에서 결정된 데이터 메모리 주소를 Data menory File에 인가하여 데이터를 메모리로부터 읽어들이는 것입니다. 읽어 들여진 메모리 값은 MEM/WB 레지스터에 저장되어 다음 stage로 전달됩니다.

 

● stage4: Write Back

다섯 번째 clock cycle에서는 write back이 일어납니다.

 

Multy cycle 디자인을 위해 추가 된 각 단계 사이에서의 레지스터(RF/ID, ID/EX, EX/MEM, MEM/WB)을 통해 서로 겹치지 않고 명령어들을 동시에 여러개 실행하 수 있게 됩니다.

 

이 상태에서는 문제점이 존재하는데,

write 데이터와 함께 레지스터 파일의 입력으로 인가되는 Write register의 값이 instruction decode 되고 있는 새로운 명령어들에 대해 이미 overlap이 되어 Write register의 값이 회손된다는 문제점이 있습니다. 즉 Write register의 값을 write back stage 까지 보존을 해줘야합니다.

이 문제점을 해결하기 위해서는 ALU연산 결 과인 Write register의 값 write back 단계까지 보존해주기 위한 방법으로 이 값을 유지해주는 datapath가 추가 됩니다.

그러면 load 명령어 write back 단계로 진입하더라도 다른 명령어에 의해서 Write Register의 값이 훼손 되지 않고 공급될 수 있습니다.

 

 

(6) Hazards

프로세스의 전체 datapath를 n개의 stage로 나눌 때 최대 n개의 명령어가 동시에 datapath 상에서 실해될 수 있기 때문에 이상적으로는 n배의 throughput 향상이 있게 됩니다.

하지만 이것에는 제한 요소가 존재합니다.

프로세서의 pipeline을 통한 throughput 향상을 제한하는 요소를 Hazrads라고 합니다

Hazrads는 연속적인 명령어 실행을 제한 시킵니다.

Hazrads의 종류에는 3가지 종류가 있습니다.

 

● structual hazard

하드웨어 구조적 문제입니다.

pipeline상에 두 명령어가 동시에 하나의 하드웨어 resource에 접근하는 resource conflict입니다.

하나의 예시로 load(5개의 stage 필요), add(4개의 stage 필요, memory access 필요없음)명령이 동시에 실행된다고 할 때

load명령이 write back 단계에 진입할 때 한 cycle 늦게 시작한 add 명령어도 write back 단계로 진입할 수 있게 됩니다. 그럼 동시에 두 명령어가 하나의 레지스터 파일에 write 작업을 수행하기 때문에 register file에서 conflict가 발생해서 structual hazard가 발생하게 되는 것입니다.

이것의 해결책으로는 뒤에 실행된 add 명령어가 structual hazard가 해소된 다음 실행될 수 있도록 실행을 미루면 됩니다

 

해결 방법1)

pipeline stall 또는 pipeline bubble이라고 불리는 Delay instruction을 추가하여 앞선 명령어의 funcitonal unit의 사용이 끝날 떄 까지 뒤 따라오는 명령어를 잠시 쉬게하는 것입니다.

그렇다면 뒤 따라오는 명령어는 1cycle~2cycle 정도 쉬게 되어 delay가 발생하지마 전체적인

throughput 관점에서는 손해가 별로 없게 됩니다.

 

해결 방법2)

하드웨어 설계를 변형해 여러 명령어가 동시에 사용할 수 있게 만들어주는 것입니다.

즉 레지스터 file에 두 개의 명령어 접근을 허용하도록 하는 것입니다.

이 방법은 하드웨어를 제설계해야하고 복잡도를 증가시키기 때문에 일반적으로

 

structual hazard을 해결하는 방법은 pipeline stall을 추가하는 해결 바업1)을 사용하는 것인데 add명령 R-type은 MEM 단계가 없는데 이 단계 즉 pipeline stall을 추가하여 MEM 단계에서 아무것도 하지 않는 stall, bubble 상태로 만들어 그냥 쉬게 하는 것입니다.

 

● Data hazard

이것은 예로 A=B+C, D+A+E와 같은 순차적인 add 명령이 있다고 할 때 두 번째 덧셈 명령어의 경우 첫 번째 덧셈의 결과인 A의 값을 두 번째 덧셈의 피연산자로 사용하는데 pipeline stage 상에서 두 번째 명령어가 A를 읽어들이는 시점은 instruction decode 단계입니다.

이 단계에서 register File로부터 피연산자를 fetch하게 되는데 두 번째 명령어가 instruction decode 단계에 있을 때, 첫 번째 명령어는 겨우 execute 단계에 있게 되어

두 번째 명령어의 피연산자 A를 가져올 때 A의 값이 할당되지 않았거나, update되지 않았으므로 문제가 발생하게 됩니디.

Data dependency type ① RAW(Read After Write) 하나의 레지스터에 대해 선헝해는 I명령어가 값을 쓰고 그 이후 뒤 따르는 j명령어가 그 값을 read 할 때 발생하는 depedency이다.   ② WAW(Write After Write) 선행 된 I명령어에서 값을 쓴 후에 뒤 따르는 j명령어에서 값을 write해야하는 상황에서 발생하는 dependecncy이다. 이 경우는 파이프라인 상에서 레지스터에 write을 하는 state가 write back stage로 한정되기 때문에 Data hazard의 원인은 아니다.   ③ WAR(Write After Read) 선행하는 I명령어에서 특정한 레지스터로부터 값을 읽고 그리고 난 이후에 해당 레지스터에 데이터를 쓸 때 발생하는 dependencey가 된다. operand fetch 같은 경우는

 

Data hazard solution ① Stalls 해저드를 해결하는 가장 쉬운 방법으로 파이프라인을 Stalls 시키는 것으로 dependence가 해소 될 때까지 뒷 따라오는 명령어를 쉬게하는 것이다. 하지만 파이프라인 Stall이 빈번하게 발생하면 전체적인 프로세서의 성능이 떨어지게 됩니다.   ② Change clock cycle 전체 clock cycle을 반으로 나누어 앞쪽에서는 레지스터의 write back을 수행하고 뒷 쪽에서는 read를 수행하는 방식이며 이 방식은 한 clock cycle안에 레지스터에 write과 read를 할 수 있기 때문에 그만큼 파이프라인 stalls을 줄일 수 있습니다.   ③ Forward or bypassing ALU의 연산결과를 write back하기 전에 미리 다음 명령어로 전달해주는 방식이다. 이방법을 사용하면 RAW dependence 가 있을 때 write back이 끝 날 때 까지 다음 명령어들이 기다릴 필요가 없어진다.   <한계> 대부분의 low dependency로 인한 데이터 해저를 해결하지만 해결 못하는 경우도 존재한다. 이 경우는 어쩔 수 없이 파이프라인을 Stall 시키는 방법을 사용해야한다.   ④ Restrict sofwware 하드웨어적 해결책이 아닌 소프트웨어적 해결책으로 주로 컴파일러에서 intruction 스케줄링을 통해 데이터 해저드가 발생하는 명령어의 sequences를 제거해주는 방식이다.

 

 

● Control hazard

Control hazard는 instruction hazard드라고 부르기도 합니다.

보통 프로그램 카운터(PC)의 값이 브랜치(branch)로 인해 변경되었을 때 발생합니다.

예를 들어 if –else문에서 if문이 돌지 else문이 돌지는 if문의 제어문에 의해 결졍이 됩니다.

즉 if문명령어 또는 else문 명령어가 돌려고하는데 아직 if문의 제어문의 결정이 이루어지지 않았다면 이 문제를 해결하기 위해 명령어를 다시 읽어온는 re-fetch 문제가 발생하며 이는 overhead를 야기합니다.

Control hazard solution ① Stall 이 방법은 branch taken이 발생하면 파이프라인을 채워놨던 명령어들을 flush시키고 새로운 주소로부터 명령어를 fetch 해오는 간단한 방법입니다.   ② Predict taken or not-taken 브랜지가 taken되었는지 taken되지 않았는지를 예측하는 방법으로 기존의 beq명령어 다음에 단순히 PC+4를 통해 명령어를 fetch 해왔던 방법과는 다르게 예측 알고리즘을 적용해 beq 명령어 다음 브랜치 target Address로부터 명령어를 패치를 할지 등을 예측하는 방법을 말합니다. 예측이 틀릴 경우 Stall을 하는 방법과 동일한 결과가 발생하게 되고, 예측이 맞을 경우 추가적인 성능 저하가 없게 됩니다. 이 방법은 Control hazard를 해결하는데 가장 일반적으로 사용되는 방법이다.   ③ Scheduling branch delay slot 브랜치가 taken or not-taken을 결정할 때 까지 control dependency가 전혀 없는 명렁들을 fetch해서 실행하는 방식으로 컴파일러의 intruction 스케줄링을 가장 기본적인 방식으로 하고 있는데 이런 명령어들은 branch delay slot을 통해 taken여부와 상관 없이 파이프라인을 실행하는 방식이 됩니다. MIPS Processor 역시 branch delay slot 을 사용합니다.

Branch Prediction scheme ① Predict-not-taken 무조건 not-taken이라고 예측하는 방법으로 branch 명령 다음에 파이프라인을 채우는 명령어들을 not-taken path에서 명령어들을 fetch해서 파이프라인을 채우는 것입니다.   ② Predict-taken 이 방식은 무조건 taken이라고 예측하는 방법으로 1번과 2번 방법을 static branch prediction(정적 예측)이라고 합니다. 이 기법은 하드웨어적 구현은 간단하지만 예측 정화도는 떨어집니다.   ③ Dynamic branch prediction - 이 방식은 일반적으로 가장 많이 사용되는 기법으로 각각 브랜치의 taken, not-taken 히스토리에 기반해서 다음 브랜치의 결과를 동적으로 예측하는 방법으로 구현이 어렵지만 정확도가 비교적 높습니다. 이 방식은 과거의 브랜치 히스토리를 기반으로 미래의 브랜치 taken여부를 예측하는 기술로 branch hisory table이라 불리는 추가적인 하드웨어 장치를 통해 히스토리를 저장하고 히스토리를 기반으로 branch prediction을 수행합니다.   - branch hisory table 이란 브랜치 명령어에 PC 값에 일부 LSB 비트를 index로 사용하고 이전 실행에서 해당 브랜치 명령어에 taken 또는 not-taken여부를 1bit 로 기록한 table입니다.   한 프로그램 내에서 여러 브랜치가 존재하기 때문에 명령어 별로 히스토리르 기록해서 다음 예측에 활용하는 방식이며 Dynamic branch prediction 기법은 실제 브랜치 결과를 평가해서 매번 branch hisory table 을 새로 업데이트 하며 만약 예측이 틀린 경우에는 파이프라인을 flush한 뒤에 새로운 주소에서 명령어르 fetch 하는 방식으로 동작합니다. 따라서 branch prediction의 성능은 prediction의 정확도와 예측 실패시에 패널티에 의해 결정됩니다.   일바적으로 Dynamic branch prediction은 1bit 또는 2bit prediction 형태로 구현이 됩니다. branch hisory table각 index 마다 주로 1bit 또는 2bit의 prediction state가 포함됩니다.

- 1bit prediction 초기 상태를 prediction taken 상태에 있다고 가정하면(동일한 PC 주소 값을 가진 브랜치 명렁이 실행되면 무조건 taken이라고 예측하는 가정) 이때 만약 실제 브랜치 결과가 taken이면 자기 자신을 유지하는, predict taken 상태를 유지합니다. 반면 브랜치의 결과가 not-taken이라면 상태 천이라고 불리는 state 전환이 이루어져 predict not-taken 상태로 상태 천이가 일어나며 이 상태에서 반복문에 의해 동일한 브랜치 명령어가 다시 실행되면 이번에는 not-taken으로 예측하게 되는 것입니다. 이와 같은 방식으로 현제 상태의 값이 branch predict에 예측 출력 값이 되며 각각의 dege에 있는 값들이 실제 branch taken 여부가 되게 됩니다. 예측 상태와 실제 상태 값에 의해 다음 예측 값이 결정되는 구조입니다. ibit predict 역시 매우 높은 정확도를 가집니다.   2bit prediction 1bit prediction를 확장한 방법으로 상태의 수가 2개에서 4개로 들어나게 됩니다. 1bit prediction 에서는 taken와 not-taken만 존재했는데 2bit prediction 에서는 상태의 값이 4개이므로 4단계로 나누게 되는데 (Strongly taken, Weakly taken, Not taken, Weakly not taken) 좀 더 천천히 점전적으로 예측이 변경됩니다. 예를 들어 Strongly taken상태에서 Not-taken이 한 번 발생했다고 하면 1bit prediction에서는 바로 Not-taken의 상태를 예측하여 상태 천이가 일어났지만 2bit prediction 에서는 Strongly taken상태에서 Not-taken이 한 번 발생하면 Weakly taken 상태가 됩니다. 따라서 여전히 taken을 예측하게 됩니다. 정리하면 (Strongly) taken 상태에서 Not-taken으로 상태가 천이 되기 위해서는 Not-taken이 두 번 발생해야함을 의미합니다. 이와 같은 방식으로 branch predict의 민감도를 낮췄다고 할 수 있으며 1bit prediction의 예측도 보다 더욱 예측도가 올라가게 됩니다.