3.3 Multiplication

🔑Table of Contents

1. Multiplication        - 곱셈
2. Multiplication Hardware (First version)
3. Optimized Multiplier ( Sequencial version)  - 최적화된 곱셈기
4. Add and Right Shift Multiplier Hardware     - 4bit 수들의 곱
5. Faster Multiplier     
6. MIPS Multiplication
7. 궁금한점

---

📌Multiplication

• Multiplicand 왼쪽으로 시프트, Multiplier 오른쪽으로 시프트됨 -> 64비트 ALU(산술 논리 연산장치)를통해 연산된다
• product의 길이 = Multiplicand와 Multiplier의 길이를 합친 값(32bit * 32bit = 64 bit)
• 곱셈과정
  •  shift와 덧셈
    • Multiplier의 각 비트를 확인해 비트값이 1이면 Multiplicand를 product에 더한다
    • Multiplicand는 shift left, Multiplier는 shift right
    • 이 과정 반복해 모든 비트 검사
  • control test
    • 모든 비트 검사했는지 확인 -> 연산끝나면 결과값인 Product저장

📌 Multiplication Hardware (First version)

 

 

 

1. Test Multiplier0  = 가장 오른쪽 비트가 1인지 0인지 검사

     - 0: 다음단계로 넘어감

2. 1: product에 더해 결과를 저장

3. shift the Mulitiplicand register left 1 bit (곱셈 자리 올림)

4. shift the Mulitiplier register right 1 bit (다음 비트 검사하기 위함)

5. 32번 반복확인 -> 확인되면 알고리즘 완료 

     - 반복 안됐을경우 1단계로 돌아가 Multiplier 가장 오른쪽 비트검사

6. Done = 32번 반복이 완료되면 Product 레지스터에 저장됨

 

 

 

 

 

 

📌 Optimized Multiplier (Sequencail version)

최적화된 곱셈기 (순차적인 버전)

 

*병렬(parallel)로 단계를 수행한다 : add/shift

 

*partial-product에 더할 때마다 하나의 싸이클이 집행

 

📌 Add and Right Shift Multiplier Harware

덧셈과 오른쪽 쉬프트의 반복을 통한 곱셈기

4 bit 두 수를 곱하는 예시

• 처음에 product의 하위 4비트에 multiplier(승수)로 채워진채 시작
• multiplicand (피승수) = 0b0110 (=6)
• product = 0b0000 0101(=5)
  • 처음  0000 0101
  • add(1)   0110 0101
  • shift  0011  0010
  • add(2)  0011  0010  (그대로 내려옴)
  • shift 0001  1001
  • add(3)  0111 1001
  • shift 0011  1100
  • add(4) 0011  1100 (그대로 내려옴)
  • shift  0001  1110  ->결과 30

※ 4-bit 수의 곱셈이라 add/shift가 4단계 일어나면 종료

 

📌 Faster Multiplier

더 빨라진 곱셈기

* 이전에는 4 -bit 수들을 곱하려면 4번의 반복이 필요했음 (32 -bit는 32번의 반복)

* 여러개의 adder을 사용함 (cost/performance 교환)

   → 결과를 빨리 얻을수있음(성능이 높음), 하드웨어를 많이 사용해 비용이 높음)

• pipeline화 가능하다 (chapter 4)
• 각각의 곱 행동을 병렬적(parallel)으로 수행( → 적은 하드웨어 리소스로도 빠른 연산가능)

📌 MIPS Multiplication

• product에 2개의 32-bit 레지스터를 사용 (결과는 64-bit로 저장되기 때문에)
  • HI : most-significant 32 bits 상위 32비트
  • LO : least-significant 32 bits 하위 32비트
• Instructions
  • mult rs, ts    / multu rs, rt (곱셈)
    • HI와 LO로 64 bit의 product를 생산(곱한다)
  • mfhi rd   /  mflo  rd           (곱셈결과를 상위/하위 32비트를 rd에 저장)
    
    • HI/LO 로부터 rd로 move
    • 만약 product가 32 bits보다 커서 오버플로우가 될지 HI의 값을 미리 보려고 할 때에 사용가능하다
  • mul rd, rs, rt
    
    • rs와 rt를 곱하고 결과의 하위 32비트를 rd에 저
    • mult, multu는 64비트결과, mul은 32비트 결과

 

 

 

📍?<궁금한점>📍

🔎개념

• Multiplicand(피승수) : 곱해지는 수
• Multiplier(승수) : 곱하는 수
• Product : 두수를 곱한 결과값