1
From Hardware to Software

This first chapter provides a brief overview of the components found in all computers, from mainframes to the processing chips in tablets, smartphones and smart objects via desktop or laptop computers. Building on this hardware-centric presentation, we shall then give a more abstract description of the actions carried out by computers, leading to a uniform definition of the terms "program" and "execution", above and beyond the various characteristics of so-called electronic devices.

1.1. Computers: a low-level view

Computer science is the science of rational processing of information by computers. Computers have the capacity to carry out a variety of processes, depending on the instructions given to them. Each item of information is an element of knowledge that may be transmitted using a signal and encoded using a sequence of symbols in conjunction with a set of rules used to decode them, i.e. to reconstruct the signal from the sequence of symbols. Computers use binary encoding, involving two symbols; these may be referred to as "true"/"false", "0"/"1" or "high"/"low"; these terms are interchangeable, and all represent the two stable states of the electrical potential of digital electronic circuits.

1.1.1. Information processing

Schematically, a computer is made up of three families of components as follows:

• - memories: store data (information) and executable code (the so-called von Neumann architecture);
• - one or more microprocessors, known as CPUs (central processing units), which process information by applying elementary operations;
• - peripherals: these enable information to be exchanged between the CPU/memory couple and the outside.

Information processing by a computer - in other terms, the execution of a program - can be summarized as a sequence of three steps: fetching data, computing the results and returning them. Each elementary processing operation corresponds to a configuration of the logical circuits of the CPU, known as a logic function. If the result of this function is solely dependent on input, and if no notion of "time" is involved in the computations, then the function is said to be combinatorial; otherwise, it is said to be sequential.

For example, a binary half-adder, as shown in Figure 1.1, is a circuit that computes the sum of two binary digits (input), along with the possible carry value. It thus implements a combinatorial logic function.

Figure 1.1. Binary half-adder

The essential character of a combinatorial function is that, for the same input, the function always produces the same output, no matter what the circumstances. This is not true of sequential logic functions.

For example, a logic function that counts the number of times its input changes relies on a notion of "time" (changes take place in time), and a persistent state between two inputs is required in order to record the previous value of the counter. This state is saved in a memory. For sequential functions, a same input value can result in different output values, as every output depends not only on the input, but also on the state of the memory at the moment of reading the new input.

1.1.2. Memories

Computers use memory to save programs and data. There are several different technologies used in memory components, and a simplified presentation is as follows:

• - RAM (Random Access Memory): RAM memory is both readable and writeable. RAM components are generally fast, but also volatile: if electric power falls down, their content is lost;
• - ROM (Read Only Memory): information stored in a ROM is written at the time of manufacturing, and it is read-only. ROM is slower than RAM, but is non-volatile, like, for example, a burned DVD;
• - EPROM (Erasable Programmable Read Only Memory): this memory is non-volatile, but can be written using a specific device, through exposure to ultra- violet light, or by modifying the power voltage, etc. It is slower than RAM, for both reading and writing. EPROM may be considered equivalent to a rewritable DVD.

Computers use the memory components of several technologies. Storage size diminishes as access speed increases, as fast-access memory is more costly. A distinction is generally made between four different types of memory:

• - mass storage is measured in terabytes and is made either of mechanical disks (with an access time of ~ 10 ms) or - increasingly - of solid-state drive (SSD) blocks. These blocks use an EEPROM variant (electrically erasable) with an access time of ~ 0.1 - 0.3 ms, known as ?ash memory. Mass storage is non-volatile and is principally used for the file system;
• - RAM, which is external to the microprocessor. Recent home computers and smartphones generally possess large RAM capacities (measured in gigabytes). Embedded systems or consumer development electronic boards may have a much lower RAM capacity. The access time is around 40-50 ?s;
• - the cache is generally included in the CPU of modern machines. This is a small RAM memory of a few kilobytes (or megabytes), with an access time of around 5 - 10 ?s. There are often multiple levels of cache, and access time decreases with size. The cache is used to save frequently used and/or consecutive data and/or instructions, reducing the need to access slower RAM by retaining information locally. Cache management is complex: it is important to ensure consistency between the data in the main memory and the cache, between different CPUs or different cores (full, independent processing units within the same CPU) and to decide which data to discard to free up space, etc.;
• - registers are the fastest memory units and are located in the center of the microprocessor itself. The microprocessor contains a limited number (a few dozen) of these storage zones, used directly by CPU instructions. Access time is around one processor cycle, i.e. around 1 ns.

1.1.3. CPUs

The CPU, as its name suggests, is the unit responsible for processing information, via the execution of elementary instructions, which can be roughly grouped into five categories:

• - data transfer instructions (copy between registers or between memory and registers);
• - arithmetic instructions (addition of two integer values contained in two registers, multiplication by a constant, etc.);
• - logical instructions (bit-wise and/or/not, shift, rotate, etc.);
• - branching operations (conditional, non-conditional, to subroutines, etc.);
• - other instructions (halt the processor, reset, interrupt requests, test-and-set, compare-and-swap, etc.).

Instructions are coded by binary words in a format specific to each microprocessor. A program of a few lines in a high-level programming language is translated into tens or even hundreds of elementary instructions, which would be difficult, error prone and time consuming to write out manually. This is illustrated in Figure 1.2, where a "Hello World!" program written in C is shown alongside its counterpart in x86-64 instructions, generated by the gcc compiler.

Figure 1.2. "Hello world!" in C and in x86-64 instructions

Put simply, a microprocessor is split into two parts: a control unit, which decodes and sequences the instructions to execute, and one or more arithmetic and logic units (ALUs) , which carry out the operations stipulated by the instructions. The CPU runs permanently through a three-stage cycle:

• 1) fetching the next instruction to be executed from the memory: every microprocessor contains a special register, the Program Counter (PC), which records the location (address) of this instruction. The PC is then incremented, i.e. the size of the fetched instruction is added to it;
• 2) decoding of the fetched instruction;
• 3) execution of this instruction.

However, the next instruction is not always the one located next to the current instruction. Consider the function min in example 1.1, written in C, which returns the smallest of its two arguments.

EXAMPLE 1.1.-

This function may be translated, intuitively and naively, into elementary instructions, by first placing a and b into registers, then comparing them:

Depending on the result of the test - true or false - different continuations are considered. Execution continues using instructions for one or the other of these continuations: we therefore have two possible control paths. In this case, a conditional jump instruction must be used to modify the PC value, when required, to select the first instruction of one of the two possible paths.