{'fraction_non_alphanumeric': 0.027661378828694003, 'fraction_numerical': 0.005786690611593336, 'mean_word_length': 4.612122060470325, 'pattern_counts': {'":': 3, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Machine Learning for CUDA+MPI Design Rules

We present a new strategy for automatically exploring the design space of key CUDA+MPI programs and providing design rules that discriminate slow from fast implementations. In such programs, the order of operations (e.g., GPU kernels, MPI communication) and assignment of operations to resources (e.g., GPU streams) makes the space of possible designs enormous. Systems experts have the task of redesigning and reoptimizing these programs to effectively utilize each new platform. This work provides a prototype tool to reduce that burden. In our approach, a directed acyclic graph of CUDA and MPI operations defines the design space for the program. Monte-Carlo tree search discovers regions of the design space that have large impact on the program's performance. A sequence-to-vector transformation defines features for each explored implementation, and each implementation is assigned a class label according to its relative performance. A decision tree is trained on the features and labels to produce design rules for each class; these rules can be used by systems experts to guide their implementations. We demonstrate our strategy using a key kernel from scientific computing -- sparse-matrix vector multiplication -- on a platform with multiple MPI ranks and GPU streams.


I. INTRODUCTION
This work presents a new strategy for automatically exploring the design space of key CUDA+MPI operations and providing design rules that discriminate slow from fast implementations. High performance MPI+CUDA programs are assembled from more primitive operations, particularly GPU kernels, inter-node communication, and GPU data transfers. In order to overlap communication with computation, these operations are typically asynchronous and parallel. The order of these operations and how they are assigned to system resources greatly affect performance, but optimal orders and assignments can be difficult to identify.
For example, Figure 1 shows the performance of 2036 different distributed MPI+CUDA sparse-matrix vector multiplication (SpMV, Section III) implementations sorted from fastest to slowest The fastest implementation is 1.47× faster than the slowest. The kernel implementations and MPI communication methods are identical -only the order of operations and the assignment of GPU operations to streams are changed.
The freedom to reorder independent operations and assign those operations to various system resources yields a combinatorial explosion of possible implementations, even for relatively simple distributed CUDA+MPI programs. Experts typically design these programs according to various heuristics (e.g. longest possible communication window, maximum GPU utilization, etc.) and then engage in a process of iterative measurement and refinement to achieve their objectives. Different computer systems have different performance characteristics, forcing implementers to repeat this process for each target system. The example in Figure 1 is just a single matrix input on a single execution platform. As new systems with new performance characteristics come online, program authors must revisit the design of their key operations to ensure continued performance.
We simplify this design process with a new system for automatically exploring the design space of CUDA+MPI programs and providing design rules that discriminate slow from fast implementations. Our contributions are • A Monte-Carlo tree search strategy for exploring the CUDA+MPI design space, and • A decision-tree-based method for generating rules to discriminate fast from slow programs. The goal is to provide program implementers with specific design rules for meeting performance objectives. Simultaneously, "black-box" tuning results are avoided, granting implementers complete provenance over the final program design. Monte-Carlo tree search identifies interesting regions of the design space (Section III-C). Class labels are generated through convolution and peak detection (Section IV-A). Feature vectors are created through a custom sequence-to-vector transformation (Section IV-B). A decision tree trained on the features (Section IV-C) and labels produces design rules (Section IV-D).
program performance (Section III-C). A sequence-to-vector transformation is applied to define features for each explored implementation, and each implementation is assigned a class label according to its relative performance (Sections IV-A and IV-B). A decision tree is trained on the features and labels to produce design rules for each class (Sections IV-C and IV-D).
We demonstrate our strategy with a CUDA+MPI sparsematrix vector multiplication on the Perlmutter HPE Cray EX platform at NERSC (Sections IV and V). Long term, the system will be applied to high-performance libraries like Tpetra [1], [2], and the design-rule generation will be expanded to accommodate multiple platforms and multiple inputs. An open-source implementation is available at github. com/sandialabs/tenzing.

II. BACKGROUND
Both MPI and GPUs typically are used in an asynchronous manner, in which the CPU initiates communication or computation operations and proceeds with its own thread of execution while the MPI implementation and GPUs work in parallel. Asynchronous operations allow overlapped communication and computation, since (in principle) a GPU kernel can be executing while an MPI communication is in-flight.
CUDA provides streams and events to control and synchronize asynchronous operations. A GPU stream is a queue of such events in which each operation must complete before the next begins. A GPU has multiple streams, allowing multiple sequences of operations to proceed independently (and in parallel when execution resources permit). A CUDA event represents a particular point in a stream's execution. It allows the CPU or other streams to synchronize with a particular state of a given stream, either waiting for that state to be realized in the future, or proceeding immediately if that state already existed in the past.
MPI's facility for synchronization is the MPI Request. An MPI Request object is associated with a particular MPI operation, e.g. MPI Isend. The CPU can interact with that object to query or control the ongoing communication operation.

A. Monte-Carlo Tree Search For Performance Optimization
Monte-Carlo tree search [3], [4] (MCTS) is a heuristic search method for decision problems that describes the search space in a tree. Each tree node represents a state of the search, and the node's children describe possible next states from the current state. The tree is grown by balancing exploration and exploitation values for each node, which are used to guide the search towards the optimal result. MCTS (and the similar beam search) have been examined previously in the context of performance optimization. As in our work, MCTS has been used for task-scheduling, though it does not explicitly seek the fastest implementation. Instead, MCTS is used to discover regions of the design space that have a large effect on performance.
Adams et al. [5] use beam search to generate imageprocessing and deep-learning programs from high-level Halide descriptions. Wang et al. [6] use MCTS to design neural network architectures. Exploitation is based on network accuracy. The search is slowed by long network training times before accuracy can be evaluated. A neural network is used to estimate the performance of the proposed networks during MCTS. Zheng et al. [7] propose Ansor for automatically generating tensor programs. Among other things, Ansor attempts to generate fast task graphs for deep neural networks. Ansor engages in random sampling of the task graph space, and then uses a gradient-descent approach for scheduling those tasks. Our work uses MCTS to address sampling and scheduling jointly. Halaji et al. [8] use MCTS to tune deep learning and image processing programs.
MCTS has also been used to determine optimal parameters for various tasks. Kruse, Finkel, and Wu [9] and Koo et al. [10] use MCTS for choosing loop optimizations in LLVM's polyhedral loop optimizer. Anderson et al. [11] uses beam search to optimize loop nests for Halide programs. Our work does not use MCTS to optimize individual tasks; rather, in this work, we focus on task scheduling.

B. Decision Trees in Program Optimization
Decision trees represent decision processes as a binary tree of conditional statements. Each node in the tree tests a particular feature and each child represents an outcome. Decision trees have been used in various aspects of program optimization. As opposed to prior works, we do not use the decision tree to make optimization decisions, but instead to determine distinguishing properties of various implementations.
Monsifrot and Amarasingh [12] use a decision tree to choose whether to unroll program loops based on hand-crafted features, followed by Leather, Bonilla, and O'Boyle [13] to choose loop unroll factors. Yu and Rauchwerger [14] use decision trees to predict appropriate loop parallelization strategies. Grewe, Wang, and Boyle [15] and Wang, Grewe, and Boyle [16] use decision trees to decide how effective GPU acceleration will be. Ding et al. [17] use decision trees to choose the optimal algorithm implementation for different inputs. Lokuciejewski [18] uses random forests to predict the benefits of function inlining. Benedict et al. [19] and Rejitha, Benedict, Alex, and Infanto [20] use random forests to predict energy cost of OpenMP and CUDA programs.

C. MCTS for Scheduling Outside of Computing
MCTS has been applied to non-computer-science taskscheduling problems as well. Lubosch, Kunath, and Winkler [21] apply MCTS to a benchmark semiconductor fabrication scheduling problem. Runarsson, Schoenauer, and Sebag [22] apply MCTS to a job-shop scheduling problem, and find that MCTS produces as good or better results than other algorithms. Wu, Wu, and Liang [23] similarly consider a multi-objective version of the problem, and determine that MCTS finds state-of-the-art solutions in much less time. Neto, Constantino, Martins, and Pedroso [24] apply MCTS to a forestry harvesting problem, where stands of trees are assigned a lifespan before harvesting. They find that MCTS is able to find solutions for large problems in reasonable time.

III. DESIGN SPACE EXPLORATION
The combination of stream assignments and operation orderings can yield a tremendous number of valid implementations; too many to enumerate, much less explore. Even for the simple SpMV example described below there are 2036 implementations. Some implementation decisions have a large impact on performance, and some do not. Figure 1 shows this effect -certain decisions move an implementation from one performance regime to another, but many decisions have little effect. This work uses Monte-Carlo tree search to jointly explore the space of implementations, biasing the search to focus on regions of high performance impact, without needing the space to be enumerated a priori.
The proposed system is demonstrated using a distributed sparse-matrix vector multiplication, summarized in Figure 3, on the Perlmutter platform, summarized in Table I. The SpMV is distributed across four ranks in a single node (Figure 3b). The matrix A is a band-diagonal matrix with 150 000 rows/columns, 1 500 000 non-zeros and a bandwidth of 150000 4 . This bandwidth approximately balances the size of local and remote matrix multiplications (Sec. III-A). The non-zeros are uniformly randomly distributed within the band. GPU operations can be scheduled between two CUDA streams.

A. DAG Representation of CUDA + MPI operations
Consider an arbitrary CUDA+MPI program P . Program P contains operations that can depend on each other. In this sense, P defines a graph G P : the vertices of G P are the operations of P and the edges of G P are the dependencies between them. For example, if P consists of two operations and . and the latter can start only after the former completes, then G P is → .
To more precisely define "operations," we include Table II. An operation is either synchronous or asynchronous, and it can correspond to computation (e.g., CUDA kernel launches), communication (e.g., MPI point-to-point and collective functions), or other supporting instructions (e.g., MPI_Wait, cudaDeviceSynchronize). This is captures the predominant model for distributed GPU programming, where a CPU control thread offloads the bulk of the compute to asynchronous GPU operations, coordinated with asynchronous MPI communication, and interspersed with a small amount of synchronous CPU operations to marshal or organize data.
Our work pertains only to programs P for which G P is a DAG (i.e., for which G P is directed and acyclic). If P has an unbounded loop, G P is not a DAG, but the system can be applied to the loop body in isolation, or a fixed number of unrolled iterations. The dependence graph G P of our SpMV example is a DAG; see Figure 3c. Consider multiplication of sparse matrix A with vector x to produce vector y shown in Figure 3. A common distributed memory implementation evenly divides contiguous rows of A, x, and y evenly across MPI ranks. A rank's y entries can then be computed as the sum of a "local" and "remote" matrix-vector multiplication y L = A L x L and y R = A R x R , as in Figure 3b. A L has the column entries of A that correspond to x L , the locally-held rows of x; A R has the rest, corresponding to x R , the rows of x held by other ranks. Thus, A L x L can be computed directly, but A R x R must wait for x R to be assembled from the remote x entries that correspond to non-zero columns in A R .  In this formulation, A is considered to be static, so the entries that make up x R are fixed. The values in those entries are not considered to be static, so each rank must copy a subset of its x L entries into one buffer for each other rank (the Pack vertex ). Communication is done with point-topoint MPI_Isends (PostSends vertex ) and MPI_Irecvs (PostRecvs vertex ).
The granularity of the operations is flexible. For example, SpMV could have been implemented with a set of parallel independent vertices for each separate pack and MPI Isend instead of collecting them into single Pack and PostSends vertices. This finer granularity would eliminate false dependencies between packing for one rank and sending to another, e.g. not being able to send to rank 1 before the pack for rank 2 is completed. The downside of this fine granularity is a larger space of implementations to search.
Artificial start and end vertices are added, where there must be a path from start to each vertex and a path from each vertex to end. Start serves as a single entry point for the program, and end as an artificial CPU operation to ensure all program operations have completed before the program completes.
A non-trivial program will have some degree of flexibility with respect to the actual order of operations. For example, in Figure 3c, one valid execution sequence is ---------. Another is ---------.

B. CUDA+MPI Programs as a Sequential Decision Problem
In the general case where some operations are asynchronous and may execute in parallel, it is not possible to evaluate the performance of a partial program sequence, nor is it possible to look at a set of operations with finished predecessors and choose the successor from among them that will ultimately result in the fastest execution. Only with the entire program sequence in place can the performance be determined.
Recall that G P is a DAG whose vertices are the operations of a CUDA+MPI program P and whose edges are the dependencies of these operations. A topological traversal of G P specifies P , where all dependencies of a vertex are completed before the vertex is executed. We address the following problem: Given G P and an objective function f , we seek a traversal of G P for which f is minimal. In other words, we seek the complete program which respects the operation dependencies in the DAG and minimizes some objective function (e.g. execution time, our specific function is described in Sec. III-C1). More formally, we seek a traversal P * that solves where P is the set of traversals of G P . In the SpMV example, f (P ) is the expected runtime of P , but a different f could be of interest depending on the application. Solving (1) exactly is intractable for G P and f that arise in practice. We therefore reformulate (1) as a sequential decision problem [25]. The reformulation is equivalent to (1) and is also intractable, but in the sequential decision paradigm, P * is constructed one vertex at a time, which is a natural way to construct a graph traversal.
To introduce the sequential decision alternative to (1), we first describe its states. Let P k be a prefix of length k; P k is a list of k vertices from G P that could later be extended into a complete traversal (i.e., to an element in P). Since the DAG G P has a finite N vertices, the prefix P k should have at least k ≥ 0 and no more than N vertices (at which point it is a complete traversal from P).

C. Monte-Carlo Tree Search for CUDA+MPI Programs
To compute P * k (the length k prefix of an optimal program P * ), we must know the optimal performance of all programs beginning with all prefixes having length not greater than k. Deriving this information is infeasible in general. Were we to have it, however, computing P * k from P * k-1 would be trivial: we would append to P * k-1 a vertex that preserves the best possible performance of programs beginning with P * k-1 (which is f (P * ) by definition). We refer the reader to [25], [26] for introductions to this sequential decision making paradigm.
Monte-Carlo tree search is a technique that approximates this exact yet infeasible construction of P * by estimating the optimal performance of the most impactful prefixes. It stochastically approximates P * while estimating the optimality of various P k along the way. The state of the search is represented as a tree, where each tree node is an operation from the DAG and the ancestors of that node represent the prefix P k taken to get there. The tree is built through four iterated phases: selection chooses the subtree to explore, expansion increases the information stored about that subtree, rollout estimates optimality of P k , and backpropagation stores that information in the tree. For MPI programs, MCTS is executed on only a single rank, with all ranks participating in the empirical measurement of the program.
1) Selection: A heuristic is used to favor exploring subtrees that feature larger observed performance ranges. Starting with the root, children are recursively selected by maximizing an explore/exploit value. The exploration value is defined as c ln N n , where c = √ 2 is the exploration parameter, N is the number of rollouts in which the tree node participated, and n is the number of rollouts the child has participated in. If the child subtree has been fully explored (all possible descendants have been benchmarked), the exploration value is set to negative infinity. The exploitation value is given by where t c max and t c min are the maximum and minimum time observed in the child subtree, and similarly t p max and t p min for the parent subtree. The intuition is to favor child nodes with times that represent greater coverage of the parent's execution times. Since all child subtree times are contained in the parent subtree, 0 ≤ V ≤ 1. If a child or parent has not recorded two executions in its subtree, there is no basis for comparison and 1 is used.
The combined value is the sum of the exploration and exploitation components and the largest value is selected. The recursive search terminates at any node that has a child with no rollouts.
2) Expansion: A zero-rollout child of the node chosen by the selection phase is created. This allows the search algorithm to retain additional information about this high-value region of the implementation space discovered during selection. The selected node corresponds to a P k , which is used to select the possible next operations based on the DAG. The set of next operations is all vertices v in G P not in P k and where all predecessors are in P k , with two additional considerations.
First, any GPU-type vertices in G P must be converted to BoundGPU vertices by assignment to a CUDA stream. In principle, each GPU vertex is replaced with one BoundGPU vertex for each stream; however, multiple available streams can introduce redundancy to P. For instance, if P is defined on two equivalent streams s 1 and s 2 , then the P that arises from swapping all assignments to s 1 and s 2 should attain the same value of f . To circumvent this redundancy, any children that represent equivalent P k under a stream bijection are pruned from the tree.
Second, the DAG does not require synchronization operations to be explicit. Therefore, some prefixes may require synchronization operations before proceeding to the next vertex of G P . For example, in Figure 3c, edge → requires a synchronization operation because the GPU kernel in must complete before the MPI operations in can start. Table III summarizes when and how synchronization operations arise. These synchronization operations depend on P k , not the DAG, so they cannot be inserted in a preprocessing step.
3) Rollout: The performance of the subtree rooted at the node created in the expansion phase is estimated. As described in Section III-B, the optimality of P k is not directly available. Therefore, it is estimated by constructing a complete P , with prefix corresponding to the expanded node. Recursively, random children are selected until the operation sequence is complete.
The generated P is broadcast to all ranks. Benchmarking is done in terms of measurements and samples. Each sample is a single invocation of P , and each measurement corresponds to a single estimate of the time taken to execute P . A measurement is generated by starting a timer and repeating n samples samples until a time t measure of 0.01 s has elapsed. The time for P is estimated as the maximum tmeasure n samples across all ranks. The empirical performance measurements are recorded and stored alongside the selected sequence to use for rule generation (Section IV). The nodes corresponding to this random rollout are constructed and added to the tree as well to retain their performance information.

4) Backpropagation:
The results from the rollout are propagated to each ancestor node along the rollout path. Each node tracks the fastest (t min ) and slowest (t max ) times observed during rollouts in the subtree rooted at that node. If a rollout in the subtree produces an empirically measured time t, then each node along the path is updated as t min ← min(t, t min ) and t max ← max(t, t max ).

IV. DESIGN RULE GENERATION
After MCTS has explored interesting regions of the implementation space, the empirical performance of those implementations is used to generate design rules for different performance classes. Recall that during the MCTS rollout, the empirical time for each generated P was recorded along with P itself. This records the performance of various points in the design space, biased towards regions of the design space where there is greater performance variability, i.e., where design decisions have a larger impact.

A. Generating Class Labels
The traversals explored during MCTS are grouped into classes according to their performance. Figure 4 summarizes the automatic class labeling process. First, the benchmark data is sorted least to greatest (Figure 4a). Then, the benchmark data is convolved with a step function with a radius r, given by is computed for all i where r < i < length(a) − r, i.e., only where the convolution kernel completely overlaps with the array a. The radius of the step function is set to 0.5% (minimum 1) of the number of measurements to screen  Figure 4b. The convolution result has a peak where the sorted performance measurements take a large increase. Peaks are detected through a simple comparison with neighboring values [27], [28]. Small peaks and corresponding small time increases can be screened away by choosing only the most prominent peaks. In this work, only peaks above the 98th percentile of prominence are kept. Thus, the number of performance classes need not be known a priori. Each peak location is used as a boundary between performance classes (Figure 4c). Each traversal sequence is then labeled with the corresponding class.

B. Generating Feature Vectors
Each traversal is transformed into a fixed-length vector of ordering and stream assignment features. An ordering feature is defined for each pairwise combination of traversal operations u and v. This feature is 1 if u appears in the traversal before v, and 0 otherwise. Similarly, a stream assignment feature is defined for each pairwise combination of BoundGPU operations. This feature is 1 if u and v occur in the same stream, and 0 otherwise. Many of these feature entries will have the same value for all traversals, e.g. u will precede v in all traversals if u → v in the program DAG. Such features are removed from the resulting vectors as they provide no discriminatory power for different sequences.

C. Decision Tree Training
The scikit-learn python package [29] is used to train a decision tree using the class labels and feature vectors. scikitlearn implements the CART algorithm [30]. Training involves several hyperparameters summarized in Table IV.
Ultimately, the paths to leaf nodes of the decision tree are used to determine discriminatory features of each class of sequences. Therefore, a maximally-accurate decision tree is desired, without concern for overfitting. The number of leaf nodes of the tree is initially set to the number of classes, and iteratively increased until classification error no longer shrinks. Algorithm 1 produces the decision tree classifier clf. "train()" is a function that takes max_leaf_nodes as an argument, and trains a tree with the provided max_leaf_nodes and max_depth = max_leaf_nodes−1 and returns an (error, classifier) tuple.
Algorithm 1 Decision tree hyperparameter search producing classifier clf.
mln ← 2 max leaf nodes err ← ∞ training error cur, clf ← train(mln) error, classifier tuple while cur < err do err ← cur for i in 1 to 5 do try increasing tree size cur , nclf ← train(mln + i) if cur < err then better hyperparameters clf ← nclf mln ← mln + i break end if end for end while Figure 5 shows the result for the sample problem, ultimately settling on 13 nodes with a tree depth of 6.

D. Rule Generation
The design rules that define each performance class can be determined by all paths through the decision tree that arrive in a leaf node that contains that performance class. Figure 6 shows an intermediate decision tree discovered during the iterative parameter search process in Section IV-C. (The full tree is unwieldy to display, but the procedure described below is the same.) "Samples" refers to the number of training samples that fall into a particular box. "Classes" describes what proportion of the samples fall into each class. The path from the root node to describes the design rules that will place an implementation into that leaf node. For node , those rules are: 1) "y L before CES-b4-PostSend": CES-b4-PostSend is an inserted (and automatically named) synchronization operation before PostSend. The local multiplication should occur before that inserted synchronization. 2) "y L , Pack in different streams": the local multiplication and pack kernels should be in different streams 3) "Pack before y L ": the Pack operation should be launched before the local multiplication Note that leaf node provides an alternate set of rules for ending up in the same performance class. provides rules for implementations in the intermediate class, and and in the slowest class. Finally, it is possible that the features cannot perfectly discriminate a class (). In this case, it is because the intermediate tree was not allowed enough leaf nodes.

V. EVALUATION OF MCTS
Prior sections evaluated the techniques on an exhaustive search of the solution space for the provided SpMV. The class labels and rules were generated from the complete 2036 possible traversals. For larger applications, such a comprehensive search is not possible, and design rules must be generated from a subset of the search space. The given number of MCTS iterations is used to create class labels, each with an associated performance range. That decision tree is used to classify all possible implementations Accuracy is given as the proportion of implementations with performance that falls within the label's range, i.e., how well using only a subset generalized to the entire space. The effect of MCTS are explored by examining how the discovered design rules change as more of the search space is explored. Table V summarizes the quality of the design rules depending on how many MCTS iterations are allowed. The provided number of MCTS iterations executes, yielding a reduced set of traversals and corresponding execution times. Features and class labels are generated from the subset of samples. Each class defines a performance range, from the slowest sample in the class to the fastest. The entire space of 2036 implementations is then classified using the rules derived from the reduced subset, and the proportion that fall within the performance range is reported. As the number of MCTS iterations increases, the accuracy of design rules for classifying the design space increases, up to nearly 100% at 200 iterations.
A qualitative way of examining the results is presented in Tables VI, VII, and VIII, which summarize the design rules generated for each performance class. Each column of the table displays the generated rulesets that discriminate a given performance class, and each cell in the column corresponds to a different path through the decision tree to that class. When there are multiple paths to the same performance class, the cells in a column may be mutually contradictory. For example, the first and third cell in the 2036 column of Table VI have different rules for whether the Pack and y L operations should be in different streams. However, each ruleset prescribes the necessary conditions for an implementation to be in a performance class; as long as all rules in a given ruleset are followed, other decisions do not matter. The cells are sorted top-to-bottom by the number of training samples that followed those rules. For brevity of presentation, only the three rulesets with the most samples are shown for each case.
The rules generated for the full SpMV traversal (rightmost column, having 2036 implementations) are taken as the canonical, accurate rules since they reflect classification of all possible implementations. The cells are annotated with information about their consistency with these canonical rules. In an ideal system, each cell in a column would correspond directly to one cell in column 2036 (though not necessarily the entry in the same row); however, two kinds of inconsistencies  First, a ruleset may be overconstrained, or consistent with the canonical rules but with additional harmless restrictions. This is highlighted in blue in each cell. Table VI shows that for the fastest performance class, the rules discovered by fewer MCTS iterations tend to be overconstrained, with almost all rulesets featuring at least one spurious rule. Second, a ruleset may be underconstrained; i.e., it does not restrict the order and assignment of operations sufficiently to fit within the comprehensive search rules. The two slower performance classes (Tables VII and VIII) suffer from this problem. Relatively few rules are completely accurate; most are missing at least one constraint. This is annotated in red in each cell. Although most cells have an error, they are typically "almost" correct when compared to the rules generated from the full traversal (column 2036).
There are two ways to use these rules. First, program implementors may take any ruleset that corresponds to the desired performance class and follow the rules in their implementation. Doing so will ensure the performance of the implementation falls within that class. Second, implementors can analyze the rules to gain deeper insight into the properties of the implementation.
Additional study is necessary to determine why class 1 behaves so distinctly from classes 2 and 3, and why the quantitative accuracy is so high ( Figure V) despite the inconsistencies in textual rules. It may be that the inaccuracies in the rulesets are enough to prevent a perfect match with the rulesets for the exhaustive search, but are not so significant that they push a program P into the wrong class very often.

VI. FUTURE WORK
Substantial work is required to increase the capabilities of the system, as well as understand the quality of the results. Results have been presented for only a single program (SpMV) on a single platform (Perlmutter with two streams per GPU) with a single input (the synthetic banded matrix). Initial results suggest that the prototype is working well, but examination across additional platforms, programs, and inputs is required. A natural extension is to generate rules that generalize across inputs. This extension requires changes to the feature-vector generation to include features that discriminate between inputs. The work is currently being extended to 3D halo-exchange communication modeling fine-grained communication operations in each dimension. Also of interest is extending resource assignment to include multiple GPUs or NUMA nodes, instead of solely GPU streams.
It is clear that the decision tree hyperparameters affect the generated rules and their interpretability. Tables VI, VII and VIII already suggest that interpreting the design rules may be challenging. Currently, the most discriminating decision tree is sought; however, that objective may negatively impact the complexity and number of generated rules. Additional work in feature vector generation and decision tree training parameters may increase the quality of the generated rules.
Finally, the MCTS search strategy preferentially explored design-space areas with high performance impact. Other MCTS strategies should be considered, at least as a baseline for comparison. For example, a search strategy that randomly samples the design space could be used to show that the current strategy indeed produces better results.

VII. CONCLUSION
This work presents the design and initial evaluation of a system to generate design rules for CUDA + MPI operations. It takes as input a DAG representation of the program, which is used in a Monte-Carlo tree search exploring performancesensitive regions of the design space. Performance classes and implementation features are derived from the results of the design space search, and then converted to textual rules. Program developers can use these rules to understand which aspects of their program most impact the program's performance.
Evaluation is limited to a specific CUDA+MPI sparsematrix vector multiplication; additional work is needed to verify and extend the functionality of the system. Of particular TABLE VI: Design rules that define performance class 1 generated for various MCTS iterations. The three rulesets generated for 2036 iterations are taken as canonical. All rulesets generated with fewer search iterations are consistent with one of the canonical rulesets. Rules highlighted in blue are extraneous, but do not violate a ruleset. 50 100 200 400 2036 y L before CES-b4-PostSend y L different stream than Pack Pack before y L y L before CES-b4-PostSend y L different stream than Pack Pack before y L y L before WaitSend y L before CES-b4-PostSend y L different stream than Pack Pack before y L y L before WaitSend y L before WaitRecv PostSend before y L Pack before y L CER-after-Pack before y L y L before WaitSend PostRecv before CES-b4-PostSend y L before CES-b4-PostSend y L different stream than Pack Pack before y L y L before CES-b4-PostSend Pack same stream as y L CER-after-Pack before y L y L before CES-b4-PostSend Pack same stream as y L CER-after-Pack before y L y L before WaitSend y L before WaitRecv CES-b4-PostSend before y L y L before WaitRecv PostSend before y L y L before WaitSend Pack before y L PostRecv before CES-b4-PostSend y L before WaitRecv Pack before y L CER-after-Pack before y L y L before WaitSend y L before PostSend y L before CES-b4-PostSend CES-b4-PostSend before y L y L before WaitRecv PostSend before y L PostRecv before PostSend y L before WaitSend y L before WaitSend y L different stream than Pack Pack before y L CES-b4-PostSend before y L PostSend before y L y L before WaitRecv PostRecv before PostSend y L before CES-b4-PostSend Pack same stream as y L CER-after-Pack before y L y L before WaitSend Pack before y L y L before WaitRecv Pack before y L y L before CER-after-Pack y L different stream than Pack y L before CES-b4-PostSend Pack same stream as y L CER-after-Pack before y L WaitSend before y L yr different stream than y L insufficient rules WaitRecv before y L yr different stream than y L insufficient rules CES-b4-PostSend before y L WaitRecv before y L yr different stream than y L y L different stream than Pack Pack before y L CES-b4-PostSend before y L y L before yr insufficient rules y L before WaitSend y L different stream than Pack Pack before y L CES-b4-PostSend before y L y L before PostSend insufficient rules y L before WaitSend y L before Pack Pack different stream than y L PostRecv before Pack insufficient rules y L before WaitSend y L before Pack Pack different stream than y L PostRecv before Pack insufficient rules CES-b4-PostSend before y L y L before WaitRecv y L before PostSend Pack same stream as y L CER-after-Pack before y L CES-b4-PostSend before y L insufficient rules y L before WaitSend Pack same stream as y L CER-after-Pack before y L y L before WaitRecv CES-b4-PostSend before y L y L before PostSend CES-b4-PostSend before y L y L before PostSend y L before WaitSend Pack before y L insufficient rules CES-b4-PostSend before y L y L before WaitRecv y L before PostSend Pack before y L CER-after-Pack before y L y L before WaitSend CES-b4-PostSend before y L y L before WaitRecv PostSend before y L PostSend before PostRecv y L before WaitSend note is modifying the system to support generalized design rules across multiple inputs, and improving the rule generation and interpretibility. For the limited scope of the current evaluation, the prototype produces promising results. Pack same stream as y L y L before CER-after-Pack insufficient rules y L before WaitSend Pack same stream as y L y L before CER-after-Pack y L before WaitSend y L before Pack Pack same stream as y L WaitRecv before y L yr same stream as y L y L before CES-b4-PostSend Pack same stream as y L y L before CER-after-Pack CES-b4-PostSend before y L WaitRecv before y L Pack before y L Pack same stream as y L insufficient rules WaitSend before y L yr same stream as y L insufficient rules WaitSend before y L yr same stream as y L insufficient rules y L before WaitRecv y L before Pack Pack same stream as y L CES-b4-PostSend before y L WaitRecv before y L yr same stream as y L CER-after-Pack before y L WaitRecv before y L y L before WaitSend Pack same stream as y L insufficient rules y L before CES-b4-PostSend Pack same stream as y L y L before CER-after-Pack y L before WaitSend Pack before y L y L before WaitRecv y L before CER-after-Pack Pack same stream as y L Pack before y L insufficient rules CES-b4-PostSend before y L y L before WaitRecv PostSend before y L PostRecv before PostSend WaitSend before y L yr same stream as y L CES-b4-PostSend before y L WaitRecv before y L yr same stream as y L y L before WaitSend Pack before y L PostSend before y L y L before WaitRecv CER-after-Pack before y L WaitSend before y L yr same stream as y L Pack before y L insufficient rules