OpenGL and Colours

Often times, in OpenGL, I tend to think about tinting colours.  Doing colour arithmetic.  Then the painfully obvious realization came to me.

I normally treat an RGBA vector as a point in 4-space.  Then why don't I normally define colour transformations through matrix operations?  Making a monochrome image becomes re-orienting (transforming) the space of colours to that of a single line running from black to white.

Even wikipedia has the matrices to go from RGBA to YUV space.  Continuing along that logic, I could build matrices that take in an image in RGBA and increase the Y component of it.

Even further along, if I use 5x5 homogeneous transformation matrices then the values can be shifted.  So blacks can become red...  Actually, this is very nicely done using SIMD operations (128-bit vectors, I think processors sporting the new 256-bit vectors are out or will soon be out.  I pray my code is compiler friendly enough to not need to explicitly worry about the issue).

Rotations do as they are expected.  For example, rotating from red to blue would continually swap the colours.  Potentially a very elegant way to manipulate colour.

Normally, interpolating of values between transformation matrices can be a bad idea.  The vectors within the matrix represent the visible space.  (imagine a 3x3 matrix.  When drawn, the resulting area corresponds to how the matrix will alter points passed to it.  Swapping the x-y coordinates is as simple as swapping the first and second rows of a 3x3 matrix when using column vectors.)  Interpolating them can cause a collapse (go to vector 0) of the space.

Obviously, there are OpenGL extensions to support this.  Some of it in software (writing the shader code or the software code to do such transforms is trivial).  I just thought of putting this out as glColor alone is very restricted compared to what can be done with matrices.  Especially since all intuitions from linear transformations in space can be applied to colours.

Insanity

Here's my take on what insanity is.  It is due to a failure somewhere in the thought process.

I used to think it was something global.  As though everything goes wrong; a mind's capabilities that end up collapsing.  Nothing legit could come out of an insane person.

But, spending time with a person that may be deemed insane at times I must revise my conclusion.  First, this insanity is of a part of the mind.  In the case I saw, it was the ability to retrieve data - the memory was dying.  Interesting may be a sick word to use in context, but I'll admit that the reasoning seemed to be working perfectly.  Operating on imperfect material just completely messed up the reasoning.  Add in very short-term memory, and it's chaos.

Another thing I noticed was slipping in and out of the dream world.  Given the person was tired, this was expected.  What wasn't expected was the content within the dreams and reality to be indiscernible.  Awaking from a dream thinking that what happened in the dream applies to reality.  I guess the opposite is true as well.

Then there was complete denial of the insanity.  All the checks and balances in the person's mind told them their logic was flawless.  Even though information was incorrect, this was not detected.  Even the fatigue did not give them a hint that they might be not thinking straight...

The fatigue also added a slowness to actions.  Seconds were needed to reason about simple things, such as how to use an appliance.

Not something to wish onto anyone.  But very annoying since the person losing their marbles can not detect themselves that they have lost it.  Hurting others in their environment without realizing it...  Animosity builds within relationships...

In the end, the madness was due to lack of sleep and lack of nutrition.  Two important things, without which we may become a burden onto the world.

Parallel Processing For the Masses?

Full well I realize that Amdahl's law specifies that the upper bound of time equals the sum of the serial portions of an application.  Another part of me wonders if it really matters.

Let me rephrase my thoughts: certain portions of applications explicitly need the extra compute power to run.  Image processing, audio processing, and physics simulations are heavy.  But the glue between these is not.

Of course, we are heading towards the land of highly parallel architectures.  There is no denying it.  Compute-intensive applications will benefit.  The OS will become more complex.  Most programmers will not see the difference.  They should not need to care about threads.  Not even about mutex.  Even less about race conditions.

Before I was advocating implicit parallelization through complex objects that would run asynchronously to the main application.  But then I started thinking about actual applications to realize that only certain frameworks would need to behave like this.  To apply any parallelization strategy globally is silly.  Consider processor affinity: a single application using a single thread on a single core will more easily benefit from the cache than a system that is distributed among cores.

If I were to write an application, my first reaction is not to parallelize it, but to see how well it behaves on a single core.  Test it.  Debug it.  Get it working.  If the performance is good enough, then I don't bother going the extra step.  The argument that processors will become more parallel at the expense of speed is valid -- my reply is that the thinking IBM's Cell was well ahead of its time.

Let us now consider a simple forms-based application.  The application may be serial, but the database engine is a highly parallel system capable of efficiently managing unthinkable amounts of data.  The form should run on a single core.  There should have no mutexes.  No race conditions.  The bottle-neck should be accessing and processing requests to the database.  To replace what is currently threads (thinking of .NET with a thread stalled with the database query while the other does the UI) the database API should be asynchronous and trigger events on the main thread of the application.   Congratulations!  Many more people are taking advantage of parallel architectures without becoming parallel programmers!

A more complex example: an image viewer.  Something that shows pictures captured from a camera.  This application will ask the OS to load an image.  Should loading the image be a sequential task?  Not for JPEG.  Should the application try to load a different image on multiple threads or should the OS work on loading images in the background and present results when needed?  The latter should be the case.  Ideally, the programmer never has to worry about a mutex.  Not even a race condition.  The word "parallel" should never come to mind.  Essentially, effort should be expended on the UI rather than the technological merits.

I've come up with a counter-example for myself.  What if an image is loaded and immediately drawn somewhere?  I'll remind myself that OpenGL is a successful asynchronous API, and that drawing only occurs when glFinish is called (maybe even glFlush, and there are other conditions, but we don't need to explore them).  So we request an image to be loaded.  That happens in the background.  Need to blit it?  Sure!  That can be added to the queue.  Display to the screen?  That can be queued as well!  At the end of the draw call tree for the window and its controls?  Good, crunch through that drawing in parallel and display it.

Let us suppose that the application also does facial recognition.  Something heavier.  Let us suppose that the OS does not support it and it must be done from scratch.  "Scratch" is never the case.  At a certain point the Eigenvalues will most likely need to be calculated for the light-corrected faces.  That sounds like something any scientific library will provide.  And these libraries will be tuned for modern parallel machines.

What I'm getting at is that parallelism is not something that everyone will have to deal with.  And no-one should want to deal with it.  Small pockets of people will deal with it.  Most coders will work in software will then become highly sequential.  A push to make parallelism exposed in all wakes of software is not the right move.  Rather, specialized libraries and software as a service should be parallel.

Software as a service?  Think an SQL server.  Indexing services specifying what files change.  Any request to the OS.  Pattern recognition services in the OS.  This opens the door to NUMA-style architectures which partition memory regions with processing units -- a much easier way to scale up the number of cores.

Pushing the idea further; parallel applications should be (in the worst case, like) servers independent of the UI.

What I'm getting at is that there are already many things that need to be thought of when writing code.  UI design and usability.  Correctness.  Resource leaks (lingering connections to a database, for example).

Performance from multiple cores, when done right, requires careful management of data.  Processor affinity must be respected.  Cache lines should not be shared amongst cores.  Cache lines should be accessed sequentially.  Race conditions.  Synchronization.

Consider that an application made to use cache correctly can run twice as fast as the same application made to use multiple threads.

Why should a controller, that ran well on a i386, be forced to worry about parallelism on multiple cores?  Are we that bad at creating application programming interfaces?

My conclusion is that parallel processing is not for the masses.  It should be available; but used with discretion.  This rush towards parallelism in all matters is part of a techno-freak's fantasized reality-distortion field.  Yes - we are going parallel.  No - we don't need to make software thousands of times more complicated to write (saving time & money) to benefit from it.

Who decides whether your average person must become a parallel programmer?  API designers.  I'm sure that if they took a step back, then they would realize that for most purposes asynchrony on a single thread is the easy the way forward for end-users of the API.

EDIT: I initially wrote this quite late.  I cleaned up the argument (a bit).

NOTE: I really should add notes about the GPU; but that will be left for another post.

Monetize and Stats

There's this feature called "Monetize" in the blog settings.  It's even there for all of my blogs.

As most of my posts go: little, if any, research.  Take the information here with a grain of salt.  I write these posts fairly quickly and am bound to make mistakes.  If there is a mistake, point it out with relevant sources and I'll happily edit the content.

Many of which do not have any readers.  This one, if Google's stats are right (I think they're inflated), has about 100 page hits a month.  That's less than 100 readers a month.  And this blog actually has more readers than any of my other blogs.  Admittedly, if we're optimistic, I might say that the potential revenue is $0.15$ a month (assume a CPC of $0.30$, each person actually clicks, and we get 50% - you can verify these numbers Google Traffic Estimator Sandbox and http://adsense.blogspot.com/2010/05/adsense-revenue-share.html).

So... let's say that to make this venture break even (writing takes time), then $100.00 a month would cover my time to write silly rants.  Assuming I'd even care about the cash.

Ok, that's about 666 clicks per month.  If (assumption again, beware) 10% of readers click (I'm sure my target audience loves ad-block. I love ad-block too!), that's about 6660 readers a month.

Why did I feel like ranting?  Consider this: blogs with few readers that have ads will benefit whoever serves ads (larger accumulated potential user-base).  It also makes blogs that exist in the hopes to make profit stick out like a sore thumb.  It is possible for a new blog to attract a large user-base on the first or second post.  Enough to make ads a good idea.

On the other-hand - wouldn't a blog like that try to keep the momentum going for a few months?  See that success is good after the first month (or so) and then monetize?

Why did I write this?  I enjoy looking at the stats.  Trying to understand why 100 lost souls would wander to this blog each month.  Looking for patterns.  I've found a few, but that's for another post.  This one arose when I compared the stats to the monetize features.

I'm aware there are plenty of sites that offer hints on how to maximize profit using ads.  I don't care for that.  This blog is my little soap box.  It has no focus.  It has no research.  It just rants.  100 readers a month is amazing for something with so little focus that it hurts.  100 is amazing since I'm not targeting anyone, just writing what I'd contemplate anyhow.  Writing what I'd write anyhow and forget in a drawer....

Now my rants are forgotten, but indexed by search-engines all over!

Doxygen: Step-by-step

I've started to use Doxygen to document a small little experimental library of mine.  Here are the steps I would use to document in retrospect.

First step was to create a header file for the library.  Call it myLibrary.h.  In addition to including any files that should be publicly available, I put in a nice piece of documentation to specify what the library does.

/*! \mainpage
My library does something.  It's awesome.


Here are two examples:
- \subpage AwesomeDemo1
- \subpage AwesomeDemo2
*/

This just sets up our main page.  It states what the library does.  I have two example pages.  One of them is called AwesomeDemo1 and the other is AwesomeDemo2.  The dash denotes that this is a list of items.

Ok, that's a good first step.  Now, let's look at AwesomeFunctionality.h.  All of the following are fragments from AwesomeFunctionality.h with some comments mixed in to explain what's going on:

/*! \file AwesomeFunctionality.h
\brief This is awesome
Awesomeness is achieved by doing awesome things.  These awesome things arise from the awesome code made available in this header file.
*/

This declares what the file does.  What should we find in this file?!  It sort of emphasizes the simple fact that no file should be a catch-all for garbage that belongs elsewhere.  Give your file a purpose!  In Doxygen, when you generate a file list, the text after "brief" becomes a short description of the file (call it an overview so someone knows if they want to know more).  The text afterwards is for once the reader decides to get more information.

/*! \page AwesomeDemo1 First Awesome Demo


Here's something awesome:
\code
Awesome *x = new Awesome();
\endcode
*/

Recall our AwesomeDemo1?  Here we name it "First Awesome Demo", which will be linked to from the main page (and also serves as the name for this page).  Following is the text on the page, and a piece of sample code.

I tend to learn from example, and Doxygen will link the sample code to the documented classes.  Be clear and concise about what the demo does with little added fluff and your reader will be happy.

/*! \defgroup AwesomeGroup The awesomeness begins here
This group contains a set of things that are awesome and you should look at!
*/

This defines a module that the user will see as "The awesomeness begins here".  You might want to name it something reasonable, such as "Compositing Capabilities".  Imagine if you're a reader that wants to do "awesome things".  Then if functions and classes related to "awesome thing" can be found in a single place, it makes the reader's life easier.

Finally, let's get to the interesting part:

//! Does something awesome
/*! \ingroup AwesomeGroup
  This is an awesome thing!


  Look at the function \ref AwesomeFunction for more details!
*/
class Awesome
{
//! Awesome data member
int m_awesome;
};

Finally, some code.  This is just a header file, so it's just a skeleton.  The first comment is the brief.  "Does something awesome" should give the reader a clear idea of what the object does.  The longer documentation, using C-style comments (don't forget the !), first specifies that this has something to do with the AwesomeGroup.  Then we give a longer description of what the object does.  Notice we use "\ref", it will make a link to the function called AwesomeFunction.  Normally, for classes, links are automatically created.

For each member within the class, we document them as our next example.  If there isn't much, we just leave in the brief comment.

//! Initializes the awesomeness
/*! \ingroup AwesomeGroup
\param[in] something something or other
\pre The awesomeness has not been initialized 
\post The awesomeness is initialized
\exception If the awesomeness was already initialized
\return An awesome integer
*/
int AwesomeFunction(int something)


Now...  for methods within a class, normally I wouldn't use "\ingroup".  The rest is to be used judiciously.  Your goal is to give enough information so that the object may be used without drowning the user with too much information.

The parameters can be named as either [in], [out], or [in,out].  Specify if data will change or not.  Const should be used for [in] though.

The pre-condition, post-condition, and exception parts should be used judiciously.  Or so I believe.  It is nice to have them though.

Return - well, it's always a good idea to say what that is.

I used the GUI front-end.  Upon compiling the documentation, I did not include any private headers or source (.cpp) files.  Essentially, only the public documentation should be easy to get.  Private documentation should be accessible within the headers but more challenging to get at.

As a reader, you must have realized that most of my efforts have been for the reader.  And the logic is quite simple - the documentation is for another person - a future reader.  Documentation simply makes your project more accessible to others.  Something that is essential for open-source projects.  To be used, it has to be easy, and require minimal effort on the part of the user (regardless of functionality).

Simulating a Simple Fluid on I.B.M.'s Cell Broadband Engine...

I have just spent a bit more quality time with a PS3 running Linux (I opted to not update the firmware).  Upon coding, I realized one thing: spe_context_run is extremely slow.  My programming strategy was to use the PPE to quickly assign tasks to the SPU in a way that would minimize cache misses.

I'll step back a bit.  The PPU runs a simple piece of code that tells it what it should run on each SPU once a task completes.  What it should run depends upon what data is already loaded into the SPE's local store, what data is already local to the cell but within another SPE's local store, and what has to be uploaded.  The problem is that I can't call spe_context_run too often or else the application is too slow.   The best performance I obtained by doing the same amount of work and DMA data transfers while minimizing the number of calls to spe_context_run.

What does this mean?  The SPE should be treated as an independent machine that so happens to share memory with other SPEs and the PPE.  It should be given a big list of tasks that it can work on without any support from the PPE.

Why is this a challenge?  I'm integrating the equations of fluid flow.  Communication should occur between the SPEs for the boundary conditions.  Rather, I'm betting that border conditions only need to be worried about during the change of frame.  Why?  If I can run the simulations sufficiently fast (80+fps) then my calculations say that this little cheat will not be noticed by the user of the system.

Numerical modelling for my claim?  consider the CFL condition.  Let's say the grid-size is 1.  Then the maximum velocity should be about 1 grid-cell per pass of a finite-differencing-based advection scheme.  I'd suggest using forward and backwards finite differencing for integration rather than central differencing as central differencing will have trouble with sharp edges.  Anyhow, we have a maximum velocity of 1/timestep.  At 80fps, that's about 80 pixels that data can travel per second across the grid.

That is sufficient for my purposes.  For a 1024x1024 grid, it would take 12.8 seconds for something to travel across it.  Projected onto a sufficiently large surface (not a monitor) the user will feel like the fluid is moving at a brisk pace.

Maybe a Lagrangian method would be better.  Or even a finite-element method.  I've already tuned my code for Eulerian grids...  unfortunately.  I'll build something better in the next development cycle.

Education Through Games? (arithmetic)

One of my favourite quotes is something along the lines: "the human body can do infinite amounts of work -- as long as it isn't what it's supposed to do..."

I'm talking specifically about the use of video-games.  Since people tend to enjoy playing them there must have a way to infuse them with educational material.  So the logic goes.  Likewise, the same logic should work for board-games, or any other type of game.

However, overtly claiming the educational nature of a game makes it less entertaining.  Requiring someone to "play" an educational game is about as fun as doing homework.

To successfully make a game that teaches something, the game must be primarily designed to entertain and challenge.  The learning should occur implicitly.

For example, let's consider a turn-based battle sequence in an RPG.  Each action by the player balances how much damage that can be taken versus what can be dealt.  Let's say the player has one unit and the computer opponent has a single unit.

The units on both side have HP (health power) and Damage.  Both are integral values.  Damage from one player deducts health power from another player.  If health power reaches 0, then a player loses (dies).

A step back reveals that the player can compare both numbers.  If Damage exceeds HP then the opponent is guaranteed to fail.  This leads to the typical strategy: concentrate all fire-power on the weakest of the opponent's units.  The weakest unit of the opponent will die off.

What we have described is a system that requires knowledge of the concepts underlying the number system and a means to compare.  Many games display meters to reflect the underlying integral value as a quick-reference metric.  But the end result is the same.  I'll argue that this type of game can be more effectively used as an educational game then games designed to be educational for use in an educational setting.

Even this is an over-simplification of the scenario.  Often, the HP of the opponent's units are unknown.  Through defeating an opponent once, the player can estimate how much HP that opponent has.  This requires the ability to sum up values and maintain a mental dictionary of the capabilities of each opponent.

Further within the game, the human player must deal with more and more complex scenarios.  Poison, applied to a unit, will decrease the unit's HP each and every turn by some amount.  Resistance to different magics (fire and ice could be the magics) also affects how the player positions their units against opponent units.

Tactical RPGs take this concept a step further and adds in the lay of the land to the mix.  Attacking a unit from behind leads to more damage being dealt at the expense of having to move a unit in place to do the attack.

In the end, if I wanted someone to learn something about arithmetic, I would suggest an RPG.  With any luck, the one they'll choose will force them to consider the underlying numerical system.