Posts

Jeremy and Muli remind me that x86-class CPUs refill a missed TLB entry in hardware. That’s what I get for rambling at midnight! On these CPUs, the hardware walks the page tables directly when a miss occurs. The operating system still gets involved during context switches, to keep the page tables and TLB consistent; and it also shoots down individual TLB entries when messing with memory mappings. In my puny and lame defence, most RISC CPUs (you know, the ones that nobody uses any more) trap to the operating system when a TLB miss occurs, and do the refilling in software. (A few, like SPARC, have an auxiliary cache that’s bigger than the TLB, to speed up software reloads.) Jeremy also asked if a TLB lookup and L1 cache lookup can happen in parallel. As he points out, they can’t if the L1 cache contains physical addresses (which is called physical indexing). L1 caches that are virtually indexed do show up, though, because they allow the TLB lookup to occur in parallel with the L1 cache lookup. The machinery is more complicated due to the need to account for a single physical address having multiple virtual addresses mapping to it. As far as I know, only the HP PA and AMD Athlon, both of which are defunct, have virtually indexed caches.

In an earlier post, I briefly discussed the oprofile system profiler. I was going somewhere with that; here’s another step along the path. Modern CPUs that use virtual memory have to be able to turn virtual addresses into physical addresses efficiently. While a userspace process operates on virtual addresses, accessing any part of the memory hierarchy requires physical addresses. This means that when your CPU goes to touch even the first-level (L1) cache, it must do this virtual-to-physical translation. The CPU does this efficiently using a tiny cache called the translation lookaside buffer, or TLB. Each entry in the TLB maps a virtual page to a physical page, where a page is a range of consecutive addresses. A typical TLB has between 32 and 2048 entries, and a CPU will have a hierarchy of TLBs to go along with its hierarchy of caches. For example, an AMD Opteron has a 32-entry first-level TLB, and a 512-entry second-level TLB. (In fact, it has separate TLBs for handling instruction and data addresses; these are called the iTLB and dTLB.) The number of pages that a TLB can translate at once is called its range. With a 4KB page size and 512 entries, a TLB has a range of 2MB. The 2MB doesn’t have to be contiguous; I just mean that such a TLB can translate 2MB of virtual addresses to physical addresses at one time. If the CPU needs to translate a virtual address that is not currently covered by a TLB entry, this is called a TLB miss. (If there is an entry in the TLB, a successful lookup is called a hit.) Because TLB lookup time is critical to the performance of the CPU, the normal case (of lookups resulting in hits) is handled entirely in hardware. In fact, a TLB lookup is performed in parallel with an L1 cache lookup, so that both can be done in a single cycle. But when a TLB miss occurs, the hardware throws up its hands and causes a trap. This suspends normal execution of the CPU so that the operating system can load a new value into the TLB entry where the miss occurred. The component of the kernel that handles this step is called the TLB miss handler, and it’s critical to performance, too. Since PC-class systems running Linux always use a 4KB page size, the reach of the TLB is tiny compared to the size of physical memory. For example, my desktop system has 2GB of RAM, and 1024 TLB entries; this gives its TLB a reach of only 4MB, or 0.2% of RAM. I’ll return to the subjects of TLB size, page size, and oprofile soon.

I just read some notes from an entertaining talk (one that’s surprisignly accessible, even if you’re neither a computer scientist nor a string theorist) that Scott Aaronson recently gave at Stanford, and came across this gem: But what could NP-hardness possibly have to do with the Anthropic Principle? Well, when I talked before about computational complexity, I forgot to tell you that there’s at least one foolproof way to solve NP-complete problems in polynomial time. The method is this: first guess a solution at random, say by measuring electron spins. Then, if the solution is wrong, kill yourself! If you accept the many-worlds interpretation of quantum mechanics, then there’s certainly some branch of the wavefunction where you guessed right, and that’s the only branch where you’re around to ask whether you guessed right! It’s a wonder more people don’t try this. ...

Inspired by a discussion on a mailing list, I dug up a copy of Ian Stewart and Jack Cohen’s Figments of Reality, to find the definition of the zombike. […] We begin with a topic that has greatly excited many philosophers: along with Dennett, we think it is a complete red herring. We mention it because you may well run into it, and deduce from the awe in which it seems to be held in some quarters that it is a serious contribution to the subject - which it is not. This is the concept of a “zombie”, which is exactly like a human in every respect except that it is not conscious. Zombies are thought experiments, often used to focus attention on the (alleged) ineffable quality of consciousness that is so different from the physicochemical activities of material brains. imagine a zombie, the argument goes. It functions just like a real human being, right down to the electrical activity of its brain cells - but you know it’s not conscious, because that’s how you imagine it. Conclusion: consciousness is different from the physical activity of a material brain. There are so many things wrong with this suggestion that it is hard to know where to start. The main one is that it’s a cheat. It’s a Silly Question in disguise, one of the “but what if you saw a ghost?” variety […] You might as well encourage people to imagine a zombike, which is exactly like a bicycle in every way except that it does not move when the pedals are pushed. Oh, mystic miracle of ineffable immateriality, the source of motion in a bicycle is not anything physical! ...

“Uh oh. I’ve drawn the attention of the shetland pony riders of the apocalypse.”

Inspired by this Language Log article, a few newly minted words and fresh observations from home: Indispensable kid’s verb of the year: to “attackle”. Superman’s alter ego is Clark Dent. The protagonist of the past summer’s flaccid offering from Pixar is Lightning the Queen.

If you’ve had to do much performance tuning on a Linux system, you may have come across the oprofile system profiler. It may sound like a great piece of software, but it’s got a name for being difficult to use. In this article, I’m going to try to show that oprofile is decidedly non-scary, and is in fact quite easy to use. On most of my development systems, I run Fedora Core 6. What I’m going to describe is tailored to that environment, but shouldn’t be hard to adapt to other distributions. The following instructions work just fine for me on 32-bit x86, 64-bit x86, and 64-bit PowerPC. On Fedora, installing oprofile is simple: ...

If you use IRC to collaborate on a software project, chances are you’ve come across pastebin.com, a site where you can post snippets of code, program output, patches, and the like, and then give out the URL of the snippet to other people in the channel you’re working in. A similar site is paste.lisp.org, which controls a network of bots that sit in IRC channels and announce newly pasted URLs for you. These seemingly trivial services make it vastly easier to do collaborative development and debugging. I just ran across a mathbin.net, a site that takes one step closer to nerd heaven, by allowing you to write mathematical equations using LaTeX’s notation; it then renders the mathematics as inline images, using LaTeX’s renderer. The results are beautiful; here’s an example of the Airy function defined over real values. ...

Local scientists, ancient reptiles, volcanic eruptions, and Antarctica! All in one story! Really, this article was written precisely and exactly for me. In brief, a paleontologist from Berkeley (across the Bay from me) was involved in a spectacular find: an almost complete skeleton (cartilage and all) of a juvenile plesiosaur, buried in 70 million year old volcanic ash. The team found it on their second trip to Vega Island, off the coast of the Antarctic Peninsula. Strangely, the coverage in the Valley’s local paper, the Mercury News (linked above), is of better quality than the corresponding news article in Nature. That doesn’t happen often.

If you’re using a fairly modern laptop with an Intel chipset, the chances are that it has an Intel ICH7 I/O controller hub: $ lspci | grep -i ide 00:1f.2 IDE interface: Intel Corporation 82801GBM/GHM (ICH7 Family) Serial ATA Storage Controller IDE (rev 01) This usually means that your internal hard disk and CD-ROM/DVD drive (if you have one) are wired using Serial ATA (SATA), not the obsolete Parallel ATA standard. However, while the Linux SATA driver will happily take control of your hard disk, for some reason the older IDE driver will often capture the CD-ROM drive. You can tell by looking at /dev/cdrom: ...