The Barnes-Hut traversal on the integrated GPU, which is the hardest thing this project asks of the device. More...

#include <cstdint>
#include <memory>
#include <span>
#include <string_view>
#include "orrery/backend/executor.hpp"
#include "orrery/backend/sycl_device.hpp"
#include "orrery/backend/worker_statistics.hpp"
#include "orrery/core/softening.hpp"
#include "orrery/core/types.hpp"
#include "orrery/core/vec3_span.hpp"
#include "orrery/solvers/force_solver.hpp"
#include "orrery/solvers/interaction_count.hpp"
#include "orrery/solvers/octree.hpp"

Classes
struct	orrery::solvers::SyclTreeTimings
	Where one force evaluation spent its time. More...
class	orrery::solvers::SyclTreeSolver
	Barnes-Hut with the traversal on a SYCL device. More...

Enumerations
enum class	orrery::solvers::TreeTraversal : std::uint8_t { kIndependent , kCoherent }
	Which of the two traversals the device runs. More...

Functions
constexpr std::string_view	orrery::solvers::to_string (TreeTraversal traversal) noexcept

Detailed Description

The Barnes-Hut traversal on the integrated GPU, which is the hardest thing this project asks of the device.

Phase 9 put direct summation on the GPU and it went well, for a reason that is worth stating before this file explains why it does not apply here: every work-item did identical work in identical order over identical memory. A wide SIMD machine is built for exactly that. A tree walk is the opposite. Two neighbouring particles agree about most of the tree and disagree about the part of it nearest them, so their walks visit overlapping but different sets of nodes, in different numbers, for different lengths of time. Section 7 of the implementation plan calls this the phase where naive GPU ports fail, and the mechanism of that failure is the subject of this file.

What actually goes wrong

A GPU does not execute work-items independently. It executes them in sub-groups of a fixed width, 32 on this device, which share one instruction pointer. When the lanes of a sub-group take different branches the hardware runs both sides and masks off the lanes that did not want each, so the cost of a divergent branch is the sum of its sides rather than the maximum. A walk written as though each work-item were a thread therefore does not cost what its own node count suggests. It costs what the whole sub-group's node counts add up to, because every lane is switched off while the others finish the nodes it did not need, and switched on again while they wait for the nodes it did.

That cost is already being paid. The lanes are already stepping through the union of their walks. What the independent walk does not do is use the time: a lane sitting masked out during another lane's node is a lane doing nothing.

The mitigation

So the sub-group walks the tree together. One node index for the whole sub-group, advanced by agreement: the group descends into a node when any lane in it needs to, and skips the node's subtree when none does. Each lane then decides for itself what to do at the node the group has arrived at, and a lane that accepted an ancestor of that node contributes nothing until the walk leaves the subtree it accepted.

The trade is exact and measurable in both directions. Against it, the sub-group visits the union of its lanes' walks, so a lane sees nodes its own walk would have skipped and the total node visits rise. In favour of it, the visits are the ones the hardware was executing under a mask anyway, and the walk now has one instruction stream rather than 32 interleaved ones: the acceptance test is evaluated for every lane at once, the node is read from memory once for the whole sub-group instead of 32 times from 32 addresses, and the escape pointer is followed once.

Both halves are measured rather than argued. docs/performance/sycl_tree.md reports the node visits each traversal makes and the time each takes, and the interesting result is that the coherent walk is faster while visiting more nodes.

What is not given up

The answer. This is the part that separates the scheme here from the published warp-coherent traversals it otherwise resembles, and ADR-0029 sets it out: those make the whole warp descend when any lane needs to and let the lanes that would have accepted the cell descend with it, which computes a different, more accurate sum whose value depends on which particles shared a warp. This traversal masks instead. A lane that accepts a cell adds the cell's term and then contributes nothing until the group leaves that subtree, so each target is summed over exactly the nodes its own walk would have visited, in the same order.

The consequence is that the two traversals in this file are the same function of the input, and tests/solvers/sycl_tree_solver_test.cpp requires them to agree. It also means the interaction counts reported here can be required to equal the CPU solver's exactly, which they are, and that is a far stronger statement about the device walk than any tolerance on an acceleration: it says the device visited the same cells and summed the same pairs, not merely that it arrived somewhere nearby.

Where the tree comes from

The host builds it, exactly as solvers/barnes_hut_solver.hpp does and with the same code. ADR-0028 records why construction stays on the CPU and only the traversal moves, the short version being that the traversal is where the time is and construction on this hardware is not the bottleneck it is on a discrete part.

The staging that ADR-0027 introduced for Phase 9 mostly disappears here, and that is a genuine architectural dividend rather than an optimisation. A tree solver already has to copy the particles into the tree's sorted order before it can walk anything, and already has to scatter the accelerations back to the caller's order afterwards. This solver performs that gather straight into shared memory and that scatter straight out of it, so the copy the GPU needs is the copy the algorithm needed anyway. What remains is the node array, which is O(N / leaf capacity) rather than O(N) and is measured beside everything else.

Enumeration Type Documentation

◆ TreeTraversal

enum class orrery::solvers::TreeTraversal : std::uint8_t

strong

Which of the two traversals the device runs.

Both are kept and both are correct. The independent walk is not dead code left behind: it is the baseline the coherent walk is measured against, and a mitigation whose baseline has been deleted is a mitigation nobody can check. Section 7 of the implementation plan asks for the divergence mitigation to be measured rather than assumed, and this enumeration is what makes the measurement a matter of running the same benchmark twice.

Enumerator

kIndependent

One work-item per target, each following its own node index.

The port a first attempt writes: the CPU walk with the loop over targets replaced by a work-item. Correct, and slower than it looks, for the reason this file opens with.

kCoherent

One node index per sub-group, advanced by agreement.

Classes

Enumerations