Social Force Modelling

Description #

Project for Advanced Systems Lab, where the entire grade rests on how fast you can make one numerical kernel run on a single core. Ours was the social force model, which simulates pedestrian crowds by treating each person as a particle driven by attractive and repulsive “social” forces from their destination, from other pedestrians and from obstacles.

In a team of four we started from a straightforward baseline implementation and worked through successive optimisation rounds:

• Cost analysis — counting flops and establishing a roofline to know what the achievable ceiling actually was.
• Scalar optimisation — strength reduction on the force kernels, hoisting and precomputing invariants, replacing transcendental calls with cheaper approximations.
• Memory layout — moving from array-of-structs to struct-of-arrays and blocking the interaction loop so the working set stays in cache.
• Vectorisation — hand-written AVX intrinsics for the inner loops, with the data layout reshaped so loads stay aligned and contiguous.

Each version was benchmarked against the baseline across a range of crowd sizes, which is where most of the interesting results came from — the fastest variant depends on whether the working set still fits in L2.

(Source code not provided due to university policy)