ClubHeap: A High-Speed and Scalable Priority Queue for Programmable Packet Scheduling
summary
ClubHeap implements a hardware-friendly clustered heap that achieves a CPR of one so it can issue a push+pop every cycle and effectively schedule a flow each clock, claiming about 3x throughput vs BMW tree at similar FPGA resource cost. An FPGA prototype validates the design, shows up to 70% SRAM savings when M=16, and lets K tune a frequency/resource tradeoff (recommend K=2–16). It targets PIFO-style schedulers, uses on-chip SRAM only, and omits DR‑PIFO/PIEO support.
AI-written summary · about
chapters (11)
- 0:00ClubHeap introduction
- 2:11Pyo priority queues
- 3:38Evaluating throughput and scalability
- 5:47Hardware heaps scalability
- 6:48Frequency versus throughput
- 8:11Heap data dependency
- 10:17SRAM optimization with clustering
- 11:21ClubHeap vs BMW tree vs BBQ
- 12:26ClubHeap scalability
- 12:49Limitations and future work
- 13:09Q&A
related talks
18mBBQ: A Fast and Scalable Integer Priority Queue for Hardware Packet Scheduling
13mSifter: An Inversion-Free and Large-Capacity Programmable Packet Scheduler
22mProgrammable Calendar Queues for High-speed Packet Scheduling
22mEiffel: Efficient and Flexible Software Packet Scheduling
16mGearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair Queuing
17mThemis: Scheduling-Aware Buffer Management for HBM-Based Hybrid Buffers
25mApproximating Fair Queueing on Reconfigurable Switches
23mSP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority Queues