Suhwanc

본 내용은 컴퓨터 아키텍처 - 컴퓨터 구조 및 동작 원리 책(한빛아카데미) 바탕으로 정리하였습니다.

 

 

Index

  • 1. 디지털 논리회로
  • 2. 연산장치의 개요
  • 3. 정수의 덧셈, 곱셈
  • 4. 정수의 나눗셈

 

1. 디지털 논리회로

 

컴퓨터는 전기적 신호를 사용하여 모든 데이터를 0과 1의 조합으로 표현하고 처리한다. 이때 0과 1로 표현되는 2진 데이터는 논리 게이트(logic gate)라는 디지털 논리회로로 처리된다.

 

이번에는 컴퓨터 설계 과정에서 많이 사용되는 디지털 논리회로를 맛만 보겠다.

진짜 맛만 볼게..

 

1.1 논리 게이트

 

첫 번째로 논리 게이트는 논리회로의 기본 하드웨어 소자이다.

기본 연산으로 AND, OR, NOT, XOR 등이 있으며 이들은 0 또는 1의 값을 리턴한다.

위 연산에 대한 설명은 기본적인 내용이므로 생략하겠다.

 

1.2 조합 회로와 순차 회로

 

디지털 논리회로는 조합 논리회로(combinational)와 순차 논리회로(sequential)로 분류된다.

조합 논리회로는 현재의 입력에 의해서만 출력이 결정되고, 기억소자(memory)를 포함하지 않는 반면,

순차 논리회로는 기억소자를 포함하기 때문에 현재의 입력뿐만 아니라 내부 상태에 의해서도 출력이 결정된다.

 

조합 논리회로는 기본적인 논리 게이트의 조합으로 구성되며, 대표적으로 가산기(adder), 비교기, 디코다와 인코더, 멀티플렉서(MUX)와 디멀티플렉서 등이 있다.

 

순차 논리회로는 플립플롭(flipflop)과 같은 기억소자와 조합 논리회로로 구성되고, 클록(clock)의 사용 여부에 따라 동기식과 비동기식으로 구별된다.

 

동기식은 클록이 1이 될때 입력값을 반영하는 방식이고, 비동기식은 클록과 관계없이 입력값이 변하면 알아서 반영된다.

 

1.3 디코더와 인코더

 

디코더(decoder)

해독기라고도 하는 디코더는 출력 단자 중 단 하나만 1이고 나머지는 0을 출력하는 장치이다. 예를 들어 출력 단자가 3개라 하면 경우의 수는 001, 010, 100 이 3개가 전부인 셈이다.

디코더는 입력 신호를 감지한 후 입력 신호의 패턴에 대응하는 출력 단자를 활성화하는 방식이며, 일반적으로 입력 단자가 n개이면 출력 단자는 2^n 개를 가진다. 이는 입력 단자 수에 대한 가능한 모든 경우의 조합을 갖춘 개수이다.

 

인코더(encoder)

인코더는 디코더와 반대되는 동작을 수행하는 장치로, 입력 단자가 다수이지만 단 하나의 입력 단자만 1이고

출력 단자는 입력 단자에 대응하는 코드를 출력한다. 따라서 입력 단자가 2^n개, 출력단자가 n개다.

 

1.4 멀티플렉서와 디멀티플렉서

 

멀티플렉서(MUX)

다중화기라고도 불리는 멀티플렉서는 다수의 입력 단자 중 조건에 맞는 하나를 선택하여 단일 출력 단자로 연결하는 조합 회로이다. 많은 입력 값 중 하나만 선택하므로, 데이터 선택기라고도 한다.

 

디멀티플렉서(DEMUX)

멀티플렉서와 반대로, 디멀티플렉서는 하나의 입력 단자를 다수의 출력 단자로 연결하는 조합 회로이다.

이는 n개 입력이 2^n개 출력으로 변하는 디코더와 이름도 비슷하고, 속성도 비슷하다.

 

1.5 반가산기와 전가산기

 

반가산기(half adder)

반가산기는 1비트 단위의 덧셈을 수행하는 장치로, 만약 A, B 비트가 들어갔다면 결괏값으로 s(sum), carry(올림수)를 출력하는 장치이다.

 

전가산기(full adder)

전가산기는 하위 비트에서 발생하는 올림수를 포함하여 덧셈 연산을 수행하는 조합 논리회로이다.

하위 비트에 의한 올림수를 포함하므로 확장 시 2비트 이상의 가산기를 설계할 수 있다.

 

 

 

2. 연산장치의 개요

기본적으로 CPU는 제어장치와 연산장치로 구성되며, 추가로 레지스터 파일과 CPU 버스를 포함하고 있다.

연산장치는 산술 논리 연산장치(ALU)를 줄인 말로 실행 장치라고도 하며, 기본적으로 덧셈, 뺄셈 같은 산술 연산과
AND, OR 같은 논리 연산, 시프터(shifter), 보수기(complenenter) 등을 포함한다.

 

2.1 연산장치와 레지스터 파일

 

그림은 picoMIPS 아키텍처에서의 연산장치와 레지스터 파일을 보여준다.

위 그림을 자세히 보면, 범용 레지스터 파일에 들어오는 A0, A1, A2는 주소 단자이고, D0, D1, D2는 입력 데이터로 16bit로 구성되어있다.

 

2.2 산술 장치와 논리 장치의 통합

프로세서가 산술 연산과 논리 연산을 위한 명령어를 제공하면 이를 위한 하드웨어를 지원해야 한다.

위 그림은 ALU 내부에 있는 산술 장치와 논리 장치가 통합된 구조를 보여준다.

우선, 16비트로 구성된 입력 데이터가 산술 장치, 논리 장치 각각에 입력되고, 올림수는 산술 장치에만 해당된다.

또한 제어 신호는 총 3비트로 구성되며 2비트는 각 장치의 연산 종류를, 1비트는 MUX에서 어떤 것을 출력할지를 결정하는 역할을 한다.

 

2.3 플래그 레지스터

Flag register는 CPU 내 연산 과정 중에 발생한 상태 데이터들을 저장하는 역할을 한다.

대표적으로 올림수(C), 오버플로우(V), 부호(S), 0 값(Z)이 있고, 프로그램 제어를 위해 사용된다.

ex) 분기 명령어(Z)

 

3. 정수의 덧셈, 곱셈

 

3.1 덧셈 연산

 

2의 보수에 대한 덧셈 연산은 10진수 덧셈처럼 오른쪽에서 왼쪽으로 한 자리씩 더하면서 올림수가 발생할 경우 올림수도 함께 더하면 된다.

-3+1=-2

하지만, 여기서 중요한 건 오버플로우이다. 표현할 수 있는 비트는 한정적이기 때문에 오버플로우가 발생할 경우 결괏값이 다르게 나올 수 있기 때문이다. 다음 상황을 보자.

이런 경우, -9를 표현할 방법이 없어서, carry bit이 발생하면 버리게 되는데, 그 결과로 0111(7)이 돼버린다.

 

 

3.2 덧셈 뺄셈 장치

4 bit 정수의 덧셈, 뺄셈 장치

위 그림은 4개의 전가산기(FA)를 직렬로 연결한 4비트 정수의 덧셈, 뺄셈 장치이다.

뺄셈의 경우, 우측 상단의 s를 1로 보내면, 모든 y가 2의 보수처리가 되는데, 이를 이용해 뺄셈을 구현한다.

 

3.3 곱셈 연산

 

이진수의 곱셈 연산을 할 때, 우리는 직접 종이로 10진수 곱셈처럼 풀면 놀랍게도 풀리는 것을 볼 수 있다.

그림을 보면 위에 110, 101을 피승수, 승수라고 하고

중간 과정 (110, 000, 110)을 부분곱이라고 한다.

컴퓨터는 이런 부분곱이 3개 이상 나오면 CPU의 기본적인 연산장치(ALU)로는 입력 단자가 모자라 추가적 설계가 필요하게 되는데, 아래는 그에 대한 해결책을 설명한다.

 

3.4 시프트-덧셈 방식의 곱셈 연산

 

위 그림은 피승수 0110과 승수 0111의 시프트 - 덧셈 방식의 곱셈 연산을 보여준다.

각 단계별로, 누적 부분곱과 그 단계에서 나온 부분곱을 더한 후, 오른쪽 시피트를 계속해나가면

결과적으로 곱셈이 수행됨을 알 수 있다.

하지만 이 경우, 승수에 1이 많을수록 덧셈 수가 증가한다는 단점이 있다.

 

3.5 Booth 알고리즘

 

Booth 알고리즘의 원리는 다음과 같다.

우리가 만약 A x 01111110(2) 연산을 수행한다면 다음과 같이 나타낼 수 있다.

위 그림처럼, 비트가 1일 때마다 모두 곱하고 더할 수도 있겠지만, 더 큰 자릿수를 이용해 간단한 풀이법을 생각할 수도 있다.

Booth 알고리즘은 아래와 같은 방식을 따르는데, 이 방식은 일련의 패턴이 정해져 있다.

 

  • 승수 B(b0, b1, b2,..., bn)가 주어졌을 때, b0의 오른쪽에 값이 0인 1비트 b(-1)을 추가한다.
    ex. B(b0, b(-1), b1,..., bn)
  • 오른쪽 추가 비트 b(-1)로 부터 1비트씩 왼쪽으로 이동하며 2개의 비트를 묶어 점검한다.
  • 2비트 묶음 값에 따라 아래 표와 같이 수행한다. 

Booth 알고리즘을 사용한 0110(6) x 1011(-5) 연산 과정

이 방식을 사용하면 연산 횟수도 줄어들 뿐만 아니라 음수 연산도 가능하다는 장점이 있다.

 

4. 정수의 나눗셈

 

4.1 나눗셈 연산

위에서 손으로 푼 곱셈처럼 나눗셈도 우리는 종이로 충분히 계산할 수 있다.

몫 7, 나머지 3

문제는, 컴퓨터는 몫이 시작하는 자리를 우리처럼 한 번에 못 찾고,

윗 자릿수부터 하나하나 크기 비교를 해봐야 안다는 것이다.

아래는 이에 대한 해결방법을 설명한다.

 

4.2 복원 알고리즘

 

복원 알고리즘은 시프트를 이용해 피제수를 이동시키며 뺄셈 연산을 하여 비교한다.

복원 알고리즘

과정은 다음과 같다.

  • 1단계 : 부분 나머지를 1비트 왼쪽으로 시프트 하고, 부분 나머지의 왼쪽 4비트에서 제수(0010)를 뺀다. 뺄셈 결과가 음수면 부분 나머지를 원래대로 복원하고, 몫의 LSB에 0을 추가한다. 현재 몫은 0이다.
  • 2단계 : 그다음 부분 나머지와 몫을 1비트 왼쪽으로 시프트 한다. 이번엔 뺄셈 결과가 음수가 아니므로 몫의 LSB에 1을 추가한다. 현재 몫은 01이다.(2진수)
  • 3~4단계 : 위 과정을 반복하니 몫은 0101이 되고, 나머지는 피제수의 왼쪽 4비트 값으로 0001이 된다.

이런 복원 알고리즘은 뺄셈 연산 후 음수면 다시 복구해줘야 하기 때문에 느리다는 단점이 있다.

 

4.3 비 복원 알고리즘

 

비복원 알고리즘은 복원 알고리즘의 단점을 보완한 좀 더 효율적인 나눗셈 방법이다.

3(0011) ÷ 1(0001)

비복원 알고리즘의 과정은 다음과 같다.

 

  • 제수를 피제수의 왼쪽 비트와 맞추고, 제수를 뺀다.
  • 아래 과정을 피제수의 마지막 비트까지 반복한다.
    - 제수를 오른쪽 shift
    - 만약 부분 나머지가 음수라면 shift 된 제수를 더하고, 대응하는 비트의 몫은 0
    - 음수가 아니라면 대응하는 비트의 몫은 1

'Computer Architecture' 카테고리의 다른 글

6. 디지털 논리회로와 연산장치  (0) 2020.12.09
5. 데이터 종류와 형식  (0) 2020.11.26