Introduction
해당 글에서는 두 가지 MIPS의 구현에 대해 살펴봅니다:
- A simplified version - Single cycle; 하나의 명령을 하나의 cycle에서 처리하는 방법. *CPI = 1
- A more realistic pipelined version
Multi-cycle version
Instruction Execution
PC는 instruction memory에서 다음에 실행할 instruction의 주소를 fetch합니다. 그 후 PC에 4를 더해 다음 target address를 계산합니다.
Register numbers를 이용해서는 register file에 접근하며, register의 값을 읽습니다.
Instruction class에 따라 ALU가 수행하는 연산이 달라질 수 있습니다:
- 만약 그냥 arithmetic instruction이라면 ALU는 해당 instruction에 맞는 연산을 수행합니다.
- 만약 memory load/store라면 ALU는 offset와 base address의 합을 수행합니다.
- 만약 Branch명령이라면 ALU는 target address를 계산합니다.
따라서 CPU의 구조를 보면 다음과 같습니다:
data path의 흐름에서 어떤 data를 입력으로 할 것인지, 혹은 어떤 명령을 수행할 것인지에 대한 분기점을 제공하는 components를 multiplexer(mux)라고 합니다. 그리고 mux들을 통제하는 control unit으로 CPU가 구성됩니다.
Logic Design Basics
일반적으로 정보들은 binary로 encoded되어있습니다. 이때 0은 low voltage를 1은 high voltage로 나타내며, 하나의 wire에는 오직 하나의 bit만을 전송할 수 있습니다. 즉, 한 번에 여러 개의 bits들을 보내려면 여러 개의 wire를 묶어서 연결해야합니다.
이때 회로의 종류는 크게 두 가지입니다:
- Conditional element (조합회로) (예: ALU)
- 이는 오직 입력 data에 의해 출력이 결정됩니다.
- State (sequential) element (예: register, memory)
- 정보를 저장합니다.
- state(상태)와 입력의 조합에 따라 다음 state를 설정합니다. 즉, 같은 입력이어도 결과가 다를 수 있습니다.
Sequential Elements
Register는 대표적인 sequential element의 예시입니다. register는 clock signal을 사용해 언제 데이터를 update하고 데이터를 저장할지를 결정합니다. 아래의 그림은 positive edge-triggered방식으로 Clk가 0에서 1로 바뀌었을때 데이터를 update합니다:
*Clk가 변하지 않거나, 1->0으로 변할 때는 데이터를 수정하지 않으며, Clk가 0->1일때만 바뀐 입력 D로 Q를 update합니다. 참고로 negative edge-triggered방식은 Clk가 1->0으로 바뀔때 데이터를 update하는 방식입니다.
이때 register의 state로 Clk뿐만 아니라 Write까지 넣을 수도 있습니다. 이는 오직 Write control input이 1일때만 값을 수정하는 것입니다. 즉 register는 Write가 1일때, Clk이 1->0으로 바뀌는 순간 write operation을 수행하는 것입니다.
Clocking Methodologies
clocking methodologies를 통해 state element들을 안정적으로 update할 수 있습니다.
clock cycle동안 combinational logic을 이용해 데이터를 처리하며, state element와 clk를 통해 데이터를 register에 write하거나 read합니다. 위 그림은 일반적인 clocking methodologies 실행 방법을 나타내고 있습니다. 그림에서도 알 수 있듯이, one clock cycle의 길이는 가장 긴 combinational logic의 시간에 의해 결정됩니다. 만약 이 보다 작은 clock cycle을 갖는다면 하나의 combinational logic이 완전히 이뤄지지 않은 상태에서 state element가 실행될 수도 있습니다. *Single cycle에서는 이렇지만 multi-cycle에서는 clock cycle이 작아도 된다.
An ALU (arithmetic logic unit)
ALU에는 다양한 연산들을 지원합니다:
만약 32-bit ALU를 만들고 싶다면, 해당 1-bit ALU부품들을 병렬로 나열하여 구성해야합니다.
Building a 32-bit ALU
이떄 ALU의 Operation MUX는 조건에 따라 사용하는 ALU unit을 선택하는 역할입니다. 예를 들어 Control Unit이 ALU에 1에 해당하는 Operation을 주었다면 해당 ALU는 OR연산을 수행하는 것입니다.
What about subtraction (a-b)?
덧셈 말고 뺄셈은 어떻게 구할 수 있을까요? 이는 2의 보수법을 사용합니다. (a-b)의 경우 b를 negate(보수) 취한 후 1을 더해 -b를 표현합니다. 이를 적용한 ALU는 다음과 같습니다:
따라서 Control unit이 ALU에 Operation은 2를 넣고, Binvert에 1을 넣으면 해당 ALU는 (a-b) 연산을 수행하는 것입니다. 하지만 아직 +1을 하는 부분은 ALU element에 존재하지 않습니다. 마지막에 +1을 하기 위해 가장 위에 있는 혹은 가장 앞에 있는 ALU의 Carry In에 1을 넣고 시작함으로써 구현할 수 있습니다. 이를 통해 b에 negate를 취한후 +1을 해줘 -b를 표현할 수 있는 것입니다.
Tailoring the ALU to the MIPS
MIPS에서 slt나 beq등을 구현하기 위해서는 대소비교가 필요합니다. 그렇다면 ALU를 통해 어떻게 대소비교를 할 수 있을까요? subtraction을 사용하면 됩니다.
slt의 경우 rs < rt인 경우 1을, 아닌 경우 0을 rd에 넣습니다. rs < rt는 (rs - rt) < 0을 의미하며, 이때 1을 return합니다. 즉 (rs - rt)가 음수이면 1을 반환하는 것인데, 이는 (rs - rt)의 sign bit와 동일합니다. 따라서 slt를 위한 ALU는 (rs - rt)를 수행한 후 결과의 sign bit를 return하면 됩니다.
beq의 경우 rs = rt 인 경우와 아닌 경우를 구분해야합니다. 이도 (rs - rt) = 0이면 rs = rt 임을 이용합니다. 따라서 rs - rt의 결과가 0이면 1(참)을 return, 아닌 경우 0(거짓)을 return합니다. 이는 NOR를 사용합니다. NOT(rs - rt) 의 결과를 return하는 것 입니다.
이 모두를 적용하면 다음과 같은 ALU가 만들어집니다:
MSB에 해당하는 ALU는 추가적으로 Overflow를 check합니다. 이는 carry in과 carry out의 값의 차이를 이용하여 detection할 수 있습니다. Less는 slt를 위한 입력으로 MSB ALU의 set output은 최종 subtration 결과의 sign bit를 의미합니다. 이를 32-bit ALU의 전체 그림을 통해 보면 이해가 빠릅니다:
LSB를 제외한 Less input은 0을 넣습니다. 그 후 끝까지 subtraction을 수행한 후 마지막 bit인 sign bit의 값(set)을 LSB의 Less에 넣어줍니다. 만약 Operation이 3이라면, Less의 값이 각 bit의 Result로 나오며, 그 결과는 slt가 true인 경우 100...00을, false인 경우 000...00을 return합니다.
equality의 test를 적용한 32-bit ALU는 다음과 같습니다:
각 bit의 출력 결과를 모두 모아 NOR를 수행하며 zero인지 아닌지를 출력해주는 것 입니다.
*이때 각 operation별로 control line의 입력은 다음과 같습니다.
이 모든걸 적용한 ALU의 모습은 다음과 같습니다:
ALU Extenstion
ALU에서 a에 대해서도 binary invert를 넣어주어 더욱 다양한 ALU기능을 수행할 수 있습니다. ALU 두 개를 이용하여 NOT(A OR B)을 수행하지 않고 (NOT A) AND (NOT B)로 나타낼 수 있습니다(드 모르간의 법칙). 또한 NOT(A AND B)가 아닌 (NOT A) OR (NOT B)를 수행할 수도 있습니다:
ALU Extension을 적용하면 각 operation별 control line은 다음과 같습니다:
Register File
Register File은 다음과 같습니다:
2 read, 1 write file입니다. *참고로 이에 반해 memory는 1 read, 1 write file입니다.
이 register file은 read와 write로 구분하여 자세히 살펴보겠습니다. 먼저 read register입니다:
5-bit register number를 이용하여 MUX를 control합니다. 이를 이용하여 register address에 해당하는 데이터를 읽을 수 있습니다. 그 다음으로는 write register입니다:
먼저 Write control이 1이 아니면 AND 연산에 의해 register write연산이 수행되지 않습니다. Register number는 5-bit 2진수 표현으로 되어있는데 이를 n-bit 값으로 변환하는 decoder가 존재합니다. 만약 00101이 register number로 들어왔다면, decoder에 의해 나온 출력은 n이 32일때, 0000/0000/0000/0000/0000/0000/0001/0000 입니다. Write control과 decoder에 의해 나온 출력으로 각 register의 C값을 결정합니다. C=1이라면 data D를 쓰고, C=0이라면 쓰지 않습니다.
그림을 자세히 보시면 register data는 일단 모든 register에 접근하는 것을 알 수 있습니다. 즉, register에 값을 쓰냐 마냐는 C값에 의해 결정되는 것입니다.
이를 한 번에 그리면 다음과 같습니다:
Building a Datapath
위에 나왔던 ALU와 register file등을 이용하여 MIPS datapath를 구성할 수 있습니다.
Fetching instructions
우선 fetching입니다. clk가 한 번 뛸 때마다 CPU는 fetch -> decode -> execution을 수행해야합니다. 즉 가장 먼저 PC에 해당하는 instruction을 instruction memory에서 꺼내온 후, 바로 PC값에 4를 더해 다음 instruction address를 준비합니다(fetch). 이는 명시적인 write control signal을 필요로 하지 않으며 그냥 clock signal에 의해 PC가 update됩니다. read도 마찬가지로 read control signal을 필요로 하지 않습니다.
Decoding Instructions
Decoding은 control unit을 통해 해당 instruction의 명령 타입을 분석하는 과정을 말합니다. MIPS에서는 opcode와 function field의 값을 control unit에 넘겨주는 과정입니다. 그리고 두 value(rs, rt)를 register file으로부터 일단 데이터를 읽습니다. 이는 MIPS instruction의 특징 때문인데, 우리가 다루고자 하는 MIPS instruction에서는 일단 rs와 rt는 register address와 관련되어있으며 거의 모든 명령에서 rs와 rt에 해당하는 register값은 읽어야합니다. 그래서 명령과 상관없이 일단 읽어 놓는 것입니다. *load의 경우 rt가 memory에 있는 데이터를 저장하는 register address값이기 때문에 read가 아닌 write address이긴 하지만 뭐.. read에도 넣어도 상관없다는 개념. 즉 control unit의 decoding결과 rt의 readed data는 사용하지 않을 수도 있다는 뜻.
Executing R format Operation
R format에 경우 op와 funct field의 값에 의해 수행하는 operation이 달라지고 해당 operation에 따라 rs와 rt값이 operand로 하여 ALU의 input으로 들어가고, 그 결과를 rd에 해당하는 address에 작성합니다.
Excuting Load and Store Operation
Branch Instructions
ALU에서 substraction을 수행한 후 zero output을 활용합니다.
Executing Jump Operations
jump는 그냥 뒤에 28bits를 이용하여 target address를 계산하여 다음 PC값으로 세팅합니다:
Creating a Single Datapath from the Parts
fetch와 decode, execute를 각각의 명령에 대해 오직 하나의 cycle에서 실행하는 Single cycle design에서는 하나의 명령에 한 번 이상의 resource datapath를 가질 수 없습니다. 즉 memory를 instruction 꺼내는 용도로 한 번, memory에 있는 데이터에 접근하는 용으로 한 번, ... 이런식으로 한 번의 cycle에서 여러 번의 resource datapath를 가질 수 없습니다. 따라서 같은 memory안에 있더라도 instruction memory와 data memory를 구분하여 사용하는 것 입니다.
Multiplexor는 input이 되는 elements들이 operation들의 종류에 따라 달라질 수 있기 때문에 이들을 선택하는 역할을 수행하며, write signal의 경우는 Register file과 data memory의 write control을 담당합니다. 그리고 앞서 말했듯, cycle time은 가장 긴 path에 의해 결정됩니다. *일반적으로 load. instruction memory 갔다가, ALU계산을 통해 memory address구하고, data memory에서 data를 가져와, 다시 register로 돌아가 write address에 저장해야하는 매우 긴 path를 갖습니다.
Single Cycle Datapath with Control Unit
이는 MIPS instruction별 용도이며, 아래는 control unit을 포함한 full datapath입니다:
Effect of Control Signals
control signal의 역할들입니다. 이때 중요한건 Write signal과 Read signal은 don't care가 없다는 것입니다. 일부 control signal들의 경우 control signal이 어떤 값이든 결과에 영향을 주지 않을 경우 don't care로 설정하는데, write이나 read의 경우 don't care로 설정해서는 안됩니다. 반드시 데이터를 읽는 경우 read signal을 1로, 안읽는경우 0으로 설정해야합니다. write도 마찬가지입니다.
이때 Control unit의 input과 output을 테이블로 나타내면 다음과 같습니다:
이를 이용해서 control unit을 구현할 수 있습니다:
ALU control
ALU control은 ALUOp0와 ALUOp1, R-format의 경우 function field를 input으로 하여 ALU의 MUX에 줄 control signal을 만들어내는 control unit입니다. 예를 들어 Load/Store의 경우 base reg + offset을 해야하기 때문에 ALU는 addition으로, Branch의 경우 rs - rt = 0 ? 을 확인해야하기 때문에 ALU는 subtraction으로, R-type의 경우는 function filed에 따라 ALU의 type이 변해야합니다. NOR를 구현하지 않는다고 했을때(ALU control의 MSB, 4번째 bit는 상관없음), ALU control의 truth table은 다음과 같습니다:
이를 다시 정리하면 다음과 같습니다:
이를 이용하여 ALU control을 구현하면 다음과 같습니다:
