[컴퓨터구조개론] 4. Integer Arithmetic

Where are we?

 

이 수업에서 다루고 있는 내용은 ISA에서 RTL까지이다. ISA는 딱 하드웨어와 소프트웨어의 인터페이스이며 ISA를 지나면 소프트웨어는 그 밑에 부분을 볼 수 없다. Microarchitecture는 효율적으로 ISA를 implement한다. 캐쉬가 없이도 말이다. Clock speed, cache size, chips개수 등등을 결정해준다. 다만 오직 layout과 organization이 어떻게 구성이 되어있는지는 그 밑에 있는 부분으로부터 알 수 있다. 간단히 말하자면 간단한 정보는 알 수 있지만 그것이 어떻게 디자인 되어있는지는 알 수 없다는 것이다.

 

Introduction

비트는 비트이다. 무슨 소리일까? 말 그대로 비트는 그냥 1아니면 0이다. 하지만 비트는 협약 같은 것이 있다. 예를 들자면 1011은 어떤 값인가. 1011은 1011이다. 하지만 2’s complement notation으로 인코드를 하게 되면 1011은 다른 의미를 갔게 된다. 다시 말해 비트의 의미는 interpretation으로 결정되지 inherent로 결정되지 않는다.

그래서 우리가 정수를 표현하기 위해선 이 interpretation rule을 사용해야한다. 정수를 표한하기 위해서는 2’s complement뿐만 아니라 overflow, negative numbers등 조건들도 완성이 되야한다. 그럼 지금부터 조금씩 알아가도록 하자

 

 

Integer Addition and Subtraction

정수의 addition이 주어지면 먼저 정수를 바이너리로 바꿔서 이진법의 형태로 더하게 된다. 그리고 비트끼리 덧셈을 하게 되면 만약에 캐리가 마지막까지 가면 마지막에는 이를 무시하기 때문에 오버플로우가 생겨버린다.

덧셈경우 오버플로우가 생기는 경우는 양수끼리 더했을 때 또는 음수끼리 더했을 때이다.

 

Integer Subtraction

Circuit은 덧셈과 똑같다. 뺄셈에서 오버플로우가 생기는 경우는 한수가 양수 한수가 뺄셈일 때 일어날 수 있다.

 

 

Adder회로의 디자인이다. 오른쪽에 있는 부분이 ripple-carry adder라고 한다. 각 박스가 하나의 digit합을 연산한다. 이 ripple-carry adder에서 검은색은 data flow를 파랑색은 control flow를 뜻한다.

박스안에는 왼쪽 밑의 회로로 구성되어 있다. A, B각각 1비트이다.

 

Dealing with Overflow

Some language ignore overflow(아마 대부분). Addu, addui, subu같은 instruction은 오버플로우를 무시한다. 그치만 Ada,Fortran같은 옛날 언어는 오버플로우가 일어날 때 exception을 필요로 한다. MIPS에서 add, addi, sub은 exception을 보여준다.

Exception은 context jump initiated by hardware라고 한다. 점프이긴한데 하드웨어가 하는 점프이다. 만약 오버플로우가 일어나면 그 상황의 예외 코드를 보여준다. 더 자세한건 나중에… 이러한 함수를 exception handler라고 한다.

그럼 구체적으로 예외처리가 될 때 어떤 일이 일어나는 가.

-save PC in exception program counter (EPC) register, EPC는 특별한 register이다. 왜 여기다 다음에 수행할 instruction address를 EPC에 저장하는 가? 당연히 exception을 부르고 나서는 에러가 나왔던 부분으로 다시 돌아가야 되기 때문에 그렇다. 그러고 나서는 jump to predefined handler address. 그리고 exception handler는 mfc0(special instruction, move from coprocessor reg)를 실행하게 된다 to ECP 값을 검색하기 위해 to return after corrective action.

Coprocessor는 느린 clock cycle, 느린 속도 때문에 CPU 밖으로 분리된 칩이 coprocessor이다. Exception handler가 이 coprocessor안에 있었다. 물론 요즘에는 기술들이 좋아져서 CPU안에 있다. 그래서 mfc0가 coprocessor안에 있는 EPC에서 예외처리를 불러오고 이를 CPU안의 PC에 이동시킨다.

 

Arithmetic for Multimedia

컴퓨터 미디어 또는 비디오를 처리할 때 아주 많은 픽셀들로 구성이 된다. 각 픽셀은 integer number로 구성된다. 픽셀 표현방법은 대표적으로 RGB(red, green, blue) 값인데 각 값은 8비트이다. 각 비트는 해당 색이 얼마나 진한지 표현하게 된다. 멀티미디어를 처리하는 과정에서 벡터를 많이 사용한다. {R,G,B}이런식으로 말이다.그래서 두 색깔을 합칠때도 있고 그렇다. 그래서 하나의 벡터 합을 구할 때 한번의 덧셈을 하지만 실상은 여러 번의 덧셈을 한꺼번에 하고 있는 것이다. 그래서 요즘 컴퓨터들은 vector instruction set을 지원한다. Mips,AMD,Intel는 64비트 adder를 사용한다. 이는 굉장히 다양하게 사용될 수 있다 64비트 둘을 input으로 사용할 수도 있고 벡터의 경우 8개의 8비트 그리고 또다른 8개의 8비트를 input으로 사용할 수도 있다. 그럼 이는 같은 single cycle에 처리할 수 있다. 이 때 일어나는 carry는 무시해야 한다. 왜냐하면 각 비트는 독립적인 다른 의미의 비트이기 때문이다. 8-8이외에도 4-16, 2-32비트로 나누는 것도 가능하다. Sometime 이러한 벡터 instruction을 SIMD(single instruction, multiple-data)라고 불리기도 한다.

Saturating operations. 우리가 오버플로우가 일어나는 현상에 대해서는 잘 알고 있다. 두 근사 최대값을 더하면 오버플로우로 인해 굉장히 작은 값이 나온다. 이와 같이 아주 밝은 픽셀끼리 더하게 되면 오버플로우 때문에 아주 어두운 픽셀이 나오게된다. 사진 또는 비디오에는 saturating value라는 것이 있다. 밝음의 최대값인데 이 값이 넘어가면 오버플로우는 발생하지 않고 최대 밝기 값으로 남게 된다. 이로 인해서 값이 바뀌어 에러가 났다고 생각 할 수도 있지만 다시 처음으로 돌아가 하얀색이 아예 검은색으로 바뀌는 걸 원하지는 않을 것이다.

 

Integer Multiplication

Multiplication

Multiplicand * multiplier = product. 여기서 multiplicand가 m비트 multiplier가 n비트이면 product는 mn비트가 되어서 굉장히 큰 값이 나오게 된다.

 

박스는 storage를 의미한다, 반바지 모양은 computing(계산하는) unit이다. 동그라미는 control unit이다. 보면 알 수 있듯이 mutiplier는 32비트이고 multiplicand는 64비트이다. Multiplicand가 64비트인 이유는 우리가 multiplicand값을 product에 넣을 때 우리는 먼저 multiplicand를 left shift한다. 그래서 multiplier의 msb는 requires multiplicand to be left shifted by 31 times. 그래서 multiplicand가 64비트까지 커질 수도 있다. Control test는 현재의 비트가 1인지 0인지 판단한다. 1이면 perform addition operation of the multiplicand after shift multiplicand to the one bit.

Left shift operation은 값이 0인지 1인지 상관없이 거쳐간다. 그래서 모든 clock에서 multiplier는 오른쪽으로 shift, multiplicand는 왼쪽으로 shift한다. 그리고 control test에서 값이 1이면 add가 실행이 되어 multiplicand를 product에 더하게 된다. 그래서 product의 결과가 ALU(Arithmetic Logic Unit)에 이어지게 된다. 이 과정을 32번 반복하면 product를 얻게 된다.

그래서 multiplication은 32clocks이 필요하다. 64비트 머신이면 64clocks이 필요하다.

위에서 product는 처음에는 0으로 initialized되어 있다. 그리고 control test가 multiplicand와 multiplier를 가리키는 거는 shift left와right을 실행하기 위해서이다.

(대충 이런식으로 진행된다)

 

Optimized Multiplier

 

이전에는 세개의 레지스터를 사용하였지만 refined된 곱셈은 두개의 레지스터만 있어도 실행할 수 있다. Multiplicand와 product만 있으면 된다. product에는 multiplier를 동시에 저장이 된다. 처음 시작이 되면 product자리의 뒤에 절반은 multiplier값이 할당된다(나머지 절반은 0이다). 그이후의 상황은 비슷하다. Control test에 1이들어오면 ALU가 실행이된다. 여기서 살펴봐야 할 것은 ALU가 위 상황보다 절반비트가 된 것인데. 이 절반비트의 결과가 product의 앞32비트에 저장된다. 그리고 product는 right shift한다. 그럼 product와 multiplier가 동시에 right shift되는 것이다. 이는 multiplicand를 왼쪽 shift한 것과 같은 효과이다. 그래서 원래의 디자인보다 훨씬 간단해진것을 알 수 있다.

근데 이 디자인의 이상한 점은 이 과정을 한 clock cycle에 끝낼 수가 없다. add하고 저장하는데 한 clock, 그리고 shift하는데 한 cycle이 필요하다. 그래서 이 과정을 32두번 반복하면 64이상의 clocks가 필요로 한다. 암다의 법칙에 의해서 만약에 이 multiplication을 적게 사용하면 괜찮겠지만 많이 사용하게 될 경우 오래걸려 새롭게 refined되어야한다.

 

Faster Multiplier

 

이게 새로운 형식의 multiplier인데 각 Mplier*Mcand는 32비트*N(Mcand크기)이고 이 형식을 사용했을 경우 log2 32clocks만에 계산할 수 있다.

또한 pipelining을 사용할 수 있다 여러 개의 곱을 수행해야 할 때 효율적으로 log2 N clocks로 끝낼 수 있다.

 

MIPS Multiplication

HI는 most-significant 32bits, LO는 least-significant 32bits를 의미한다.

Mult rs, rt은 rs와 rt의 곱을 HI/LO에 저장하게 된다.

Mfhi rd/ mflo rd, mfhi는 hi의 값을 일반 레지스터에 저장하고 mflo는 lo의 값을 일반 레지스터에 저장한다. 일반적으로 결과는 lo에 저장하게 된다 다만 오버플로우가 일어나면 hi을 확인해야한다. Multu rs, rt는 unsigned 버전이다.

Mul rd, rs, rt는 수도 instruction이다. 이는 위의 두 instruction을 쉽게 사용할 수 있다.

 

Integer Division

Division

Dividend / divisor = quotient + remainder

 

 

알고리즘이 위 곱셈과 비슷한 것도 있고 간단해서도 하고 왼쪽 알고리즘을 천천히 읽어보면 쉽게 이해할 수 있다고 본다.

 

Optimized divider

 

이것도 곱셈과 비슷하다 두개의 레지스터가 있고 모양도 비슷하다. 대신 두개의 shift가 있다. Dividend는 remainder의 오른쪽에 위치한다. 처음에는 remainder가 shift left한다. 그래서 dividend가 맨오른쪽에 1비트 남는다. 그리고 왼쪽 1비트가 절반을 넘어간다. 그리고 divisor가 들어오는데 만약에 divisor가 remainder의 왼쪽 절반을 뺄수가 없다면 다른 루프를 들고 오른쪽 끝에는 0을 집어 넣는다. 빼는게 가능하면 맨오른쪽에 0이 아니고 1을 집어 넣는다. 이렇게 32번 반복하면 quotient는 remainder의 오른쪽 절반에 저장이 되고 remainder은 왼쪽 절반에 저장이 된다. Right shift는 한번도 안썼는데 왜 있을까? 왜냐면 곱셈이랑 똑같으니까 곱셈때 다시 사용할 수 있게 만들어 놨다고 한다….

Faster Division

곱셈처럼 나눗셈은 parallelized divider는 없다. 근데 좋은 알고리즘은 있는데 그런 알고리즘도 굉장히 느리다.

 

MIPS Division

HI: 32비트 remainder

LO: 32비트 quotient

Div rs, rt/ divu rs, rt   #rs/rt

Use mfhi, mflo to access result

MIPS division은 오버플로우를 체크하지 않는다.

 

(사진은 시험끝나고 올리도록)