Chapter 3. Memory

Source Code

Introduction

시작하며

Having built the computer’s ALU, this module we turn to building the computer’s main memory unit, also known as Random Access Memory, or RAM. This will be done gradually, going bottom-up from elementary flip-flop gates to one-bit registers to n-bit registers to a family of RAM chips. Unlike the computer’s processing chips, which are based on combinational logic, the computer’s memory logic requires a clock-based sequential logic. We will start with an overview of this theoretical background, and then move on to build our memory chipset.

Key concepts: combinational vs sequential logic, clocks and cycles, flip-flops, registers, RAM units, counters.

**💡 컴퓨터의 ALU를 구축한 후 이 모듈에서는 컴퓨터의 주 메모리 장치(RAM 또는 랜덤 액세스 메모리라고도 함)를 구축합니다. 이 작업은 기본 플립플롭 게이트에서 1비트 레지스터, n비트 레지스터, RAM 칩 제품군으로 점진적으로 상향식으로 진행됩니다. 조합 논리를 기반으로 하는 컴퓨터의 처리 칩과 달리 컴퓨터의 메모리 로직에는 클럭 기반 순차 로직이 필요합니다. 이 이론적 배경에 대한 개요부터 살펴본 다음 메모리 칩셋을 제작해 보겠습니다.

주요 개념: 조합 논리 대 순차 논리, 클록과 사이클, 플립플롭, 레지스터, RAM 단위, 카운터.**

Unit3-1. Sequential Logic

앞 서 챕터 2개의 프로젝트는 시간적인 문제를 고려 하지 않았다. 입력을 하면 바로 출력이 되는 형태이고, 입력한 값은 시간이 지나 변하지 않는 불변 자료형의 상태에서 프로그래밍을 해 왔다.

컴퓨터 하드웨어는 시간이 지나 과거의 것 들을 기억하여 중간 결과, 마지막 결과를 연산 하는 과정을 구현 할 수 있다.

논리 게이트를 이용 해서 일정 시간 동안 값을 저장 하는 방법
변수가 값을 기록 하도록 설정 하고 그 값을 유지 하는 방법

챕터 1,2 는 시간과 무관한 칩이었고 이 것들을 조합 칩 이라고 부른다. 칩 내부에서 계산에 걸리는 시간을 제외 하고는 지연 없이 다양한 조합의 입력에 대한 출력을 내기 때문이다.

앞으로 만들 칩은 순차 칩이다. 현재 시점의 입력 뿐 아니라 이전에 처리 했던 입력 및 출력에도 영향을 받는다.

당연히 현재와 이전의 개념은 시간과 관련이 있다. 이전에 메모리에 저장 해 둔 내용을 기억 할 수 있는 것이다.

Combinational Chip

Sequential Chip

Untitled

The Clock

시간의 진행은 틱과 톡이라는 2진 신호를 연속적으로 생성 하는 클록을 이용 하여 모델링 할 수 있다.

틱의 시작과 톡의 종료 사이의 시간을 주기 라고 하는데, 이 주기는 컴퓨터의 모든 메모리 칩의 작동을 조정하는 역할을 한다.
한 주기는 0-1, 고-저, 틱-톡의 두 상태를 연속적으로 오가는 발전기로 구현 됨
각 클록 주기는 하나의 이산적 시간 단위를 모델링 한 것
클록 상태는 2진 신호로 표현 되며, 이 마스터 클록 신호는 하드웨어의 회로망을 통해 컴퓨터에 있는 모든 메모리 칩에 동시에 전달 됨

💡 이러한 모든 칩 내에서 클록 입력은 저수준의 DFF 게이트로 보내지며, 칩은 새로운 상태로 바뀌고 클록 주기의 끝에서만 값을 출력하게 됨

Physical Time

Untitled

Quiz

연속 시간 대신 불연속 시간 단계를 사용하는 이유는 무엇인가요?
1. 시스템 상태가 안정화되도록 하기 위해서입니다.
2. 더 빠릅니다.
3. 전자를 한 곳에서 다른 곳으로 순간적으로 이동시켜 전기 신호의 지연을 방지합니다.
4. 양자 시간의 한계로 인해 시간이 불연속적이기 때문입니다.
⇒ 1

Unit3-2. Flip Flops

Remembering State

Missing ingredient: remember one bit of information from time t-1 so it can be used at time t.
At the “end of time” t-1, such an ingredient can be at either of two states: “remembering 0” or “remembering 1”
This ingredient remembers by “flipping” between these possible states.
Gates that can flip between two states are called Flip-Flops.

**💡 기억해야 할 정보

시간 t-1에서 한 비트의 정보를 기억하여 시간 t에서 사용할 수 있도록 함
“시간의 끝” t-1에서 이러한 성분은 두 가지 상태 중 하나에 있을 수 있으며, “0” 또는 “1”을 기억함
이 가능한 상태 사이를 “플립”하는 방식으로 기억함
두 상태 사이를 넘나들 수 있는 게이트를 플립플롭이라고 함**

The Clocked Data Flip Flop

Untitled

out은 지난 시간의 것을 기억 하고 있다

이 칩에서 기억 할 점은 순차 칩이며 이전의 값을 기억 한다는 것이다.

**💡 클록과 함께 0과 1의 두 안정 상태를 왔다 갔다 할 수 있는 시간의존적 논리 게이트를 도입 해서 논리 게이트가 상태를 유지 하고 시간이 변함에 따라 응답 하도록 하는 문제를 해결 하고자 하며 이 것을 데이터 플립플롭 이라고 부른다. → 입력 및 출력이 1비트 데이터로 된 플립 플롭임 각 시간 단위가 끝날 때 DFF가 이전 시간 단위의 입력 값을 출력 한다.

DFF(이하 데이터 플립플롭)는 컴퓨터 아키텍처에서 눈에 띄는 역할을 하는 레지스터, RAM 장치, 카운터와 달리, 다른 메모리 장치 깊숙한 곳에서 조용히 제 역할을 하는 저수준 부품일 뿐이다.

DFF들은 모두 마스터 클록에 연결되어, 거대한 합창단 같이 행동하며, 각 클록 주기가 끝날 때 컴퓨터 내 모든 DFF 출력들은 이전 클록 주기의 입력에 따라 맞춰진다.

그 외 시간에는 DFF가 “잠금” 상태가 되는데, 이 말은 입력이 변해도 출력이 곧 바로 영향을 받지 않는다 하드웨어적으로는 시스템 내 모든 DFF게이트에 마스터 클록의 신호를 동시에 전달하는 전용 클록 버스를 통해 이런 시간의 의존성을 구현한다.**

Untitled

첫번째 주기에서는 이전 주기 입력이 없으므로 DFF 출력이 정의 되지 않는다.
그 뒤로 이어지는 모든 시간 단위에서 DFF 출력은 이전 시간 단위의 입력이 된다.

Untitled

시간의 문제

예시)

ALU: 7 - 2
- OUT: 5
- ALU의 연산에는 2가지 이유로 항상 지연이 발생함.

지연 발생

칩의 입력이 갑자기 나타나지 않는다는 점
- 그 대신 입력 신호는 다릅 칩의 출력에서 이동 해 온 것이며, 이동에는 시간이 걸림
칩이 계산을 수행 하는 데도 시간이 걸림
- 칩에 부품이 많을수록(논리가 정교할수록), 칩 회로에서 출력이 다 만들어질 때 까지 시간이 더 오래 걸림

**💡
시간의 진행은 연속적으로 생각된다.

즉, 두 시점 사이에는 항상 또 다른 시점이 있고 그 사이의 변화는 무한히 작음

시간이 연속적으로 진행된다고 보지 않고, 주기라는 고정된 길이의 간격으로 쪼개서 봄

연손적인 시간의 화살표 개념에서는 시간을 무한히 나눌 수 있지만, 주기 개념에서는 시간은 더이상 쪼개지 않고 가장 기본적인 단위가 됨
주기가 전환 될 때만 실제로 세상에 변화가 일어나고, 주기 도중에는 세상의 변화가 정지 됨**

Untitled

⇒ 상태 변화는 주기가 전환 될 때만 관찰되며 주기 도중의 변화는 무시됨

시간을 이산적으로 생각하면 연속적인 변화를 무시 할 수 있음

이산적인 시간의 개념

이산적 시간 개념을 통해 통신이나 계산 중에 발생하는 시간 지연과 관련된 무작위성을 줄일 수 있음
시스템 전체에서 여러 칩들의 연산을 동기화 하는 데 그 개념을 활용 할 수 있음

**💡 주기가 끝날 때만 상태를 확인하기 때문에 시간 지연은 관찰하지 못하며 대신, 게이트에 0을 입력 하면 1이 출력 되는 것 처럼 보이게된다. 즉, 매 주기가 끝날 때 마다 관찰 해 보면 즉시 출력한다고 결론을 내릴 수 있기 때문에 시간의 문제에서 벗어날 수 있다.

주기 길이 설정

어떤 시간 지연이든 문제가 없을 정도로 주기를 길게 잡는 것
컴퓨터가 빠르게 동작하도록 주기를 짧게 잡는 것

주기 길이는 시스템 내 모든 칩에서 발생하는 최대 시간 지연보다는 살짝 더 길게 잡아야함**

Implementation of the D Flip Flop

In this course: it is a primitive
In many physical implementations, it may be built from actual Nand gates:
- Step1 : create a “loop” achieving an “un-clocked” flip-flop
- Step2: Isolation across time steps using a “master-slave” setup
Very Cute
- But conceptually confusing
Our Hardware Simulator forbids “combinatorial loops”
- A cycle in the hardware connections is allowed only if it passes through a sequential gate

**💡 DFF 구현하기

실제 낸드 게이트로 구현 할 수 있음
- 1단계: “클럭되지 않은” 플립플롭을 달성하는 “루프” 만들기
- 2단계: “마스터-슬레이브” 설정을 사용하여 시간 단계에 걸쳐 분리하기
→ 마스터 슬레이브 구조: 마스터 서버의 데이터를 복제 한 슬레이브 영역에서 컨트롤 어시스트 하기
간편하다
- 하지만 개념적으로는 혼란스러움
하드웨어 시뮬레이터는 “조합 루프”를 사용 할 수 없음
- 하드웨어 연결의 사이클은 순차 게이트를 통과하는 경우에만 허용됨**

Sequential Logic Implementation

이 순차 칩들은 조합 칩과도 상호 작용 할 수 있다. 순차 칩은 피드백 루프를 통해 이전 시간 단위의 입력 및 출력에 응답 할 수 있다.

조합 칩은 피드백 루프를 넣으면 출력은 입력을, 입력은 출력을 따르므로 결국 출력이 자기 자신을 따라 결정되는 문제점이 존재한다. 하지만, 피드백 루프가 DFF 게이트를 거친다면 출력을 다시 입력으로 넣는 데 문제가 없다.

DFF 자체에 시간 지연이 있어서 시간 t의 출력이 자기 자신이 아니라 시간 t - 1의 출력에 따르기 때문

**💡 피드백 루프란?

출력 신호를 다시 입력으로 넣는 구조**

Untitled

순차 논리 설계에는 일반적으로 조합 칩에서 입력을 받거나 조합 칩에 연결되는 DFF게이트가 들어간다. 순차 칩은 이런 연결을 통해 현재 및 이전 입출력에 응답할 수 있게 된다.
- 입력을 받고 조합 칩에서 나온 Output은 DFF를 거쳐 반환하고, 그 값을 다시 Input에서 사용하게 된다.

순차 칩에 시간 의존성이 있어서 얻게 되는 중요한 부가 효과는 전체 컴퓨터 아키텍처를 동기화 하는 데 이 특성을 활용 할 수 있다.

만약, ALU에게 x+y 명령을 내렸다고 가정 한다면

**💡 ALU

INPUT: x+y

x: 근처 레지스터의 출력 값
y: 멀리 위치한 RAM 레지스터의 출력 값

→ 거리, 저항, 간섭 같은 물리적 제한으로 x 및 y의 전기 신호가 ALU에 도착하는 시점 상이

⇒ 조합 칩인 ALU에는 시간 개념이 없으므로 언제 어떤 데이터가 들어오든 계속 값을 더함

x + y는 올바른 값을 출력 할 때 까지 시간이 걸릴 뿐 더러 이전의 출력 값은 의미가 없게 됨

이 문제를 극복하기 위해 이산적인 시간 개념을 도입 하면 신경 쓸 필요가 없게 된다.

비트 하나가 가장 긴 경로를 따라 전송되는 시간과, 칩 내에서 가장 오래 걸리는 계산 시간을 더한 것 보다 클록 주기를 살짝 더 길게 만들면 되기 때문이다.

→ 이렇게 하면 주기가 끝날 때는 ALU의 출력이 유효하다고 보장 할 수 있음

이 방법은 위에서 언급 했던 서로 다른 하드웨어 부품들을 하나의 시스템으로 동기화 하는 기술이다.**

Remembering For Ever: 1 -bit Register

Goal: remember an input bit “forever” : until requested to load a new value

비트 칩은 1비트 정보를 저장 하며, 칩 인터페이스는 데이터 비트를 전달 하는 입력 in과 쓰기 기능을 설정하는 load 입력, 그리고 레지스터의 현재 상태를 출력 하는 Out으로 이루어짐

load 비트가 설정 되지 않으면 레지스터가 잠금 상태가 되며, 입력 값과 관계 없이 현재 상태를 유지함

Working “Bit” Implementation

Untitled

Load에 의해 값이 결정되기 때문에 Multiplexor 을 이용 하면 파이프라인을 연결 할 수 있다
Quiz
- DFF는 항상 “in” 비트를 저장하는 반면, Bit는 “로드”가 1로 설정된 경우에만 저장한다
- DFF는 일시적으로 정보를 저장할 수 있는 반면, 비트는 여러 주기에 걸쳐 정보를 저장할 수 있음

t = 1

Untitled

INPUT: in, load 값을 입력 받고, Multiplexor를 통과 한다.
- 이 때, 이전 값은 모르기 때문에 0으로 설정이 되어 Multiplexor는 a,b, sel의 구조로 1이 된다.
OUT = 1 ⇒ 이 값은 DFF의 INPUT으로 쓰이게 되고, OUTPUT은 1이 된다.

t = 2

Untitled

Unit3-3. Memory

Memory

Memory:
- Main memory: RAM
- Secondary memory: disks
- Volatile / non-voiolatile
RAM:
- Data
- Instructions
Perspective:
- Physical
- Logical

The most basic memory elment: Register

Untitled

메모리 설계에 가장 근간이 되는 1-bit 레지스터의 원리를 알고 있기 때문에 큰 이해 없이 단일 비트 레지스터를 여러개 가져와서 서로 나란히 놓을 수 있다는 것을 알 수 있으며 이렇게 하면 16비트 숫자의 추상화를 만들 수 있다.

이 것을 추상화 레지스터라고 한다.

레지스터의 너비는 일반적으로 매개변수 w이며 다른 컴퓨터에서 16비트, 32비트, 64비트가 될 수 있다.

Register’s state: 현재 레지스터에 저장된 값

Register / read logic

Untitled

레지스터의 값을 어떻게 읽을까?

출력 값을 확인 하면 된다 → 출력은 단순히 레지스터의 상태를 반환하기 때문
- 따라서 출력에서 나오는 값을 조회하기만 하면 특정 시간 주기에 레지스터 내부에 무엇이 저장되어 있는지 알 수 있음

Register / write logic

이제부터 레지스터에서 숫자 17을 기억하도록 하고 싶다고 가정해보자.

To set Register = v
set in = v
set load = 1

17이라는 새 값을 설정하고 로드 비트를 불러온다 여기서 로드 비트를 불러온다는 것은 로드 비트를 1로 설정함.

Register = v
그리고 다음 주기부터 레지스터의 출력도 이 값 v를 내보내기 시작 → 그래서 다음 주기 부터 레지스터는 새로운 값 17을 기억함

RAM unit

Untitled

RAM abstraction:
- 메모리에 대해 생각하는 방식은 메모리를 주소 지정이 가능한 레지스터의 시퀀스로 생각하는 것
- 즉, n개의 레지스터로 구성된 RAM 장치의 경우 0 부터 n-1을 뺀 범위의 주소가 있는 것과 같음
강조 해야 할 중요한 사항:
- 이 RAM 장치에 얼마나 많은 레지스터가 있든, 그리고 수백만 개의 레지스터가 있든 상관없이 특정 시점에는 하나의 레지스터만 선택된다.
- 즉, 다른 모든 레지스터는 아무런 역할을 하지 않는다. 따라서 특정 시점에 어느 레지스터가 작동하고자 하는 레지스터인지 명시 해야 함
- 그렇기 때문에 레지스터의 주소를 선택 해야 한다.
**💡 n개의 레지스터 중 하나를 선택해야 한다면, 코드를 생성하기 위해 몇 비트가 필요할까?

예를 들어, 레지스터가 8개라고 가정 해보자.
- k (width of address input): k = log2 n
- 따라서 8의 로그는 3 → k = 3
- 0번 레지스터는 000으로 표시된다.
- 7번 레지스터는 111로 표시된다.
  - 따라서 이 다이어그램에서 k라고 부르는 주소 입력의 길이는 이 특정 RAM 장치의 레지스터 수인 n의 로그와 같다**
이것이 순차적 칩이라는 것을 기억 할 것, 클럭 입력에 따라 달라진다.
Quiz
- 레지스터의 너비와 레지스터의 주소의 차이는 무엇인가요?
  1. 둘은 같은 것이다.
  2. 주소는 모든 레지스터에서 동일 하지만, 너비는 각 레지스터마다 고유하다.
  3. 너비는 단일 레지스터가 저장하는 데이터의 양이고, 주소는 더 큰 칩 내에서 레지스터의 위치이다.
  4. 레지스터의 주소는 너비의 log 값이다.

RAM은 직접 접근 메모리 장치로, n개의 레지스터 칩으로 구성된다. RAM은 각 레지스터마다 특정 주소(0에서 n-1 까지)를 할당 하고, 이 주소를 이용해 레지스터를 선택하고 읽기 / 쓰기 작업을 한다.

임의로 선택된 메모리 레지스터에 접근하는 시간이 즉각적이고** RAM의 크기나 레지스터의 주소와 무관** 하다는 점이다.

Unit3-4. Counters

Where counters come to play

The computer must keep track of which instruction should be fetched and executed next
This control mechanism can be realized by a Program Counter
The PC contains the address of the instruction that will be fetched and excuted next
Three possible control settings:
- Reset: fetch the first instruction → PC = 0
- Next: fetch the next instruction → PC++
- Goto: fetch instruction n → PC = n

So, what is counter?

A chip that realizes this abstraction

**💡 Counter

컴퓨터는 다음에 어떤 명령을 가져와 실행해야 하는지 추적해야 한다.
이 제어 메커니즘은 프로그램 카운터로 구현할 수 있다.
PC에는 다음에 가져와서 실행할 명령어의 주소가 들어 있다.

👉 이런 추상 적인 시스템을 실행 하는 칩을 카운터라고 한다.**

카운터는 매 시간 단위마다 1씩 증가시키는 칩으로, inc와 reset 제어 비트만 제외 하면 레지스터와 인터페이스는 같다.

Counter abstraction

Untitled

16-bit Counter

Input: In[16], load, inc, reset
- reset == 1
  - 출력 값을 0으로 설정
- load == 1
  - 출력 값을 입력 받은 값으로 설정한다
- inc == 1
  - 출력 값을 1 증가시킨다.
- 그 외 입력이 없을 땐 카운터는 아무 것도 변화시키지 않는다.

**💡 resetting:

counter = 0

incrementing:

counter++

loading:

setting counter = 0

else:

counter does not change**
Quiz

PC - HDL

Untitled

위에 프로그램 카운터의 역할에 대해 설명 했듯이, 과연 그 역할에 맞게 수행 하는지 HDL Simulator로 증명 해보자.

가설

프로그램 카운터에 어떤 입력도 없다면 아무런 변화가 없다
load에 비트를 입력 하면 프로그램 카운터에 입력 받은 값을 설정한다
inc에 비트를 입력 하면 프로그램 카운터 값이 1 증가한다
reset에 비트를 입력 하면 값을 초기화한다

프로그램 카운터는 어떠한 입력을 받지 않으면 아무런 변화가 없다

Untitled

클록 주기를 변화 시켰을 때 PC의 값은 0이며, 출력 값도 0인 것을 확인 할 수 있다.

load가 1일 때 입력 받은 값을 프로그램 카운터에 저장한다

Untitled

Tik: 8 → 8+

주기 사이의 변화를 지켜 보면, 틱을 실행 했을 때 프로그램 카운터는 입력 받은 값을 담고있음

Tok: 8+ → 9

주기가 끝나는 시점에 출력 값을 현재 프로그램 카운터의 값으로 설정 하는 것을 확인 할 수 있음

inc가 1일 때 프로그램 카운터의 저장 된 값을 1 증가 시킨다

Untitled

클록 주기가 끝난 시점에서 값을 확인 해 보면 1이 증가 되지 않았다. 현재 입력 받은 설정 값을 보면 이해 할 수 있다. increment를 통해 1을 증가 시켰다. 하지만, load로 입력 받은 값을 다시 호출 하고 있기 때문에 이 값은 17에 머무를 수 밖에 없다.

옵션을 변경 하고 가설을 증명 해보자.

이로써, 다음 주기 끝에 값을 추적 해 봐도 1이 더 증가하는 것을 볼 수 있다.

reset이 1일 때, 프로그램 카운터 값은 0으로 초기화된다

아까와 비슷하게 increment에 비트가 입력 되고 있지만 알다시피 리셋은 모든 것을 초기화 시키기 때문에 값은 0을 담고 있는 것을 볼 수 있다.

이렇게, 프로그램 카운터가 하는 역할을 직접 구현 해 보며 증명 하는 시간을 갖게 되어 클록 주기가 빠르면 이 값의 변화가 얼마나 빠를지 예상이 안될 정도로 컴퓨터구조는 정말 천재들의 놀이터인 것 같다.