Computer Systems: A Programmer’s Perspective (2nd Edition)

I picked up Computer Systems: A Programmer’s Perspective (2nd Edition) by Randal Bryant and David O’Hallaron while searching for a stimulating book on computer architecture or operating systems. CSAPP turned out to be a good find since it is aimed at the intersection of computer architecture, computers systems and OS. Using practical examples and problems the book walks the student through all the hardware and software knowledge that is required to understand how a program comes to life on a computer.

Assume a student compiles a Hello world program and runs it. A plethora of hardware features and a large set of software come together to make this simple magic possible. Software like compiler, assembler, linker, loader, libraries and operating system kernel help to compile and load the program. Hardware features like hard disk, main memory, controllers, buses, cache and the processor bring the program to life. Also, hardware and software need to also act in tandem in virtual memory, system calls and interrupt handling to make the execution of a program scalable, efficient, fast and safe. This book argues that a good programmer needs to be aware of all the afore mentioned concepts and these are what the book tries to cover.

Some notes about this book:

  • The book is structured as a workbook. You read a concept, solve a problem or experiment with a program that illustrates it and then move on to the next concept. There are trivia, blurbs and practical information about IA32 (Intel) architecture and Linux where-ever necessary. This ensures that the book remains grounded in reality and never feels dry to study.
  • The authors have tried their best to introduce as many of modern multiprocessor concepts as possible in a practical way. There is a lot missing, for example, super-scalar architecture and out-of-order execution. However, the programmer interested in these details can easily learn about them with a book like Inside The Machine.
  • The chapters on memory hierarchy and virtual memory are the real treasure in this book. The sections on cache here and in Inside The Machine stand head-to-head as the most practical introductions to the topic.
  • Virtual memory is an important concept, but sadly it gets short shrift in computer science education. This is because it requires the OS and hardware to work together and those subjects are typically covered by two different courses or textbooks in university. Not having to deal with such caste boundaries, this book is able to show the student how virtual memory is brought to life.
  • The book gets a bit vague towards the end. I was not interested in and did not see any benefit for this book to touch on areas of system I/O, network programming and concurrency.

I am happy to conclude that CSAPP is a stimulating book to study and work through. This book covers all the knowledge that a good programmer needs to understand how his program executes upon the OS and CPU and how to make it efficient, fast and scalable. I highly recommend Computer Systems: A Programmer’s Perspective for anyone who feel they need a better grasp of these ideas.

Advertisements

Programming Massively Parallel Processors

The next step for a CUDA newbie after CUDA by Example would naturally be the book Programming Massively Parallel Processors by David Kirk and Wen-mei Hwu. They taught the first course on CUDA at UIUC for a few semesters and this book is based on its lecture notes. I had used their lecture notes and videos when I first learnt CUDA.

To write any CUDA application that moulds the problem optimally to the CUDA architecture requires the programmer to think very differently from programming on a CPU. Using a matrix multiplication example, the authors walk the student through many levels of improvement. The authors introduce the different facets of the architecture and end up improving the performance of the solution by as much as two orders of magnitude in the end.

All the concepts of the CUDA architecture are covered: the thread-block-grid hierarchy, the global-shared-local memories and barrier synchronization. Details of the warps and the warp scheduler are explained. Since most CUDA applications are scientific, there is an entire chapter on the floating point format. This chapter gives a practitioner’s perspective that I found to be more useful than the popular but obscure What every computer scientist should know about floating-point arithmetic. There are two chapters on application case studies, which are mostly useless since one cannot understand the application intimately enough to draw any lessons from it.

CUDA runs only on NVIDIA devices. OpenCL is its twin that is designed to be used on all kinds of CPU and GPU processors. The authors have thrown in a chapter on OpenCL for folks who need to transition to it. OpenCL is exactly like CUDA, except that it does not have an equivalent of the CUDA Runtime API. So, the programmer ends up spending some time building the scaffolding required to run his kernels.

Programming Massively Parallel Processors is a easy book to study from. It should be accessible to any intermediate-to-expert programmer. Newbies can check out CUDA by Example before studying this book. I do wish this book covered some information on cache configuration, launch bounds, profiling, compiler options and other intimate details which one ends up using to squeeze out the last bit of performance. Currently, I do need to fall back onto the CUDA Programming Guide for such information. The book is also a wee bit outdated since the Fermi architecture is not well covered and the new Kepler architecture has already been released.

Aardvark’d

A few years ago, Joel Spolsky decided to show the world how software is created. He invited a documentary crew to film the summer interns at his company Fog Creek create what was code-named Project Aardvark. It would be later branded as the product Copilot. This documentary was named Aardvark’d: 12 Weeks with Geeks and sold on DVD. The entire movie is now available on Youtube here.

When there is some problem on their computer, a lot of people ask their family or friends to help fix it. Most of the time the helpers are physically far away. So, Project Aardvark set about creating a website which could connect the seeker and the helper, the helper could view and interact with the seeker’s desktop and hopefully fix the problem.

Aardvark’d follows the four interns: three programmers and one marketer as they go about learning and creating this software. I have nothing more to say because this Aardvark’d is super-boring, watching paint dry would be more exciting than this. Neither do we get to see the daily hustle-bustle life of a Fog Creek employee nor are we given the technical insight into Project Aardvark. Instead we are fed shots of the interns sitting at their computer working, some stupid contests and some talking points from Joel Spolsky and Paul Graham.

Aardvark’d is a mega-bore of a documentary and I highly recommend avoiding spending the one hour or so of your life on it. Just watch the trailer, believe me when I say that there is absolutely nothing more to see in the movie than what is shown in the 2 minutes of that trailer.

Algorithms (4th Edition)

One of the biggest roadblocks in studying Computer Science is the popular tome Introduction to Algorithms by CLRS. It is the most common textbook for introductory algorithms courses at universities. While it is a great book for learning analysis of algorithms and as a reference, it is a horrible book to learn algorithms. I am pretty sure a great many number of students have been turned off from and have fear of algorithms since this book was their first look at algorithms. Thankfully, there is an excellent cure for this problem.

I recently re-discovered the wonderful world of microprocessors with the book Inside the Machine. It made me realize that there must be books out there on every topic that are more intuitive, stimulating and illustrative than the status quo. I started to look for such a book on algorithms. After checking out almost every textbook on this topic out there, I discovered Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne. And, I fell in love! 😀

This is an introductory textbook for algorithms. The book covers all the most important algorithms on sorting, searching, graphs and strings. Real-world problems and historical perspectives are provided at the beginning of every chapter to motivate the algorithm. After that a skeleton of a Java class is sketched out with the API that is demanded by the problem. The authors then show why other algorithms studied earlier in the book cannot solve this problem. Using these failings as a key, the user is introduced to a new concept that can solve the problem. This is then advanced to the final algorithm with full working Java code to fill out the skeleton API. Finally, many propositions about the time and space complexity of the algorithm are put forward with their proofs.

I never thought that I would find an Algorithms book so addictive that I would study it cover to cover! What is so special about this book? There are a few reasons for that. First are the illustrations. There are more illustrations in this book than there are pages (yes, unbelievable!). The authors have taken great pains to tear apart the difficulty in understanding how and why an algorithm works. And then the code: this is the simplest, most elegant real code ever written for algorithms. Do red-black trees haunt your dreams? This book banishes that fear by elegantly using 2-3 trees and morphing that understanding to red-black trees. And finally the proofs. Every proposition and its intuitive proof is such a joy to work through and finally understand that it gives one a high!

In my humble opinion, Algorithms (4th Edition) by Sedgewick and Wayne is the best introduction to algorithms. There is quite simply no other book out there that will make you fall in love with algorithms like this one. My only advise is that you make sure you understand every illustration and concept in the book. That goes a long way in giving you an intuitive feel of the algorithm. If you are picking up this book, do remember to check out the book’s website. It contains a lot of supporting content, including code and errata. (I am honored to have been able to contribute quite a few errata there 😉 ). The final icing on the cake is that Sedgewick and Wayne will soon be teaching a two-part Algorithms course based off this book at Coursera soon!

Inside the Machine

I find most of the celebrated books on computers to be extremely dry. Though they are packed with important information, they make no effort to engage the reader and fail to give an intuitive understanding of the subject. Jon Stokes is that rare breed of technology writer whose book Inside the Machine is so edge-of-the-seat absorbing that it is hard to believe that it is about computer architecture and microprocessors. Stokes is the co-founder of the Ars Technica website, one of my favorite haunts, where he has written in-depth articles about processors since 1998.

The first 4 chapters of the book deal with the basic architecture and execution steps of a microprocessor, pipelining and superscalar execution. Stokes takes the reader through 4 conceptual views of the CPU: (1) as a calculator (2) as a computer reading instructions and data from memory (3) the programmer’s view of the processor, also known as the Instruction Set Architecture (ISA) and (4) the actual microarchitecture of the chip. In here and in the rest of the book, Stokes uses lots of colorful illustrations to depict how the CPU is structured and how it behaves while processing instructions. Without a doubt, these are the most engrossing diagrams I have seen of computer architecture and they are easy to grasp and remember. Add to this the countless wonderful analogies that Stokes describes in the text that help to see the topic from many different viewpoints.

The rest of the book picks many popular processors and uses each to introduce a contemporary technique or concept. What follows are the items I found interesting in this part of the book. Chapter 5 deals with the Pentium and Pentium Pro (P6) microarchitectures, using them to explain branch prediction, dynamic scheduling and micro-operation decoding. Chapter 6 uses PowerPC processors to talk about RISC and its typical microarchitecture. Chapter 7 introduces the Pentium 4 (NetBurst) microarchitecture whose ginormous 20-stage pipeline I loathed and whose trace cache I thought was a really cool idea. Chapter 8 covers vector support: MMX, SSE and SSE2 in Intel and AltiVec in PowerPC processors. Chapter 9 talks about 64-bit computing, tells the story of Intel’s failure to push a new ISA through the 64-bit Itanium and how AMD stole the show with its x86-64. Chapter 11 is oddly placed towards the end and it deals with caching. Special mention goes to the kick-ass analogies and delightful illustrations of the types of caching and caching hierarchy here. The final Chapter 12 brings the reader to today, with the power-saving architecture of Pentium M and the Core 2 Duo multi-threading architecture.

Inside the Machine is an absolute must-read for anyone who works with computers. I only wish the ARM microarchitecture, which is now popular on handheld devices, was covered in the book. Jon Stokes really succeeds in giving the reader a big-picture view of the internal structure and workings of today’s microprocessors. Do not be surprised if this book turns you into a processor geek who follows the microarchitectures of upcoming processors. Inside the Machine is the kind of book on science and technology that I love to read and cherish.

Version Control by Example

Look what arrived in my snail-mail last weekend: a free dead-tree copy of Version Control by Example written by Eric Sink! 😀 I know Eric Sink from his Source Control HOWTO, a series of fantastic introductory posts on the subject. In this book, Eric Sink gives a simple introduction to version control systems (VCS), the common operations in a VCS and he illustrates these operations in Subversion, Mercurial, Git and Veracity. The book ends with chapters that dip into the internal workings of distributed VCS (DVCS), common workflows of using DVCS and best practices.

Eric Sink is a delightful writer with the talent to make technology accessible and fun. (He reminds me of Tanenbaum, whose textbooks I love for the same reason.) I especially loved his analogy of VCS to a multi-threaded program, which he uses all through the book. Before getting into examples, he provides a solid debate on the pros and cons of centralized VCS (CVCS) vs. DVCS. After that, he shows a sample workflow between two programmers, one in the USA and other in UK, who have to collaborate on the code of a game using a VCS. He uses this scenario four times, once for each VCS he illustrates in the book. I used to use Subversion for my personal work before and my current life completely revolves around Mercurial. So, I loved going through the chapters on these VCS, it acted as a good revision. I skipped the chapter on Git, after seeing (yet again) how it makes every action more complicated than necessary. The final tool is Veracity, an open-source DVCS created by SourceGear which is Eric Sink’s company. It adds some extra features needed by commercial users that are not provided in most free DVCS.

Version Control by Example is a super-fast read. It is a practical book, there is nothing to mull or chew over here. If you are either thinking about using a VCS (oh, you must!) or thinking about switching from a CVCS to a DVCS, please pick up this book. The dead-tree version has gaudy page design and is printed on glossy paper. But, once you get over these distractions, the content is good. The book is also available online here.

Windows Sysinternals Administrator’s Reference

I have been a huge fan of the Sysinternals tools ever since I switched to Windows for my work. These tools give the ability to peek into every heartbeat of Windows, and you develop an appreciation for the beauty and complexity of this operating system. So, it is no wonder that I eagerly awaited the Windows Sysinternals Administrator’s Reference once Mark Russinovich announced it earlier this year. Written by Mark and Aaron Margosis, this book helps readers use the Sysinternals tools effectively to understand the working internals of Windows, and to diagnose and fix problems.

Part 1 talks about the history of Sysinternals tools and gives a brief description of administrator privileges, user-kernel mode, processes, threads, jobs and handles in Windows. Though designed similar to other operating systems, Windows is a different beast. This chapter is a highly educational read to understand just how it differs and to catch up on the Windows OS jargon. The first 3 chapters of Part 2 are worth the price of the book itself — they go deep into the capabilities of Process Explorer, Process Monitor and Autoruns. Having learnt these 3 tools one can start to live comfortably with Windows. (Well, almost!) The rest of Part 2 covers the other Sysinternals tools, most of which I do not use. Part 3 is a compendium of many troubleshooting mystery cases, which were solved by using Sysinternals tools. Followers of Russinovich’s blog or talks will be familiar with most of these since he has written and presented about them before. Written like a detective mystery, each of these are sure to be engaging to geeks.

Windows Sysinternals Administrator’s Reference is a good companion to the Windows Internals books, providing the much needed practical information and tools to get down-and-dirty with the internals of Windows. Like his blog and talks, Russinovich’s narrative here is entertaining and educational to read. The book completely pays for itself with just Part 1 and the first 3 chapters of Part 2. This book is a must for everyone who uses Windows as their primary operating system.