The computer system, abstraction and levels of transformation
The seven levels that take a problem down to electrons, the idea of abstraction, and the difference between ISA and microarchitecture. A map of the rest of the course, and short-answer questions on the midterm.
This course answers the question “how does a computer really work?” from the bottom up. It starts from the transistor, goes up to gates, circuits, memory, the processor, machine code, assembly and finally C. The first week is the map of this journey. On the midterm, this part usually brings short-answer questions: list the levels, what is the ISA, why abstraction exists. Points earned with little effort.
Five things to remember from this week:
- A computer is not smart, it is fast. It does everything with very simple steps.
- Abstraction is hiding detail. All of computer engineering is built on it.
- There are seven levels of transformation: from Problem to Devices. Memorize the order.
- The ISA is the contract where software and hardware meet.
- With enough time and memory, all computers can compute the same things.
Abstraction
When you drive a car, you do not think about the pistons inside the engine. You press the gas pedal and the car speeds up. The pedal is an interface that hides the complexity of the engine from you. This is called abstraction: hiding the detail that is not useful to you at the moment and seeing only the part you will use.
In a computer, each level abstracts the one below it:
- When you write C, you do not know which register is used.
- When you write assembly, you do not know the gates inside the add instruction.
- When you draw an adder circuit, you do not know the electrons inside the transistor.
Abstraction makes you faster. But it has a cost: when something does not work as expected, you need to be able to go below the abstraction. The textbook calls this deconstructing the abstraction. To understand why a program is slow you need to know about memory access, and to understand an overflow error you need to know about bits. This course teaches you those lower levels.
TIP · The exam sentence. “Abstraction is a technique for hiding detail so that we can deal with a complex system at a higher level.” It is enough that you can write a similar sentence in your own words.
Hardware and software are not separate
In the old view, “hardware people” and “software people” were separate. This course argues the opposite: a good programmer knows how the hardware underneath works, and a good hardware designer thinks about the software that will run on it. For example, someone who knows how an array is laid out in memory writes code that uses the cache better.
What a computer can do: the universal computing device
In the 1930s Alan Turing proposed an abstract machine to define a computation: the Turing machine. Each Turing machine does a single job (for example addition). Turing also defined the universal Turing machine: this machine can simulate any Turing machine using the description given to it.
Today’s computers are equivalent to the universal Turing machine. The consequence:
| Statement | True? |
|---|---|
| A cheap laptop can compute everything a supercomputer can compute. | Yes, with enough time and memory. |
| The two run at the same speed. | No, the difference is in speed and memory. |
| A new job requires buying a new computer. | No, writing a new program is enough. |
That is why a computer is called a universal computing device. A calculator is not like that: it only does the jobs put in at the factory.
The seven levels of transformation
To make a computer solve a problem, you turn it step by step into the movement of electrons. Each step is a level.
| # | Level | What is done? | Example |
|---|---|---|---|
| 1 | Problem | Described in natural language | “Find the class grade average” |
| 2 | Algorithm | A step-by-step, precise method | Add up the grades, divide by the count |
| 3 | Program (language) | Written in a programming language | C code |
| 4 | ISA | The machine’s instruction set | LC-3 ADD, LD, BR |
| 5 | Microarchitecture | The hardware design of the ISA | Data path, control unit |
| 6 | Logic circuits | Gates and circuits | Adder, mux, register |
| 7 | Devices | Transistors | CMOS |
You can remember the order with a made-up sentence such as “People Always Prefer Interesting Movies Late Daily”: Problem, Algorithm, Program, ISA, Microarchitecture, Logic circuits, Devices.
Problem → Algorithm
The problem is described in natural language, and natural language is ambiguous. In the phrase “old men and women”, are the women old too? A computer cannot resolve this ambiguity. That is why the first transformation is turning the problem into an algorithm. An algorithm must have three properties:
- Definiteness: every step is precisely defined.
- Effective computability: every step can really be done by a computer. “Find the largest prime number” cannot be done, because there is no such number.
- Finiteness: it ends in a finite number of steps.
There can be many algorithms for the same problem. One may be faster, another may use less memory.
Algorithm → Program
The algorithm is written in a programming language. Programming languages contain no ambiguity; a computer can parse them mechanically. There are two kinds of language:
- High-level: C, Java, Python. Independent of the machine.
- Low-level: assembly. Tied to a specific ISA, each line is generally a single machine instruction.
Program → ISA
The ISA (Instruction Set Architecture) is the contract between software and hardware. It defines everything that the programmer (or the compiler) can give to the computer:
- Which instructions exist and what their codes are (opcode),
- What kinds of data the instructions work with (data types: 2’s complement integers, characters, floating point),
- How the location of the operand is found (addressing modes),
- How many registers there are, how memory is addressed.
The compiler translates a C program into the ISA. The assembler translates assembly into machine code. Examples: x86 (Intel/AMD), ARM (phones), LC-3 (the teaching computer of this course).
ISA → Microarchitecture
The microarchitecture is how the ISA is realized in hardware. The ISA says “what to do”, the microarchitecture says “how to do it”. There are many very different processors that run the same ISA: one is cheap and slow, another is expensive and fast. All of them run the same machine code.
An analogy: the interface for driving a car (steering wheel, pedals, gears) is the ISA. How many cylinders the engine has is the microarchitecture. As a driver, if the interface is the same, you can drive any car.
Microarchitecture → Logic circuits → Devices
Every part of the microarchitecture (adder, register, memory) is built from logic circuits. The circuits are made of transistors. In this course we will see CMOS transistors (week 3).
Roadmap of this course
| Week | Level | Topic |
|---|---|---|
| 2 | Data | Bits, 2’s complement, IEEE 754, ASCII |
| 3-4 | Devices, Logic circuits | Transistor, gate, combinational circuit, latch, memory, FSM |
| 5-6 | Microarchitecture | The von Neumann model, the instruction cycle, I/O |
| 7-8 | ISA | LC-3 instructions and their encoding |
| 10 | Program (low-level) | LC-3 assembly |
| 11-14 | Program (high-level) | C |
So during the semester you climb the levels from the bottom up.
Worked examples
Example 1. An ISA has 100 different instructions. How many bits must the opcode field have at least?
k bits → 2^k different codes
2^6 = 64 < 100 not enough
2^7 = 128 ≥ 100 enough
answer: 7 bitsExample 2. Place the following at their levels.
| Statement | Level |
|---|---|
x = a + b; | Program (language) |
ADD R1, R2, R3 | ISA (assembly notation) |
| A 4-bit ripple-carry adder | Logic circuits |
| “First add, then divide by 2” | Algorithm |
| An n-type MOS transistor | Devices |
| How many clock cycles an instruction takes to finish | Microarchitecture |
Example 3. “A company redesigned its processor. Old programs run without being recompiled.” Which level changed? Answer: the microarchitecture. Because the ISA stayed the same, the old machine code keeps working.
Common mistakes
| Wrong idea | The truth |
|---|---|
| ISA and microarchitecture are the same thing | The ISA is the interface, the microarchitecture is its realization |
| The compiler translates machine code into hardware | The compiler translates a high-level language into the ISA |
| A fast computer can solve more problems | What they can compute is the same, there is only a speed difference |
| Level order: Program, Algorithm, … | First Algorithm, then Program |
| Logic circuits is the lowest level | At the very bottom is Devices (transistors) |
| An algorithm may run forever | Finiteness: it must end in a finite number of steps |
| Programming in natural language is possible | Natural language is ambiguous, the machine needs a single meaning |
Test yourself
Exam-style questions. Solve them on paper first, then reveal the answer.
List the levels of transformation from the problem statement down to the physical devices, in order.
Show answer
From top to bottom: the problem is described in natural language, turned into an algorithm, written in a programming language, the compiler translates it into the ISA, the ISA is realized by a microarchitecture, the microarchitecture is made of logic circuits, and the circuits are made of transistors (devices).
What is abstraction, and why is it useful to a computer engineer?
Show answer
Abstraction means hiding the detail you are not interested in at the moment and seeing only the interface that is useful to you. For example, when you use an adder circuit you do not think about the transistors inside. It gives efficiency. But when something breaks, you need to be able to go below the abstraction (deconstruct).
Name the three properties every algorithm must have.
Show answer
Definiteness: every step is precise and contains no ambiguity. Effective computability: every step can really be done by a computer. Finiteness: the algorithm ends in a finite number of steps.
Why can't a computer be programmed directly in a natural language such as English or Turkish?
Show answer
In natural language the same sentence can have more than one meaning. A computer has to do every step with a single meaning. That is why programming languages, which have no ambiguity and can be mechanically parsed, are used.
Which level is described as the interface between software and hardware, and what does it specify?
Show answer
The ISA (Instruction Set Architecture) is the complete list of commands a program can give to the computer. It defines the opcodes, the operand types (data types), the addressing modes, and the layout of registers and memory. Software is written down to the ISA; hardware realizes the ISA.
Can one ISA have more than one microarchitecture? Give the reason.
Show answer
The ISA says what to do, the microarchitecture says how to do it. There are many very different processors that run the same x86 instruction set: their speed, cost and power consumption differ, but they run the same program. The relationship is one-to-many: one ISA, many microarchitectures.
What is the difference between a compiler and an assembler?
Show answer
A compiler translates a high-level language like C into the instructions of the target ISA. An assembler translates the assembly language, which is already almost one-to-one with machine instructions, into 0s and 1s (machine code). In assembly each line is mostly a single machine instruction.
An ISA has 40 different instructions. What is the minimum number of bits needed for the opcode field?
Show answer
With bits you can write different opcodes. , so at least 6 bits are needed.
Every LC-3 instruction is 16 bits and the opcode is the top 4 bits. How many distinct opcodes can the LC-3 have?
Show answer
A 4-bit field can write different values. In the LC-3, 15 of these 16 values are used and one (1101) is reserved.
True or false: a small, cheap computer can compute everything a supercomputer can compute, given enough time and memory.
Show answer
This is a consequence of computers being universal computing devices. According to Turing, a universal Turing machine can simulate every Turing machine. The difference is only in speed and amount of memory, not in what it can compute.
A program runs correctly on one processor but you want it to run faster. Changing which level keeps the program binary unchanged: the ISA or the microarchitecture?
Show answer
Machine code is written for the ISA. As long as the ISA stays the same, the program runs without being recompiled. A faster microarchitecture (a better pipeline, a bigger cache) runs the same binary faster. If you change the ISA, you have to recompile the program.
Which level of transformation is the first one that a computer can execute directly, without further translation?
Show answer
A C program does not run without being compiled, an assembly program does not run without being assembled. Machine code at the ISA level is the form that the hardware directly fetches and executes. The levels below it (microarchitecture, circuits) are the hardware that runs this code.
Verification: The conceptual answers were compared with the concepts of Patt & Patel chapters 1-2; the numeric questions (number of opcode bits, number of addresses) were computed with node (verify/SEN2201/01.mjs).