Cache Coherence Gyaan

Total Geek talk, noobs feel free to close the tab.

Finally, I realized that it is good to share technical knowledge , because the more you share the more you know.

Basics: Cache is a mid level memory between the CPU and the RAM, the simple funda behind cache is that it is a bit expensive and much more faster than your RAM (in terms of access time) , so during processing some of the data from RAM is brought into the cache, the data which is assumed to be accessed much more often. So that the system becomes more efficient.

Now, all is good till the time there is only one core, but if there are multiple cores which are sharing the same memory space, it creates a bit of a mess. One needs to know who is changing the memory contents, because each core would be having its own cache. Say, there is a variable which is used by both the cores, and both of them have cached it. Now, if core1 updates its value in its cache, or even if it updates its value in the memory. Core2 needs to know that the value of this variable has been changed and it should update its value before using it. Well this is called as the "Cache Coherency" problem. The problem statement is simple, "Figure out if something has been messed up, and if yes , what??"

Before we delve into the details, we need to have some more basics. There are two ways to maintain a cache (even if there is a single cache), through which we decide that what data should be loaded into the cache and when, because the size of cache w.r.t RAM is quite less. (Just as a spec my laptop has 4 GB RAM and 3MB of cache). This is maintained as either write through cache or a write back cache. In a write through cache, the contents of the cache are written back to the memory as soon as they are updated in the cache. In a write back cache, the contents of the cache are kept in the cache even when they are changed, but when they need to be swapped out of the cache to load some other memory contents, only then they are written back into the memory.

Now, there are two ways to handle this situation :

• The Software way
• The Hardware way

In the software way, to implement cache coherency, it is the responsibility of the compiler , and sometimes the programmer (if he/she is programming in assembly language) to take care of cache coherency. A simple and a bit inefficient way of doing so is flush the cache or mark it as invalid, as soon as you write a shared/global variable. Well this a very inefficient way and there are many more efficient ways to do this. And these ways generally depend on the hardware too.

Now the problem with having cache coherency through Software means is, firstly, it is inefficient one might end up updating the whole cache even when only a few memory locations are changed. Secondly, and most importantly, the code which depends on software cache coherency cannot be easily ported from one machine to another, as the other machine might be having a different hardware configuration.


In the hardware way, there is special space reserved in the cache for cache coherence. The cache is in general divided into cache lines, say if a cache line consists of 100 bytes of data then whenever data would be swapped out of cache into the memory or data is swapped into the cache it is transacted into multiples of this number. One can imagine a cache as a 2D memory consisting of some number of lines. And for each cache line there is a directory entry in the special space reserved for cache coherence, this space is generally called as "cache directory". For each cache line there are 3 bits reserved in the directory which tell about the state of the data in that cache line.

The issues with hardware coherency is, first, it generates a lot of inter cache traffic, whenever a cache write occurs, that cache needs to send info about this to all the other caches so that they can update themselves. Secondly, the amount of cache memory which is usable for storing data decreases.



So which one is better ?

Well it depends on the situation, if the program has too little shared variables, then the hardware method is preferable, as the amount of inter cache traffic is manageable. Whereas if the amount of shared variables are too many and they are updated by different threads quite often, then the software method is preferred, as in this case network traffic will be too much, and it is fine to flush the whole cache at once instead of doing it one by one, by hardware method.


Now, how about a system in which we can dynamically change from software coherency to hardware coherency. This is a paper which talks about such a system, and also inspired me to write this blog.

My First Snakey Game

First of all. Yay!! its working...!! and perfectly fine... \m/

Finally after a lot of time I am feeling like a doer and less like a speaker or manager. I just coded away a snakey game probably in something around 3-4 hours, in python + pygame. And it is awesome, not the game, as in even that is awesome, but yeah the feeling of accomplishing a project, even though a micro one is great.

Well I always wanted to make games sometimes just for fun. And yeah for sure I am having fun now. Also if anyone wants to play it, you can download it from http://bit.ly/bvgFF8 . Though you would be requiring to install python and pygame on your system to run it..!!

Whats the theory behind it??

Okay, this one is totally philosophical, those not interested can leave at any time.

Well it has been quite some time and I have been thinking about a lot of things. The most time consuming being "What next??" or say "What do I want ultimately from my life?". The biggest problem being the hunger for more, there is always a feeling of trying to get more out of my life, trying to get more out of my time. Okay this is not just about more money or more marks!! or more friends??,but maybe more achievements or maybe more knowledge. Sometimes, it is about making more sense out of my life. But, all that i think would make more sense out of my life, before doing them, end up hardly making any difference once I am done with them.

Now, for quite some time, I used to believe that materialistic things are things like Money, objects, and similar things. But now I think hey even achievements are also like materialistic only, you achieve achievements to gain something, maybe success, or popularity or maybe even money, but yeah doesn't it sounds like materialistic after all.

There was this guy who was mentoring me sometime back,(no it isnt deepank, this time) he used to say that his theory of life is like a circle, you get one aim then you complete it and get another aim and then you complete it and it goes on and on and on, and eventually you end up dying one day. And yeah then he added external factors like failure of an aim, gaining knowledge in every loop and so on. Well I liked his idea at that time, but now its like , c'mon life cudn't be that dumb. I guess life should be something like building a house, you collect all the raw materials for making it , then you learn all the skills for making it, then comes all actual building of the house, and after some time you feel like okay I have worked enough on it, its time to live inside it and enjoy the ambiance, though you still maintain it and upgrade it occasionally. And then yeah one fine day, you feel like okay now I am feeling bored lets die.

Well this one sounds more meaningful and more interesting, but still keeping this in mind in real life is quite difficult. The big issue is that I want to make multiple houses, bloody I want to be great at many things. As in I guess its high time I should make myself realize that I can't be great at many things or even great at anything, as in there are good enough chances for that too, and that might be the case even (You who is reading this post right now maybe knowing better). And I guess there are many more things, this is just one, as in there should be something much more meaningful towards life, I don't know what, probably I am too young for that, but yeah there should be.

Okay, this might make me sound like a nomad roaming in a desert looking for something (yeah I feel so sometimes), the worst part being he doesn't knows what is he looking for, but pretty sure about the thing that once he finds it he would be able to know that this is what he was looking for. God!! This post sounds crazy.

Well at the end I would say, any comments/help is welcomed.

Whats "right" and whats "wrong" ?

When I was a kid, the answer to the above question used to be straightforward. The rules were defined by my parents and brother and the answer used to be based on those rules + a little bit of intuition. The same was the thing with who is "good" and who is "bad". Most of the times the answers used to be loud and clear. Also, every person used to be either "good" or "bad", there were no middle categories. And yeah, I generally used to keep myself into my limits of a good person according to those rules.

Then came the teen-age. When I was entering my teen-age, there was a hell lot of discussion going on about how to handle teenagers, be it newspaper, television etc etc etc. In most of them, I was referred to be a part of a specie called "Today's Generation", and there were some particular tags associated with this specie; "resilient" , "arrogant" ,"pre-mature" and a whole sort of things, which I probably wasn't even able to decipher at that time. That was a time when doing a "wrong" thing also felt fine. Breaking the rules was the "in" thing for our specie. After all, preconsciously though, I was a part of this specie (well I still am, although the name has changed). Even in this case I used to be pretty sure about, what is right and what is wrong, although doing "wrong" was not even so "wrong". People still used to be either "good" or "bad", but now they were according to my own limit of wrongness, If their deeds were "wronger" than me then I used to consider them as "bad" else "good". Also, there was an added category of "no comments", which used to consist of very small population though.

Finally, came the latter half of college life, when all these categories seemed to merge with each other. I went on to the most basic thing, the rules. Who defined those rules that we follow. Some of them were defined by my parents, some other were defined by teachers, some were defined by my peers. Well the problem was that, it wasn't even them who defined those rules, they just told those rules to us, and god knows who else defined those rules for them. Obviously these rules trickled down to me with some modifications(modifications which my parents, teachers etc would have made to make their life better).

Then came the question, shall I follow all these rules or trash all of them. Well I have already been following these rules, and probably my life hasn't been flowing that smooth by following these rules. I guess that was the reason why I was thinking so deep about this matter. So this option was auto canceled. Then came the option of redefining rules, I soon realized that one cannot define all rules by himself, probably I didn't had that much experience about things. So, I started changing those rules which I thought were wrongly created, according to me(This decision making was based on my previous experience as well as on the solution to the situation at hand).

So now there is nothing defined as "right" and nothing defined as "wrong". Its just "right for me"(at that time) or "wrong for me". No person is "good" and no person is "bad". Its just "good according to me" and "bad according to me". But these lines are very very bleak, heavily mixing with each other. Because, whenever I am at a stage to tag a person "bad" in accordance with some action of that person, I happen to think "okay, maybe it isn't wrong according to him".

I guess the best thing of this approach till now has been this only, "None is good, none is bad, its just that some people are compatible with me and some are not". Also, I believe that the converse of this is also true, "None hates me, its just that I am not compatible with some of the people".

Your own home made Youtube Video Downloader

Well , till quite some time back I have been using some Youtube video downloader application, most of which have stopped working now. So, there was this one awesome video which I wanted to download.

Suddenly, I come to stuck with this simple logic, that hey if firefox is playing this video then it must be downloading that video onto the memory and then playing it. So why don't I pick up this video from there. So the most obvious place to check for such a thing was the /tmp/ folder ( I am on Ubuntu currently) and voila here it was resting in peace waiting for me to close the tab and get deleted.

So all that one has to do for his home made Youtube Downloader to work is to cut this video from your temp folder and save it at some good place before you close the tab and here you go, you home made Youtube Downloader is ready.

OpenCv 2.0 with Ubuntu 9.04

Recently I have started working on my final year project, and I got stuck with a pretty nice idea of documenting it on my blog.
I am working on 3-D Modeling using Videos. As usual the first steps of doing a project is to get the development environment settled up, and doing the feasibility study. In our case we had decided to use OpenCV for video manipulation, because of two reason :
1.) It's faster than any other library present out there for the same purpose.
2.) Its pretty advanced(read as a lot of inbuilt functionality) and optimized.

I am just documenting the method which worked for me, there were other easier one's which didn't worked for me :(.

First of all one needs the ffmpeg (for video support) and GTK 2.0 for OpenCv to work properly. Sadly, one needs to check out ffmpeg from trunk and compile it for his own platform, no binaries in Ubuntu repositories.

1.) Check out ffmpeg from their svn repo:

cd ~
svn checkout svn://svn.ffmpeg.org/ffmpeg/trunk ffmpeg
cd ffmpeg

2.) Then for sure one needs to compile ffmpeg and install it:

./configure --enable-shared
make
sudo make install

This thing takes its own sweet time, So you can go and get some coffee for yourself.

3.) Then you need to get GTK Development libraries:

sudo apt-get install libgtk2.0-dev

4.) Finally one needs to download code for OpenCV 2.0 and Compile and install it :

cd ~
wget http://downloads.sourceforge.net/project/opencvlibrary/opencv-unix/2.0/OpenCV-2.0.0.tar.bz2
tar -xvf OpenCV-2.0.0.tar.bz2
cd OpenCV-2.0.0
./configure --with-ffmpeg --with-gtk --with-quicktime=false
make
sudo make install

This is again a thing which will give you ample of time to take a break and make some calls to your fiends.

After you are done installing OpenCv, then comes the issue of how to use it. I was using openCV with C++ and tried some sample examples of O'Rielly book.
After a little searching I figured out that to include the OpenCv files while compiling my C++ files I need to use :

g++ `pkg-config --cflags opencv` `pkg-config --libs opencv` filename.cpp -o test

Now, this is neither easy to remember nor easy to type every time I compile some code. So, I found this nice little hack of adding aliases.

There exists a .bashrc file in your home folder. It is basically a config file for your login profile. One can add aliases for terminal commands in this file and then use them :

alias gcv="g++ `pkg-config --cflags opencv` `pkg-config --libs opencv`"

Now whenever, I type gcv in my terminal , it is interpreted as g++ blah blah blah.

I will keep adding the progress of my project to this blog, so stay tuned.