Machines Called Computers
George Boole
- 조지 불은 19세기의 저명한 수학자. "The Laws of Thought"의 저자
- 인간의 논리적 생각은 명제 그리고 명제들을 and, or, not, if로 결합함으로써 표현할 수 있다고 주장 (조지 불 주장의 핵심)
→ 철학, 논리학에서 다룬 것을(논리적 생각) 수학으로 깨끗하게 정립할 수 있게 되었음
(인간의 논리적인 생각은 원래 철학, 논리학에서 다루던 것)
→ Mathematical logic 분야를 열다. (수학자들이 빈틈없이 논리를 전개하는데 꼭 필요)
mathematical logic과 computer science에는 2가지 연결고리 있음
💡첫번째 연결고리: artificial intelligence💡두번째 연결고리: Boolean algebra
Propositional Logic (명제 논리학)
- 조지 불이 제안한 이론
- propositional logic(명제논리학)에서 proposition은 basic building block
- Proposition: 선언적 문장. 반드시 ture 또는 false로 판단이 되어야한다.
x+3 = 5 : 이건 명제가 아니다. 명제 논리학에는 variable 개념이 들어가있지 않다.
추후 확장된 논리학에서(first-order logic)에서는 variable이 쓰여도 명제로 받아들임
x의 값이 결정되면 참 또는 거짓을 판단할 수 있다고 봄
- Compound proposition: 명제들을 and, or, not, if로 결합해도 참 또는 거짓 판단 가능. 즉 명제!
"recursive"하게 적용가능
Mathematical logic 과 Computer science의 연결고리
1. AI: knowledge-Based Approach
1945년에 최초의 컴퓨터인 애니악이 발명되었음. 사람들은 컴퓨터라는 기계가 만들어졌으니
이제 스마트한 소프트웨어만 개발하면 사람과 같이 생각하는 기계를 만들 수 있지 않을까?
생각하며 AI라는 용어를 만들고 연구에 들어감.
→ 다방면의 연구가 진행되었는데 그 중 중요한 축이 "knowledge-based approach"
연구하는 사람들은 사람은 intellgent 하며 그 이유는
사람은 살면서 많은 지식을 축적하고 그 지식을 기반으로 여러가지 추론을 하기 때문이라고 생각했음
그렇다면 컴퓨터라는 기계 안에 데이터로 지식을 충분히 저장하고, 논리적인 추론을 담당하는 프로그램
을 넣으면 사람과 같이 생각할 수 있는 기계를 만들 수 있을 거라고 생각함(knowledge-based approach 핵심 생각)
지식을 (명제의 형태로 저장하고) 논리적인 추론을 하는데 이론적인 기반을 제공해준게 mathematical logic
🥵주의: AI는 전부 knowledge-based approach로? 아님. 또 다른 축들이 있음
그 중 하나가 딥러닝(뉴럴 네트워크를 기반으로 하는 AI 기법)
Logic Programming
지난 70년간 컴퓨터 사이언스에서는 크게 4가지의 프로그래밍 패러다임을 만들었는데 그중 하나가 logic progamming
knowledge-based approach와 관련해서 만들어진 패러다임.
declarative programming이라 Fact와 Query로 이루어진다.
<Fact>
일단 알고 있는 지식을 정리함(fact). 이 지식을 바탕으로 논리적인 추론이 가능함→ query 요청하는게 가능.
1) 이렇게 단편적인 지식을 저장하는 것도 가능하고
2) 이런식으로 지식을 저장하는 것도 가능하다.
<parent와 child에 대한 rule을 가르쳐줌>
<선조에 대한 rule을 가르쳐줌>
→ 내포된 개념 잘 살펴보기
<Query>
결과적으로 추론(query)이 가능해진다.
→ 세조는 누구의 parent인가? ) 예종과 의숙공주
→ 단종은 문종의 child인가? ) True
→ 태종은 누구의 child인가? ) 설계에 따라 달라질 순 있지만 이 예에서는 태종의 부모는 정의되어 있지 않으므로 False라고 답함
→ 단종의 선조이면서 의숙공주의 선조인 사람은 누구인가?) 태종과 세종
<정리>
- logic programming은 우리가 해왔던 프로그래밍 스타일과 다름.
이런 프로그래밍 스타일을 declarative programming
- fact와 query로 구성되어 있음
- 사람이 직접 하면 되지 않나 생각할 수 있지만 수백만개의 지식이 있고 이걸 바탕으로 추론할때 사람은 정확하지 않음. 하지만
컴퓨터는 정확하다. 제한된 역할은 컴퓨터가 사람보다 훨씬 더 빠르고 정화하게 수행한다.
- C++, C 같은 건 fact와 query가 아니라 많은 양의 statement로 구성.
많은 명령문을 실행함으로써 원하는 목적을 달성한다고 해서 '임패러티브 프로그래밍' 이라고 함
2. Boolean Algebra (binary value + and, or, not 사용)
- algebra는 arithmetic(숫자를 다루고 사칙연산을 한다. (+, -, x, /) )이 다루는걸 그대로 받아들임
한가지 추가적으로 등장하는 개념이 variable.
→ variable의 사용으로 방정식이 등장하게 된다. (algebraic equation)
→ 이런 방정식은 세상의 많은 현상들을 모델링하는데 매우 중요
Elementary Algebra에선 실수값, 변수를 사용할 수 있고 사칙연산이 가능하다.
- boolean algebra에서는
set of values {0, 1}, set of operations: AND, OR, NOT 사용실수값 대신 → binary value
사칙연산 대신 → and, or, not
변수 사용 가능
- bool의 claim의 scale
2500년 전 사람들은 세상의 모든건 물, 불 흙, 공기로 이루어져있다고 생각했음.
그 후 수학이 발달하면서 어떤 수학자들은 이 세상은 숫자로 이루어져있다고 생각.
그리고 불은, 인간의 논리적인 생각은 명제와 and, or, not if로 이루어져있다고 주장. 세상의 근원과 관련된 아주 큰 주장
- boolean algebra는 digital logic design으로 연결. digital logic design에서는 boolean algebra에서 사용하는
and, or, not을 게이트로 만들어서 컴퓨터라는 자동장치를 만들었음.
이렇게 엄청난 영향을 미쳤기 때문에 어떤 사람들은 boole이 computer science의
개념적인 기초를 이루었다고 말하기도 한다. (복잡한 자동장치 설계 위한 수학적 기반 제공)
→ Boolean algebra 에서 이런 truth table이 주어졌을때 F를 x, y, z의 함수로 표현할 수 있겠는가? 와 관련된 고민도 함.
→ 간단하면 쉽게 풀수 있지만 복잡하면 바로 못 품. 그리고 푼다해도 유일한 방법이 아닐 수 있으며 더 심플한게 있을수도..
→ truth table이 주어졌을 때 관계를 띄워주는 알고리즘이 필요하다! 이게 boolean algebra의 문제
Automata(자동장치) Design and Boolean Algebra
- 지금까지 Ai, boolean algebra에 대해 살펴보았음. boole이라는 분의 업적이 computer science에
어떻게 영향을 미쳤는지 살펴본거. (mathematical logic과 computer science의 연결고리이므로)
이제 자동장치의 설계 및 구현에 초점을 맞추어 공부해볼거임.
- 인류는 간단한 자동장치에서 시작해서 점점 복잡한 자동장치를 만들어갔음. 그리고 400년 전에 정교한
기계장치인 스팀 엔진이 탄생함. (산업이 발달)
→ 더 똑똑한 장치를 만들기 위해 디지털 스위치라는 새로운 소자가 필요하다는 걸 알게 되었음
Electronics and Digital Switches
- 디지털 스위치는 그림처럼 3개의 단자를 갖는 소자.
점선으로 표시된 단자가 제어단자(control)
제어단자의 신호에 따라 스위치가 on 또는 off → 이렇게 on, off 2개의 상태를 갖는다 해서 디지털 스위치라고 부른다.
- mechanical 스위치(ex: 우리 방 불 끄고 키는거) 이건 사람이 제어한다. 사람의 힘으로 제어를 한다면 정교한 X
하지만 디지털 스위치는 센서에서 오는 전기적인 신호로 제어를 하므로 정교한 작업이 가능
- (Elecro-Mechanical) Relay: 인류가 최초로 만든 디지털 스위치
열고 닫히는게 기계적으로 철컥철컥 동작해서 electro-mechanical relay 라고 한다.
제어신호를 전기적으로 가해주면 전자석에 전기가 흘러 자석이 되고 통로가 닫혀서 신호가 흐르게 된다.
제어신호를 안넣으면 전기가 안흘러서 자석이 아니기 때문에 통로가 닫히지 않음. 신호가 흐르지 못함
→ 기계적인 움직임이 개입하다보니 동작하는 속도가 빠르지 않음.
- Electron or Vaccum Tube
Relay랑 구조는 비슷한데 기계적임 움직임을 없애고 방전현상을 이용해서 디지털 스위치를 구현.
라디오, TV, 최초의 컴퓨터인 애니악 등에 이 디지털 스위치가 사용됨.
→ 이렇게 디지털 스위치가 만들어짐에 따라 20세기 초에는 정교한 형태의 자동장치, 여러가지 형태의 계산기가 만들어짐
추후 이것보다 좋은 트랜지스터라는 디지털 스위치가 만들어져 오늘날처럼 빠른 컴퓨터를 만드는게 가능해짐.
Simple Automaton vs More Meaningful Automaton
디지털 스위치 사용한 설계와 사용하지 않은 설계를 비교해보자. (물의 수위가 높아지면 수문을 닫는 자동장치)
이건 디지털 스위치를 사용한 and, or, not 개념이 내제된 자동장치
Automata Design (Shannon, 1938)
섀넌) 20세기에 큰 업적을 남긴 유명한 엔지니어.
그동안 자동장치를 수작업으로 설계했음. 섀넌은 복잡 & 정교한 자동장치 를 만들기 위해선 체계적인 방법이 필요하다고 생각.
그리고 automata design boolean algebra와 관련이 있다는걸 알게됨
섀넌이 생각한 Systematic design of automata
- 원하는 기능을 나열
- 원하는 기능들을 보고 이걸 단위명제로 나눈다. (true 또는 false 값을 가지도록)
- 그리고 이들 명제 간의 관계를 truth table로 표현한다.
- output을 input variable의 boolean function으로 표현
(boolean algebra에서 연구하던게 truth table을 보고 output 을 input에 대한 함수로 표현하게 해주는 알고리즘)
(즉, 샤넌이 발견한건 우리가 하고 있는 오토마타 디자인(Digtal logic) == boolean algebra 문제)
→ 이 발견을 통해 복잡하고 정교한 자동장치를 체계적으로 설계할 수 있게 되었음
Digital Logic Design
- Binary(0, 1) 사용, AND OR NOT 이라는 로직게이트로 유용한 자동장치 만듬, 체계적인 설계 방법을 다루는 분야
Combinational logic design
- combinational logic design:
→ combinational logic이란? input이 결정되면 output이 정확하게 결정되는 시스템
- combinational logic design
주어진 것: AND, OR, NOT gates
패러다임:
- 원하는 기능 정리
- input 과 output variable을 결정
- input 과 output variables들의 관계를 truth table 표현
- output을 Input variable의 boolean function으로 표현
→ combinational logic design을 통해 4 bit adder를 만들 수 있음
(개념만 배우는거라 carry는 무시)
→ input variable과 output variable이 이렇게 정해진다.
→ truth table은 input variable이 8개이므로 2의 8승이라
총 2의 8승(256) 줄이 나온다.
→ 이제 F3 를 input variable에 대한 함수로 표현하고
→ F2도.., F1도..., F0도...
좋아보이지만 여기엔 숨은 문제가 있음: complexity (복잡도!!)
→ 32비트 adder, 64비트 adder 만든다 생각하면 끔찍..
Abstraction
공학 아닌 분야에서의 추상화
- 모든 엔지니어링 디자인에서는 복잡도 문제가 발생한다. 이런 complexity를 줄일 방법이 abstracion
- 우리 말로 추상화
- 자연어는 사실 추상 덩어리. 예를 들어 종이에다가 사과라는 글씨를 썼을 때 이 종이에 쓴 사과를 먹을 수 없음
즉, 이건 사과라는 object를 추상적으로 표현한거임.
- 공학에 좀 더 가깝게 접근해서 Selective ignorance: 작가가 그림 그릴 때 강조하고 싶은 부분은 강조하고
생략하고 싶은건 과감히 생략. 이렇게 꼭 필요한 것만 기억한다는 의미로 selective ignorance는
공학에서의 추상화의 의미와 일맥상통
공학에서의 추상화
공학에서의 추상화는 다음 2가지의 합 :1. Inteface(사용법)와 2. Implemenation(구현: 설계/구조/동작)
1) 모든 공학제품은 interface와 implemenation으로 구성된다.
2) 모든 공학제품은 Implemenation을 몰라도 interface만 알면 사용이 가능하다.
→ 이런것들이 어떻게 complexity를 줄일 수 있을까?
다음 두 파트를 공부하면서 이에 대해 알아볼거임
- Machine-level programming
→ "Interface" : machine instruction
→ "Implemenation": machine(CPUs)
- High level programming
→ "Inteface": programming language
→ "Implemenation": compilers(or interpreters)
공학에서 설계할때 Inteface와 Implemenation 중 뭐가 먼저?: Interface 디자인이 먼저!
Two Major Interface in CS
컴퓨터 사이언스에서 제일 중요한 2개의 interface: 1. Machine-level language, 2. programming language
1) 머신 instruction
머신(cpus) 은 머신 instruction이라는 인터페이스를 제공. 이 인터페이스를 구현한건 머신(cpus)
실제로 cpu의 구조, 설계방법, 동작 원리를 모르더라도 머신 instruction(사용법)만 이해하고 있으면
이를 사용해서 프로그램을 짤 수 있다.
머신 instruction interface가 중요한 이유) 이 인터페이스가 없으면 컴퓨터가 존재 X
어떠한 프로그램도 돌릴 수 없다.
그래서 1945년 애니악이 만들어지면서 machine instruction도 같이 등장함.
컴퓨터 구조론에서 배우는 부분이 바로 machine(CPUS) 와 machine instruction
2) High level language
high level programmig 하기 위해 필요한게 바로 high level language(ex: C, C++, Java)
C language가 사용법이고 이걸 제공한건 C compiler
생산성 향상을 위해 만든 이 인터페이스가 2번째로 중요한 인터페이스다.
Engineering: Building Abstraction
공학제품들은 매우 복잡해서, 작은 부품들로 복잡한 모듈을 만들고 이걸 사용해서 더 복잡한 모듈을 만드는 과정을 밟게 됨.
이 과정에서 필수적으로 수반되는게 abstraction.
ex) 32bit ALU design
- 현재 사용가능한 primitive는 AND, OR, NOT
- XOR 제작. 이렇게 만들고 나면 구현까지 생각할 필요 없고 Inteface만 가져옴. 그러고나면
primitive: AND, OR, NOT, XOR
- 같은 방식으로 MUX를 구현하고 추상화해서 primitive에 추가
- primitive: AND, OR, NOT, XOR, MUX를 사용해서 1 bit ALU를 제작하고 추상화함
<그중에서 1-bit full adder 만드는 것만 보면>
아까 배웠던 단계를 따라 Input과 Output을 정한다.
- Input: two bits to add, carry from right
- Output: sum, carry to left
→ 이걸로 2의 3승개의 열을 가진 truth table을 만들고
→ sum과 carry to left를 input variable에 대한 함수로 표현한다.
→ 결과 :one-bit full adder도 공학제품이다. 이걸 설계하고 다른 곳에서 사용할 때 구현을 그대로 가져갈 필요가 X
인터페이스만 알면 된다.
<결과적으로 만들어진 1-bit ALU를 보면>
1-bit adder: 로직 연산, 산술 연산 다 가능하다.
- primitive: AND, OR, NOT, XOR, 1 bit ALU를 가지고 32 bit ALU를 디자인
(1 bit ALU 32개 연결시키고, carry 체인을 연결하면 된다. )
→ 사실 32비트 ALU가 이렇게 쉽게 설계되는건 아님. 우리 지금 기능에만 초점을 맞췄고, 성능엔 전혀 초점을 안맞췄다.
ALU는 컴퓨터에서 매우 핵심적인 요소이기 때문에 성능이 매우 중요함에도 불구하고!
→ 32비트 ALU + 여러 레지스터들 + 연동하기 위한 로직 회로들이 합쳐져 CPU가 만들어진다. 이것도 하나의 abstraction
여기에다가 메모리를 추가하고 I/O 장치등을 추가하면 컴퓨터라는 굉장히 복잡한 abstraction이 만들어진다.
→ 레지스터들: CPU 안에 임시로 데이터를 저장하는 장소. 그 중 몇개..
PC(program counter): 다음에 실행할 instruction의 주소를 담는 곳
IR(instruction register): 실행할 instruction을 가지고 와서 담는 곳
Primitive-Composition-Abstracion <공학에서의 Abstraction>
앞에서 짧게 abstracion이라고 표현했지만 길게 표현하면 제목과 같음.
- 디지털 로직 디자인의 기본 패러다임이다.
모든 digital logic의 처음 Primitives: AND, OR, NOT gate
Composition: primitive를 사용해서 약간 복잡한 functional unit을 만든다.
Abstraction: 만든 functional unit를 인터페이스만 보고 사용할 수 있도록 추상화시킨다.
그럼 이건 새로운 primitive가 된다.
- 모든 공학 디자인에서 공통되는거. 분야마다 primitive가 다를 뿐.
hierarchically하게 적용하여 점점 더 복잡한 abstraction을 만들어간다.
Storage(Register and Memory)
(메모리는 AND, OR, NOT 기반의 자동장치)
- SR flip flop에 주변 회로들을 조금씩 추가하면 1 bit storage를 만들고 abstraction 할 수 있음.
1 bit storage에는 0 또는 1을 write 하거나 read 할 수 있다.
- 1 bit storage 32개를 병렬로 연결하면 32 bit storage를 만들 수 있음.
(안에 구획 나눈게 보이면 Implemenation. 안보이면 Interface)
Main Memory in 32 bit Computer
- 32bit storage 인터페이스를 위아래로 많이 포개면 메인 메모리가 만들어진다.
그런데 이렇게 메모리 location이 많아지면 cpu는 어느 메모리 location에 읽고 쓸지 결정해줘야한다.
→ 그걸 담당해주는게 address!
- Address: memory의 각 location에 대한 unique identifier
- Decoder: address가 주어지면 address에 따라 해당 위치의 메모리를 enable 시키는 장치
ex) 만약 32bit storage 8개 포개놓았으면 address는 3비트 쓰면 된다. 이때 쓰는 디코더를
3-to-8 decoder 라고 부른다.
Number of Address Bits
- 256 = 2^8 memory locations(주소 개수): 8-bit address
- 64K = 2^16 memory location: 16-bit address
→ 8 bit microprocessor 에서 사용
- 4G = 2^32 memory location: 32 ㅠㅑㅅ ㅁㅇㅇㄱㄷㄴㄴ
→ 32 bit processor에서 사용
32-bit Computers
cpu의 register도 32비트. 머신 instruction 길이도 32비트.
데이터 기본 크기도 32비트. address도 32비트.
→ memory location의 크기 4G
→ 이후 64비트 컴퓨터로 확장
Sequential Logic Design
- 우리가 사용한 복잡한 기능들은 거의 다 combinational 이 아니라 sequential logic이다.
sequential logic도 combinational logic과 마찬가지로 and, or, not 기반이다.
if 개념은 뒤의 수업에서 배우게 된다.
- output은 input과 state 값에 따라 결정
- next state는 input과 state 값에 따라 결정
- Register랑 Memory 이 둘은 storage가 필요한 sequential 로직임
Register랑 Memory를 포함하는 CPU 역시 sequential 로직
전체적인 컴퓨터라는 기계도 sequential 로직
Synchronous Sequential Logic Circuits
cpu 안에는 많은 회로들이 들어있음. cpu가 잘 동작하기 위해서는 많은 회로들이 시간에 동기되어 사용되어야 함
같은 시간에 연산을 시작하고 같은 시간 내에 연산을 끝내야 이들이 협력하여 유용한 동작을 할 수 있음.
그렇게 하기 위해 cpu 안에 있는 모든 회로에는 외부로부터 clock이라는 시그널이 제공된다.
- clock 신호가 올라가는 순간 동작이 시작함. 이때 state 값을 가지고 있고, input이 주어진다.
clock 한주기 동안 열심히 계산을 해서 다음 clock이 올라가기 전까지 output과 next state 값 결정
- 이렇게 clock 한주기마다 새로운 단위연산을 진행한다.
Uploaded by N2T