개념
곱셈 과정에서 첫 번째 피연산자는 multiplicand(피승수)라고 부르고, 두 번째 피연산자는 multiplier(승수)라고 부른다.
최종 결과는 product(곱)이라고 부른다.
즉, multiplicand * multiplier = product 라고 할 수 있다.
곱셈 알고리즘에는 두 가지 버전이 있다.
곱셈 하드웨어 1
첫 번째 버전은 Multiplicand 레지스터, ALU, Product 레지스터는 모두 64비트이고, Multiplier 레지스터만 32비트인 경우이다.
Multiplicand와 Multiplier가 n bit이라면 n번 반복하게 되는데, Multiplier의 LSB에 따라 수행하는 작업이 달라진다.
- Multiplier의 최하위 bit을 확인한다.
1-1. LSB = 1 이라면, product = product + multiplier
1-2. LSB = 0 이라면, 연산을 수행하지 않는다.- Multiplicand를 왼쪽으로 1bit씩 이동한다.
- Multiplier을 오른쪽으로 1bit씩 이동한다.
예제
2 X 3을 계산하되, 공간을 절약하기 위해 4비트 수를 이용하여 0010 X 0011로 하자.
따라서 계산 결과는 0000 0110 이다.
곱셈 하드웨어 2
두 번째 버전은 Multiplicand 레지스터, ALU, Multiplier 레지스터는 모두 32비트이고, Product 레지스터만 64비트인 경우이다. 별도의 Multiplier 레지스터가 사라지고, Multiplier을 Product 레지스터의 오른쪽 절반에 넣는다.
Multiplicand와 Multiplier가 n bit이라면 n번 반복하게 되는데, Multiplier의 LSB에 따라 수행하는 작업이 달라진다.
- Multiplier의 최하위 bit을 확인한다.
1-1. LSB = 1 이라면, product = product + multiplier
1-2. LSB = 0 이라면, 연산을 수행하지 않는다.- Product / Multiplicand를 오른쪽으로 1bit씩 이동한다.
이 알고리즘은 Optimized Mulitplier로 연산을 병렬로 수행함으로써 매 반복이 1 clock cycle만 걸리도록 개선되었다.
예제
2 X 3을 계산하되, 공간을 절약하기 위해 4비트 수를 이용하여 0010 X 0011로 하자.
따라서 계산 결과는 0000 0110 이다.
요약
Multiplicand * Multiplier = Product
Mulitplication
- Multiplier의 최하위 bit을 확인한다.
1-1. LSB = 1 이라면, product = product + multiplier
1-2. LSB = 0 이라면, 연산을 수행하지 않는다.- Multiplicand를 왼쪽으로 1bit씩 이동한다.
- Multiplier을 오른쪽으로 1bit씩 이동한다.
Optimized Mulitplier
- Multiplier의 최하위 bit을 확인한다.
1-1. LSB = 1 이라면, product = product + multiplier
1-2. LSB = 0 이라면, 연산을 수행하지 않는다. - Product / Multiplicand를 오른쪽으로 1bit씩 이동한다.
