Router Heap

HeapInterface

class HeapInterface

Interface to heap used for router optimization.

Subclassed by DAryHeap< D >

Public Functions

virtual void init_heap(const DeviceGrid &grid) = 0

Initializes heap storage based on the size of the device.

Note

This method must be invoked at least once prior to the following methods being called:

  • try_pop

  • add_to_heap

  • push_back

  • build_heap

  • empty_heap

  • is_empty_heap

Parameters:

grid – The FPGA device grid

virtual bool try_pop(HeapNode &heap_node) = 0

Pop the head (smallest element) of the heap. Return true if the pop succeeds; otherwise (if the heap is empty), return false.

Parameters:

heap_node – The reference to a location to store the popped heap node.

virtual void add_to_heap(const HeapNode &heap_node) = 0

Add HeapNode to heap, preserving heap property.

Parameters:

heap_node – The element to add.

virtual void push_back(const HeapNode &heap_node) = 0

Add HeapNode to heap, however does not preserve heap property.

Parameters:

hptr – The element to insert.

virtual void build_heap() = 0

Restore the heap property.

This is useful in conjunction with HeapInterface::push_back when adding multiple heap elements.

virtual bool is_valid() const = 0

Is the heap valid?

virtual void empty_heap() = 0

Empty all items from the heap.

virtual bool is_empty_heap() const = 0

Is the heap empty?

DAryHeap

template<unsigned D>
class DAryHeap : public HeapInterface

Min-heap with D child nodes per parent.

Note

Currently, DAryHeap only has two children, BinaryHeap and FourAryHeap. On small circuits, these heaps have negligible differences in runtime, but on larger heaps, runtime is lower when using FourAryHeap. On Koios large benchmarks, the runtime is ~5% better on FourAryHeap compared to BinaryHeap. This is likely because FourAryHeap has lower tree height, and as we can fit 8 heap node (each is 8 bytes) on a cache line (commonly 64 bytes on modern architectures), each heap operation (the comparison among sibling nodes) tends to benefit from the caches.