Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to write a program in C to measure the speed of cache?

Tags:

c

caching

Write a program and try to compare(measure, if you can) the time of accessing data from main memory and cache.

If you can do that, then how to measure the speed of each level of cache?

like image 362
Sayakiss Avatar asked Apr 26 '13 17:04

Sayakiss


People also ask

How will you measure the performance of cache?

The performance of the cache memory is measured in terms of a quantity called Hit Ratio. When the CPU refers to the memory and reveals the word in the cache, it's far stated that a hit has successfully occurred.

What is cache in C?

Cache memory is an extremely fast memory type that acts as a buffer between RAM and the CPU. It holds frequently requested data and instructions so that they are immediately available to the CPU when needed. Cache memory is used to reduce the average time to access data from the Main memory.

How is cache miss measured?

You can also calculate a miss ratio by dividing the number of misses with the total number of content requests. For example, if you look over a period of time and find that the misses your cache experienced was11, and the total number of content requests was 48, you would divide 11 by 48 to get a miss ratio of 0.229.

How does cache memory speed up the program execution?

Cache memory, which also is a type of random access memory, does not need to be refreshed. It is built directly into the CPU to give the processor the fastest possible access to memory locations and provides nanosecond speed access time to frequently referenced instructions and data.


2 Answers

You need to come up with a heuristic that forces a 100% (or very close) cache miss (hopefully you have a cache invalidation op code?) and 100% cache hit. Hooray, that works for 1 level of cache. Now, how to do the same for level 2 and 3?

In all seriousness, there probably isn't a way to do this 100% reliably without special hardware and traces connected to the CPU and memory, but here's what I would do:

Write a "bunch" of stuff to 1 location in memory - enough that you can be sure that it is hitting the L1 cache consistantly and record the time (which affects your cache so beware). You should do this set of writes without branches to try and get rid of branch prediction inconsistancies. That is best time. Now, every so often, write a cache-line's worth of data to a random far away location in RAM at the end of your known location right and record the new time. Hopefully, this takes longer. Keep doing this recording the various times and hopefully you will see a couple of timings that tend to group up. Each of these groups "could" show timings for L2, L3, and memory access timings. The problem is there is so much other stuff getting in the way. The OS could context switch you and screw up your cache. An interrupt could come along and through your timing off. There will be a lot of stuff that could throw the values off. But, hopefully, you get enough signal in your data to see if it works.

This would probably be easier to do on a simpler, embedded type system where the OS (if any) won't get in your way.

like image 200
Michael Dorgan Avatar answered Nov 15 '22 18:11

Michael Dorgan


This generally requires some knowledge of the “geometry” of cache and other aspects of it. It is also helpful to have some control of the system beyond simple user access to it and implementation-dependent things such as finer timing than might be supplied through the standard C clock mechanism.

Here is an initial approach:

  • Write a routine that takes a pointer to memory, a length, and a number of repetitions and reads all of that memory in consecutive order, repeatedly.
  • Write a routine that takes a pointer to memory, a length, and a number of repetitions and writes to all of that memory in consecutive order, repeatedly.
  • The above routines may have to convert their pointers to volatile to prevent the compiler from optimizing away accesses that otherwise have no effect.
  • Allocate a large amount of memory.
  • Call each of the above routines, getting the current time before and after each call, and calling with a variety of lengths to see the times for different lengths.

When you do this, you will typically see fast speeds (number of bytes read/written per second) for small lengths and slower speeds for longer lengths. The speed decreases will occur where the sizes of the different levels of cache are exceeded. So you are quite likely to see the sizes of L1 and L2 cache reflected in data collected using the above technique.

Here are some reasons that approach is inadequate:

  • It does not control the instructions used to read or write cache. The C compiler may well generate load-word and store-word instructions, but many modern processors have instructions that can load and store 16 bytes at a time, and reading and writing may be faster with those instructions than with four-byte word instructions.
  • Cache will behave differently when you access in sequentially than if you access it randomly. Most caches make some sort of attempt to track when data is used, so that recently-used data is kept in cache while other data is cast out. The access parts of real programs generally differ from the consecutive operations described above.
  • In particular, consecutive writes to memory may be able to fill an entire cache line, so that nothing needs to be read from memory, whereas a real-world usage pattern that writes only one word to a particular location may have to be implemented by reading the cache line from memory and merging in the changed bytes.
  • Competition from other processes on your system will interfere with what is in cache and with measurement.
like image 40
Eric Postpischil Avatar answered Nov 15 '22 17:11

Eric Postpischil