Traffic generation options


English: Read Only Memory
English: Read Only Memory (Photo credit: Wikipedia)

This is a blog post where I am going to write about things as a way of clarifying, in my own mind, what the best way of tackling a problem is.

So far, in research for my PhD, I have concentrated on establishing some base points for potential performance of Network-on-Chip systems running multithreaded code.

Nearly nine months ago I hacked at Valgrind‘s Lackey tool to ensure it produced XML output recording every memory reference made by a piece of code running under it. This was really basic stuff – Lackey recognises four primatives – code for code-in-execution, and load, store and modify (a combined load and store) for read-write memory. So typically you get blocks of code followed by some read-write records and then some more code. I don’t know what the operands are, just the primative type, the address and the size of the piece of memory being used (whether for code or read-write operations).

I then used that to record the output of one of the Parsec parallel benchmarks – a 16 thread (actually it executes 18 threads) piece of video transcoding. In the real world this ran in seconds, under Lackey it took a few days and output about 200GB of XML.

That XML can then be broken down into thread-specific strands of execution – 18 of these in all, of various sizes, but all of the order of several GB at least.

These are then plugged in to some sort of simulator. The basic hardware model being simulated has remained the same throughout (mostly, I did fiddle with it a bit a while back but decided that wasn’t worth it). So we have 16 cores sharing a flat 512kB memory space (this is very loosely based on the Parallella system, but it is not meant to be any sort of simulation of it). There is no caching and no sense that any part of the memory is further from one core than another.

What does alter is the page replacement algorithm used. I first tried FIFO and the code ran for many weeks and completed in about 60 billion simulated ticks – if a memory reference is to a page in the 512kB then it is deemed to take 1 tick to complete, if the reference is to a page (a 4k page size has been used thus far), it takes 100 ticks per 16 byte line to load (25600 ticks for a whole 4k page) – and plainly we have to decide what page gets evicted if our 512k store is already full.

Messing about with various LRU models showed that a two queue LRU did give a little better performance than a simple single LRU queue, and that completed in around 50 billion ticks (and two weeks or so of running).

I then built – more or less starting from scratch – a version of the simulator that modelled Belady’s OPT. That required some very large binary trees to be used – along with 250GB of RAM – and completed the code in about 22 billion ticks (and about three weeks in wall clock time).

All these models showed one piece of common behaviour – thrashing, as demonstrated by the fact that adding additional cores to the execution did not increase the amount of code being executed: instead each individual core had to handle more page faults as the cores competed for the small pool of memory.

I now have two pieces of code running which aim to measure the (in)efficiency of these “traditional” paging approaches – come back in a few weeks to see what they show.

So, while they run I need to get on to the next stage, which is testing some alternative approaches. But I have  a problem – I cannot wait three weeks for each experiment to run. There simply is not any time for that.

The alternatives boil down to chopping up sections of my current XML from the benchmark, or writing a traffic generator.

The traffic generator idea has a lot to be said for it – my supervisor certainly is in favour – but it is not without weaknesses: the degree of locality between the different threads executing is really quite important – a lot of locality and the fault count falls and code gets executed fast – poor locality and the fault count rockets.

But how do I model that: I am not sure there is any literature out there that discusses this problem in much detail – multithreading is hard and for that reason rational people avoid it!

But using the chopped up XML is not without issues either – it’s inflexible, it elevates one instance of executing code to be a model for all executing code and so is just as vulnerable to the question of locality.

Leslie Huckfield case exposes Wikipedia’s weaknesses


Wikipedia
Wikipedia (Photo credit: Octavio Rojas)

Les Huckfield is hardly likely to be famous outside his own household, but 35 years after he was a junior minister in Jim Callaghan’s Labour government he is back in the news again today – because, now living in Scotland, he has backed Scottish independence.

The pro-independence “Yes” campaign are, not surprisingly, doing all they can to milk this endorsement: they desperately need some “Labour” support if they are to have the remotest chance of winning.

Ordinary folk might be inclined to say “Leslie Huckfield [as he now calls himself], who’s he then?” and go to Wikipedia and look him up (click the link to see).

What they get there is a short article that is pretty light on detail and does not do much to impart the flavour of his politics – having once been a strong critic of far left entryism into Labour, Huckfield turned into one of the strongest defenders of the Militant Tendency’s/Revolutionary Socialist League’s presence in the Labour Party and, reports John Rentoul, once proposed banning all car imports into the UK.

But more importantly, it completely leaves out the one thing from his time as an elected politician that Huckfield should be famous for: successfully stopping his attempted prosecution for allegedly dishonestly obtaining expenses of more than £2,500 from the European Parliament by deception.

The story of that – and why it proved important in more recent British political history – is covered in this article in the Law Society Gazette.

There is no sign, that I can see, that someone has deleted this information from the Wikipedia article and certainly no suggestion that Huckfield himself has stopped this from getting out. (Nor, I should add, is there any suggestion that Huckfield did anything improper in seeking to stop his prosecution.)

But this is a warning against relying on Wikipedia as a complete source. And it is also a reminder of why paying someone to do a job thoroughly – such as compiling an encyclopaedia – may still have advantages over relying on crowd sourcing.

I love Wikipedia, it is surely one of the greatest things to come out of the Internet – but it is not something I would rely on when it really mattered.

Proving Heliocentricity


Is it stupid to think that the Sun revolves around the Earth?

Oblique view of the phases of Venus
Oblique view of the phases of Venus (Photo credit: Wikipedia)

Well, of course anyone even slightly exposed to scientific thinking who believes that today is certifiably a fruitcake or, as Professor Brian Cox puts it “a nobber”.

But proving heliocentricity – unlike, say, the spherical nature of the Earth, is not actually all that simple at all.

The crudest evidence suggests to us that the Sun goes round the Earth once every 24 hours and it is quite easy to disprove that, but the alternative – that the Sun goes round the Earth once every year is a lot more difficult.

Painstaking collection of data about planetary movements will show they (other than Mercury and Venus) display so-called “retrograde movement” at around the time they are in opposition to the Sun (on the opposite side of the sky) – something that is much simpler to explain through heliocentricity than geocentricity – but collecting that data is not something you and I are likely to do in a hurry.

Venus and Mercury’s different behaviour does suggest they orbit the Sun and as the geocentric model came under attack in the 16th and 17th centuries that was one of the earliest concessions of geocentricity’s defenders: but even that is not definitive (remember we have no theory of gravity here and so we may posit any orbital period we like for these planets).

Even the discovery of the phases of Venus towards the end of the opening decade of the 17th Century did not completely kill the idea of geocentricity off – though it was the heaviest blow yet.

In fact the idea of geocentricity lingered on in scientific thinking for some decades. Partly that was the influence of the Catholic Church but that is not the full explanation – heliocentricity turns out to be quite hard to prove.

Copernicus was wrong (maybe)


The Hubble Deep Field South looks very similar...
The Hubble Deep Field South looks very similar to the original HDF, demonstrating the cosmological principle. (Photo credit: Wikipedia)

No, I haven’t taken leave of my senses and decided the Sun moves around the Earth (but here is a pop quiz for all of you laughing at that idea – can you think of a simple experiment that would prove to a 10-year-old that the Earth moves around the Sun?).

In fact the issue here – the so-called Copernican Principle, or in its grander form the Cosmological Principle – was almost certainly not Copernicus’s view at all. But his paper – De Revolutionibus – opened the door to it, and indeed to the positivist idea of science in general.

The Copernican Principle states that there is nothing special about the position of Earth, the grander Cosmological Principle states that, at a sufficiently large scale, the universe looks the same in all directions – including (and this is important for what is coming) from where we are. In other words not just Earth is nothing special, but nowhere is anywhere special.

But what is that is all wrong? A fascinating article in this week’s New Scientist looks at just this.

That there are limits to the Cosmological Principle is obvious – the world is not smooth, even at some very large scales (look at the night sky – most of it is dark).

The standard scientific response to this is to state that at a sufficiently large scale – around 400 million light years – the matter density between galaxies and the inter galactic void evens out. But that assumption is based on our observations of our locality: yet what if, actually, we were in an atypical part of the universe? The atypicality could even be meta-typical (in other words we could have a super-Cosmological Principle but accepted that the universe was lumpy.)

This matters because our cosmological models are based on the assumption that the Cosmological Principle is correct and that therefore we are typical observers of the universe: hence the phenomena we see are ones that would be seen by any observer and are therefore artefacts of the universe’s physical nature and not our observational position.

So, for instance, we have data that appear to show that the expansion of the Universe is speeding up. We do not know why this is, so we call it “Dark Energy“. But what if the apparent speed up was because, actually, the universe was not isotropic (did not look the same in all directions) and the additional mass in one direction was impacting on the perceived rate of expansion of the universe?

The beauty of this question is that asking it does not mean challenging Einstein’s General Relativity – it’s not an exercise in metaphysical speculation but an argument firmly within the positivist realm bequeathed to us by Copernicus in the first place.

And finally…It is actually quite tough to devise a simple experiment to show that the Earth revolves round the Sun – but the orbits of Venus and Mercury are probably the best examples: these planets are never in opposition to the Sun. Though binoculars to observe the planets’ phases are probably needed to fully escape any Ptolemaic theories’ grasp.

Finally, finally… this book – Can You Speak Venusian? A Trip Through the Mysteries of the Cosmos – was very funny when I read it about 35 years ago, whether it has stood the test of time I am not sure.

Racey code can damage your (mental) health


Running the Hackney half marathonI’ve had a tough week. Ran a half marathon (quite badly, but I finished – see the picture) on Sunday, hobbled around York University (blister on my foot) on Monday before returning to London and coping with the added stress of a new job.

All the while the failure of my latest piece of code to work was annoying me too – eating away at me and making me wonder if the whole PhD thing was a bit of Quixotic nonsense or even Panzan stupidity.

Anyone who has chased down a bug for days will know the feeling – the root cause must be out there somewhere, even if you have been through your code dozens of times and can see nothing wrong.

Sitting on a long commute to my place of (temporary) work this morning I realised that my problem could only be down to one thing – a race condition.

I am emulating an LRU/2 type page replacement policy – with two page queues – a “high” and a “low”: pages are initially assigned to low, but can be pushed into high on a second reference. Pages only leave via low (they can be pushed out of high into low if we run out of space in high and so on).

With one thread running there was no problem, but when a second thread came on board the application fell over – and I realised it was because the manipulation of the LRU queues was not atomic.

And, a few dozen code changes later (done on the reverse journey back to London) – and some accounting for C++ template strangeness (it seems that an iterator across a map, means the map is not const – that took me a while to work out) and the problem has gone away and suddenly academic endeavour feels worth it again.

A vision in yellow


Some locations in the London Borough of Hackney.
Some locations in the London Borough of Hackney. (Photo credit: Wikipedia)

Yesterday I ran in the Hackney Half Marathon – my first ever race at that distance. It was a very hot day and I ran a poor race – I had aimed to keep a 5’30” pace per kilometre but in fact ran the first 7km faster than that and ran the first 10km three seconds faster than the 10km I ran last month: not very clever.

I ended up paying the price – going into meltdown at about 11 miles, though I did finish and that’s something to be proud of.

But it is fair to say I was in something of a state by the time I crossed the line, in 2:15:45 (my hope had been for something around 1:55).

Desperate for some sort of energy restoring drink (I missed the energy drink handout on the way round, possibly because by that point – at 8 miles – I was already approaching zombie runner state) I flopped to the ground and drank the “energy” drink I’d been given (actually I think it had little calorific value and the energy it claimed verged on new age mysticism).

Only feeling slightly better I decided to head off to the bag collection point, knowing I had two genuinely sugary Lucozade bottles in my bag.

As I stood up I seemed to get cramp in every muscle in both legs and then – strangely – my vision was washed a sort of sepia yellow.

I didn’t feel faint – particularly (though it’s fair to say I wasn’t fully compos mentis either) – but I did think, “oh here we go”. But the moment passed quite quickly – especially as I knew I had to complete standing up to end the pain in the legs – and I staggered off.

Since then I have read that this is quite likely to be caused by low blood pressure – or, less likelier, by hypoglycaemia. Low blood pressure might seem an odd cause in that I’d just undertaken some extremely strenuous exercise – but I dare say blood pressure in my brain was quite low, with blood diverted to my limbs, and suddenly lowered further by the effort of standing.

It was a stark reminder, though, of the way that our vision of the world is completely internally created. “Colours” are purely perceptional, not real.

The intelligent computer has arrived


The Turing Test, version 2, as described by Al...
The Turing Test, version 2, as described by Alan Turing in “Computing Machinery and Intelligence” (Photo credit: Wikipedia)

At least, that is the claim being made by the University of Reading and it seems to have some credibility – as a computer entered into their annual “Turing Test” appears to have passed – convincing a third of the judges that it was a human and not a machine.

This definition of intelligence relies on Turing’s own – in his famous 1950 paper “Computing Machinery and Intelligence”  (well worth reading, and no particular knowledge of computing is required) – a definition I like to think of as being summarised in the idea that “if something looks intelligent it is intelligent”: hence if you can make a computer fool you into thinking it is as intelligent as a 13-year-old boy (as in the Reading University case), then it is as intelligent as a 13 year old boy.

Of course, that is not to say it has self-awareness in the same way as a 13-year-old. But given that we are struggling to come up with an agreed scientific consensus on what such self-awareness consists of, that question is, to at least a degree, moot.

Enhanced by Zemanta
Follow

Get every new post delivered to your Inbox.

Join 929 other followers

%d bloggers like this: