Delays in a binary memory tree queue

This is a bit niche, but I spent a fair bit of this weekend working out what the algorithm to calculate how long a memory request packet would take to traverse a binary tree (from a leaf to the root) was. And now I have written a Groovy script (testable in your browser at – click on ‘edit’ and then ‘run’) to calculate the results.

(I am sure that this has been done before – many times – but I couldn’t find the algorithm on a quick search and then the desire to solve this myself took over).

The problem is this: memory request packets enter the tree at a leaf, they then have to cross a series of multiplexors until they reach the root (which is where the tree interfaces with the memory supply). Each multiplexor (mux) has two inputs and one output, so taken together the muxes form a binary tree.

As request packets could arrive at the leaves of a mux at the same time, there has to be a decision procedure about which packet progresses and which is delayed. The simple choice is to favour packets on either the left or the right leaf (in my case I went with the right). The question is then what is the average and maximum delay for a request packet.

So, if you muck about with the script you’ll see that the absolute maximum delay on a 256 leaf tree (eg., on a Bluetree memory tree connected to a 256 tile NoC) is 495 cycles, while the average maximum delay (ie for a leaf in the middle of the tree) is 248 cycles.

In contrast if the load is just 1% then these figures fall to about 3 and 1.5.

There is a flaw here though – because this all assumes that no new packets enter the system while the original request packet is traversing it – but in a dynamic system, even with a load as low as 1%, this is highly unlikely – packets that enter the tree “to the right” of the original request could potentially add to the delay if they chain with packets already present.

Is Groovy dying?

English: Logo of the Groovy project
English: Logo of the Groovy project (Photo credit: Wikipedia)

A few years ago, on my Computer Science MSc, there was something of a mini-revolt as some of the students – already working as developers – complained that the object-orientated design course was being taught in Groovy – a JVM-based language that, in effect, is a dynamic extension of static Java. They said there were no jobs in Groovy so why were we being taught that?

I wasn’t one of them. I wasn’t (and I am not) working as a developer and so Groovy, which crossed the boundaries between Java’s imperative and Scala‘s functional approaches was interesting and powerfully expressive. But, yes, it was a bit of a niche.

I have come back to Groovy now because, for my PhD, I want to write a more powerful and dynamic NoC simulation than has proved possible in C++. Groovy has the tools – especially closures – that allow the writing of good DSLs and so was a natural choice.

But the Groovy landscape seems barren. As I write I haven’t been able to make any progress on my code because it seems a Java update broke Groovy support and, because the infrastructure for Groovy support through appears to have collapsed.

I have asked a question on Stack Overflow: but traffic is light.

Meta programming: giving Integers a “fibonacci” property in Groovy

A tiling with squares whose sides are successi...
Image via Wikipedia

So, you just decide that each Integer should have an automatic property of knowing it’s Fibonacci number, well now your wish is granted:
Integer.metaClass.getFibonacci {
     fib = delegate
     def fibno = 1
     while (fib) {
         fibno += fibno
     return fibno

     Integer x = 25
     println x.fibonacci

I admit this is probably not the most useful additional property one could add to an integer and, of course, it is a function of an integer and not a property, but that was not my point…

Redirecting stdOut in Groovy

Groovy (programming language)
Image via Wikipedia

I am adding this because – while it is out there on the web – it took me some time to find it and I suppose this helps make it more visible in search engines.

I was writing a Groovy unit test for a void function that normally would print to the screen. The only simple way to test would be to redirect stdOut to a string and then test the string.

This is the (or one) way to do it:

public void testPrint() {
//based on solution on
//redirect stdOut and check string is formatted
def bufStr = new ByteArrayOutputStream()
def oldStdOut = System.out;
def newStdOut = new PrintStream(bufStr)
System.out = newStdOut
System.out = oldStdOut
String prtTestStr = bufStr.toString()

Found my copy of “Basic Computer Games”

a tic tac toe game
Image via Wikipedia

This book – Basic Computer Games – is now, justly, regarded as classic and my brother (don’t tell him I have got it) and I spent many evenings and weekends typing in the code from it into our ZX80 and later a Spectrum.

Image via Wikipedia

Pristine copies are said to sell for many hundreds of pounds, though so many were sold at the time that second-hand copies are very cheap.

Right now I have a coursework exercise of writing a game – what I used to call exie-ohsies, but in England is called “noughts and crosses” and in the US “tic-tac-toe” – in the Groovy programming language.

There is a tic-tac-toe program in the book and I wonder if it would be practical to reimplement that in Groovy (suitably acknowledged of course)?

Update: having looked more closely at the assignment I don’t think the BASIC code will fit too well. A pity, because it might have been fun.