I tackled this problem recently using some of these answers as a starting point. The most helpful thing to keep in mind is that boids are a sort of simple n-body simulation: each boid is a particle that exerts a force on its neighbors.
I found the Linde paper difficult to read; I suggest instead looking at S.J. Plimpton's "Fast Parallel Algorithms for Short-Range Molecular Dynamics", which Linde referenced. Plimpton's paper is far more readable and detailed with better figures:
In a nutshell, atom-decomposition methods assign a subset of atoms permanently to each processor, force-decomposition methods assign a subset of pairwise force computations to each proc, and spatial-decomposition methods assign a sub-region of the simulation box to each proc.
I recommend you try AD. It's the easiest to understand and implement. FD is very similar. Here is nVidia's n-body simulation with CUDA using FD, which should give you a rough idea of how tiling and reduction can help drastically surpass serial performance.
SD implementations are generally optimizing techniques, and require some degree of choreography to implement. They're almost always faster and scale better.
This is because AD/FD requires building a "neighbor list" for each boid. If every boid needs to know the position of its neighbors, the communication between them is O(n²). You can use Verlet neighbor lists to reduce the size of the area each boid checks, which allows you to rebuild the list every few timesteps instead of every step, but it's still O(n²). In SD, each cell keeps a neighbor list, whereas in AD/FD every boid has a neighbor list. So instead of every boid communicating with each other, every cell communicates with each other. That reduction in communication is where the speed increase comes from.
Unfortunately the boids problem sabotages SD slightly. Having each processor keep track of a cell is most advantageous when the boids are somewhat evenly distributed across the entire region. But you want boids to cluster together! If your flock is behaving properly, the vast majority of your processors will be ticking away, exchanging empty lists with each other, and a small group of cells will end up performing the same calculations AD or FD would.
To deal with this, you can either mathematically tune the size of cells (which is constant) to minimize the number of empty cells at any given time, or use the Barnes-Hut algorithm for quad-trees. The BH algorithm is incredibly powerful. Paradoxically, it's extremely difficult to implement on parallel architectures. This is because a BH tree is irregular, so parallel threads will traverse it at wildly varying speeds, resulting in thread divergence. Salmon and Dubinski have presented orthogonal recursive bisection algorithms to distribute quadtrees evenly among processors, which must be restated iteratively for most parallel architectures.
As you can see, we're clearly in the realm of optimization and black magic at this point. Again, try reading Plimpton's paper and see if it makes any sense.