Looks like one hope/theory knocked on the head

Samsung DDR4 (Photo credit: samsungtomorrow)

Now I have mapped the speed of OPT and LRU using a traditional two level memory hierarchy, my task is to find something better that might make NoC a more viable computing platform.

One thought that occurred to me was that the preference of C and similar languages for page aligned memory in certain situations might make it feasible or reasonable to cache the first 128 bits (16 bytes) in faster access memory.

So I wrote some code to test which 16 byte “segments” of a page were accessed by code.

The list that follows is for read/write accesses (i.e. not instructions). I will get around to plotting a graph, but it looks like that idea – which was always a bit of a straw clutching exercise – is not going to fly.

 

Segment: 0 Count: 3145700

Segment: 1 Count: 4892407

Segment: 2 Count: 3207293

Segment: 3 Count: 3790303

Segment: 4 Count: 5315932

Segment: 5 Count: 8143085

Segment: 6 Count: 6060159

Segment: 7 Count: 3900910

Segment: 8 Count: 10018940

Segment: 9 Count: 3738990

Segment: 10 Count: 3654813

Segment: 11 Count: 3887982

Segment: 12 Count: 4046926

Segment: 13 Count: 7366857

Segment: 14 Count: 5029997

Segment: 15 Count: 5555853

Segment: 16 Count: 5101695

Segment: 17 Count: 4919006

Segment: 18 Count: 5536030

Segment: 19 Count: 3679621

Segment: 20 Count: 3496416

Segment: 21 Count: 4175369

Segment: 22 Count: 4126270

Segment: 23 Count: 3264013

Segment: 24 Count: 4100255

Segment: 25 Count: 4322633

Segment: 26 Count: 9749020

Segment: 27 Count: 19622721

Segment: 28 Count: 11919679

Segment: 29 Count: 3679721

Segment: 30 Count: 8063852

Segment: 31 Count: 11752619

Segment: 32 Count: 23894391

Segment: 33 Count: 14935880

Segment: 34 Count: 17010081

Segment: 35 Count: 12806447

Segment: 36 Count: 11758764

Segment: 37 Count: 13757944

Segment: 38 Count: 5967876

Segment: 39 Count: 8410322

Segment: 40 Count: 9751409

Segment: 41 Count: 10568546

Segment: 42 Count: 8047474

Segment: 43 Count: 9064589

Segment: 44 Count: 9219878

Segment: 45 Count: 7913851

Segment: 46 Count: 4868922

Segment: 47 Count: 5057902

Segment: 48 Count: 6649602

Segment: 49 Count: 8562603

Segment: 50 Count: 3609239

Segment: 51 Count: 3965129

Segment: 52 Count: 4869654

Segment: 53 Count: 5149858

Segment: 54 Count: 2055722

Segment: 55 Count: 32499129

Segment: 56 Count: 2733892

Segment: 57 Count: 8887833

Segment: 58 Count: 2329809

Segment: 59 Count: 2946391

Segment: 60 Count: 2946919

Segment: 61 Count: 8444848

Segment: 62 Count: 2890405

Segment: 63 Count: 3106806

Segment: 64 Count: 3349164

Segment: 65 Count: 4892046

Segment: 66 Count: 4453014

Segment: 67 Count: 4943979

Segment: 68 Count: 4595481

Segment: 69 Count: 6552969

Segment: 70 Count: 15521259

Segment: 71 Count: 4037689

Segment: 72 Count: 3737825

Segment: 73 Count: 5438653

Segment: 74 Count: 5012634

Segment: 75 Count: 4229649

Segment: 76 Count: 11143742

Segment: 77 Count: 6171722

Segment: 78 Count: 11938365

Segment: 79 Count: 11041493

Segment: 80 Count: 6030829

Segment: 81 Count: 9557385

Segment: 82 Count: 23490594

Segment: 83 Count: 9314300

Segment: 84 Count: 11119997

Segment: 85 Count: 8870504

Segment: 86 Count: 9059886

Segment: 87 Count: 4581160

Segment: 88 Count: 13002081

Segment: 89 Count: 6050274

Segment: 90 Count: 4850064

Segment: 91 Count: 4495531

Segment: 92 Count: 6551494

Segment: 93 Count: 6294404

Segment: 94 Count: 5852555

Segment: 95 Count: 9759357

Segment: 96 Count: 5688209

Segment: 97 Count: 9991460

Segment: 98 Count: 5155181

Segment: 99 Count: 3923768

Segment: 100 Count: 3319723

Segment: 101 Count: 8659639

Segment: 102 Count: 4416737

Segment: 103 Count: 2534491

Segment: 104 Count: 2470280

Segment: 105 Count: 2709695

Segment: 106 Count: 2535015

Segment: 107 Count: 3050061

Segment: 108 Count: 2772341

Segment: 109 Count: 3621580

Segment: 110 Count: 3332878

Segment: 111 Count: 4358518

Segment: 112 Count: 4282092

Segment: 113 Count: 3523498

Segment: 114 Count: 3111625

Segment: 115 Count: 3474108

Segment: 116 Count: 2809375

Segment: 117 Count: 3592879

Segment: 118 Count: 2768848

Segment: 119 Count: 10525789

Segment: 120 Count: 4122297

Segment: 121 Count: 3660249

Segment: 122 Count: 3432971

Segment: 123 Count: 3671499

Segment: 124 Count: 3066933

Segment: 125 Count: 3271576

Segment: 126 Count: 7069611

Segment: 127 Count: 3774229

Segment: 128 Count: 3258290

Segment: 129 Count: 2416892

Segment: 130 Count: 3413264

Segment: 131 Count: 2789339

Segment: 132 Count: 7841394

Segment: 133 Count: 2992968

Segment: 134 Count: 3624867

Segment: 135 Count: 3304507

Segment: 136 Count: 3573405

Segment: 137 Count: 4226925

Segment: 138 Count: 4803447

Segment: 139 Count: 5630354

Segment: 140 Count: 6420305

Segment: 141 Count: 4721786

Segment: 142 Count: 4860223

Segment: 143 Count: 4183175

Segment: 144 Count: 3790705

Segment: 145 Count: 7974241

Segment: 146 Count: 4146253

Segment: 147 Count: 3063269

Segment: 148 Count: 3485084

Segment: 149 Count: 2923729

Segment: 150 Count: 2947715

Segment: 151 Count: 3818073

Segment: 152 Count: 2769076

Segment: 153 Count: 2645308

Segment: 154 Count: 4452525

Segment: 155 Count: 4793146

Segment: 156 Count: 2281903

Segment: 157 Count: 3256076

Segment: 158 Count: 2414992

Segment: 159 Count: 2951958

Segment: 160 Count: 1747487

Segment: 161 Count: 2385269

Segment: 162 Count: 4128250

Segment: 163 Count: 5101661

Segment: 164 Count: 3579155

Segment: 165 Count: 3746030

Segment: 166 Count: 3117725

Segment: 167 Count: 3516756

Segment: 168 Count: 6842484

Segment: 169 Count: 2145906

Segment: 170 Count: 2281955

Segment: 171 Count: 3043248

Segment: 172 Count: 2946803

Segment: 173 Count: 2638829

Segment: 174 Count: 3543883

Segment: 175 Count: 3509146

Segment: 176 Count: 7295889

Segment: 177 Count: 3061840

Segment: 178 Count: 4201176

Segment: 179 Count: 22324025

Segment: 180 Count: 7157776

Segment: 181 Count: 14223711

Segment: 182 Count: 5079461

Segment: 183 Count: 6497476

Segment: 184 Count: 3395786

Segment: 185 Count: 3594557

Segment: 186 Count: 4511617

Segment: 187 Count: 3377908

Segment: 188 Count: 4015556

Segment: 189 Count: 3884031

Segment: 190 Count: 4418048

Segment: 191 Count: 4425675

Segment: 192 Count: 4151888

Segment: 193 Count: 4073928

Segment: 194 Count: 7515643

Segment: 195 Count: 4260252

Segment: 196 Count: 15629731

Segment: 197 Count: 8020217

Segment: 198 Count: 8051874

Segment: 199 Count: 8100937

Segment: 200 Count: 4875180

Segment: 201 Count: 6493053

Segment: 202 Count: 5447678

Segment: 203 Count: 5587693

Segment: 204 Count: 4748458

Segment: 205 Count: 5004972

Segment: 206 Count: 6418567

Segment: 207 Count: 10145254

Segment: 208 Count: 5678528

Segment: 209 Count: 5601157

Segment: 210 Count: 5702977

Segment: 211 Count: 5590463

Segment: 212 Count: 6693545

Segment: 213 Count: 4030951

Segment: 214 Count: 5199543

Segment: 215 Count: 7942092

Segment: 216 Count: 6376629

Segment: 217 Count: 7480443

Segment: 218 Count: 5150624

Segment: 219 Count: 4318579

Segment: 220 Count: 4535156

Segment: 221 Count: 3908294

Segment: 222 Count: 4547756

Segment: 223 Count: 4509968

Segment: 224 Count: 2944729

Segment: 225 Count: 3301802

Segment: 226 Count: 3638158

Segment: 227 Count: 4838325

Segment: 228 Count: 9253359

Segment: 229 Count: 2775284

Segment: 230 Count: 3601569

Segment: 231 Count: 3482137

Segment: 232 Count: 3594477

Segment: 233 Count: 2952485

Segment: 234 Count: 3315834

Segment: 235 Count: 2438082

Segment: 236 Count: 4846832

Segment: 237 Count: 2711387

Segment: 238 Count: 5907452

Segment: 239 Count: 3551899

Segment: 240 Count: 3621086

Segment: 241 Count: 3032466

Segment: 242 Count: 3572000

Segment: 243 Count: 3020379

Segment: 244 Count: 3275738

Segment: 245 Count: 3398733

Segment: 246 Count: 4023338

Segment: 247 Count: 3839542

Segment: 248 Count: 6434160

Segment: 249 Count: 3999611

Segment: 250 Count: 4388716

Segment: 251 Count: 8178958

Segment: 252 Count: 3622946

Segment: 253 Count: 3564538

Segment: 254 Count: 3182242

Segment: 255 Count: 3133097

Using XSLT to manipulate an SVG file

I am generating a lot of the graphics for my project using Scalable Vector Graphics (SVG) – an XML format.

The advantages of SVG are obvious – it is human readable, it preserves some of the data in the output (eg in the relative placing of the dots on a graph), Groovy has good support for it and, in theory at least XML Stylesheet Transformations (XSLT) means that it can be manipulated outside of a formal programming environment using another bit of XML (an XSL stylesheet) and freely available XSLT tools – eg xsltproc on Linux.

But XSLT is one of those Cinderellas of the computing world – widely relied on but not generally understood or widely discussed. As a result I have struggled over the last 24 hours to work out how to do what ought to be a simple thing: removing a set of dots of one colour from an SVG. I still have not got to the bottom of all the issues – specifically xltproc seems to have an issue with XML namespace declarations and/or DTD declarations – but I have fixed it for all practical purposes, so thought I should document it for future users…

Before I describe the problem more fully as well as the solution, I have to recommend this book – XSLT: Mastering XML Transformations. For Beginners and Advanced Users – which gave me the pointers to a solution I just could not find online.

So here is the graph (in PNG format because WordPress does not support SVG) I want to manipulate.

This is memory map – via Valgrind – of Firefox (7) opening and closing (I created a page that, once Firefox was configured, would close the browser.)

The different types of memory accesses – for instructions (red), loads (blue), stores (yellow) and modifies (green) are all on superimposed and which colour you see depends on the order they are written if they access the same page.

So the answer, with an SVG, is obvious, just look at the colour you want to see.

Ought to be easy, right? Well, I suppose when you know how to do it, it is easy. But it’s not completely simple!

Each dot on the graph is drawn with an XML element like this:

<circle cx='102' cy='699' r='1' fill='none' stroke='red' stroke-width='1' />

The trick is to create a template for all the elements but inside that template only copy out the elements that match the correct stroke attribute. (Attributes are not children of node elements either, so you have to copy them out explicitly.)

Here’s a stylesheet that does it:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" indent="yes"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="colour">yellow</xsl:param>
<xsl:template match="/">
	<xsl:apply-templates select="svg"/>
</xsl:template>
<xsl:template match="svg">
	<xsl:copy>
		<xsl:for-each select="@*">
			<xsl:copy/>
		</xsl:for-each>
		<xsl:text>
</xsl:text>
		<xsl:apply-templates select="rect"/>
		<xsl:apply-templates select="line"/>
		<xsl:apply-templates select="text"/>
		<xsl:apply-templates select="circle"/>
	</xsl:copy>
</xsl:template>
<xsl:template match="line">
	<xsl:copy>
		<xsl:for-each select="@*">
			<xsl:copy/>
		</xsl:for-each>
	</xsl:copy>
<xsl:text>
</xsl:text>
</xsl:template>
<xsl:template match="rect">
	<xsl:copy>
		<xsl:for-each select="@*">
			<xsl:copy/>
		</xsl:for-each>
	</xsl:copy>
<xsl:text>
</xsl:text>
</xsl:template>
<xsl:template match="text">
	<xsl:copy>
		<xsl:for-each select="@*|node()">
			<xsl:copy/>
		</xsl:for-each>
	</xsl:copy>
<xsl:text>
</xsl:text>
</xsl:template>
<xsl:template match="circle">
	<xsl:if test="@stroke=$colour">
		<xsl:copy>
			<xsl:for-each select="@*">
				<xsl:copy/>
			</xsl:for-each>
		</xsl:copy>
		<xsl:text>
</xsl:text>
	</xsl:if>
</xsl:template>
</xsl:stylesheet>

(This code be shortened to just copy-of the line, rect and text elements.)

And here’s an example:

xsltproc  -o inst.svg --stringparam colour "red" pickcolour.xsl master.svg

What that working set comparison graph should have looked like

The graphs look similar but the differences are important – this one (the correct one), appears to confirm that Peter Denning‘s findings about the working set model versus LRU still hold good, at least in broad terms – though this still suggests LRU has better performance characteristics than might be expected.

But it’s late now and I am going to bed – perhaps more later.

Related articles

• The graph is wrong (cartesianproduct.wordpress.com)

Lifecycle of a Linux page … 2

Took another day’s worth of work to get this right … last night’s effort had a few mistakes in it as well as being not such a great piece of Metapost. So here’s the correct version:

As before, the Metapost of this image is available at http://github.com/mcmenaminadrian

Lifecycle of a Linux page

This has taken about two days of my free time and it’s not done yet…

The work goes on…

Now available to all

I think I have more or less got this right now:

Paging explained/simplified

This is also now available on git: https://github.com/mcmenaminadrian/Paging

This was also helpful in explaining how the curves work.

And of course this – The LATEX Graphics Companion – was also essential.

Copyright (c) Adrian McMenamin, 2011, reuse licensed under the CC0 Licence.

Related Articles

• Getting Started with Git, EGit, Eclipse, and GitHub: Version Control for R Projects (r-bloggers.com)

Close(r) but no cigar (yet)

Paging

Still having a few issues with the METAPOST syntax

Struggling to make up for the art failings

Have spent the whole night trying to get LaTeX and METAPOST to draw my simple paging system diagram. Have got this far:

My eldest daughter has a piece of art going on display at a gallery tomorrow. All I can say is that she doesn’t get her great skill at this from me!

I failed art at school

Art was the only subject in which I failed a school exam – getting a low 30-something in 1980’s end of year tests. Not that I cared much. But as the years have gone by I have on more than one occasion wished I was rather better at it. Even now, trying to write a scientific paper – and for me, at least back then, art was always the opposite pole to science – my art skills are rather letting me down.

Virtual memory and paging

This graphic shows you why – now I have reduced it in size it looks passable (as a hugely simplified explanation of paging and virtual memory, but the arrows are still very ragged. Still, this is better than I would have managed even a year ago.