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.

Unit3-1. Sequential Logic

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

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

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

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

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

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

Combinational Chip

Sequential Chip

The Clock

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

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

Physical Time

• 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.

The Clocked Data Flip Flop

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

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

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

시간의 문제

예시)

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

지연 발생

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

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

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

이산적인 시간의 개념

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

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

Sequential Logic Implementation

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

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

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

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

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

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

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

• Load에 의해 값이 결정되기 때문에 Multiplexor 을 이용 하면 파이프라인을 연결 할 수 있다

• Quiz

  

  • DFF는 항상 “in” 비트를 저장하는 반면, Bit는 “로드”가 1로 설정된 경우에만 저장한다
  • DFF는 일시적으로 정보를 저장할 수 있는 반면, 비트는 여러 주기에 걸쳐 정보를 저장할 수 있음

t = 1

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

t = 2

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

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

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

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

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

Register / read logic

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

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

Register / write logic

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

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

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

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

RAM unit

• RAM abstraction:

  • 메모리에 대해 생각하는 방식은 메모리를 주소 지정이 가능한 레지스터의 시퀀스로 생각하는 것
  • 즉, n개의 레지스터로 구성된 RAM 장치의 경우 0 부터 n-1을 뺀 범위의 주소가 있는 것과 같음

• 강조 해야 할 중요한 사항:

  • 이 RAM 장치에 얼마나 많은 레지스터가 있든, 그리고 수백만 개의 레지스터가 있든 상관없이 특정 시점에는 하나의 레지스터만 선택된다.
  • 즉, 다른 모든 레지스터는 아무런 역할을 하지 않는다. 따라서 특정 시점에 어느 레지스터가 작동하고자 하는 레지스터인지 명시 해야 함
  • 그렇기 때문에 레지스터의 주소를 선택 해야 한다.

  이것이 순차적 칩이라는 것을 기억 할 것, 클럭 입력에 따라 달라진다.

• 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

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

Counter abstraction

16-bit Counter

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

• Quiz

  

PC - HDL

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

가설

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

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

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

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

Tik: 8 → 8+

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

Tok: 8+ → 9

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

  

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

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

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

• Tik

  

• Tok

  

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

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

• Tik

  

• Tok

  

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

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