Performance Optimization using Multimodal Modeling and Heterogeneous GNN

Initially, each application is instrumented to accept variable input at runtime. Additionally each OpenMP loop is instrumented to call appropriate PAPI (Mucci et al., 1999) APIs for profiling purposes. Each instrumented application is then profiled for each input size and configuration. This is a one time cost of creating the dataset and identifying the best configurations as labels of the dataset. A major bottleneck of this process is the large number of available performance counters. All systems used for this experiment reports $>$50 preset counters. We collected 20 PAPI counters based on the ideas presented in (Alcaraz et al., 2019; Alcaraz et al., 2021, 2022) for the Polybench suite. We extend and update these techniques to build our own dataset of OpenMP loop signatures. For each loop, we used 30 input sizes ranging from $3.5$KB to $0.5$GB. Profiling with multiple inputs provides insight into how these inputs impact the execution behavior of each OpenMP loop. The input sizes were selected with the intention of stressing each of the three cache levels (L1, L2, L3) to different degrees. This type of input-driven profiling lets us explore how varying runtime parameters can help alleviate latency issues. However, including all counters while training our tuning model leads to a feature explosion and negatively impacts model convergence. To improve model convergence, we used Pearson’s correlation (Benesty et al., 2009) and identified five performance counters that are most correlated to execution time, and used these for training purposes. For the remaining applications, we only profile them to collect these five counters. For an application with multiple OpenMP loops, the associated counters and execution times are collected in a single run. This implicitly accounts for the effect on hardware components a preceding loop might have on succeeding ones. These steps reduce the profiling cost to a large degree. The selected performance counters are L1, L2 cache misses, L3 load misses, number of retired branch instructions, and mispredicted branches across all loops, inputs and experiments.

In this section, we have compared our results with three autotuners, ytopt, OpenTuner, and BLISS and two state-of-the-art code representations PROGRAML and IR2Vec. ytopt (Balaprakash et al., 2020) and BLISS (Roy et al., 2021) are autotuners based on Bayesian optimization. OpenTuner (Ansel et al., 2014) is a search-based autotuner which employs various search techniques such as AUC Bandit, Nelder-Mead, Torczon hillclimbers, etc. ytopt and OpenTuner have been previously used for a variety of tuning tasks (Koo et al., 2021; Wu et al., 2021; Zhang et al., 2018; Han et al., 2020; Hagedorn et al., 2018) and were hence chosen as baselines for this paper. BLISS represents a more recent state-of-the-art autotuner based on Bayesian optimization. We have also compared against unimodal DL approaches that uses only PROGRAML (Cummins et al., 2021) or IR2Vec (VenkataKeerthy et al., 2020) as the code representations of choice.

One of the most widely used techniques for improving the performance of OpenMP code is by varying the thread-level parallelism. Simply allocating more threads to a workload might not produce the best results as shown in Figure 1.

The heterogeneous GNN model used across our experiments consists of three homogeneous GNN models. We experimented with a few popular graph neural networks: graph convolution networks (GCNs) (Kipf and Welling, 2016), graph attention networks (Veličković et al., 2017), GraphSAGE (Hamilton et al., 2017), and gated graph neural networks (GGNN) (Li et al., 2015). We observed that using GGNNs for modeling each relation in the flow graphs produces the best end results. The IR2Vec embeddings are modeled using DAE layers with Sigmoid activation function as described in Section 3.2. The output tensors from these models are then fused and concatenated with the performance counters and fed into the MLP layers to predict the number of threads. This model is optimized with the AdamW optimizer (Loshchilov and Hutter, 2018).

To evaluate our model performance, we perform 5-fold cross validation.

Here, we run the same experiment five times, where the five validation folds are mutually exclusive sets and the union of these five sets equal the set of all loops in the dataset. For each validation fold, the other loops in the dataset (four-fifth of all loops) are assigned to the training set. The model is then iteratively trained and validated five times to ensure coverage of all loops in the dataset. In the absence of a designated, representative test set, k-fold cross validation allows us to test the skill of the model on unseen data. Our model achieves geometric mean accuracy of 86% in identifying the best threads across five folds.

The results in Figure 4 show that our approach performs better compared to other approaches. For each loop in the validation set, we use the predicted configuration for each input to obtain the execution time for that combination, and calculate the speedup (speedup = $\frac{Runtime_{default}}{Runtime_{new}}$) with respect to the default execution time. We repeat this process for each loop in the validation set. The geometric mean of these speedups is presented as each bar for each fold in Figure 4.

As mentioned before, we compared our approach with two unimodal approaches using PROGRAML and IR2Vec as the code representation of choice along with the tuners ytopt, OpenTuner, and BLISS. We defined the same search space for these tuners. These tools performed search space optimizations to predict better performing configurations. We treated the tuners as black boxes, and simply provided the search space and target metrics. In this experiment, speedups are calculated with respect to the execution time with default OpenMP configurations (all threads, static scheduling, compiler calculated chunk size). In three out of five folds, our approach produced normalized speedups of $\geq 0.95\times$, and in one out of five folds normalized speedup between $0.9\times$ and $0.95\times$ of the oracle speedups. The IR2Vec tuner led to normalized speedups of $\geq 0.9\times$, but $<0.95\times$ in three out of five folds, and had normalized speedups $<0.85\times$ in the remaining folds. The PROGRAML tuner produced normalized speedups of $>0.85\times$ in one out of five folds. As seen in Figure 4, ytopt produced normalized speedups $>0.75\times$ in one out of five folds. OpenTuner and BLISS produced speedups of $>0.75\times$ in two out of five folds. Our approach only shows reduced performance gains in one fold. This is primarily due to the presence of the trisolv kernel from Polybench. The serial version of trisolv has better performance than the parallel version used in this paper. This worsens the result of fold one, as the DL model does not see similar trends for other loops based on code modeling and execution behavior.

Amongst the considered tuning approaches, our method came closest to the oracle predictions. Oracle predictions in this experiment are those configurations obtained by brute-force tuning. ytopt, OpenTuner, BLISS, the PROGRAML tuner, the IR2Vec tuner, and the MGA tuner produced geometric mean speedups of $1.46\times$, $2.33\times$, $1.67\times$, $2.79\times$, $3.17\times$, and $3.4\times$ across all folds compared to oracle speedups of $3.62\times$.

Importance of dynamic information.

Performance profiling is an overhead of our approach. However, we posit that modeling performance counters is essential for such DL-based tuning. We performed a set of ablation studies to validate this claim. We trained three DL models with only static features and observed some performance degradation when performance counters were not a part of the feature set. The results from the validation set obtained by performing a randomized 80/20 split are shown in Figure 5. Compared to achieved speedups of $3.9\times$, $3.6\times$, and $3.0\times$ by the MGA, IR2Vec and PROGRAML models (uses both static and dynamic features) respectively, the speedups fell to $2.8\times$, $2.5\times$, and $2.5\times$ without performance counters. This is expected as these static features do not explicitly provide information about the impact of varied inputs on execution. In addition, we also train a model with only dynamic features. It showed the smallest speedups amongst all the DL-tuners designed in this paper, achieving speedups of only $2.1\times$. Therefore, static and dynamic features are both essential for tuning. We also compare these results with the ytopt, OpenTuner, and BLISS predictions. The tuners that use static-only features and both static and dynamic features have better performance than ytopt, OpenTuner, and BLISS.

Varying Input Sizes. To evaluate the generalizability of our method, this section primarily evaluates how our model performs when both loops and input sizes are unknown. We initially selected at random 20% of the 30 input sizes considered in this paper, and set it aside for validation. We then split the loops using 5-fold validation as described before. Following this process, each validation fold now consists of unseen loops and the unknown input sizes set aside before. However, to reduce bias and preserve generalizability, the loops in these validation folds are different from the validation folds in the previous experiment (e.g. validation loops in fold one of this experiment is different from the validation loops in fold one of previous experiments). In the previous experiments, only the OpenMP loops were unknown in the validation set. The model had been trained on the training set of OpenMP loops and all input sizes. In contrast, in this experiment, the model is trained on the OpenMP loops in the training set and $80\%$ of the input sizes. The loops in the validation sets and the unknown inputs are tested in this experiment and the results are shown in Figure 6. We observe that our model performs well producing geometric mean speedups of $2.35\times$ across all folds, compared to mean oracle speedups of $2.68\times$. There is some performance drop as input sizes highly impact performance counters and the best runtime configurations. Without prior knowledge of program behavior at these input sizes, the model performance suffers.

The experiments performed in previous sections have achieved good results. However, those search spaces are fairly small. In order to assess the scalability of our approach to larger search spaces, we experimented with tuning the number of threads, scheduling policy, and chunk sizes at the same time. The search space is defined in Table 2 using ideas from (Bari et al., 2016; Bari et al., 2019).

In this experiment, we have used a smaller subset of the applications considered in the paper and worked on benchmarks from Polybench and Rodinia. We have additionally experimented with a proxy application, LULESH (Karlin et al., 2013a, b) from the DARPA UHPC program. To compensate for the reduction in the size of the dataset, we performed leave-one-out validation instead of 5-fold validation. In this method of validation, we leave out data associated with one benchmark application (all loops in this application are present in the validation set) as the validation set and train our model on the rest. This process is repeated for each considered application. As shown in Figure 7, this leads to normalized speedups of $>0.95\times$ of the oracle speedups in $21$ out of $30$ applications, and $>0.85\times$ normalized speedups in 28 out of 30 applications. trisolv is the worst performing application due to reasons discussed in Section 4.1.3. Our approach outperforms ytopt, OpenTuner, and BLISS in 28, 29, and 26 cases out of 30. ytopt, OpenTuner, and BLISS produce $>0.95\times$ of the oracle speedups in 7, 2, and 12 cases out of 30. Overall, our model produces geometric mean speedups of 2.23$\times$ compared to oracle speedups of 2.38$\times$. The improvement in performance of most kernels can be attributed to better cache performance, branch predictions, and load balancing. We show the impact of using the predicted OpenMP configurations for this system on cache misses, clock cycles, and branch mispredictions compared to the default configuration of using all threads and static scheduling in Figure 8 for the 2mm kernel. There is a clear relation between improved performance and reduced cache misses, and branch mispredictions. In most kernels used in this paper, the profitable configurations lead to improvements in most of these factors, leading to improved performance.

In this section, we analyzed if our auto-tuner can predict the number of threads on other $\mu$-architectures. We re-used the model in Section 4.1.3 (trained on data from Comet Lake $\mu$-architecture) to predict the number of threads on single-socket 8 core systems belonging to the Broadwell and SandyBridge $\mu$-architecture (access provided by Cloudlabs infrastructure (Duplyakin et al., 2019)). Limiting the scope of this experiment to testing hardware portability to single-socket 8 core systems helps us to directly use a pre-trained model without additional training (different core/socket count would necessitate re-training). Static code graphs, sequential code vectors, and the performance counters from the target systems (Broadwell/Sand Bridge) were passed as inputs to the pre-trained model. We validated this approach on 25 kernels from the PolyBench benchmark with STANDARD and LARGE inputs. Similar to Section 4.1.4, we perform leave-one-out validation for this experiment. The data from the Comet Lake system was always used for training in this experiment. For each validation fold, the validation kernel was executed twice on the target $\mu$-architecture to collect the necessary counters. The L1, L2, and L3 cache counters were then computed as a function of the system cache sizes relative to the system on which the training data is collected (e.g. L1 cache misses for Sandy Bridge are computed as $\frac{L1\_CM\times{L1\_cache\_size}_{SandyBridge}}{{L1\_cache\_size}_{CometLake}}$). The branch misprediction counters were divided by the number of reference clock cycles. These counters were then normalized to a [0,1] scale and fed into the model to predict the number of the threads. This process completely removes the overhead of re-training models for other similar $\mu$-architectures.

As shown in Figure 9, our approach performs well while predicting the number of threads on Braodwell and Sandy Bridge with a model trained on data from Comet Lake. In most cases, the predicted configurations lead to optimal/better performance. We observed that only using static features leads to the model making similar predictions for Comet Lake, Broadwell, and Sandy Bridge. Without modeling performance counters, the predictions for unseen loops are what it would be for the training $\mu$-architecture. This led to degraded performance on the target $\mu$-architectures.
Observations and Analysis. For these experiments, our approach produces the best results overall. The experiments considered in this section fall more under the scope of online/offline auto-tuning than compiler optimizations. Search-based autotuners are more suited to this type of autotuning. However, these do need to execute code multiple times to identify profitable configurations from the search space. Our approach in this section needs only two runs (two runs are needed due to system limitations; the selected performance counters cannot be collected in one run; essentially, we only need one run when systems permit) during inference, irrespective of the size of the search space. In comparison, ytopt, OpenTuner, and BLISS require multiple runs to identify profitable configurations. As an example, for the experiment in Section 4.1.4, we consider the time taken for tuning the 2mm benchmark from PolyBench with LARGE input. The MGA tuner takes approximately 90 seconds to identify near-optimum configurations during inference. This includes the time needed for profiling and prediction. OpenTuner takes roughly 180 seconds (the specified time limit), ytopt takes approximately 260 seconds to finish tuning with the maximum evaluations set to ten, and BLISS takes around 220 seconds. The settings for the three tuners were chosen to achieve a balance between acceptable results and speed of tuning. Letting them run longer, although much more expensive, might improve results. In conclusion, not only does our technique produce better results than the other approaches considered in this work, it is also faster than existing tuners.

We use the dataset published by Ben-Nun et al. (Ben-Nun et al., 2018) for this experiment. It has 256 unique OpenCL kernels from seven benchmark suites comprising of AMD SDK, NPB, NVIDIA SDK, Parboil, Polybench, Rodinia and SHOC. The data size and workgroup size were varied for each kernel to obtain a labeled dataset with 670 CPU- or GPU-labeled data points for each of the two devices, AMD Tahiti 7970 and NVIDIA 970. As this is a published dataset, no modifications were made to it, and performance counters have not been used in this experiment.

For modeling purposes, we use similar techniques used in the previous section. We initially use the extracted IR of the OpenCL kernels in the dataset. The IRs are then passed through PROGRAML and IR2Vec to obtain the code graphs and code vectors. As before, the code graphs are modeled using Heterogeneous GNNs and the code vectors are modeled using DAEs. For this experiment, the modeled outputs from the GNN and DAE models are concatenated as before. In addition, we also add transfer and workgroup sizes from the dataset to the feature set before passing the feature set onto the fully connected MLP layers. Following the techniques used in (Cummins et al., 2021; VenkataKeerthy et al., 2020), we have also used ten-fold stratified cross-validation to evaluate our results. We were able to replicate the experiments reported in (VenkataKeerthy et al., 2020), and these results are used to compare our results. The results from (Cummins et al., 2021) are used directly to compare our results. In this task, we validate if our approach can outperform the state-of-the-art to reinforce our hypothesis that existing code representations are good enough to be used in conjunction for better performance.

Our experimental setup leads to state-of-the-art results in identifying the correct device. We achieve accuracy of 97.9% and F1-score of 0.98 in identifying the best device on the NVIDIA GPU. On the AMD GPU, we achieve accuracy and F1-score of 97.7% and 0.97. In comparison, PROGRAML achieves accuracies of 80% and 86.6% on the NVIDIA and AMD GPUs and corresponding F1-scores of 0.88 and 0.8. IR2Vec (flow-aware representation) achieves accuracies of 89.68% and 92.82% on the NVIDIA and AMD GPUs. Comparisons with other works on this dataset are shown in Table 3. The accuracy numbers for Grewe at al. (Grewe et al., 2013), DeepTune (Cummins et al., 2017), and inst2vec (Ben-Nun et al., 2018) are cited from (VenkataKeerthy et al., 2020).

We have also analyzed performance improvements due to the predictions by our model. The speedups are calculated in comparison to static mappings as done in (VenkataKeerthy et al., 2020). On the NVIDIA 970 system, our approach leads to speedups of $1.3\times$ compared to oracle speedups of $1.34\times$. The oracle speedups are calculated by analyzing the execution time on the best device and comparing it to the static mapping baseline. In comparison, the predictions in (VenkataKeerthy et al., 2020) led to speedups of $1.26\times$. On the AMD Tahiti system, our predictions lead to speedups of $1.62\times$ compared to speedups of $1.58\times$ produced by IR2Vec (VenkataKeerthy et al., 2020) and oracle speedups of $1.66\times$.
Observations and Analysis. We have shown in this section that our approach produces better results than the state-of-the-art in this field without the need of a completely new code representation technique. We analyzed our model’s predictions to identify those cases where our model outperformed the state-of-the-art. We were only able to replicate the experiments in (VenkataKeerthy et al., 2020) (best results in existing literature) and our observations are with respect to this paper. Our overall performance was better as our edge case predictions were better. We noticed that our model outperformed in corner cases where kernels with small inputs were mapped to the GPU, and kernels with large inputs were mapped to the CPU. As an illustrative example, consider the makea kernel from the CG benchmark in NPB. In the dataset, this kernel gets mapped to a GPU with a small input class S, whereas the same kernel with much larger input class C gets mapped to the CPU. This behavior can be due to the presence of multiple function calls from inside a loop. The called functions, also have parallel loops in them. This, we believe, creates an overhead which leads to faster execution on the CPU for larger inputs. For the smaller inputs, the number of function calls are much less which does not create a bottleneck for GPU execution, leading to much faster execution on GPUs. The MGA model is able to identify such edge cases as our approach can capture the characteristics of individual instructions and arguments along with the data, control, and call flows in a kernel.