Cache
From Unofficial BOINC Wiki
Contents |
[edit] General
Ok, bear with me …
In the simplest form, a cache is nothing more than a temporary holding area. Just like you might put post-it notes on places in your books that are relevant to you, a computer likes to put things in places where it can get back to them in a hurry if it needs them.
Ok, next thing to understand is the concept of a cache "hit" and a cache "miss." It is simple, if the item desired is in the cache when an access is made we have a cache "hit"; if it is not in the cache when we want it we have a cache "miss."
Cache components are always a trade off between cost and speed. Just like a Porsche costs only a little more than a Yugo but you do get slightly better performance out of the Porsche with only a minor increase in the monthly gasoline costs. In the world of computers the same rules of economics hold true; the faster it is, the more it costs. So, here is a partial list of the most common caches and where they are in relationship to each other:
[edit] CPU L1 Cache
This is the cache closest to the computer's Central Processor (usually on the processor chip itself) and it operates at core speed. This Cache may be divided into instruction store, data store, and micro-operation store (you don't want to know, trust me). This is the smallest cache within the system and is typically in the general vicinity of 8 to 50 Kilobytes in size. This cache, on a cache miss will pass the request on to the L2 cache (if there is one).
[edit] CPU L2 Cache
This is the next cache out from the computer's Central Processor. It is usually a significantly larger cache and ranges from 128 Kilobytes to 1 or 2 MegaBytes. This cache is also usually on the CPU chip, but in some cases like in the Pentium Pro it was on a separate chip contained within the chip package, in rarer cases it will be off chip and located on the motherboard. This cache, on a cache miss will pass the request on to the L3 cache (in the highly unlikely event you have one) or out to main memory.
[edit] CPU L3 Cache (you should be so lucky)
This cache, is usually off the main CPU chip and is not common in today's machines (well, lets wait a week, it is sure to be out then). This cache, on a cache miss will pass the request on to the main memory.
[edit] Main memory
Conceptually, the next 2 "layers" in this model are in main memory. Bear in mind, however, that in reality, that the computer's main memory is not cache. It is RAM.
[edit] allocated memory
When a user opens a program (such as the BOINC manager) or a program forks a process (such as a science application), the computer's operating system typically allocates a block of main memory (RAM) and loads the program's instructions into that block of RAM. If the computer is low on memory the operating system may only load part of the program into RAM and leave the rest on disk. Because disk has moving parts, this may slow the computer down noticeably; therefore, the more RAM you have in your computer, the better.
[edit] page cache
The operating systems of most modern computers use virtual memory, which maps the memory addresses used by application programs to various physical memory locations, both in RAM and on the hard drive; this way, non-contiguous blocks of memory can be made to seem contiguous, and hardware architecture is "hidden" from applications.[1], [2]
The page cache is a part of RAM that mirrors part of the contents of the hard drive, to facilitate this process; if your computer has a large amount of RAM, the operating system can use the extra RAM as page cache.[3]
[edit] disk buffer
This cache is located on the disk drive[4] and is 2 MegaBytes to 8 MegaBytes in today's disk drives. As items are read off the disks, or written to the disk they are stored in the disk drive's cache. This cache, and the Disk Drive itself can also be used as a storage location for portions of "virtual memory" that cannot be held in main memory.
[edit] An Application Cache
(like in the BOINC Client Software (I told you to bear with me …) This cache is specific to the application and the information it stores is almost always on the disk drive. In the case of the BOINC Client Software we want to make a local copy of work so that even if the Project's Data Server is unavailable, we will keep the BOINC Client Software and the science Science Applications busy at all times.
[edit] How it All Works
Ok, now this is how it all works. When the computer starts up all of the caches, except those on the hard drive are empty. So when the computer tries to get its first instruction, it generates a series of cache misses all the way out to the hard disk. Here is the bad news, all these cache misses actually took more time to get that first instruction than it would have if we had just gone directly to the sources. So why did we do this? Simple, the start up is an a-typical event (we hope, but I have had days …) and over time the caches slowly fill with data and instructions that we ask for time and again.
The desired hit ratio we would like to see is in the area of 90% or better. Cool, and you don't even know the best part of all of this. That expensive L1 cache and all his buddies down the line actually during normal operation give the CPU an effective speed of the L1 cache. Almost always we are going to get cache hits and those are going to add up. So, we use a little bit of expensive memory to give us what is effectively core processor speed all the way out the main memory. A very nice cost benefit trade off.
In the case of our project cache (queue), the same kind of effect plays out. You have a science Science Application and you want to keep doing productive work. If we had to connect to the project's Data Server only on those occasions where we were out of work, well, you would have a lot of lost productivity. So, what we do is we download several Work Units down to our local "cache" which we call a queue and as we complete each Work Unit in process we save that in the out-going queue and get the next Work Unit from the queue and proceed about our business. This way, Internet outages, down servers, long week-ends, and all of the other problems of life are smoothed out and we keep crunching along.
[edit] For Example
Ok, as an example, we are going to assume for simplicity's sake that the "miss rate" is 10% for each level (although because disk buffers are usually small, let's suppose the disk buffer miss rate is really high, let's say 90%). What this means, is for every access to a CPU level instruction or data item, 90% of the time we can satisfy the need with a cache "hit". So, while the CPU is processing the program and acting on the data, the CPU must obtain each instruction and each data item. Because of cost we want to gain the most speed with the least cost. Speed is expensive, when you buy your sports car, well, they cost more than a plain old station wagon.
Now for the fun. The CPU asks for the next program instruction (step) and so it tries to read the instruction out of the "Level 1" cache. The good news is that 90% of the time the instruction is there and available. In a one hour period of running, 54 minutes all of the data items and instructions will come out of the Level 1 cache.
In the event of a Level 1 cache "miss," for 6 minutes of that hour, we will have to get the next instruction or data item out of the Level 2 cache and these accesses will re-fill the Level 1 cache.
In the event of a Level 2 cache "miss," for 36 seconds of that hour, we will have to get the next instruction or data item out of that portion of main memory assigned to the program, and these accesses will re-fill the Level 2 cache.
In the event of a "miss" in the portion of main memory normally used by the program, for 3.6 seconds of that hour, we will have to get the next instruction or data item off the page cache, that is, the part of the main memory which is not assigned to the program but rather, mirrors part of the disk drive.
In the event of a total "miss" in main memory, for 0.36 seconds of that hour, the operating system will look for the next instruction or data item off the disk drive. But sometimes the disk drive controller will see that the item is in the disk buffer, and it will be loaded from there into RAM. The rest of the time, for 0.27 seconds of the hour, the computer will have to access the actual hard drive itself to get the information.
The result looks like this:
| CPU | hit % | Miss Time |
|---|---|---|
| Level 1 | 90% | 360.0 seconds or 6 Minutes |
| Level 2 | 90% | 36.00 Seconds or ~1/2 a minute |
| Main memory (application) | 90% | 3.600 Seconds |
| Main memory (page cache) | 90% | 0.360 seconds |
| Disk buffer | 10% | 0.324 Seconds |
| Disk drive | variable | variable |
Now, I ignored many other factors, and possibly used "hit" and "miss" rates that are, ahem, bogus; but you can see the effects …
[edit] Also See
[edit] external links
1howstuffworks.com: virtual memory
2Wikipedia:virtual memory
3Wikipedia:page cache
4Wikipedia:virtual disk buffer
