Procrastination time: what does this mean?

I am supposed to be writing some more stuff for my PhD thesis, but this feels like a more legitimate way to procrastinate than others…

I have plotted the performance of a model of a multi-core processor system and, because it was something to do, applied a Fourier Transform to the data (the black plots in first chart):

2k LRU performance

So, my question is, what does the second chart mean? If it means anything of course.

I get that the real component is plotted on the x-axis and the imaginary component on the y-axis, but is there any information conveyed in the chart?

Summing an infinite series

I dare say what I am about to write is no great revelation and indeed I was probably taught this for ‘A’ level maths, but forgot it…

Anyway, I was reading about the Fast Fourier Transform (FFT), which, discovered in the 1960s, radically improved the speed of signal analysis. Older algorithms had been able to analyse N signal samples in O(N^2) time, while the FFT manages it in O(Nlog_2N) time.

It does this by relying on the fact that one can combine two N samples to get a 2N sample in N operations, ie.,

N \rightarrow 2N in N operations
2N \rightarrow 4N in 2N operations
4N \rightarrow 8N in 4N operations

Hence we can get N samples in log_2N doublings. But how many operations does that take?

FFT of Mona Lisa
FFT of Mona Lisa. Public domain image

For the above example (N = 8 ) we can see it is \frac{N}{2} + \frac{N}{4} + \frac{N}{8} and for the more general case we can see this is N(2^{-1} + 2^{-2} + ... )N times an infinite series.

For the overall complexity of the algorithm to be O(Nlog_2N) this series should add to 1. Does it?

Yes, it does, and here’s a proof…

We can rewrite our series as…

X = r + r^2 + r^3 + r^4 + ...


Y = \frac{X}{r} = 1 + r + r^2 + r^3 + ...  = 1 + X

Hence \frac{X}{r} = 1 + X

And \frac{X}{r} - X = 1 .

As we know r = \frac{1}{2} we get 2X - X = 1 so X = 1

Have we reached “peak silicon” and what can we do about it?

Moore’s Law states that the number of transistors that can be squeezed into a given slice of silicon doubles every two years (or 18 months) – something I wrote about recently and where I declared “More transistors means greater speed, more and cheaper memory and so on … ”

Except, maybe not. As the graph below, shamelessly grabbed from Herb Stutter’s “The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software“, shows, while Moore’s Law (the green graph) holds true, the other associated improvements that we have come to expect to parallel it, such as a similar increase in efficiency per watt (royal blue graph) and clock speed (navy blue) have not. In short, we can build cheaper chips but they are not necessarily much faster.

Herb Sutter's graph of CPU performanceAnd, as this article recounts, we are now talking about “dark silcon” – bits of chips that have to remain unpowered while other parts are in use so as to ensure the whole chip does not fry or fail due to too high power consumption.

So, if we have reached the point of “peak silicon” what can we do about it?

The chip manufacturers have responded by packing more and more cores into their devices and that works up to a point – we do not even need to have very parallel coding outside the operating system to take some advantage of that on even a typical multitasking desktop machine. But none of us are doubling the number of video renderers, MP3 decoders, database queries and spreadsheet calculations we run in parallel every 18 months, so the “Moore paradigm” of computing power doubling in that time will be lost.

A more fundamental alternative is to rewrite our software so that it becomes inherently designed to take advantage of multicore machines. Writing effective parallel software is not easy, but it can be done for lots of tasks. But even then there are limits – “Amdahl’s law” reminds us that parallelisation will only speed the parts of a program that can be run in parallel: if say we had a piece of code that must be run in serial and takes 5 seconds, and some code that currently takes 55 seconds but could be made perfectly parallel, then if we had 2 processors it takes 5 seconds (serial time), plus 27.5 seconds for the parallel code, doubling the processors but not quite halving the time, with a 46% saving. Doubling the number of processors again (to 4) cuts total computing time to 18.75 seconds but the proportional saving has dropped to 42%. In other words, the “Moore paradigm” also disappears.

The third thing we can do is look for better algorithms: the recent announcement of a vastly improved fast fourier transform (FFT) algorithm shows what can be done here – algorithmic improvement can vastly outstrip hardware speedup. But currently for many problems (those in NP space) there is no prior known algorithm available and computing power can be simply dedicated to going through all the possible algorithms looking for the one that works (we do not know what algorithms solves an NP problem but once a solution is found we can verify it ‘easily’). Assuming, as most mathematicians are said to do, that P does not equal NP (ie there is no yet to be discovered algorithm that cracks NP problems) this at least means that “peak silicon” will keep internet commerce safe for the foreseeable future but it is bad news in lots of other ways.

There is a fourth option, of course, which is to get a better physics – either for silcon fabrication, quantum computing or some other physics based innovation. Right now, though, these are probably still the least likely options but as the links below show, lots of people are working .

Better algorithms, not better hardware are what make your computer faster, faster

Moore's Law, The Fifth Paradigm.
Image via Wikipedia

Many people have heard of Moore’s Law – which states that the number of transistors that can be packed into a piece of silicon doubles every two years (or 18 months in another formulation). More transistors means greater speed, more and cheaper memory and so on … so in the thirty two years since I first saw a real “micro-computer” raw processing power has increased by over 30000 times on even the conservative formulation of the law.

The contrast with other engineering improvements is enormous: typical lightbulbs have become six or seven times more energy efficient in that period – something that LED technologies might double again in the next few years. Great, but nothing like computing.

But this contribution from the electronics engineers, while of course impressive, is minuscule in comparison to some of the improvements won by the mathematicians and the computer scientists who have perfected better, faster, methods to solve the common problems. These improvements in algorithms are not universal, unlike Moore’s Law, but can be much, more bigger – often in the factor of millions of times faster.

We are on the verge of having another such improvement revealed – to the “fast fourier transform” (FFT) algorithm which allows signals to be broken down into their components for compression and other purposes.

The FFT improvement is said to be (the paper is yet to be published and only the abstract is in the public domain) around a factor of 10 – which could have big implications for any application where fat data has to be pushed over a thin line and some loss of quality is permissible (mobile telephony is one obvious example but home sensors could be another).

The FFT image compression algorithm was patented some years ago, but as a pure mathematical procedure such a patient has no application in UK (or EU) law (and surely that is right – how can it be possible to patent something which already exists?) – it is not clear what the legal position of this innovation will be.

Once again, though, all this shows the fundamental importance of maths and science education to us all – and the importance of pure mathematical and scientific research. A little more emphasis on this and a little less on the “needs of industry” (very few employers are interested in research as opposed to getting their products out of the door a bit faster or cheaper) would be a welcome step forward for policy makers.

More computing nostalgia

I stumbled across this collection of covers of “Practical Computing” – or as they styled it Practical Comp\mu ting – a really great magazine from the early days of “microcomputers” in the UK.

It used to have articles which were a bit more scientific and investigatory than others – I particularly remember one talking about how to describe n-dimensional space in a program.

I particularly remember these covers/issues – some of which still look great to me today, thirty years on. I desperately wanted to run the US presidential election program here too, but it used elements of the BASIC language that I simply could not work out how to substitute for from the ZX80’s limited vocabulary (back then most things were targeted at the variety of BASIC found on a Commodore PET).

October 1980 Practical Computing(NB as I recall the junior minister was Kenneth Baker).

Practical Computing November 1980

Hmmm… Fast Fourier Transforms….

Practical Computing December 1980

And finally – I remember thinking this was a stunning image:

Practical Computing January 1981