Distributed Parallelism for N-body using MPI, C++11 threads and SIMD

Over the final few weeks of the last trimester, for one of my modules I have been doing research into different methods of parallelism, how effective they are on performance and generally whether or not I can get much of a speed up with them. This post will discuss the algorithm used, optimisations performed and the specific results into this test. Overall it was found that combining multiple different paralellisation together (MPI & C++ threads & SIMD) produced the fastest speed up although this was not nearly as fast as the GPU compute shader version that was tested.

If you like percentages and data this is the post for you. I will make a post later and link to relevent articles on how I went about optimising these different versions another day.

Algorithm

The algorithm I tested was a simple N-body with gravity. The serial version that was used as a baseline and tested against the other versions of the applications was based on the version taken from the DirectX SDK and as such uses certain DirectX data structures although these are unnecessary. The algorithm is as follows.

// Body to body interaction, acceleration of the particle at 
// position bi is updated
void bodyBodyInteraction(D3DXVECTOR3& ai, D3DXVECTOR4& bj, D3DXVECTOR4& bi, 
                         float mass, int particles ) 
{
 // Get the vector between the two points
 D3DXVECTOR3 r = D3DXVECTOR3(bj.x - bi.x, bj.y - bi.y, bj.z - bi.z);

 float distSqr = dot(r, r); // Find the dot product of the vector
 distSqr += softeningSquared;

 float invDist = 1.0f / sqrt(distSqr);
 float invDistCube =  invDist * invDist * invDist;
 float s = mass * invDistCube * particles;

 // Update the acceleration with the calculated value
 ai = D3DXVECTOR3(ai.x + (r.x * s), ai.y + (r.y * s), ai.z + (r.z * s));
}

// Call this function to calculate the next position of all the bodies
// in the system, represents a single pass
void calculateGravity()
{
 // Loop through every particle in the system
 for(int i = 0; i < MAX_PARTICLES; i++)
 {
  D3DXVECTOR4 pos = pData1[i].pos; // Stash a local copy of
  D3DXVECTOR4 vel = pData1[i].velo; // the position and velocity
  D3DXVECTOR3 accel = D3DXVECTOR3(0, 0, 0);
  float mass = g_fParticleMass;

  // Calculate acceleration to be applied to the
  // using all the other particles in the system
  for (int tile = 0; tile < MAX_PARTICLES; tile++)
   bodyBodyInteraction(accel, pData1[tile].pos, pos, mass, 1);

  // Update the velocity and position of current particle using the 
  // acceleration computed above
  vel = D3DXVECTOR4( vel.x + accel.x * 0.1f, 
                                        vel.y + accel.y * 0.1f, 
                                        vel.z + accel.z * 0.1f, 
                                        vel.w);   
  vel *= 1;     // damping
  pos += vel * 0.1f;   // apply deltaTime 

  pData2[i].pos = pos; // Save the newly calculated position and velocity
  pData2[i].velo = D3DXVECTOR4(vel.x, vel.y, vel.z, length(accel));
 }

 pData1 = pData2; // Swap the buffers
}

The above algorithm represents that simple sequential version used for the tests, the data structures can be changed for arrays of floats, vectors or anything else but the underlying theory is the same. For each particle in the system, calculate the gravitational effect on it based upon every other body in the system. The bodyBodyInteraction function above calculates the acceleration effect upon one body based upon another, whilst the actual acceleration is applied after this has been calculated in the calculateGravity function. It is then applied and stored in pData2 which is a temporary list of all the new positions so that later particles in the list can still refer to the old positions. After all the calculations are complete we can then switch pData1 and pData2 and then loop the process ad infinitum.

Optimisations

I optimised this algorithm for multiple versions using C++11 threads, MPI and SIMD with a comparison against a version with DirectCompute shaders found in the DirectX SDK. Since this problem is primarily a data parallel problem I simply modified the algorithm slightly so that I could split up the data set to work across multiple cores or machines. SIMD required much more modification of data structures and instructions to properly function. The change can be seen below.

void calculateGravity(int start, int end)
{
 for(int i = start; i < end; i++)
 {

The algorithm will now work by specifying a range of values to work upon in the range of data. This is useful for the multi-threaded approach where thread 0 will do the first group of values, 0 - 255 for example, then thread 1 will do the second group, 256 - 511. This follows the parallel data and sequential processing model.

SIMD

SIMD (Single Instruction Multiple Data) by far required the biggest changes through the code, the main things that were changed were the use of the D3DX11VECTOR types which were changed to 32 byte  __m128 values instead. Luckily the position and velocity information for each particle fit perfectly into these types as they are also represented by 4 floats each. The other primary change was the use of SIMD operations. Since there were a large number of changes made more details on these changes will be outlined in another post.

// Body to body interaction, acceleration of the particle at position bi is updated
void bodyBodyInteraction(__m128& ai, __m128& bj, __m128& bi, float mass, int particles ) 
{
 __declspec(align(16)) __m128 r = _mm_sub_ps(bj, bi);
 
    float distSqr = dot(r, r);
    distSqr += softeningSquared;

    float invDist = 1.0f / sqrt(distSqr);
 float invDistCube =  invDist * invDist * invDist;
    
    auto s = _mm_set1_ps( mass * invDistCube * particles ); 

 ai = _mm_add_ps(ai, _mm_mul_ps(r, s));    
}

In the above code the distance between bodies is defined as "__declspec(align(16)) __m128" this means that we are using a memory alignment of 16 bits on our __m128 data type. This data type is used for the Streaming SIMD Extension (SSE) instructions.

The first instruction used in this section is "_mm_sub_ps(bj, bi)", this simply subtracts the values of bi from bj. With these SSE instructions we can perform the subtraction of each part at the same time on the CPU instead of one after the other. This should give us a theoretical speed up of four times for this single calculation.

The other instructions used in this section were "_mm_add_ps" which adds two __m128 together, "_mm_mul_ps" which multiplies two __m128s and "_mm_set1_ps" which simply sets all the values in an __m128 to the value defined.

By altering all of these vector operations to use SIMD we can make use of the hardware support on the CPU to speed up the time taken for a single operation. Whilst the speed gain for a single operation may be relatively negligible, we are doing them multiple thousands of times resulting in a compounding speed saving. It was interesting to note that despite both Intel and AMD supporting SSE instructions only the Intel CPU received a speed increase, the application ended up running slower on AMD hardware. This highlights some of the difficulties of using SIMD as you must take in account specifics of the CPU you are programming for. Memory alignment and how the individual CPU processes the instructions can result in differing level of speed increases. Improving the speed on the AMD machine was beyond the scope of this project but I have no doubt that it is possible.

C++11 Threads

For the C++11 threads we create the threads as follows.

// split up work for number of threads in system
for(int j = 0; j < num_threads; ++j)
{
 threads.push_back(thread([=](){ calculateGravity(start, end); }));
}
for(auto& t : threads)
 t.join();
pData1 = pData2; // Since it's multi-threaded we do the 
   // buffer switch after all threads are complete
}

The main changes are that now we must switch the data buffers after all threads have been rejoined as opposed to inside the function due to the parallel approach we have taken. The C++ threaded application simply splits up the data amongst each of the availible hardware threads for processing then rejoins at the end. As such the amount of speed increase is dependent upon the number of hardware threads available.

Since this application makes use of the number of cores on the CPU, this could be combined with the SIMD level parallelism and as such a version of this application was also produced taking into account the changes made by the SIMD application. It was found that this version did offer a speed up over the threaded or SIMD version alone.

I'll write a more detailed post about C++11 threading and how to do so and put a link here when it is done.

MPI

MPI (message passing interface) allows distributed applications to communicate across networks to each other. The main communication methods that were used for this application were "MPI_BROADCAST" and "MPI_SENDRECV" these two processes allowed the application to communicate the data across all machines and then have each machine send it back to a host machine.

Using MPI, multiple instances of the application can be running across different computers in a network, each one has an ID, with the host as 0. As such for these applications, all of the data was sent out to each machine on the network. Each machine that is not the host machine will wait until it has received its data before it goes on to process it, the host machine will then start sending the data to all the machines depending on the communication method being used. "MPI_BROADCAST" sends the data specified to all machines in the network and requires all of the nodes to be listening and call it at the same time. The other method is "MPI_SENDRECV" which acts as a point to point communication between two nodes. For the version of the application created I instead used "MPI_SEND" and "MPI_RECV" the distinction being that these are uni-directional. One process on the system will call "MPI_SEND" and the specified node must then at some point call "MPI_RECV", if either node is not ready to send or receive then that node will wait. This was used for the communication of the newly calculated positions back to the main node.

The code below shows the point that decides which part of the application is run by the node itself. "my_rank" is the nodes rank within the communication network, a rank of 0 belongs to the host node. As such, if you are not rank 0 then you are worker node, in this manner the stuff within the first if statement is performed only by the worker nodes. 

if (my_rank != 0)
{
   // Not main process - wait to receive message
   PARTICLE* message = new PARTICLE [ MAX_PARTICLES ];

   // Wait to receive data from host node
   MPI_Bcast(message, MAX_PARTICLES * 8, MPI_FLOAT, 0, MPI_COMM_WORLD);
   pData1 = message;
     
   calculateGravity(0 + (divide * my_rank), divide + (divide * my_rank));
   pData1 = pData2;

   message = new PARTICLE [divide];

   for(int k = 0; k < divide; ++k)
      message[k] = pData1[k + (divide * my_rank)];

   MPI_Send(message, divide * 8, MPI_FLOAT, 0, 0, MPI_COMM_WORLD);
}

The below else statement is what is performed by the host node. The primary differences are that it needs to initialize the particle system, broadcast the data out to all the nodes, calculate a portion of the data and the finally rejoin all of the calculated data from across the network.

else
{
   InitiliaseParticles();// Initilise the groups of particles
   
   // Send out the list of particles to all nodes
   MPI_Bcast(pData1, MAX_PARTICLES * 8, MPI_FLOAT, 0, MPI_COMM_WORLD);

   calculateGravity(0 + (divide * my_rank), divide + (divide * my_rank));

   pData1 = pData2;

   for(int k = 1; k < num_processes; ++k)
   {
      PARTICLE* message = new PARTICLE [ divide ];
      MPI_Recv(message, divide * 8, MPI_FLOAT, k, 0, 
               MPI_COMM_WORLD, MPI_STATUSES_IGNORE);

      for(int x = 0; x < divide; ++x) 
      pData1[x + (divide*k)] = message[x];
   }
}

The MPI version of the application was combined and tested with all other versions of the application. Since MPI is just a method of communicating between computers this meant that each computer itself could still benefit from the other parallelisation techniques to make use of the local hardware. Of course, in this instance the biggest performance factor was the speed of the network.

It was interesting to note that the application seriously slowed down for the smallest of data sizes, this was due to the transfer time of the data being higher than the time taken to process it on a single machine. As such it is important to take this into consideration when designing your application.

More details into MPI and their functions will be outlined in a post in future. 

Test Results

The main applications that were tested were as follows:

·        Sequential N-Body

·        Sequential N-Body – With SIMD

·        Parallel N-Body – C++11 Threads to split up data

·        Parallel N-Body - C++11 Threads (with SIMD)

·        Parallel N-Body – Compute Shader (GPU SIMD )

·        Parallel N-Body – MPI with Multiple computers (Sequential)

·        Parallel N-Body – MPI with Multiple computers (Parallel)

The applications were tested on two different systems, one Intel based and the other AMD.

	CPU Name	Year	CPU Speed	Cores	GPU	NM	Cache
Computer 1 - Home	AMD Phenom II x6 1055T	April 27, 2010	3.25GHz	6	GTX 460	336 CUDA Cores	1GB GDDR5 @ 1800 MHz
Computer 2 – University	Intel i5 2500	Q1'11	3.3 GHz	4	GTX 550 Ti	192 CUDA Cores	1 GB GDD5 @ 1,026MHz

The cluster used for each of the MPI tests were combinations of 2, 4, 8 and 16 computers all with the same configuration as Computer 2 in the above table connected over a 100 Mbit network.

Sequential

The baseline speeds for each computer running the sequential version of the application was as follow:

Serial	1024	2048	4096	8192	16384	32768	65536
Computer 1 (ms)	78	328	1359	5484	22013	88429	357092
Computer 2 (ms)	67.75	250	992.75	3961.5	15839	63843.5	254323

As can be seen in the above results the differences between Computer 1 & 2 are minor and there is no difference between the two as the data size increases. The times from this algorithm will form the base case to compare against the other optimisations later on. It is interesting to note that Computer 1, despite having 6 cores, has no performance increase over Computer 2, this shows clearly that there is much room to make use of the parallel hardware available in the system.

For the following results, speed up shows how the speed of the parallel application ran compared with the sequential version. A speed up of 100% in this case 

Sequential with SIMD

The first optimisation that was tested was the SIMD version of the application. The test results and speed up versus the baseline version are shown below.

SIMD	1024	2048	4096	8192	16384	32768	65536
C1	78	328	1359	5484	22013	88429	357092
C1 (w/ SIMD)	93	375	1527	6077.75	23982	96716	387619
Speed Up	-16%	-13%	-11%	-10%	-8%	-10%	-9%
C2	67.75	250	992.75	3961.5	15839	63843.5	254323
C2 (w/ SIMD)	43.25	168.75	676.25	2694.5	10655	42562.5	170354
Speed Up	57%	48%	47%	47%	49%	50%	49%

As we can see from the above results, on the AMD based Computer 1 there was actually a reduction in performance when using these specific SIMD instructions. Computer 2 on the other hand received a moderate speed boost. Since SIMD in this case is performing 4 operations at the same time it is expected that the maximumm possible speed boost would be 4 times faster. This shows that more work is needed to realise the full potential of SIMD on the CPU for this application.

C++ Threads

These are the results for the application that used just threads by themselves.

C++ Threads	1024	2048	4096	8192	16384	32768	65536
C1	78	328	1359	5484	22013	88429	357092
C1 (C++ Threads)	15	62	265	953	3734	14968	59709
Speed Up	420%	429%	412%	475%	489%	490%	498%
C2	67.75	250	992.75	3961.5	15839	63843.5	254323
C2 (C++ Threads)	19	80.75	278.75	1100.75	4411.75	17523	70323.8
Speed Up	257%	209%	256%	259%	259%	264%	261%

As we can see above, the AMD based CPU, Computer 1, received the biggest speed improvement and managed to surpass the Intel CPU which only had 4 cores. Both CPUs managed to achieve a much higher speed improvement much closer in line with the level of parallelism supported by each CPU. Computer 1 achieves nearly its ideal speed improvement of 6 times whilst computer achieves nearly 4 times.

C++ Threads (with SIMD)

These results relate to the threaded version that was also combined with SIMD to see if much more of a signifcant speed increase could be obtained. In the interests of keeping this article shorter the specific timing values have been omitted and can be found in the appendix.

C++ Threads (with SIMD)	1024	2048	4096	8192	16384	32768	65536
Computer 1
Threads Speed Up	420%	429%	412%	475%	489%	490%	498%
Threads & SIMD Speed Up	222%	393%	415%	433%	427%	423%	416%
Computer 2
Threads Speed Up	257%	209%	256%	259%	259%	264%	261%
Threads & SIMD Speed Up	344%	441%	397%	372%	359%	364%	362%

MPI 

There was a lot of data in the MPI test results and as such these have been omitted. I will post a link to the full report when it is completed so that exact figures can be seen. In the mean time I have plotted a graph below with speed differences. The main point to note for the MPI results was that for the small data sizes it resulted in significant slow down, the more computers thrown at the problem the slower it got. Only at the larger data sizes was a performance increase shown but it shows that MPI would be more effective than the other techniques at the largest of data sizes.

Final Comparisons

There is a lot more data in relation to the rest of the results but they can be found in the actual report.

The table below shows the percentage speed up of each different application over the varying data sets (Although useful, the information relating to the AMD system has not been plotted). Here we can see that the fastest version was indeed the GPU version which was several thousand times faster than the sequential version. Even in comparison to the other techniques it is a mile ahead. Despite this, C++ threads and SIMD manage to make a consistent speed up over all of the data sets. The major point of interest in this example is that the MPI version of the application actually performs significantly worse at smaller data sizes than all of the other applications. It does manage to make a speed up at the highest of data sizes and based on this trend I predict it could gain an even better speed up at larger data sizes.

Figure 1 - Graph of plotted percentage speed up

I wrote this in a bit of a rush so if there are any inaccuracies or inconsistencies or if you simply have a question feel drop me a message and I'll fix them up or get back to you ASAP.

---

Email: markmmiller@hotmail.co.uk
Xbox Live: Dr Death MK 2
Steam: 7thsanctum
Follow @7thsanctum
Origin: 7thsanctum
Youtube: 7thsanctum
Github: 7thsanctum

SIE App Jam Day (2013) - Super Santa Brawl

Apologies for the delayed post but I've had a bunch of project work that needed to be finished which will be discussed later. 

Anyways, two weeks ago on November 30th the Scottish Institute for Enterprise hosted an app jam at Heriot-watt university organised by one of my fellow game dev students who is also acting as the Napier representative for SIE. The main purpose of the app jam is to make some kind of application that might have some form of business potential and other elements that are awarded are things like completeness, originality and how interesting your idea actually is. Naturally, as a game student, I used this chance to instead spend time making a game. If you remember back to one of my previous posts I attempted to also make a game at the same app jam but didn't manage to fully complete it and as such didn't do very well in the scope of the competition. Luckily this time I managed to make a bit of a better and more complete game and won one of the top prizes which were £40 amazon vouchers and a Raspberry Pi with case.

The jam itself lasts around 10 hours over the course of a day. Unity was used to develop the game, as well as this Unity had recently released some new features to support 2D game development and as such I used this as an opportunity to learn how to use them. The theme for the jam was "Christmas" and to keep inline with this theme I investigated some Christmas themed sprite sheets. I found one that had a fairly nice santa sprite taken from the game Daze before Christmas for the NES. The first several hours were spent wrestling with and understanding Unitys new sprite animation system but after a while I managed to get things working, a lot of my understanding of how collisions work with the character as well were learned from the Unity2D tutorial on 2D platforming which showed how to use the new 2D physics system as well.

Figure 1 - The final game

The game itself was based on the likes of Super Smash Bros and involves two players running and jumping around the arena throwing snowballs at each other. To allow multiplayer I set up and used two Xbox 360 controllers. This was the first time I had used controllers for a game as well and Unity itself does not currently support rumble for gamepads so to get this feature I used XInput. Using the right stick the player can aim the direction of the fire balls, fire with the right trigger, jump using A and move with the left stick. If a player is hit with a ball directly they will lose a health point, 4 hits results in a death and the player respawning whilst the other player gains a point. The rumble intensity is modified based on the distance of an explosion to the player so the further away the player is from an exploding ball the lower the intensity versus a direct hit which will cause significant rumble.

Overall I was quite pleased with what I had learned over the 10 hours making this game as it had been a while since I actually made one. More work is needed before this is fully finished and I will need to change many of the art assets but I will do this when I next get a chance.

I took some videos using fraps but I'm currently having problems getting it to actually work. As such the video linked below is an older prototype version and was only what was made within the first few hours of the jam. I will update this once I actually fix my movie maker problems.

---

Email: markmmiller@hotmail.co.uk
Xbox Live: Dr Death MK 2
Steam: 7thsanctum
Follow @7thsanctum
Origin: 7thsanctum
Youtube: 7thsanctum
Github: 7thsanctum

Voxel Engine Update - DirectX

As part of my honours project I have been rejigging the particle engine I made last year to a voxel engine. The plan for this project is to optimise the engine for use with the GPU, investigating the effectiveness of the Geometry shader for rendering cubes and perhaps using other elements such as Computer shaders to provide further speedups.

Currently I have a 64^3 (262144 cubes) data set rendered at a steady 30fps on GTX 550 Ti. This is currently without optimisations. I can increase the total to 128 ^3 or 256^3 successfully but these suffer significant slowdown, resulting in 5fps and less than 1fps which are difficult/impossible to interact with.

The images below show 128*64*64 cubes. The image on the left has some cubes removed to demonstrate that there are cubes below the surface and each coloured dot is an individual cube. Click on the images for higher resolution versions.

I have several things that I need to work on next, namely arrays over 512^3 run out of memory or cannot be defined and as such I will have to find a way to deal with this. After performing several calculations as well many optimisations will have to be performed to achieve a dataset much larger that 512^3, to simply store all of the vertices required for the number of vertices for a 1024^3 grid we would need 128GB. This would be a feat using even HDDs let alone in memory. As such to have a world of 1024^3 we would need to store this info on disc and perhaps load chunks of it into memory.

I also need to get some more interesting volume data sets to render to make it most interesting. Noise or other 3D models etc.

Anyways enjoy these close ups and I will have some more updates in future once I've finished some of my other courseworks.

128*64*64 - 524288 cubes

For the vertices alone we are using approximately 64MB on the GPU, this is being generated for every frame.

---

Email: markmmiller@hotmail.co.uk
Xbox Live: Dr Death MK 2
Steam: 7thsanctum
Follow @7thsanctum
Origin: 7thsanctum
Youtube: 7thsanctum
Github: 7thsanctum

3D Tilt Virtual Reality App - Unity3D

This post is a bit late but I only just realised I never made it!

Last year I worked on a group project developing an application designed for mobiles that was meant to demonstrate a "3D effect", the idea being we could bring 3D virtual reality to the masses via smartphones and gyroscopes. The main inspiration for our client was a video of a ballerina inside of a box. The video can be seen below.

From this vague description we were to research and make our own application that demonstrated a similar style of 3D effect. During the project we went through several different iterations and drastically different ideas before the final product was implemented. The first view versions focused mainly on being a game where you fly around the universe, go to different planets and space stations and witness all sorts of interesting and scripted events. Sadly when we approached the client with what we had made the 3D effect wasn't so good or prominent due to the set up of the scene. This resulted in a big change where we decided to try and create a holographic projector type set up.

A video of the application so far can be scene below:

To get this effect we made use of camera distortion technique known as the offset projection matrix. This is where the camera view frustum is distorted allowing various visual effects to be achieved. A regular view frustum is uniform in shape as can be seen in the image below.

Figure 1 - Example View Frustum

The view frustum in most cases is defined simply by the distance and sizes of the far and near planes, they are usually centre aligned and thus symmetrical giving all the objects in the world the correct appearance. For our phone application the users perspective relative to the phones screen has changed, what we wanted to do in this case was alter the frustum relative to the rotation of the phone so that we maintain the users perspective and distort the objects in a manner which would be correct from their point of view.

Figure 2 - Far plane shifting (I apologise for the use of paint)

In the above image we can see how the far plan must be shifted relative to the users position where the near plane is fixed and still parallel with the far plane. This is required because of the users change in position, simply rotating the camera on it's axis will not achieve the required distortion, feel free to attempt this and you will see exactly what I mean.

The only major problem that was not solved over the course of this project was the drift caused by the gyroscope on the mobile device. This drift meant that when the phone was righted back to it's original position it wouldn't quite be right or perhaps when rotating upon any axis it would detect false movement ruining the illusion if the application was used for too long. For just now we implemented a reset button that allowed the user to reset the view which helped alleviate most of the problem. As well as this I kept meaning to add in more of the application to bring it up to a complete level, the original idea being to create an "educational, hologram viewer" application, this would include information about each object that was shown but this is still a work in progress whilst I am at University.

Anyways thanks for reading. I will upload an APK of the application when I can.

---

Email: markmmiller@hotmail.co.uk
Xbox Live: Dr Death MK 2
Steam: 7thsanctum
Follow @7thsanctum
Origin: 7thsanctum
Youtube: 7thsanctum
Github: 7thsanctum

New term, C++11, Fractals and futures!

It's been a while, I really ought to get to updating this blog more often. It's the new trimester and the beginning of the final year at university though so I should have some interesting things in store for the coming months! The current modules I've been working on are Concurrency and Parallel Systems as well as Management of Software Projects, both have their ups and downs. Aside from that I have my honours project that I will be working over the next several months until April next year which will take up a big bulk of my time. Hopefully I will be able to make some interesting posts as I progress with that.

Anyways enough talk, first up we have a C++11 concurrency project that I've been working on over the past few days.

Mandelbrot Set

As a part of an exercise in understanding futures in the C++11 standard I parallelised the Mandelbrot set. The Mandelbrot set is famous for being used in the generation of the Mandelbrot fractal which can be seen in the image below.

Figure 1 - Mandelbrot Fractal

The generation of a fractal image such as the Mandelbrot above is commonly parallelised and is done so by simply splitting up the image into different section and then assigning the different work loads to different threads. By using std::async we are returned a std::future object instead of a std::thread. The std::future object will eventually hold the value being returned, in this case the pixel values of the image. [C++ Concurrency in Action Practical Multithreading]

int main()
{
 auto num_threads = thread::hardware_concurrency();

 // Calculate the range of pixels each thread will work on
 auto strip_height = dimension / num_threads;

 // Create futures for each thread
 vector<future<vector<float>>> futures;

 // We give each thread the calculation and the data range
 // with which we want it to work on. We also make it 
 // asynchronous so that we get a std::future reference back
 // so that we may retrieve the value we want later
 for(int i = 0; i < num_threads; ++i)
  futures.push_back(async(mandelbrotcalculation, 
     i * strip_height, 
     (i + 1) * strip_height));

 // The results of the calculation
 vector<vector<float>> results;
 // Get the results from the future! 
 // Bear in mind that f.get() can only be called once
 for (auto& f : futures)
  results.push_back(f.get());

 return 0;
}

The code above shows  the main for the application generating the fractals and how we would operate the futures for this mandelbrot generation. Bear in mind instead of creating std::thread objects we are using std::futures which allow us to get the returning value from the thread later. "Mandelbrotcalculation" is simply out function for calculating the colour for a single pixel, the maths of which will be covered in a later post. A more indepth discussion on how it works can be read here on Wolfram Mathworld.

The resulting application still takes some time and I still need to measure timings to see how much faster it is than just calculating everything on a single thread would be but results in the following image.

Figure 2 - Part of the Mandelbrot Rendered

Currently I still need to fix my application so that it renders the whole image rather than just a part but in the course of writing this blog post I have realised partially where I have gone wrong so I will have to get working on that asap.

---

Email : markmmiller@hotmail.co.uk
Xbox Live : Dr Death MK 2
Steam : 7thsanctum
Follow @7thsanctum

DirectX - Geometry Shader (Lot's of cubes and particles!)

Just posting a quick update for my geometry shader experiments. I managed to increase the particle count by a crazy amount to just above 450,000 ! The first program I made to do this created just plain old particles, billboarded towards the camera and with basic blending.

Be sure to click to view in HD

This was pretty cool and I easily managed to get above the 450,000 target. At this amount the system runs smoothly and gets a nice steady 52 FPS. This is at fullscreen 1920*1080 resolution.

Look at those pretty particles!

 After this I played about with multiple emitters and pumping up the emission rate but none of these gave me any satisfaction. Then I remembered  the geometry shader isn't just for particles, I could create any geometry from a single point, so what about cubes? I then did some jiggery pokery inside the shader, spent far too long working out how to create a cube using a triangle strip and voila, the cube demo was born.

Over 450,000 of the finest cubes known to man

Now for this system you would think it would run 6 times slower due to the extra faces, dropping from 52 to about 9 fps. You'd be wrong though, with this system the application still manages an impressive 28 FPS at fullscreen 1920*1080, this is all without any form of instancing, culling or other optimization techniques.

For a bunch of cubes they sure are colourful

Although this program isn't a significant achievement in the realms of computer technology it goes to demonstrate the significant power of the Geometry Shader as well as the GPU. This level of geometry would simply not be possible on the CPU in real time. Anyways, check out some realtime videos of this stuff below, be sure to watch in full HD for the best quality!  Due to the way youtube compresses videos down I had to alter the brightness which is why there is a colour difference with the screenshots above. I really should modify this in shader but that would be sensible.

Also check out some random cool patterns I made below.

---

Email : markmmiller@hotmail.co.uk
Xbox Live : Dr Death MK 2
Steam : 7thsanctum
Follow @7thsanctum