Multi-objective Optimization in CPU Design Space Exploration: Attention is All You Need

The attention mechanism has become one of the most crucial concepts in deep learning. Inspired by human biological systems, which focus on distinctive and relevant details when processing large amounts of information, attention mechanisms allow models to prioritize important data instead of treating every input equally. This selective focus enhances the efficiency and effectiveness of handling complex data.

A typical attention layer in a neural network dynamically identifies the most relevant parts of the input. The attention score is defined as:

It operates using three key vectors: query (Q), key (K), and value (V). The attention mechanism calculates a score by comparing the query and key vectors, which are normalized via a softmax function to produce attention weights. These weights then compute a weighted sum of the value vectors, emphasizing the most critical information. This process is especially effective in self-attention, where each input element attends to all others, and in multi-head attention, which captures different aspects of the input through multiple attention heads. Attention layers are foundational in models like transformers (transformer, ), enabling flexible and efficient learning of dependencies within sequences.

DSE is a critical technique in the optimization and design process, primarily used to identify and analyze various design options within CPU design (PPA1, ; PPA2, ; PPA3, ; PPA4, ). Its goal is to systematically explore all possible design alternatives to find the optimal or near-optimal solutions that meet specific design requirements and constraints (ArchExplorer, ; MoDSE, ; BOOMExplorer, ; ActBoost, ; wangduo1, ; wangduo2, ).

To expedite the process, prevailing DSE frameworks adhere to the fundamental principles of BO (MoDSE, ; BOOMExplorer, ; ActBoost, ; Archranker, ). BO leverages a surrogate model that serves as a predictive tool, approximating the underlying objective function (GPR, ; random_forest, ; ensemble_learning, ). Additionally, an acquisition function drives the optimization process in DSE frameworks, efficiently navigating the DSE by identifying promising design points (PPA2, ), which is a set of micro-architectural parameters, for evaluation (ArchExplorer, ). The above two facilitate effective exploration of the design space within a reasonable time (BO1, ; BO2, ).

Fig. 1 illustrates the core workflow of the BO-based DSE framework. Prior to the exploration stage, the framework first trains the surrogate model using sampling methods, such as Plackett-Burman ranking(PBrank, ; MoDSE, ), to generate the training set (①, ②, ③). Once the surrogate models are trained, the exploration stage begins. The acquisition function selects a design point from the design space (❶) and sends it to the surrogate models to evaluate the PPA (❷). The framework then iteratively updates the Pareto-optimal set and repeats this process (❸, ❹).

A key concept in CPU DSE is the Pareto optimal set. A solution is considered as Pareto optimal if there is no other solution that improves some objective without worsening at least one other objective. To formalize the DSE as a multi-objective optimization task, the micro-architectural parameters are serialized as a feature vector $x$ referred to as a design point. The collection of all design points forms the design space $D$. Performance Metrics used to evaluate a design point are denoted as $y=f(x)$. In an n-objective minimization problem, a design point $x$ is defined to be dominated by $x^{*}$ if

This dominance is denoted as the partial order $x^{*}\prec x$ and $y^{*}\prec y$. Conversely, if $x^{*}$ does not dominate $x$, it is denoted as $x^{*}\nprec x$ and $y^{*}\nprec y$. Among all design points, the set of design points that are not dominated by any other design points is called the Pareto optimal set $\Omega$, formulated as:

The PHV is determined by the Pareto optimal set and a reference point, as shown in Fig.2(a). It is represented by the region of blue points, enclosed by light gray lines, with the reference point labeled as $Z_{\text{ref}}$. A larger PHV indicates a better compromise achieved by the solution set across multiple optimization objectives. In Fig.2(b), the new design points $x$ and $y$ demonstrate superior performance or power compared to the original design points, with both expanding the PHV, illustrated by the red and purple regions, respectively.

Modern CPU design is becoming increasingly complex, with a growing number of micro-architectural parameters. The exploration in such a significantly large design space is known as the high-dimensional DSE. Current DSE frameworks face three primary challenges in high-dimensional tasks.

First, DSE frameworks struggle with effectiveness due to the limited accuracy and efficiency of surrogate models in high-dimensional design spaces. The surrogate models in prevailing DSE frameworks (ActBoost, ; MoDSE, ; BOOMExplorer, ; Archranker, ), which typically use statistical regression methods, are simple while vulnerable. Specifically, prediction accuracy can decline as dimensionality increases. For instance, when the number of parameters exceeds 75, BOOMExplorer struggles to accurately predict and associate micro-architectural parameters with performance metrics.

This issue arises from the sparser feature space in high-dimensional condition (dimencurse, ), indicating the need for more training data to accurately capture the data distribution. However, the training and inference time increases greatly as the size of the training set grows. For instance, with a training set of size $n$, the complexity of training the inverse of the covariance matrix typically reaches $O(n^{3})$ and the inference through the inverse of the covariance matrix is $O(n^{2})$. This considerable computational cost renders high-dimensional design spaces impractical.

Second, the performance of DSE frameworks is hindered by the inefficiency of acquisition functions when dealing with high-dimensional design spaces. Acquisition functions are crucial for finding optimal design configurations, but they face challenges in high-dimensional design spaces. Current methods often rely on expert knowledge (ActBoost, ; MoDSE, ; BOOMExplorer, ) or complex feature engineering (ArchExplorer, ) to identify the bottleneck of the current micro-architecture, which can introduce biases, require significant time, and lack scalability. For instance, ArchExplorer only analyses the first hundred thousand of the instructions and achieves the optimal architecture with the number of parameters 21 over 15 days (ArchExplorer, ). Moreover, some methods rely on large-scale or even exhaustive search (MoDSE, ; ActBoost, ; BOOMExplorer, ). In high-dimensional spaces, this exhaustive search becomes computationally prohibitive due to the enlarged design space. For example, MoDSE can only perform with the number of parameters 10 (totaling 36,864 design points) (MoDSE, ). When the number of parameters increases to 30, it may take $1.9\times 10^{29}$ years. The high computational cost of such searches slows down the DSE process, delaying the identification of high-performance designs. This inefficiency slows down the DSE process, highlighting the need for more advanced and efficient acquisition strategies to handle complex, high-dimensional problems.

Third, conventional DSE frameworks fail to recognize the impact of each parameter on performance metrics. This limitation can cause these frameworks to overlook critical insights into how individual parameters impact the performance metrics, making it difficult to quickly and accurately identify bottlenecks in the current design. This phenomenon can be attributed to two primary reasons. Firstly, existing surrogate models cannot unveil the contributions of each parameter to the performance metrics because they rely on mathematical analysis (ActBoost, ; Archranker, ) or simplistic black-box models (BOOMExplorer, ; MoDSE, ) for prediction. Secondly, prevailing DSE frameworks typically adhere to a two-stage DSE scheme, treating the surrogate model and acquisition function as independent entities. This separation inhibits the exchange of information, preventing a comprehensive understanding of parameter efficacy (BOOMExplorer, ; MoDSE, ; ActBoost, ; ArchExplorer, ). Moreover, the lack of integration between these two components hinders the ability of the acquisition function to adaptively refine the exploration results based on feedback from the surrogate model, resulting in suboptimal performance and less effective DSE.

DSE is a crucial process in CPU design, often consisting of two important tasks: prediction and bottleneck analysis. Prediction helps estimate the performance of various design configurations, while bottleneck analysis identifies critical constraints that limit system efficiency. Both tasks are essential to guide CPU design effectively.

Recent advances in attention mechanisms offer significant advantages in addressing these challenges, proving to be highly effective for both performance prediction and bottleneck analysis. First, attention has been demonstrated to excel in regression tasks (attention_regression1, ; attention_regression2, ), accurately capturing complex relationships between inputs and outputs. Second, attention mechanisms inherently highlight the importance of different parameters by assigning varying weights, thus enabling a more fine-grained analysis of key design factors. These strengths align directly with the core needs of DSE, where both accurate performance prediction and the identification of critical design parameters are essential for driving effective design exploration.

Figure 3 provides an overview of AttentionDSE. It comprises three primary components: 1) Predictors, which provide rapid and accurate predictions of performance metrics (e.g., IPC) for given micro-architectures across benchmarks, thereby obviating the need for time-intensive simulations; 2) Micro-architecture Serialization, designed to reduce the computational burden associated with predictions, thereby expediting the performance evaluation process; 3) Bottleneck Analysis and Iterator, which identify the micro-architectural parameters that introduce performance bottlenecks within micro-architecture modules, facilitating the exploration of promising micro-architectural candidates by selectively modifying these parameters. The process of the AttentionDSE consists of a predictor training stage (①, ②, ③, ④) and an architecture exploration stage (❶, ❷, ❸, ❹, ❺).

The training stage is a one-time process, and the sequence of operations is represented by hollow numbers. This stage focuses on training predictors for performance metrics, ensuring that the models accurately capture the relationships between micro-architectural parameters and performance metrics. Unlike other approaches that rely on specialized sampling methods, AttentionDSE adopts a random sampling approach and then converts the design point to the sequence input, generating the training set (①, ②, ③). Next, the deep learning model, integrated with the PDA, functioning as the predictor, is trained to predict performance metrics (④). Benefiting from probabilistic attribute correlation in attention calculation, it’s more convenient to capture the intricate relationship between parameters, which informs exploration hints for the exploration stage.

Once the predictors are trained, AttentionDSE is ready for the exploration stage, which is iterative and aims for efficient multi-objective optimization. The exploration stage begins with a random sampling of design points (❶), followed by the exploration of the Pareto optimal set of these points through the trained predictors (❷). Each design point in the Pareto optimal set is analyzed to determine the contribution of each parameter (❸). The Bottleneck Analysis Iterator then selects the next design point based on the ABA algorithm (❹, ❺). This iterative process continues until the preset performance metrics are met, ensuring efficient and thorough exploration of the design space. Fig. 4 presents a detailed workflow of the exploration stage. All these techniques will be discussed in detail in the following sections.

A fast and accurate performance predictor can replace traditional simulation methods, serving as the cornerstone of an efficient DSE framework. This approach significantly accelerates design iterations and reduces the overall design cycle. As discussed in Section 4, the attention-based model is a promising option for developing such a predictor. Neural networks possess strong nonlinear fitting capabilities, making them well-suited for learning from high-dimensional data. Additionally, they benefit from robust hardware acceleration and a well-developed GPU-based framework, collectively enhancing training and inference speed.

In this subsection, we propose an attention-based prediction model as the single-objective predictor. We aim to develop a more accurate and scalable predictor that emphasizes efficiency in high-dimensional DSE.

The training procedure of the attention-based prediction model is demonstrated in Algorithm. 1. The prediction model consists of two key components: embedding preprocessing and the attention-based model. For embedding preprocessing, the procedure involves three steps: (a) Embedding, which transforms the discrete and heterogeneous alternatives of each micro-architectural parameter into a continuous numerical representation, simplifying optimization and enhancing the representation of relationships within the micro-architecture; (b) Position Embedding (PE), which assigns positional encoding to each item in the parameter sequence, enabling the model to learn parameter attributes more effectively and constrain the embedding space of each parameter; and (c) Prediction Token (PT), which gathers information from parameter embeddings using the self-attention mechanism and fuses it through multilayer perceptron (MLP), allowing the model to perceive the entire parameter sequence effectively. As for the attention-based model, to ensure the generalizability and versatility of the model, the predictor includes only vanilla self-attention, MLP, and normalization operations, which are the minimal necessary components of the transformer model (transformer, ). This streamlined design aims to maintain the attention mechanism’s inherent advantages. By focusing on these core components, we can leverage the self-attention mechanism’s ability to capture information within the input design point, allowing for the effective handling of complicated relationships between the design point and performance metrics in high-dimensional DSE tasks. The inclusion of MLP layers provides the model with the capacity to learn complex patterns and representations, while normalization operations ensure stable and efficient training by mitigating issues related to internal covariate shifts.

Although the prediction time is significantly reduced compared to simulation, further reductions are still necessary, especially when handling the large-scale design spaces of CPUs. Fortunately, from a micro-architectural design perspective, not all micro-architectural parameters are strongly correlated with one another, presenting an opportunity to reduce the computational burden of the attention mechanism significantly. For instance, the fetch buffer is closely related to the fetch width and fetch queue but has only a weak relationship with the writeback width. Therefore, in this section, we introduce the PDA mechanism as an alternative to the vanilla self-attention mechanism to alleviate the computational burden. The PDA mechanism includes two aspects: the micro-architecture serialization method and the sliding window attention mechanism.

In previous work (GPR, ; MoDSE, ; ensemble_learning, ; BOOMExplorer, ), the order of parameters is not a concern. Because GPR (GPR, ; BOOMExplorer, ) relies on the distance and similarity between input data rather than their arrangement order in statistical regression methods. Similarly, in ensemble learning (ensemble_learning, ; MoDSE, ), the training process of multiple weak learners introduces randomness, making the order of parameters irrelevant. To address this challenge in the attention-based predictor, we introduce a serialization approach named Perception-driven Serialization (PDS), aimed at preserving architectural information and laying the groundwork for the sliding window attention technique. This technique employs a graph-based method to delineate relationships among all parameters within each pipeline stage.

An example is illustrated in Fig. 5(a). We chose the Rename stage, shown in Fig. 5(b), as an example, where there are four parameters to be serialized including the free list (F), the rename map (R), the scoreboard (S), and the history buffer (H). The PDS first transfers the micro-architecture into a perceptual graph, which is an undirected graph based on the dataflow among these components, as depicted in Fig. 5(c). In a perceptual graph, vertices represent the parameters within each pipeline stage, while edges denote the datapaths between these components. The edges are categorized into two types: red edges, which connect to other pipeline stages and are labeled as external edges, and black edges, which connect to components within the current pipeline stage and are labeled as internal edges. To quantify the perception of each component, we leverage the perception degree $D$ of each parameter in the perceptual graph. The perception degree is calculated as follows:

Here, the internal edges represent the intra-stage perception field, while the external edges represent the inter-stage perception field. After calculating the perception degrees, the sequence of the micro-architecture is determined using the insertion sort algorithm. Parameters with the larger perception degree are inserted into the middle of the sequence as shown in Fig. 5(d). After all the pipeline stages have been serialized, the final vector of the micro-architecture is combined according to the order of the pipeline stages.

After the micro-architecture has been serialized, the vanilla self-attention mechanism can be replaced by the sliding window attention mechanism due to the parameter clusters. Fig. 6 shows an example of attention weight calculation compared with vanilla self-attention and PDA. For vanilla self-attention, every parameter must calculate the attention weight with every other parameter, as shown in Fig. 6(a). To optimize this process, we set the window size to the maximum perception degree among all parameters. In this example, the window size is set to five, as illustrated in Fig. 6(b).

In general, with the help of the PDA, each parameter calculates the attention weight only with its relative parameters. In this way, for a parameter vector of length $n$, the computational complexity is reduced from $O(n^{2})$ to $O(n)$. Thus, the PDA approach alleviates the limitations posed by number of parameters, enhances scalability, and reduces the training and inference time of the prediction model.

Bottleneck analysis is a critical step in CPU design, enabling architects to identify the key factors that impact system performance. In this subsection, we propose the ABA algorithm, which equips AttentionDSE with the capability to analyze attention weight heatmaps generated by an attention-based predictor. The ABA algorithm, detailed in Algorithm 2, reveals the intricate relationships between micro-architectural parameters and performance metrics, thus guiding the exploration of design space. This approach ensures that the most influential design parameters are prioritized during optimization, leading to more efficient and effective DSE.

In the attention weight heatmap, each row represents how the current parameter is influenced by other parameters, reflecting the correlations between them. For a particular parameter, the sum of all weights in its corresponding column indicates the overall influence of this parameter on others. Therefore, if the total sum of attention weights in the column corresponding to a certain parameter is minimal for IPC or maximal for Power or Area, we infer that this parameter has a significant impact on the current performance metrics. ABA algorithm then updates the Pareto optimal set by updating the design point based on this bottleneck analysis, ensuring continuous improvement and exploration of the design space.

To clarify the execution process of the ABA algorithm, Fig. 7 illustrates a toy example that demonstrates how the ABA algorithm updates micro-architectural parameters step by step to enhance performance (IPC). Initially, AttentionDSE randomly samples a design point and sends the parameters to the predictor. Based on the attention weight heatmap from the self-attention layer, the ABA algorithm sums all the columns and selects the parameter with the minimal sum as the current performance bottleneck, which in this example is the integer ALUs. The ABA algorithm then increases the number of ALUs from six to eight, improving performance. In the subsequent iteration, the ABA algorithm identifies the instruction queue size as the current bottleneck using the same process. The ABA algorithm increases the queue size from 64 to 80. By strategically adjusting the instruction queue size, the pipeline is provided with a sufficient flow of instructions, further optimizing performance.

We evaluate the AttentionDSE framework using SPEC CPU 2017 workloads.

We further conduct an ablation experiment to demonstrate the effectiveness of the optimizations. We select 600.perlbench_s as the representative dataset, and the results are consistent across other datasets.