[Study] Multi Cycle Implementation

지난 포스트 두개를 통해서 간단한 Single Cycle Implementation을 정리했다. 그런데 정리하다보면서 느낀 건 1cycle상에서 처리하다보니, 특정 instruction 에서는 그 처리 시간이 늦어지는 경우도 있다는 것이다. 가령 lw(load word)와 같은 명령어는 같은 instruction을 수행하는데 있어서 MIPS Architecture에 구현된 대부분의 모듈에 Access한다. 당연히 해당 target 주소를 읽어오기 위해서 Register로부터 Read를 해와야 하며, Memory 에 저장되어 있는 값을 읽어오기 위해 Memory Read도 일어날 것이다. 또한 Target Address를 연산하기 위해서 ALU Operating도 있을 것이고, 구한 값을 다시 Register에 write하는 과정도 포함될 것이다. 아무래도 여러모듈에 동시에 Read/Write를 하다 보면 전체적인 처리시간이 길어지게 된다. 

 그리고 지난 포스트에서도 얼핏 나왔다시피 특정 instruction에서만 사용하는 모듈들이 있었다. 예를 들어 이런 것이다.

동그라미 처져 있는 모듈은 지난 포스트의 Data Flow에서도 언급했다시피 PC를 다른 주소로 바꿔주는 Branch Instruction에서만 쓰이는 모듈이다. 그런데 바로 밑에도 같은 기능을 수행하는 ALU 모듈이 존재한다. 그래서 타이밍만 어떻게 맞추면 Branch Instruction시에 필요한 Add Operation을 ALU에서 처리할 수 있게끔도 바꿀 수 있다는 말이다. 

또한 같은 Physical Memory가 위와 같이 용도에 따라서 나눠져 있다. 이러면 실제 설계시에도 같은 역할을 할 수 있음에도 용도에 따라서 중복으로 만들어줘야 한다는 문제가 발생하는 것이다. 즉 Single Cycle Implementation 자체는 해당 instruction을 한 Cycle내에서 반드시 처리해야 되는 목적으로 인해서 필요한 모듈을 Architecture 상에 집약시켜야 한다는 점이 있다. 경우에 따라선 필요하지 않음에도 그 만일을 위해서 비효율적으로 만든다는 것이다. 

 그래서 나온 개념이 이걸 굳이 1 instruction = 1 cycle 이란 개념에 묶이는 것이 아니라 한 Cycle 내에서도 단계를 나눠서 instruction이 수행될 수 있도록 처리하자는 것이다. 기존 방식에서는 instruction 중 가장 느린 instruction 의 동작시간에 맞춰서 수행되었기 때문에 전체적으로 느렸었는데 이렇게 하면 굳이 필요없는 단계에서는 빼버리고 수행할 수 있기 때문에 조금더 효율적으로 처리할 수 있을 것이다. 결과적으로 Single Cycle에서 놀고 있던 모듈도 효율적으로 동작시킬 수 있을 것이고, 또는 위와 같이 특정 상황에 대비해서 모듈을 만들어놓을 필요가 없어질 것이다. 물론 처리속도도 기존 방식보다 빨라질 수 도 있을 것이다. 이런 접근 방식을 Multi Cycle Implementation 이라고 한다. 이 개념이 설계상에 집약된 것이 처음 포스트에서 설명했던 pipelined Implementation이 될 것이다. 

 강의에서 설명하는데 Multi Cycle Implementation을 설명할 수 있는 가장 큰 특징은 바로 speculative Execution이다. speculative라는 단어 자체가 뭔가를 예측한다는 뜻을 담고 있는데 instruction들을 한 Cycle 상에서 동시에 처리하는 데 있어서는 상황에 따라서 그 결과값을 보장하지 못하는 경우가 발생하기도 한다. 예를 들어 맨 처음 포스트에서 설명했던 pipeline hazard 같은 경우에도 타이밍에 따라서 원치 않는 결과가 나올 수도 있다는 것이다. 하지만 분명 Multi Cycle Implementation의 목적을 계속 살리자면 이러한 hazard를 해결하는 뭔가가 제시되어야 할 것이다. 그렇게 error가 발생할 수 있는 확실하지 않은 상태에서 수행해놓는 동작이 speculative라는 단어로 설명될 것이다. 

 또한 중간중간에 다른 단계에서 이전 정보를 활용할 수 있도록 temporary register가 있는 것도 Single Cycle Implementation과의 차이이다.  그리고 조금전에 언급했던 만약의 상황에 대비해서 설계한 불필요한 모듈을 줄일 수 있다는 점도 차이점이라고 할 수 있다. Multi Cycle Implementation이 적용된 MIPS Architecture는 다음과 같다.

위의 이미지와 보면 차이가 몇가지 나타난다. 간단히 요약해보자면 기존에 Instruction과 Data로 구분되어 있던 Memory가 하나로 통합되어 있으며 다만, 그 구분을 Register에 두고 따로 분리되었다. 또한 Register File상에서 나온 Data를 임시로 저장하기 위한 Temporary Register A,B가 새로 생겼고, 기존에 3개 있던 ALU 모듈도 PC counter ALU와 branch instruction을 위한 ALU가 하나의 ALU로 통합되었다. 이 때 필요성을 느끼겠지만 한 cycle내에서 동시에 여러 instruction이 수행되기 때문에 해당 cycle마다 줘야하는 control Signal의 정의를 확실히 해야 한다.

 그럼 간단히 Data flow에 대해서 살펴보고자 한다. 

먼저 상기해야 될 것은 기존의 Single Cycle Implementation의 Data Flow는 Instruction의 종류, 다르게 말하면 Instruction을 구성하는 Format에 따라서 Flow를 구분했었다. 하지만 Multi Cycle Implementation은 이 모든 것을 몇가지 공통된 요소로 나눠서 구분을 둔다. 그래서 대부분의 instruction을 다음의 5단계 동작에 나눠서 수행한다고 가정한다.

Instruction Fetch (IF)

|

Instruction Decode / Register Fetch (ID)

|

Execution (EXE)

| 

Memory Access (MEM)

|

Memory Write Back (WB)

먼저 instruction Fetch의 Data Flow이다.

Instruction Fetch 단계에서는 다들 알다시피 PC Counter의 값을 증가 시키면서 Instruction을 추출하는 과정을 거친다. 기존의 Single Cycle에서는 따로 PC Counter에 ALU가 따로 있어서 4를 더하는 방식이었지만 여기서는 하나로 통합된 ALU를 통해서 수행한다. 이때 4라는 값은 ALU 전단계에 있는  2bit MUX로부터 나온다. 즉 이 4라는 값을 얻으려면 2bit MUX에 Control Signal이 들어가야 한다는 것을 알 수 있다.

다음은 Instruction Decode 인데 여기서는 Instruction Fetch로부터 얻어온 Data로부터 지난번에 언급한 bit field를 추출하는 작업을 수행한다. 여기서 유심히 봐야 할 것은 I[15:0]의 흐름이다. 분명 지금은 Instruction Decode의 단계이기 때문에 I[15:0] bit field가 사용될 필요가 없다. 왜 하는 것일까? 이유는 Multi Cycle에서의 Branch instruction 수행 과정을 살펴보면 알 수 있다.

이게 Branch instruction 이 수행되는 단계인데 잘 보면 이 instruction을 수행하는데 있어서 필요한 정보가 모두 Instruction Decode 단계에서 나와있다는 것을 알 수 있다. 결론적으로 이 Branch Instruction 자체는 Multi Cycle Implementation 내에서는 3stage만에 결과를 얻을 수 있다는 것이다. 즉 이 단계를 위해서 이전 ID단계에서 미리 imm16에 대한 결과값을 구해놓는 것이다. 사실 branch instruction이 아닌 다른 instruction이 들어올 경우에는 이게 사용되지 않겠지만, 만약에 branch instruction 이 들어온다면 이전 포스트에서 소개했던 Single Cycle에서의 branch instruction보다 효율적으로 처리할 수 있을 것이다. 바로 이런게 앞에서 언급한 Speculative Execution의 scheme이 담겨 있다고 할 수 있을 것이다. 

 자 그럼 다시 거슬러 올라가서 Execution이 일어나는 세번째 단계인데, 이 부분부터 이전에 언급했던 format에 따른 data flow가 차이를 나타낸다. 먼저 R-format일 경우는 Execution이 다음과 같이 수행된다.

분명 이전 단계로 얻은 인자 값들은 Temporary Register에 저장되어 있는 상태이므로 이 값을 ALU로 흐르게 하면 결과 값이 연산될 것이다. 값이 ALUOut이라는 역시 Temporary Register에 저장되어 있으면서 다음 Timing에 Register로 직접 쓰게 하는 것이 Instruction 의 끝이 된다.

Single Cycle Implementation과 차이가 있는 건 Temporary Register가 있어서 결과 값들을 시간이 지나도 Access할 수 있다는 점 정도가 될 듯 하다. 아무튼 Multi Cycle Implementation에서는 Arithmetic instruction은 4단계에서 모두 수행이 완료된 것을 확인할 수 있다. 다음은 I-format을 사용하는 Instruction 중 sw와 lw에 대한 Data flow이다. 잠깐 I-format을 다시 보자면 

과 같고 당연히 immediate value를 처리하는 단계가 필요할 것이다. 그래서 다음과 같이 수행이 된다.

앞에서 언급한 내용을 다시 짚어보자면 이 I[15:0]이 2bit mux를 거치기 때문에 앞의 PC+4와 중복되는 것을 피하기 위해서는 당연히 이 2bit mux에 대한 control signal이 사전에 정의되어야 함을 알 수 있다. 

 이제 Memory Access가 일어나는 단계인데 조금 고민해볼게 있다. load는 말 그대로 위에서 구한 ALUOut을 다시 register에 넣는 것으로 전체 operation이 끝날 것이고 store는 그 결과 값을 Memory에 넣는 것을 끝날 것이다. 그런데 앞에서 말했다시피 이전 Single Cycle 에서는 따로따로 있던 Memory가 하나로 통합되었다는 것이다. 그래서 load냐 store냐에 따라서 앞에서 설명한 단계를 더 수행할 수도 있고 지금 Memory Access에서 끝날 수도 있다는 것이다. 먼저 store를 보자면 그냥 ALUOut을 다시 집어넣는 과정으로 종료가 된다. 

그런데 Load의 경우에는 이 Memory Access를 통해서 Memory에 쓰고 난 후에 Register에 write하는 과정까지 수행해야 한다. 다시 말하자면 Store는 IF-ID-EXE-MEM까지가 끝이고 Load는 IF-ID-EXE-MEM-WB 까지 수행해야 된다는 것이다. 

대략적인 instruction Data Flow를 살펴보았다. 그런데 한가지 안 다룬게 있다. 바로 지난 포스트 마지막에도 언급했던 Unconditional Branch인 jump관련 instruction이다. branch 자체는 ALU를 거친 결과를 비교해서 그 조건에 따라 PC값이 바뀌는 게 목적이었지만 jmp같은 경우는 이유를 따지지 않고 무조건 PC값을 변화시키기 때문에 ALU를 거칠 필요가 없다, 그 때 언급하지 않았던 J-format도 잠깐 언급하면 다음과 같다.

그냥 Opcode를 제외한 나머지 field를 주소 연산에 사용하겠다는 것이다. 역시 이 instruction도 branch와 마찬가지로 3단계에서 operation이 종료된다.

Decode가 된 후에는 이미 jump라는 것을 알았으므로 I[25:0]에 대한 것과 opcode의 concaternate시킨 결과를 활용해서 이동할 address를 구한다. 이때 I[25:0]는 26bit이므로 전체 address 단위인 32bit에 맞춰주기 위해서 shift left 2 단계를 거치게끔 해야 된다. 

아무튼 이런식으로 instruction을 수행하다 보면 기존의 Single Cycle Implementation보다 control signal을 세밀하게 구성해야 된다는 것을 알 수 있다. 그때는 opcode만을 분석해도 해당 모듈에 대한 control signal을 결정지을 수 있었지만 이제는 다음의 state를 미리 고려하면서 조절해줘야 한다는 것이다. control Signal까지 포함시키면 다음과 같이 Implementation 시킬 수 있다.

여기까지 진행하면 이제 지금 stage가 무슨 state인지를 tracking하는 과정이 필요하다는 것을 알게 된다. 어차피 이 state 자체가 위와 같이 IF/ID/EXE/MEM/WB로 finite하게 나눠져 있으므로 이 state가 타이밍에 따라서 어떤식으로 변화하는지를 예측하면 얼마든지 control Signal Generator를 만들 수 있을 것이다. 그걸로 쓸 수 있는 개념이 Finite State Machine이다. 이 FSM에 영향을 주는 변수를 뭘로 고려하느냐에 따라서 Mealy machine이냐 Moore Machine이냐를 구분할 수 있는데 우리는 현재 다음 state를 따지는 데 있어서 단순히 현재 state만 보면 알수 있게끔 되어 있다. 

이게 Moore Machine의 정의이며 다음 state를 고려하는데 있어서 현재 state만을 따지는 것이 된다. 이걸 그대로 control Signal에 투영시키면 다음과 같이 구현될 수 있다.

위의 FSM Diagram을 살펴보면 해당 state때에 어떤 Control signal을 Enable하고 Disable해야 할지를 잘 설명하고 있다. 이걸 그대로 Programmable Logic Array위에 구현하면 그게 바로 논리 회로로 구현한 Control Signal Generator가 될 것이다.

 아무튼 대략적인 Multi Cycle Implementation에서의 Data Flow를 정리해봤다. 1cycle=1instruction의 개념에서 벗어나 한 cycle안에 놀고 있는 다른 모듈을 활용하면서 단계로 나누고 처리한다는 개념 자체는 개별적인 처리시간은 동일하면서 내부 로직을 통해서 전체 처리시간을 줄인 효율적인 방안이 바로 Multi Cycle Implementation이고, 이제 이 개념이 나오면서 Cycle과 instruction의 상관관계를 시스템의 performance를 측정하는데 사용하게 되었다. 그밖에도 speculation이라는 개념에 따라 미리 수행하는 operation이 생겨났기 때문에 이에 따른 control Signal 제어가 조금 복잡해졌으며, 이는 Moore FSM을 적용하면 쉽게 Generator를 만들 수 있다는 것까지 정리한다.