[Chapter 3.2 컴퓨터 구조 및 설계] 2진수 곱셈, 곱셈 하드웨어

본 정리는 CS422-컴퓨터 구조 및 설계 : 하드웨어/소프트웨어 인터페이스. David A. Patterson, 존 헤네시 책을 바탕으로 하고 있음을 미리 알립니다.

 

2진수 곱셈

---

2진수 곱셈이 어떻게 이루어지는지 보기에 앞서 십진수의 1000 곱하기 1001을 하는 과정을 살펴보자.

Multiplicand를 보통 피승수 (곱셈을 당한다)

Multipler를 승수

최종결과를 곱(Product) 이라고 부른다. 

 

즉, 우리는 0과 1만의 세계에선, 다음과 같은 단계만 거치면 된다.

1. 승수의 자리 수가 1이면 피승수(1X피승수)를 해당 위치에 복사한다.
2. 승수의 자리 수가 0이면 0(0X피승수)을 해당 위치에 복사한다.

 

 

초기의 곱셈 하드웨어

초기의 곱셈 하드웨어

Multiplicand는 64bit로 초기엔 좌측의 32bit가 0으로 초기화 되어있어 원래의 Multiplicand수 그대로를 나타내고 이후 한번 연산이 진행될 때마다 shift left되어 자릿수가 하나 증가된다.

 

Multipler는 shift right하며 lsb를 하나하나 control test에 보낸다.

 

즉, 위의 십진수 곱의 예와 같아진다.

 

처음엔 1000 * 1(1001 중 lsb)을하여 product에 더하고,

다음에 Multipler는 shift right하였으니 0(100 중 lsb) / Multiplicand는 shift left 하였으니 10000 → 10000 * 0 = 0

다음에 Multipler는 shift right하였으니 0(10 중 lsb) / Multiplicand는 shift left 하였으니 100000 → 100000 * 0 = 0

다음에 Multipler는 shift right하였으니 1(1 중 lsb) / Multiplicand는 shift left 하였으니 1000000 → 1000000 * 0 = 1000000

 

즉, 1000000 + 1000을 하면 1001000의 결과를 얻을 수 있게되는 것이다.

 

이를 32번 반복하면, 32bit 이진수의 곱셈 결과를 알 수 있다.

 

초기 곱셉 하드웨어 알고리즘

 

개선된 곱셈 하드웨어

Multipler가 사라졌고, product가 64bit로 바뀌었다.

Multipler는 Product 레지스터의 우측 32bit만큼 자리를 차지하고 있다.

 

이제 우리는 Product 레지스터를 shift right 할 것이다. 

 

똑같이 1000과 1001을 곱한다고 가정해보자 (32bit이므로 앞에 많은 000000bit 들이 있었을 것이다.)

Product는 좌측의 32bit는 0으로 초기화 되어있고, 우측의 32bit는 1001로 초기화 되어있다.

 

이제 Product 전체를 shift right하여 1001의 lsb인 1을 뽑아오고, 그 1과 Multiplicand 1000과 곱해 Product에 더해준다.

이 과정을 32번 반복하는데, Product의 좌측 32bit도 같이 shift right되므로,

마찬가지로 1000+1000000의 결과를 얻을 수 있다.

 

즉, 처음 Product에 곱한 값이 더해질때는 1000(0*32)로 매우 큰 수겠지만, 여기에 shift right한 것에 또 더하고 shift right 한것에 또 더하고 이것을 32번 하면 좌측의 32bit도 결국엔 곱셈을 더한 결과로 채워지게 된다는 것이다.

 

결국, 우리가 십진수 계산하는 것과 같아진다.

 

 

부호있는 곱셈의 경우엔 어떨까?

 

간단하게, 31bit의 곱셈을 해준다음 부호 판별만 해서 부호비트를 붙여주면 된다.

 

 

빠른 곱셈 하드웨어

이는 덧셈기 병렬 트리구조를 만든 것인데, 앞의 하드웨어에선 하나의 덧셈기로 32번 연산을 하였었다.

 

그러나, 이렇게 덧셈기를 32개 사용해 병렬트리 구조를 만들면 log2(32) 즉, 5번의 덧셈 시간만 기다리면 된다.

 

 

MIPS는 64비트 곱을 저장할 수 있는 한 쌍의 32비크 레지스터를 제공한다.

이것은 Hi LO라고 불린다.

 

프로그래머는 32비트 정수 곱을 범용 레지스터로 가져오기 위해 mflo(move flom lo) rd, mfhi(move flom hi) rd 명령어를 사용한다.