Minsoo's Studyroom

1. Project Introduction

이번 프로젝트에서는 저번 프로젝트에서 구현한 Single Cycle 방식의 MIPS 시뮬레이터를 향상 시킬 것이다. 기존의 Single cycle은 1 cycle에 1 instruction을 끝내기 위한 과정으로 순차적인 실행 방식을 취해 결과적으로 모든 instruction의 수행 시간은 수행시간이 가장 긴 instruction에 맞춰 똑같이 정렬된다. 하지만 Pipeline의 경우 IF, ID, EX, MEM, WB다섯 단계로 이루어져 있는 multi cycle의 구조를 띄고 있어 하나의 instruction이 완료되기 까지 5사이클이 요구 되어 하나의 instruction이 명령을 수행하는 중간에 다음 instruction은 쉬고 있는 것이 아닌 앞선 명령어가 하나의 단계를 마치고 다음 단계로 넘어갈 때, 해당 단계를 수행하도록 하는 것이 pipeline의 구조라고 말 할 수 있다. 즉, 아래 그림과 같이 여러 Instruction이 동시에 처리시켜 전체 instruction이 처리되는 속도를 높이는 것이 pipeline의 목적임을 알 수 있다.

이때, 각 단계는 특정 명령을 수행하게 된다. IF단계에서는 pc를 증가시키며 올바른 instruction을 추출하며, ID단계에서는 IF단계에서 추출한 명령어를 decode하고 레지스터 값을 읽어오며, EX단계에서는 ALU에 의해 특정 연산을 수행하며 MEM단계에서는 메모리에 접근하여 필요한 경우 메모리에 저장, 값을 읽어오는 명령을 수행한다. 마지막으로 WB단계에서도 필요한 경우 레지스터에 값을 저장시키는 명령을 수행한다.

결과적으로, 우리는 시뮬레이터를 구현하여 한 번에 처리할 수 있는 instruction의 수를 늘려 instruction들을 동시에 실행시킴으로써 하드웨어 활용도를 극대화시킬 수 있다.

2. Project Goals

이번 프로젝트에서도 다음 기능들이 가능하도록 Architecture를 구축하는 것을 목표로 한다.

⦁ Arithmetic: add, sub, addi, slt ..

⦁ Memory references: lw, sw ..

⦁ Branches: jump, beq ..

또한, pipeline으로 구현하는 경우 발생하는 hazard에 대해 알아보며 이를 해결 하는 방법에 대해 자세히 알아보고 이를 토대로 구현하는 것을 목표로 한다. 뿐만 아니라, branch prediction이라는 분기예측을 통해 기존의 pipeline보다도 더욱 clock cycle을 줄일 수 있는 방법에 대해 고안하여 구현하는 것도 이번 프로젝트의 목표이다.

3. Concepts used in CPU simulation

A. Pipeline Hazard

Pipeline을 하는 이유는 multi cycle을 기반으로 instruction들이 동시에 명령을 수행하도록 하여 전체적으로 single cycle보다 처리 시간을 줄이고자 하는 것이 목적이다. 하지만 모든 기술 구현에는 trade-off가 존재하듯, Pipeline을 구현하는데 있어서도 처리시간을 줄이는 장점을 가져올 수 있긴 하지만 이에 따른 문제가 발생한다. 이를 Hazard라고 한다.

hazard란 다음 Instruction이 다음 clock cycle에서 정상적으로 수행되지 못하는 것을 나타낸다. 보통 Instruction과 Cycle간의 비율을 CPI( Cycle Per Instruction)이라고 하고, 이상적인 Pipeline은 바로 한 개의 Instruction이 처리되는데 걸리는 Cycle이 1인 구조를 취한다. 하지만 위와 같이 hazard가 발생해버리면 CPI가 1보다 높아지는 경우가 발생할 수도 있는 것이고, 심각한 경우에는 원치 않는 답까지 얻게 될 수도 있는 것이다.

hazard의 종류에는 크게 3가지가 있다.

⦁ Structural Hazarden

⦁ Data Hazard

⦁ Control Hazard

◎ Structural Hazard는 말 그대로 pipeline 구조로 인한 문제이다.

◎ Data Hazard는 Data에 대한 Read/Write Sequence가 엇갈리면서 발생하는 문제이다. 즉, 현재 instruction의 결과가 이전 instruction들의 결과에 dependent 하기 때문에 발생하는 문제인 것이다. 이에 따른 경우 3가지를 들 수 있다.

① Read After Write(RAW)  ② Write After Write(WAW)  ③ Write After Read(WAR)

따라서 위 3가지의 문제가 발생할 경우 일종의 결과가 지나갈 길을 만들자는 뜻에서 Forwarding (bypassing)을 사용하여 올바른 값을 넘겨주어 문제를 해결 할 수 있다.

◎ Control Hazard는 보통 Fetch단계에서 pc의 값에 4를 더해주어 다음 instruction이 오게 하지만 예외적으로 Jump나 Branch instruction이 들어올 경우 다음 instruction의 pc값은 이전 instruction의 pc값에 4를 더해준 값이 아닌 다른 pc의 값으로 들어가게 된다. 하지만 각 단계의 역할에 따라 빠르면 Decode 늦으면 Execution 단계에서 다음 pc의 값을 알 수 있게 된다. 따라서 Fetch 단계로 instruction이 잘못 들어와 최종 연산에 문제가 생기는 현상을 Control Hazard라 한다. 따라서 이를 해결하기 위해 잘못 들어온 instruction을 없애주는 stall을 사용하여 문제를 해결할 수 있다. 하지만 계속해서 stall을 사용하여 control hazard를 해결할 경우 많은 cycle낭비가 될 수 있다.

따라서 branch prediction이라는 분기예측을 통해 조금의 cycle낭비를 줄이는 것이다.

B. Branch prediction

Branch prediction이란 다음 실행될 조건문이 어떤 곳으로 분기할 것인지를 확실히 알게 되기 전에 미리 추측하는 CPU 기술이다. 만약 파이프라인이 조건 값의 계산이 끝날 때까지 대기한다면, 이전 명령어가 전체 파이프라인을 통과할 때까지 다음 명령어는 파이프라인에서 수행되지 못하고 대기하게 될 것이다. Branch prediction은 이런 낭비를 막기 위해 단순한 알고리즘에 따라 다음 명령을 미리 추론한 후 미리 실행시킨다. 만약 분기 예측기의 예측이 맞으면 파이프라인은 낭비 없이 계속 수행되며, 예측이 틀릴 경우 미리 실행되던 명령이 stall되고 올바른 명령이 다시 실행된다.

그런데 사실 이 예측에도 한계가 존재한다. pipeline의 특성상 multi cycle형식으로 구성되어 있어서 여러 instruction을 동시에 실행시키게끔 되어 있다. 하지만 앞에서 예측이 잘못되었을 때에는 stall을 사용하여 해결하면 된다고 언급하였지만 instruction의 수가 커지게 되면 이런 penalty로 인한 손실이 굉장히 커질 것이다. 따라서 여기서 고민하는 것은 instruction을 늘리면서도 어떻게 하면 penalty로 인한 손실을 줄일 수 있느냐는 것이다. 지금 발생하는 mispredict를 빠르게 판단하고 그에 맞는 대처 방안을 줄 수 있으면 그만큼 penalty를 줄일 수 있지 않는가 하는 접근 방식은 다음과 같다.

Branch Prediction의 static prediction 수행방식은 Always-Not-Taken이나 Always-Taken을 수행하되, 만약 mispredict가 일어나면 해당 instruction을 flush 시키고 다시 retry하는 구조로 되어 있다. 하지만 Prediction의 결과물이 20개의 instruction으로 이뤄져 있는데 마지막에 Prediction이 잘못 되었다는 것이 판별되면 20개의 instruction이 모두 waste되는 비효율적인 결과를 낳는 것이다. 따라서 runtime 내에 mispredict가 일어나면 유동적으로 수행 절차를 바꿀 수 있는 방식이 Dynamic Prediction 방식이다. 그래서 보통 이걸 수행하기 위해서는 Branch Target Buffer가 구조 내에 포함된다.

먼저 static scheme중 하나인 always not-taken의 경우에는 다음과 같다

1. Always not-taken

단순히 들어오는 branch instruction들에 대해 모두 거짓이라 가정하고 nextPC= PC + 4로 계산하는 방법이다. 하지만 이 경우 branch가 참인 경우 모두 틀리기 때문에 정확도가 낮다.

Inst(h)가 branch instruction이라 가정하면 t2때 Execution단계에서 target address가 계산된다. 따라서 t2에서 branch가 참인지 거짓인지 실제로 알게 된다. 참이라는 결과가 나올 경우 t3에서는 MEM단계 앞의 stage들을 모두 flush하고 IF단계에는 올바르게 계산된 instruction이 fetch된다.

2. Branch Target Buffer(BTB)

BTB는 branch가 참인 경우도 예측하기 위해 고안되었다.

처음에 BTB history에는 아무것도 없는 상태이다. 여기서 branch instruction이 들어오는 경우 history에 아무것도 없으므로 예측이 불가능하다. 따라서 target address가 Execution 단계에서 실제로 계산된 후 BTB history에 tag(pc)와 target address가 저장된다.

branch instruction이 history에 update된 후 같은 PC의 branch instruction이 들어오면 update된 결과 값에 따라서 예측을 하게 된다. 예측이 계속 맞다가 어느 순간 틀리게 되면 틀린 경우에만 그 branch instruction에 대해 tag과 target address을 BTB history에 다시 update한다.(last state)

이때, non-branch instruction이 들어올 경우에는 항상 다음 pc는 pc+4가 저장된다.

Dynamic Prediction 방식은 다음과 같이 나타낼 수 있다.

①                                                              ②

for문이나 while문을 생각해보면 loop를 계속 돌다가 어느 순간 탈출하게 된다. 계속 도는 경우에는 조건문의 방향이 정해지게 된다. 따라서 이전 branch의 결과를 저장하는 table을 작성하여 방향성을 알 수 있다.

3. Gshare branch predictor

Gshare란 BTB에서 BHSR(Branch Histroy Shift Register)를 추가한 version이다. branch들의 taken(1), not-taken(0)들을 BHSR에 기록한다. Shift register이기 때문에 이전 결과 값들이 왼쪽으로 한 칸씩 밀려 저장된다.

이때, taken과 not-taken의 패턴을 저장해주는 pattern table을 추가로 만들어 저장을 해주어 구현할 수 있다. 위 그림과 같이 Global branch history와 pc를 xor을 취해 해당 값을 pattern table의 index역할을 해주어 패턴을 뽑아내며, BTB에 현재의 Branch가 들어있는지를 판단하여 target address를 정한다. 최종적으로 taken하며 BTB에 target address가 들어 있을 경우 pc의 값을 target address로 바꿔주어 분기예측을 실행한다.

깃허브 주소: https://github.com/thdalstn6352/Computer_Architecture/ 참조

1. Project Introduction

이번 프로젝트에서는 MIPS 시뮬레이터를 구현하였다. MIPS 시뮬레이터를 통해 주어진 Binary파일(.bin)을 읽어와 올바른 값을 도출하는 것을 목표로 한다.

MIPS Green Sheet에 의하면 각 instruction은 I, R, J 유형으로 분류되며 32개의 범용 레지스터를 지닌다. 각 유형에 맞추어 instruction을 통해 opcode, rs, rt rd, imm, func, address 등의 값을 뽑아내고 Data Path에 의해 순차적으로 연산을 시작한다. 연산은 pc값에 의해 시작되게 되는데, 초기 pc는 0x0으로 시작하며 매 instruction을 수행할 때마다 + 4가 더해지게 된다. 단, Jump나 Conditional Jump인 Branch 연산의 경우 pc값은 정해진 규칙에 의해 변한다. 즉, 매 사이클을 돌 때마다 Architectural State가 변경될 뿐만 아니라 pc의 값을 변경해주어 최종적으로 pc값이 0xFFFF:FFFF 이 될 경우 종료된다.

각 사이클은 6개의 Phases들에 의해 수행된다. 1. Fetch 2. Decode 3. Evaluate Address 4. Fetch Operands 5. Execute 6. Store Result 순이다. 단, 모든 instruction이 6개의 phases들을 요구하진 않는다.

매 사이클마다 phases를 지나며 pc가 0xFFFF:FFFF가 되어 사이클이 종료될 경우 최종 결과는 Register의 2번에 저장된다.

결과적으로, 우리는 시뮬레이터를 구현하여 bin파일을 불러와 각 instruction을 올바르게 해독하여, 해독 결과에 따라 해당하는 연산과 메모리 접근등을 통해 Architectural State를 변경해주는 것이다.

2. Project Goals

이번 프로젝트는 다음 기능들이 가능하도록 Architecture를 구축하는 것을 목표로 한다.

– Arithmetic: add, sub, addi, slt ..

– Memory references: lw, sw ..

– Branches: jump, beq ..

또한, Single Cycle이 작동하는 방식과 Single Cycle과 Multi Cycle의 차이점을 파악하고, Data Path를 기반으로 하며 MIPS Green Sheet를 활용하여 체계적으로 코드를 구현해 주어진 bin파일을 실행시켜 올바른 Architectural State를 도출한다. 이를 통해 MIPS-32ISA 구조를 이해하며 cycle의 수와 시간이 cpu에 미치는 영향에 대해 알 수 있다.

3. Concepts used in CPU simulation

A. ISA(Instruction Set Architecture) - MIPS 정리

(1) ISA란?

앞선 보고서에도 언급하였지만 ISA란 하드웨어와 사용자가 어떻게 지시하고 명령을 수행을 할 것인지에 대한 규약이다. 이때, 명령어의 수행 내용, 시스템의 형태, 명령어에 따라 시스템 상태의 변화 등을 정의하게 된다.

뿐만 아니라 레지스터의 수와 상태, 명령어의 형식과 내용, 메모리 모델과 Input/Output등 많은 것들에 대한 규약이 있다. 이 규약은 하나로 정해져 있는 것이 아니라 CPU에 따라 다른 여러 규약이 존재한다.

(2) MIPS-32 ISA

MIPS(Microprocessor without Interlocked Pipeline Stages)는 밉스 테크놀로지에서 개발한 RISC ISA로 초소형 마이크로 컨트롤러에서부터 고급 네트워킹 장비에 이르는 수십억 가지 전자 제품의 핵심 부분인 고성능의 업계 표준 아키텍처이다. 탄탄한 instruction과 32 비트에서 64 비트까지의 확장성, 광범위한 소프트웨어 개발 도구 등 사용자에게 폭 넓은 지원을 제공한다.

각 명령은 4-byte word 크기의 2진수로 표현되어 있고, 이들은 각각 하나의 연산을 수행한다.

-MIPS-32 ISA의 명령어 형식은 아래와 같이 나눌 수 있다.

◎ R-type

◎ I-type

◎ J-type

B. Endian

컴퓨터의 메모리와 같은 1차원의 공간에 여러 개의 연속된 대상을 배열하는 방법을 뜻한다. Endian은 큰 단위가 앞에 나오는 빅 엔디언(Big-endian)과 작은 단위가 앞에 나오는 리틀 엔디언(Little-endian)으로 나눌 수 있다.

두 방법은 서로 다른 여러 아키텍처에서 서로 공존하고 있다. 그러나 x86 아키텍처가 리틀 엔디언을 쓰기 때문에, 오늘날 x86 아키텍처를 사용하는 대부분의 데스크톱 컴퓨터는 리틀 엔디언을 쓰며 이를 ‘인텔 포맷’이라 한다. 이번 프로젝트에서 리틀 엔디언으로 표현된 instruction을 빅 엔디언으로 바꾸는 연산을 수행하였다.

c. Data Path

= 연산들을 수행하기 위한 여려 유닛들의 구조로 MIPS연산은 크게 5개로 나눌 수 있다.

(1) Instruction Fetch(IF) : PC에 있는 명령어(instruction)을 가져온다.

(2) Instruction decode and register operand fetch (ID/RF) : 명령어를 해석하고 필요한 레지스터 값을 읽는다.

(3) Execute/Evaluate memory address (EX/AG) :　명령에 필요한 연산을 수행하고 필요할 경우 메모리 주소를 계산한다.

(4) Memory operand fetch (MEM) : 메모리 주소를 가져와 값을 저장하거나 읽어오는 연산을 수행한다.

(5) Store/writeback result (WB) : 필요한 경우 최종 연산 결과를 레지스터에 저장한다.

(a) R_Type Data_Path

(1) Instruction Fetch(IF) : PC에 있는 명령어(instruction)을 가져온다.

(2) Instruction decode and register operand fetch (ID/RF) : 명령어를 해석하고 rs와 rt 레지스터 값을 읽는다.

(3) Execute/Evaluate memory address (EX/AG) :　rs와 rt를 이용하여 올바른 연산을 수행한다.

(4) Memory operand fetch (MEM) : 데이터 메모리에 접근하지 않는다.

(5) Store/writeback result (WB) : 연산의 결과를 레지스터 rd에 작성한다.

(b) LW Data_Path

(1) Instruction Fetch(IF) : PC에 있는 명령어(instruction)을 가져온다.

(2) Instruction decode and register operand fetch (ID/RF) : 명령어를 해석하고 rs레지스터 값을 읽고 16비트의 imm을 32비트로 바꾸어주는 SignExtimm연산을 수행한다.

(3) Execute/Evaluate memory address (EX/AG) :　rs와 Extimm을 이용하여 덧셈 연산을 수행한다.

(4) Memory operand fetch (MEM) : 연산 결과를 메모리의 주소로 가져와 해당하는 메모리의 값을 읽어온다.

(5) Store/writeback result (WB) : 연산의 결과를 레지스터 rt에 작성한다.

(C) SW Data_Path

(1) Instruction Fetch(IF) : PC에 있는 명령어(instruction)을 가져온다.

(2) Instruction decode and register operand fetch (ID/RF) : 명령어를 해석하고 rs레지스터 값을 읽고 16비트의 imm을 32비트로 바꾸어주는 SignExtimm연산을 수행한다.

(3) Execute/Evaluate memory address (EX/AG) :　rs와 Extimm을 이용하여 덧셈 연산을 수행한다.

(4) Memory operand fetch (MEM) : 연산 결과를 메모리의 주소로 가져와 해당하는 메모리에 rt의 값을 작성한다.

(5) Store/writeback result (WB) : 결과를 레지스터에 저장하지 않는다.

(D) Branch Data_Path

(1) Instruction Fetch(IF) : PC에 있는 명령어(instruction)을 가져온다.

(2) Instruction decode and register operand fetch (ID/RF) : 명령어를 해석하고 rs와 rt의 레지스터 값을 읽는다.

(3) Execute/Evaluate memory address (EX/AG) :　rs의 값과 rt의 값을 비교하여 beq와 bne의 조건에 만족할 경우 pc값에 4를 더하고 BranchAddress를 더한다.

(4) Memory operand fetch (MEM) : 메모리에 접근하지 않는다.

(5) Store/writeback result (WB) : 결과를 레지스터에 저장하지 않는다.

(E) Jump Data_Path

(1) Instruction Fetch(IF) : PC에 있는 명령어(instruction)을 가져온다.

(2) Instruction decode and register operand fetch (ID/RF) : 명령어를 해석하여 Jump target address을 읽어 pc를 바꾸어준다.

(3) Execute/Evaluate memory address (EX/AG) : 연산을 하지 않는다.

(4) Memory operand fetch (MEM) : 메모리에 접근하지 않는다.

(5) Store/writeback result (WB) : 결과를 레지스터에 저장하지 않는다.

깃허브 주소: https://github.com/thdalstn6352/Computer_Architecture/ 참조