(The Morgan Kaufmann Series in Computer Architecture and Design) David A. Patterson, John L. Hennessy - Computer Organization and Design RISC-V Edition_ The Hardware Software Interface-Morgan Kaufmann-24-101-1-9 copy.pdf

1 Computer Abstractions and Civilization advances Technology by extending the...

1 Computer Abstractions and Civilization advances Technology by extending the 1.1 Introduction 3 number of important 1.2 Seven Great Ideas in Computer operations which we Architecture 10 can perform without 1.3 Below Your Program 13 thinking about them. 1.4 Under the Covers 16 1.5 Technologies for Building Processors and Alfred North Whitehead, An Introduction to Mathematics, 1911 Memory 25 Computer Organization and Design RISC-V Edition. DOI: http://dx.doi.org/10.1016/B978-0-12-820331-6.00001-6 © 2016 2021 Elsevier Inc. All rights reserved. 1.6 Performance 29 1.7 The Power Wall 40 1.8 The Sea Change: The Switch from Uniprocessors to Multiprocessors 43 1.9 Real Stuff: Benchmarking the Intel Core i7 46 1.10 Going Faster: Matrix Multiply in Python 49 1.11 Fallacies and Pitfalls 50 1.12 Concluding Remarks 53 1.13 Historical Perspective and Further Reading 55 1.14 Self-Study 55 1.15 Exercises 59 1.1 Introduction Welcome to this book! We’re delighted to have this opportunity to convey the excitement of the world of computer systems. This is not a dry and dreary field, where progress is glacial and where new ideas atrophy from neglect. No! Computers are the product of the incredibly vibrant information technology industry, all aspects of which are responsible for almost 10% of the gross national product of the United States, and whose economy has become dependent in part on the rapid improvements in information technology. This unusual industry embraces innovation at a breathtaking rate. In the last 40 years, there have been a number of new computers whose introduction appeared to revolutionize the computing industry; these revolutions were cut short only because someone else built an even better computer. This race to innovate has led to unprecedented progress since the inception of electronic computing in the late 1940s. Had the transportation industry kept pace with the computer industry, for example, today we could travel from New York to London in a second for a penny. Take just a moment to contemplate how such an improvement would change society—living in Tahiti while working in San Francisco, going to Moscow for an evening at the Bolshoi Ballet—and you can appreciate the implications of such a change. 4 Chapter 1 Computer Abstractions and Technology Computers have led to a third revolution for civilization, with the information revolution taking its place alongside the agricultural and industrial revolutions. The resulting multiplication of humankind’s intellectual strength and reach naturally has affected our everyday lives profoundly and changed the ways in which the search for new knowledge is carried out. There is now a new vein of scientific investigation, with computational scientists joining theoretical and experimental scientists in the exploration of new frontiers in astronomy, biology, chemistry, and physics, among others. The computer revolution continues. Each time the cost of computing improves by another factor of 10, the opportunities for computers multiply. Applications that were economically infeasible suddenly become practical. In the recent past, the following applications were “computer science fiction.” Computers in automobiles: Until microprocessors improved dramatically in price and performance in the early 1980s, computer control of cars was ludicrous. Today, computers reduce pollution, improve fuel efficiency via engine controls, and increase safety through nearly automated driving and air bag inflation to protect occupants in a crash. Cell phones: Who would have dreamed that advances in computer systems would lead to more than half of the planet having mobile phones, allowing person-to-person communication to almost anyone anywhere in the world? Human genome project: The cost of computer equipment to map and analyze human DNA sequences was hundreds of millions of dollars. It’s unlikely that anyone would have considered this project had the computer costs been 10 to 100 times higher, as they would have been 15 to 25 years earlier. Moreover, costs continue to drop; you will soon be able to acquire your own genome, allowing medical care to be tailored to you. World Wide Web: Not in existence at the time of the first edition of this book, the web has transformed our society. For many, the web has replaced libraries and newspapers. Search engines: As the content of the web grew in size and in value, finding relevant information became increasingly important. Today, many people rely on search engines for such a large part of their lives that it would be a hardship to go without them. Clearly, advances in this technology now affect almost every aspect of our society. Hardware advances have allowed programmers to create wonderfully useful software, which explains why computers are omnipresent. Today’s science fiction suggests tomorrow’s killer applications: already on their way are glasses that augment reality, the cashless society, and cars that can drive themselves.  1.1 Introduction 5 Traditional Classes of Computing Applications and Their Characteristics Although a common set of hardware technologies (see Sections 1.4 and 1.5) is used in computers ranging from smart home appliances to cell phones to the largest personal computer (PC) A computer supercomputers, these different applications have distinct design requirements designed for use by and employ the core hardware technologies in different ways. Broadly speaking, an individual, usually computers are used in three dissimilar classes of applications. incorporating a graphics Personal computers (PCs) in the form of laptops are possibly the best-known display, a keyboard, and a form of computing, which readers of this book have likely used extensively. Personal mouse. computers emphasize delivery of good performance to single users at low costs and server A computer usually execute third-party software. This class of computing drove the evolution of used for running larger many computing technologies, which is merely 40 years old! programs for multiple Servers are the modern form of what were once much larger computers, and users, often simultaneously, are usually accessed only via a network. Servers are oriented to carrying sizable and typically accessed only workloads, which may consist of either single complex applications—usually a via a network. scientific or engineering application—or handling many small jobs, such as would supercomputer A class occur in building a large web server. These applications are usually based on of computers with the software from another source (such as a database or simulation system), but are highest performance and often modified or customized for a particular function. Servers are built from the cost; they are configured same basic technology as desktop computers, but provide for greater computing, as servers and typically storage, and input/output capacity. In general, servers also place a higher emphasis cost tens to hundreds of millions of dollars. on dependability, since a crash is usually more costly than it would be on a single- user PC. terabyte (TB) Originally Servers span the widest range in cost and capability. At the low end, a server may be 1,099,511,627,776 little more than a desktop computer without a screen or keyboard and cost a thousand (240) bytes, although communications and dollars. These low-end servers are typically used for file storage, small business secondary storage applications, or simple web serving. At the other extreme are supercomputers, which systems developers at the present consist of hundreds of thousands of processors and many terabytes started using the term to of memory, and cost tens to hundreds of millions of dollars. Supercomputers are mean 1,000,000,000,000 usually used for high-end scientific and engineering calculations, such as weather (1012) bytes. To reduce forecasting, oil exploration, protein structure determination, and other large-scale confusion, we now use the problems. Although such supercomputers represent the peak of computing capability, term tebibyte (TiB) for 240 bytes, defining terabyte they represent a relatively small fraction of the servers and thus a proportionally tiny (TB) to mean 1012 bytes. fraction of the overall computer market in terms of total revenue. Figure 1.1 shows the full Embedded computers are the largest class of computers and span the widest range range of decimal and of applications and performance. Embedded computers include the microprocessors binary values and names. found in your car, the computers in a television set, and the networks of processors that control a modern airplane or cargo ship. A popular term today is Internet of Things (IoT) which suggests may small devices that all communicate wirelessly over embedded computer A computer inside the Internet. Embedded computing systems are designed to run one application or another device used one set of related applications that are normally integrated with the hardware and for running one delivered as a single system; thus, despite the large number of embedded computers, predetermined application most users never really see that they are using a computer! or collection of software. 6 Chapter 1 Computer Abstractions and Technology kilobyte KB 103 kibibyte KiB 210 2% megabyte MB 106 mebibyte MiB 220 5% gigabyte GB 109 gibibyte GiB 230 7% terabyte TB 1012 tebibyte TiB 240 10% petabyte PB 1015 pebibyte PiB 250 13% exabyte EB 1018 exbibyte EiB 260 15% zettabyte ZB 1021 zebibyte ZiB 270 18% yottabyte YB 1024 yobibyte YiB 280 21% ronnabyte RB 10 27 robibyte RiB 2 90 24% queccabyte QB 10 30 quebibyte QiB 2 100 27% FIGURE 1.1 The 2X vs. 10Y bytes ambiguity was resolved by adding a binary notation for all the common size terms. In the last column we note how much larger the binary term is than its corresponding decimal term, which is compounded as we head down the chart. These prefixes work for bits as well as bytes, so gigabit (Gb) is 109 bits while gibibits (Gib) is 230 bits. The society that runs the metric system created the decimal prefixes, with the last two proposed only in 2019 in anticipation of the global capacity of storage systems. All the names are derived from the entymology in Latin of the powers of 1000 that they represent. Embedded applications often have unique application requirements that combine a minimum performance with stringent limitations on cost or power. For example, consider a music player: the processor need only to be as fast as necessary to handle its limited function, and beyond that, minimizing cost and power is the most important objective. Despite their low cost, embedded computers often have lower tolerance for failure, since the results can vary from upsetting (when your new television crashes) to devastating (such as might occur when the computer in a plane or cargo ship crashes). In consumer-oriented embedded applications, such as a digital home appliance, dependability is achieved primarily through simplicity— the emphasis is on doing one function as perfectly as possible. In large embedded systems, techniques of redundancy from the server world are often employed. Although this book focuses on general-purpose computers, most concepts apply directly, or with slight modifications, to embedded computers. Elaboration: Elaborations are short sections used throughout the text to provide more detail on a particular subject that may be of interest. Disinterested readers may skip over an Elaboration, since the subsequent material will never depend on the contents of the Elaboration. Many embedded processors are designed using processor cores, a version of a processor written in a hardware description language, such as Verilog or VHDL (see Chapter 4). The core allows a designer to integrate other application-specific hardware with the processor core for fabrication on a single chip. Welcome to the Post-PC Era The continuing march of technology brings about generational changes in computer hardware that shake up the entire information technology industry. Since the fourth edition of the book, we have undergone such a change, as significant in the  1.1 Introduction 7 1600 Smart phone 1400 1200 1000 Millions 800 600 Cell phone 400 (excluding smart phones) PC (excluding tablets) 200 Tablet 0 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 FIGURE 1.2 The number manufactured per year of tablets and smart phones, which reflect the post-PC era, versus personal computers and traditional cell phones. Smart Personal mobile phones represent the recent growth in the cell phone industry, and they passed PCs in 2011. PCs, tablets, and devices (PMDs) are traditional cell phone categories are declining. The peak volume years are 2011 for cell phones, 2013 for PCs, and 2014 for tablets. PCs fell from 20% of total units shipped in 2007 to 10% in 2018. small wireless devices to connect to the Internet; past as the switch starting 40 years ago to personal computers. Replacing the PC they rely on batteries for is the personal mobile device (PMD). PMDs are battery operated with wireless power, and software is installed by downloading connectivity to the Internet and typically cost hundreds of dollars, and, like PCs, apps. Conventional users can download software (“apps”) to run on them. Unlike PCs, they no longer examples are smart have a keyboard and mouse, and are more likely to rely on a touch-sensitive screen phones and tablets. or even speech input. Today’s PMD is a smart phone or a tablet computer, but tomorrow it may include electronic glasses. Figure 1.2 shows the rapid growth over Cloud Computing refers to large collections time of tablets and smart phones versus that of PCs and traditional cell phones. of servers that provide Taking over from the conventional server is Cloud Computing, which relies services over the Internet; upon giant datacenters that are now known as Warehouse Scale Computers (WSCs). some providers rent Companies like Amazon and Google build these WSCs containing 50,000 servers and dynamically varying then let companies rent portions of them so that they can provide software services to numbers of servers as a PMDs without having to build WSCs of their own. Indeed, Software as a Service (SaaS) utility. deployed via the Cloud is revolutionizing the software industry just as PMDs and WSCs Software as a Service are revolutionizing the hardware industry. Today’s software developers will often have a (SaaS) delivers software portion of their application that runs on the PMD and a portion that runs in the Cloud. and data as a service over the Internet, usually via a thin program such as a What You Can Learn in This Book browser that runs on local Successful programmers have always been concerned about the performance of client devices, instead of their programs, because getting results to the user quickly is critical in creating binary code that must be installed, and runs wholly popular software. In the 1960s and 1970s, a primary constraint on computer on that device. Examples performance was the size of the computer’s memory. Thus, programmers often include web search and followed a simple credo: minimize memory space to make programs fast. In the social networking. 8 Chapter 1 Computer Abstractions and Technology last two decades, advances in computer design and memory technology have greatly reduced the importance of small memory size in most applications other than those in embedded computing systems. Programmers interested in performance now need to understand the issues that have replaced the simple memory model of the 1960s: the parallel nature of processors and the hierarchical nature of memories. We demonstrate the importance of this understanding in Chapters 3 to 6 by showing how to improve performance of a C program by a factor of 200. Moreover, as we explain in Section 1.7, today’s programmers need to worry about energy efficiency of their programs running either on the PMD or in the Cloud, which also requires understanding what is below your code. Programmers who seek to build competitive versions of software will therefore need to increase their knowledge of computer organization. We are honored to have the opportunity to explain what’s inside this revolutionary machine, unraveling the software below your program and the hardware under the covers of your computer. By the time you complete this book, we believe you will be able to answer the following questions: How are programs written in a high-level language, such as C or Java, translated into the language of the hardware, and how does the hardware execute the resulting program? Comprehending these concepts forms the basis of understanding the aspects of both the hardware and software that affect program performance. What is the interface between the software and the hardware, and how does software instruct the hardware to perform needed functions? These concepts are vital to understanding how to write many kinds of software. What determines the performance of a program, and how can a programmer improve the performance? As we will see, this depends on the original program, the software translation of that program into the computer’s language, and the effectiveness of the hardware in executing the program. What techniques can be used by hardware designers to improve performance? This book will introduce the basic concepts of modern computer design. The interested reader will find much more material on this topic in our advanced book, Computer Architecture: A Quantitative Approach. What techniques can be used by hardware designers to improve energy efficiency? What can the programmer do to help or hinder energy efficiency? What are the reasons for and the consequences of the switch from sequential processing to parallel processing? This book gives the motivation, describes multicore the current hardware mechanisms to support parallelism, and surveys the microprocessor new generation of “multicore” microprocessors (see Chapter 6). A microprocessor containing multiple Since the first commercial computer in 1951, what great ideas did processors (“cores”) in a computer architects come up with that lay the foundation of modern single integrated circuit. computing?  1.1 Introduction 9 Without understanding the answers to these questions, improving the performance of your program on a modern computer or evaluating what features might make one computer better than another for a particular application will be a complex process of trial and error, rather than a scientific procedure driven by insight and analysis. This first chapter lays the foundation for the rest of the book. It introduces the basic ideas and definitions, places the major components of software and hardware in perspective, shows how to evaluate performance and energy, introduces integrated circuits (the technology that fuels the computer revolution), and explains the shift to multicores. In this chapter and later ones, you will likely see many new words, or words that you may have heard but are not sure what they mean. Don’t panic! Yes, there is a lot of special terminology used in describing modern computers, but the terminology actually helps, since it enables us to describe precisely a function or capability. In addition, computer designers (including your authors) love using acronyms, which are easy to understand once you know what the letters stand for! acronym A word To help you remember and locate terms, we have included a highlighted definition constructed by taking the of every term in the margins the first time it appears in the text. After a short initial letters of a string of words. For example: time of working with the terminology, you will be fluent, and your friends will RAM is an acronym for be impressed as you correctly use acronyms such as BIOS, CPU, DIMM, DRAM, Random Access Memory, PCIe, SATA, and many others. and CPU is an acronym To reinforce how the software and hardware systems used to run a program will for Central Processing affect performance, we use a special section, Understanding Program Performance, Unit. throughout the book to summarize important insights into program performance. The first one appears below. The performance of a program depends on a combination of the effectiveness of the Understanding algorithms used in the program, the software systems used to create and translate Program the program into machine instructions, and the effectiveness of the computer in executing those instructions, which may include input/output (I/O) operations. Performance This table summarizes how the hardware and software affect performance. Hardware or software Where is this component How this component affects performance topic covered? Algorithm Determines both the number of source-level Other books! statements and the number of I/O operations executed Programming language, Determines the number of computer instructions Chapters 2 and 3 compiler, and architecture for each source-level statement Processor and memory Determines how fast instructions can be Chapters 4, 5, and 6 system executed I/O system (hardware and Determines how fast I/O operations may be Chapters 4, 5, and 6 operating system) executed 10 Chapter 1 Computer Abstractions and Technology Check Check Yourself sections are designed to help readers assess whether they Yourself comprehend the major concepts introduced in a chapter and understand the implications of those concepts. Some Check Yourself questions have simple answers; others are for discussion among a group. Answers to the specific questions can be found at the end of the chapter. Check Yourself questions appear only at the end of a section, making it easy to skip them if you are sure you understand the material. 1. The number of embedded processors sold every year greatly outnumbers the number of PC and even post-PC processors. Can you confirm or deny this insight based on your own experience? Try to count the number of embedded processors in your home. How does it compare with the number of conventional computers in your home? 2. As mentioned earlier, both the software and hardware affect the performance of a program. Can you think of examples where each of the following is the right place to look for a performance bottleneck? The algorithm chosen Komputacija, fib seq. The programming language or compiler Game dev (Pyth vs. C#) The operating system Mobile/Server The processor Gaming The I/O system and devices Flight system Seven Great Ideas in Computer 1.2 Architecture We now introduce seven great ideas that computer architects have invented in the last 60 years of computer design. These ideas are so powerful they have lasted long after the first computer that used them, with newer architects demonstrating their admiration by imitating their predecessors. These great ideas are themes that we will weave through this and subsequent chapters as examples arise. To point out their influence, in this section we introduce icons and highlighted terms that represent the great ideas and we use them to identify the nearly 100 sections of the book that feature use of the great ideas.