Large-Scale Particle Systems on PlayStation 3
By: Dave Loyd
Supervisor: Anton Ephanov
Masters of Interactive Technology degree conferred July 12, 2008
Thesis / Project completed: July 11, 2008

This thesis investigates the use of the Cell processor in the PlayStation 3 (PS3) to properly depth-sort particles in large-scale particle systems. Using PS3 Linux for the development platform, multiple sorting methods are explored to test efficiency for up to 500,000 particles in existence simultaneously.

Visibility sorting is broken up into two separate phases, using both the Power Processor Element (PPE) and the Synergistic Processor Elements (SPEs) in the Cell processor. On the PPE, a bucket sort algorithm is used to loosely sort the particles into a single array of data. This workload is then split into chunks and dispatched in parallel to the SPEs, where the second sorting phase is completed. In this second phase, both quick sort and Odd-Even Merge sort are tested for performance sorting the particles. Odd-Even Merge sort is then tested using only two or four passes to compare against a full sort.

The results demonstrate that sorting large numbers of particles is possible, though bottlenecks do exist. In particular, using more efficient algorithms on the SPEs can result in large speed gains, but ultimately the bucket sort performed on the PPE becomes the slowest component.

Download entire thesis (.pdf)