Exploring Computation

Alex Papadimoulis on the Mechanics of Quitting

pramod.sub@gmail.com (Pramod) — Thu, 22 May 2008 17:49:00 +0000

Head over to WordPress for the full story.

Functional Programing 101: List Comprehensions and Closures

pramod.sub@gmail.com (Pramod) — Wed, 14 May 2008 18:11:00 +0000

For a bunch of reasons I've detailed here, I decided to shift my blog to WordPress. But don't worry, in order to serve you better, I will make sure I post a link here every time I make a new entry over there. :-)

Anyway, the functional programming series continues and this time we will look at list comprehensions and a simple closure. Head over to WordPress for the action!

A Question of Two Exchanges

pramod.sub@gmail.com (Pramod) — Mon, 05 May 2008 14:15:00 +0000

Let me interrupt the functional programming 101 series to pose an interesting question.

Question: Which of these two methods of swapping a list of integers is faster?

Method 1: Plain C Code

for(int i = 0; i <  array_size; i++)
{
    int temp = a[i];
    a[i] = b[i];
    b[i] = temp;
}

Method 2: Inline Assembly using the XCHG instruction.

__asm
{
    mov ecx, array_size;
    mov esi, a;
    mov edi, b;

loopstart:
    mov eax, [esi];
    xchg [edi], eax;
    mov [esi], eax;

    add esi, 4;
    add edi, 4;
    sub ecx, 1;
    jnz loopstart;
}

(Vague?) Hint: The Intel engineers who designed the XCHG instruction decided that it would primarily be used to implement synchronization primitives like semaphores and mutexes.

Comment to let me know what you're thinking about the two snippets of code and why any one of the two should be faster or slower than the other. In my next entry I will post the answer and also dig deeper in the mechanics of the exchanges.

Functional Programming 101: Lambda Forms

pramod.sub@gmail.com (Pramod) — Sun, 13 Apr 2008 04:43:00 +0000

I got into an argument with Ashwin the other day about lambdas and closures in C++ 0x. Unfortunately, if you're jetlagged and feverish you tend not make a whole lot of sense, and that is what happened with me. At the moment, I am not very jetlagged and a little less feverish, so hopefully, the following makes a little more sense. [The good thing is even if it doesn't make any sense I already have a solid excuse :-)].

In the Beginning
Lets use a simple example: I have a list of integers and I want to create another list that contains only those elements from this list that are greater than 5. The straightforward way to write this is like below:

def filter_above_5(l):
o = []        # initialize empty list
 for num in l: # iterate over list
    if num > 5: o.append(num)
 return o      # return filtered list

I wrote the snippet above in python, but hopefully, it is easy enough to read even if you haven't seen the language before. [1]

Shown below is example of how you'd use the filter_above_5 function.

print "original list:", l
print "filtered list:", filter_above_5(l)

Simple enough, isn't it? For reasons that we will come to later, people like to call this an imperative implementation.

Lets Make This Functional
If you think about it, filter_above_5 is a special case of a generic filter function which iterates over an input list and produces an output list that contains all the elements from the input list that satisfy some condition. [If you wanted to make things sound complicated, you'd use predicate instead of "some condition" and sequence and sub-sequence instead of input and output list. :-)] Jokes apart, it would be cool if we could write a general function like this:

def filter_list(predicate, l):
o = []
 for element in l:
   if predicate(element): o.append(element)
 return o

filter_list is a function that takes a list and a function (our predicate) as parameters and iterates over each element of the input list, and adds only those elements to the output list that satisfy the predicate. Then you'd call filter_list like below:

def greater_than_5(x): return x > 5
print "original list:", l
print "filtered list:", filter_list(greater_than_5, l)

It turns out that python already has a builtin function filter that does exactly what our filter_list function does. So our implementation just boils down to calling the that function with our custom predicate:

def greater_than_5(x): return x > 5
print "original list:", l
print "filtered list:", filter(greater_than_5, l)

Notice the difference between our initial implementation and new one. filter_above_5 did not just tell the interpreter what to do, it also specified exactly how to do it using a series of commands. For that reason, we call it an imperative implementation.

Our newest implementation that uses the builtin filter function does not specify how the filtering should be done. For instance, with all this ado about multi-core, it is not far fetched to think of a version of filter that spawns a number of threads and splits up the work of filtering among these threads. The cool thing is, if, say, Python 3.1 implemented such a multi-threaded filtering function, all our code which used the filter function would get the performance improvement for free.

Plus, notice that this version contains much lesser code, and we're programming at a much higher level of abstraction, not to mention the fact that the new version is more elegant.

All put together, I think it is fair to say, that the implementation that is based on filter is "better" than the imperative implementation.

Notice an important thing about filter - we are passing a function as a parameter to another function. Programming languages which allow this kind of thing - passing and returning functions from other functions, construction of functions at runtime etc. - are said to have first class functions. Now, exactly what set of attributes are required for a language to be deemed to have first class function support is a controversial topic, and so we will side-step that issue here. [2] The important point is passing functions to other functions doing so is a key aspect of functional programming. And since we're doing this in our filtering snippet, we're going to call it a functional implementation.

Enter the Lambda
Nothing we've done so far can't be done from, say, C/C++. In C for instance, we could've created a filter function that operated on array of void*, and used a function pointer to pass the predicate around. [Similar in spirit to the qsort library function]. In C++, we could have created a templatized version of filter that was allegedly more elegant and worked in more or less the same way, but would claim to be "safer" because it would be type-checked. [3]

Recognize that functions like greater_than_5 are use and throw functions. They are created only for the purpose of being called from the filtering function, and then they are never used again. Unfortunately, despite the fact that these functions are going to be called from exactly one place, they will still be sitting in source code polluting our namespace. What would be cool is a way of creating the function greater_than_5 specifically for the purpose of passing it to filter and then "forgetting about it".

The solution to this problem is called a lambda function. In python it looks like this:

print "original list:", l
print "filtered list:", filter(lambda x: x>5, l)

Pay attention to the first argument to filter: "lambda x: x>5". What it means is: create a function that takes one parameter as input - "x", and returns the value of the expression x>5 and then return that function that just got created. Note that the created function is anonymous. The key benefit now is that if I had to call filter in a hundred different places with 50 different filtering predicates, I needn't create a 50 predicates similar to greater_than_5 just to pass them to filter. I can create each of these functions at the point at which filter is called.

This means my code will look much cleaner; there will be no namespace pollution and most importantly I will have to write lesser code.

So, in summary lambda forms allow the functional programmer to create anonymous functions that can be passed around to other functions. Or even be stored for later use [although this is somewhat uncommon].

Isn't this just syntactic sugar?
The thing is, besides the lack of namespace pollution, and some fewer keystrokes to type [not that these aren't important things, but lets play the devil's advocate here], we still haven't gained much by using the lambda. And the fact is, if these were the only advantages of the lambda, lambda's would just be cute syntactic sugar.

But there is more - the key advantage of lambda's is when they are combined with a language that supports closures. We will look at closures in the next post.

In the meantime, if any of the above didn't make sense, or you have some feedback, please comment below.

[1] If you still run into problems understanding the syntax, please do let me know using the comments.

[2] Point is that it is is not correct to call python a functional programming language. If you want to be PC, it is a multi-paradigm language with some functional programming features. Anyway, lets not get into these religious wars and concentrate on the fun stuff instead. :-)

[3] Ensuring const-correctness on your elegant function, making it behave like a STL function so that it works correctly for everything that implements forward_iterators and/or const_forward_iterators and fun times spent debugging the wonderfully cryptic error messages that compilers spit out for templates are but minor prices to pay for that elegance. [Sorry, I couldn't resist that crack :-)]

EDIT (16-Apr-07): Added missing argument to the call to filter. Thanks Psygote for pointing this out!

weblog.rename("Exploring Computation");

pramod.sub@gmail.com (Pramod) — Sun, 13 Apr 2008 04:15:00 +0000

When I started off blogging, I wasn't sure where this was going and it seemed that I was going to be blogging about more or less random things. (Hence the lousy title :-) But as I blogged more and more, two things happened - (1) my own thoughts became a lot clearer about what I wanted to do and (2) the agenda for the blog itself became clearer.

So, moral of the story: this new tagline for the blog is that it will be about exploring the art, science, hardware and software of computation. For that to make any sense, I think it is important to define the meaning of the term computation. Here is what wikipedia has to say:

Computation is a general term for any type of information processing that can be represented mathematically. This includes phenomena ranging from human thinking to calculations with a more narrow meaning. Computation is a process following a well-defined model that is understood and can be expressed in an algorithm, protocol, network topology, etc.

The content of the blog is going to remain similar. The name change is an attempt to bring the documentation in sync with codebase, it is not a modification of the project scope. :-D

I hope you like the name change. If you don't, please let me know why. (If you do, you can still take this opportunity to compliment my naming skills :-)

Paul Graham on Programmers and Their Bosses

pramod.sub@gmail.com (Pramod) — Sun, 23 Mar 2008 09:56:00 +0000

At last, Mr. Graham has written something I agree with! :-)

The restrictiveness of big company jobs is particularly hard on programmers, because the essence of programming is to build new things. Sales people make much the same pitches every day; support people answer much the same questions; but once you've written a piece of code you don't need to write it again. So a programmer working as programmers are meant to is always making new things. And when you're part of an organization whose structure gives each person freedom in inverse proportion to the size of the tree, you're going to face resistance when you do something new.

This seems an inevitable consequence of bigness. It's true even in the smartest companies. I was talking recently to a founder who considered starting a startup right out of college, but went to work for Google instead because he thought he'd learn more there. He didn't learn as much as he expected. Programmers learn by doing, and most of the things he wanted to do, he couldn't—sometimes because the company wouldn't let him, but often because the company's code wouldn't let him. Between the drag of legacy code, the overhead of doing development in such a large organization, and the restrictions imposed by interfaces owned by other groups, he could only try a fraction of the things he would have liked to. He said he has learned much more in his own startup, despite the fact that he has to do all the company's errands as well as programming, because at least when he's programming he can do whatever he wants.

An obstacle downstream propagates upstream. If you're not allowed to implement new ideas, you stop having them. And vice versa: when you can do whatever you want, you have more ideas about what to do. So working for yourself makes your brain more powerful in the same way a low-restriction exhaust system makes an engine more powerful.

Intel Interesting

pramod.sub@gmail.com (Pramod) — Tue, 18 Mar 2008 16:12:00 +0000

Apologies for the corny title, but I couldn't stop myself! :-)

The most immediate news is the 6-core Dunnington, expected to release in the second half of this year. It looks like it has a 3-way split 9MB L2 cache, 16 MB of L3 cache and micro-architecture based on the Penryn. The kicker is that it only has a TDP of 80W!

There is more and more information about the Nehalem now becoming available. We'd already heard about the integrated DDR3 memory controller and simultaneous multi-threading (the successor to hyperthreading). The latest update is that the Nehalem will feature a QuickPath interconnect capable of transfer rates of upto 25.6 GBps. And it is not just more memory bandwidth and multiple cores that will improve performance, it turns out that the Nehalem will increase the OOO execution window to 128 uOps (from 96 on the Penryn) - so individual cores are also going to get faster!

In the longer term Sandy Bridge - the second of Intel's 32 nm processors - is going to have a 256-bit wide SSE execution unit. The only complaint I have about this is that it is 2 years away from shipping. :-)

See here, here and here for more details.

Random Link Clearance

pramod.sub@gmail.com (Pramod) — Wed, 05 Mar 2008 17:10:00 +0000

Links I've accumulated over the last week or so:

50 Cent vs Windows XP. In Da Club mixed with error sounds from XP. I like this better than the original!
Scott Meyer's wonderful comic with Basic Instructions on How to Seem Smart.
On a slightly more serious note, Jeff Atwood explains how to hack your progress bars to make your code seem faster!

SSE Tutorial : Part III

pramod.sub@gmail.com (Pramod) — Sat, 01 Mar 2008 15:26:00 +0000

After fighting with blogger for about half-an-hour to make it get the damn formatting right, I've given up. So I've published it on Google Docs instead.

Click here to see the document, and please leave your comments below.

Finding Which Core Your Thread is Running On

pramod.sub@gmail.com (Pramod) — Thu, 21 Feb 2008 15:38:00 +0000

How do you figure which core of a multi-core processor your thread in running on?

At first, I figured that there might be a Win32 function to do this. So, I looked around unsuccessfully in MSDN hoping for a "get" equivalent of SetThreadAffinityMask or SetThreadIdealProcessor.

It turns out the correct way to find this information is to ask the processor. Seems logical if you think about it, but unfortunately the answer not easily googleable because of the weird terminology!

After a little digging around, I found that the CPUID instruction has this interesting beast called an APIC ID. Intel documentation says:

"Each logical processor has a unique APIC ID,which is initially assigned by the hardware at system reset and can be later reprogrammed by the BIOS or the operating system. On a processor that supports Hyper-Threading Technology, the CPUID instruction also provides the initial APIC ID for a logical processor prior to any changes by the BIOS or operating system."

Simplified, this just means that in a multi-processor/multi-core system, the APIC ID is a unique identifier for each logical processor.

What's a logical processor? A hyperthreaded system capable of running two threads "in parallel" has two logical processors. A quad-core system has 4 logical processors. A simple way of looking at this is that you have as many logical processors as graphs in the performance tab of the task manager!

So, all you have to do is use the CPUID function 0x0001 and look in bits 31-24 of the EBX register, which is where the APIC ID lives. This looks like this:


int apic_id;
__asm   
{
mov     eax, 1;
cpuid;
shr     ebx, 24;
mov     apic_id, ebx;
}

So that's that!
Let me know if you have questions/comments.

Einstien Quote

pramod.sub@gmail.com (Pramod) — Sun, 10 Feb 2008 14:08:00 +0000

Here is one of my favourite Albert Einstein quotes:

“
The more a man is imbued with the ordered regularity of all events, the firmer becomes his conviction that there is no room left by the side of this ordered regularity for causes of a different nature. For him neither the rule of human nor the rule of divine will exists as an independent cause of natural events. To be sure, the doctrine of a personal God interfering with natural events could never be refuted, in the real sense, by science, for this doctrine can always take refuge in those domains in which scientific knowledge has not yet been able to set foot. But I am persuaded that such behavior on the part of the representatives of religion would not only be unworthy but also fatal. For a doctrine which is able to maintain itself not in clear light, but only in the dark, will of necessity lose its effect on mankind, with incalculable harm to human progress. In their struggle for the ethical good, teachers of religion must have the stature to give up the doctrine of a personal God, that is, give up that source of fear and hope which in the past placed such vast powers in the hands of priests. In their labors they will have to avail themselves of those forces which are capable of cultivating the Good, the True, and the Beautiful in humanity itself. This is, to be sure, a more difficult but an incomparably more worthy task.

”

Experiments with CUDA/CUBLAS on a Tesla C870

pramod.sub@gmail.com (Pramod) — Sat, 09 Feb 2008 13:05:00 +0000

I've been playing around with the CUDA/CUBLAS/CUFFT libraries recently attempting to benchmark the kind of performance improvements possible with GPUs. I've found some surprising results along the way, and I thought I'd put them down here.

Data transfer between GPU/CPU is still a big bottleneck. On my relatively old DDR2-533M bus with the Tesla sitting in PCIe-x16 slot I am seeing throughputs in the 1100-1300 MB/s range. Obviously, smaller data sizes don't see the full throughput. Note that pinned memory is about twice as fast as "regular" memory. I am told that some folks have seen over 3GB/s using pinned memory; presumably using faster buses than mine. Taken by itself, that is a very impressive number but even that does not make the transfer bottleneck go away.

A corollary of the previous result is that to see a real speedup (lets arbitrarily define this as >= 20X over single threaded CPU code) for single operations, the big-Oh complexity of operation you're doing on the GPU must be higher than that of the data transfer. Not sure if I put that too well, what I'm saying is: you will see a big speedup with matrix-matrix multiply because the operation is O(n^3) and the data transfer is O(n^2). On the other hand, matrix-vector multiply will not see as much of a speedup because both your data-transfer and operation are O(n^2). [1]

There are sweet spots for CUBLAS kernels. Sgemm likes matrix sizes that multiples of 32, and Sgemv likes matrices with rows that are multiples of 16. Performance at the sweet spots is much much better.

Sgemv throughput peaks at only 10 or so GFLOPs when the trans input is 't'. When trans is 'n', I'm seeing throughputs of over 35 GFLOPS. Translated into English, this means that cublasSgemv is much faster at doing y = Ax + y [trans='n'] than y = transpose(A)x + y [trans='t'].

Sgemm gives me peak throughputs of 120+ GFLOPs. There are some variations for different inputs, but except for the multiple of 32 quirk (which can bring the 120 GLOPs number down to 100 GFLOPs), I haven't seen anything that affects performance significantly.

Sgemm and Sgemv are much faster than Ssymm and Ssymv. My recommendation is to use Sgemm and Sgemv throughout - even for symmetric matrices.

Another weird thing I'm noticing is high CPU usage. With almost no CPU code running [except the data-transfers and kernel-invocations] I am seeing CPU usages in the 50-70% range. I know for a fact that several NI device drivers can do DMA between main memory and modular instruments with less than 10% CPU usage. I'm no device driver expert but I figured I'd see numbers in the same ballpark here. I'd love to see the CPU usage number go down, so I can bang out even more FLOPs using the CPU.

Overall, my experience with CUDA has been extremely positive. Despite the weird performance quirks, the technology seems very promising. The API is well designed and easy to program and debug. One minor complaint I have is the column-major array storage. This combined with the Sgemv trans='t' performance bug is causing me a few problems.

Let me know if you have questions/comments.

Footnotes
[1] The situation could be different if you multiplying vectors with a constant matrix [so you don't need to push the matrix over the bus again and again], in that case Sgemv can give you big performance gains over CPU code.

On Relevant Research

pramod.sub@gmail.com (Pramod) — Fri, 08 Feb 2008 18:39:00 +0000

Mahesh sent me this fascinating newsgroup thread from back in 1992 where Andrew Tannenbaum (of the OS and networking books fame) flames Linus Torvalds and make some less than correct predictions about Linux! Highly recommended reading.

Anyway, there's this thing has been bugging me for a long time now, but this newgroup thread and my recent visit to NCC '08 pushed these thoughts to fore and I figured I put them down here for public ridicule. :-) What I've been thinking about is fundamentally simple: what fraction of research is actually useful? [1]

To me, the fundamental point of research (or for that matter anything at all) is that it should solve somebody's problem. Mathematically beautiful results, and elegant languages are all very well and good if you're making a living writing papers and textbooks. But, unless people are able to use them to do stuff they couldn't before, they are useless. When you put it down like this what I'm saying seems fairly obvious, but people just keep missing this damn stupid obvious fact all the time. Consider the Lisp fanboys led by Paul Graham and his ilk: they keep going on and on about how Lisp is a wonderfully elegant language that will expand your ways of thinking, blah blah blah, you should move to Lisp and you will be saved, blah blah blah. Granted, Mr. Graham actually made a ton of money selling his Lisp web-app to Yahoo, but I believe this is because he was a good programmer who wrote good code for a good application. IOW, it had nothing to do with Lisp and everything to do with the application and its programmers. For, if Lisp were the magic route to startup success Cleartrip.com wouldn't suck so much [2]. Not to mention that there'd be more guys trying to repeat the formula and succeeding.

My theory is that people who consider themselves reasonably intelligent human beings [3] find it is extremely hard to resist the tendency to show off how smart they are. And so, they get caught up in intellectual games that don't achieve anything useful. As a consequence lots of research keeps falling into this trap of doing stuff not because it helps make something better, but rather as a means for the doer to show off how much smarter s/he is than the rest of us.

Coming back to the point about Lisp : an elegant, theoretically beautiful language is great, but what is really required is a reasonably productive language that is efficient, has great interoperability and will allow me to leverage existing code. [4] I don't claim to speak for anyone else, but efficiency is definitely a criteria for me - I am working on real applications that have real timing requirements that look very difficult to achieve from even relatively fast high-level languages like C#. And I can assure you that interoperability and the ability to leverage existing codebases is a huge deal for anybody. And so my response to the Lisp/ML/Haskell advocates is to get back to me when a compiler that can provide performance to within, say, 50% of C, and will work seamlessly with existing code is available.

I went off on a rant about Lisp, but I should clarify that I am not against using Lisp or any other functional language. (In fact, I'm trying to teach myself F# right now) The point I am trying to make is that for a programming language to be really useful to everybody, there are more constraints than just elegance of expression. Similarly, like Lawrence C. Foard points out to Mr. Tannenbaum, theorizing about an OS's elegance and portability is bogus if you don't meet the first criterion - usability. [5] Generalizing, I believe this is a point that applies to all research, if something doesn't make something possible/easier/better/faster it isn't worth doing.

Footnotes:

[1] I am using research and useful without defining them precisely, hopefully, you all get what I mean. My goal here is to explore a line of thought, not to get into vague semantic arguments. :-)

[2] The last time I used it, I got sever errors on 3/8 page reloads! I find it ironic that for a Lisp startup they have an MBA for a CEO!

[3] EDIT: There used to be a comment where which was being misinterpreted, so it doesn't exist any more! :-)

[4] And may I say that Anders Hejlsberg, Jim Hugunin and team have done wonderful job achieving just that with the CLR and DLR.

[5] By usability I mean being able to use the OS to run real applications.

Answer to the question in the SSE Tutorial Part I

I'd asked why "add eax, 1" would be preferred to "inc eax". It turns out inc eax is a 1-byte instruction, and so can screw up alignments for subsequent memory fetches. (Something along these lines, I will put a more detailed explanation shortly).

SSE Tutorial : Part II

pramod.sub@gmail.com (Pramod) — Sun, 27 Jan 2008 14:20:00 +0000

A note before I start: not all the features mentioned below appeared in the same revision of the SSE instruction set. (IOW, the instruction set is constantly evolving, so your mileage may vary depending on when you bought your processor).

The key point to SSE is that AMD and Intel have put 8 new 128-bit registers on their processors. You can view the registers as:

16 8-bit integers
8 16-bit integers
4 32-bit integers
4 32-bit single precision floating point numbers (float)
2 64-bit double precision floating point numbers (double)

And you can do math on all the 16/8/4/2 elements "in parallel". The obvious benefit is that if you're doing the same operation on all the elements of an array, doing it 16 at a time or 4 at a time is faster than doing one at a time. There is also another benefit - it turns out that on modern processors and buses, reading memory elements that are aligned on 128-bit boundaries is much faster. So, optionally, SSE provides instructions to perform 128-bit aligned reads and writes from memory. (Of course, you can choose not to use them, because there are equivalent unaligned reads as well) There are also instructions provides closer control over caching behaviour - for instance the MOVNTDQ instruction writes a 128-bit value (Double Quadword) to memory whilst hinting to the processor to not store that value in the cache. The instruction PREFETCH, (obviously), prefetches values into the cache.

One big feature (especially for C/C++ programmers) that came with SSE was faster double/float to integer conversion instructions. When coding using the x87 floating point stack, the code to convert a floating point number to an integer in C, would work roughly like this: (a) store the FPU rounding mode (b) Set the rounding mode to truncate [note that this is required by the C standard] (c) Convert double to integer (d) Restore old FPU rounding mode. The whole circus was rather expensive. SSE gives 2 sets of fast instructions to convert doubles/floats (and the tuples of 4 floats and 2 doubles) to integers. The instruction itself specifies the rounding mode to use (i.e. truncate/round) and so no messing with the FPU state is required. In fact, the so-called SSE acceleration that the VC++ 8 compiler pretends to do is mainly limited to using the faster convert instructions!

Besides the fast math there are some other benefits. SSE finally got rid of the floating point register stack, so the new floating point code is easier to write and a little faster at times. There are also some pretty cool instructions aimed at specific problems. An example is the CRC calculation instruction that is available with SSE revision 4!

Anyway, that's it for now. Next time, I promise more code and less gyan. Let me know if you have questions/comments.

Software Engineers aren't?

pramod.sub@gmail.com (Pramod) — Sun, 27 Jan 2008 06:55:00 +0000

You all probably know that Ravi Mohan has started off this controversy (flame-war?) by saying something to the effect of "You can call yourself an engineer, but by my definition of an engineer, you're lying (to yourself). You're actually a clerk.".

The who is an engineer and who isn't debate that he's started off reminds of one of these useless academic questions we got asked in VTU. [1] Whether you conform to what X's defines an engineer/clerk/manager/scientist to be, is completely irrelevant and useless. The designation you have is just a label - an aid for identification. If you claim to be a engineer, but you aren't - who cares? [2] The key goal is you should be happy doing what you're doing. To be fair, Ravi says as much (albeit in a provocative tone).

The unfortunate part of this debate is that people are going to take offense because they perceive being called a clerk as an insult. They'd like to think they are better than clerks, and they don't like being told otherwise.

My point is, people have all sorts of foolish and not-so-foolish delusions - and mostly they cause no harm. Sometimes, it is these so-called delusions that give you motivation during hard times. If your ECG technician fancies himself a cardiac specialist, good for him. Smile while he gives you advice on your heart and use your common sense on whether to follow it. Don't shout at him and call him a unqualified technician. Not following his advice is perfectly fine, but if you shout at him or even make fun of him privately, you're being arrogant.

The only defense I can see for this whole series to have been posted on the internet is that it opens up an interesting line of thought. Exactly what does an engineer mean? Lets follow this to its logical end. Assume that we did arrive at a consensus on an exact definition for engineers. Now you can say with authority that X is an engineer and Y isn't. Now that we have this, I can't see a single useful benefit having it. I can see a lot of pissed off engineers/clerks (take your pick). And that is why I believe he should've kept his thoughts to himself.

I also don't buy the don't-read-my-blog-if-you-don't-agree-with-me argument. It is a bit too similar to:

Person A: You're an idiot. Did you know that?
Person B: Why the hell are you insulting me?
Person A: Don't listen to me if you don't like what I say.

Yes, everybody has a right to their opinions, but with that right comes the responsibility of having to stand up for them. If you believe that X is true, you've got to take the shit that comes with it.

Ravi, I suggest you do some introspection on whether this who is and isn't engineer thing actually did anybody any good. May I also point out that insulting the commenter who (rightly/wrongly) criticized your blog entries was uncalled for.

[1] Case in point: Differentiate between a for-loop and while loop.
[2] There is also a bigger question here - can you even make a definition of an engineer that is objective? If not, and it seems like that to me, whose definition do you pick as the "right" one? Having said that, I believe that in this specific instance, since the definition itself is irrelevant, the question doesn't need any answering.

A Quick and Dirty Intro to SSE - Episode I

pramod.sub@gmail.com (Pramod) — Tue, 25 Dec 2007 14:03:00 +0000

Since, I've done a little bit of assembly language coding using SSE, I thought it might be useful to write up a little introduction here.

What is SSE?

SSE = Streaming SIMD Extensions. It is an instruction set for IA-32 processors that speeds up doing SIMD operations.

What the heck is SIMD anyway?

SIMD = Single Instruction Multiple Data. Example: you want to add 1.0 to every element of a floating point array - so your instruction (Add 1.0) is the same for each element, but the data (the elements of the array) are different - hence multiple data and single instruction.

Why can't I just use a loop?

Loops are slow. That's why.


                  mov     ecx, nElements
addOneLoop:
                  mov     eax, [esi]
                  add     eax, 1
                  mov     [esi], eax
                  add     esi, 4
                  sub     ecx, 1
                  jnz     addOneLoop

Assuming that all elements of the array are in L1 cache (which is a bogus assumption, but will do for our purposes help simplify the explanation), the processor will spend far more time doing the book-keeping for the loop - decrement the counter, increment the pointer, executing the branch, than actually doing the addition. In fact, the add eax, 1^* is the fastest instruction in the loop because the immediate operand is a nice small constant, and the other operand is a register. In fact, if you looping condition is more complicated than the one shown, or if you have a branching construct inside of the loop, branch misprediction alone can slow your code by a factor of around 2/3!

It turns out that this kind of loop is really common in certain applications - signal and image processing for instance, and so AMD and Intel support the SSE instruction set which accelerate these algorithms.

Must be complicated, right?

Not really. It is quite simple, and we'll go into the details over the next few posts. Let me know if you have any questions/comments.

The Eager Student's Question Corner: (Or maybe lame section name corner :-)
* Any guesses as to why I used "add eax, 1" instead of "inc eax"?

Size Matters

pramod.sub@gmail.com (Pramod) — Tue, 25 Dec 2007 13:29:00 +0000

Steve Yegge latest post starts off talking about code size, meanders around to how much Java sucks and how Java programmer's are oblivious to it and ends with a plug for dynamic languages. Business as usual, right? :-)

Fortunately, Jeff Atwood has deciphered Mr. Yegge's hidden meaning and given us an executive summary:

If you personally write 500,000 lines of code in any language, you are so totally screwed.
If you personally rewrite 500,000 lines of static language code into 190,000 lines of dynamic language code, you are still pretty screwed. And you'll be out a year of your life, too.
If you're starting a new project, consider using a dynamic language like Ruby, JavaScript, or Python. You may find you can write less code that means more. A lot of incredibly smart people like Steve present a compelling case that the grass really is greener on the dynamic side. At the very least, you'll learn how the other half lives, and maybe remove some blinders you didn't even know you were wearing.
If you're stuck using exclusively static languages, ask yourself this: why do we have to write so much damn code to get anything done-- and how can this be changed? Simple things should be simple, complex things should be possible. It's healthy to question authority, particularly language authorities.

My two cents on the issue:

Code is like life, if you pay attention to detail when it is small, it will be easier to maintain when it grows. So, being scrupulous when you're writing code the first time round, as opposed to "making-it-work-now-and-cleaning-it-up-later" will really pay off in the long run.
Even if you can't write in a dynamic language, just programming in these languages a little will show you newer, cleaner ways of expression that you can take back to C++/Java.

Both posts are highly recommended reading.

blog.restart();

pramod.sub@gmail.com (Pramod) — Sun, 02 Dec 2007 14:34:00 +0000

A few months down the line, I've figured that completely shutting down the blog was a bad idea and so I am going to start blogging again.

 RantGenerator blog = Pramod.createRantObject();
 blog.restart();

I have a couple of interesting things I want to blog about. So stay tuned please!

Shutting down blog

pramod.sub@gmail.com (Pramod) — Sat, 06 Oct 2007 13:57:00 +0000

Hi everybody,

I am not able to find enough time to do justice to this blog and so I've decided to stop blogging for now. I don't want to delete the blog, because at some point, I want to start again, and I kinda like the domain name! :-) But I think that is at least a few years into the future.

So, for now, this blog is officially shutdown.

When I started writing, I didn't really expect anybody to read this. But quite a few people did, and I really appreciate your support.

Thanks!
-- Pramod

Is Assembly Language Still Worthwhile?

pramod.sub@gmail.com (Pramod) — Mon, 23 Jul 2007 16:17:00 +0000

I've been spending the last few weekends coding in Assembly Language.

The interesting thing is, I've heard from a whole bunch of people (Ashwin, Anand and most recently Nigel) that modern compilers do a very good job of optimizing C/C++. And so, (a) it will very difficult to write code that is faster than the compiler (b) it is a not a worthwhile exercise writing assembly code. Now, I am always skeptical when people say that computers can do something better than humans! :-) And for that (and other reasons), I find that statement somewhat hard to digest.

On a related note, there is a lively debate going on at the "Programmable Logic DesignLine Newsletter" about whether people still programming in assembly language. The general consensus seems to be: yes, maybe, sometimes, but watch your step! And that is more or less how I feel about the issue! :-)

Now on the compiler vs. human issue, I think a human can always hand tune compiler generated code to do better. I don't think this is always going to be worthwhile because of the amount of effort this involves, but if you want to be at the bleeding edge of performance, judicious coding in assembly can only do you good. I say this with confidence because as a human you will always know more about the program than your compiler!

Let me give you an example. Ashwin wrote this convolutional coding function that looks somewhat like this:


inline int8 calculateMaskedParity(int32 SRState, int32 mask)
{
 int32 y = SRState&mask;
 y ^= (y>>16);
 y ^= (y>>8);
 y ^= (y>>4);
 y ^= (y>>2);
 y ^= (y>>1);
 y &= 1;
 return (int8)y;
}

extern "C" CONVOLUTIONALENCODERASM_API 
void convolutionalEncodeC(LVInt32ArrayHandle hGenMatrix, LVInt8ArrayHandle inBitStream, LVInt8ArrayHandle outBitStream)
{
 int8 *inBits   = (*inBitStream)->data;
 int8 *outBits  = (*outBitStream)->data;
 int32 numberOfBits = (*inBitStream)->size;
 int32* genMatrix = (*hGenMatrix)->data;
 int32 nMasks = (*hGenMatrix)->size;

 int32 srState = 0;
 int32 outIndex = 0;
 for(int i=0 ; i<numberOfBits ; ++i)
 {
  srState <<= 1;
  srState |= inBits[i];
  
  for(int j = 0; j < nMasks; j++)
   outBits[outIndex++] = calculateMaskedParity(srState, genMatrix[j]);
 }
}

Ignore all the structures prefixed with LV, they are basically ways of passing data between LabVIEW and C/C++. The meat of the code is inside that the for loop. And the for loop calls that neatly written function calculateMaskedParity which xor's all that bits in an integer in time proportional to log(n) where n is the number of bits in a integer. You'd think that this was a pretty good convolutional coding function and if you ask me, I'd say that it is! But I was able to write a function that does convolutional coding and puncturing, and with an option for different puncturing vectors operating on different parts of the input bits in assembly language that ran at the same speed as the plain coding function!

I was able to do this because I knew how many times each loop was going to typically run. I could make decisions like this inner loop is going to be run 30/40 times, so I'd better keep everything this one needs in a register. This variable is only going to be used once every 100 or so bits, I don't really need to use a register for this. I could say, I need to do outBits[i], but I don't have room for a register for outBits. But stop, outBits is just [ebp+12], and the loop counter is eax, so I can use [ebp+eax+12] instead! No compiler can figure out these kind of "optimizations" - they can create graphs and re-order instructions, they can allocate registers "optimally". But if there are 4 variables and only 3 registers, the compiler can't make decisions like: now "i" needs a register, inPtr needs a register, but I am only going to be writing out if this bit is not going to be punctured, so I probably skip the register for outPtr and use it to keep track of my puncturing vector instead - because compilers cannot understand programs!

Now I am not saying that we should all go and write everything in assembly. (We should go write everything in Python, not assembly :-) what I am saying is, you can always "beat" the compiler if you put sufficient effort into it. Whether that effort will be worth your while depends on your needs and your application.

Another reason you might want to use assembly language is if you want to take advantage of some special features of your architecture/instruction set. I will try and blog about this in over the next few days, so stay tuned. :-)

Intel Taking GPU Threat Seriously

pramod.sub@gmail.com (Pramod) — Fri, 08 Jun 2007 16:04:00 +0000

Ashwin found this Intel Presentation about the threat to CPUs from GPGPU.

The presentation makes very interesting reading, and I think the multi-core "gpu-like" architecture that the presentation is recommending is far more scalable than the path Intel are going down on now. Also, programming one of those SPMD cores is going to be so much fun! :-)

Ant Colony Optimization

pramod.sub@gmail.com (Pramod) — Sun, 03 Jun 2007 04:44:00 +0000

Ant Colony Optimization is a combinatorial optimization technique discovered by Marco Dorigo of the at the Université Libre de Bruxelles.

Basically, the method tries to model how ants find their way to food.

Initially, ants move in random directions seeking food. As an ant moves, it drops pheromone trails on the ground. This serves two purposes, once the ant finds food, it has a way to get back home. Secondly, another ant moving around knows that an ant passed through here and went in a certain direction. Thirdly, ants which encounter pheromone trails are likely to follow that trail. The probability of following a trial increases with the amount of pheromone dropped on that trail. Finally, the pheromone doesn't stay around forever, it evaporates.

Picture this scenario: an ant finds its way to food and returns to the base. Around the same time, a few other ants stumble upon this trail. Some of them decide follow it. These ants will also find the food. In doing so they will lay out a pretty strong concentration of pheromone on the ground - causing even more ants to follow that trail. Pretty soon all the ants will have a route to food.

The story doesn't end here. Say one of the ants is a rebel. It breaks out of the pheromone trail to the food and "discovers" a shorter path to the food. Because of the pheromone that the rebel laid out, some of the other ants will also follow the new trail. If the route is shorter, fewer ants will be required to achieve the same concentration of pheromone as the initial longer trail. Pretty soon, all the ants will switch to the shorter trail. Cool, huh?

It gets better. Supposing an evil human drops a big fat book right on the route to the food. (Probably squashing a few ants, but that's not the point) The ants will now face one of two scenarios: (a) they have an alternative (and also what used to be sub-optimal) path to the food (b) they don't have a path to food. Option (a) presents no trouble at all. The ants will just simply switch to the other trail (because now there is only one trail to follow). Option (b) will mean the ants will now start from scratch again. After a while, a new path to the food will be found and the pheromone along the old path will have evaporated. And so, the ants will stop following the path to that leads to a dead-end and switch to the new route.

Ant Colony Optimization techniques are an attempt to use a similar algorithm to optimize a function. They work by exploring a search space using entities analogous to ants, and metrics that are analogous to pheromones. There are three key points here:

The algorithm is stochastic.
The algorithm is massively parallel - because you can put as many ants as you want on the problem and each ant's path can be computed independently of other ants. (And so are amenable to a parallel implementation)
The algorithm relies on communication via the environment (the "pheromones") rather than between the ants themselves. (And so reduce the evils of communication between agents in parallel machines)

Ant Colony algorithms have been applied to many different problems with considerable success. You should visit the official website for more information.

Excellent Video (and a little philosophy)

pramod.sub@gmail.com (Pramod) — Fri, 01 Jun 2007 15:50:00 +0000

My goal for this blog has been to keep the content (for want of a better term :-) technical. But why should my blog be technical? Well, I don't want a personal blog because I believe personal communication should not be done on "broadcasts". I guess I'm a little old fashioned in that respect. I don't have anything to say about movies, music or any of that stuff. I don't think whining on a blog is going to make the world a better place - Looks like I'm unique in that respect though! :-) And, I don't want one of these "mind-dump" blogs - thank you very much. So, what all of that boils down to is my content filter usually lets in only technical posts!

I said usually, and today I've got something unusual! Anand showed me this really great video on YouTube. If you've not seen it already, I am sure you will enjoy it. Just be patient and watch it till the end!

Presentation on GPU's for Signal Processing

pramod.sub@gmail.com (Pramod) — Mon, 14 May 2007 15:48:00 +0000

UPDATE: I have pulled the presentation down. I will soon put up a slightly modified version of the presentation. I apologize for the inconvenience.

Ashwin, Nick and I recently presented a paper at NITech (a National Instruments internal technical conference) on how to use Graphics Processing Units for "general purpose" computation. Ashwin and I were specifically interested in using GPUs for Signal Processing (Part II of the presentation), and we ported some "standard" signal processing algorithms to the GPU and benchmarked against their LabVIEW implementations.

If you're interested the presentation is here.

I think the best way to do this is to view the presentation on a dual monitor system with one monitor showing the slides so that you can see the animations and the other monitor set up so that you can read the notes as you go along. There are lots and lots of notes and a couple of hidden (and unfortunately incomplete) slides too, so it shouldn't be too hard to figure out what we're trying to say.

And of course, you are most welcome to contact me with questions, comments and ideas at pramod.subramanyan@gmail.com.

What are you waiting for? Go click that link!

Intel Performance Primitives and a Random Story

pramod.sub@gmail.com (Pramod) — Fri, 11 May 2007 22:17:00 +0000

A colleague of mine recently found this. Looks like Intel have created optimized processor specific libraries for computationally intensive tasks.

Cool.

This reminds me of the last time I downloaded a library from Intel. This one. Let me tell you the whole story.

It was about 4-5 months ago (probably Oct/Nov 2006), and I was trying to optimize a software FM-Demodulator. The demodulator had this tight loop - probably 4 or so computationally intensive statements inside and I wanted to find out which of those statements was the worst of the lot. So, because I am too lazy to download and install a profiler and figure out how to use it, I did the next best thing - I stuck a bunch of timing code around each statement using the Windows API QueryPerformanceXXX functions so I could measure how long each statement was taking to execute.

In case you've never done this before, this is typically how its done:


  LARGE_INTEGER freq, start, end;
  QueryPerformanceCounter(&start);
  {
    // do your stuff here;
    // and then some more
    // and more
  }
  QueryPerformanceCounter(&end);
  QueryPerformanceFrequency(&freq);
  double time = (double) (end.QuadPart - start.QuadPart)/freq.QuadPart;

So I had this timing code all around each statement inside the loop trying to figure out which statement was the worst of the lot. And then I ran it, and spit out the timing results. Found out that all of the statements were taking almost exactly the same time to run!

Huh? One statement was this complex arctan, and another was this simple FP subtraction, how can they both take the same time?

Good question. It turns out that all the time was actually being spent inside the timing measurement functions! And because the time my code took to execute was so small, all I was measuring was how long it took for the QueryPerformanceCounter function to run!

My guess is that some kind of hardware timer was being queried inside QueryPerformanceCounter, and since talking to hardware timer means I/O - and this in turn means all sorts of arbitration, interrupts and switching into kernel mode and a gazillion other overheads - moral of the story: QueryPeformanceCounter is slow!

Good. I like the irony. A function that is supposed to help you make your code faster is itself slow.

Anyway, once I'd figured this out, I was searching for other ways of making timing measurements. So I came across this enhanced timer thingy on Intel's website. So without further ado, I jumped to the last page and downloaded the damn thing and set about measuring my code timings with Intel's Enhanced Timer.

Good stuff happened, I got exactly the same measurements.

Then I dug a little bit deeper, by looking into the Enhanced Timer source files. Turns out the so-called Enhanced Timer was itself using QueryPerformanceCounter! Grrr!

Anyway, the point of all this is:

The so called Enhanced Timer is not enhanced at all.
Measuring code timings is only accurate for code that takes at least a couple of hundred milliseconds to run.
Don't ever trust a marketing flyer. :-)

Update: I heard from Sastry that some NI customers have used IPP, and with excellent results. So I take back all the nasty things I said about Intel's software engineers. However, I still think Intel have a long way to go before they are up to speed on the software side of things.