[밑바닥부터 만드는 컴퓨팅] 01장 불 논리

개요

해당 내용은 ‘밑바닥부터 만드는 컴퓨팅 시스템’ 책의 1장 내용을 정리하였습니다. 하드웨어 관련 내용이 대수 있어 소프트웨어만 보던 개발자에게는 조금 생소하긴 했습니다. 그래도 컴퓨터를 이해하기 위해서는 좋은 내용들이라고 생각됩니다.

1. 배경

해당 장에서는 불 대수를 간략하게 살펴보고 복잡한 기능을 하는 칩의 구성을 살펴봅니다. 이후 실습을 통해 실제 하드웨어 설계 방법을 진행합니다.

1.1 불 대수

불 대수는 [참 / 거짓], [1 / 0], [예 / 아니오] 와 같은 불 값을 대루는 대수학입니다. 앞으로의 불 값은 [1 / 0]으로 사용할 것입니다. 컴퓨터가 1과 0으로 구성되었다는것도 불 대수를 기반으로 하기 때문이죠.

어떠한 불 함수를 정의하는 가장 쉬운 표현은 입력과 결과를 나란히 쓰는 방법이고, 이를 진리표라고 부릅니다. 뒤에서 다시 다루겠지만, and 연산의 진리표는 다음과 같이 표현할 수 있습니다.

x	y	out
0	0	0
1	0	0
0	1	0
1	1	1

진리표 말고도 입력값에 대한 불 연산으로도 표현이 가능합니다. 기본적으로 자주 사용되는 불 연산은 and, or, not 과 같은 연산이 있습니다. and는 x*y, or은 x+y 와 같이 표현할 수 있습니다.

1.2 게이트 논리

게이트는 불 함수를 구현한 물리적 장치입니다. n개의 변수를 받아 m 개의 2진 결과값을 반환하는 불 함수가 있다면, 이 함수를 게이트에는 n개의 입력 핀에 입력하여 계산한 뒤 m개의 출력 핀으로 보내게 됩니다. 가장 단순한 형태의 게이트들은 트랜지스터라고 불리는 아주 작은 스위치 장치들을 특정 구조로 연결해서 특정 기능이 가능하도록 만들었습니다. 0과 1을 표현할 수 있는 스위치는 여러 기술로 구현할 수 있지만, 그 기능들을 모두 불 대수로 추상화할 수 있다는 사실은 매우 중요합니다. 컴퓨터 과학자들은 전기 회로, 스위치, 릴레이, 전원 공급장치 같은 물리적인 영역에 신경 쓸 필요가 없기 떄문입니다. 그 대신 컴퓨터 과학자들은 다른 누군가가 하드웨어를 물리적으로 구현한 하드웨어를 사용하기에 추상적인 불 대수와 게이트 논리만 신경쓰면 됩니다. (극공감…!) 하드웨어 설계자는 기본 게이트인 and, or, not과 같은 게이트를 조합하여 더 복잡한 기능을 구현합니다.

예를 들어 3way and 게이트를 구성한다고 생각해봅시다. and(a, b, c) = and(and(a, b), c) 로 구성할 수 있습니다.

xor 게이트도 마찬가지로 and와 or 게이트로 구현이 가능합니다. xor은 입력이 (1, 0) 또는 (0, 1) 일때 결과가 1입니다. 즉 xor(a, b) = or( and(a, not(b)), and(not(a), b) ) 로 표현할 수 있습니다.

앞에서 나타낸 xor 식으 5개의 게이트로 구성하였지만, 4개의 게이트로도 구성이 가능하다고 합니다. 기능적 관점에서의 설계는 요구된 사항을 어떤 방식이로든 만족하도록 설계하면 됩니다. 효율성 관점으로는 가능한 적은 수의 게이트를 이용하는 최소 비용 최대 효과를 내는 것이 요구사항이 됩니다.

1.3 실제 하드웨어 구성

앞서 언급한 게이트는 대학시절 컴퓨터구조에 대한 수업을 할때면 가장 먼저 배우는 내용입니다. 하지만 그때는 저는 소프트웨어 개발자이기에 그냥 이런게 있구나… 하고 넘어갔었죠. 아마 대부분의 사람들도 그랬을것 같습니다.

다음은 책에 작성된 예시입니다. 칩 제조 공장을 열었고 XOR 게이트 100개를 제조해달라는 주문을 받았습니다. 주문계약금으로 납땜기, 구리선, AND 게이트, OR 게이트, NOT 게이트가 여러개 들어있는 셋트를 구매하였습니다. 이 게이트들은 입력과 출력 및 전원공급 단자가 달린 플라스틱으로 되어있습니다. 우리는 구메한 게이트를 구리선으로 하나씩 납땜하여 XOR 게이트를 만들 수 있습니다. 이후 플라스틱 케이스로 밀봉하고 XOR이라고 이름표를 붙입니다.

간단하게는 이러한 방법을 사용하여 칩을 만들 수 있습니다. 하지만 부족한 점이 많습니다. 초보자에게는 칩 설계도가 맞는지 확신하기 어렵습니다. 만약 납땜을 다 하고 테스트하는데 원하는대로 동작하지 않는다면 물리적인 구조를 고쳐야 할 것입니다. 시간도 많이 걸리고, 실수하기도 쉽습니다. ㅠㅠ

1.4 하드웨어 기술 언어

해당 부분은 알아두면 좋겠지만, 개발자에게 꼭 필요한 내용은 아닐것으로 생각되어 간단하게만 정리하려 합니다.

오늘날 하드웨어 설계는 위와같은 방법으로 진행되지는 않습니다. 하드웨어 기술 언어(Hardware Description Language) 또는 HDL이라 불리는 도구룰 사용하여 칩 아키텍쳐를 설계하고 최적화합니다. 칩 설계자는 HDL로 프로그램을 작성하여 테스트를 합니다. 이 테스트들은 가상의 컴퓨터 시뮬레이션으로 실행하여 칩의 동작을 테스트할 수 있습니다. 그렇게 하여 원하는 출력값이 나타나는지 확인할 수 있습니다.

하드웨어 설계자는 칩의 동작뿐만 아니라 연산 속도, 소비 전력, 기타 변수 등 다양하게 고려해야 합니다. 원하는 요구사항을 만족할 때 까지 칩을 설계하여 최적화를 합니다.

2. 명세

해당 절에서는 불 연산을 수행하는 다양한 게이트들에 대해서 정의합니다.

2.1 기본 논리 게이트

2.1.1 Nand 게이트

Nand 게이트는 And 게이트와 반대되는 값을 나타냅니다.

a	b	Nand(a, b)
0	0	1
0	1	1
1	0	1
1	1	0

칩 이름: Nand
입력: a, b
출력: out
기능: If a=b=1 then out=i else out=1.
설명: 이 게이트는 가장 기본이 되는 게이트이므로 따로 구현할 필요가 없다.

2.1.2 Not 게이트

Not 게이트는 컨버터 라고도 불립니다. 입력된 비트를 변환해줍니다.

a	Not(a)
0	1
1	0

칩 이름: Not
입력: in
출력: out
기능: If in=0 then out=1 else out=0.

2.1.3 And 게이트

And 게이트는 입력값이 모두 1일때 1을 반환하고, 그 외에는 0을 반환합니다.

a	b	And(a, b)
0	0	0
0	1	0
1	0	0
1	1	1

칩 이름: And
입력: a, b
출력: out
기능: If a=b=1 then out=1 else out=0.

2.1.4 Or 게이트

Or 게이트는 입력된 값 중 하나가 1이라면 1을 반환하고 그 외에는 0을 반환합니다.

a	b	Or(a, b)
0	0	0
0	1	1
1	0	1
1	1	1

칩 이름: Or
입력: a,b
출력: out
기능: If a=b=0 then out=0 else out=1.

2.1.5 Xor 게이트

배타적 논리합 이라고도 불립니다. Xor은 두 입력값이 다를때 1을 반환하고 그 외에는 0을 반환합니다.

a	b	Xor(a, b)
0	0	0
0	1	1
1	0	1
1	1	0

칩 이름: Xor
입력: a, b
출력 out
기능: If at then autel else out=0.

2.1.6 멀티플렉서

멀티플렉서는 3-입력 게이트로 선택비트를 이용하여 나머지 두 데이터 중 하나를 선택합니다. 멀티플렉서라는 이름은 통신시스템에서 하나의 출력선에 여러 신호를 직렬화하는데 사용되는 기기명에서 따온 것이라고 합니다.

a	b	sel	out
0	0	0	0
0	1	0	0
1	0	0	1
1	1	0	1
0	0	1	0
0	1	1	1
1	0	1	0
1	1	1	1

칩 이름: Mux
입력: a,b, sel
출력: out
기능: If sel=0 then outca else out=b.

2.1.7 디멀티플렉서

디머리플렋는 머리블렉서와 정반대 기능을 합니다. 선택한 비트에 따라 두 출력선 중 하나를 선택하여 신호를 보냅니다.

침 이름: DMux
입력: in, sel
출력: a,b
기능: If sel = 0 then {a=in, b=0} else {a=0, b=in}.

sel	a	b
0	in	0
1	0	in

2.3 기본 게이트의 멀티비트 버전

컴퓨터 하드웨어는 일반적으로 버스(bus)라 불리는 멀티비트 배열에 대한 연산을 수행합니다. 예를 들어 32bit의 컴퓨터는 두개의 32비트 버스에 대한 and 연산을 할 수 있습니다. 이러한 연산은 32개의 2진 and 게이트를 나란히 놓고 각 비트쌍마다 and를 적용하는 방식으로 구현됩니다.

헤당 절에서는 16비트 컴퓨터 구척에 필요한 멀티비트 논리게이트가 소개됩니다. 만약 data라는 16비트 버스가 있다면 data[0]. data[1] … , data[15]와 같이 각각 표현할 수 있습니다.

2.3.1 멀티 비트 Not

멀티비트 Not 은 n 비트 입력 버스의 모든 비트에 Not 연산을 수행합니다.

칩 이름: Not16
입력: in [16] // 16비트 핀
출력: out [16]
기능: For i=0..15 out [i]=Not (in[i]).

2.3.2 멀티 비트 And

멀티 비트 And 는 두개의 n 비트 입력 버스로 들어오는 모든 n비트 쌍에 대해 and 연산을 수행합니다.

칩 이름: And16
입력: a[16], b[16)
출력: out [16]
기능: For i=0..15 out[i]=And(a[i],b[i]).

2.3.3 멀티 비트 Or

멀티 비트 Or 는 두개의 n 비트 입력 버스로 들어오는 모든 n비트 쌍에 대해 or 연산을 수행합니다.

첩 이름: Or16
입력: a[16], b[16]
출력: out[16]
기능: For i=0..15 out[i]=or(a[i],b[i]).

2.3.4 멀티비트 멀티플렉서

멀티비트 멀티플렉서는 입력이 n 비트라는것을 제외하면 위에서 언급한 멀티플렉서와 같습니다. 선택은 여전히 1비트입니다.

첩 이름: Mux16
입력: a[16], b[16], sel
출력: out [16]
기능: If selea then for i=0..15 out[i]=a[i]
      else for i=8..15 out[i]=b[i].

2.2 산술 논리 연산 장치

산술 논리 장치 (ALU, arithmetic logic unit) 는 특정 컴퓨터 플랫폼의 핵심 역할을 하게 됩니다. 이 ALU는 내부 부품을 최소화하면서 많은 기능을 할 수 있습니다.

ALU는 16비트의 x와 y가 입력되고 16비트의 out이 출력됩니다. 또한 6개의 입력비트를 이용하여 18개의 정해진 산술 및 논리 연산을 수행하게 됩니다. 다음은 ALU 의 명세입니다.

아래는 6개의 입력비트를 이용한 18의 산술 연산에 대한 진리표입니다.

zx	nx	zy	ny	f	no	out=
1	0	1	0	1	0	0
1	1	1	1	1	1	1
1	1	1	0	1	0	-1
0	0	1	1	0	0	x
1	1	0	0	0	0	y
0	0	1	1	0	1	!x
1	1	0	0	0	1	!y
0	0	1	1	1	1	-x
1	1	0	0	1	1	-y
0	1	1	1	1	1	x+1
1	1	0	1	1	1	y+1
0	0	1	1	1	0	x-1
1	1	0	0	1	0	y-1
0	0	0	0	1	0	x+y
0	1	0	0	1	1	x-y
0	0	0	1	1	1	y-x
0	0	0	0	0	0	x&y
0	1	0	1	0	1	x	y

단순한 연산부터 확인해보겠습니다. a+b 는 단순히 a와 b를 더하면 됩니다. 따라서 f만 1로 변경해주면 a와 b를 더하게 됩니다.

이번엔 a-b를 보겠습니다. nx, f, no 가 1입니다. x를 반전하여 y와 더한 후 출력을 한번 더 반전시킵니다. 예시로 8비트로 5-3을 보겠습니다.

1. x를 반전 
Not(00000101) = 11111010 (-6)

2. y와 add 연산 

  11111010  (-6)
+ 00000011  (3)
-----------
  11111101  (-3)

3. 출력을 반전
Not(11111101) = 00000010 (2)

이와 같은 방법으로 x-y를 구현할 수 있습니다. 나머지 연산들도 위와 같은 방법으로 따라해보면 신기하게도 해당 기능이 수행되게 연산됩니다.