tag:blogger.com,1999:blog-72855228183498646672024-03-27T23:53:34.296+00:00Netduma Team BlogThe musings of the <a href="http://www.netduma.com">Netduma</a> team. Anonymoushttp://www.blogger.com/profile/05316739893737008207noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-7285522818349864667.post-65035534023720983842015-01-29T14:50:00.001+00:002015-01-29T14:50:02.753+00:00<div style="text-align: center;">
<b>How to dominate lag with the Duma, the BIG picture</b></div>
<div style="text-align: left;">
<br />
<b>Introduction</b><br />
<br />
This document will run you through the steps to diagnose and control lag using your Netduma R1. If you'd like a slightly more technical explanation of what lag is please read this.<br />
<br />
I start of by explaining where delays(the root cause of lag) are introduced on the Internet. Then I run you through a simple 4 step process to control those delays.<br />
<br />
<b>Where are packet delays introduced?</b></div>
<div style="text-align: left;">
<b><br /></b></div>
<div style="text-align: left;">
There are 4 places where delay can be introduced on the Internet. The first three are illustrated in figure 1. The blue line shows the path a packet takes from your home to the other player. The three red circles mark points where delay can occur:<br />
<br />
<ol>
<li>If someone or a device is downloading/uploading heavily it can cause delay at your home</li>
<li>The distance a packet has to travel across the Internet</li>
<li>If the person you're connected to is downloading or uploading heavily it can cause delay</li>
</ol>
<div>
Just to clarify in points 1 and 2 its not your ISP making you lag. Its yourself or the people you live with that's doing it. </div>
</div>
<ol>
</ol>
<div>
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzxOFdnAsVdFLKa2hO-8FVitxOKhszirlaVpgHIHsHu7_u-vk2hZt5M9NNXlYRRo-VS58RBgc0JFZGGublElAz935IqbcTap-18LqqvAgZ_44-jG7qPDk-MfUw7I0kG3O9KruH0nPB3sg/s1600/LagCause.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhzxOFdnAsVdFLKa2hO-8FVitxOKhszirlaVpgHIHsHu7_u-vk2hZt5M9NNXlYRRo-VS58RBgc0JFZGGublElAz935IqbcTap-18LqqvAgZ_44-jG7qPDk-MfUw7I0kG3O9KruH0nPB3sg/s1600/LagCause.png" height="202" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Figure 1. Delay points on the Internet.</td></tr>
</tbody></table>
<div style="text-align: center;">
<br /></div>
The fourth potential cause of delay is if there is a signal or configuration problem in your local area.<br />
<br />
<div style="text-align: center;">
<b>Steps to Diagnose & control lag </b> </div>
<br />
<b>How to dominate lag - Step A </b><br />
<b><br /></b>
We need to determine if its a signal or configuration problem. You can do this on the Duma by selecting "Internet Diagnosis" on the main menu and clicking "Run Test". If the results are below "ok" you likely have an issue with your Internet. I'd recommend you call your local ISP and use the information in the "Details" button to let them know there is an issue.<br />
<br />
If the results are good jump to Step B.<br />
<br />
<b>How to dominate lag - Step B</b><br />
<b><br /></b>
We need to determine if its other people at your home are making you lag. This is a simple task please select "Network Monitor" on the Dumas main menu. You'll see two graphs illustrating your current network usage.<br />
<br />
The utilisation bars above the graph show how much of your connection is being used. If either of them ever goes above 70%, then this means other people at your home could be making you lag. Please see the Congestion control manual to combat this.<br />
<br />
<b>How to dominate lag - Step C</b><br />
<b><br /></b>
If the Geo-filter is supported for your game. The Duma can be used to stop you connecting to players that are too far away. Therefore eliminating cause number 2 of delay. See the Geo-filter manual.<br />
<br />
<b>How to dominate lag - Step D</b><br />
<b><br /></b>
After following steps A,B and C you should have control over the causes 1,2 and 4 of lag. So all that is left is cause number 3. That is connecting to other players or hosts with a bad connection. The solution here is simple use the allow & deny feature to stop you connecting to them. See the Allow & Deny manual.<br />
<div style="text-align: left;">
<br /></div>
Anonymoushttp://www.blogger.com/profile/05316739893737008207noreply@blogger.com31tag:blogger.com,1999:blog-7285522818349864667.post-36384142820829581732014-10-29T15:33:00.001+00:002014-10-29T15:38:33.262+00:00You had me at Halo…a short story of how Netduma came to be<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Hello
and thank you for visiting our very first post. Our blogs will be
focused on topics that are of interest to us and hopefully you as well.
Namely:</span></div>
<div class="MsoNormal">
</div>
<ol>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;"><span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span></span><span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Starting a business</span></span></li>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;"><span style="font-size: 10pt;">Technology</span></span></span></li>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;"><span style="font-size: 10pt;"><span style="font-size: 10pt;"><span style="font-family: 'Times New Roman'; font-size: 7pt;"> </span></span><span style="font-size: 10pt;">Gaming</span></span></span></span><span style="font-family: Arial, sans-serif; font-size: 10pt;"> </span></li>
</ol>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Being our first blog it is only appropriate to start at the beginning; <b>how Netduma came to be.</b> <o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">As
the title implies, the answer is with Halo. To be specific, it began
when we, the co-founders (Iain and Luke), met through our mutual love of
Halo 2. <o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">When
Iain was one month into his first year at Nottingham University he
posted an open invite on Facebook to an all-day Sunday LAN at his
college. Luke, in a nearby college, practically sprinted over having not
played Halo for over a month (a long time in gaming). So with a
controller in one hand and a Halo disc lodged under his arm, Luke shook
Iain’s hand and the two of us met for the first time. <o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">After
running over the other players at the Sunday LAN, we both quickly
realised that we were well matched in ability. From that point forward,
and to this day, nearly ten years on from when we first met, we look to
play Halo whenever we have the time, including competitively at UK
events.<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnPwcU-EqUF-vlhLdjBXt8zMxgNW7N-CjFWFn_giVCMNmaQ8qw9lspwgJVx4WPS3l59X3Mi2xfvX-kxhQO3oPem0R2B76vN06VFSUmm8f2Mbzyli8tTY5TQhFtcA9iS5LGZuTfG6uYT4N-/s1600/bad+kids+playing.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnPwcU-EqUF-vlhLdjBXt8zMxgNW7N-CjFWFn_giVCMNmaQ8qw9lspwgJVx4WPS3l59X3Mi2xfvX-kxhQO3oPem0R2B76vN06VFSUmm8f2Mbzyli8tTY5TQhFtcA9iS5LGZuTfG6uYT4N-/s1600/bad+kids+playing.jpg" height="265" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i style="font-size: medium; text-align: start;"><span style="font-family: "Arial","sans-serif"; font-size: 10pt;">Here we are crushing dreams (and probably being crushed ourselves) at i52 in 2014. Iain is on the right, Luke is sat to the left. We were lucky to have two great teammates (Penguin & Hapax)</span></i></td></tr>
</tbody></table>
<div class="MsoNormal">
<span style="font-family: Arial, sans-serif; font-size: 10pt;">From teaming together we gained two important lessons:</span></div>
<div class="MsoNormal">
</div>
<ol>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-size: 13px;">We made a great team; and</span></span></li>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-size: 13px;">We hated lag</span></span><span style="font-family: Arial, sans-serif; font-size: 10pt;"> </span></li>
</ol>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">No
doubt these two points resonate with you as much as they have done so
for us. We all have that one other player who we just click with from
day one and we don’t know of a serious gamer who has not experienced lag
when playing online.<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">So with these two learnings in mind, we made this pact on a somewhat inebriated night out in 2008:</span></div>
<div class="MsoNormal">
</div>
<ol>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-size: 13px; text-indent: -24px;">Iain would research the root causes of lag and how to mitigate them</span></span></li>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-size: 13px; text-indent: -24px;">Luke would go to London to learn as much as he could about business</span></span></li>
<li><span style="font-family: Arial, sans-serif; font-size: x-small;"><span style="font-size: 13px; text-indent: -24px;">Together, we would one day launch a company to help gamers</span></span><span style="font-family: Arial, sans-serif; font-size: 10pt;"> </span></li>
</ol>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Despite
the distance of time and the random events that life has thrown at us,
this drunken promise has held firm. In November, we will launch the
Netduma R1, a router we truly believe is like no other in the world. How
did we achieve this? By ensuring that every feature we developed would
fulfil this one vital question:<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">“Will it help gamers?”<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">This has helped us to develop a router we are very proud of. A router that solves the real issues that gamers face.<o:p></o:p></span></div>
<div class="MsoNormal">
<br />
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">We
have not got to this point on our own. We have a talented team of people working with us, that will hopefully continue to expand in the future. </span><br />
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">At
the time of writing, we have revealed just two of our unique features
and there are so many more to announce, including one feature we are
internally naming as the ‘show-stopper’ because of the difference it has
made to our own online gaming. It may sound fickle but we genuinely get
a buzz of excitement whenever any of you interact with us on social
media, whether it be a Retweet, a like on YouTube or a comment on
Reddit. Just knowing that there are other gamers who are discovering
what our router can do and then positively engaging with us is hugely
motivating.<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">In
many ways, even though it is six years on from our pact, we are still
at the beginning. Our launch in November will mark six years of hard
work, tough lessons and a lot of fun. <o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Ultimately we hope that this beginning evolves into something extraordinary, and that you will be with us the entire way.<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZbVG6pFUMDy5i9CpgEiFMRYDN50Ed-SeNnTMJG72kKGYDgQ-3B3zpT6ucZMIxpTt3gijdQe-ygZ8Rt4jrhgKzYA6n338kaRgzRIg25NTDdgkwz2V76pXNKMZSnOgD1yeJv_oIHRfV-3RU/s1600/Where+was+Carmen.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgZbVG6pFUMDy5i9CpgEiFMRYDN50Ed-SeNnTMJG72kKGYDgQ-3B3zpT6ucZMIxpTt3gijdQe-ygZ8Rt4jrhgKzYA6n338kaRgzRIg25NTDdgkwz2V76pXNKMZSnOgD1yeJv_oIHRfV-3RU/s1600/Where+was+Carmen.jpg" height="300" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i style="font-size: medium; text-align: start;"><span style="font-family: "Arial","sans-serif"; font-size: 10pt;">Here we are, somewhat fresher faced, at the Halo 3 launch party. We thought Carmen Electra would be there. Sadly she wasn’t.</span></i></td></tr>
</tbody></table>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Thank you for reading.</span><span style="font-family: Arial, sans-serif; font-size: 10pt;"> </span></div>
<div class="MsoNormal">
<span style="font-family: "Arial","sans-serif"; font-size: 10.0pt;">Luke</span></div>
Netduma Lukehttp://www.blogger.com/profile/02975354634237078697noreply@blogger.com43tag:blogger.com,1999:blog-7285522818349864667.post-44534323249456521672013-02-07T23:15:00.004+00:002013-02-12T17:00:07.749+00:00Surfendipity<br />
<div align="CENTER" style="margin-bottom: 0cm;">
<b>Attached Code:</b> <a href="https://github.com/iainkfraser/PageRank/tree/blogcode">https://github.com/iainkfraser/PageRank/tree/blogcode</a></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
Let's start with a question. How would
you order all websites in order of importance? You could order by
most popular, most informative or most authoritative.
</div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
None of those are truly satisfactory
because the question is subjective. It depends on who is asked.
For example I would rank technical, comedy and competitive gaming
sites highly conversely fashion, gossip and liberal arts sites would
rank extremely low. Yet incomprehensible many (majority?) people
think the opposite.
</div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
So we alter a websites rank depending
on the viewer. This is what Google does now but originally googled
ranked websites using the PageRank algorithm (named after one of the
founders Larry Page). The algorithm takes an objective approach to
solving the problem.
</div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="175" name="graphics2" src="http://4.bp.blogspot.com/_wFWqWIH-WFU/RwdKrU69i3I/AAAAAAAACdE/ghA9HSqJpbU/s320/monkey_computer.gif" width="200" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
Figure 1. Random surfer</div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
We have all been there, you go on the
web with a specific purpose and then through a magical Intertubes
journey you end up somewhere totally unpredictable. For example I
started today searching for the relationship between static code
analysis and the halting problem, and I hate to admit ended up on <a href="http://www.youtube.com/watch?v=dQw4w9WgXcQ">youtube</a>...</div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
Jeez Louise what on earth does that
anecdote have to do with PageRank? Its a nice analogy of how PageRank
works. Given a user (for example a monkey) that surfs the web by
randomly clicking links. The PageRank of a website is the probability
of that user landing on the site after a significant number of
clicks. This is illustrated in Figure 2.<br />
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img border="0" height="322" name="graphics1" src="http://upload.wikimedia.org/wikipedia/commons/thumb/f/fb/PageRanks-Example.svg/400px-PageRanks-Example.svg.png" width="400" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
Figure 2. Graph with
PageRank values.
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So you can think of
hyper-links as the source website vouching for the destination
website. This explains why website B in Figure 2 is ranked so highly
because many sites link to it. In contrast site C is ranked highly
even though it has only one incoming link. The reason being its got
an incoming link from the big dogg B. Since its likely to land on B it is
also likely to land on C.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
“Its not what you know
or who you know – its who knows you.”</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Ok that makes sense and if
you're like me you must be wondering how on Gods green earth do you
calculate those probabilities? That is what the rest of the article
is about. First we need Markov chain models. These model the
movement through a stochastic state machines. These are just state
machines with transitions based on probabilities like so:
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhAaQLOcfioq2uAr0cH8-zL5ECi3iM5EHEzLWvMKX1ae5f7w5wd51xxn_ErhrJlC8YQ_XBLALLXLJwfZxzs_Q9VEB8DY_dBKWC0WU56FgfmFWq8yjprcYrOgKOAde68zO1t81ctUI2VpiA/s1600/markov2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhAaQLOcfioq2uAr0cH8-zL5ECi3iM5EHEzLWvMKX1ae5f7w5wd51xxn_ErhrJlC8YQ_XBLALLXLJwfZxzs_Q9VEB8DY_dBKWC0WU56FgfmFWq8yjprcYrOgKOAde68zO1t81ctUI2VpiA/s1600/markov2.png" /></a></div>
<br />
Figure 3. Directed graph
to illustrated state transitions</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So just to clarify we can
move from state A to B with probability of 0.5 and from B to C with
1.0 and so on so forth.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
The Markov chain is just a
sequence of random variables ( X<sub>1</sub>, X<sub>2</sub>, … Xn )
that represent a single state. So you can imagine just walking along
the graph. So let's say we start at state A. Then the random variable
X<sub>1 </sub>represents our first step so it is
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
P( X<sub>1</sub> = A ) =
0.0</div>
<div align="CENTER" style="margin-bottom: 0cm;">
P( X<sub>1</sub> = B ) =
0.5</div>
<div align="CENTER" style="margin-bottom: 0cm;">
P( X<sub>1</sub>= C ) =
0.5
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
The most important feature
of the Markov chain is that the transitions probabilities do not
depend on the past. In this article we assume the transitions are
constant throughout. So it doesn't matter at all what ridiculous
journey you took to get to a state. To predicate the future all you
need is the current state and the transitions. So just to reiterate
the past is irrelevant on Markov chains.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Right let's represent the
state transitions using a transition matrix <b>T</b> . Since the
transitions are probabilities we call it a stochastic matrix (technically the total probability of moving from one state to the
others is 1 so the rows sum to 1).
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="61" name="graphics4" src="http://www.numberempire.com/equation.render?T%20=%20%5Cbegin%7Bpmatrix%7D0.0%20&%200.5%20&%200.5%20%5C%5C%200.0%20&%200.0%20&%201.0%20%5C%5C%201.0%20&%200.0%20&%200.0%5Cend%7Bpmatrix%7D" width="156" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So the entry at row i and
column j represents the probability of moving from state i to state
j. For example <b>T</b><sub><b>23</b></sub> is the probability of
moving from state B to state C i.e. 1.0.
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Why did we bother converting
the graph to a matrix. Well it turns out it has a few neat
properties. Let's say we started at state A and I asked you what's the
probability of moving to state C in two steps?
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
To answer assume the
following notation P(IJ) means the probability of moving from state I
to state J in one step (just look up the matrix). So for example
P(AB) = 0.5. So the probability of going from A to C in two steps is
the probability of going from A to every state (A, B, C) then the
probability of going from that state to C. i.e.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="54" name="graphics5" src="http://www.numberempire.com/equation.render?%5Cbegin%7Barray%7D%7Blcl%7D%20=%20P(AA)%20*%20P(AC)%20+%20P(AB)%20*%20P(BC)%20+%20P(AC)%20*%20P(CC)%20%5C%5C%20=%200.0%20*%200.5%20+%200.5%20*%201.0%20+%200.5%20*%200.0%20%5C%5C%20=%200.5%20%5Cend%7Barray%7D" width="413" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
Notice that this corresponds
to the entry <b>T</b><sup><b>2</b></sup><sub><b>AC</b></sub>. If you
try it out for the rest of the entries it turns out that the product
of the transition matrix is the probabilities of going from the
row to the column in 2 steps. That is <b>T</b><sup><b>2</b></sup><sub><b>ij
</b></sub> the probability of going from state i to state j in two
steps. If you multiply that by the transition matrix you get the
state transitions for 3 steps. So it turns out that <b>T</b><sup><b>n
</b></sup>is the state transitions for n steps. Really neat huh? I
thought so anyway.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Ok let's multiply our transition matrix so we can see the probabilities for two, three,
four, five, twenty and one hundred steps:</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="61" name="graphics6" src="http://www.numberempire.com/equation.render?T%5E2%20=%20%5Cbegin%7Bpmatrix%7D%200.5%20&%200%20&%200.5%20%5C%5C%20%201%20&%200%20&%200%5C%5C%20%200%20&%200.5%20&%200.5%20%5Cend%7Bpmatrix%7DT%5E3%20=%20%5Cbegin%7Bpmatrix%7D%200.5%20&%200.25%20&%200.25%20%5C%5C%20%200%20&%200.5%20&%200.5%20%5C%5C%20%200.5%20&%200%20&%200.5%20%5Cend%7Bpmatrix%7D" width="350" />
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="61" name="graphics7" src="http://www.numberempire.com/equation.render?T%5E4%20=%20%5Cbegin%7Bpmatrix%7D%200.25%20&%200.25%20&%200.5%20%5C%5C%20%200.5%20&%200%20&%200.5%20%5C%5C%20%200.5%20&%200.25%20&%200.25%20%5Cend%7Bpmatrix%7DT%5E%7B5%7D%20=%20%5Cbegin%7Bpmatrix%7D%200.5%20&%200.125%20&%200.375%20%5C%5C%20%200.5%20&%200.25%20&%200.25%20%5C%5C%20%200.25%20&%200.25%20&%200.5%20%5Cend%7Bpmatrix%7D" width="400" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="61" name="graphics8" src="http://www.numberempire.com/equation.render?T%5E%7B20%7D%20=%20%5Cbegin%7Bpmatrix%7D%200.399%20&%200.200%20&%200.400%20%5C%5C%20%200.400%20&%200.199%20&%200.400%20%5C%5C%20%200.400%20&%200.200%20&%200.399%20%5Cend%7Bpmatrix%7DT%5E%7B100%7D%20=%20%5Cbegin%7Bpmatrix%7D%200.4%20&%200.2%20&%200.4%20%5C%5C%20%200.4%20&%200.2%20&%200.4%20%5C%5C%20%200.4%20&%200.2%20&%200.4%20%5Cend%7Bpmatrix%7D" width="403" /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Something very interesting
happens. The entries seem to converge until all the columns values
become equivalent. This means that after a certain number of steps
it doesn't matter which state you started on. The probability of
getting to another state is constant. My mind = blown. So let's try
visualise this:</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpH14TgXPsN5wLoTPr8lnELKQ6WQ0jQuJW-Hn9Y8FSjGsBqnPJGggAzD3M6Pb-5QGEW2iiH9MglhHn8kbNj3He1F_rtKoJI2KQejH7RvhalCx-pePelgYlhqsDdmu2JXq4FKPh32ivYr0/s1600/converge.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjpH14TgXPsN5wLoTPr8lnELKQ6WQ0jQuJW-Hn9Y8FSjGsBqnPJGggAzD3M6Pb-5QGEW2iiH9MglhHn8kbNj3He1F_rtKoJI2KQejH7RvhalCx-pePelgYlhqsDdmu2JXq4FKPh32ivYr0/s1600/converge.png" /></a></div>
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
Figure 4. State with
converged population distribution.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So let's say we start with a
100 people. Let's use the values of the converged matrix to place people on the graph. So let's put 40% of them on A and another 40% on C. The last
20% can go on B. So move forward one step in the Markov chain.<br />
<br />
Half of A will go to B and the other half will go to C. So the new B
will have 20% of people. The new C has 20% and the rest of the
people from old B which is also 20% therefore the new C has 40%.
Finally new state A has all the people from old state C i.e. 40%.
Whad'ya know? We are back where we started. So this shows the steady
state that the Markov chain converges on. Once we get into this distribution we stay there forever.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So if the small graph used
in the example actually represented three websites and the related
hyper-links. Then the stabilised values (i.e. the probabilities for
each column in converged matrix) represent the PageRank of each
website. Sweet!</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
This blog is already long
enough so I'm going to skip over the intuitive proof of convergence.
Although Ive put that in the appendix A. I'll just show how we can use
the transition matrix to calculate the PageRank.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
If we represent the initial
distribution (for example of people) using a vector e.g.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="62" name="graphics10" src="http://www.numberempire.com/equation.render?%5Cbegin%7Bvmatrix%7D0.25%20%5C%5C%200.25%20%5C%5C%200.5%5Cend%7Bvmatrix%7D" width="36" /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
That means ¼ of people are
in state A and another ¼ in B and the rest ( ½) are in C. If we
multiply the transition matrix with the vector. We will get a new
vector representing the distribution after the first step. By the
same token if we multiply it by an n step transition matrix then the
result is the distribution after n steps. So written mathematically,
given a transition matrix <b>T</b>, a source distribution <b>s </b>(represented as a row vector) we can calculate the resulting
distribution <b>r</b> after n steps using:
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<b>r = s . T<sup>n</sup>
<sup> </sup></b>
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So we have two very similar concepts but they are not equivalent.
</div>
<ol>
<li><div align="LEFT" style="margin-bottom: 0cm;">
After a number of steps
the probability of getting to a state is constant regardless of
where you start. So no matter what initial distribution you start
with you will end up with stable distribution.
</div>
</li>
<li><div align="LEFT" style="margin-bottom: 0cm;">
If you apply a single
state transition on the stable distribution you will get the stable
distribution.</div>
</li>
</ol>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Let's go through both these
points in order. To illustrate point 1 let's pick any random
distribution and multiply it with the stable matrix (the converged
matrix). So let's say we have 0.3, 0.3 and 0.4 in states A,B and C
respectively. Represent it as a row vector and multiply with the
converged matrix:</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="66" name="graphics13" src="http://latex.codecogs.com/gif.latex?%5Cbegin%7Bbmatrix%7D%200.3%20&%200.3%20&%200.4%20%5Cend%7Bbmatrix%7D%20%5Cbegin%7Bpmatrix%7D%200.4%20&%200.2%20&%200.4%5C%5C%200.4%20&%200.2%20&%200.4%5C%5C%200.4%20&%200.2%20&%200.4%20%5Cend%7Bpmatrix%7D%20=%20%5Cbegin%7Bbmatrix%7D%200.4%20&%200.2%20&%200.4%20%5Cend%7Bbmatrix%7D" width="380" /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Notice the result
distribution is the stable distribution. So intuitively what does
this mean? It just means that given the initial distribution and
taking it through a significant number of steps we will eventually
end up at the stable distribution.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
The stable distribution is
interesting because once you're in it you remain in that distribution
forever . This just a rewording of point 2. So let's illustrate this
by multiplying the stable distribution with the initial transition
matrix:</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="66" name="graphics12" src="http://latex.codecogs.com/gif.latex?%5Cbegin%7Bbmatrix%7D%200.4%20&%200.2%20&%200.4%20%5Cend%7Bbmatrix%7D%20%5Cbegin%7Bpmatrix%7D%200.0%20&%200.5%20&%200.5%5C%5C%200.0%20&%200.0%20&%201.0%5C%5C%201.0%20&%200.0%20&%200.0%20%5Cend%7Bpmatrix%7D%20=%20%5Cbegin%7Bbmatrix%7D%200.4%20&%200.2%20&%200.4%20%5Cend%7Bbmatrix%7D" width="380" /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Notice we get the stable
distribution again. That makes sense because the definition of the
stable distribution is one that doesn't change when transitioned. If
you try any other distribution on the transition matrix you will not
get the same result.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So if you recall from linear
algebra an eigenvector is a vector that is only scaled when
transformed by a matrix. That is, given a matrix <b>T</b>, a vector <b>s
</b>(called eigenvector)
and a scalar lambda (called eigenvalue) we have</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="13" name="graphics14" src="http://latex.codecogs.com/gif.latex?Ts%20=%20%5Clambda%20s" width="64" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
This looks very similar to
our answer above. Except we have a value of lambda as 1 and we are
using a row vector (we could change that by transposing both). So
it turns out that the stable distribution is the eigenvector of the
transition matrix with an eigenvalue of 1.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So moving back to our
PageRank algorithm where the transition matrix is a representation of
the web and the stable distribution is the PageRank of websites. We
can say the PageRank is the eigenvector of the stochastic matrix
representing the topology of hyper-links. Wow! that sounds
complicated but hopefully we now understand what that
means.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Let's generate the algorithm. So our input is the
stochastic transition matrix representing the Web. We want the stable
distribution (i.e. the eigenvector). Remember a multiplication of any distribution with the convergence matrix will be that stable distribution / eigenvector. So all we have to do is multiply any distribution with our convergent matrix to get the answer.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So the problem reduces to finding the convergent matrix. Well we know to do that we just need to multiply repetitively (take to the exponent) the transition matrix until it converges. So let <b>x</b> be our initial distribution. Just set it to 1/n where n is the number of components in the vector (i.e. websites). And we have the following formula to calculate the eigenvector: </div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: center;">
<img src="http://latex.codecogs.com/gif.latex?x_{i+1}%20=%20x_{i}%20T" /></div>
<div style="margin-bottom: 0cm; text-align: center;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
Huh? bear with me. Let's expand this out:</div>
<div style="margin-bottom: 0cm; text-align: left;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: center;">
<img src="http://latex.codecogs.com/gif.latex?\begin{array}{lcl}%20x_{1}%20=%20x_{0}T%20\\%20x_{2}%20=%20(x_{0}T)T%20\\%20x_{3}%20=%20((x_{0}T)T)T%20\\%20x_{4}%20=%20(((x_{0}T)T)T))T%20\\%20\vdots%20\\%20x_{n}%20=%20x_{0}T^n%20\end{array}" /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So by doing it in this order we can skip a few operations. We can do vector-matrix product instead of matrix-matrix product which has far fewer operations. So the last and final question is when do we stop? when we hit the stable distribution (eigenvector). That is when:
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: center;">
<img src="http://latex.codecogs.com/gif.latex?x_{i+1}%20=%20x{i}" /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So let's convert this into a floating point friendly algorithm:
<br />
<pre style="background-image: URL(https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2pTTGb1U6OPolmlE60ECZlveVwpgfeCQvbPvNJ6BU0CtAmdzO3KuZNNuncxQe69TT8Pxy22zoHm9TlrCyBxImcwJ6wGZQAa4YxOytwjB95V2rZEkg0CASkvu9boPdkqhkP8DbEfigPf67/s320/codebg.gif); background: #f0f0f0; border: 1px dashed #CCCCCC; color: black; font-family: arial; font-size: 12px; height: auto; line-height: 20px; overflow: auto; padding: 0px; text-align: left; width: 99%;"><code style="color: black; word-wrap: normal;"> /* Inputs are
* n = number of websites
* T = is a n x n transition matrix
*/
vector x = { 1/n, 1/n, ..., 1/n } // initial distribution
do {
old = x
x = x * T
delta = | x - old |
} while( delta > EPISILON );
</code></pre>
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
So once the algorithm is complete, <b>x</b> will be the stable distribution, eigenvector and the PageRank of the web.<br />
<br />
So its been a pretty lengthy article for such little code. Always the way with Maths heavy algorithms. For more information on PageRank read "The PageRank Citation Ranking: Bringing Order to the Web" and on Markov chains I highly recommend "Finite Markov Chains and Algorithmic Applications" by Olle Häggström.<br />
<br />
So Appendix A has a high-level explanation for convergence. Then Appendix A shows how Google converts the web graph into a Google matrix so that it has a convergent property.<br />
<br />
Right I applied the algorithm to the request for comments (RFC) and used citations as links/edges. The PageRank of all RFCs (at the time of writing) in descending order:<br />
<br />
<a href="https://github.com/iainkfraser/PageRank/blob/master/rfc_pagerank_with_titles.txt">https://github.com/iainkfraser/PageRank/blob/master/rfc_pagerank_with_titles.txt</a><br />
<br />
That's all folks - PEACE!<br />
<br />
<div style="text-align: center;">
<br /></div>
<div>
<div align="LEFT" style="margin-bottom: 0cm;">
<b>Appendix A - Convergence</b></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
I'm
going to very <b>briefly</b> describe state transition restrictions
that allow convergence. Then i'll explain intuitively why convergence
occurs. If you want to learn more about Markov Chains in more detail then refer to a book, it's a subject in its own right.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<i>Theroem: Any
<b>irreducible</b> and <b>aperiodic</b> Markov chain has exactly one
stationary distribution. </i><br />
<br />
Before I explain irreducible and aperiodic
let me say the converse isn't true. Not being irreducible and
aperiodic does not mean there isn't a stationary distribution it just
means there may not be. So irreducible and aperiodic chains are
interesting because we are guaranteed to have stationary distribution
(and therefore a PageRank).</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
An
irreducible graph means there is always a way to get from one state
to another eventually. If you can't you call it reducible. Figure 5.
has some example illustrations.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBAh0LrkO9RY9ow_1o4ARl-rrN18D_CrZTlA14qHWDAaoY0IIokgODHZZF7TxFRaZVCumYuJEgDEku_m-S9EEtxpopiZv-bqo_Cmv_iABMWN4_GDEHxVXXekIsrhunGd6fu3ACtz03lwU/s1600/irreduicble.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="82" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBAh0LrkO9RY9ow_1o4ARl-rrN18D_CrZTlA14qHWDAaoY0IIokgODHZZF7TxFRaZVCumYuJEgDEku_m-S9EEtxpopiZv-bqo_Cmv_iABMWN4_GDEHxVXXekIsrhunGd6fu3ACtz03lwU/s400/irreduicble.png" width="400" /></a></div>
<div style="margin-bottom: 0cm; text-align: left;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
Figure
5. The two chains on the left are reducible and the one on the right
is irreducible
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
By the
way its called reducible because you can split into two or more
separate graphs and model those using Markov chains. So its quite
obvious there can't be a stationary distribution because remember the
stationary distribution means: the probability of getting from any
state to a certain state is constant. So clearly if you can't get to
a state the probabilities can't be the same because some states can
reach but other(s) cannot.
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgH9LOEl1Zkra75_xLYWpjec2QcbJeBDTSdO9GVy1eHoS4mPruPGFTGY1Vyv1TXSZWBujvKocO69287rDPg5YUdW-hbqSnGHA1zPyj9uoy1Th_bgvgnxo-p0Qv6SMfh9-e5oWgod4a5ThQ/s1600/aperiodic.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="85" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgH9LOEl1Zkra75_xLYWpjec2QcbJeBDTSdO9GVy1eHoS4mPruPGFTGY1Vyv1TXSZWBujvKocO69287rDPg5YUdW-hbqSnGHA1zPyj9uoy1Th_bgvgnxo-p0Qv6SMfh9-e5oWgod4a5ThQ/s400/aperiodic.png" width="400" /></a></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<span style="text-align: left;">Figure
6. The two on the right are aperiodic and the left has a period of of
2.</span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Aperiodic
is a bit more difficult to explain. So I'm going to explain it with
an example, again read one of the Markov chains books for the formal
definition (quickly its the greatest common divisor of the number of
steps to get back to the same state).
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So look
at example in Figure 6a. If you place all one hundred people on S1. Then if we do the
next step they all move to S2 (so none on S1). Then they all move back to S1 and so
on and so forth. So clearly its never going to converge because it
oscillates. It has a period of 2, because getting back to state S1
takes a minimum of 2 steps.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Compare
that with Figure 6c which is aperiodic. So S1 is trivial because we can get
straight back to S1 in one step. But S2 we can get back in
2,3,4,5,7... steps. Why isn't that periodic? Let's run through an
instance of a Markov chain. So all 100 people move from S2 to S1.
Then 50 go back S2 and the other 50 stay on S1. Now look at this
distribution (which originally started with 100 on s2) we can get
back to S2 now in 1 step forever. Ergo its not periodic.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So let's
get onto a intuitive description of the proof. If the graph is
aperiodic and irreducible then eventually (after a number of steps)
every value in the transition matrix will be between 0 and 1
exclusively (i.e. not 0 or 1). Because there is a way to get from
any state to any other state.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJ4Mn-LDsFa6e-OVxTIzMQNYNtqD8knDSwcaPgIX7r8JT4qMPF5Rx9nmFFK5MozjTYJhWGE6C9HsRGx86o5toUaYgi8WkT1DUWF7lup625Jt7Mys8W7_kaCvsjuTdVw4lFggOQlVVPHHs/s1600/step1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiJ4Mn-LDsFa6e-OVxTIzMQNYNtqD8knDSwcaPgIX7r8JT4qMPF5Rx9nmFFK5MozjTYJhWGE6C9HsRGx86o5toUaYgi8WkT1DUWF7lup625Jt7Mys8W7_kaCvsjuTdVw4lFggOQlVVPHHs/s1600/step1.png" /></a></div>
<div style="margin-bottom: 0cm; text-align: center;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: center;">
Figure 7. Probability of moving to B in one step</div>
<div style="margin-bottom: 0cm; text-align: center;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
So let's start thinking of a hypothetical graph shown in Figure 7. I was going to use variables for transition probability but I think numbers are simpler to understand. So if we were playing a game and wanted to get to B in one step we would start at C and if we didn't want to get to B we would start at A. How about two steps? </div>
<div style="margin-bottom: 0cm; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="margin-bottom: 0cm; text-align: center;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqB0oQmkS_6isdlpimB0vwgphzl8D9O1r88hu3qoxtYB0UsFE5NkAWMTjsFh27ws_Hq9MDNVWaMDfwhUXeA4ihTqB9PxQGs3Ep_4mNPQf5PmacJ5O9P4qenrSlNQxQZgoEoKaV0B5DDEY/s1600/step2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="171" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqB0oQmkS_6isdlpimB0vwgphzl8D9O1r88hu3qoxtYB0UsFE5NkAWMTjsFh27ws_Hq9MDNVWaMDfwhUXeA4ihTqB9PxQGs3Ep_4mNPQf5PmacJ5O9P4qenrSlNQxQZgoEoKaV0B5DDEY/s640/step2.png" width="640" /></a></div>
<br /></div>
<div style="margin-bottom: 0cm; text-align: center;">
Figure 8. Probability of moving to B in two steps</div>
<div style="margin-bottom: 0cm; text-align: center;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
So if I asked you to try get to B, what would you say? B->C->B right. Because we already know ending with C -> B is the optimum for one step. So we want the optimum something to C which is B. So the optimum odds of landing on B for 2 steps is 0.54. Notice that the odds are worse than just the single step.</div>
<div style="margin-bottom: 0cm; text-align: left;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
Now if I asked you try to avoid getting to B in two steps what would you say? Well again we want to pick the most likely of landing on A->B (the least likely single step) so we would choose A->A->B which has overall odds of 0.18. Notice again these odds are greater (so in response to the question worst) than the single step.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgD3VTHWB_sCh0j0r8a4b9Gkvh4RmlVGC3qwfdneqnMyiuPPnTPnR0_M0sV8wXr6YRui_0D2aCaHwdKSUifeV6-OVE0TfOTyOplU25YqD-RCgDFoFopqMtQTCq36z473dI0XKppu04_oaU/s1600/step3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="352" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgD3VTHWB_sCh0j0r8a4b9Gkvh4RmlVGC3qwfdneqnMyiuPPnTPnR0_M0sV8wXr6YRui_0D2aCaHwdKSUifeV6-OVE0TfOTyOplU25YqD-RCgDFoFopqMtQTCq36z473dI0XKppu04_oaU/s640/step3.png" width="640" /></a></div>
<div style="text-align: center;">
<br /></div>
</div>
<div style="margin-bottom: 0cm; text-align: left;">
<br />
<div style="text-align: center;">
Figure 9. Probability of A->B in three steps. Notice the minimum is increasing</div>
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
This illustrates why convergence works. The maximum and minimum probabilities of getting to B will be in the first step. Because in the next step the probability of getting to the maximum step is not 1 so its going to lose a bit (to the other branches). And the probability of getting to the minimum step is also not 1 so we will gain a bit (by the other branches). </div>
<div style="margin-bottom: 0cm; text-align: left;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
Through induction (due to recursive nature of the steps) we can show that after each step the minimum will raise and the maximum will fall until they eventually converge. Therefore no matter where you start you have the same probability of getting to the destination (B in this case).</div>
<div style="margin-bottom: 0cm; text-align: left;">
<br /></div>
<div style="margin-bottom: 0cm; text-align: left;">
It should now make sense why you don't want 1 or 0 entries in the matrix forever. Because that means the maximum or minimum doesn't have to fall or raise and thus converge. </div>
<div align="LEFT" style="margin-bottom: 0cm;">
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<b>Appendix B – Google
Matrix</b></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So we
need the Markov chain to be irreducible and aperiodic to guarantee
that there is a stable distribution (see Appendix 1). An easy way
to do that is to have a link from every state to every other state.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So how
can we transform the hyper-link graph into this type of graph.
Because clearly every website doesn't link every other website. The
way Google does it, is to imagine that the random surfer may get
bored and when that happens they randomly teleport to random website.
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So how do
we apply this logic to the transition matrix? Well we need a
probability of the user getting bored call d (for damping) which is
usually set to 0.85 (the clever dudes at Google figured this number
out). Then we can convert the transition matrix to:</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<img align="BOTTOM" border="0" height="38" name="graphics16" src="http://latex.codecogs.com/gif.latex?dT%20+%20%5Cfrac%7B1-d%7D%7Bn%7Dee%5ET" width="114" /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
So the
d<b>T</b> just dampens all the links due to the chance of getting more bored. Then there is a chance of ( 1 – d ) divided by the number
of sites of randomly teleporting to another site. So we need to add
that to every entry in the matrix which is what ee<sup>T</sup> (generates a n x n matrix of all ones using outer product).</div>
</div>
<div>
<br /></div>
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
Anonymoushttp://www.blogger.com/profile/05316739893737008207noreply@blogger.com162tag:blogger.com,1999:blog-7285522818349864667.post-50720114993532779532013-01-30T22:35:00.002+00:002013-01-31T17:09:43.472+00:00Cache Money Hoes<div style="text-align: center;">
<b style="text-align: left;">Attached Code: </b><a href="https://github.com/iainkfraser/cache_transpose" style="text-align: left;">https://github.com/iainkfraser/cache_transpose</a></div>
<div style="text-align: center;">
<br />
<div style="text-align: left;">
<i>Before we begin, the underlined words are briefly described in the glossary at the end. If there are any terms you don't understand let me know and I'll place them in the glossary as well.</i></div>
<br /></div>
<div style="text-align: left;">
As the wise contemporary philosophers the Wu-Tang Clan<span style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: x-small; line-height: 16px;"> </span><span style="background-color: white; color: #222222; font-family: arial, sans-serif; line-height: 16px;">once said:</span><span style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: x-small; line-height: 16px;"> </span></div>
<blockquote class="tr_bq">
<span style="background-color: white; color: #222222; font-family: arial, sans-serif; line-height: 16px;">"Cache Rules Everything Around Me ( C.R.E.A.M ) "</span></blockquote>
Many people believe this is just typical rappers exhibiting the materialistic nature of modern life. However, they were in fact visionaries describing the importance of memory hierarchy utilisation on processor performance.<br />
<br />
Traditionally the <u>time complexity</u> of an algorithm was based on the RAM model. The model assumes that access to all memory locations takes equivalent constant time. In reality a <u>cache hit</u> is an order of magnitude faster than a <u>cache miss</u>.<br />
<br />
Therefore it should be possible to significantly improve an algorithm by reordering its memory access to be cache friendly. This isn't a particularly novel idea and it has a name: c<i>ache aware algorithms</i>.<br />
<br />
The problem with cache aware algorithms is that they depend on the cache size. The algorithm must be tuned for every different cache it runs on. This unportable tuning was the inspiration for<span style="line-height: 19.200000762939453px;"><span style="font-family: sans-serif; font-size: x-small;"> </span><span style="font-family: inherit;">Harald Prokop's <i>cache oblivious algorithms</i>. They are algorithms that are cache aware but don't require tuning.</span></span><br />
<br />
To illustrate cache-oblivious and cache-aware algorithms we first need an algorithm we can improve. The key is that we don't change the time complexity at all. That means we still do the same number of operations - so the processors do the same work. The only variant is the order of memory access and therefore cache utilisation.<br />
<br />
Algorithms that access memory often are ripe for the picking. I decided to implement the matrix transpose because it one of the simplest memory heavy algorithms. The matrix transpose simply takes the rows of input algorithm and makes them the columns of the output matrix, like so: <br />
<br />
<div style="text-align: center;">
<img src="data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEAAkGBhIGERQUBxQTEBMUEiAYFBcRFxgXFBMfFhwVGRMZFBIYJyckGR0lJRkYKzAhJC8tOC4tFh89NTwqNSoxLCoBCQoKDgwOGg8PGTAkHCI1KjU1LC81NC0yKjUpLC8qNCwsKTUsLCwwNSwtLSksNSwsLCkwNDY0NSwxLC8sLzYsNf/AABEIAGYAxQMBIgACEQEDEQH/xAAbAAEAAwEBAQEAAAAAAAAAAAAAAwQFBgIBB//EADgQAAIBAwEECAQEBQUAAAAAAAECAAMEERIFEyExBjI0QVFhdLIicXOBFEKxwxUjM5GhJDVSU3L/xAAYAQEBAQEBAAAAAAAAAAAAAAAAAQMCBP/EACYRAQEAAgEDAwQDAQAAAAAAAAABAhEDMUGREyHwEmFxwVGx4QT/2gAMAwEAAhEDEQA/AP3GIiAiJn9IK7WtpcPQOlkt3ZSOYKoxB4+cA1xWvP8Ab92iEcKlTU+riOrRXTlSOTax8iOJ0J4o0hbqFpAKqgBQOQA4ACZ1HbJe9qWroBot1rBw2dQd6iYKYGCNB7zzneOGWW7O3uNSImTR205utxcUTTVqbPSfVnWKZVampMfB11xxOc90Y4ZZ712NtOsGZTuCFbB0lgWUHuJUEZHlkfMSpRuqluQNpBBkhVqUydLE4HxI39PJ4Aam8M5Izemd0j4WtcjmlJqinnpamNdNhnvDKpHynA0YiICIiAiIgIiICIiAiIgIiICIiAiIgJmdKOxXXpansaaczOlHYrr0tT2NA05i09lVUv3uTu9DW60cam1AI1R9WNOOJfGnPdnPdNqJphyXDeu80miZNta3QuXe4ajuSMIFDGqoHIajwwTknh4eE1okxzuO9d1JndI+x3Pp6nsaaMzukfY7n09T2NOBoxEQEREBESK6ri1Rnfkqkn7DMDxd39Oxx+JdVLHCgn4nPPCJzY+QyZNSqCqAVzgjIyCDx8VPEfIyvY2m5GqqAarKN42PiPlnwGTgchLWYCIiAiIzASpb7UpXT6KbjeBdW7bK1MA41btsNpz+bGJbkVxapdgCuA2DkeKniAynuPE8R4wJYlLZNw9eni6/qI5R+XxaThXwOWtdLae7XjuiBdiQ3V2lkuq5YIuoLljgZYhVGfMkD7yaXV1sJmdKOxXXpansaaczOlHYrr0tT2NINOInNtdVNn7RRLitVNOvTbSjou61rpKrRdRkHSHJDk5xw5TXj4ryb1ekt8Jbp0kROVHStLraVGha16LIaVYMiOpqbymaWA4BypwamF5/Ax7uF4uHLl39PaW+Jst06qZ3SPsdz6ep7GmjM7pH2O59PU9jTFWjERARIkukqOyIwLoAWXvXVnTkeeDM/Zu3v4lXrURSdDQYK7MUxlkSooGDniGH9jNJx5WWydPf55ibaso7c7NW+k36GXpR252at9Jv0MzVenOXAVdr0dOkMbGtqxjJ/mWgGf7f4nRyBrKmza2RC+c6io1ZHAHVzm3DyTC23vLPM0lm085W9opa7QoVrVA5d2o1HpVM1AxDHFZO+muk8M8CROqka26IxZVUMebADJ+Z744eX07fvLPJZtJOSqbK/wBeLlDa3WKu7bKD8RbZXSAlUE5wckqQODsfI9bI1tkViyqoY82AGo/My8PNeLeu815+dizaSIiYKo7N69f6/wC3SiNm9ev9f9ulECjt2kdsM1to1IaRNQurhDq+FNFQKVLDiccx8M+dHtoVNsWg/EpUSso0PvUq2+sr+ddY1BW58M88Tdiej1p6f0a6a/3z+k17qNhavQJNblj/ALalT/DgY+ci6UdiuvS1PY005mdKOxXXpansaY5ZfVd1WnKlDZVOg2pQzHUWGtmfSW6xQMTp+0txEys6UJSOxaBrJW3aiqisqsBjAqaS+QOBJ0jifPxMuxGOVx6UJndI+x3Pp6nsaaMzukfY7n09T2NORoyOvWFurM4YhVJIVSzHAydKLksfIDJkkRBx73NWzrW1zunK1iadYJSrNU0v8VNqtMJlChAHxHgHbym9Y7EWwrXFam9RmuWVnV9OhSihF0aVDDgBzJ5TSienk/6LlNSa9tfmb3PDmRmWdlUpODV5Dn/Pqv3H8rDB+8l252at9Jv0MvSjtzs1b6TfoZjnncruul6IlBNu29SubdKqGuBkpn4uABP3AZTjngiTHDLLepvQvxEgrXtO3amlZgr1WIpqTxcqpZsDyCkySW9BPEStU2jTpOKbMN4fyjJYA8iQOQ8zwiS3oLMREgo7N69f6/7dKI2b16/1/wBulEC9ERATM6UdiuvS1PY005mdKOxXXpansaBpyp/F6Bq7nfUt9jO61rvcYznd5zyluc1Y22i6L2Vw9UGqwrUqyLmnkHjSbSrAAgcyQQTN+LjxzmVy7T52v6/KWulkL3aU2VHdQ7dVSwDNzPBeZ5H+0mnIbDrXFC4xVRmercVfxGtcbpFNT8NUSp3hlFNdOTxJxjDRxcP145XfT5+v6nct06+Z3SPsdz6ep7GmjM7pH2O59PU9jTBWjERAREQEo7c7NW+k36GXp4rUhWUq/Jhg/eB7nO1b2nc3yI9vcaqJJp1Ny4o6nT+Y2/xp4LkeZYiaNrffhQE2limwOlGLDTVAPwFSfzEYyp5HOMjidAHV1eM1485hvc6y/bqlj7OL2ja3tXaVo9WihpJcVMVEqMxVDRqINa6AEznPM5Y4+XaROuDm9K26l3LPM0WbJyFhbXlnctpVs1L12rMSDRa3IYUSpzkVFxTGBj82cjBnXxHFzXjmU1Lv+SzZESlc7UWmdNtirVI4U0I1f+m/4qO9j8hkkA4K+bN69x9f9ulElsLT8EmGJYlmZie8uxZseCgnAHHAAHHEQLMREBMzpR2K69LU9jTTlLbdo20LavToY1VKLourgMspAyfDjAuxIra4F0ivTzhhnB5jxBHcRyI8RJYCIiAmd0j7Hc+nqexpozO6QDe29SmnWrIaSDxaoCo+wyScclUnugaMREBERAREQPjKHBDgEHgQeR+YhECABAAByA5D5CfYgIiICIiAninSWiMUgFHgBgf4nuICIiAiIgIiIFGps4o2uyqNTJ6yka6TZxx0Hqnn1SM6jq1cMXoiAiIgeagJB3ZAOOBIyAe4kcM/KVbbZ+7Yvcu1Vzy1cETyp0hwHM/EctxwSQAAiBciIgIiICIiAiIgIiICIiAiIgIiIH//2Q==" /></div>
<div style="text-align: center;">
<br /></div>
<br />
You don't need to understand matrices at all to understand this algorithm. You only need to understand one definition:<br />
<div style="text-align: center;">
<img alt="[\mathbf{A}^\mathrm{T}]_{ij} = [\mathbf{A}]_{ji}" src="http://upload.wikimedia.org/math/6/7/6/676a09fb68a5cfb70409594b8622e226.png" /></div>
<br />
This simply states that the entry with jth row and ith column for the input matrix is equal to the entry with ith row and jth column in the output matrix. <br />
<br />
This cache-unaware or naive algorithm directly uses this definition. As shown below:<br />
<pre style="background-image: URL(https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj2pTTGb1U6OPolmlE60ECZlveVwpgfeCQvbPvNJ6BU0CtAmdzO3KuZNNuncxQe69TT8Pxy22zoHm9TlrCyBxImcwJ6wGZQAa4YxOytwjB95V2rZEkg0CASkvu9boPdkqhkP8DbEfigPf67/s320/codebg.gif); background: #f0f0f0; border: 1px dashed #CCCCCC; color: black; font-family: arial; font-size: 12px; height: auto; line-height: 20px; overflow: auto; padding: 0px; text-align: left; width: 99%;"><code style="color: black; word-wrap: normal;"> for( int i = 0; i < N; i++ ){
for( int j = 0; j < N; j++ ){
out[j][i] = in[i][j];
}
}
</code></pre>
<br />
Just a side note, the matrices here are large e.g. in this blogs associated code N=1024 i.e. the matrix is 4MB ( each entry is 4 bytes so 4x1024x1024) . Anyway back to the analysis 2D arrays in C are stored in <u>row-major</u> order. <br />
<br />
This means that an entry's horizontal neighbours ( i.e. row neighbours ) will be on the same cache line. Unless the entry itself is at the end of a cache line. Therefore accessing a horizontal neighbour will likely be a cache hit. Conversely accessing a vertical neighbour will likely be a cache miss ( unless its a relatively small matrix and its row is small enough to fit in a cache line ).<br />
<br />
The naive algorithm reading the input matrix will often cache hit because it traverses in row order ( the inner iterator j walks the column ). However writing to the output matrix will likely cache miss due to column order traversal.<br />
<br />
How can this be improved? Well we can change the order of writing to minimize the cache misses. That is exactly what the cache-aware algorithm does. It splits the matrix into a set of sub-matrices that have a size equivalent to the cache line. Then runs that algorithm on the sub-matrices:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYVdxVGwXKNj-y0Gf5_tFSs6Vz0Ly7fytaxa0pMqCkTS055gDemSHE0uWtxBiqGNWTiAFJp6lp38arbPzJcH87c7enpipeIlQdKiadCGCKG1NTQ9EgBE5oH_7ZPW3VCX0JHPw8s1ZFSEw/s1600/matrix.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="132" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYVdxVGwXKNj-y0Gf5_tFSs6Vz0Ly7fytaxa0pMqCkTS055gDemSHE0uWtxBiqGNWTiAFJp6lp38arbPzJcH87c7enpipeIlQdKiadCGCKG1NTQ9EgBE5oH_7ZPW3VCX0JHPw8s1ZFSEw/s320/matrix.png" width="320" /></a></div>
<br />
Don't let sub-matrices confuse you. We are still essentially following the <img alt="[\mathbf{A}^\mathrm{T}]_{ij} = [\mathbf{A}]_{ji}" src="http://upload.wikimedia.org/math/6/7/6/676a09fb68a5cfb70409594b8622e226.png" style="text-align: center;" /> rule. The only difference is we are restricting it to a sub-blocks of the matrix. Once the block has been transferred with minimal cache misses we move onto the next block. Use the source Luke if you want to know more.<br />
<br />
The problem with the previous cache aware algorithm is it took the cache line size as a parameter. So we would have to tune it for each different target. Can we eliminate this tuning? Sure we can! The cache oblivious (CO) way.<br />
<br />
The CO basically keeps splitting the matrix into sub-blocks until we reach blocks of size 1. In reality you set it to slightly larger then one to minimize the cost of recursion. Then apply the transpose on the blocks. So the CO is basically the cache-aware algorithm but the tuning is done automatically through divide and conquer.<br />
<br />
But wait, isn't setting the block size too small going to cost a cache miss? No thats the clever bit! If the block is smaller than the cache line then the siblings and eventually parent block ( the block that encompasses the subblock ) will still be in cache. As shown below<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-d0msAgZQ30apMMHnZzGviUoevlYnDkWEU8X64SrkAq-2jDvBbj9nI2Wj0vgAuTpEnf-OHcQQz70oNJrLtVY0ZYrNSverap1fK6dXjokfPqXJ1xfuTg8q1-Q4ZdGH3chx50cmI50psDI/s1600/matrix1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="212" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-d0msAgZQ30apMMHnZzGviUoevlYnDkWEU8X64SrkAq-2jDvBbj9nI2Wj0vgAuTpEnf-OHcQQz70oNJrLtVY0ZYrNSverap1fK6dXjokfPqXJ1xfuTg8q1-Q4ZdGH3chx50cmI50psDI/s320/matrix1.png" width="320" /></a></div>
<div style="text-align: center;">
<br /></div>
<div style="text-align: center;">
<br /></div>
The initial block being accessed is the sub-block in the top left consisting of red and blue blocks. Its entries are shown in the cache line above. Once its been accessed its sibling block ( the top right block consisting of green and yellow ) is accessed. Since the blocks are smaller than the cache line the siblings entries are also in cache.<br />
<br />
So lets see if the wu-tang hypothesis is correct. The average results of running the transpose on a 1024x1024 matrix 100 times are:<br />
<br />
<table border="1" style="text-align: justify;">
<thead>
<tr><th>Naive</th><th>Cache Aware</th><th>Cache Oblivious</th></tr>
</thead>
<tbody>
<tr>
<td>5704 ms</td>
<td>763.33 ms</td>
<td>1212 ms </td>
</tr>
</tbody>
</table>
<br />
Of course the Wu-Tang clan was right on the money. So the algorithms are doing the exact same amount of operations and the difference is huge. The cache oblivious algorithm is slightly slower because its paying for the recursion. As the size of the matrix grows the cost of recursion will reduce. So we can say that the cache oblivious algorithm is asymptotically equivalent to the cache aware one. <br />
<br />
This blog has given a very broad overview. For more information please read <span style="font-family: inherit;"><span style="line-height: 19.1875px;">Harald Prokop's MIT master's thesis and the attached source code</span><span style="font-size: x-small; line-height: 19.1875px;">. </span></span><br />
<span style="font-size: x-small; line-height: 19.1875px;"><span style="font-family: inherit;"><br /></span></span>
<span style="line-height: 19.1875px;"><span style="font-family: inherit;">For the people that do read the thesis one thing that had me confused was the cache complexity was often stated as O( 1 + k / N ) and I couldn't figure out where the 1 came from. Its because big-O represents worst case, and the worst case in terms of cache is when the memory address is misaligned so you have to pay for an additional cache miss per object access. </span></span><br />
<span style="font-family: sans-serif; font-size: x-small; line-height: 19.1875px;"><br /></span>
<br />
<div style="text-align: center;">
<img src="data:image/jpeg;base64,/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEAAkGBhQSERMUEhQWFBUWGBgXGBgYGRsXFxoXHBkYGBoYGBwXHCcfGBojGhgXHy8gIycpLC0sFx4xNTAqNSYrLCkBCQoKDgwOGg8PGiwkHyQsLCwsLCwsLCwsLCwsLCwsKSwsLCwsLCwsLCwsLCwsLCwsLCwpLCwsLCwsLCwsLCwsLP/AABEIAMIBAwMBIgACEQEDEQH/xAAbAAACAwEBAQAAAAAAAAAAAAADBAECBQAGB//EAEIQAAECBAQDBQYEBQIGAgMAAAECEQADITEEEkFRBSJhEzJxgZEGQqGxwfAjUtHhFDNicoIH8UOSorLC4nPSFTRT/8QAGQEAAwEBAQAAAAAAAAAAAAAAAAECAwQF/8QAKBEAAgICAgEDBAIDAAAAAAAAAAECESExAxJBIjJhBBNR8HHBFCOB/9oADAMBAAIRAxEAPwBKRmUZbzC2VQLA7kPQBmbXaDpCaOVAqlqBs7BhYaxEtRAHOHCuZzoS2328Ekj+WSlIcEE0DEkuBXWNkYBgEpSs51hpaa9CQxFbmOVlzLOdVctOiSH18NIth5pcDMhI5kqSA7m4DgUZ4IVOCULAKkljlYk6lwH2hiDpQkqPeUTNzWZuQtuTQwHCrSEy2T/xBmqQQWobVoYIvElLgTBmCQT5MdqAgl4Ilc1lALTcFNUvkvr8IBBMIEMl0KfOWbmALatp9Y6TII7MlASRmAzHcGzm+rNrAZssKU3aEEKQtgSaFtrX8IHOWhImUWoJUlVwmoOWjeZeAQwieXCs6GyMaAsU94OAwHSDTMRLUFDlcpCu4TfuljfwgGFUoIokZcxLNVi7Ek3cxVBKgVGTzFBDEF6WFKNan6QAMT5wBVz5SUijBLBhdTOP3ikwLzKZaQyECiqhqqJf5wKYiYsgLlB8hc2qFOA+lBBJ0vmXyJdSLKVUnUXozXhAX7V+0AmsTlWwcsij3b4QKdOylZM0+ABJDlx3mFotIWqo/DDSxZrjbNpXWCozKcKyZcoqchcvqIAOmTkhXMtbZkqDhhbL6A184T7NHZqBmOAsPy1Cq7b7wSbnUZrdmdgMv5hQ9IuuWR2g7FJFDrVWpd+sIYPEzwgTCM9VAulh8ateCKmfzQmWonvVJZVQCCA21GiFTFhS6JSnKkBgCSaV1JEaP/4ZalKVMK8qgQAaAgnQhTsz6a9YmUlFNsErEJKCtakkIQxCwCHVo7h6XADVMHThZtCMoAW5BAcpoyRlB119Ho+kjDBJdg5p9P1Hmr8ojQkYdjnuXdI3P5m6X6MkC0cv35SVpUadEKK4caAgJPvKAAUT/S9EgD3qnY6xm8V4TcoSmYMzmqgqlrUcVtGhxaYsAIQ5mK1u2jsNBQaQhKQcMkZlZnIzAnmrYn9GFGjj/wAmcZdvHyX1VUYxzOSkISUrBBUXBd3N/SkXxZCgpuyPNro+tGcwxj+GofNLllSVKBUAouNv8a+UIFQWS8uYkZwDVnv0qI9Pi5I8ke0TFpo7NMyqcoqoZWyaeBp84pPmrJSMiVgLIcCwoXfRqxGLxEtakOipJALtr4VtA1FBNFKGdZPpTQ2jQCVJVzcgSyndvGpfSBTTMGclaRWlrAdB84riGWk8yyM1fAOwqdIicpRSpkAnMzNRjs20AAsZNcqGcvylkuC522iypicwehzNfVvjFJqCCpRSxoHAOnQ9YpMWoqAUkGt2dmAGnWAoqhk5cyiam43br8YGldQyizqvR2o3g8WzKccgYCpI1uwc+ERZgAm52p4CEMGkqIuD5ftERaWhTCo+/KOgoLGhlUpYCC4ZTubliBSxrGhOQRVMsBspdRNzcgPC0tKstZgGZJa4FKEhvnFky0kqqTRIAA0La61i0SxpEvKUMJY5vBiW1NzrBsKFg51S0uMwBcn3X3gCVozsSaKSpiHZwAK6CCSAKgEAlSk8w1IHjWGSGJJUSZYLyyXyl3y1S4P20WyDMsCUTyJsSxDCgpp9IDhkFMvKZndCklgqhuDW1HiyZ4yK/EJGRKuUEHQO5LeUAF1pPMpKQklCSSXoaEAvQCkWnIWXV2oAKRRyQC4KiG8aRVE78UkoKmlh3JUTSwFnaDCZoZYAyg2IqDRIbppAIopOZa+dIOZGtSXfXpFFDIljMSCAuoJN2rTb6wVOUK5ZdSsFTkuDVi2zRXDTwopUZYDlaSWNCbGpsaQgJQUIyOpailBrQMKuS77wOWUUPZk8ijdzcmtndvjBEkkAASwSg16v3dQzxdeIKQB2gBMssAzOAasBX6NAAKaEkzCuWCMiHYkFy1G0gc5aES3ys2QMDW+bbreLqmLKe+lRKQRoHF7hiIMU5goL7J8oLliRQO4td4QApqJaSs5jzKS9AdXHl+0dNSg9oQVqzqagBIINPEaxaYpRLIyKI7MkABtiz9I1+BYCZmJmJAqSAKBlUFrk1r0PSFJ0rGslpGAEsoX72lAHAHnQM/iQdKPS61ByipYaJJJoDu7t4Qx2TqA3DB6BKBc9cxP/AFGKmQBTUm/hrXT/ANd48/kuTNVgFhcI6sx8AnQCxfwAb/njTmkISVHSwP3qfWBBDAAUDV8NB6N8OsYvtDjeYSZZOdTW0Fg2jmoHmTRMYcs69MS0jK4pxITZuQOqtSNCKhIPS52q+sdjOK5kZCo83K4UtgBYHPVfifWzaOCwEvDIykBSiOdRHKnVrVSCP8ix0YeW4pORMWVS05QOrv8A1BtDdtIlQlFbGti2H4rPkzCkl0v3SxBGzmvn66xrLUTzySopU5YmqVWZozJTTAyriz/dj+8O8NQxIHgUm77p3Px8Yvil0l2j/wBQTVoFhlzBLRmZ+a5BLguG9fhFUzFMCQgMl35bvcNu4jp8luUoyp53ZzcUI+9DA5mFCUq5VqOVKasA3Q+UeqnatHODXODy3IJJKjlRcb/R4kLRopRzKLav0EQmWXBZLhH5n8ooh+WiNTpTaxhgVnSO6c7AEks7/sIGuYySAsuA5NddYlKgznI5BoFFmEBUh7JTmUmvM4ppWAorNSA5K9BUg6iBlIJVelKMGo2sEUglqgBk2bTqYHPmnKrmAY3/AFgGiq58sFqiOgKzXvJ8/wDaOhAbcuWbAAByzkHlIqzlrtDAJDJdAJS2jv5eVIz8MjNUghgpPldrbw2Uuksg1CTfUs9B4AxaJYXDKJHeSSQQbDmFjUWG0GKiK/hh8qnLXsR+8DUkpPcBDpIrqRrWClNFICUGpAJZnuKeIhkhzMJL5k5cwUwIsQzGmu8SlASkhIlimxVVJqG1YQtlIPMlPcLMphQbaQRFVPyMWNyXKkt6EwAcJ4P/ABFk5CRQfIG9LRMspyhjMqjZtfGheBSJpJQ0xnSqycrmtaWaJQrPkGcFOVrkOp7/AEhWA0qYop7s3uiubmJB02gOIXcrTMOUBYBNyGoKUiMEhgEmY/etmNC+up/SAyEg8+ctkNWL7Zr0F4BDUuYhyAgkEs705qmwdnioBLfhgZSAaGxFwTWLIIOfLMIAEssM1uniY5UoELBStbrTYNcvR7jrABKJLZXRYqTRTBjRwCbdItKwaitKAhJGUJ73MXplIG5YWgUxKUg0LqXuzAEhxSnhHqvZngyEjtlIeYAcpV7vM6WfUua6RLdDSsHgOCplr5srosz5QoFgTmu1SB06iNAEsH7yqqJNXNEjoyW8zFp55gm4ofkoqPiSkeBV1gahmAa5LaW949Honz6RzSk3s0SLSBRSvBqaVCR51X5xGZ+Yh9ALPeg6XJ6HoIX/AIkrVlFEI7x3Lcx8AOUeJgs7FhKStRZhR9B12JZ26AXjlvqnJlAeL8U7FOqlqOgqVFgwHpbcamE+HYb+Glqnzw81bvahNAhLA1LMSNiBQEmJKkoH8ZiTlakpJvU0IGq1P5ON6Am4pc5aZiwElIBTLNUygffX+aavYPQAAXiIrr6n7vH7+Si3EMR2icq5SyTUMQEpJ1IdSlADoLXjzGLwRSaUIr+4/SNvG4nQImLWSFBWUE75srZVD+gVtUvGVM4zMUs/xASoXSqWkJSRqQAHfcGohSTQJiGZ6iihUj6j+n5QxLmCYxsoff3+0ROSFF0M2jfoT8IVUnLUUa42/b5QSjeUV8G3Km9qAFllaKsXtVt/WM2ehQSoKCnASCGaoJq516xEifXNo7HodH2h/GoTOQxfMGY7gWB+T9Y3+n5q9MjKUfKMcpbtPw1EZQHJJBsGYWiilAOEiqQK1Pl6wXEEfiABblTGwrf9op2przKDpdmtQW3tHoEA5Mx0g9mKg2Bv9bQA3bI3KTR/SCrWyVB1Cl21s14qE0KQTRh1Bo8AwPZgAhiWCR9WtpErQ5UcpLUANi5eCT5jP3jmO9m+kCWhxRJqqxO1j4QDAzUl+6/34x0ET/YY6EUbEmpZzRXhcfSCJB5U5VKGU3Uet21tWASZlnXTMg2OzfOOlIAUhyqiTl0q6vj4xSM2OZCC4Sl8qSzl6Mw8o7sy7FKgy02YvS/0gMgJKfeAKACblgaCm0M5HJbOzoOwLDTyhkhf4ZuXKpmUm+zl7fGKJJApL9xFXOhpta8cocw5XDrSRma/6iLzJCClQB90MM1GFvjAAckgpYoSxrYmo+pcwvKDDvSyc7Bw2lQKXiJksArKQCSUtVzQCrROU5jyBs9C3S/rAAUBiClUsjms2j0rXWBSAyUnMhhLUSw6tT1iQg5U8iKBb11JZmeBy5YYpyoHIQAVaAuNbQCCYrFJ7NQzqHcFBWz+JpElSCGJWXWgXbLyj4ROJBLEZDzA0IFMrCp84hSVAqzFJGcEOxYNaAA2Aw6FzkJSVfzqjQhIJKegIFzH0JacqEg9VKt1J6VJMeW9kEdrOKiUfh5u7+Y2JcXYH1jU9qZ2eWJQOVWIV2QY8wlMTNUNmlgt1UneMpFrQtwqYqYheIUf5ysyAf8A+YcSgH/M5mn/AOUDSBY3GKDJQeddj+VIuv1NBuUjwP3lBKQyUBmGgZmHkyQNH6RKEOSpTBTcoFQlALD6sTcknrHPLJSKYZAlpynQ1O5v6AVMZ0mYJpM+bTDyycouZkzfqBYC1PKOUg4iYqWktLT/ADlvQJFcgJuTdR/aGsRje1QkSkgSh/Jcd7K47VvdlCybFSlPS45k++XrwXoVWDNUZswfiWlINeyRXmIPvEPe56ZjDmEwyRl7TMaOEiqlP7yyR7xapFWYAgMC4LAhKRqTUC5JpzmwIpqwoPdABXxuKslCikrd1gjOoNUoKrJYMZh0okMGFPH8gYnth7QzEDIgAAnmWCCSGqnMByncP0YRg4TjCZgZRB3OvQqar7KFfEUi2JwCpSlPVCiSzkhn1JqfG8ITuEsc6GI1Go8WuOumu8RSZaHyMgccyTfo++3jYwRKwoUPgdvGE8Niii4bx0H6fAwyqTqhq+782e4ifIAjLKS42Yi/zumGcLiQKGxsf/EwOXMBDjTd3HltDMhKFAhQ09NiDrFNeUIrxFJUmhINLX+H3SEwo5i02hLCmguP3hmTMaiiXFHgWKRlUgpypckl+oq20dX0/K36WZyXkSmzCe6sVU9tOlKxypho6g3Mot0tFlAFiMhu1GNNoCVEAOUuAXtrHUSDI3UeQPTUmp8YhKg4JV7tz1+sXVmJUcgqA2j2cXis5JYgMCwoWgKKmYE0KqjziIhRP5k+n7R0AzXQuhVm5WazB3gyJ5JBCk+6S4903bzEC7RgE5hXM2lWB2i6M2VjlKsouzOFRSIDhbAZli+Wl2NrRdMuiQStTpynbX9IDNpmfIGykWLKtWCBDlipQZWgNrt1hkkYNTuQhnA71y1DU0tBkB69mQQFJo4pfSFiRygqPdXVqtX9YNly0zmpcMC9UmkAFiFLUHlkFgSx/Kp2rrFp6CM7A1KVVUz16WDn4QOStKQlsymSqpNW186x0pAbMJXui7mr/GEIYlashIGeupL31vHIw7Jz9mkKAUEglqOK3aFlyUnM6AXXS48zF1zEZ0ptmC9bat8IAOVh3Sc0ssUvynUKp87wSaGC1BCyohJZ9dBb1gRMtIy5lAZAAaWzQzh5AUtvxCGQkhvdJAJDm+V4QHrvZTDhElUzKAZii7dGB+S4nic8dpmbuAoTQEuSCtvFSQP8TtG6gImSgZGVgCE7Uox2IIY63EeZnSz2uViSmge+al31FCdyRvTk+6p5Ro40Hkp5ag1Ic79B8R4lZhTiOIVMUJMrvquQHCEij7U7o3J2eG58zKEoSHUeVIc6vr1qX8TGXOPZgy5ai5P4ywWLs+RJ92mvuJrciMJPs68L9opYCTMOlSRKH/60skKY1xE0GqXuUBVzrDuBkiYrPMUkAg5EqOVKgkPQVaUkA110pVQJctCUJmTmyhkIlpDBWiZUtN8u+pq+rZfH/absyVZXmroACCwDMBRsqd7A7lmv2v5/oNmzxLiqJaSpZBe4Ou2axCdk6uCdo8fP9oJYWoy5ZK1gZlmj+VSlNtiSHOgGKufMmqK5inL/AOKeid1dT8LRk8U9oEyuWUkLVqSeUbudT4W+EQ4dvSaqNZZ6lHFMxaYAx1DsPW3jAMVJUg5pZcdPn0+XhGNwvjSJwoQlf5XBPkR3vukaUqaUlwabRk+NxeCmk9FxPTMACwkKFiEgC+o8f1eKy5xlqYihrT5pJ+UFVIC6jlV8PMQFSiBkXT4+j/7w0+xFUO9klYzJIzfPoYpLINuUjTY9OnSFUrMognmSddPM6HrDqmXUFlfbZh9YdNCOUl6jzhTELVmAZFEuATV7PDSJl3DHUbHcbiFuJTA1fCjWOvnSNuH3ky0LIcAKKQ4FKuASW3gcxLqW6NgDZwbxGKlAggKIAIpltHTZjKqou500AjuIKKSOYhKqECKKSxJAuQKn4RYTe65UWD7U6xSUaB0u5fWn7wDBzJiwS2RtHjoZl1AdIHRjHQsjHilw5AdLKFaaP9YKtNSAl2BFCfEQBMsBu6xe5L7t1hiVMpYDz2ofhFohl5wPOOVNEnR9HNYMcSdF/la9qO8LrVWmQUIe9v2iyJzucwYoBPL1Z/2hiGgskkAp1ANHGoFor/EkOrMgpDEa9FBhA5eIGYgqIsWADX+NIqqeEkAKJqRalatCEMomuWzFubTQhxXwMUmzaAArLpIdtvGxiETVAOVh2Jdrsa6RytTmUQkpNHetx8YYEmZ/WoNlXXxY2g4ngVKiSlf5Q7HxuOsCSvqWcpLga2HUxQzmKylStGcUAhCCKzKqFsGIY3DKvHr+B+zKghU98y1jlSRZH5mNyWtt1jznCsMqbMyhRZ3WwblIsDu9v2j03DOPmRMZf8lQBG8uuUKN+VR00v8Amjn5pOqRcEvIojHKw0zNKDocBSDTPuoHRV2NmSSaGnqR2eKliZKNSGCmY9UqBsdOj7QrxvgYm/iIqDVQFSQ10+NAelrxkyhMwilLFUj+YNFFtDooCx6AaxxS/MUarGweLQpBUTyzFAuTUSpeppdRpQGrpGrhSUlMtIUsHLYIFVk0IS4usmpO76JS/rcTh5eJQlYLVFbF0vyrGhSSaHumseA9o8cZa1ITRYudEJ2SOo1+w4NLH7/IOOQHHeOkOpRR2jMhIPJKRZvSji9QKAk+ZUDVcwkvUkli2nQDpFigAGYssBWv/cevy+XneK8TM7T8MglKagrqzqL0T/s7u1pXo0S6hOLccKuWXyo/OO8rcIH1LAaxjSJRmEZfIhuUuKOW5SDctV/M0mWpThuYg0YVCaskigYPykN1jU4XgEyyZs1kkBwnUGvMr+qhYXFSemuI6FsCv2a7oWsJUScoQCWN6knwqwh3D8QmSDkngrTou5Hj+YfHxjSkYh051DIDZ73YP1Igq5QWmooRYiv7RPb8joJIxIUApJBBsRb76Q2icCMqw4+/SPOzeGLlErkGmqTUHxGvzpfSHOHcUTM5Tyr1Sf8AxOvheM5caeUF/k1VYfJaqNoBNklPMiqfik7NtDMma3UbbQRclueXUG4jO6wxAULCw9juL9PEfKAYjN3SQLHfY03i65YLqRQ6p6/QxT+JKg2u+o3+VovjfWSZLWBUz3fnI5hcVfbwiuYbv3rhz8Ylrcz1NwLa3gZW7FzqbDwj0TMrOmcx7xppQfARVSakMpmGu8WnSiSQQpswF/jA1pqe8ObxtAMvTr6x0KTMMCTRXpEwDNiVUhgCGB+LH4QZCaigA5gRAZVPy2WKCt4YkqcnRi9R0pDRDCpAOVlDenUMfjWKhTgBzqk8tL/KIMsh2YctwNRBFra6jQpO16NDEShWrpdmLJ2+kTm5iXDAIo1v3iZUy/MTRZs/r4RVM45jzUZGm14BDKXFTVs9Mt9REImkpJGcUSbAG/zpAluxOYvz2HURRw2V1EZARrV4BBpk1lAMoDPrua6RaQFqSAFElXKAAfzfOrRc3opRdQJpQUt4RsezmGYdop1EZgnN41LdAwHVXSJcqVsDRkYVMhBT3iWKtSpwwSPG3g596F5qM96vUgUzPysDoD3QbBIUqkNz5lC9Sd9SaE2/xHnA8LLJITmAKtbMhjXoSl22TXWnOylke9l+JGUOzWodnmyy1V7xclI2l1AGzgeGh7Q4JRAWiyaszsp3Cm1ANW3SBqYxcSAUqamYZJY6PUtuwPqBDnBeOKTLUJp5JZCEzSe9oyvOytsr1LnldrKNVnDMXi3ERw7DKXdy60k1Uo0odx+bW/vBvHYzjJmspQLGozBlAXYx6f2pwCMVOSorYJr2dkqVoX0DPQ+ug8Z7XT1SwJSP5izyW5QKlTmwo7mnlGX+vlacNm0Lh7jD41jFTFlJDS0McpcZ1E8rke67k6sgilDCCSczzC6SX7QUUB/UkUWBQWoLFIEOIxqVulYo7hVgdlbp6eOlocwfDkDmWSsgulJACRrmVfM3WnQx0xn1xIGryhfA4XswZqjWqQ1CkHQA1ExdKHupqammjhsKgJE2YmrMA1noyQ5cnqSb1guCSiY61OUoJYqOoNVq0J5R4BhBJiBNU6qIToU5aa1Jq4FTsYHIREiWpas5YpHdsRrVOwY9656CkOZYxcV7SjNkkozncuEs7coAcj0tC0v2nWlYE6WEgs5GYEPqQrvfCDq2FnojCeO4UmZUcqtCN/8AeG1zkpDqUANyWHxikuaSpQKWax36Nd/B6ekNEsRwvFVIV2c+h91eh8dj19W12ZM4p+o/T9IzD2c9KgRYsXDEagsbAitYTl49WGZM4lUuyVt3fHcfEQSgpBZ6OdJzcyb/AH9tCM5BUTlHOkO2438vpDGHxdiC4NaVBG4hfGkOVDNzAs2mhH184z44Ny6sTwDUpulK8u9oXWpveOiaDXWGEAu4erUKreUUCypuUhibnb9Y9DRkDCwr81FN8IXGjJUHOh0H6wRUwbENXeppFMrAtmNB01hjC5RqFfGOgM2Q5Jc1/qjoVoDQKyAak60HqPjBZJ5Kg09aVECTKp71Mw/SCILqIr7vxEUhBpam0UXJ8ga/CJlklJIzaNTYwJSbB1Uyu1N4MVWSxurWGIIFHN71xZhcWi5SVcvMCQfh1gIQwHL+XXyi6AE5jzXVr0gEE7QuaquBalafpFkKJZ1ixSaajWBy1jvZjXKW84Zw8lS1JCVEkqOmnU6CE3Qqsrh5Jmd0qKl5QkdXYeTx7OXKCUhKQzMlPXqfE5lH+4RTgvAUyucuV2CjZLu5A6JzF70h/CS35v8AJvF2HkkD1jJy76KlFxwwErBucrO1TuSxZI8frFZuHCVhy6l8powSLqvd1NXVoZ4ksSgQo0sas7gFhuSzdGFReMdUs5iFXUMy292XonpmqK17x0jKSvAItPmZiCKAhk/26q87jxRsYaxc1KJfZgU1DUJ28BQQLBzAtSpjMEgN5d3p3q/4g2Lwri5jEJD083OpLxDwrKWTA4jhcuchTAOejCppa+zR5NXHET0MsUUFAZrFNASlQYgHyet49F7Z8SAQmWnLmVUgkgFIuKbu3nHjRKVMIDc2YpS/dWFMcoKBQhiRRmJs0ZLgi/UbLkawRiOGX7JTE6LOYV1CjXyLv0jQThLJlsyRQFxyhkprYLUQVNZoZ4b7PFCSZi2JolCS6R63UfJmgeLlKlcz0e4+o9T5QpN62axS2sAZmIJHZuAxY0sQRdrttaFOOY4cshB5WzL1JF2pUktmO5aDSmKTyO/vWI8z4kt1MO4TBMnmNTBDDK+25HkMXiQlqHokv6lqlvza6QTIpaEpykOsdiDXlIYsToVFJ2f1j0eL4clThgR1rE8E4UlMxUwsMtEpsEBi5+J9SdY6O1IznxOJorwiWSlVWGQb2YtuSB8IHMAmJKVJKQL7UJsdQAAXtUagwWZKzqAKUlLOFailtwp2OlOormcTnEukMAGIfugaKUH5iWOVH9OY0iErMycTxewRXYsVKUN0pcEj+tRAjF4hiFzGQQpQBLB8xKjW4ABItSgtWH+HYFa8xJaWalRotR8feDb20aNeTIly8zMGS7s5L2rG8V+CGzN4Hg50pgohKGPJcvUkj8v12jQmKzAPmADlrXpWDJmAAE5nCXLD7rHYhOb3iLU1YV9YtQzZNiy1BxRQta1BEFlEUVQO+kFXODEZlO2a2loGUDdRcgfWLEVXLZLAGw1pA1oDigrcZtouJbVINSb0tAyQz5TbzrAMplJrk+IjouUtYK8hHQUMfQqutwf2giF01ppq4hOWaOQHYa7H9IYkO5cBr9YaEHQS1yXcHS9RBEv3iDffekLZSSwZrFulRBwnw9dw/wA4YiU3tZxQ+YMGlKYvzVY+tDAEpYBmdhrWhj0PAvZ7tarH4b03V4bJ6xMpJKxxg5OkC4VwNc+iXQgEjOfF2A1j2nDuEokpZIrqTUmNDBYYJADM1gLQzMTSMW3I7IQUBGcKbBj8S3/alUVCxkUWq/0YXppBJozeoHw/94yONLLZQVgOay5glqqbOR5FqitopYOHkdyEeIMJpdWeeQCE1ZA/MUlasgAq9HNBUiFJ0y8sEqKiCsihUsmgDWswGjE2Qt7LUJYMuSkJW7qq4SWcqWpVVrAq6qJDk6JLPDsKmWAo1Z8oLgkmhUdiWAD2A3C3zYBccRKlpBAdNaWfuimzWGwjEmzwkFRNACTs2v6CJ4njO1XeiSTQlns43DUD6dY8v7UcSp2STUsVdEvb0+sYyfaVG0Y0rMjiWK7aapZep7pHME1Ccu9HpSqhs0P8Bw3ZIXOUCCHQhKmAMwhifIFt2z7RnYbCGfNQlNc7LYmxIzZx0SXdO3w9vOw8iVJEtSglCQB3mJatW1NSd3O8XJ1gpIQwaCUZlmqi4owCaAU0ds3npCE+Spcyg5Ugihepv8Az9TGzgWxi1Jk9xNFLAZNfdG5avQeUetkeziEJAbSIUXs6uOMds+czMJUBqCHU4PKm0etxXBgDmSA43F9wRC+IUiYMpSEqFGt6bxpxuOvJrKTWlg8bipTQguaQ7NUMQQ4PiNo1OLpyKI+2jKThnBWo5QA42atx93g5FjBPK11ydiJ4EvKgO/eAJ5iWSEgkuASznRIMAweEzKUVqdAIDMAkrpVOqQGAawAA0EBzElrKFOhI7wBF2NCRqDGvJlMkAElzZqbmDiTeGcM6WgxSk3ylnbw29IouZVV9BQRIJIdj7xoB4Ry5JJYihUPeajUMdVUYHF3UOahAsLRZy5oTWjkbQPK+7ZjqD6xREkB6HVV4AKLO+ax2f4RAIJdlG3q0QiULlNWAZ9z84ssAGtyaV2F4BgFBymliRU9NI5MrSopv1iymAAYMz6m+sVV0Aow/WAYMoJq3/XHQRMoN3RHQDDpYsakPtoYNKNNr6aAwuFUPQaHYwdB0rWl96wIQaWRmP9224iyplKPdNhU0iibuHNRR49BwH2dM4hS3CAXFaqZ/RPXXSBulY4xcnSL8A4EZpC1PkBNLZq/9vzj32DwbCg/QeERhMEEhm6BobE0JG0Ye52zujFRVIu+UWhHHYohNmgGK4ukFs0YHFOOpqHiuy8G0eJ7Z6kIBlq2cO3VCR8xHlOKYXEleSXNxOSqiE5Ahjf8AGUh0gf3Wj0eBx2aUmYOZKkJzgXTqFAauSfMdYzpk6WVZldooPRKnTLcahJHNX+4DRjSG2eTJZEuG8NTKSHLjdzzVzMCalL1Kj3mc0SIQ43xXM6RbXfqOlGDaAgXKmpxbizrNWSKBIvuSrMSHtSujhu/jTsWlCTNmHKkaHT1qSX8akmpMc/JLwjXj47yzsdjBIRmVVR7qRUknQDX76x46ZNW5Mz3zmIbMVbJDfN9LmGOI4pU9WcKKQXAS1AhhRi3MakvS17QpLZD5Qzn8oHkSVV+XSCEeq+TR5GsCtSSVD8NSk5S1Tlcki5ABOWgs0W4fJmYqeiRKGZSiMyyM2RA7yy+wtS6mjNn4uYtQRLGYqICWqSTQANfaPsnsV7HDAyOYAz1sZqhUA6IB/Klz4lzs1/IRjbNrg3B5eGlJlyxQDW5OqiwDkwxNnbxCpwTeM/FYlVVd4dL+msS2dkYEYxcea4mH6ERpzZxYk6/GMDiGK8tPvpGLNUqMTFAzV5SaJuen66Qjj59wksQQ2zspvJKUlTdANYrjMdlUo+vQV9S0Zqsa8wy/fbKGrzqUMyaWZISmuxjeOVk4ud1hGjwmQSgLUliWSAlTgJBuCd9fCNKZN5g16m/l8YqtQQnKCGRlFn1r8YoFcrl9WIGjx0Q0cMtl5kqljonvbmJCqsQGCmGukd2rGpJBUGp0igWa1cVZx1ixEIsO5qT6sIriNQAnQX9Ys2gDUFhq8EmVLVd9ul4QwBNXGUXJ8qAQBayS5I5WTbUwaY4o5cC7dYgG9R3tvhAMjNfmDP8AAaCBgWPnbUxa9QTrS0DUHalGFSesAyqlqc3HkImCn/Ex0AyqFAA2qRpveCJs9z4bFoFLBO9GazkvHqOAezilqC5rhINEXfbNtXSJclHZUYuTwH9mvZwrPaTRy+6GYqG5/p+ce+wmHYBukJSUWjQlpfU/flGHbsztjBQQ2E0dgehikxR/K3m8WTJb3jCuMewr8I10ifJkcYQlQIWB6MR5x889oeHrQ5lLzjZVD6/rHtuJyJlaH5x4Pjs5SSX/AEjnbt6O/j9uwnsz7fmUjsJpMhSXyTKsQTVCr+W7xpI4wFkqM1U1arlypYagDgZUepZ6AGsfMuIz8xJiPZ7hRnTi7iWiqmeuuUNqfk8aZlg87l40n2Z9DXjkjmW2Yd1A0Gnnc13Jqb4+OnKmqBWKDup7yUndtSLuXvYWjQGClWUlOX+1mDOHI+sef4rxfDopLKlK1ylkg+JcekL7XXJmuRSwkOS8LbvNepy/ufSBT5YD5lAfPyf9I81O4wsisxTbO3xDR7b/AE39jTjFfxE9KuwQaBX/ABVA90f0A3Ott2ZVfB67/Tv2XShKcUtPMofhZnLJIbtNgSLUtXUN7cKv8I6YQIWVMibN4RKz1g9fv5xlzlkWLHbQ/oYdxEx3ah+cYnEFq3t0+ZeM2zdGXjuNBWZJJChoQxjBx+MAEaOMSlQ5hXRWojyfE5zOCXAr4woqypNRVmfiuJlCwQxJdgd2o/hBvZbBEqM1Se67akr1NdnJ8TGbh8AqfMpRIurrqBvHscPIyJCRQUSGPmfWOpR8HkTnbsKuUbupqUalLwJEskO6hc23g6S2rOTrELU5HMdDf4RsYAw7gutqm19IkuaMbbtUxYpLf8w71tYrOIDs1xqTAMlcs0GWx3NgICs5UuynPV7wQIozCubWOBoRSwuYBlMrE96p+QiqjR3NHNW10gipYNSd7FoCUgkjctvaAZ3ZjpUAX3iq5TEMA3j6CLga9TpHMWtWmggGU7FPT1joqQBp8I6EB6X2d4IJSQtYdZt/SP1Yx6vCCm0ZEheYxryVM0ec5t5Z6qgoqkaMmWbiHEyBdlP97RnInkWhmVjFaxcGiZWMGaRcHwb5QpiJgNQWMacjFkj/AGgip6TQsY6MMzTaZ5PFY5VQ4ePGe0uIUUkEJMfVsTwqSvvy0k+h+FYw+J/6dYWeGPaI/tWfkXER0ZtHkVUfBcSlNSIS4bxeZJmlSC4eqT3VaVb5x9vP+ieFI/nz/WX/APSMPFf6C5STKxJPRcv6pI+UWotZMpNSwz5hjeKzp5OdZb8ookeWvnCK5Jj3mO/0txktY7NKZr0OVTeZzsw84917If6UyZGWbjMs6YKhF5ST1cfiHxp01iXsXVRR4X2B/wBKF4vLPxLy8O4ITZc0dPyo/qudN4+3ScOmWkIQkJQkAJSkMABQADYQeYuFpi4zlIaRSatoUVNPh6D5xebN+/8AaEJ6z18n+gjJyN4ojETL1+/GMbHYnf8ASGcTiBUAjy/3jzePxrPWvWsRdmiQlxTGaUjLwmCCxmXUEhh5tC/E8WwUTpX78TCfA+MTU0JzJd2Nx4HTwjr46WWcv1ClNVE9JLwyUpISkNSgGjxZMtvArOmwicLiswdLlgKEsXJgigHFrnUx1I8ppp0wQB5Tm3ekTNSSWerD3YME8pdvU3Mcg3oKEkV2FIYFEyNtlFyPKOKL12AYARec5GWlaa+JiEF2bK1TbyEIYNVN3qdDFVJJ3u9RtBey6DQUfxMcoubabbwDAJS7G3pqYotG7UBN9YYVKrRt/SBrdq3pUCAYAoBHkNYgoAAb56CGEk3ru1PBooxfVraQACGHG0dBhL+3ETCsZ67BffwjVRf73jo6PL8HsDcow3LSNo6OjWJlIIE/SHZYqPvQREdG0CZB0nmiJo+/OOjo2M1suDSF8Qax0dD8B5IUKtpErtER0YTHEHMhYmOjoy8myFp6R9+cZmIuRHR0Yy2aIxuIGhjzGNTQ+MTHQ4lPR5XjncH9w/8AKJ4QImOjqRnA3sHRaY2MoYU3iY6N+HTOH6z3lpNj5QP3v8THR0aHKXGnn8oBOPL5fWIjoTEiqjQ/3D5ReQkZRHR0IopKSMppofnABp4n5RMdANFpQt4fWLlAew1jo6AAKkjaJjo6EB//2Q==" /></div>
<span style="font-family: sans-serif; font-size: x-small; line-height: 19.1875px;"><br /></span>
<span style="font-family: inherit; line-height: 19.1875px;">So the take home for today is, when your code runs slow don't forget the cache! Until next time keep it real...</span><br />
<span style="font-family: sans-serif; font-size: x-small; line-height: 19.1875px;"><br /></span>
<span style="font-family: sans-serif; font-size: x-small; line-height: 19.1875px;"><br /></span>
<span style="font-family: sans-serif; font-size: x-small; line-height: 19.1875px;"><br /></span>
<span style="font-family: sans-serif; font-size: x-small; line-height: 19.1875px;"><b>Glossary</b> </span><br />
<br />
<i>Time Complexity</i> - A way of comparing algorithms mathematically. Instead of comparing them by actual time measurements that are affected by the computer the algorithm is run on. Compare them by the expected number of operations. The number of operations is typically dependent on the size of the input n. So we say its complexity is a function of n.<br />
<br />
<i>Cache Hit</i> - When the CPU attempts to access an object that's already in cache.<br />
<br />
<i>Cache Miss</i> - When the CPU attempts to access an object that's not in cache so it must be copied from memory to cache ( a line size at a time ).<br />
<br />
<i>Row Major</i> - A 2D ( or n dimensional ) array in C is actually stored as one large single array. In row major order rows are written out after each other. So for example if the array is defined as x[3][5] and you access element x[2][4] its actual set at 2*5 + 4 because it has to skip the first two rows and then move to the 4th element.Anonymoushttp://www.blogger.com/profile/05316739893737008207noreply@blogger.com65