Computer Architecture E-Book

Gérard Blanchet

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 390

Veröffentlichungsjahr: 2013

Beschreibung

This book lays out the concepts necessary to understand how a computer works. For reasons of clarity, the authors have deliberately chosen examples that apply to machines from all eras, without having to water down the contents of the book. This choice helps to show how techniques, concepts and performances have evolved since the first computers. The book is divided into five parts. The first four, which are of increasing difficulty, are the core of the book: "Elements of a Basic Architecture", "Programming Model and Operation", "Memory Hierarchy", "Parallelism and Performance Enhancement". The final part provides hints and solutions to the exercises in the book as well as appendices. The reader may approach each part independently based on their prior knowledge and goals.

Leseprobe

Contents

Preface

PART 1. ELEMENTS OF A BASIC ARCHITECTURE

Chapter 1 Introduction

1.1. Historical background

1.2. Introduction to internal operation

1.3. Future prospects

Chapter 2 The Basic Modules

2.1. Memory

2.2. The processor

2.3. Communication between modules

Chapter 3 The Representation of Information

3.1. Review

3.2. Number representation Conventions

3.3. Character representation

3.4. Exercises

PART 2. PROGRAMMING MODEL AND OPERATION

Chapter 4 Instructions

4.1. Programming model

4.2. The set of instructions

4.3. Programming examples

4.4. From assembly language to basic instructions

Chapter 5 The Processor

5.1. The control bus

5.2. Execution of an instruction: an example

5.3. Sequencer composition

5.4. Extensions

5.5. Exercise

Chapter 6 Inputs and Outputs

6.1. Examples

6.2. Design and addressing of EU

6.3. Exchange modes

6.4. Handling interrupts

6.5. Exercises

PART 3. MEMORY HIERARCHY

Chapter 7 Memory

7.1. The memory resource

7.2. Characteristics

7.3. Memory hierarchy

7.4. Memory size and protection

7.5. Segmentation

7.6. Paging

7.7. Memory interleaving and burst mode

7.8. Protections, example of the I386

Chapter 8 Caches

8.1. Cache memory

8.2. Replacement algorithms

Chapter 9 Virtual Memory

9.1. General concept

9.2. Rules of the access method

9.3. Example of the execution of a program

9.4. Example of two-level paging

9.5. Paged segmentation

9.6. Exercise

9.7. Documentation excerpts

PART 4. PARALLELISM AND PERFORMANCE ENHANCEMENT

Chapter 10 Pipeline Architectures

10.1. Motivations and ideas

10.2. Pipeline management problems

10.3. Handling branches

10.4. Interrupts and exceptions

Chapter 11 Example of an Architecture

11.1. Presentation

11.2. Executing an instruction

11.3. Conflict resolution in the DLX

11.4. Exercises

Chapter 12 Caches in a Multiprocessor Environment

12.1. Cache coherence

12.2. Examples of snooping protocols

12.3 Improvements

12.4 Directory-based coherence protocols

12.5. Consistency

12.6. Exercises

Chapter 13 Superscalar Architectures

13.1. Superscalar architecture principles

13.2. Seeking solutions

13.3 Handling the flow of instructions

13.4 VLIW architectures

13.5. Exercises

PART 5. APPENDICES

Appendix A Hints and Solutions

A1.1. The representation of information

A1.2. The processor

A1.3. Inputs and outputs

A1.4. Virtual memory

A1.5. Pipeline architectures

A1.6. Caches in a multiprocessor environment

A1.7. Superscalar architectures

Appendix B Programming Models

A2.1. Instruction coding in the I8086

A2.2. Instruction set of the DLX architecture

Bibliography

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

© ISTE Ltd 2013

The rights of Gérard Blanchet and Bertrand Dupouy to be identified as the author of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2012951898

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-429-3

Preface

This book presents the concepts necessary for understanding the operation of a Computer. The book is written based on the following:

– the details of how a computer’s components function electronically are beyond the scope of this book;

– the emphasis is on the concepts and the book focuses on the building blocks of a machine’s architecture, on their functions, and on their interaction;

– the essential links between software and hardware resource are emphasized wherever necessary.

For reasons of clarity, we have deliberately chosen examples that apply to machines from all eras, without having to water down the contents of the book. This choice helps us to show how techniques, concepts and performance have evolved since the first computers.

This book is divided into five parts. The first four, which are of increasing difficulty, form the core of the book: “Elements of a basic architecture”, “Programming model and operation”, “Memory hierarchy” and “Parallelism and performance enhancement”. The final part, which comprises appendices, provides hints and solutions to the exercises in the book as well as programming models. The reader may approach each part independently based on their prior knowledge and goals.

Presentation of the five parts:

1) Elements of a basic architecture:

– Chapter 1 takes a historical approach to present the main building blocks of a processor.

– Chapter 2 lists in detail the basic modules and their features, and describes how they are connected.

– Chapter 3 focuses on the representation of information: integers, floating-point numbers, fixed-point numbers and characters.

2) Programming model and operation:

– Chapter 4 explains the relationship between the set of instructions and the architecture.

– Chapter 5 provides a detailed example of the execution of an instruction to shed some light on the internal mechanisms that govern the operation of a processor. Some additional elements, such as coprocessors and vector extensions, are also introduced.

– Chapter 6 describes the rules – polling, direct memory accesses and interrupts – involved in exchanges with peripherals.

3) Memory hierarchy:

– Chapter 7 gives some elements – hierarchy, segmentation and paging – on the organization of memory.

– Chapter 8 presents cache memory organization and access methods.

– Chapter 9 describes virtual memory management concepts, rules and access rights.

4) Parallelism and performance enhancement:

– Chapter 10 gives an introduction to parallelism by presenting pipeline architectures: concepts, as well as software and hardware conflict resolution.

– Chapter 11 gives the DLX architecture as an example.

– Chapter 12 deals with cache management in a multiprocessor environment; coherence and protocols (MSI, MEI, etc.).

– Chapter 13 presents the operation of a superscalar architecture conflict, the scoreboarding and Tomasulo algorithms, and VLIW architectures.

5) Complementary material on the programming models used and the hints and solutions to the exercises given in the different chapters can be found in the appendices.

PART 1

Elements of a Basic Architecture

Chapter 1

Introduction

After providing some historical background, we will highlight the major components of a Computer machine [MOR 81, ROS 69, LAV 75]. This will lead us to describe a category of calculators that we will refer to as classic architecture machines, or classic architecture uniprocessors. We will examine the functions performed by each of their modules, and then describe them in greater detail in the following chapters.

1.1. Historical background

1.1.1. Automations and mechanical calculators

The first known mechanical calculators [SCI 96] were designed by Wilhelm Schickard (1592–1635) (≈1623), Blaise Pascal (≈1642) and Gottfried Wilhelm Leibniz (1646–1716) (≈1673): they operate in base 10 through a gear mechanism.

Figure 1.1.Blaise Pascal’s Pascaline

It is up to the user to put together series of operations. The need for a sequence of processes that is automated is what will eventually lead to the design of computers.

The sequencing of simple tasks had already been implemented in the design of music boxes, barrel organs, self-playing pianos, in which cylinders with pins, cam systems and perforated paper tapes determined the melody. The loom, designed by Joseph-Marie Jacquard (1752–1834), is another example of an automaton. A series of perforated cards indicates the sequence of elementary operations to perform: each hole allows a needle to go through, and the tetrahedron that supports the cards rotates at the same pace as the shuttle which carries the thread that is woven. Introduced in the years 1804–1805, Jacquard’s invention was formally recognized by France as being of a public benefit in 1806. In 1812, there were 11,000 such looms in France [ENC 08]. Some can still be found in operation in workshops around Lyon.

Figure 1.2.An example of Jacquard’s loom, courtesy of “La Maison des Canuts”, Lyon, France

This system provides a first glance at what will later become devices based on programmable automatons, or calculators, dedicated to controlling industrial processes.

Charles Babbage (1792–1871) was the first to undertake the design of a machine combining an automaton and a mechanical calculator. Having already designed a calculator, the Difference Engine, which can be seen at the Science Museum in London, he presented a project for a more universal machine, at a seminar held in Turin in 1841. His collaboration with Ada Lovelace (the daughter of Lord Byron) allowed him to describe a more detailed and ambitious machine, which foreshadows our modern computers. This machine, known as the analytical engine [MEN 42], autonomously performs sequences of arithmetic operations. As with Jacquard’s loom, it is controlled by perforated tape. The user describes on this “program-tape” the sequence of operations that needs to be performed by the machine. The tape is fed into the machine upon each new execution. This is because Babbage’s machine, despite its ability to memorize intermediate results, had no means for memorizing programs, which were always on some external support. This is known as an external program machine. This machine introduces the concept of memory (referred to by Babbage as the store) and of a processor (the mill). Another innovation, and contrary to what was done before, is that the needles, which engaged based on the presence or the absence of holes in the perforated tape, do not directly engage the output devices. In a barrel organ, a note is associated with each hole in the tape; this is formally described by saying that the output is logically equal to the input. In the analytical engine, however, we can already say that a program and data are coded.

Figure 1.3.Babbage’s analytical engine

This machine is divided into three distinct components, with different functions: the automaton–calculator part, the data and the program.

While each row of the perforated tape contains data that are “logical” in nature – the presence or the absence of a hole – the same cannot be said for both the automaton, which is purely mechanical, and the calculation unit, which operates on base 10 representations.

1.1.1.1. Data storage

The idea that it was necessary to automatically process data took hold during the 1890 census in the United States, a census that covered 62 million people. It was the subject of a call for bids, with the contract going to Herman Hollerith (1860–1929). Hollerith suggested using a system of perforated cards already used by certain railway companies. The cards were 7.375 by 3.25 inches which, as the legend goes, correspond to the size of the $1 bill at the time. The Tabulating Machine Company, started by Herman Hollerith, would eventually become International Business Machines (IBM), in 1924.

Figure 1.4.A perforated card: each character is coded according to the “Hollerith” code

In 1937, Howard Aiken, of Harvard University, gave IBM the suggestion of building a giant calculator from the mechanical and electromechanical devices used for punch card machines. Completed in 1943, the machine weighed 10,000 pounds, was equipped with accumulators capable of memorizing 72 numbers, and could multiply two 23-digit numbers in 6 s. It was controlled through instructions coded onto perforated paper tape.

Figure 1.5.Perforated tape

Despite the knowledge acquired from Babbage, this machine lacked the ability to process conditional instructions. It did, however, have two additional features compared to Babbage’s analytical engine: a clock for controlling sequences of operations and registers, a type of temporary memory used for recording data.

Another precursor was the Robinson, designed in England during World War II and used for decoding encrypted messages created by the German forces on Enigma machines.

1.1.2. From external program to stored program

In the 1940s, research into automated calculators was a booming field, spurred in large part by A. Turing in England; H. Aiken, P. Eckert and J. Mauchly [MAU 79] in the United States; and based in part on the works of J.V.Atanasoff (1995†) (Automatic Electronic Digital Computer (AEDQ) between 1937 and 1942).

The first machines that were built were electromechanical, and later relied on vacuum tube technology. They were designed for specific processes and had to be rewired every time a change was required in the sequence of operations. These were still externally programmed machines. J. von Neumann [VON 45, GOL 63] built the foundations for the architecture used by modern calculators, the von Neumann architecture.

The first two principles that define this architecture are the following:

– The universal applicability of the machines.

– Just as intermediate results produced from the execution of operations are stored into memory, the operations themselves will be stored in memory. This is called stored-program computing.

The elementary operations will be specified by instructions, the instructions are listed in programs and the programs are stored in memory. The machine can now go through the steps in a program with no outside intervention, and without having to reload the program every time it has to be executed.

The third principle that makes this calculator an “intelligent” machine, as opposed to its ancestors, is the sequence break. The machine has decision capabilities that are independent from any human intervention: as the program proceeds through its different steps, the automaton decides the sequence of instructions to be executed, based on the results of tests performed on the data being processed. Subsequent machines rely on this basic organization.

Computer designers then focused their efforts in two directions:

– Technology: using components that are more compact, perform better, with more complex functions, and consume lower energy.

– Architecture: parallelization of the processor’s activities and organization of the memory according to a hierarchy. Machines designed with a Harvard architecture, in which access to instructions and to data is performed independently, meet this condition in part.

Figure 1.6 presents the major dates and concepts in the evolution that led to what is now called a computer. Note that without the methodological foundation provided by Boolean algebra, the first computer would probably not have emerged so quickly. This is because the use of this algebra leads to a unification of the representations used for designing the components and coding the instructions and data.

Figure 1.6.From externally programmed to parallel Computing

1.1.3. The different generations

Since the Electronic Discrete Variable Automatic Computer (EDVAC) in 1945, under the direction of J. von Neumann [VON 45, GOL 63] (the first stored-program calculator), hundreds of machines have been designed. To organize the history of these machines, we can use the concept of generations of calculators, which is based essentially on technological considerations. Another classification could just as well be made based on software criteria, associated with the development of languages and operating systems for calculators.

1.1.3.1. The first generation (≈1938–1953)

Machines of this era are closer to laboratory prototypes than computers as we picture them today. These machines consist of relays, electronic tubes, resistors and other discrete components. The ENIAC, for example, abbreviated form for Electronic Numerical Integrator And Computer, was made up of 18,000 vacuum tubes, consumed around 150 kW, and was equipped with 20 memory elements (Figure 1.71).

Figure 1.7.A photograph of ENIAC

Because of the difficulties in the calculation part of the work, the processes were executed in series by operators working on a single binary element.

Being very energy-intensive, bulky and unreliable, these machines had an extremely crude programming language, known as machine language. Program development represents a considerable amount of work. Only one copy of each of these machines was made, and they were essentially used for research purposes. This was the case with the ENIAC, for example, which was involved in the research program for developing the Bomba [LAU 83], a machine used for decrypting messages during World War II.

1.1.3.2. Second generation (≈1953–1963)

The second generation saw the advent of machines that were easier to operate (the IBM-701, among others). Transistors (the first of which dates back to 1947) started to replacing vacuum tubes. Memory used ferrite toroids, and operating systems, the first tools designed to facilitate the use of computers, were created. Until then, machines were not equipped with development environments or with a user interface as we know them now. Pre-programmed input–output modules, known as Input Output Control Systems (IOCS) are the only available tools to facilitate programming. Each task (editing, processing, etc.) is executed automatically. In order to save time between the end of a job and the beginning of another, the batch processing system is introduced, which groups together jobs of the same type. At the end of each task, the operating system takes control again, and launches the next job. Complex programming languages were created, and become known as symbolic coding systems. The first FORTRAN (FORmula TRANslator) compiler dates back to 1957 and is included with the IBM-704. The first specifications for COBOL (COmmon Business Oriented Language) were laid out in 1959 under the name COBOL 60. Large size applications in the field of management are developed. Magnetic tapes are used for archiving data.

1.1.3.3. Third generation (≈1964–1975)

The PLANAR process, developed at FAIRCHILD starting in 1959, makes it possible to produce integrated circuits. This fabrication technique is a qualitative breakthrough: reliability, energy consumption and size being dramatically improved.

Alongside the advances in hardware performance came the concept of multiprogramming, the objective of which is to optimize the use of the machine. Several programs are stored in the memory at the same time, making it possible to quickly switch from one program to another. The concept of input–output device independence emerges. The programmer no longer has to explicitly specify the unit where the input–output operation is being executed. Operating systems are now written in high-level languages.

Several computer operating modes are created in addition to batch processing:

– Time sharing, TS, lets the user work interactively with the machine. The best known TS system, Compatible Time Sharing System (TSS), was developed at Massachusetts Institute of Technology (MIT) and led to the Multics system, developed collaboratively by MIT, Bell Labs and General Electric.

– Real time is used for industrial process control. Its defining feature is that the system must meet deadlines set by outside stimuli.

– Transaction processing is mainly used in management computing. The user communicates with the machine using a set of requests sent from a workstation.

The concept of virtual memory is developed. The joint use of drives and memory, which is seamless for the user, creates the impression of having a memory capacity far greater than what is physically available. The mid-1960s see the advent of the IBM-360 calculator series, designed for general use, and equipped with an operating system (OS/360) capable of managing several types of jobs (batch processing, time sharing, multiprocessing, etc.).

This new era sets the stage for a spectacular increase in the complexity of operating systems. Along with this series of calculators emerges the concept of compatibility between machines. This means that users can acquire a more powerful machine within the series offered by the manufacturer, and still hold on to their initial software investment.

The first multiprocessor systems (computers equipped with several “automaton–calculation” units) are born at the end of the 1960s. The development of systems for machines to communicate with one another leads to computer networks.

Figure 1.8.In the 1970s, memory still relied on magnetic cores. This photograph shows a 4 × (32 × 64) bit plane. Each toroid, ≈0.6 mm in diameter, has three wires going through itscenter

Figure 1.9.The memory plane photographed here comprises twenty 512-bit planes. The toroids have become difficult to discern with the naked eye

In the early 1970s, the manufacturing company IBM adopted a new policy (unbundling) regarding the distribution of its products, where hardware and software are separated. It then becomes possible to obtain IBM-compatible hardware and software developed by companies in the service industry. This policy led to the rise of a powerful software industry that was independent of machine manufacturers.

1.1.3.4. Fourth generation (≈1975–)

This fourth generation is tied to the systematic use of circuits with large, and later very large, scale integration (LLSI and VLSI). This is not due to any particular technological breakthrough, but rather due to the dramatic improvement in fabrication processes and circuit design, which are now computer assisted.

The integration of the different processor modules culminated in the early 1970s, with the development of the microprocessor. Intel® releases the I4004. The processor takes up only a few square millimeters of silicon surface. The circuit is called a chip. The first microcomputer, built around the Intel® I8080 microprocessor, came into existence in 1971.

Figure 1.10.A few reprogrammable memory circuits: from 8 kbits (≈1977) (right-hand chip) to 1 Mbit (≈1997) (left-hand chip) with no significant change in silicon surface area

Figure 1.11.A few old microprocessors: (a) MotorolaTM6800 (1974, ≈6,800 transitors), IntelTMI8088 (1979, ≈29,000), ZilogTMZ80 (1976, ≈8,500), AMD Athlon 64X2 (1999, from ≈122 millions to ≈243 millions); (b) Intel i486 DX2 (1989, ≈1.2 million), Texas InstrumentsTMTMX320C40 (1991, ≈650,000)

The increase in the scale of integration makes it possible for anybody to have access to machines with capabilities equivalent to the massive machines from the early 1970s. At the same time, the field of software development is exploding.

Designers rely more and more on parallelism in their machine architecture in order to improve performance without having to implement new technologies (pipeline, vectorization, caches, etc.). New architectures are developed: language machines, multiprocessor machines, and data flow machines.

Operating systems feature network communication abilities, access to databases and distributed computing. At the same time, and under pressure from microcomputer users, the idea that systems should be user friendly begins to take hold. The ease of use and a pleasant feel become decisive factors in the choice of software.

The concept of the virtual machine is widespread. The user no longer needs to know the details of how a machine operates. They are addressing a virtual machine, supported by an operating system hosting other operating systems.

The “digital” world keeps growing, taking over every sector, from the most technical–instrumentation, process command, etc.–to the most mundane–electronic payments, home automation, etc.

1.2. Introduction to internal operation

1.2.1. Communicating with the machine

The three internal functioning units – the automaton, the calculation unit and the memory unit that contain the intermediate results and the program – appear as a single module accessible to the user only through the means of communication called peripheral units, or peripherals.

The data available as machine inputs (or outputs) are only rarely represented in binary. It can exist in many different formats: as text, an image, speech, etc. Between these sources of data and the three functional units, the following must be present:

– sensors providing an electrical image of the source;

– preprocessing hardware that, based on this image, provides a signal usable by the computer by meeting the electrical specifications of the connection (e.g. a filter, followed by a sampling of the source signal, itself followed by a link in series with the computer);

– exchange units located between the hardware and the computer’s core.

Exchange units are a part of the computing machine. The user ignores their existence.

We will adopt the convention of referring to the system consisting of the processor (calculator and automaton) + memory + exchange units as the Central Processing Unit (CPU).

Figure 1.12.User–machine communication

It is important to note that the symbols “0” and “1” used in Figure 1.12 to represent data are notations used by convention. This facilitates the representation of logic values provided by the computing machine. They could have been defined as “α” and “β”, “φ” and “E”, etc.

What emerges from this is a modular structure, the elements of which are the processor (calculation and automaton part), the memory, the exchange units, and connections, or buses, the purpose of which is to connect all of these modules together.

1.2.2. Carrying out the instructions

The functional units in charge of carrying out a program are the automaton and the calculator:

– the automaton, or control unit, is in command of all the operations;

– the module tasked with the calculation part will be referred as the processing unit.

Together, these two modules make up the processor, the “intelligent” part of the machine.

The basic operations performed by the computer are known as instructions. A set of instructions used for achieving a task will be referred to as a program (Figure 1.13).

Every action carried out by the computing machine corresponds to the execution of a program.

Figure 1.13.Processor and memory

Once it has been turned on, the computer executes a “fetch-execution” cycle, which can only be interrupted by cutting its power supply.

The fetch operation consists of retrieving within the memory an instruction that the control unit recognizes – decodes – and which will be executed by the processing unit. The execution leads to (see Figure 1.14) (1) a local processing operation, (2) something being read from or written into memory, or (3) something being read from or written into an exchange unit. The control unit generates all of the signals involved in going through the cycle.

Figure 1.14.Accessing an instruction

1.3. Future prospects

Silicon will remain the material of choice of integrated circuit founders for many years to come. CMOS technology, the abbreviated form for complementary metal-oxide semiconductor (and its derivatives), long ago replaced TTL (transistor-transistor Logic) and ECL (emitter-coupled logic) technologies, even inside mainframes, because of its low consumption and its performance capabilities. The power supply voltage keeps dropping – 3.3, 2.9, 1.8 V are now common – while the scale of integration increases with improvements in etching techniques (half-pitch below 30 nm) and the use of copper for metallization. There are many improvements in fabrication processes. Computer-aided design (CAD), helps reduce development time and increases circuit complexity. The integration of test methods as early as during the design phase is an advantage for improving fabrication yields.

– It is the architecture that is expected to greatly enhance the machine performance. Parallelism is the main way to achieve this. It can be implemented at the level of the processor itself (operator parallelism and data parallelism) or on the higher level of the machine, by installing several processors which may or may not be able to cooperate. The improvement of the communication links becomes significant to transmit data. Protocols and bus technology are rapidly evolving to meet this objective.

– User-friendly interfaces are now commonplace. Multi-task operating systems are used on personal machines. Operating systems now have the ability to use the machine’s hardware resources.

– The cost of a machine also includes the cost of the software designed for operating it. Despite the emergence of improved software technology (object-oriented approach, etc.), applications are developed and maintained with lifecycles far beyond the replacement cycle of hardware.

– As early on as the design phase, machines are equipped with the means of communication which facilitate their integration into networks. Working on a machine does not imply that the processing is performed locally. Similarly, the data handled can originate from remote sites. While this concept of delocalization is not new, the concept that access should be transparent is quite recent (distributed computing).

Throughout this book, the word architecture will refer to the organization of the modules which comprise the computing machine, to their interconnections, and not to how they are actually created using logic components: gates, flip-flops, registers or other, more complex elements.

1http://ftp.arl.army.mil/ftp/historic-computers

Chapter 2

The Basic Modules

This chapter presents the main modules that constitute a computer: the memory, the processor and the exchange units. We will review the operation of registers and counters used in the execution of instructions. We will not discuss in detail the internal workings of the different modules, and will instead focus on their functions.

2.1. Memory

Memory contains all of the data used by the processor. There are two types of data: a series of instructions and data on which to execute these instructions.