Introduction to Computer Architecture

Welcome to this introductory guide on Computer Architecture. This document is designed for university students beginning their journey into the principles of programming and computer science. Understanding computer architecture is fundamental because it explains how the hardware you write software for actually works. It's the bridge between the physical world of electronics and the abstract world of code.

1. History of Computing Machines

The concept of automated computation is not new. It stretches back to antiquity with devices like the abacus. However, the modern computer's journey began with mechanical devices and evolved through electronics to the microscopic integrated circuits we use today.

The Mechanical Era

Early pioneers like Blaise Pascal (Pascaline, 1642) and Gottfried Wilhelm Leibniz (Stepped Reckoner, 1672) created mechanical calculators that could perform basic arithmetic. However, it was Charles Babbage who envisioned a programmable machine. He is often considered the "father of the computer" for his designs of the Difference Engine and the more ambitious Analytical Engine in the 19th century. The Analytical Engine was a mechanical general-purpose computer that possessed many features of modern computers, including an Arithmetic Logic Unit (ALU), control flow in the form of conditional branching and loops, and integrated memory. Working with him, Ada Lovelace is credited with writing the first algorithm intended to be processed by such a machine, making her the first computer programmer.

The Electronic Revolution

The 20th century saw the transition from mechanical to electronic computing. Key milestones include:

• ENIAC (Electronic Numerical Integrator and Computer): Completed in 1945, it was among the first general-purpose electronic computers. It was massive, filling a large room, and had to be physically rewired to change its program.
• The Von Neumann Architecture: A pivotal moment came when John von Neumann proposed a computer architecture where both program instructions and data are stored in the same memory. This "stored-program computer" concept is the basis for nearly all modern computers. It consists of a Central Processing Unit (CPU), a memory unit, and input/output devices.

Hierarchy and Necessity

The development of computing machines has been driven by necessity: the need for faster calculations for military applications (e.g., artillery firing tables), scientific research, and eventually, business and consumer applications. This led to a hierarchy of advancements:

1. Vacuum Tubes: Enabled the first electronic computers but were bulky, unreliable, and consumed immense power.
2. Transistors: Invented in 1947, they replaced vacuum tubes. They were smaller, faster, more reliable, and consumed less power. This marked the "second generation" of computers.
3. Integrated Circuits (ICs): In the 1960s, engineers found a way to place many transistors onto a single silicon chip. This miniaturization drastically reduced cost and size while increasing power, leading to the "third generation".
4. Microprocessors: The 1970s saw the development of the microprocessor, an entire CPU on a single chip, which ushered in the era of personal computers (the "fourth generation").

2. The Meaning of Computer Software

If hardware represents the physical components of a computer system, software is the set of instructions, data, or programs used to operate computers and execute specific tasks. It is the intangible part of the computer that tells the hardware what to do and how to do it.

"Hardware is the stage, software is the play."

Software is broadly divided into two categories:

• System Software: This software manages the computer hardware and provides a platform for application software to run. The most important piece of system software is the Operating System (OS), like Windows, macOS, or Linux. Other examples include device drivers and utility software.
• Application Software: This is the software designed to perform specific tasks for the end-user. Examples include web browsers, word processors, games, and database applications. The code you write as a programmer is typically application software.

The relationship is layered: your application software talks to the operating system, and the operating system talks to the hardware. This abstraction makes programming much easier, as you don't need to know the exact electronic details of the hardware you're running on.

3. Number Systems

Computers do not understand human language or even the decimal numbers we use daily. At their core, they operate on a binary system. Understanding different number systems and how to convert between them is crucial.

General Representation of a Number

Any number can be represented in a base (or radix) \(b\) system. The value of a number is given by the polynomial formula: \[ D = \sum_{i=-m}^{n-1} d_i \cdot b^i \] Where \(d_i\) is the digit at position \(i\), \(b\) is the base, \(n\) is the number of integer digits, and \(m\) is the number of fractional digits.

Proof of the Formula (by Example)

This formula is the definition of positional notation. Consider the decimal number 37.5. Here, \(b=10\), \(n=2\), \(m=1\). The digits are \(d_1=3, d_0=7, d_{-1}=5\). Expanding the sum: \[ D = (d_1 \cdot 10^1) + (d_0 \cdot 10^0) + (d_{-1} \cdot 10^{-1}) \] \[ D = (3 \cdot 10) + (7 \cdot 1) + (5 \cdot 0.1) = 30 + 7 + 0.5 = 37.5 \] This demonstrates that the formula is a generalized way of expressing how the position of a digit determines its value.

Conversion Algorithms

Decimal Integer to Any Base \(b\)

The algorithm uses successive division. Let \(D\) be the decimal integer. \[ D = q_0 \cdot b + r_0 \] Where \(q_0\) is the quotient and \(r_0\) is the remainder (which will be the least significant digit, \(d_0\)). Next, we divide the quotient \(q_0\): \[ q_0 = q_1 \cdot b + r_1 \] Here, \(r_1\) is the next digit, \(d_1\). We continue this until the quotient becomes 0.

Proof of the Algorithm

By substituting the expressions for the quotients back into the first equation: \[ D = (q_1 \cdot b + r_1) \cdot b + r_0 = q_1 \cdot b^2 + r_1 \cdot b + r_0 \] Substituting again, \(q_1 = q_2 \cdot b + r_2\): \[ D = (q_2 \cdot b + r_2) \cdot b^2 + r_1 \cdot b + r_0 = q_2 \cdot b^3 + r_2 \cdot b^2 + r_1 \cdot b + r_0 \] This continues until the last quotient is zero. The final form is: \[ D = r_k \cdot b^k + \dots + r_2 \cdot b^2 + r_1 \cdot b^1 + r_0 \cdot b^0 \] This is the polynomial representation of the number in base \(b\), where the digits \(d_i\) are the remainders \(r_i\). Since we find \(r_0\) first, the remainders must be read in reverse order.

Decimal Fraction to Any Base \(b\)

The algorithm uses successive multiplication. Let \(F\) be the decimal fraction. We want to find the digits \(d_{-1}, d_{-2}, \dots\) in the representation: \[ F = d_{-1}b^{-1} + d_{-2}b^{-2} + d_{-3}b^{-3} + \dots \]

Proof of the Algorithm

Multiply the entire equation by \(b\): \[ F \cdot b = d_{-1} + d_{-2}b^{-1} + d_{-3}b^{-2} + \dots \] The integer part of this result is \(d_{-1}\), the first fractional digit. The new fractional part is \(F_1 = d_{-2}b^{-1} + d_{-3}b^{-2} + \dots\). We repeat the process: \[ F_1 \cdot b = d_{-2} + d_{-3}b^{-1} + \dots \] The integer part is now \(d_{-2}\). This process is repeated to find successive digits until the fractional part becomes zero or the desired precision is reached.

5. Memory

Computer memory is any physical device capable of storing information temporarily or permanently. In the context of the Von Neumann architecture, memory holds both program instructions and data. Modern systems use a memory hierarchy to balance speed, cost, and capacity.

The hierarchy is effective due to the Principle of Locality:

• Temporal Locality: If an item is accessed, it is likely to be accessed again soon (e.g., loops in code).
• Spatial Locality: If an item is accessed, items with nearby memory addresses are likely to be accessed soon (e.g., sequential array elements).

This principle allows a small, fast cache to significantly speed up access to a large, slow main memory.

6. Representation of Integers

Unsigned Integers

A number is represented by its straightforward binary equivalent. With \(n\) bits, you can represent integers in the range \([0, 2^n - 1]\).

Signed Integers: Two's Complement

The most common method is Two's Complement. The most significant bit (MSB) is the sign bit (0 for positive, 1 for negative). With \(n\) bits, the range is \([-2^{n-1}, 2^{n-1} - 1]\).

Proof of the Range

• Maximum Value: The largest positive number has a sign bit of 0, followed by \(n-1\) ones: \(011\dots1\). This is a geometric series: \(2^{n-2} + 2^{n-3} + \dots + 2^1 + 2^0\). The sum of this series is \( \frac{2^{n-1}-1}{2-1} = 2^{n-1} - 1 \).
• Minimum Value: The most negative number is represented by \(100\dots0\). In two's complement, the weight of the MSB is negative. So, the value is \(-1 \cdot 2^{n-1} + 0 \cdot 2^{n-2} + \dots + 0 \cdot 2^0 = -2^{n-1}\).
• Value of -1: The representation for -1 is \(111\dots1\). The value is \(-2^{n-1} + (2^{n-2} + \dots + 2^0) = -2^{n-1} + (2^{n-1} - 1) = -1\). This confirms the system's consistency.

Mathematical Foundation and Proof of Negation

Two's complement works based on modular arithmetic. For an n-bit system, arithmetic is performed modulo \(2^n\). The two's complement of a positive number \(x\) is defined as \(TC(x) = 2^n - x\).

The "invert and add one" shortcut is derived from this definition. The one's complement (inverting the bits) of \(x\) is equivalent to subtracting \(x\) from the largest \(n\)-bit unsigned number, which is \(2^n - 1\). \[ \text{One's Complement of } x = (2^n - 1) - x \] If we add 1 to the one's complement: \[ ((2^n - 1) - x) + 1 = 2^n - x = TC(x) \] This proves that the "invert and add one" algorithm correctly computes the two's complement of a number.

Sign Extension

To convert an \(n\)-bit two's complement number to an \(m\)-bit number where \(m > n\), you must copy the sign bit to fill the new, higher-order bits. For a positive number, you pad with 0s. For a negative number, you pad with 1s.

7. Representation of Decimal Numbers

Floating-Point Numbers (IEEE 754 Standard)

This standard represents decimal numbers in a form of scientific notation. The value is: \[ \text{Value} = (-1)^S \times (1.M) \times 2^{(E - \text{Bias})} \]

The standard defines several formats. The two most common are:

• Single-Precision (32-bit): 1 sign bit (S), 8 exponent bits (E), 23 mantissa bits (M). Bias = 127.
• Double-Precision (64-bit): 1 sign bit (S), 11 exponent bits (E), 52 mantissa bits (M). Bias = 1023.

Special Values

The standard reserves certain exponent values to represent special numbers:

This allows for representing outcomes of invalid operations, like \(1/0\) (Infinity) or \(\sqrt{-1}\) (NaN).