We are going to parallelize a 2D physics engine for games, specifically the LiquidFun extension to Box2D by Google. As LiquidFun/Box2D is a large library, we will be specifically tackling the problem of particle dynamics within the library. We will be implementing basic parallelism by using Intel's Threading Building Blocks and/or openMP.
LiquidFun is a 2D physics engine for game based upon Box2D that includes particlebased fluid simulation. It is an open source written in platform independent C++ by Google, and it has an additional functionality that adds a particle based fluid and soft body simulation to the rigid body functionality in Box2D. As Box2D is a complete 2D physics engine, it has many different functionalities. We chose to focus on the portion of the code that deals with particle dynamics, including velocity, collision, adhesion/cohesion, and other attributes.
We profiled liquidfun’s particle collision library, and measured the time complexity and the usage of functions in the program. Since, our choice of architecture is a multi-core Intel processor, we decided to use Intel’s Threading Building Blocks (Intel TBB). TBB is a C++ template library that take advantage of multi-core processors. We first idenfitied a single for-loop that is safe to process each element concurrently, and replaced it with the template function tbb: :parallel_for to break a iteration space into chunks and runs each chunk on a separate thread.
| Duration | Bryan's Tasks | Ji Hye's Tasks |
|---|---|---|
| April 17th (Thur) + 3 days (April 19th, Sat) | Write more tests that test particle detection functionality and profile it | Parallelize for loops and check performance improvement |
| April 20th (Sun) + 3 days (April 22nd, Tues) | Based on profiling result, find areas where it can be parallelized using pthreads | Create pthreads level parallelism and look for improvements based on SIMD |
| April 23rd (Wed) + 4 days (April 25th, Sat) | Based on profiling result, vectorize using SIMD intrinsic | Vectorize using SIMD |
| April 26th (Sun) + 4 days (April 29th, Tues) | Analyze the performance improvement, and look for algorithmic improvmene that utilizes parallelism. | Implement an algorithm that efficiently parallelize the program |
| April 30th (Wed) + 4 days (May 3rd, Sat) | Write a test case that shows an improvement of performance. | Analyze why the performance of physical simulator was greatly improved by certain parallell implementation |
| May 4th (Sun) + 4 days (May 7th, Wed) | Last minute analysis and programming / check with course staffs | Last minute analysis and programming / check with course staffs |
| May 8th (Thur) + 2 days (May 9th, Fri) | Webpage / post | Prepare for presentation |