Learning Computer Architecture with Raspberry Pi

Learning Computer Architecture with Raspberry Pi

(Parte 1 de 4)



Architecture with

Raspberry Pi ®



Architecture with

Raspberry Pi ®

Eben Upton, Jeff Duntemann, Ralph Roberts, Tim Mamtora, and Ben Everard

Learning Computer Architecture with Raspberry Pi®

Published by John Wiley & Sons, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 w.wiley.com

Copyright © 2016 by John Wiley & Sons, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN: 978-1-119-18393-8 ISBN: 978-1-119-18394-5 (ebk) ISBN: 978-1-119-18392-1 (ebk) Manufactured in the United States of America

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 2 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 1 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748- 6008, or online at http://www.wiley.com/go/permissions

For general information on our other products and services please contact our Customer Care Department within the United States at (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Library of Congress Control Number: 2016945538

Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in this book.

Publisher’s Acknowledgements

VP Consumer and Technology Publishing Director:

Michelle Leet

Professional Technology & Strategy Director:

Barry Pruett

Marketing Manager: Lorna Mein

Acquisitions Editor: Jody Lefevere

Project Editor: Charlotte Kughen

Copy Editor: Grace Fairley

Technical Editor: Omer Kilic

Editorial Manager: Mary Beth Wakefield

Editorial Assistant: Matthew Lowe

About the Authors

EBEN UPTON is a founder of the Raspberry Pi Foundation, serves as the CEO of Raspberry Pi (Trading) Ltd, its trading arm, and is the co-author, with Gareth Halfacree, of the Raspberry Pi User Guide. In an earlier life, Eben founded two successful mobile games and middleware companies (Ideaworks 3d and Podfun), held the post of Director of Studies for Computer Science at St John’s College, Cambridge and wrote the Oxford Rhyming Dictionary with his father, Professor Clive Upton. He holds a BA in Physics and Engineering, a PhD in Computer Science, and an Executive MBA, from the University of Cambridge.

JEFF DUNTEMANN has been professionally published in both technical nonfiction and science fiction since 1974. He worked as a programmer for Xerox Corporation and as a technical editor for Ziff-Davis Publishing and Borland International. He launched and edited two print magazines for programmers and has 20 technical books to his credit, including the best-selling Assembly Language Step By Step. He wrote the “Structured Programming” column in Dr. Dobb’s Journal for four years and has published dozens of technical articles in many magazines. With fellow writer Keith Weiskamp, Jeff launched The Coriolis Group in 1989, which went on to become Arizona’s largest book publisher by 1998. He has a longstanding interest in “strong” artificial intelligence, and most of his fiction (including his two novels, The Cunning Blood and Ten Gentle Opportunities) explore the consequences of strong AI. His other interests include electronics and amateur radio (callsign K7JPD), telescopes and kites. Jeff lives in Phoenix, Arizona with Carol, his wife of 40 years, and four bichon frise dogs.

RALPH ROBERTS is a decorated Vietnam Veteran who worked with NASA during the Apollo moon-landing program and has been writing about computers and software continuously since his first sale to Creative Computing magazine in 1979. Roberts has written more than 100 books for national publishers and thousands of articles and short stories. In all, he’s sold more than 20 million words professionally. His best sellers include the first U.S. book on computer viruses (which resulted in several appearances on national TV) and Classic Cooking with Coca-Cola®, a cookbook that has been in print for the past 21 years and has sold 500,0 copies.

TIM MAMTORA works as a master engineer in IC Design for Broadcom Limited and is currently the technical lead for the internal GPU hardware team. He has worked in mobile computer graphics for nearly seven years and previously held roles developing internal IP for analog TV and custom DSP hardware. Tim holds a Masters in Engineering from the University of Cambridge, and he spent his third year at the Massachusetts Institute of Technology, which sparked his interest in digital hardware design. He is passionate about promoting engineering and has dedicated time to supervising undergraduates at the University of Cambridge and giving talks about opportunities in engineering to his old school. Outside of work he enjoys a variety of sports, photography and seeing the world.

BEN EVERARD is a writer and podcaster who spends his days tinkering with Linux and playing with robots. This is his second book; he also wrote Learning Python with Raspberry Pi (Wiley, 2014). You can find him on Twitter at @ben_everard.

About the Technical Editor

OMER KILIC is an embedded systems engineer who enjoys working with small connected computers of all shapes and sizes. He works at the various intersections of hardware and software engineering practices, product development and manufacturing.

—Eben Upton In memory of Alan Drew, without whom I would have stopped before I got started.

To the eternal memory of Steve Ostruszka 1917-1990, who gave me his daughter's hand and honored me with his friendship. —Jeff Duntemann

Table of Contents

Cut to the Chase3
The Knee in the Curve4
Forward the Foundation5

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1

CHAPTER 1 The Shape of a Computer Phenomenon . . . . . . . . . . . . . . . . . . . . . .7

Growing Delicious, Juicy Raspberries7
An Exciting Credit Card-Sized Computer12
What Does the Raspberry Pi Do?14
Meeting and Greeting the Raspberry Pi Board14
GPIO Pins15
Status LEDs16
USB Receptacles18
Ethernet Connection18
Audio Out19
Composite Video21
CSI Camera Module Connector21
Micro USB Power2
Storage Card23
DSI Display Connection24
Mounting Holes25
The Chips25
The Future25

CHAPTER 2 Recapping Computing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27

The Cook as Computer28
Ingredients as Data28
Basic Actions30
The Box That Follows a Plan31
Doing and Knowing31

Programs Are Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32

The System Bus36
Instruction Sets36
Voltages, Numbers and Meaning37
Binary: Counting in 1s and 0s37
The Digit Shortage40
Counting and Numbering and 040
Hexadecimal as a Shorthand for Binary41
Doing Binary and Hexadecimal Arithmetic43
Operating Systems: The Boss of the Box4
What an Operating System Does4
Saluting the Kernel46
Multiple Cores46

CHAPTER 3 Electronic Memory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47

There Was Memory Before There Were Computers47
Rotating Magnetic Memory48
Magnetic Core Memory50
How Core Memory Works50
Memory Access Time52
Static Random Access Memory (SRAM)53
Address Lines and Data Lines54
Combining Memory Chips into Memory Systems56
Dynamic Random Access Memory (DRAM)59
How DRAM Works60
Synchronous vs . Asynchronous DRAM62
SDRAM Columns, Rows, Banks, Ranks and DIMMs64
Error-Correcting Code (ECC) Memory69
The Raspberry Pi Memory System70
Power Reduction Features70
Ball-Grid Array Packaging71
Locality of Reference72
Cache Hierarchy72
Cache Lines and Cache Mapping74
Direct Mapping76
Associative Mapping78
Set-Associative Cache79
Writing Cache Back to Memory81
Virtual Memory81
The Virtual Memory Big Picture82
Mapping Virtual to Physical83
Memory Management Units: Going Deeper84
Multi-Level Page Tables and the TLB8
The Raspberry Pi Swap Problem8
Watching Raspberry Pi Virtual Memory90

CHAPTER 4 ARM Processors and Systems-on-a-Chip . . . . . . . . . . . . . . . . . . . . .93

The Incredible Shrinking CPU93
Transistor Budgets95
Digital Logic Primer95
Logic Gates96
Flip-Flops and Sequential Logic97
Inside the CPU9
Branching and Flags101
The System Stack102
System Clocks and Execution Time105
Pipelining in Detail108
Deeper Pipelines and Pipeline Hazards109
The ARM11 Pipeline112
Superscalar Execution113
More Parallelism with SIMD115
Rethinking the CPU: CISC vs . RISC119
RISC’s Legacy121
Expanded Register Files122
Load/Store Architecture122
Orthogonal Machine Instructions123
Separate Caches for Instructions and Data123
ARMs from Little Acorns Grow124
Microarchitectures, Cores and Families125
Selling Licenses Rather Than Chips125
The ARM Instruction Set126
Processor Modes129
Modes and Registers131
Fast Interrupts137
Software Interrupts137
Interrupt Priority138
Conditional Instruction Execution139
The ARM Coprocessor Interface143
The System Control Coprocessor143
The Vector Floating Point (VFP) Coprocessor144
Emulating Coprocessors145
ARM Cortex145
Multiple-Issue and Out-Of-Order Execution146
Thumb 2147
Thumb E147
big .LITTLE147
The NEON Coprocessor for SIMD148
ARMv8 and 64-Bit Computing148
Systems on a Single Chip150
The Broadcom BCM2835 SoC150
Broadcom’s Second- and Third-Generation SoC Devices151
How VLSI Chips Happen151
Processes, Geometries and Masks152
IP: Cells, Macrocells and Cores153
Hard and Soft IP154
Floorplanning, Layout and Routing154
Standards for On-Chip Communication: AMBA155

CHAPTER 5 Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159

Programming from a Height159
The Software Development Process160
Waterfall vs . Spiral vs . Agile162


Programming in Binary165
Assembly Language and Mnemonics166
High-Level Languages167
Après BASIC, Le Deluge170
Programming Terminology171
How Native-Code Compilers Work173
Lexical Analysis175
Semantic Analysis175
Intermediate Code Generation176
Target Code Generation176
Compiling C: A Concrete Example177
Linking Object Code Files to Executable Files183
Pure Text Interpreters184
Bytecode Interpreted Languages186
Just-In-Time (JIT) Compilation189
Bytecode and JIT Compilation Beyond Java191
Android, Java and Dalvik191
Data Building Blocks192
Identifiers, Reserved Words, Symbols and Operators192
Values, Literals and Named Constants193
Variables, Expressions and Assignment193
Types and Type Definitions194
Static and Dynamic Typing196
Two’s Complement and IEEE 754198
Code Building Blocks200
Control Statements and Compound Statements200
Switch and Case202
Repeat Loops205
While Loops205
For Loops207
The Break and Continue Statements208
Locality and Scope211


Object-Oriented Programming214
OOP Wrapup224
A Tour of the GNU Compiler Collection Toolset224
gcc as Both Compiler and Builder225
Using Linux Make228

CHAPTER 6 Non-Volatile Storage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .231

Punched Cards and Tape232
Punched Cards232
Tape Data Storage232
The Dawn of Magnetic Storage235
Magnetic Recording and Encoding Schemes236
Flux Transitions237
Perpendicular Recording238
Magnetic Disk Storage240
Cylinders, Tracks and Sectors240
Low-Level Formatting242
Interfaces and Controllers244
Floppy Disk Drives246
Partitions and File Systems247
Primary Partitions and Extended Partitions247
File Systems and High-Level Formatting249
The Future: GUID Partition Tables (GPTs)249
Partitions on the Raspberry Pi SD Card250
Optical Discs252
CD-Derived Formats254
DVD-Derived Formats254
Flash Storage257
ROMs, PROMs and EPROMs257
Flash as EEPROM258
Single-Level vs . Multi-Level Storage260
NOR vs . NAND Flash261
Wear Levelling and the Flash Translation Layer265


Garbage Collection and TRIM267
SD Cards268
The Future of Non-Volatile Storage271

CHAPTER 7 Wired and Wireless Ethernet. . . . . . . . . . . . . . . . . . . . . . . . . . . .273

The OSI Reference Model for Networking274
The Application Layer276
The Presentation Layer276
The Session Layer278
The Transport Layer278
The Network Layer279
The Data Link Layer281
The Physical Layer282
Thicknet and Thinnet283
The Basic Ethernet Idea283
Collision Detection and Avoidance285
Ethernet Encoding Systems286
PAM-5 Encoding290
10BASE-T and Twisted-Pair Cabling291
From Bus Topology to Star Topology292
Switched Ethernet293
Routers and the Internet296
Names vs . Addresses296
IP Addresses and TCP Ports297
Local IP Addresses and DHCP300
Network Address Translation302
Standards within Standards305
Facing the Real World305
Wi-Fi Equipment in Use309
Infrastructure Networks vs . Ad Hoc Networks311
Wi-Fi Distributed Media Access312
Carrier Sense and the Hidden Node Problem314
Amplitude Modulation, Phase Modulation and QAM316
Spread-Spectrum Techniques319
Wi-Fi Modulation and Coding in Detail320
How Wi-Fi Connections Happen323
Wi-Fi Security325
Wi-Fi on the Raspberry Pi326
Even More Networking329

CHAPTER 8 Operating Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331

Introduction to Operating Systems3
History of Operating Systems3
The Basics of Operating Systems336
The Kernel: The Basic Facilitator of Operating Systems343
Operating System Control344
Memory Management346
Virtual Memory347
Disk Access and File Systems348
Device Drivers349
Enablers and Assistants to the Operating System349
Waking Up the OS349
Operating Systems for Raspberry Pi354
Third-Party Operating Systems356
Other Available Operating Systems356

CHAPTER 9 Video Codecs and Video Compression. . . . . . . . . . . . . . . . . . . . . .359

The First Video Codecs360
Exploiting the Eye361
Exploiting the Data363
Understanding Frequency Transform367
Using Lossless Encoding Techniques371
Changing with the Times373
The Latest Standards from MPEG374
H .265378


Motion Search378
Video Quality381
Processing Power382

CHAPTER 10 3D Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .383

A Brief History of 3D Graphics383
The Graphical User Interface (GUI)384
3D Graphics in Video Games386
Personal Computing and the Graphics Card387
Two Competing Standards390
The OpenGL Graphics Pipeline391
Geometry Specification and Attributes393
Geometry Transformation396
Lighting and Materials400
Primitive Assembly and Rasterisation403
Pixel Processing (Fragment Shading)405
Modern Graphics Hardware411
Tiled Rendering411
Geometry Rejection413
Raspberry Pi GPU417
Open VG421
General Purpose GPUs423
Heterogeneous Architectures423

CHAPTER 1 Audio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .427

Can You Hear Me Now?427
Sound Cards428
Analog vs . Digital429
Sound and Signal Processing430


Recording with Effects432
Encoding and Decoding Information for Communication433
1-Bit DAC434
Raspberry Pi Sound Input/Output437
Audio Output Jack437
Sound on the Raspberry Pi438
Raspberry Pi Sound on Board439
Manipulating Sound on the Raspberry Pi439

CHAPTER 12 Input/Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .447

Introducing Input/Output448
I/O Enablers451
Universal Serial Bus452
USB Powered Hubs455
Universal Asynchronous Receiver/Transmitters458
Small Computer Systems Interface459
Parallel ATA459
Serial Advanced Technology Attachment460
RS-232 Serial460
High Definition Media Interface461
Raspberry Pi Display, Camera Interface and JTAG464
Raspberry Pi GPIO464
GPIO Overview and the Broadcom SoC465
Meeting the GPIO466
Programming GPIO473
Alternative Modes479
GPIO Experimentation the Easy Way480

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .481 xviii



Architecture with

Raspberry Pi ®


WHEN I WAS 10 years old, one of my teachers sat me down in front of a computer at school. Now, this isn’t what you think. I wasn’t about to be inducted into the mysteries of computer programming, even though it was a BBC Micro (the most programmable and arguably the most architecturally sophisticated of the British 8-bit microcomputers, on which I would subsequently cut my teeth in BASIC and assembly language). Instead, I was faced with a half-hour barrage of multiple choice questions about my academic interests, hobbies and ambitions, after which the miraculous machine spat out a diagnosis of my ideal future career: microelectronic chip designer.

This was a bit of a puzzler, not least because what I really wanted to be was a computer game programmer (okay, okay, astronaut) and there was nobody in my immediate environment who had any idea what a 10-year-old should do to set him on the path to the sunlit uplands of microelectronic chip design. Over the next few years, I studied a lot of maths and science at school, learned to program (games) at home, first on the BBC Micro and then the Commodore Amiga, and made repeated, not particularly successful, forays into electronics. As it turned out, and more by luck than judgment, I’d happened on a plausible road to my destination, but it wasn’t until I arrived at Cambridge at the age of 18 that I started to figure out where the gaps were in my understanding.


Cambridge occupies a special place in the history of computer science, and particularly in the history of practical or applied computing. In the late 1930s, the young Cambridge academic Alan Turing demonstrated that the halting problem (the question “Will this computer program ever terminate, or halt?”) was not computable; in essence, you can’t write a computer program that will analyse another arbitrary computer program and determine if it will halt. At the same time, working independently, Alonzo Church proved the same result, which now shares their names: the Church-Turing thesis. But it is telling that while Church took a purely mathematical approach to his proof, based on recursive functions, Turing’s proof cast computation in terms of sequential operations performed by what we now know as Turing machines: simple gadgets that walk up and down an infinite tape, reading symbols, changing their internal state and direction of travel in response, and writing new symbols. While most such machines are specialised to a single purpose, Turing introduced the concept of the universal machine, which could be configured via commands written on the tape to emulate the action of any other special-purpose machine. This was the first appearance of a now commonplace idea: the general-purpose programmable computer.


After the outbreak of the Second World War, Turing would go on to play a central role in the Allied code-breaking effort at Bletchley Park, where he was involved (as a member of a team—don’t believe everything you see at the movies) in the development of a number of pieces of special-purpose hardware, including the electromechanical bombe, which automated the process of breaking the German Enigma cipher. None of these machines used the specific “finite state automaton plus infinite tape” architecture of Turing’s original thought experiment; this turned out to be better suited to mathematical analysis than to actual implementation. And not even the purely electronic Colossus—which did to the formidably sophisticated Lorentz stream cipher what the bombe had done to Enigma—crossed the line into general-purpose programmability. Nonetheless, the experience of developing large-scale electronic systems for code-breaking, radar and gunnery, and of implementing digital logic circuits using thermionic valves, would prove transformative for a generation of academic engineers as they returned to civilian life.

One group of these engineers, under Maurice Wilkes at the University of Cambridge’s Mathematical Laboratory, set about building what would become the Electronic Delay Storage Automatic Calculator, or EDSAC. When it first became operational in 1949, it boasted a 500kHz clock speed, 32 mercury delay lines in two temperature-controlled water baths for a total of 2 kilobytes of volatile storage. Programs and data could be read from, and written to, paper tape. Many institutions in the U.S. and UK can advance narrow claims to having produced the first general-purpose digital computer, for a particular value of “first”. Claims have been made that EDSAC was the first computer to see widespread use outside the team that developed it; academics in other disciplines could request time on the machine to run their own programs, introducing the concept of computing as a service. EDSAC was followed by EDSAC I, and then Titan. It was only in the mid-1960s that the University stopped building its own computers from scratch and started buying them from commercial vendors. This practical emphasis is even reflected in the current name of the computer department: Cambridge doesn’t have a computer science faculty; it has a computer laboratory, the direct descendant of Wilkes’ original mathematical laboratory.

This focus on the practical elements of computer engineering has made Cambridge fertile ground for high-technology startups, many of them spun out of the computer laboratory, the engineering department or the various maths and science faculties (even our mathematicians know how to hack), and has made it a magnet for multinational firms seeking engineering talent. Variously referred to as the Cambridge Cluster, the Cambridge Phenomenon or just Silicon Fen, the network of firms that has grown up around the University represents one of the few bona fide technology clusters outside of Silicon Valley. The BBC Microcomputer that told me I should become a chip designer was a Cambridge product, as was its perennial rival, the Sinclair Spectrum. Your cell phone (and your Raspberry Pi) contains several processors designed by the Cambridge-based chip firm ARM. Seventy years after EDSAC, Cambridge remains the home of high technology in the UK.


Cut to the Chase

One of the biggest missing pieces from my haphazard computing education was an idea of how, underneath it all, my computer worked. While I’d graduated downwards from BASIC to assembly language, I’d become “stuck” at that level of abstraction. I could poke my Amiga’s hardware registers to move sprites around the screen but I had no idea how I might go about building a computer of my own. It took me another decade, a couple of degrees and a move out of academia to work for Broadcom (a U.S. semiconductor company that came to Cambridge for the startups and stayed for the engineering talent) for me to get to the point where I woke up one morning with “microelectronic chip designer” (in fact the fancier equivalent, “ASIC architect”) on my business card. During this time, I’ve had the privilege of working with, and learning from, a number of vastly more accomplished practitioners in the field, including Sophie Wilson, architect (with Steve Furber) of the BBC Micro and the original ARM processor, and Tim Mamtora of Broadcom’s 3D graphics hardware engineering team, who has graciously provided the chapter on graphics processing units (GPUs) for this book.

(Parte 1 de 4)