Friday, June 24, 2011

"Good morning, Vietnam"

"Adrian Cronauer: Goooooooood morning, Vietnam! Hey, this is not a test! This is rock and roll! Time to rock it from the Delta to the D.M.Z.!"

Hello critters!
Long time, no see, the past few days I've been a bit busy but here is the next little thought dump.
Firstly on the agenda is a long standing issue with the mathematics surrounding computer science (or computer science using mathematics anyway you prefer), some guy wrote a book arguing that modern computer scientists don't need mathematics or that, and I quote,
"The notion of the algorithm, simply does not provide conceptual enlightenment for the questions that most computer scientists are concerned with." 
Needless to say I am STRICTLY AGAINST that point (and generally that idea), and I will try to summarize & generalize my arguments in a few brief points:

  1. The most basic notion and idea that comes to mind first is that you cannot truly grasp a concept about any subject without understanding the underlying principles and methods that lead to the creation and support of that idea. 
  2. One cannot show adequately and fully an idea which builds, or somehow relies, upon those principles. 
  3. Algorithm proofs & analyses. (not so general)
  4. The statement that mathematics isn't needed in computer science in itself implies that one limits oneself to only use some small part of the arsenal that is presented to him, or called another way one becomes a coding monkey. (Thanks to the CAD monkeys for the term :)
  5. The aforementioned limit also applies to mental development in those fields.
  6. etc. etc. 

Now don't get me wrong, I don't say that a computer scientist should be able to prove the Four colour theorem, but graph theory  for example is very heavily used in all aspects of computer science and having a more in-depth knowledge in it can prove vital in many situations, it could turn a good solution into a great one, but then proving so would also require mathematics, but then showing its limits as well and so forth. There are many likewise examples that could be given for other mathematics branches involved in computer science. There are a few related links in the end.

Second on the agenda is shorter and more technical, an interesting branchless solution to the integer comparison problem. There are numerous solutions on-line for it, but this one is a bit different and goes like this:
 Let's have two integers X and Y, then we want to be able to take 2 different "paths" in our program based on  the following criterion: if X <= Y -> path 1, otherwise -> path 2, but we want to do it branchless (no conditionals).
Solution: Define a 2 element jump array (or any other type of array needed based on the criterion), lets call it jump_table[2]. Then just execute the following: 
jmp jump_table[((X-Y)>>31)&0x1];
Simple proof (that it works): X-Y in integer notation would be either positive, zero or negative (trichotomy), 
 1. if it is positive or zero: bit 32 == 0 (and we take path 1) 
 2. if it is negative: bit 32 == 1 (and we take path 2)
After testing it against the conditional version for 1000000 iterations it proved to be ~ 16 % faster overall. But the most important property is that it is branchless, and in some cases that matters much more.

Third on the agenda I've been really agitated with the multi-core craze that's been going on lately. Now people started counting their cores, instead of the clock speed (as was the previous misdirection). I have always disliked (that's me being polite) people who try to show-off without having any valid reason to do so (aka posers/fakes). I think that humility is a virtue, and even in case one has reason to show-off it should be left to the public to decide so. Bragging shows simplicity and eagerness for recognition rather than eagerness for the subject itself. Now to the point, multiple cores is not real multiprocessing, because they have to share the same bus, memory lanes and of course socket. It _WILL NOT_ provide linear speed-up in anything for those (and many other) simple reasons, more to the point more cores doesn't mean more "speed", higher "speed" or any of the like. Such notions are more complicated and actually depend on many variables on multiple levels (hardware design, software design etc.). If manufacturer X has announced 16 core chip it doesn't necessarily mean it will perform better than provider Y's 4 core chip. More cores can better obturate a bus if used/designed correctly of course, and can provide very good speed-up for CPU intensive applications (which again depends on the software/hardware design working together). I don't want to get more technical, I think you should get the point by now. In my next post I'll probably write down a few thoughts about virtualization and the "cloud". 

'til next time!

P.S. In the next posts I'll give a brief overview of my new way for load-balancing between multiple peers which uses  relatively simple notions from combinatorics. One day it should become a paper.. (laziness)
If there are any mistaken/illogical sentences - I couldn't get a good night sleep, get over it!

The links:
Computer Science Mathematics - Some of the mathematics background required for computer science.
Theoretical Computer Science Talk - Given by Akamai's chief of technology, Tom Leighton
Want to be a computer scientist? Forget maths (Article) - About the book I talked about earlier.
From rigor to rigor mortis - A bonus. Take a look inside, you may like it.

No comments:

Post a Comment