Highly Parallel Programming Self Reminders

Threads, that's the topic of the day.  Very simple?  I've been experimenting with ways to distribute my code, and I've come to a few simple conclusions:

Hide Threading:  Threading should be done by the underlying API.  And this underlying API's threads should block so they aren't squandering CPU resources.  This means that whenever the given threaded component is used, it will use CPU resources as needed.

Worker Threads:  Have a few dedicated threads for the heavy lifting - and choose the number of threads based upon the number of cores that are available.  All other threads should be in a nearly permanently blocked state.  This means that your worker threads won't compete with the resources of the other threads.

Document:  Knowing what's thread-safe is critical to writing code that won't fail in the long run.

Queues:  Use a queue structure to send messages between threads.  This means that a thread won't block immediately if another thread doesn't reply immediately.

Cache:  Be aware of it, and code expecting the CPU to have a cache.  Programs written in Java, as well as in C will benefit from being aware of the cache and the underlying structure of the system's memory.  For multi-core processors, this can be the source of a speed boost (eg. L2 cache is shared among cores on Core2Duos).

Compress:  Do you really need all that data to travel across the bus?  Minimize data transfer when possible by reducing the number of bits needed to represent the data.

Benchmark:  You don't know the ultimate gain in speed.  Test your theories -- preemptive optimization may actually hurt the performance of the application.  Overflowing the bus degrades performance, btw.

Use What You Need:  If a single core gets the job done - then use a single core.  Distributing a problem has overhead - programmer wise as well as speed-of-execution wise.

Have a Game Plan:  The most important part.  Know how things will be structured overall.  If you can't see the whole structure in your mind, consider alternatives as it might be too complicated.

Extra thoughts as of February 24, 2015:
Tasks:  Use task managers to handle multi-threading when possible.  For example Grand Central Dispatch in OS X will automatically manage the number of available threads based upon available CPU across all applications.

Task Stealing:  Tasks, described as a series of interdependent operations based on data transformations, allow tasks to focus on recently touched data.  Task stealing, if I recall, is quite optimal and allows another core to steal tasks when it is idle from those assigned to other CPUs.  Look at Cilk and Intel Thread Building Blocks as concrete implementations.

Asynchronous:  I believe the OpenGL API provides an example of what to strive for in terms of APIs.  Writing serial code and logic is easy, parallel is hard.  Shouldn't the API run in parallel while giving the illusion of sequential execution?

Better Terrain Rendering

After work, I get home. I spend the day in front of a computer, and wish to rest by writing even more code. What could be better?

Well, I'm currently working on a special project as a portfolio piece/awesome thing for the yearly Apple developer competitions. On the side, I've given up on GameLib - too much code with too little return - objective-C suits my needs. I still miss GameLib for it's ability to cram all implementation details in the .c file as opposed to C++/Objective-C - but if I keep with that route, I'll spend more time maintaining the library than taking steps forward with my interests...

Now, on to the meaty part, the rendering! I love ray-tracing, but it's not the solution that I'm searching for. What I want is a fast, detailed, renderer for terrain. Something that could draw the smallest pebble to the longest blade of grass.

So here's my first solution to my little problem: render a special mesh that is the terrain. Simply, have a mesh with concentric circles - where the user should focus the circles are closer and denser. Then, the further, the sparser they become. The fun part comes when it's time to render - use a height-map to display the mesh and to do bump-mapping. So as the user approaches something they see a wonderfully high polygon count, but further away it appears blurred (which I use to mask all the other shortcuts I've used)

Now I want a million blades of grass with such features -- sending me back to the drawing board, even though I may have a solution resting in my head. I just haven't thought it through enough yet.

Raytracing Woes

Well, last semester I wrote a raytracer for class. Now I'm currently adapting it to other projects this semester, and working on it to be fast enough to become the default renderer in GameLib.

It's amazing how much a month of neglect of code brings out all the flaws. Rested mind, I easily found spots where the logic was questionable - and impossible to enter if statements. And all that in the core ray-shooting code.

Right now I'm adding amortized rays, and removing bad code. The program is somewhat faster - from 0.8fps -> 1.8fps max on a 256x256 texture. I had hoped for more than just a single fps gain - so will revisit the code next week to improve subdivisions.

The implementation from last semester used Altivec to amortize rays - the problem being that if rays diverged paths then a lot of useless calculations would be done (the higher the resolution, the better the benefit, or so is the bet).

Collision Detection as Rasterization

The easiest method to collide objects takes n factorial time. That is, compare each and every object with each other.

Now, the smarter methods involve using quad-trees, arrays, graphs -- essentially any method to minimize the search path given a region.

Let's assume the following:

• Memory is cheap
• Small world
• Looks right preferred over perfection

Given that, let's work on the 2D problem (some games can be represented as 2D problems in a 3D environment -- for example, if the number of objects to collide on the y-axis is little, and the level spans quite a distance on the x & z axis). And, we'll use this example. Let us assume that we have access to a big array, about 1024x1024 which can be used to represent a view of the world from the top.

Each element of the array can be thought of as a pointer to a sprite object. All that we have to do is then "render" the level onto this bitmap of pointers. It'll tell us exactly what object is colliding with which other object. I'm currently using this in one of my games since some sprites have very odd/ever changing shapes. Also, this must not be a new/clever technique since other games have over-sized morphing objects.

But, here comes the interesting part: we have hardware to do rasterization. If we only had 4 objects, we could assign each object to a specific element (RGBA) and render the scene from above without the land/useless detail. Any time a pixel is shared between two objects, then it could be used to raise a red flag. The more clever may want to use the individual bits (but since everything is done in floating-point, I'm not sure how exact the colors 1,2,4,... are when normalized. Also, the other problem is that the bitmap has to be brought back to the host -- which uses quite a bit of bandwidth.

On the other hand, rasterizing on the CPU takes away time that would normally be used for AI/other game logic.

For those who want the most speed, they should read the articles on quad-trees, etc. in Game Programming Gems. These provide smarter/proven ways of doing collision detection than this little rant.

A few notes about GameLib

Well, the time to post GameLib is getting closer. I've been keeping a little SVN database on my local machine to keep track of it. Once commit #7 (this is after a years worth of coding) is done, the system will have a very mature implementation for matrices (now it's quite basic), and have it's own entry-point (the current one is platform-dependant).

What does GameLib look like in code? It's OOP design was partly inspired with DirectX compatibility in mind (that I wouldn't have to do too many hacks to port it). Well, let's say it has the following interfaces/objects (and more):

• Object - handles reference counting/allocation tree


• IString - handles static strings


• I3D_Device - access to state of currently-rendering-to 3D device. Also allows creation of sub-objects from device.


• ILight - A light, allocated from the device


• ITexture - A texture,


• IGPUDataPool - Use this to prevent loading the same image twice into memory (retains pooled objects with weak references)


• IVertexBuffer - Used for holding everything that is needed to describe a mesh


• IInputDevice - Used for getting input from a game-pad, etc.


• IState - Used with the finite-state machine (game is loaded up in a state).

I'm still wondering about initialization; but will code it as follows (since booting up the system is getting more complex every day). Right now, I'm debating whether having a struct be filled, or having an object that can be queried and can return errors.

Also, the exceptions are used only in cases of extreme failure, and should not be used to manage program state (once the library gets out).

And for the license, do I have to pre-pend it to the start of each file? If so, then that'll take a bit more time before the first upload.

All this, to say that it exists, I've spent a year or so on it, but I just haven't gotten to uploading it yet.