Choice can be a drag. For finding movies in particular, modern interfaces don’t help at a all. At times it feels like navigation, so why not make a map out of it?
As the saying goes, a picture is worth a thousand words. On occasion, I’ll see a great data visualization that just blows me away. At the surface, the data is just reshaped to be useful, but often times a story is told that no one expected.
At times, modern web interfaces are kinda drab because they feel like databases. Not much in the design seperates the UI from the data layout. Espcially when it comes to picking films, there have been too many instances of me just sort of scrolling. “Thank you, next” as Ariana Grande might say.
I decided to to turn this into a realtime rendering problem. There are 65,000 ish films in the kaggle dataset, and I’d like to interactively render all of them in a force directed-graph. The goal is to make exploring the movies like wandering through a map.
But What is a Force Directed Graph
They’re very popular, I’ll have you know.
Basically, it is a particle simulation. Every particle is a node. The nodes repel like electrons (all to all). Linked nodes are treated as springs and attract each other. This is a textbook example of an $ O(N^2) $ problem commonly used in computer science school. There is a high degree of implicit parallelism for both repulsion and attraction, but their differences dictate seperate treatment.
Current Performance Optimizations
Just to get a felling of cost, with an $ O(N^2) $ algorithm disappear 65,000 bodies each computing pairwise forces against each other is billions of interactions each with thousands of instructions.
Barnes Hunt for Replusion
The repulsive force of one node is a sum of its repulsion against all other nodes. Barnes & Hunt propsed using a quadtree to compute forces on collections of neighboring particles rather than every one individually. The technique is very popular and relatively straightforward to impliment.
Given the goal of having it be realtime, it has to run on the gpu. One of the bains of gpu programming is branchy and recusive code. Modern gpus have a hard accelerated means of tree construction and traversal. Though these are for BVHs and ray tracing, recent research as explored their application in particle simulation. I may impliment this at a future date but for now I’m opting for a gpu implimentation of the original algorithm with a quadtree.
Brute Force for Attraction
For attractive forces, things get a little tricky. Unlike the all to all nature of replusion, attractive forces are inheritly sparse and irregular. For simplicity sake, I’ve opted to basically
Right now I’ve sped up vector operations using Swift’s built in SIMD api. Without knowing the knitty gritties of the computer stack, I’m fairly confident in saying that it is inefficient.
The more interesting optimizations come from thinking less like a programmer and more like the hardware.
A SIMD-Centric Design
Modern GPUs don’t really execute one thread at a time. They execute groups of threads together in lockstep. On Apple Silicon GPUs that group consists of 32 lanes, called a SIMD-group (a warp on Nvidia). Normally, hard coding constants is considered bad practice. This is one of the few places where I think it’s justified. Instead of pretending each thread is an independent worker, I structured much of both the simulation and rendering around these groups.
For the particle simulation, this mostly shows up in reductions and broadcasts. Computing the bounding box, for example, doesn’t have every thread writing into shared memory. Each lane computes a local minimum and maximum before the entire SIMD-group reduces those values using simd_min() and simd_max(). Only lane zero performs the final write back to memory.
topLeftX = simd_min(topLeftX);
topLeftY = simd_max(topLeftY);
bottomRightX = simd_max(bottomRightX);
bottomRightY = simd_min(bottomRightY);
if (simd_lane_id == 0) {
topLeft.data[0].x = -0.99f;
topLeft.data[0].y = 0.99f;
bottomRight.data[0].x = 0.99f;
bottomRight.data[0].y = -0.99f;
}
The same pattern appears when computing the center of mass for each Barnes-Hut node. Every lane accumulates mass for a subset of particles, then the SIMD-group combines the partial sums before a single lane writes the result back to memory.
M = simd_sum(M);
R.x = simd_sum(R.x);
R.y = simd_sum(R.y);
if (simd_lane_id == 0 && M > 0.0f) {
R /= M;
totalMass.data[nodeIndex] = M;
centerOfMass.data[nodeIndex] = R;
}
The rendering pipeline leans even harder into this idea.
Instead of asking “How does this edge generate its geometry?” it’s better to ask “How do 32 edges generate their geometry together?”
I wanted the graph to have a neuron-like appearance. Every edge has to blend smoothly into the previous and next edge around a node, so each thread needs information about its neighbors. A traditional vertex shader is a poor fit for this problem because every vertex is processed independently. Recovering neighboring information would require additional memory reads, often loading the same data multiple times.
Object and mesh shaders offer a much more data-centric programming model. Rather than treating vertices as the fundamental unit of work, an entire threadgroup cooperates to generate a small piece of the graph. Each thread is responsible for constructing the geometry for a single half-edge. Interestingly the threadgroup is responsible for lanuching the mesh shader kernel with some magic handled by the scheduler.
[[object]] void objectShader(
constant Buffer& terminations [[buffer(xxx)]],
...
object_data Payload& payload [[payload]],
mesh_grid_properties meshGridProperties,
...
ushort tid [[thread_index_in_threadgroup]])
{
compute_neuron_verticies(data, buffers...);
initialize(&payload, data);
// Dispatch logic
// Number of intermediate sample points on the bezier curve
// (results in numCurveLines + 1 line segments for the curve)
// Max value depends on mesh limits: must satisfy
// threads_per_threadgroup * (numCurveLines + 2) <= 256
// With 32 threads: max numCurveLines = floor(256/32) - 6 = 8
constexpr int lod = 6; // Should be based on zoom
if (tid != 0) return;
// Launches more threadgroups dynamcially based on the lod
// More threadgroups, more triangles, more resolution!
payload.numEdges = batchCount;
payload.lod = lod;
meshGridProperties.set_threadgroups_per_grid(uint3(lod, 1, 1));
}
Before rendering, a compute pass sorts the half-edges by their source node - two buffers each representing the source and target node.
- The source node buffer is grouped by index: A,A,A,A,B,C,C,C,C
- The target nodes are radix sorted by angle to go clockwise.
This means neighboring threads usually process neighboring edges in memory. The result is much better cache locality and, more importantly, it creates opportunities for threads to cooperate directly. Is there a better criterion for sorting? Maybe.
Each lane computes the geometry for its edge—its midpoint, tangent, and perpendicular offset. Instead of loading the previous or next edge from device memory, those values are exchanged directly between neighboring lanes using SIMD shuffle instructions (hence the angle sort pass). The data never leaves the SIMD-group and syronization primitives are avoided outright.
struct Payload {
float2 origin[32];
float2 prevIntersection[32];
float2 nextIntersection[32];
float2 prevMidpoint[32];
float2 midpoint[32];
float2 nextMidpoint[32];
float2 prevJoint[32];
float2 leftJoint[32];
float2 rightJoint[32];
float2 nextJoint[32];
uint gid[32];
uint numEdges;
uint lod;
};
float2 prevMidpoint = simd_shuffle_up(midpoint, 1);
float2 nextMidpoint = simd_shuffle_down(midpoint, 1);
float2 prevJoint = simd_shuffle_up(joint, 1);
float2 nextJoint = simd_shuffle_down(joint, 1);
Of course, this only works while neighboring edges happen to live inside the same SIMD-group. Nodes with a very large degree naturally span multiple groups, while nodes with only a handful of edges leave unused lanes. Whenever a SIMD-group crosses one of these boundaries, the resultant seam demands that the missing neighbor be pulled from memory. Fortunately, as the number of nodes being rendered increases so does the coherency and ulitization.
What’s Next?
At the moment, the priority is getting everything running smoothly. I’ve heard that premature optimization is a dangerous game, and maybe I’ve focused too much effort at this stage.
With the particle simulation and object shaders starting to take shape, the next step is to take on the later stages of the rendering pipeline.
