Leap
Leap is a research remote-memory system that combines majority-based page prefetching with a streamlined Linux RDMA data path.
History, not the whole working set: Leap tracks page-access differences on the paging path, avoiding continuous observation of local-memory hits. Small recent windows are searched first and expanded when no strict majority exists. [1]
Verify the vote: Boyer-Moore produces a candidate even when no value exceeds half the window. A counting pass is needed to establish a majority; the pinned Leap function performs that check. This verifies past frequency, not the next request. [2] [3]
Version boundary: Algorithm 2 describes reuse of the previous trend when no new majority is found and the prefetch window remains nonzero. In the pinned swapin_readahead function, failed detection instead jumps to the aligned-cluster fallback. Do not silently equate this revision with the evaluated implementation. [1] [3]
Resource trade-off: Prefetching spends bandwidth and cache space before demand. Leap adapts its request window using prefetch hits, separately from the history window used to detect a stride. Short-lived irregularity and permanently random access therefore need different responses. [1]
Prototype scope: The README lists Linux 4.4.0/4.11.0 and specific RDMA hardware and driver versions. Remote I/O selection and custom prefetching have separate controls. These are historical prerequisites, not current Linux compatibility claims. [4]
Worked examples: A balanced alternating history has no strict majority. A small recent window can select a new stride even when the full history favors the old one. The deterministic model also gets zero of four predictions right after an unseen phase change. Inputs, denominators and code are downloadable. [5] [6]
Relations
- related
- Infiniswap, Fastswap
Citations
- Al Maruf and Chowdhury. Effectively Prefetching Remote Memory with Leap. USENIX ATC 2020, pp. 843-857; sections 3-6.
- J Strother Moore: The Boyer-Moore Majority Vote Algorithm, author explanation
- Leap authors: trend verification and swapin_readahead fallback, revision 13787f2
- Leap authors: dependencies, code organization and independent runtime controls, revision 13787f2
- Hesela: deterministic majority-window examples and phase-change counterexample
- Hesela: executable educational majority-window model
Sources & caveats
- Source review plus synthetic algorithm examples, not a native Leap run or an RDMA performance replication.
- The model isolates strict-majority detection on complete histories; it does not reproduce kernel initialization, adaptive prefetch sizing, fallback traffic or cache eviction.
- The paper/code distinction identifies two inspected descriptions, not the revision used for the published measurements. No universal speedup or crash-durability guarantee is inferred.