Wenhao Jia

Starchart

Statistical Tuning via Automatically- and Recursively-Constructed, Hierarchically-Applied Regression Trees

Overview

Starchart is a regression tree-based GPU hardware/software optimization tool. It can be used to explore the hardware/software design space of a parameterized GPU program. The regression tree theory is used to guide the design and implementation of Starchart. As a result, Starchart outputs a recursively partitioned design space represented in a tree format. Program design parameter significance and interaction are considered to guide the partitioning process.

Please read the Starchart paper to understand how it works. Even though the paper was written using GPU programs as examples, Starchart as a tool and the ideas behind it may be applicable to a wider range of platforms and architectures.

If you use our code or results in your project, please cite our Starchart paper below.

Starchart: Hardware and Software Optimization Using Recursive Partitioning Regression Trees
Wenhao Jia, Kelly A. Shaw, Margaret Martonosi
Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques (PACT '13)

Download

The GitHub repository for Starchart is located here.

You can either go to the repository page and click Download ZIP on the right, or use the following command to clone a copy to your local disk.

git clone https://github.com/jiawenhao/Starchart.git

In the downloaded archive, only starchart_1.0.tar.gz will be used for this tutorial. The other files are provided in case you want to modify Starchart's source code.

Usage

The following tutorial walks through the process of applying Starchart to one of the examples in the original Starchart paper. By the end of the tutorial, you will learn how to load, run, and view the output of Starchart for your own applications you need to tune.

Preparation

If you haven't yet, please go and read the Starchart paper. This will make a lot of the concepts below easier to understand.

Starchart is written in R, so some experience with the R language and software environment would be helpful. A common recommendation for learning R is to read this introductory document. However, R is a very high-level language that is fairly self-explanatory, and we definitely don't use most of its features. Therefore, if you don't need to modify Starchart's source code and just want to use it, very minimal knowledge about is R is needed. To help with that, I will try to explain the commands we use in the rest of the tutorial.

Download and install R from its official website or with whatever package manager your operating system supports. Before we launch R, let's first make sure Starchart is properly installed. This will be done outside of R.

Pick a current work directory to put all your data and R scripts, such as ~/R. Put the downloaded Starchart package (starchart_1.0.tar.gz) in that directory. Open a terminal window and cd to the work directory. Run this command to install Starchart as a system (or personal) library:

R CMD INSTALL starchart_1.0.tar.gz

If you ever want to delete Starchart from the system (or personal) library path, use this command outside of R and in a terminal window:

R CMD REMOVE starchart

Now, make sure you have Starchart installed, and you can launch R by typing R (a single capitalized letter!) into the terminal window and pressing Enter. A > sign will appear for you to input interactive R commands. Type getwd() (with the parentheses!) and Enter to see the current work directory. If you haven't changed work directory outside of R, it should show the same work directory. For the rest of the tutorial, I will assume the current work directory is ~/R. To quite R, execute quit().

Type ? followed by a command name (e.g. ?getwd) in R to get help on that command. In fact, you can use ? to get help on any R keyword (e.g. ?NaN), not just commands. Make good use of it!

Constructing a Starchart Tree

Load the package with the following R command:

library(starchart)

As part of the package, the main Starchart function—starchart(…)—will be loaded into memory. The package also ships with an example data set—kmeans—which can be loaded with this command:

data("kmeans")

Take a look at the example data with the following command:

print(kmeans)

This data frame contains 500 rows and 5 columns (not counting the sequential ID column). The first few rows are shown below.

ppb tpp consec runtime wattage
1 13 13 1 0.0983674 206.5
2 16 11 1 0.1191526 201.2
3 14 12 0 0.1173948 209.2

Each row represents a particular implementation (i.e. a sample or sampled design) of the swap kernel from the Kmeans program in the Rodinia benchmark suite. The first 3 columns are program design parameters, which take randomized values, and the last 2 columns are the measure performance (in seconds) and power usage (in watts) of each corresponding program instance. The explanations of the columns are listed below.

ppb
The number of points processed by each thread block (points-per-block).
tpp
The number of threads threads processing each point (threads-per-point).
consec
Whether cooperating threads should access point dimensions consecutively.
runtime
The measured runtime of this particular kernel instance.
wattage
The measured whole-system power usage of this particular kernel instance.

Section II of the Starchart paper has more detailed description this kernel and its design parameters. Take a look at these 500 rows and try for yourself whether you can spot which design parameters have the highest influence on performance or power of this kernel. It's really difficult to see any trend without proper tools, isn't it? This is where Starchart comes into play.

Let's say we want to know how the performance (i.e. runtime) of the swap kernel from the Kmeans program is determined by the 3 program design parameters. We just need to construct a Starchart tree with the following command:

tree = starchart(kmeans[1:200, 1:3], kmeans[1:200, 4])

This should take only a few seconds. What this command does is it tells Starchart to use the first 3 columns (i.e. the 3 design parameters) of the first 200 samples to predict the 4th column (i.e. the runtime) of the same 200 samples.

In R, a data frame (such as the kmeans variable we use here) can be thought of as a two-dimensional table of data. We can use brackets to select a subset of its rows and columns in this form: [first_row(:last_row), first_column(:last_column)]. The parentheses mark optional parts and shouldn't be typed out.

More generally, a Starchart tree can be constructed using this command:

starchart(x, y)

Consistent with R naming conventions, x is a data frame containing predictor variables (also called independent variables), and y is a vector containing response variables (also called dependent variables). The number of rows in x must match the number of elements in y, representing individual samples (i.e. specific program instances). x can have one or more columns, corresponding to program design parameters, and y must be one-dimensional.

Examining a Starchart Tree

Now that we have a Starchart tree, we can view a summary of this tree:

summary(tree)

R should show a simple summary of the queried tree:

Call: starchart.default(x = kmeans[…], y = kmeans[…]) Number of nodes: 67 Number of leaf nodes: 34

We can also see the complete tree structure by running this command:

print(tree)

The output should look like this:

Printing a Starchart tree, one node per row: splitParameter splitThreshold leftChild rightChild 1 tpp 1 2 3 2 ppb 129 4 5 3 tpp 2 6 7 … … … … …

This is a little tricky to read. Because R doesn't have native support for pointers and structures, a Starchart is internally represented as several vectors (i.e. columns in the output above) that mimics a tree data structure. A tree always starts with the root node on the first row. In the output above, the root node splits all 200 samples based on their tpp values (row 1 of splitParameter): those samples that have tpp values less than or equal to 1 (row 1 of splitThreshold) belong to the left child node, and those samples that have tpp values greater than 1 belong to the right child node. Meanwhile, the root node's left child node is described by the 2nd row (row 1 of leftChild), and its right child node is described by the 3rd row (row 1 of leftChild). Reading the 2nd and the 3rd of the output above, we can continue to interpret the tree structure.

Clearly, this is not the easiest way to read a tree, but it does give the most complete information about a tree should one read it slowly and patiently enough.

In fact, we can examine the tree in a much easier and more visual way:

plot(tree)

A window will pop up that shows an overview of the whole tree:

In the visualization, splits are shown as internal tree nodes. Leaf nodes represent final design space partitions. They are shown in the form N [mean], where N is the number of samples in that design partition (subspace) and mean is the average response (or runtime in our case) of all samples in that partition.

Trying to show all tree nodes in the same graph may look a little crowded, and thus we can choose to show only the top 5 splits (nodes) with this command:

plot(tree, top.splits = 5)

The resulting tree looks a lot bigger and easier to read. However, note that this mini tree has the same structure as the top 5 nodes in the previous full graph.

Finally, with the additional white space, we can also plot split conditions on each edge:

plot(tree, top.splits = 5, edge.labels = TRUE)

This results in a tree with even more information:

For example, we can easily see that a tpp value of 1 results in the worst (longest) runtime and a tpp value greater than 8 results in the best runtime.

It may not be immediately obvious, but the height of a node in a Starchart corresponds to the significance of the split this node represents. Specifically, the higher a node is in the tree, the more sum-of-squared-error reduction it contributes in the tree building process. Refer to Figure 3 in the Starchart paper for more details.

Using a Starchart Tree

A Starchart tree summarizes the high-level, subspace-dependent performance/power trend of a program's design space in a nice and easy-to-visualize way, and it can be used in many ways to directly answer many design questions when these questions are well formulated as proper design parameters. However, the most straightforward way of using a Starchart is simply using it to predict the performance/power of a number of unknown designs.

For example, let's use this command to predict the performance of the 201st to 250th samples in the kmeans data set:

estimates = predict(tree, kmeans[201:250, 1:3])

Now plot the predicted runtimes and the actual runtimes on the same figure with this command (just copy and paste it):

barplot(t(data.frame(estimates, kmeans[201:250, 4])), beside = TRUE, legend.text = c("predicted", "actual"), xaxt = "n", ylab = "Runtime (s)")

This is the result:

Note that when making a prediction, Starchart does not have any access to the actual runtime of a sample. Compare these two groups of bars, the predictions are quite accurate, aren't they?

Try Starchart on Your Own Data!

Since you've learned how to use Starchart on one of the paper examples, it's time to try it on your own data. Note that Starchart doesn't have to be applied to only GPU tuning problems: nothing in its design prevents it from being used on a wider range of programs, architectures, and measurements.

The hardest part about using Starchart may be acquiring your own data to analyze. After all, running and collecting results from hundreds of runs could be very tedious. Thus, I'm offering my own research scripts as an example for how you might write your own scripts to automate these experiments. Download the code here, and take a look at its README file. This file is a small part of one of my current research projects. It is NOT a part of Starchart and is not as well maintained/commented. If you happen to have a current generation NVIDIA GPU to execute the OpenCL microbenchmark in the archive, you can try running the commands listed in README. Otherwise, use it as an example to jump start your own automation scripts for your own performance/power/other design space exploration experiments!

Final Words

Thank you for following the tutorial through to this point. If you find any bugs or have any comments for making the Starchart code or tutorial better, please don't hesitate to contact me using the links on the right of this page.

If you are familiar with R, please consider reading the Starchart source code yourself. There are a few convenient features that aren't mentioned in this tutorial but may potentially ease your own use of Starchart!

This article was last updated on 2/23/2014.