by krabob

Mastering multicore: Parallelizing any algorithms… and how my resource library helps

As in any big project, I use several program libraries for Math Touch Book.
I actually made a brand new Graph Theory API for it, to fit my needs. But I use another one I did between 2006 and 2009, to manage what is called application resources. This was a very interesting management library called Veda. In the case of Math Touch Book, I just re-used it to manage icons, screens, and messaging between objects. Thanks to Veda, If I need one more image for a button, I only add the image once and I have it both in the Android and iOS Apps, and for any future implementation. If I want to get rid of unused images or doubles, it is also automatized for all app versions.

Capture d’écran 2016-02-09 à 13.14.30
Managing external ressources with the Veda Lib in Math Touch Book. The interface is created automatically for any type of objects (images, fonts, sounds,…)

Veda is like a C++ patch where you add some declaration to the class you want to be managed. Then you have special serializable members (serializable means loadable/ savable/clonable). with basic data types of any kind, and one of the magic was special intelligent pointers that allowed to view your whole data as a graph with object links and dependencies. It was first made to experiment with “naked object” design pattern, which is about having interfaces to edit objects by just declaring objects, with no additional code. I also had some experiments with Java serialization, and my old xml based Amiga engine “Karate” was lacking automatic interfaces.
For your information, it is opensource and available here (and you even have Sega Dreamcast demos done with it !):

Veda source and binaries… mostly for windows xp

and Tons of Veda docs were “doxygened” here.

vedashotbig
The interface creator for Veda in 2008, showcasing some 3D. This was a Microsoft MFC implementation at the time. The current purple interfaces in other screenshots are the current SDL implementation.

As your whole objects could be managed as a graph, It was made possible to have incremental step-by step initializations for it: when You ask the construction phase of an object, It could need another linked object to be created first, and this second object could also be bound to a third ante-previously initialized object.

At the time veda was made, it had implementation for a 3D engine (that was drawn through an abstract engine, with 5 or 6 different implementations !) . In that case, I had a veda Script classes, which needed some 3D world, which needed 3d objects and cameras, which needed another 3D objects and 3D textures, which needed images of any kind.
But anything in computer science could be Veda-managed, not only 3D engines.

veda2
At left, the object list sorted by class. A blue rod meant “created”. editing a leaf object could lead to the de-creation of currently unused objects, dependant of it. The graph was used to manage object updates during edition. On the Second line of the edition deck, you can see an “intelligent pointer” to a texture. You could choose to preview an object with that GUI (here the torus) and to edit another one with the editor Deck. So you could finetune a texture, while watching the result on the object.

 All those objects were linked with intelligent pointers, and an algorithm was able to list all the objects in a leaf-to-root order, to assume you created the leaf objects and then only the dependent ones. A leaf object could be pointed many times, and any object could point another (exception was: you could not “ring” pointers), so it was really a Graph, not a tree.
So incremental initialisations were automatized, Interfaces were automatized, links and data were dynamics, whatever may be the size of the whole graph . My previous space video game “Earths of alioth” also used Veda to manage resources, and its nice progress bar at start, is done thanks to Veda.IMG_1207

At the time, I couldn’t cease to discover new advantages of Graph-theory managed resources in veda, that explains the never ending list of its features.

One of the biggest ideas came with the advent of multi core CPUs...
Since the mid-2000’s, we have efficient multi-core CPU, which means 2 or more programs can run at the same time, not only because of Preemption (which means: multi-tasking with one CPU), but because you really have multiple CPU working, which was impossible before the 2000’s, because of data cache and hardware memory issues: 2 CPU accessing the same memory would trash the memory.

Capture d’écran 2016-02-09 à 12.43.20
level design in “Earths Of Alioth” was edited with an automatized Veda interface !

But then, the problem was to create multi-core programming. in most cases, programmers didn’t change their habits: you use multi-core with long-known threads, and usually, a thread works on its own job, with its own data. For example, a thread would mix sounds alone, when a main thread would do something else.
In the case of very large computation to be performed using the same data, it is often hard to split an algorithm to make the CPU work in parallel. Because you have to be sure the data you read is coherent with what the other CPU are doing in the same time.

Basically, such an API like Veda could do that: for example, you can delegate the inits of whole branches of objects to other CPU threads when you know they are on a “separated branch”, and recover those objects to another thread when initialized.

To make it short and generalize it, knowing the graph of dependencies between objects, makes it possible to automatise the way multiple CPU can share their work with it: it’s just about some lines of Graph-theory algorithms to do that.

Thanks for your attention and have a nice day !

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *