Lune

MICRO2021Top-tier venue

PDede: Partitioned, Deduplicated, Delta Branch Target Buffer

Niranjan K. Soundararajan, Peter Braun, Tanvir Ahmed Khan, Baris Kasikci, Heiner Litz, Sreenivas Subramoney

Abstract

Due to large instruction footprints, contemporary data center applications suffer from frequent frontend stalls. Despite being a significant contributor to these stalls, the Branch Target Buffer (BTB) has received less attention compared to other frontend structures such as the instruction cache. While prior works have looked at enhancing the BTB through more efficient replacement policies and prefetching policies, a thorough analysis into optimizing the BTB’s storage efficiency is missing. In this work, we analyze BTB accesses for a large number (100+) of frontend bound applications to understand their branch target characteristics. This analysis, provides three significant observations about the nature of branch targets: (1) a significant number of branch instructions have the same branch target, (2) a significant number of branch targets share the same page address, and (3) a significant percentage of branch instructions and their targets are located on the same page. Furthermore, we observe that while applications’ address spaces are sparsely populated, they exhibit spatial locality within and across pages. We refer to these multi-page addresses as regions and we show that applications traverse a significantly smaller number of regions than pages. Based on these insights, we propose PDede, an efficient re-design of the BTB micro-architecture that improves storage efficiency by removing redundancy among branches and their targets. PDede introduces three techniques, (a) BTB Partitioning, (b) Branch Target Deduplication, and (c) Delta Branch Target Encoding to reduce BTB miss induced frontend stalls. We evaluate PDede across 100+ applications, spanning several usage scenarios, and show that it provides an average 14.4% (up to 76%) IPC speedup by reducing BTB misses by 54.7% on average (and up to 99.8%).

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

14 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Twig: Profile-Guided BTB Prefetching for Data Center Applications cites Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications
  • Twig: Profile-Guided BTB Prefetching for Data Center Applications cites Classifying Memory Access Patterns for Prefetching
  • Twig: Profile-Guided BTB Prefetching for Data Center Applications cites Divide and Conquer Frontend Bottleneck
  • Twig: Profile-Guided BTB Prefetching for Data Center Applications cites I-SPY: Context-Driven Conditional Instruction Prefetching with Coalescing
  • Thermometer: profile-guided btb replacement for data center applications cites Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications
  • Thermometer: profile-guided btb replacement for data center applications cites Twig: Profile-Guided BTB Prefetching for Data Center Applications
  • Thermometer: profile-guided btb replacement for data center applications cites Classifying Memory Access Patterns for Prefetching
  • Thermometer: profile-guided btb replacement for data center applications cites Divide and Conquer Frontend Bottleneck
  • Thermometer: profile-guided btb replacement for data center applications cites I-SPY: Context-Driven Conditional Instruction Prefetching with Coalescing
  • UDP: Utility-Driven Fetch Directed Instruction Prefetching cites Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications
  • UDP: Utility-Driven Fetch Directed Instruction Prefetching cites Twig: Profile-Guided BTB Prefetching for Data Center Applications
  • UDP: Utility-Driven Fetch Directed Instruction Prefetching cites Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications
  • UDP: Utility-Driven Fetch Directed Instruction Prefetching cites Divide and Conquer Frontend Bottleneck
  • UDP: Utility-Driven Fetch Directed Instruction Prefetching cites I-SPY: Context-Driven Conditional Instruction Prefetching with Coalescing
  • Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications cites Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications
  • Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications cites Twig: Profile-Guided BTB Prefetching for Data Center Applications
  • Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications cites Thermometer: profile-guided btb replacement for data center applications
  • Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications cites OCOLOS: Online COde Layout OptimizationS
  • OCOLOS: Online COde Layout OptimizationS cites Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications
  • Whisper: Profile-Guided Branch Misprediction Elimination for Data Center Applications cites I-SPY: Context-Driven Conditional Instruction Prefetching with Coalescing
  • OCOLOS: Online COde Layout OptimizationS cites Ripple: Profile-Guided Instruction Cache Replacement for Data Center Applications
  • OCOLOS: Online COde Layout OptimizationS cites Twig: Profile-Guided BTB Prefetching for Data Center Applications
  • OCOLOS: Online COde Layout OptimizationS cites Thermometer: profile-guided btb replacement for data center applications
  • OCOLOS: Online COde Layout OptimizationS cites I-SPY: Context-Driven Conditional Instruction Prefetching with Coalescing
  • I-SPY: Context-Driven Conditional Instruction Prefetching with Coalescing cites Classifying Memory Access Patterns for Prefetching
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers14

  1. Twig: Profile-Guided BTB Prefetching for Data Center ApplicationsTanvir Ahmed Khan, Nathan Brown, Akshitha Sriraman, Niranjan K. Soundararajan et al.MICRO 2021 · 33 citations
  2. Whisper: Profile-Guided Branch Misprediction Elimination for Data Center ApplicationsTanvir Ahmed Khan, Muhammed Ugur, Krishnendra Nathella, Dam Sunwoo et al.MICRO 2022 · 25 citations
  3. Thermometer: profile-guided btb replacement for data center applicationsShixin Song, Tanvir Ahmed Khan, Sara Mahdizadeh-Shahri, Akshitha Sriraman et al.ISCA 2022 · 23 citations
  4. OCOLOS: Online COde Layout OptimizationSYuxuan Zhang, Tanvir Ahmed Khan, Gilles Pokam, Baris Kasikci et al.MICRO 2022 · 14 citations
  5. UDP: Utility-Driven Fetch Directed Instruction PrefetchingSurim Oh, Mingsheng Xu, Tanvir Ahmed Khan, Baris Kasikci et al.ISCA 2024 · 12 citations

Builds on6

  1. Classifying Memory Access Patterns for PrefetchingGrant Ayers, Heiner Litz, Christos Kozyrakis, Parthasarathy RanganathanASPLOS 2020 · 83 citations
  2. I-SPY: Context-Driven Conditional Instruction Prefetching with CoalescingTanvir Ahmed Khan, Akshitha Sriraman, Joseph Devietti, Gilles Pokam et al.MICRO 2020 · 37 citations
  3. Ripple: Profile-Guided Instruction Cache Replacement for Data Center ApplicationsTanvir Ahmed Khan, Dexin Zhang, Akshitha Sriraman, Joseph Devietti et al.ISCA 2021 · 33 citations
  4. Twig: Profile-Guided BTB Prefetching for Data Center ApplicationsTanvir Ahmed Khan, Nathan Brown, Akshitha Sriraman, Niranjan K. Soundararajan et al.MICRO 2021 · 33 citations
  5. Divide and Conquer Frontend BottleneckAli Ansari, Pejman Lotfi-Kamran, Hamid Sarbazi-AzadISCA 2020 · 28 citations

Related papers

  1. A Storage-Effective BTB Organization for ServersTruls Asheim, Boris Grot, Rakesh KumarHPCA 2023 · 12 citations
  2. Skia: Exposing Shadow BranchesChrysanthos Pepi, Bhargav Reddy Godala, Krishnam Tibrewala, Gino A. Chacon et al.ASPLOS 2025 · 2 citations
  3. Branch Target Buffer OrganizationsArthur Perais, Rami SheikhMICRO 2023 · 8 citations
  4. AVM-BTB: Adaptive and Virtualized Multi-level Branch Target BufferYunzhe Liu, Xinyu Li, Tingting Zhang, Tianyi Liu et al.ISCA 2024 · 6 citations
  5. Alternate Path μ-op Cache PrefetchingSawan Singh, Arthur Perais, Alexandra Jimborean, Alberto RosISCA 2024 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines