From 6c000c39dde57233df233c8e448dd189958ae013 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 28 Dec 2025 23:24:59 +0100 Subject: Update doc --- doc/h48.md | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'doc') diff --git a/doc/h48.md b/doc/h48.md index 6015b2a..694a07d 100644 --- a/doc/h48.md +++ b/doc/h48.md @@ -315,6 +315,20 @@ inverse position*, then the coordinate on the normal position has not changed. Thus if we keep track of the last computed pruning value, we can reuse it and avoid an expensive table lookup. +### Pruning pipeline and prefetching + +To improve the memory access pattern and exploit +[prefetching](https://en.wikipedia.org/wiki/Cache_prefetching) +opportunities, we don't expand each neighbor one by one in the +pruning phase. Instead, we employ a *pruning pipeline*, where we +first compute the cube and inverse position for each neighbor, and +then we proceed through a series of stages, at each of which we +compute some prune off some nodes and we pre-compute the data +necessary for the next step. + +This pipeline-based strategy gives an speedup of around 25%. +Adding manual prefetching, we get an additional 20% speedup. + ### Other optimizations The H48 solver uses various other optimizations. -- cgit v1.3