Source-linked AI summary
Ithemal: Accurate, Portable and Fast Basic Block Throughput Estimation using Deep Neural Networks
Charith Mendis, Alex Renda, Saman Amarasinghe, Michael Carbin
TL;DR
Accurately estimating steady-state basic-block throughput matters for compiler and performance optimization, but analytical models are difficult to make accurate, portable, and fast on modern x86-64 processors. Ithemal learns throughput from assembly instructions and labeled data with a hierarchical multiscale RNN, achieving substantially lower error than hand-written analytical models while retaining fast estimation. Its reported throughput convention defines the value as clock cycles for a basic block, measured over 100 iterations.
Problem
Modern x86-64 microarchitectures make accurate, portable, and fast analytical throughput estimation difficult, although such estimates are important for compiler and performance optimization.
Method
Ithemal treats throughput estimation as regression and uses a hierarchical multiscale RNN to embed instructions and combine them into a block prediction from labeled assembly data.
Results
Ithemal reduces mean absolute percent error by more than 50% across all benchmarks and is more accurate than state-of-the-art analytical models while maintaining fast prediction speeds.
Takeaways & Limitations
Data-driven techniques can augment or replace manually developed throughput estimators while improving performance and portability with minimized developer effort.
Takeaways & Limitations
The paper defines its reported throughput as clock cycles for a basic block, the reciprocal of the standard throughput definition, measured over 100 iterations.
Abstract
from arXiv · showhide
Predicting the number of clock cycles a processor takes to execute a block of assembly instructions in steady state (the throughput) is important for both compiler designers and performance engineers. Building an analytical model to do so is especially complicated in modern x86-64 Complex Instruction Set Computer (CISC) machines with sophisticated processor microarchitectures in that it is tedious, error prone, and must be performed from scratch for each processor generation. In this paper we present Ithemal, the first tool which learns to predict the throughput of a set of instructions. Ithemal uses a hierarchical LSTM--based approach to predict throughput based on the opcodes and operands of instructions in a basic block. We show that Ithemal is more accurate than state-of-the-art hand-written tools currently used in compiler backends and static machine code analyzers. In particular, our model has less than half the error of state-of-the-art analytical models (LLVM's llvm-mca and Intel's IACA). Ithemal is also able to predict these throughput values just as fast as the aforementioned tools, and is easily ported across a variety of processor microarchitectures with minimal developer effort.
1 Introduction
Ithemal addresses the accuracy, portability, and speed challenges of predicting steady-state basic-block throughput by learning predictions from assembly instructions and labeled data. It outperforms sophisticated analytical models while retaining fast estimation and portability across microarchitectures.
- Throughput is the steady-state clock-cycle cost of an instruction sequence and supports runtime prediction and optimization in compilers and performance tools.
- Speed: Measuring throughput by executing blocks is too expensive for compilers and impractical for real-time systems.Compilers search many blocks, while execution-based estimates require sandboxing and repeated iterations to reach steady state.
- Accuracy: Analytical models are difficult to build because modern x86-64 processors use complex, nonlinear microarchitectural optimizations.These include micro-op fusion, out-of-order execution, and register renaming.
- Portability: Manual estimators must be rewritten for each processor microarchitecture, despite relative stability of the x86-64 ISA.Different generations have distinct instruction tables, resource charts, and optimization behaviors.
- Ithemal: A Data Driven Approach: Ithemal models throughput as regression from assembly sequences to real-valued throughputs using a hierarchical multiscale RNN.It embeds each instruction independently, then sequentially combines instruction embeddings to predict the block throughput.
- Ithemal: A Data Driven Approach: Ithemal reduces mean absolute percent error by more than 50% across all benchmarks while maintaining fast estimation speeds.The system requires training data and an ISA specification, learning salient microarchitectural details without explicit modeling.
2 Motivating Examples
The motivating examples show why hand-written throughput models can fail when processor behavior or vendor documentation is incomplete or inaccurate. Ithemal instead learns from measured performance data and closely predicts the illustrated cases.
- Motivating Examples: Hand-written analytical models can produce flawed predictions despite extensive engineering of underlying microarchitectural details.The examples compare actual throughput with predictions for short x86-64 sequences.
- Motivating Examples: The paper defines throughput as the clock cycles needed to execute a basic block and reports values for 100 iterations.This convention is the reciprocal of the standard throughput definition.
- Motivating Examples: Ithemal closely predicts measured throughput for register-zeroing instructions without explicitly encoding Intel’s optimized execution path.LLVM’s prediction is farther off because it does not model that optimization.
- Motivating Examples: For two mov instructions, the measured throughput is 103 cycles, while IACA predicts 84 cycles after identifying a fusion opportunity absent from the observed timing.Both IACA and LLVM identify a 100-cycle execution schedule before IACA applies fusion.
- Motivating Examples: Vendor documentation can be incorrect, causing tools that follow dependency-free throughput values to miss behavior in dependent instruction sequences.In sequence (c), a pipeline bypass means mov adds few cycles beyond shl, so shl dominates throughput.
3 Model Architecture
Ithemal canonicalizes assembly into structured tokens, embeds instructions hierarchically with LSTMs, and maps the resulting block representation to a real-valued throughput prediction.
- Ithemal treats throughput estimation as regression from assembly input to a real-valued instruction-sequence throughput.
- Canonicalization: Canonicalization converts each instruction into opcode, source-operand, and destination-operand tokens separated by delimiters.Constants become CONST tokens, while memory operands receive explicit delimiters.
- Embedding: The token layer maps each token to a learned n-dimensional vector, forming the inputs to instruction embeddings.The mapping is implemented as a learned linear transformation of one-hot token vectors, equivalent to a lookup table.
- Embedding: An instruction-level LSTM converts variable-length token-embedding sequences into embeddings for individual instructions.This layer handles instructions with different numbers of source and destination operands.
- Prediction: A second LSTM processes the sequence of instruction embeddings, and a linear layer computes throughput as w ·hblock +b.The prediction-layer LSTM uses weights disjoint from those of the instruction layer.
- Architecture benefits: The hierarchical design shortens memory and backpropagation paths compared with a single token-level RNN and embeds instructions atomically.The dataset averages 6.04 instructions per block and 7.97 tokens per instruction, versus about 48 cell applications for a token-level RNN across a block.
4 Data and Training
The authors build a diverse x86-64 basic-block dataset by extracting, deduplicating, and profiling compiled applications under baseline-model assumptions, then train Ithemal with supervised learning.
- Dataset: The dataset combines performance-critical benchmarks and end-user applications to cover diverse performance characteristics and a wide range of x86-64 instructions.
- Dataset construction: Applications are compiled with GCC 4.9.4 at -O3 for Haswell, instrumented with Dynamorio, and executed with standard benchmark inputs to extract basic blocks.
- Throughput profiling: Throughput profiling loops each basic block in isolation 100 times under L1-hit and non-preemptive assumptions, measuring clock cycles and filtering invalid executions.The filtering uses cache-miss and context-switch measurements to detect violations of the analytical baselines’ assumptions.
- Dataset: The final Haswell dataset contains 1,416,473 unique basic blocks after deduplication across benchmarks.
5 Evaluation
Ithemal is evaluated against IACA and llvm-mca for accuracy, speed, and portability across processor microarchitectures. It achieves higher accuracy while maintaining comparable prediction speed and requiring no architecture or hyperparameter modifications across evaluated microarchitectures.
- 5.1 Accuracy: Ithemal’s predictions are more accurate across Haswell, Ivy Bridge, and Skylake than the evaluated analytical models.Accuracy is assessed against measured throughput using average error and Spearman and Pearson correlations; IACA is unavailable for Ivy Bridge.
- 5.1 Accuracy: 74% of Haswell test blocks have Ithemal predictions closer to ground truth than both IACA and LLVM.Ithemal also achieves higher Spearman and Pearson correlations with measured throughput.
- 5.1 Accuracy: Ithemal is closer to the identity line and outperforms both analytical estimators across almost all throughput ranges.The heatmaps use 20-cycle bins; analytical models show more horizontal banding, while all estimators struggle near peaks in the throughput distribution.
- 5.2 Speed: Ithemal is as fast as llvm-mca and IACA and significantly faster than empirical basic-block evaluation in the reported measurements.Estimator throughput is computed from timed basic blocks and average instructions per block on the Haswell test set.
- 5.3 Portability: 0.089 is Ithemal’s maximum average error across the evaluated datasets, compared with 0.167 as the minimum average error of the hand-written models.The same architecture and training regime were used across Haswell, Skylake, and Ivy Bridge.
6 Neural Network Architecture Exploration
The architecture exploration compares sequential, hierarchical, and dependency-graph recurrent models for throughput prediction. The hierarchical LSTM performs best, while the results indicate that both instruction ordering and dependency structure matter.
- DAG-RNN: The DAG-RNN builds an instruction-dependence graph and propagates information along dependency paths before applying LSTM cells.When multiple prior instructions feed an instruction, their states are reduced with an element-wise maximum.
- Baselines: The token-level RNN sequentially consumes all basic-block tokens without explicitly distinguishing instructions, providing a baseline for the hierarchical model.Its design omits the topmost prediction layer used by the hierarchical architecture.
- Model comparison: The hierarchical LSTM is the best of the three evaluated models, while the sequential LSTM performs worst by far.The comparison uses training and validation loss across the first five epochs.
- Model comparison: The DAG-RNN’s lower performance than the hierarchical LSTM implies that exact instruction ordering matters in addition to dependency chains.This is consistent with the reported effect of instruction scheduling on performance and with serial behavior in modern processors.
7 Related Work
Prior work includes analytical, learned, graph-based, and simulator approaches to throughput and runtime estimation. Ithemal differs by learning basic-block throughput directly with minimal architectural knowledge and without manual feature engineering.
- Neural and graph models: Graph and neural models have also been applied to program relations, variable-level tasks, binary similarity, memory access, and branch prediction.The related approaches span gated graph neural networks, DAG-RNNs, RNNs, and perceptron models.
- Simulation: Cycle-accurate simulators have high start-up costs and are more suited to coarse-grained simulations.The cited examples include ZSim and Marss.
- Analytical models: Analytical throughput models require detailed processor modeling and considerable human development effort.Examples include llvm-mca, IACA, OS-ACA, and other analytical approaches for instruction or program runtime estimation.
- Learned models: Earlier learned models use hand-crafted features or operate at coarser granularities such as full-program runtime or speedup.These approaches include sparse polynomial regression and neural networks for execution-time or code-sequence speedup prediction.
- Ithemal: Ithemal automatically predicts throughput for basic blocks with minimal architectural knowledge embedded in the model.This distinguishes it from learned models requiring manual feature engineering.
8 Conclusion
Ithemal is a data-driven basic-block throughput estimator whose accuracy surpasses state-of-the-art hand-written analytical models. Its implementation describes memory operands with explicit delimiter tokens and provides a full token-string grammar.
- 8 Conclusion: Ithemal uses a deep neural network to estimate basic-block throughput and surpasses state-of-the-art hand-written analytical models.The approach is intended to improve performance and portability while minimizing developer effort.
- 8 Conclusion: Memory operands are represented by surrounding their address components with <M> and </M> delimiter tokens.The operands consist of a base address and optional offset and displacement.
- 8 Conclusion: The token-string representation is specified by a full grammar described in Section 3.1.
B Training Hyperparameters
The models use fixed-width vectors and asynchronous training with multiple parallel trainers, while Figure 6 compares prediction heatmaps across three Intel microarchitectures. IACA lacks a heatmap for Ivy Bridge because its latest version does not support that architecture.
- B Training Hyperparameters: All embedding, hidden, and output vectors have width 256, with asynchronous SGD using batch size 4 and 6 parallel trainers.The initial learning rate is 0.1, then decreases geometrically by 1.2 each epoch after the first 2 epochs; momentum uses β = 0.9.
- B Training Hyperparameters: Figure 6 compares Ithemal, llvm-mca, and IACA prediction heatmaps for Ivy Bridge, Haswell, and Skylake.
- B Training Hyperparameters: IACA has no Ivy Bridge prediction heatmap because its latest version does not support Ivy Bridge.
D Prediction Errors for Throughput Ranges
Figure 7 analyzes prediction error across throughput ranges and microarchitectures for test-set basic blocks below 1000 cycles, alongside throughput distributions.
- D Prediction Errors for Throughput Ranges: Figure 7 reports how average prediction error varies across throughput ranges for each method and microarchitecture.
- D Prediction Errors for Throughput Ranges: Throughput values are divided into bins with length and width 20 cycles on each axis.
- D Prediction Errors for Throughput Ranges: The figure also shows basic-block throughput distributions and average error across measured throughput ranges.
- D Prediction Errors for Throughput Ranges: Ithemal consistently predicts throughput values with lower average errors than the compared prediction methods.
E Token RNN Architecture
The Token RNN architecture is presented through its full architectural diagram, while accompanying figures visualize throughput predictions and error behavior for basic blocks across processor microarchitectures.
- E Token RNN Architecture: Figure 8 presents the full architecture of the Token RNN described in Section 6.
- E Token RNN Architecture: Figure 6 provides heatmaps of measured and predicted throughput under different models for Ivy Bridge, Haswell, and Skylake.
- E Token RNN Architecture: Figure 7 presents average error curves and throughput distributions for different models across microarchitectures.
- E Token RNN Architecture: Figure 8 is labeled as the Token RNN Architecture figure.