| Computer Architecture Research Gallery |
| Everybody likes computer graphics because it looks cool. You can see the picture and say "wow, now that looks like a real piece of flaming toast". Traditionally, computer architecture has pretty much the opposite effect. The common perception is that computer systems is all about hacking and tweaking to get 10% bigger or (dare I say) smaller bars. Instead I want more people to see that computer architecture is a field ripe with opportunity to mix algorithms, machine learning, circuit design, theory, and systems all together for the purpose of building faster, cheaper, and more power efficient machines. This page is my humble attempt to try and show some neat looking results from my own computer architecture research. While these pictures may not be as appealing as a chrome teapot, they are both useful and visually appealing (or maybe I have been staring at them too long). |
| Run Time Behavior and Phase Changes |
This is a graph of a bunch of different statistics (if you care it's L2 cache misses,
energy, L1 cache misses, I cache misses, bpred, and IPC) taken a little steps during a run
of a program (the program is gzip). If you notice, all of these parts of the processor
change behavior at the same time. Each of these shifts in behavior we term a phase change. We can even color each different phase with the colors shown to indicate the major repeating patterns. These phase changes have ramifications to any optimization we might want to apply, from the operating system all the way down to the way the architecture is designed. |
| Similarity Matrix |
This picture is a visualization of the repeating patterns found within an
executing program. This program is gzip (a compression program). "Time" runs
along Diagonal axis in terms of instructions executed. When you run gzip it
executes over 100 billion instructions which is why the axis goes over 100
billion. In many programs, such as this one, the program will change from one
behavior to another behavior and then back again. This graph let's you
visualize where these patterns are.
You may want to know: for two given points in time, is the program behaving
more or less the same or is it doing something completely different. On this
graph, you can compare 2 points by going horizontal from one and vertically
from the other. The darker the point the more those two points in the program
are similar to one another. For example, if you want to know how similar the program is after 50 billion instructions to the program after running 70 billion instructions, you trace horizontally from 50B, and vertically from 70B and you find that they are quite similar (the red arrows). If you compare the instructions at 50B to those 80B you will find that they are almost unrelated (the blue arrows). Where and when will there be drastic changes? Can we detect them? Can we predict them? The answers to these questions will help us design better software and hardware systems. |
| Similarity Matrix of gcc |
You read this the same way you would read the last matrix, tracing horizontally and
vertically to find how similar two regions of a programs execution are to one another.
Each dark box (circled in red) shows a period of time where the program is doing more or
less the same stuff. The dark box in blue shows that the the two different sections highlighted in red are both similar to one another. The program has repeating behavior even though it is not doing exactly the same thing. This means that we can build systems that not only adapt to program behavior more effectively, but that we can even predict what future behaviors will be.
|
| Automatically finding phase changes |
Using some machine learning techniques (clustering) we can build a system that can
automatically discover phases. This graph shows some statistics from an executing program
(gcc again), and the colors represent the phases that my techniques found automatically.In fact these phase were found without even looking at any of these statistics (which can be hard to gather at runtime) but rather with a new technique called basic-block distribution analysis
|
| Phases in Multi-threaded programs |
Not only single threaded programs have interesting phase behavior. This graph shows how
automatic phase classification can be used to identify repeating behaviors in a
multi-threaded Microsoft application.As the program executes, you can see how different threads are being used. At the startup, there are all kinds of threads doing different stuff.. But then it levels out and starts doing some serious work (the red phases). You can see that the red phase is interleaving with the yellow phase, and that while the majority of the time the red phase in run by thread #20, sometimes it is run by thread #18. Getting this information without phase classification would be pretty darn hard. |
| Phase detection screen shot |
Always have to have a screenshot. This is a picture (click to enlarge) of run-time phase
identification software with a graphical front end (by Jeremy Lau). In this picture you
can see XV running a blur filter on a picture, and the corresponding phases all at runtime.
|
| Automatically designed predictors |
There are lots of little predictors all through current processors, so why not design them
automatically so that it takes less time, they are designed better, and we can use even
more of them?
This is a predictor that was automatically designed for one specific branch in a program.
Designing predictors for each branch certainly would not be possible if it was not
automatic.
This predictor predicts taken (denoted [1]) if and only if the last pattern of branches was
either 0x1x or 0xx1x. The x stands of a don’t care, so the pattern 0x1x means: you should
be able to start from any node in the graph, follow a edge marked with a 0 (they all have
such a path), then take an edge marked with either a 0 or a 1 (your choice), then a edge
with a 1, and finally one more edge of your choice. After doing all that, you should
always land on a node labeled with a [1]. Go ahead… try it (it’s fun for the whole family)
|