Learn from MVP: Minimal Instruction Set CPU

Introduction

The 6502 CPU program has been a great inspiration for understanding the foundations of computer science. It’s fascinating how basic boolean functions and transistors can form such a complex and beautiful system. However, even the 6502 CPU, with its 150+ instructions, can be overwhelming for those trying to understand the fundamental principles of computing.

The Importance of Minimal Viable Products

When learning complex systems, it’s crucial to start with a minimal viable product (MVP) - understanding the most essential components that make a program run. This approach led me to explore foundational theories and historical concepts in computing.

Turing’s Influence

Alan Turing’s computational theory provides a perfect starting point. His concept of a universal computing machine demonstrates that any computable problem can be solved using a simple machine with:

• An infinite length tape
• A read/write head
• Basic operations (read, write, logic, and arithmetic)
• Position control

While we can’t implement an infinite tape, we can create a system that operates in a loop, simulating this fundamental concept.

Extension reading on Turing’s theory:

We have to compute the number, then the number should be computable. It seems the word “computable” is vague, so he gave a definition: A real number is computable if a mechanical procedure can print its digits one-by-one in finite time per digit. Replace “print a digit” with “return a value” and you have a computable (partial) function.

The probe can be seen as a finite-states machine, which react only on limited states to do some “computation”, which can be defined by limited and concrete steps.

Encode a TM’s state table as an integer (its ⟨code⟩).

• A Universal TM U takes (⟨M⟩, x) and simulates M running on input x. Legacy.
• “Program = data” → the von Neumann architecture, data can be control message(finite state) or information;

Figure 1: A simplified representation of a Turing Machine

Minimal Instruction Set Design

Based on these principles, a minimal CPU needs only four types of instructions:

1. JMP (Jump) - For program flow control
2. Logic - For basic boolean operations
3. ADD/SUB - For arithmetic operations (multiplication and division can be simulated)
4. HALT - To stop program execution

CPU Specification

After careful consideration and consultation, here’s the design for our minimal CPU:

Memory and Registers

• RAM: 64KB (65536 bytes) with 16-bit addressing
• Registers: 4 general-purpose 8-bit registers (R0-R3)
• Program Counter (PC): 16-bit register for instruction fetching

Instruction Set

CPU Operation Cycle

The CPU follows a simple fetch-execute cycle:

1. Fetch instruction from memory at PC
2. Decode instruction
3. Execute instruction
4. Update PC
5. Repeat until HALT

Look how cpu borrow the concept from Turing Machine:

This minimal setup provides the foundation for basic logic and arithmetic operations, which can be extended to handle more complex tasks.

Implementation

CPU Header (cpu.h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#pragma once
#include <iostream>
#include <vector>
#include <cstdint>
#include <iomanip>

class MinimalCPU {
public:
    uint8_t RAM[65536]{};
    uint8_t R[4] = {0};  // R0 ~ R3
    uint16_t PC = 0;
    bool halted = false;

    // Load program into memory
    void loadProgram(const std::vector<uint8_t>& program, uint16_t start = 0) {
        for (size_t i = 0; i < program.size(); ++i) {
            RAM[start + i] = program[i];
        }
        PC = start;
    }

    // Main CPU execution loop
    void run() {
        while (!halted) {
            uint8_t op = fetch();
            switch (op) {
                case 0x00: // HALT
                    halted = true;
                    break;
                case 0x01: { // LOAD Rd, addr
                    uint8_t rd = fetch();
                    uint16_t addr = (fetch() << 8) | fetch();
                    R[rd] = RAM[addr];
                    break;
                }
                case 0x02: { // STORE addr, Rs
                    uint16_t addr = (fetch() << 8) | fetch();
                    uint8_t rs = fetch();
                    RAM[addr] = R[rs];

                    // Special handling for output port
                    if (addr == 0xFF00) {
                        std::cout << "OUTPUT: " << static_cast<char>(RAM[addr]) << "\n";
                    }
                    break;
                }
                case 0x03: { // ADD Rd, Rs
                    uint8_t rd = fetch();
                    uint8_t rs = fetch();
                    R[rd] += R[rs];
                    break;
                }
                case 0x04: { // SUB Rd, Rs
                    uint8_t rd = fetch();
                    uint8_t rs = fetch();
                    R[rd] -= R[rs];
                    break;
                }
                case 0x05: { // JNZ Rd, addr
                    uint8_t rd = fetch();
                    uint16_t addr = (fetch() << 8) | fetch();
                    if (R[rd] != 0) {
                        PC = addr;
                    }
                    break;
                }
                default:
                    std::cerr << "Unknown opcode: " << std::hex << static_cast<int>(op) << "\n";
                    halted = true;
                    break;
            }
        }
    }

private:
    uint8_t fetch() {
        return RAM[PC++];
    }
};

Test Program (main.cpp)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include "cpu.h"
#include <iostream>

int main() {
    MinimalCPU cpu;

    // Test program: Load 'A' from memory and output it
    std::vector<uint8_t> program = {
        0x01, 0x00, 0x00, 0xFA,   // LOAD R0, 0x00FA
        0x02, 0xFF, 0x00, 0x00,   // STORE 0xFF00, R0
        0x00                      // HALT
    };

    cpu.RAM[0x00FA] = 'A';  // Set test data
    cpu.loadProgram(program);
    cpu.run();
    
    return 0;
}

Conclusion

This minimal CPU implementation demonstrates the fundamental principles of computing while remaining accessible and understandable. It provides a foundation that can be extended to create more complex systems, making it an excellent learning tool for understanding computer architecture.

GitHub Repository

View the complete implementation on GitHub