Computer Architecture

References

• Basic Computer Architecture, Version 3.03, Smruti R. Sarangi

Introduction

Introduction to Computer Architecture

Computer architecture is the study of computers. Computer architecture from the point of view of software is often referred to as architecture in literature. Computer architecture from the point of view of hardware is often referred to as organization in literature.

• Architecture - the view of a computer presented to a software designer
• Organization - the actual implementation of a computer in hardware

A computer is a general purpose device that can be programmed to process information and yield meaningful results.

The computer takes as an input a program, and in response performs a set of operations on the information store. At the end, it yields meaningful results. A typical program contains a set of instructions that tell the computer regarding the operations that need to be performed on the information store. The information store typically contains numbers and pieces of text that the program can use.

Modern day computers are made of silicon based transistors and copper wires that connect them; computers don't have to be built this way:

• Researchers are now looking at building computers with electrons (quantum computers), photons (optical computers), and even DNA

There are three main parts of a typical desktop computer:

1. CPU (Central Processing Unit)
2. 1. Also referred to as the processor or simply machine. The CPU is the main part of the computer that takes a program as input, and executes it. It is the brain of the computer.
2. Main Memory
3. 1. The main memory is used to store data that a program might need during its execution (information store). There is some limited storage on the processor itself. When we turn off the power, the processor and the main memory will lose all their data.
3. Hard Disk
4. 1. Represents permanent storage. We do not expect to lose our data when we shut down the system.

An instruction is defined as a basic command that can be given to a computer. A compiler takes some high level language instructions and translates it to a series of basic instructions for a computer. A compiler effectively removes the burden of creating machine (computer) readable code from the programmer. The compiler takes the high level program as input, and produces a program containing machine instructions. This program is typically called an executable or binary.

The number of basic instructions/rudimentary commands that a processor can support have to be finite. This set of instructions is typically called the instruction set. Some examples of basic instructions are: add, subtract, multiply, logical or, and logical not. Each instruction needs to work on a set of variables and constants, and finally save the result in a variable.

• Instruction Set Architecture
• • The semantics of all the instructions supported by a processor is known as the instruction set architecture (ISA). This includes the semantics of the instructions themselves, along with their operands, and interfaces with peripheral devices.

The Instruction set architecture is the way that software perceives hardware.

Instruction Set Design

• Complete - The ISA should be able to implement all user programs
• Concise - Limited Size of the Instruction Set
• • Most instruction sets have somewhere between 64 to 1000 instructions
• Generic - Instructions should Capture the Common Case
• Simple - Instructions should be simple
• • A reduced instruction set computer (RISC) implements simple instructions that have a simple and regular structure. The number of instructions is typically a small number (64 to 128)
  • A complex instruction set computer (CISC) implements complex instructions that are highly irregular, take multiple operands, and implement complex functionalities. Secondly, the number of instructions is large (typically 500+)

An ISA needs to be complete, concise, generic, and simple. It is necessary to be complete, whereas the rest of the properties are desirable (and sometimes debatable). A machine that can execute any program is known as a universal machine.

Alan Turing was the first to propose a universal machine that was extremely simple and powerful. A Turing machine contains an infinite tape that is an array of cells. Each cell can contain a symbol from a finite alphabet. There is a small piece of storage to save the current state among a finite set of states. This storage element is called a state register. The operation of the Turing machine is very simple. In each step, the tape head reads the symbol in the current cell, its current state from the state register, and looks up a table that contains the set of actions for each combination of symbol and state. This dedicated table is called a transition function table or action table. Each entry in this table specifies three things - whether to move the tape head one step to the left or right, the next state, and the symbol that should be written in the current cell.

Church-Turing thesis: Any real-world computation can be translated into an equivalent computation involving a Turing machine. Any computing system that is equivalent to a Turing machine is said to be Turing complete.

Stored-program concept: A program is stored in memory and instructions are treated as regular memory values.

Design of Practical Machines

1. Harvard Architecture

2. von Neumann Architecture

The stored program concept tremendously simplifies the design of a computer. Since memory data and instructions are conceptually treated the same way, we can have one unified processing system and memory system that treats instructions and data the same way. From the point of view of the CPU, the program counter points to a generic memory location whose contents will be interpreted as that of an encoded instruction. It is easy to store, modify, and transmit programs. Programs can also dynamically change their behavior during runtime by modifying themselves and even other programs.

Registers are named storage locations that can be accessed randomly and all instructions use registers as their operands. There are load and store instructions to transfer values between memory and registers. A stack is a standard data structure that obeys the semantics - last in, first out. A stack supports two operations - push and pop. Push pushes an element to the top of the stack. Pop removes an element from the top of the stack.

Todays computers are made of transistors. A transistor can be visualized as a basic switch that has two states - on and off. If the switch is on, then it represents 1, otherwise it represents 0. Every single entity inclusive of numbers, text, instructions, programs, and complex software needs to be represented using a sequence of 0s and 1s. A variable/value that can either be 0 or 1 is known as a bit. A set of 8 bits is known as a byte. Typically, a sequence of 4 bytes is known as a word. Assembly language is a textual representation of an ISA. It is specific to the ISA.

Architecture: Software Interface

The Language of Bits

We can divide the set of operations that can be done with buts into two major types - logical and arithmetic. Representation of numbers or text using a sequence of 0s and 1s is known as a binary representation. Boolean Variable (George Bool) - a variable that can take only two values - 0 or 1. Boolean algebra - an algebraic system consisting of Boolean variables and some special operators defined on them. A simple Boolean variable can take two values - 0 or 1.

Any Boolean Operator can be represented by the means of a truth table, which lists the outputs of the operator for all possible combinations of inputs.

In literature, + is used to mean the logical OR and . is used to mean the logical AND. The operator is used for the logical XOR.

A logic gate is a device that implements a Boolean function.

Let us consider a Boolean function with arguments:

• A minterm is an AND function on all Boolean variables, where each variable appears only once (either in its original form or in its complemented form). A minterm corresponds to one line in the truth table, whose result is 1.
• Canonical Representation - It is a Boolean formula, which is equivalent to the function . It computes an OR operation of a set of minterms.

A Karnaugh Map is a rectangular grid of cells, where each cell represents one minterm.

A number system based on Indian numerals that uses a base equal to 2, is known as a binary number system. A number system based on Indian numerals that uses a base equal to 10 is known as a decimal number system.

• MSB (Most Significant Bit) - The leftmost bit of a binary number.
• LSB (Least Significant Bit) - The rightmost bit of a binary number.

overflow - An overflow occurs when a number is too large to be represented in a given number system. underflow - An underflow occurs when a number is too small to be represented in a given number system. The point of discontinuity in a number circle is called the break point.

Floating point numbers are numbers that contain a decimal point. A fixed point number is a number that has a fixed number of digits after the decimal point. A string data type is a sequence of characters in a given language such as English.

Assembly Language

Assembly language can be broadly defined as a textual representation of machine instructions.[...] An assembly language is specific to an ISA and compiler framework; hence, there are many flavors of assembly languages.

• A high level programming language such as C or Java uses fairly complex constructs and statements. Each statement in these languages typically corresponds to a multitude of basic machine instructions. These languages are typically independent of the processor's ISA.
• A compiler is an executable program that converts a program written in a high level language to a sequence of machine instructions that are encoded using a sequence of zeros and ones.

A cross-compiler is a program that runs on machine A, and generates machine code for machine B. It is possible that B has a different ISA.

• A low level programming language uses simple statements that correspond to typically just one machine instruction. These languages are specific to the ISA.
• The term assembly language refers to a family of low level programming languages that are specific to each ISA. They have a generic structure that consists of a sequence of assembly statements. Typically, each assembly statement has two parts:

1. 1. an instruction code that is a mnemonic for a basic machine instruction
   2. a list of operands

An assembler is an executable program that converts an assembly program into machine code. The core processors of high performance 3D games need to be optimized for speed as much as possible. Most compilers fail to produce code that runs fast enough. It becomes necessary for programmers to manually write sequence of machine instructions.

The role of hardware designers is to design processors that can implement all the instructions in the ISA. Their main aim is to design an efficient processor that is optimal with regard to area, power efficiency, and design complexity.

The Basics of Assembly Language

The Machine Model

The programs is stored in a part of the main memory. The Central Processing Unit (CPU) reads out the program instruction by instruction, and executes the instructions appropriately. The program counter keeps track of the memory address of the instruction that a CPU is executing. Most instructions are expected to get their input operands from registers. Every CPU has a fixed number of registers (typically < 64). A large number of instructions can also get their operands from the CPU directly. It is the job of the CPU to co-ordinate the transfers to and from the main memory and registers. The CPU also needs to perform all the arithmetic/logical calculations and liaise with external input/output devices.

Most flavors of assembly language assume this abstract machine model for a majority of their statements. Their are a fair number of assembly instructions that are cognizant of the internals of the processor. These instructions typically modify the behavior of the processor by changing the behavior of some key internal algorithms; they modify built-in parameters such as power management settings, or read/write some internal data.

Each machine has a set of registers that are visible to the assembly programmer. In most ISAs, a return address register is used for function calls. The return address is the memory address that the program needs to return to after executing the function.

View of Memory

The memory can be thought of as one large array of bytes. Each byte is a unique address, which is essentially its location in the array. In a von Neumann machine, we assume that the program is stored in memory as a sequence of bytes, and the program counter points to the next instruction that is going to be executed.

The difference between little endian and big endian representations of multibyte data type in memory is whether they store the most significant byte in location 0 (big endian) or least significant byte in location 0 (little endian).

• row major - in this representation, an array is saved row wise in memory
• column major - in this representation, an array is stored column wise in memory

An assembly file is a regular text file, and it has a .s suffix. To generate the assembly file for test.c:

$ gcc -S test.c

A bare bones assembly language statement specifies an assembly instruction and has two parts - the instruction and its list of operands. The instruction is a textual identifier of the actual machine instruction. The list of operands contains the value or location of each operand. The value of an operand is a numeric constant. It is also known as the immediate value. The operand locations can either be register locations or memory locations.

• In computer architecture, a constant value specified in an instruction is also known as an immediate.

add r3, r1, r2

In this ARM assembly statement, the add instruction is specifying the fact that we wish to add two numbers and save the result in some pre-specified location. The format of the command is <instruction> <destination register> <operand register 1> <operand register 2>. The name of the instruction is add, and the destination register is r3, the operand registers are r1 and r2.

An assembly statement generally consists of three fields: a label (identifier of the instruction), the key (an assembler instruction or a directive to the assembler), and a comment. All three of these fields are optional. However, an assembly statement needs to have at least one of these fields. A label in an assembly file uniquely identifies a given point or data item in the assembly program.

label1: add r1, r2, r3 @ This is a comment

Types of Instructions

1. Data Processing Instructions: Data processing instructions are typically arithmetic instructions such as add, subtract, and multiply, or logical instructions that compute bitwise or, and exclusive or. Comparison instructions also belong this family.
2. Data Transfer Instructions: These instructions transfer values between two locations. A location can be a register or a memory address.
3. Branch Instructions: Branch instructions help the processor's control unit to jump to different parts of the program based on the values of operands. They are useful in implementing for loops and if-then-else statements.
4. Exception Generating Instructions: These specialized instructions help transfer control from a user level program to the operating system.

If an instruction requires n operands (including source and destination), then we say that it is an n-address format instruction.

Types of Operands

The method of specifying and accessing an operand in an assembly statement is known as the addressing mode. The simplest way of specifying an operand is by embedding its value in the instruction. Most assembly languages allow the user to specify the values of integer constants as an operand. This addressing mode is known as the immediate addressing mode. This method is very useful for initializing registers or memory locations or for performing arithmetic operations.

Register Transfer Notation: = we are transferring the contents of r2 (source register) to r1 (destination register). = the processor hardware fetches the memory address in , accesses the location, fetches the contents of the memory location, and saves the data item in .

The memory address specified by an operand is known as the effective memory address.

ARM stands for Advanced RISC Machines. It is an iconic company based out of Cambridge, UK. Most ISAs share simple instructions such as add, subtract, multiply, shifts, and load/store instructions. However, beyond this simple set, they may use many more specialized instructions.

SimpleRisc assumes that we have 16 registers numbered . The first 14 registers are general purpose registers, and can be used for any purpose within the program. Register is known as the stack pointer. It is referred to as . Register 15 is known as the return address register, and it will be referred to as . Each register is 32 bits wide. We assume a special internal register called flags, which is not visible to the programmer. It contains two fields: (qual) and (greater than). is set to 1 if the result of a comparison is equality, and is set to 1 if a comparison concludes that the first operand is greater than the second operand. Each instruction is encoded into a 32-bit value, and it requires 4 bytes of storage in memory.

The instruction is a 2-address format instruction that can transfer values from one register to another, or can load a register with a constant.

• Register Transfer Instruction: transfer values form one register to another
• Arithmetic Instructions: Self explanatory
• Logical Instruction: Self explanatory
• Shift Instructions: Note that logical shift means that it will fill the left positions with zeros
• Data transfer instructions: Load instructions loads values from memory into registers, and the store instruction saves values in registers to memory locations
• Unconditional Brach Instruction: Makes the program counter jump to the address corresponding to a label in code.
• Conditional Branch Instruction: make the program counter jump to the label specified if a condition is met

Functions

One of the most advanced features in high-level programming languages that makes their structure extremely modular is functions. Return Address: It is the address of the instruction that a process needs to branch to after executing a function. A function is essentially a block of assembly code. Calling a function is essentially making the PC point to the start of this block of code. Calling a function is as simple as branching to the label at the beginning of a function. A generic function processes the arguments, reads and writes values from memory and I/O devices if required, and then returns the result. The notion of saving registers in memory and later restoring them is known as register spilling.

A typical C or Java program starts with the main function. This function then calls other functions, which might in turn call other functions, and finally the execution terminates when the main function exits. Each function defines a set of local variables and performs a computation on these variables and the function arguments. It might also call other functions. Finally, the function returns a values and rarely a set of values. After the function terminates, the space occupied by the variables and arguments that were saved in memory need to be reclaimed. It is best to save all these pieces of information contiguously in a single region of memory. This is known as the activation block of the function.

A last-in-first-out (LIFO) structure is traditionally known as a stack in computer science. The memory region dedicated to saving activation blocks is known as the stack. Traditionally, the stack has been considered to be downward growing (growing towards smaller memory addresses). This means that the activation block of the main function starts at a very high location and new activation blocks are added just below (toward lower addresses) existing activation blocks.

• The stack if a memory region that saves all activation blocks in a program
• • It is traditionally considered to be downward growing
  • Before calling a function, we need to push its activation block to the stack
  • When a function finishes execution, we need to pop its activation block off the stack
• The stack pointer register maintains a pointer to the top of the stack. This pointer is called the stack pointer.

Encoding the SimpleRISC Instruction Set

An opcode is a unique identifier for each machine instruction.

Skipping the chapters on ARM / x86 / RISCV - I don't want to go too in depth on specific languages now.

Organization: Processor Design

Logic Gates, Registers, and Memories

Silicon is the 14th element in the periodic table. It has four valence electrons and belongs to the same group as carbon and germanium. It is less reactive than both. Over 90% of the Earth's crust consist of silicon based minerals. Silicon has electrical properties between a conductor and insulator - making it a semiconductor. It is possible to slightly modify its properties by adding some impurities in a controlled manner. This process is called doping.

• An n-type semiconductor has group V impurities such as Phosphorus and Arsenic. Its primary charge carriers are electrons.
• A p-type semiconductor has group III impurities such as boron and gallium. Its primary charge carriers are holes. Holes have an effective positive charge.
• A p-n junction is formed when we place a p-type and n-type semiconductor side by side.

At steady state, the drift and diffusion currents balance each other, and thus there is effectively no current flow across the junction. When we connect the p side to the positive terminal of a battery and n-type to a negative terminal, this configuration is known as a forward bias. In this case, holes flow from the p side to the n side, and electrons flow in the reverse. The junction conducts current. If we connect the p side to the negative terminal and the n side to the positive terminal, then this configuration is known as a reverse bias. In this case, holes and electrons are pulled away from the junction. A simple p-n junction is described as a diode. It conducts currently in only one direction, when in forward bias.

There are three terminals of a typical NMOS transistor - source, drain, and gate. Each of them can be connected to a voltage source. We have two options for the gate voltage - logical 1 ( volts) or logical 0 (0 volts). If the voltage at the gate is logical 1, then the electrons in the channel get attracted towards the gate. If the voltage at the gate is larger than a certain threshold voltage, then a low resistance conduction path forms between the drain and the source due to the accumulation of electrons. Thus, current can flow between the drain and the source. If the effective resistance of the channel is , then we have . If the amount of current flow through the transistor is low, then is roughly equal to because of the low channel resistance. The logic of the PMOS transistor is the opposite of the NMOS transistor.

With these transistors, we can create:

• CMOS inverters
• NAND Gates
• NOR Gates
• XOR Gates
• Decoders: A decoder takes as input a log(n)-bit binary number and has n outputs. Base on the input it sets one of the outputs to 1
• Multiplexers: Multiplexers take n input buts and log(n) select bits, and based on the value of the select bits, chooses one input as the output.
• Demultiplexers: A demultiplexer takes as input a log(n)-bit binary number, a 1-bit input, and transfers the input to one of n output lines.

Sequential Logic

Sequential logic elements save bits for later use - they are named like they are because the output is dependent on past inputs, which came earlier in the sequence of events.

• Clock Signal - A periodic square wave that is sent to every pat of a large circuit or processor.
• Clock Cycle - The period of a clock signal.
• Clock Frequency - The inverse of the clock cycle period.
• Flip-flop: It is a clocked latch that can save a bit.
• A level sensitive latch is dependent on the value of the clock signal - 0 or 1. Typically, it can read in new values, only when the clock is 1.
• An edge sensitive latch reflects the inputs at the output only at a fixed clock edge, such as the downward edge.

Skipping over the Chapter on Computer Arithmetic - also not going too in-depth on sequential logic and electronic memory

Processor Design

A processor acts upon a sequence of bits to do complex arithmetic and logical computations.

• Data Path: The data path consists of all the elements in a processor that are dedicated to storing, retrieving, and processing data such as register files, memories, and ALUs.
• Control Path: The control path is primarily contains the control unit, whose role is generally appropriate signals to control the movement of instructions, and data in the data path.

A port is a point of connection in a hardware structure, and is used for the purpose of either entering inputs, or reading outputs. We can have a read port (exclusively for reading data), a write port (exclusively for writing data), and a read-write port (can be used for both reading and writing).

I started reading this textbook to learn more about computer architecture. Starting at Chapter 9, it became too in-depth to be immediately beneficial (or relevant) to me. I will come back and read more of this at a later point.

Organization: System Design

The operating system itself is a specialized program that helps the processor manage itself, and other programs.

• Temporal Locality: It is a concept that states if a resource is accessed at some point of time, then most likely it will be accessed again in a short time interval
• Spatial Locality: It is a concept that states if a resource is accessed at some point of time, then most likely similar resources will be accessed in the near future

There is a standard rule of thumb in computer architecture which states that 90% of the code runs for 10% of the time and 10% of the code runs for 90% of the time.

A cache contains a set of values for different memory locations.

The main memory (physical memory) is a large DRAM array that contains values for all the memory locations used by the processor. A memory system in which the set of memory values contained in the cache at the n^th level is a subset of all the values contained in the cache at the (m+1)^th level is known as an inclusive cache hierarchy. A memory system that does not follow strict inclusion is referred to as exclusive cache hierarchy.

• Whenever a memory location is present in a cache, the event is known as a cache hit.
• Whenever a memory location is not present in a cache, the event is known as a cache miss.

A cache block or a line is a contiguous set of memory locations. It is treated as an atomic unit of data in a cache.

• Associativity: The number of blocks contained in a set is defined as the associativity of the cache.
• Way: Each entry in a set is known as also known as a way.

The term multiprocessing refers to multiple processors working in parallel. This is a generic definition, and it can refer to multiple processors in the same chip, or processors across different chips. A multicore processor is a specific type of multiprocessor that contains all of its constituent processors in the same chip. Each such processor is known as a core.

• Symmetric Multiprocessing: This paradigm treats all the constituent processors in a multiprocessor system as the same. Each processor has equal access to the operating system, and the I/O peripherals. These are also known as SMP systems.
• Asymmetric Multiprocessing: This paradigm does not treat all the constituent processors in a multiprocessor system as the same. There is typically one master processor that has exclusive control of the operating system and I/O devices. It assigns work to the rest of the processors.

A multicomputer consists of a set of computers typically connected over the network. It is capable of running a set of programs in parallel, where the programs do not share their memory space with each other.

• loosely coupled multiprocessing - Running multiple unrelated programs in parallel on a multiprocessor is known as a loosely coupled multiprocessing
• strongly coupled multiprocessing - running a set of programs in parallel that share their memory space, data, code, file, and network connections is known as strongly coupled multiprocessing.

A process represents the running instance of a program. Typically, it does not share its address space with any other process.

The behavior of memory accesses to the same memory address is known as coherence.