Lab 1: Computer Abstraction Hierarchy
People mostly take for granted the enormous behind-the-curtain technology that allows their favorite apps to work. Unit 4 gave a first glimpse at that technology for apps that rely on the Internet, with an abstraction hierarchy that includes application protocols, TCP, IP, and link layer (hardware interface) protocols. There are even more levels of abstraction inside your computer. The purpose of this lab is to tour these levels of abstraction, from high (application programs) to low (transistors).
Keep this entire lab light. Throughout the lab, there's much that can be expanded. Some students will want more, so additional interesting information is tucked away in optional reading sections that hide detail that's not needed for the AP exam but may appeal to student curiosity, like this:
Why tour that whole range of abstraction?
Most computer engineers specialize in one level of abstraction, spending their entire careers at that level. But the engineers who really change the nature of the technology are always aware of the latest developments at levels above and below their own work, because those other levels exert pressure on the design of any individual level.
For example at the start of the 1970s, computer architectures were mostly designed to provide a large and flexible set of machine language instructions. By the end of the decade, instruction sets were smaller and simpler. Why? Two reasons:
- Pressure from above. In the early '70s, a lot of programming was done by human programmers writing machine language (using assembly language notation). By the end of the decade, compiler technology had improved enough for pretty much everyone to trust compilers to produce efficient programs. For a compiler, simple instruction sets make it easier to optimize programs.
- Pressure from below. In the early '70s, processor circuitry was much faster than the computer's memory, so it made sense to get as much computation as possible out of each instruction loaded from memory. By the end of the decade, multilevel cache memory technology made memory references about as fast as processor cycles, so the way to make programs efficient was to load instructions from memory as fast as possible, each instruction doing only as much computational work as can fit before the next instruction arrives.
The details of this example aren't important for you or your students to learn; the point of the story is to motivate you in familiarizing students with the entire hierarchy from top to bottom.
Not all abstraction levels are equally important. We single out two: the software abstraction that allows a computer to solve different problems without having to be physically rewired for each one, and the digital abstraction that allows hardware designers to pretend that a transistor is always either fully on or fully off.
Abstraction has many nuanced meanings in computer science. At the end of each page that deals with abstraction, ask students, "What does abstraction mean on this page?" and consider keeping a running log.
There is a lot of reading in this lab. Find a strategy that works for your class. You might have students take turns reading, or you might have all students read a section silently and then ask one or two students to summarize out loud.
Pacing
The 10 lab pages could be split across 4–8 days (
180–360 minutes). Expected times to complete follow:
Prepare
-
Hardware Teardown. The ideal introduction to this unit is not mentioned in the student materials to leave teachers free to choose, but it's exciting and instructive for students in groups to take apart an actual (old) computer.
- Materials: Preferably, one computer per four students or so, but even just one computer with the whole class watching is still great. You don't need a working computer, but working is better; the thrill when they put it back together and it still works is fantastically motivating. In most places, it's no longer legal to dump old computers in the garbage, so nonworking computers can often be obtained free from recycling centers. Working antiques (i.e., over ten years old) can be bought very cheaply at used computer stores or recycling centers. If your school is buying new computers, you may be able to grab old ones before they leave the building.
- Instructions: ifixit.com is one good source of teardown guides, such as this example: Compaq Deskpro EN Teardown. You can perhaps find one specifically for the particular model of old computer you salvaged. It doesn't have to be on their site; just do a web search for your computer model and the word "teardown."
-
Safety:
- Do not tear down a laptop the first time you try this activity. Laptops are very dense, and parts are often held together with glue. People do tear down laptops and even get them working again, but get some experience with desktop/tower computers first. Also, laptop batteries have been known to catch fire.
- Do not tear down a cell phone in class ever. Besides sharing all the problems of laptops, they have highly explosive and flammable batteries.
- Grounding. If you want the computer to work afterward, whoever works on the electronics should be grounded before opening the case. This is to protect the electronics; the person is safe with or without grounding. Pros use a metal strap wrapped around their wrist with a wire clamped to a water pipe. Touching the metal frame of any grounded object—one that has a three-prong power cord (and is plugged in)—will do. Look up "grounding while working on a computer" to learn more.
Lab Pages
-
Page 1: Abstraction Inside the Computer.
-
Learning Goals:
- Understand that the computer abstraction hierarchy includes three major domains: software, digital, and analog.
- Understand that these domains are separated by the abstraction of a program and the abstraction of data being represented digitally, as ones and zeros.
- Understand that the software and digital domains each include a sub-hierarchy of abstraction.
-
Tips:
-
Don't worry about students memorizing the specific levels of abstraction. The main points are:
- Software lets you control a computer, abstracting away the actual machine (the program abstraction); and "zeros and ones" are an abstraction over the way transistors really work (the digital abstraction).
- The levels of abstraction in the software domain are different programs: the application programs are written in a programming language, and use libraries, and interface with the operating system to control the hardware.
-
By contrast, the levels of abstraction in the digital domain are different ways of thinking about the same physical object. Envision yourself holding a processor chip in your hand, and asking yourself:
- What's it for? (architecture)
- What are the major structures inside it? (components)
- What's physically inside the plastic case? (integrated circuits)
- What are the primitive building blocks of a digital circuit? (logic gates)
-
Page 2: The Software Domain: Applications.
-
Learning Goals:
- Understand that apps are not the complete story about software but rather the tip of the iceberg, supported by a huge collection of other software.
- Review what students already know about software but with an emphasis on creating rather than on consuming.
-
Tips:
- Here and there in the litany of software uses are bad ones: spreading fake news, making public personal info such as your political views, malware. Don't over-emphasize these, but also mention at least one if one doesn't come up naturally in discussion.
- Consider reading and discussing the chapter "Propaganda Machine" (pages 68–83) in Weapons of Math Destruction: How big data increases inequality and threatens democracy by mathematician Cathy O'Neil. It gives examples of destructive sides of "targeted advertising," and mentions a school in Brooklyn that helped expose one such destructive example.
-
Page 3: The Software Domain: Programming Languages.
-
Learning Goals:
- Understand that some languages are at a higher level of abstraction than others.
- Understand that in almost all situations, a higher level of abstraction is better, both for safety against bugs and for ease of programming.
- Learn that, nevertheless, all general-purpose languages are equivalent in the sense that an algorithm expressible in one language is expressible in any.
-
Tips:
- Automatic memory management (garbage collection) is perhaps the most important example of abstraction in a programming language. Here is some history you could share with students: when garbage collection was introduced in Lisp in 1952, mainstream programmers ridiculed it as being too slow. But since it was used in Java in 1995, every new programming language has included it. Today it would be engineering malpractice to use a language that allows programmers any control over memory allocation. It's easy to make that case, because of a long history of memory management disasters in old software.
- Students who've been exposed to other programming languages may make comparisons between languages that are almost always really about the libraries that they are comparing, e.g., "JavaScript is good because you can make web pages in it." That's because the JavaScript in web browsers has a web-page library, not because of the language itself. This is addressed on the next student page.
-
Page 4: The Software Domain: Libraries.
-
Learning Goals:
- Appreciate that anyone who writes an application program is building on the work of programmers who built libraries that do many of the hard parts.
- Understand that software libraries are excellent examples of abstraction because they hide vast amounts of complexity from the programmers while providing them with versatile utility.
-
Page 5: The Software Domain: Operating Systems.
-
Learning Goals:
- Understand that an operating system (Linux, macOS, Windows, etc.) is actually a package of hundreds of programs including applications (Finder, TextEdit, etc.) and libraries, along with one special program: the kernel that manages task scheduling.
- Tips:
- What does this page have to do with the College Board AP Framework? The AP Framework doesn't explicitly mention the operating system or its kernel, but some EKs are indirectly about the kernel, such as "5.2.1G A process may execute by itself or with other processes." If one processor is running multiple processes at once, there has to be a scheduler that switches the hardware's attention among the processes. That's part of the kernel. Similarly, the kernel is in charge of security in the file system.
-
Page 6: The Digital Domain: Architecture.
-
Learning Goals:
- Understand that the job of a computer architecture (essentially a machine language) is to enable the software abstraction by specifying how to interpret a binary sequence as representing an algorithm.
- Understand that the architecture is an interface specification, a document you can read, rather than an actual piece of hardware; many different hardware devices might implement the same architecture, e.g., at different speeds and costs.
-
Tips:
- You may want to discuss the crucial invention of the stored-program architecture made by Charles Babbage with Ada Lovelace, long before electronic circuit devices. Focus on the stroke of genius that Babbage's Analytical Engine was: the complete concept of programs and a programming language, with conditionals and loops, made long before the low-level enabling technology was available (first relays in the 1930s, then vacuum tubes, then finally transistors). Long before Babbage, there were machines that performed computations, but they had one particular computation built in, or at best (as in Babbage's Difference Engine) a particular family of computations with a particular one selected by rearranging parts of the hardware. What was required for the modern idea of a computer was the idea of a computer program, as a kind of data—just like numbers—but with codes telling the machine what to do next. "Program as data" may seem like an esoteric idea when it's encountered in the form of higher-order functions, but without that idea, there couldn't be programmable computers at all.
There are several optional topics hidden in yellow boxes at the end of the page.
- The first (PC/Mac architecture) makes the point that pretty much all computers these days (except for phones and tablets) use the same Intel x86 architecture. That wasn't always true. PCs have always been Intel-based, but the Mac started out using the Motorola 68000 architecture, then the Apple-specific PowerPC architecture, before switching to x86. If you're interested, these are further questions you can suggest as research topics:
- Why did desktop/laptop computers end up with every brand using a single architecture?
- Why don't phones and tablets use the x86 architecture?
- The next three topics provide similar explorations of smartphones, Internet-of-things architectures, and hobbyist computers. None of this material is required for the AP, but looking at one or two specific examples can make the idea of an architecture more concrete.
- The last topic is about computer architecture in general. Second sourcing is just an interesting side point about why all computers use x86, but the note about memory hierarchy is helpful understand more fully the AP's standards about memory. Specifically, the AP wants students to know that the components of a computer include the processor and the memory, but these days, the most important parts of the memory—the level-1 and level-2 caches—are part of the same chip as the processor. One reason for this is that today's processors are fast enough so that the speed of electrons through wire matters; the fastest memory has to be mere nanometers away from the processor.
-
Page 7: The Digital Domain: Components.
-
Learning Goals:
- Learn about different components of a computer, especially: the processor, which carries out the steps of a program; and memory, which holds both the program and its data.
-
Tips:
- The relevant AP CSP EK talks about the traditional idea of three components: processor, memory, and input/output. Students, on the other hand, are likely to list the things they can see and feel: the keyboard, the screen, the printer, the backup disk, and so on. In traditional terms, all those are lumped together under I/O devices. And it's the interface hardware inside the box that really counts as the I/O component.
- The most important components to understand are the processor, which carries out the steps of a program, and the memory, which holds both the program and its data. (But in a modern computer, part of the memory—the level-1 and level-2 caches—are in the same chip as the processor. The processor registers are also a very small memory.)
- The bulk of this page is about the student view of components, including the things outside the box. This is because students know about these things and they or you can point to the actual things. The exercise about buying a new computer is an attempt to bring the focus into the AP idea of components, because what makes one computer model different from another are the processor width and speed and the memory size and speed. (A third factor is the amount of disk or flash "solid state disk" memory.)
- If you have students who are eager for extra work, you could have them research how USB (Universal Serial Bus) works. Here's some history that you may want to share with students: not too long ago, there were specific connectors on the back of the computer (or on the side, if it's a laptop) for each kind of external device. Today, though, all of the external devices are likely to connect to the computer through one uniform interface: USB (Universal Serial Bus). So there's a single piece of hardware inside the machine that knows how to talk to any USB device, and then the differences among the external devices are all handled in software.
- If students raise questions to which you don't know the answer, suggest they look it up online and tell the class the answer next class meeting.
-
Page 8: The Digital Domain: Integrated Circuits.
-
Learning Goals:
- Realize that ICs are all about miniaturization and it was their invention that got us from the big-as-a-room computers to modern desktop and smaller computers.
- Consider the history of conflict materials.
-
Tips:
- Take a moment to give students a sense of the magnitudes involved. If 10 billion transistors fit on a one-inch square, the length in meters of one transistor is about 254nm. The length of a simple (inorganic) molecule is around 10nm, so we aren't yet pushing the size limit for chip density—it's heat that limits us right now. But transistors will never be as small as one molecule; to get to that size we'll need a different underlying technology. This idea is covered in more detail on Lab 3 Page 2: Moore's Law under Limitations to Moore's Law.
- The subject of conflict minerals used in everyday technology can be an upsetting one as it involves terrible human rights violations. As part of understanding the social implications of computing, students are asked to research this topic. Before presenting this page to students, research the topic yourself so that you are prepared for students' reactions to this harsh reality. At a minimum, read the two articles quoted on the student page, which present both the issues and some efforts to address them. Bear in mind, though, that these pages were written by Intel's PR department, so there's likely more to the story.
-
Page 9: The Digital Domain: Logic Gates.
-
Learning Goals:
- Understand that computer circuitry is built out of small circuits ("gates") that compute Boolean functions.
- Understand that any computable function can be expressed by combining logic gates.
-
Tips:
- It's good if students see at least one truth table (these are hidden in a yellow box), so they get the idea that the table completely defines a Boolean function. This is unlike the addition and multiplication tables they learned in elementary school, which define the function only for single-digit inputs; a Boolean function has only two possible values for each input, whereas an arithmetic function has infinitely many possible values for each input.
- Some students may argue that ICs are less abstract than logic functions. They're right if you think of "IC" and "function" as abstract (in the ordinary sense) concepts. We put the topics in this order because an IC is designed with logic gates as its building blocks. (This is one reason why students don't need to memorize the specific abstraction levels within the domains.)
- Extension activity: Since a truth table completely defines a Boolean function, and you can construct every possible truth table for a two-input Boolean function (this is a good Take It Further exercise), it follows that there are only finitely many Boolean functions—in fact, only 16 of them. This makes for a nice mini-research project: How many of the 16 are useful? How many have names? Are they all commutative? Are they all associative? And so on.
- The optional project for building an adder circuit with logic gates show how functions with multi-bit outputs can be made out of single-bit-output Boolean functions.
-
Page 10: The Analog Domain: Transistors.
-
Learning Goals:
- Understand the distinction between digital and analog.
- Understand that the digital abstraction is made possible by the bistable (a term students don't need to learn) nature of the transistor (the two flat regions in its input-output curve) and that it still takes engineering effort to ensure that each transistor stays in one of the flat regions.
-
Tips:
- Students who have studied electronics may notice that the usual way transistor curves are drawn shows output current vs. input voltage. This simplification is also correct and more easily conveys the essential idea.
Solutions