[CS] Addition, Subtraction, Multiplication, Division
1. Integer Addition
1) overflow X
(+ve) + (-ve)
2) overflow O
(+ve) + (+ve) -> sign bit에 1 넘어가서
(-ve) + (-ve) -> sign bit가 0 돼서
*carries: 자리 올림수
*+ve: positive
*-ve: negative
2. Integer Subtraction
second operand가 음수인 덧셈
? + (-ve) -> subtraction
1) overflow X
(+ve) - (+ve)
(-ve) - (-ve)
2) overflow O
(-ve) - (+ve) -> sign bit가 0 돼서
(+ve) - (-ve) -> sign bit에 1 넘어가서
3. Dealing with Overflow
1) MIPS 'addu', 'addui', 'subu' (e.g. C)
overflow 무시
2) MIPS 'add', 'addi', 'sub' (e.g. Ada, Fortran)
exception handler 발생시킴
(1) EPC(Exception program counter) 레지스터에 예외가 발생한 PC 값 저장
(2) 미리 정의된 Handler 주소로 Jump
(3) exception 해결하고
(4) mfc0(move from coprocessor register) 명령어가 EPC 값 추출
(5) 원래 PC로 컴백
*coprocessor(코프로세서): CPU와 함께 동작하는 보조 프로세서
*coprocessor 0 (CP0): 예외처리, 인터럽트 처리, 메모리 관리 등 담당
4. Arithmetic for Multimedia
1) 멀티미디어 데이터를 8비트 또는 16비트로 나누어 처리
- 64비트 adder + partitioned carry chain
*partitioned carry chain: carry chain을 여러 부분으로 나누어 병렬 처리
= SIMD (single instruction multiple data)
= 하나의 명령어로 여러 개의 8비트 or 16 비트 병렬 처리
= 대용량 데이터를 위한 병렬 처리, 고속 연산
2) Saturating operations
오버플로우, 언더플로우가 발생했을 때 값을 표현 가능 범위의 최대값, 최소값으로 설정
e.g., 표현 가능 범위 = -128 ~ 127 이라면
100 + 50 = 127
- '2s-complement modulo(순환) arithmetic'와 비슷
2의 보수 시스템에서 오버플로우, 언더플로우 발생했을 때 값이 순환하는 것
e.g.,
+127 (01111111) + 1 (00000001) -> 오버플로우
= 10000000 (-128)
-128 (10000000) - 1 (00000001) -> 언더플로우
= 01111111 (127)
e.g.,
(1) Clipping in Audio: 오디오 신호의 진폭 범위 존재. 최대값 넘어서면 신호의 상한 잘려나감.
(2) Saturation in Video: 픽셀 값 허용 범위 존재. 넘어서면 제한.
5. Multiplication
1) long-multiplication (기본적 수학 곱셈 방식)
multiplicand = 피승수
multiplier = 승수
product = 결과
-> 곱셉은 multiplier 길이만큼 더해야하는 연산이라 add 연산에 비해 매우매우매우매우!!! 비싸다.
2) product 길이 < operand 길이 합
e.g., 32비트 정수 2개 곱하면 결과는 최대 64 비트
3) Multiplication Hardware
(0) product register 0으로 초기화
(1) multiplicand register와 multiplier register에 피승수, 승수 각각 로드
(2) multiplier register 승수의 가장 오른쪽 비트 확인
(3) 1이면 product 값에 multiplicand 값 ALU로 더하고 -> product register 업데이트 (0이면 가만히)
(4) multiplicand reg shift left 1비트
(5) multiplier reg shift right 1 비트 (1비트 버림)
(6) 32번 반복
** multiplicand register 64비트 (shift lef 32번 해야하니까)
** 64비트 ALU: 두 개의 64비트 입력 받아 64비트 결과 출력
4) Optimized Multiplier
add/shift를 동시에
부분곱 덧셈
곱셈 빈도가 낮다면 ㄱㅊ
(0) multiplier를 product register 오른쪽 절반에 로드
(1) product reg의 가장 오른쪽 비트 확인
(2) 1이면 product 왼쪽 32비트 값에 Multiplicand 값 더해서 -> product register 왼쪽 32비트 업데이트 (0이면 가만히)
(3) product reg shift right (multiplier 1비트 버리고, multiplicand shift left 1 비트 한 효과)
**multiplicand register 32비트
**32비트 ALU
**multiplier register 사라짐
5) Faster Multiplier
32비트 덧셈기를 31번 사용하는 게 아니라
32비트 덧셈기 31개를 사용하자.
-> cost/performance tradeoff
-> 곱셈 병렬 처리 (pipeline)
-> log(32) = 5번의 덧셈시간만 기다리면 됨
6) MIPS Multiplication
2개의 32비트 레지스터
(1) HI
(2) LO
A. 곱셈 명령어
(1) mult rs, rt
결과는 64비트
상위 32비트는 HI에 하위 32비트는 LO에 저장
(2) multu rs, rt
부호 없는 정수 곱셈
결과는 64비트
상위 32비트는 HI에 하위 32비트는 LO에 저장
B. 결과 처리 명령어
(1) mflo rd
LO 레지스터 값을 rd 레지스터로 이동
(2) mfhi rd
HI 레지스터 값을 rd 레지스터로 이동
C. 곱셈 + 결과 처리 명령
(1) mul rd, rs, rt
rs, rt 곱해서 하위 32비트를 rd에 저장 (상위 32비트는 무시)
기본 MIPS 명령어 세트에는 포함되있지 않을수도. 고급 세트에 있음
6. Division
quotient: 몫
dividend: 피제수
divisor: 제수
remainder: 나머지
** 나눗셈 수행 전 반드시 devisor가 0인지 확인
-> 0으로 나누면 오류 발생
** n bit operands -> n bit quotient and remainder
1) Long division (수동으로 나눗셈 수행하는 방법)
- divisor <= dividend 라면
quotient 1 + subtract
- 아니라면
quotient 0 + brining down next dividend bit
2) restoring division
무조건 subtraction -> remainder가 음수라면
divisor 다시 더하기 (복원)
3) signed division
(1) 절대값으로 나누기
(2) 결과 부호 결정 (피제수 제수 부호 같 = 양, 부호 다 = 음)
(3) quotient, remainder 부호 적용
4) Division Hardware
(0) divisor register 왼쪽 32비트에 divisor 로드 / remainder register 왼쪽 32비트에 dividend 로드 / quotient 0 초기
(1) Remainder - Divisor -> Remainder reg
(2) remainder 음수인지 / 0 이상인지 체크
(3) 음수라면
- remainder + diversor -> remainder (원래 값으로 회복)
- quotient shift left (0으로 오른쪽 비트 채우기)
(4) 0 이상이라면
- quotient shift left (1로 오른쪽 비트 채우기)
(5) divisor register shift right 1 비트
(6) 33번 반복
**division은 multiplication보다 1번 더 실행
**divisor, remainder 64비트, quotient만 32비트
** 64비트 ALU
5) Optimized Divider
(1) remainder 오른쪽 32비트에 dividend 로드
(2) remainder 왼쪽 32비트 - divisor -> remainder 왼쪽 32비트
(3) remainder 왼쪽 32비트 음수인지 / 0 이상인지 확인
(4) 음수라면
- remainder 왼쪽 32비트 + divisor -> remainder 왼쪽 32비트 (회복)
- remainder shift left (0으로 오른쪽 비트 채우기)
(5) 0 이상이라면
- remainder shift left (1로 오른쪽 비트 채우기)
(6) 33번 반복
remainder가 왼쪽으로만 움직여야되는 거 아닌가...?
이해 안됨 왜 오른쪽으로 가지
** partial remainder subtraction
** multiplier랑 같은 하드웨어 사용가능
6) Faster Division
division은 multiplication과 다르게 병렬처리 불가능 (다음 단계 수행 전 뺄셈한 결과의 부호를 알아야 하기에)
faster dividers (e.g., SRT division) 은 매 단계에서 여러 개의 quotient 비트를 생성한다.
-> 병렬처리 가능 (그럼에도 불구하고 여전히 multiple steps 필요)
7) MIPS Division
결과 저장 위한 2개의 32비트 레지스터
(1) HI: remainder
(2) LO: quotient
A. 나눗셈 명령어
(1) div rs, rt
부호 있는 정수 나눗셈
(2) divu rs, rt
부호 없는 정수 나눗셈
B. 결과 처리 명령어
(1) mflo rd
LO 레지스터 값을 rd 레지스터로 이동
(2) mfhi rd
HI 레지스터 값을 rd 레지스터로 이동