SoberDSE: Sample-Efficient Design Space Exploration via Learning-Based Algorithm Selection

The paper introduces SoberDSE, a learning-based framework that addresses the limitations of single-algorithm Design Space Exploration in High-Level Synthesis by automatically selecting the most effective algorithm for specific benchmarks based on their characteristics, thereby significantly outperforming both state-of-the-art heuristic and learning-based methods while demonstrating superior accuracy in small-sample scenarios.

The Gist

The Big Problem: The "One Size Fits None" Dilemma

Imagine you are a chef trying to cook the perfect meal. You have a massive pantry (the Design Space) filled with thousands of ingredients and spices (the parameters). Your goal is to create a dish that is delicious, healthy, and cheap all at once (the Power, Performance, and Area or PPA metrics).

To find the perfect recipe, you have to try different combinations. This process is called Design Space Exploration (DSE).

However, the number of possible recipes is so huge that trying them all would take longer than the age of the universe. So, chefs use "smart shortcuts" (algorithms) to guess which recipes might be good.

The Catch:
The researchers discovered a frustrating truth: No single shortcut works for every dish.

• The "Simulated Annealing" shortcut is amazing for making a steak, but terrible for baking a cake.
• The "Genetic Algorithm" is great for soup, but fails at making a salad.

This is known as the "No Free Lunch" theorem. In the world of computer chips, if you pick just one "best" algorithm to design all chips, you will inevitably fail on some of them.

The Solution: The "SoberDSE" Sommelier

The authors of this paper, Lei Xu and his team, realized that instead of trying to invent a "super-algorithm" that does everything perfectly, we should build a smart waiter (or a Sommelier).

They named their system SoberDSE. Think of it as a highly trained sommelier who looks at your specific dish (the chip design) and says, "Ah, for this specific type of cake, you should use the 'Simulated Annealing' recipe. But for that soup, use the 'Genetic Algorithm'."

SoberDSE doesn't cook the meal itself; it just knows which expert chef to call for the specific job at hand.

How It Works: The "Hybrid Brain"

The tricky part is that the team didn't have a huge library of past dishes to learn from (limited data). If they just used a standard computer brain (Supervised Learning) to guess the chef, it might overthink and get confused. If they let the computer learn by trial and error (Reinforcement Learning) from scratch, it would take too long and waste time.

So, they built a Hybrid Brain with two layers:

1. The Experienced Intern (Supervised Learning):
   First, the system looks at the "ingredients" of the chip (its code structure) and makes a quick, educated guess: "I think 70% of the time, Chef A is the best for this." This gives the system a head start.

2. The Master Taster (Reinforcement Learning):
   Then, a smart AI agent takes that guess and refines it. It interacts with the environment, learns from its mistakes, and adjusts the recommendation. Because the "Intern" gave it a good starting point, the "Master Taster" learns much faster and doesn't get stuck in a rut.

The Results: Faster and Smarter

The team tested SoberDSE on 20 different types of chip designs (benchmarks). Here is what happened:

• Accuracy: It was much better at picking the right chef than standard computer models. It improved accuracy by about 35% compared to old methods.
• Performance: When they let SoberDSE pick the chef, the resulting chips were 5.7 times better than using the best "one-size-fits-all" heuristic methods.
• Speed: It found these great solutions 4.2 times faster than other learning-based methods.

The Takeaway

Before this paper, the industry was trying to build a "Swiss Army Knife" that could do everything perfectly. The authors realized that's impossible.

Instead, SoberDSE is like a smart dispatcher. It analyzes the problem, checks its "mental database" of what works for similar problems, and instantly assigns the right tool to the job.

In short: You don't need to invent a new super-tool to solve every problem. You just need a smart system that knows which of your existing tools is the right one for the job. SoberDSE is that smart system, and it saves a massive amount of time and money in designing computer chips.

Technical Summary

1. Problem Statement

High-Level Synthesis (HLS) is a critical Electronic Design Automation (EDA) technology that converts high-level code into hardware circuits. A major bottleneck in HLS is Design Space Exploration (DSE), which aims to find the optimal hardware configuration (balancing Power, Performance, and Area - PPA) under specific constraints.

• The Challenge: The design space grows exponentially with the number of optimization directives (pragmas), making exhaustive search computationally prohibitive.
• The Limitation of Current Methods: While various heuristic (e.g., NSGA-II, Simulated Annealing) and Reinforcement Learning (RL) algorithms exist to accelerate DSE, the No Free Lunch (NFL) theorem applies: no single algorithm consistently outperforms all others across every problem instance.
• The Gap: Existing approaches often rely on a single algorithm for all benchmarks or require massive training datasets. There is a lack of an automated mechanism to select the best DSE algorithm for a specific benchmark, especially when training data is scarce (small-sample scenarios).

2. Methodology: The SoberDSE Framework

The authors propose SoberDSE, a framework that treats DSE as an Algorithm Selection problem. Instead of designing a new DSE algorithm, SoberDSE analyzes the characteristics of a specific benchmark and recommends the most suitable existing DSE algorithm from a suite.

The framework consists of five key components:

A. Dataset Generation

• Algorithm Suite: Implements 10 DSE algorithms: 7 Heuristics (NSGA-II, SA, ACO, PSO, Lattice, HGBO-DSE, MOEDA) and 3 RL methods (Actor-Critic, Policy Gradient, QL-MOEA).
• Evaluation: Uses Average Distance to Reference Set (ADRS) as the performance metric. Lower ADRS indicates a Pareto front closer to the optimal reference.
• Data: Benchmarks are evaluated using a pre-trained Quality of Result (QoR) prediction model (ECoGNN) to avoid time-consuming hardware simulations during the training phase.

B. Benchmark Feature Graph Generator (BFGG)

• To capture the structural characteristics of benchmarks, source code is converted to an Intermediate Representation (IR) via LLVM.
• ProGraML is used to generate a Control and Data Flow Graph (CDFG).
• Enhancement: HLS pragmas are inserted as specific nodes (icmp nodes) into the graph to create a Benchmark Feature Graph (BFG), ensuring the model understands optimization directives.

C. Collaborative Recommendation Model (The Core Innovation)

To address the small-sample learning challenge (limited number of real-world FPGA benchmarks), SoberDSE employs a hybrid approach combining Supervised Learning (SL) and Reinforcement Learning (RL):

1. Supervised Initialization: A Graph Neural Network (GNN) encoder processes the BFG to generate graph embeddings ($h_G$). An MLP head predicts the probability distribution of the best algorithm. This model is trained first to provide a "warm start."
2. RL Refinement (PPO): The probabilities from the supervised model ($p_{sup}$) are concatenated with the graph embeddings to form the state ($s_t$) for a Proximal Policy Optimization (PPO) agent.
   • Actor: Selects the algorithm based on the state.
   • Critic: Estimates the value of the state.
   • Reward: Based on the deviation of the selected algorithm's ADRS from the ground-truth best ADRS.
3. Synergy: The supervised model prevents the RL agent from starting with random guesses (improving sample efficiency), while the RL agent fine-tunes the selection to avoid overfitting and local optima common in pure supervised learning.

D. Inference

During inference, the framework takes a new benchmark, generates its BFG, and uses the trained hybrid model to recommend the optimal DSE algorithm. The recommended algorithm is then executed to generate the final Pareto-optimal solutions.

3. Key Contributions

1. Empirical Validation of NFL in DSE: The authors implemented 10 state-of-the-art DSE algorithms and experimentally proved that no single algorithm dominates all benchmarks, necessitating an automated selection mechanism.
2. Hybrid Recommendation Paradigm: Proposed a novel Supervised-RL collaborative model. This approach specifically targets the "small-sample" problem in FPGA design by using supervised learning to initialize the RL agent's state, significantly boosting sample efficiency and generalization.
3. Feature-Rich Representation: Developed a method to generate feature graphs that incorporate both code structure (CDFG) and HLS-specific directives (pragmas), providing a richer input for the selection model.
4. Performance Gains: Demonstrated that selecting the right algorithm is more effective than designing a new one, achieving superior results with less computational overhead.

4. Experimental Results

The framework was evaluated on 20 training benchmarks and 9 diverse inference benchmarks (including large-scale designs like correlation with $10^{11}$ design space).

• Recommendation Accuracy:
  • SoberDSE outperformed traditional classification models (Random Forest, XGBoost, SVM, K-NN) by an average of 35.57% in accuracy.
  • It significantly outperformed the Supervised-Only model (SFM), proving the necessity of the RL component for small-sample generalization.
• DSE Performance (ADRS):
  • Compared to the best heuristic baselines (Lattice, HGBO-DSE, MOEDA), SoberDSE improved performance by 81.32%, 78.61%, and 83.24% respectively.
  • Compared to SOTA RL-based DSE methods (IRONMAN-PRO, QL-MOEA), SoberDSE showed improvements of 76.31%, 54.81%, and 75.29%.
  • Overall, SoberDSE achieved up to 5.7x improvement over heuristic methods and 4.2x over learning-based methods.
• Runtime Efficiency:
  • SoberDSE reduced total runtime by up to 75.63% compared to slower baselines (e.g., PG took 3538s vs. SoberDSE's 862s), while maintaining competitive speed with the fastest heuristics.

5. Significance

SoberDSE represents a paradigm shift in EDA optimization. Instead of the traditional approach of designing increasingly complex, monolithic DSE algorithms, it advocates for Algorithm Selection.

• Practical Impact: It solves the "No Free Lunch" limitation by automating the selection of the right tool for the job, ensuring optimal PPA trade-offs for any given hardware kernel.
• Data Efficiency: By successfully applying RL in a data-scarce environment through hybrid learning, it offers a viable path for deploying AI-driven EDA tools where large-scale labeled datasets are unavailable.
• Scalability: The framework is modular; as new DSE algorithms are developed, they can be added to the suite, and SoberDSE can learn to select them without re-engineering the core selection logic.