Locos Holdings, GK’s Blog

Pipelining ID Stage 일반적인 MIPS architecture 의 ID stage 에서는, register file 에의 read/write 동작과 branch decision, 그리고 branch 할 address 혹은 jump 할 address 의 계산과 control signal 을 만들어내는 동작을 하게 된다 . 이를 위 그림과 같은 모습으로 pipelining 하였으며  또한 EX stage 에의 load 를 좀 더 줄이기 위하여 ALU 의 control signal generate 를 ID 0 stage 에서 initiating 하여 ALU source data 와 ALU control signal 을 EX stage 에 돌입하기 전에 모두 준비해 놓을 수 있도록 하였다 .  EX stage 에서 넘어온 동작들은 노란색 글씨로 표시하였다 .  Branch address 의 연산에는 32-bit Kogge-Stone adder 를 사용하였는데 ,  ID 0 stage 에서는 propagate, generate 의 연산과 1, 2 stage 까지를 수행하고 ID 1 stage 에서 나머지 3, 4, 5 stage 와  최종 결과값을 구하도록 하였다 . 아래 그림에 기존 ID stage 에서의 worst-case delay 를 가지는 영역과  이를 pipelining 한 모습을 표시하였다 . Pipelining EX Stage MIPS architecture 의 EX stage 에서는 ALU control signal 의 generate 와  이에 따라 forward 된 data 를 포함하여...

위 그림은 일반적인 5-stage MIPS architecture의 모습이다. 이를 아래 그림과 같이 8-stage로, ID stage와 EX stage를 더 pipelining해서 더 높은 clock rate를 인가할 수 있는 processor를 만들어 보도록 하며 또한 cache memory를 설계하여 성능 향상을 높여 보도록 한다. 검증은 DE2-70 board를 사용하며 task list는 다음과 같다. 1) 8-Stage Pipelined Processor   (1) ID Stage Pipelining   (2) EX Stage Pipelining   (3) Hazard Control   (4) Memory Access Control 2) Cache Memory   (1) Instruction Cache   (2) Data Cache 3) Verification   (1) Sobel Edge Detector   (2) Pheripheral Controllers

Multiplier에 대해선 final posting이 될듯!! 64-bits Kogge-Stone adder를 구현하여 이를 radix-4 Booth encoded 64-bits multiplier에 적용하였다. (KSA를 만들면서 64비트 32비트 각각 스테이지를 하나씩 빼먹고서 며칠동안 완전 헤맸......) 크기는 위와 같다. 졸라 크긴 하다. 다들 수업때 하는 5-stage pipelined MIPS processor 하나 만들면 저만큼 될텐데 -_- output port까지의 delay는 위와 같다. 약 40ns정도에서 연산이 완료됨을 알 수 있다. level 4에서 얻어지는 게 65비트이므로 64-bits KSA에 HA 하나를 연결하여 level 5가 마무리된다. 사실 기대했던 것만큼 많이 delay가 줄진 않았는데 뭐 40ns면 훈훈하지 않나 싶....... 그리고 KSA를 만들 때 현재는 최종적으로 black cell과 gray cell을 따로 module화하여 instance하는 방식으로 structural하게 구현되어 있는데, 코드도 너무 길고 해서 그냥 게이트 레벨로 썼더니 한페이지도 안 넘었다. 근데 그런데 똑같은 로직인데 delay가 90ns에 육박해버렸다 그래서 다시 instance하여 쓰니까 24ns에서 귀결 이건 뭐 왜그런지 모르겠다 게이트레벨로 쓰니깐 신서사이즈를 잘하는지 사이즈는 많이 줄던데 안드로메다행이 되버리니....

왜인지 정확히는 잘 모르겠지만 나는 굉장히 arithmetic unit에 집착하는 편인 것 같다. 사실 processor의 설계 면에서 봤을 때는 arithmetic unit의 algorithm이나 efficiency는 전체 processor의 성능에 그렇게 큰 영향을 미친다고 볼 수 없기 때문에 (뭐 single cycle CPU라면 얘기가 다르겠지만...) 굉장한 뻘짓이긴 하다만 사실 이것만큼 재밌는 분야가 없는 것 같기도... 여하튼, 오늘의 포스팅은 Kogge-Stone adder인데, 요거는 Peter M. Kogge 횽과 Harold S. Stone 횽이 1973년도에  Kogge, P. & Stone, H.  "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations" .  IEEE Transactions on Computers , 1973,  C-22 , 783-791 요기서 제기된 이론이 되겠따. 위는 32-bits Kogge-Stone adder의 구조. 하이튼, 잡설 생략하고 톡까놓고 말해보자면 "가장 빠른 adder로 간주된다." 보통 prefix adder는 세 가지 갈래로 나뉘는데 속도↑ ------------------- 크기↓ KSA          HKA          BKA 요렇게 나뉘고 여기서 hybrid adder라던가 하는 것이 등장한다. Ladner-Fischer adder나 공부할때 많이 참조했던 UCA Oklobdzija 교수님 adder라던가 하는 것도 세부 분류라고 볼 수 있다. (현재 비마관 휴게실인데 에어콘물이 졸라 꼴꼴거려서 불안해하고있다) ...

32-bits Radix-4 booth encoded multiplier를 구현했다. compressor를 사용하여 만들어졌으며 현재는 최종적으로 32-bits Ladner-Fischer adder 2개를 연결하여 연산된다. booth encoding을 하기 전보다 크기는 약 1/6정도 증가하였으며 2's complement bits의 음수 연산이 가능하게 되었다. output port까지의 propagation delay는 49ns 정도이며  원래 구성하였던 multiplier와 차이는 없다. 이를 optimization하기 위해서 일단은 64-bits adder들의 비교 및 삽입이 우선적으로 필요하게 되었으며 compressor를 사용하였을 때 carry가 ripple되는 구간이 현재 4-bits CLA 혹은 32-bits LFA로 구성되어 있으므로 이를 변경해 보는것을 시행하여 보도록 하겠다.

저번에 썼듯이, Multiplier를 booth encoding하지 않아서 음수의 multiplication을 수행하지 못했다. 그래서 radix-4 booth encoding을 (8을 하고싶었으나 +3a 가 안드로메다로...) 했더니 이건뭐 거의 3/2 정도 delay가 더 컸다. 문제는 increment subtract를 위해서 not gate를 통과시킨 후에 +1 을 해주는 데 있어서 레알 +1 을 하니깐 -_- 그래서 그 carry들도 tree에 다 구겨넣었다. 그러니 delay는 1ns정도(_-_) 원래의 multiplier보다 빠르...ㄴ건가? 더할 수들이 반으로 줄었는데 왜! 왜! 왜! (스테이지 수가 똑같자나...._-_) not gate가 또 문제가 되는지도 모르겠다 하이튼 결과값이 제대로 안나올게 뻔하니 오늘은 디버그모드

거창하게 pipelined MIPS proessor라고 써놓았지만 만드는 방법에 대한 얘기는 아니다 이번 학기에 5-stage pipelined MIPS processor를 구성하고 주어지는 app에 대한 ASIP으로 optimization한 적이 있는데 그것에 대한 얘기 일단 현재 만들어진 것의 performance는 다음과 같다. 요건 compilation report total logic elements가 5235개 인것을 확인할 수 있다. 자세한 내용은 일단은 ALU multiplier가 포함된 size이며 multiplier는 booth encoding을 하지 않은(...) tree구조의 multiplier가 사용되었다. 그래서 먼저 booth encoding부터 시작해야겠고, register file에 swap logic이 있기 때문에 그 부분에 사용된 로직이 크다.(딜레이도 크다... 굉장히) 그래서 clock rate는 28.67MHz(period는 35ns)인데, swap logic이 추가되기 전에는 multiplication도 25ns까지 나왔지만 갑자기 부왘 하고 그래서 output port(이거 안뽑아주고 리셋하고 클락만 넣으면  극강 synthesize해버려서 작동을 안한다-_-) 당연히 ALU와, register file에 접근할 때 두 경우를 일단 반으로 뚝 짤라주면 간단하게도 큰 성능향상이 얻어질 수 있을것 같다. 요건 35ns로 simulation한 결과 x = 12의 sum of factorial(∑(n!))이 3179ns에 얻어지며 10개의 수를 bubble sort한 결과(register를 8개만 사용했을 때)가 2907ns에 얻어지는 것을 확인할 수 있다. 일단은 계절*-_-*학기를 마쳐야하지만 요걸 심각하게 pipelining해보는 것이 주...

그리하여 carry look-ahead 라는 logic이 등장하게 되는데, 이것은 전단계에서 발생할 carry를 기다리지 말고 sum을 주구장창 계산하고 있을때  미리 carry를 계산해서 넣어준다는 adder이다. 이는 다음과 같은 연산에 의해 가능해지는데, 로 해당하는 block의 carry out을 얻을 수 있다. 이를 다음 단계의 carry out에 대입하고, 또 하고, 또 하면 다음 그림과 같은 4-bits carry look-ahead block을 만들 수 있다. 한 gate의 delay를 d라고 할 때, 이 4-bits CLA block에서는 처음 p, g를 뽑을 때 1d 그리고 그로부터 Cout을 뽑을 때 2d의 delay가 발생한다. 그렇다면 최종 3d RCA에서는 각 Cout을 발생하는 데 2d의 delay가 발생하므로 4-bits에서는 8d만큼의 delay가 발생한다. 이 CLA block을 사용하여 또한 serial 연결하여 많은 bit 를 가진 수를 연산할 수 있는데, 물론 각 block의 carry는 ripple되는 것과 마찬가지이지만 어쨌거나 RCA보다 빠르긴 빠르다. Carry Select Adder는 전단계에서 carry를 받아서 계산하지 않고 0 혹은 1 두가지 경우를 모두 계산한 뒤 위와 같이 구성한 CLA block에서 연산한 carry에 따라 이를 multiplex하여 결과값을 얻는다. CSLA(걍 CSA라고 쓰면 skip, save 등 다른 adder들과 혼동의 우려가 있다)에서는  CLA adder와 달리 8-bits block을 보통 사용하는데 이는 MUX의 추가에 따른 delay 때문이다. 하여튼간 CSLA를 구성해본 모습은 다음과 같다. 요건 8-bits CLA unit 오호 이렇게 따로따로 32-bits adder를 구현하고 Quartus에서 sy...

Ripple carry adder는 간단히 full adder를 serial 연결하여 구성한다. 그러면 아래와 같은 그림을 얻을 수 있는데, 요렇게 하면 간단히 4-bit add operate를 수행할 수 있다. 그러나... 다음 단계의 FA는 전 단계 FA에서 Cout을 발생시켜서 넘겨줄 때까지 기다린 후에 연산을 수행하기 때문에 delay가 크다. 총 delay t는 각 full adder의 delay를 모두 합친 값이 된다. 따라서 critical path는 모든 FA에서 carry가 발생할 때이며 각 FA의 input에 a|b = 0 이 성립하지 않는 이상 carry out은 carry input(전단계의 carry out)에 의존하므로 기대할 수 있는 delay도 크다. 장점은, 1.작다. 2. 만들기가 쉽다. 3. 작아서 전력소모가 작다. 와 같은 별 매력없는 장점을 가지고 있다. 4-bits 연산이나 8-bits 연산 등 optimization하지 않아도 충분히 빠른 결과를 얻을 수 있을 때 사용될 수 있다. (아니면 상위 module을 미친듯이 pipelining을 하거나......) 후문으로는 이번에 Digital logic 1을 재수강할때 중간고사 대체로 8-bits RCA를 만들었었는데.... 보고서에 full adder를 boolean equation을 K-map도 안그리고 뽑아냈다고 감점을 훈훈하겤ㅋㅋㅋㅋ B+ 맞았는데 조교가 짜증나니까 그냥 넘어가기로 한닼 하이튼간 그리하여.... A. Weinberger횽과 J. L. Smith횽이 1958년에 Carry Lookahead Adder를 발표하게 된닼ㅋㅋ 그럼 다음은 CLA에 대해 쓰겠구나