Parallel Limit Order Book Simulation

Irene Liu (irenel), Lillian Yu (lyu2)

15-418 Spring 2026


📄 View Full Project Proposal

📄 View Milestone Report

📄 View Final Paper

📄 View Week 1 Notes

📄 View Week 2 Notes

📄 View Week 3 Notes

📄 View Week 4 Notes

📄 View Week 5 Notes

Detailed Schedule

✅ = done    ☑️ = in progress    ✔️ = planned

Task Who Week 1
(03/24–03/31)		 Week 2
(03/31–04/07)		 Week 2.5
(04/07–04/14)		 Week 3
(04/14–04/18)		 Week 3.5
(04/18–04/22)		 Week 4
(04/22–04/25)		 Week 4.5
(04/25–04/28)		 Week 5
(04/28–04/30)
Sequential LOB (LimitOrderBook, Order, Types.h) Combined ✅
Order generator (OrderGenerator, GeneratorConfig) Lillian ✅
Sequential MatchingEngine + main.cpp driver Lillian ✅
Golden-trace harness (make baseline / make verify) Lillian ✅
CoarseGrainedLimitOrderBook (mutex wrapper) Irene ✅
CoarseGrainedMatchingEngine + per-ticker pthread pool Irene ✅
Expand to 16 tickers, add --engine / --parallel / --threads CLI Irene ✅
scripts/bench_lob.sh + make bench Combined ✅
Milestone report, preliminary results on GHC Combined ✅
Bottleneck analysis (Amdahl partition, bookForMut mutex) Combined ✅
Fix serial partition: index-based sharding (no OrderMessage copies) Lillian ✅
Fix drainShard: cache book pointer once per shard, inline dispatch Irene ✅
Profile coarse benchmarks at 5M orders, verify 2.5–3× Combined ✅
Write script to profile coarse benchmarks at 100k/500k/5M-message for 3/8/16 tickers Irene ✅
Design fine-grained locking strategy (per-price-level vs RW lock vs CAS) Combined ✅
Implement FineGrainedLimitOrderBook: per-level locks for non-crossing adds Irene ✅
Implement fine-grained matching: range-lock or level-walk protocol for crossing orders Lillian ✅
Fine-grained cancel: O(1) removal under level lock + global id-index lock Irene ✅
FineGrainedMatchingEngine + wire into main.cpp (--engine fine) Lillian ✅
Correctness: make verify for fine-grained path (same golden) Combined ✅
Profile fine-grained on GHC: perf stat, cache misses, lock contention Combined ✅
Pad data structures to avoid false sharing (cache-line alignment on PriceLevel) Irene ✅
Evaluate under skewed workloads (e.g. 1 hot ticker + 15 cold) Lillian ✅
Measure crossing rate vs non-crossing rate to explain intra-book parallelism Combined ✅
[STRETCH] Batching: group independent non-crossing orders before matching Combined ✅
[STRETCH] Lock-free FIFO per level + CAS on best-price pointer Combined ✅
Final benchmarks: sweep 1/2/4/8 threads × sequential/coarse/fine × 500k/5M Combined ✅
Generate speedup charts + throughput bar graphs for poster Lillian ✅
Write final report Combined ✅
Poster preparation + session Combined ✅