The Magical Paper Submission

Memory Scheduling Championship Wrap-Up

The MSC Workshop was last week at ISCA, featuring a strong set of presentations.  The MSC webpage has all the final results and papers.  Congrats to the winners of each track!  Thanks to Zeshan Chishti and Intel for sponsoring the trophies and award certificates (pictured below with the winners of each track).  Numerically speaking, the workshop had about 30 attendees, we received 11 submissions, and the USIMM code has received 1254 downloads to date (261 downloads for version 1.3).

Ikeda et al., Winners of the Performance Track.

Fang et al., Winners of the Energy-Delay Track.

Ishii et al., Winners of the Performance-Fairness Track.

Some important take-home messages from the competition:

1. It is nearly impossible to win a scheduler competition that implements a single new idea.  A good scheduler is a combination of multiple optimizations.  All of the following must be carefully handled: read/write interference, row buffer locality, early precharge, early activates, refresh, power-up/down, fairness, etc.  The talk by Ishii et al. did an especially good job combining multiple techniques and breaking down the contribution of each technique.  During the workshop break, some of the audience suggested building a Franken-scheduler (along the lines of Gabe Loh's Frankenpredictor) that combined the best of all submitted schedulers.  I think that idea has a lot of merit.
2. If I had to pick a single scheduling artifact that seemed to play a strong role in many submitted schedulers, it would be the smart handling of read/write interference.  Because baseline memory write handling increases execution time by about 36%, it offers the biggest room for improvement.
3. Our initial experiments seemed to reveal that all three metrics (performance, energy-delay, and performance-fairness) were strongly correlated, i.e., we expected that a single scheduler would win on all three metrics.  It was a surprise that we had different winners in each track.  Apparently, each winning scheduler had a wrinkle that gave it the edge for one metric.

The USIMM simulation infrastructure seemed to work well for the competition, but there are a few things we'd like to improve upon in the coming months:

1. The current processor model is simple; it does not model instruction dependences and assumes that all memory operations within a reorder buffer window can be issued as soon as they are fetched.  Adding support to model dependences would make the traces larger and slow down the simulator (hence, it wasn't done for the competition).
2. We have already integrated USIMM with our version of Simics.  This automatically takes care of the dependency problem in the previous bullet, but the simulations are much slower.  In general, reviewers at top conferences will prefer the rigor of execution-driven simulation over the speed of trace-driven simulation.  It would be worthwhile to understand how conclusions differ with the two simulation styles.
3. The DRAMSim2 tool has an excellent validation methodology.  We'd like to possibly re-create something similar for USIMM.
4. We'd like to augment the infrastructure to support prefetched data streams.
5. Any new scheduler would have to compare itself against other state-of-the-art schedulers.  The USIMM infrastructure already includes a simple FCFS and an opportunistic close page policy, among others.  All the code submitted to the competition is on-line as well.  It would be good to also release a version of the TCM algorithm (MICRO'10) in the coming months.

If you have an idea for a future research competition, please email the JWAC organizers, Alaa Alameldeen (Intel) and Eric Rotenberg (NCSU).

Introducing simtrax

The Hardware Ray Tracing group has just release our architectural simulator called simtrax. The simulator, compilation tools, and a number of example codes can all be checked out from the Google Code Repository. We have a couple tutorial pages on the simtrax wiki that will hopefully get you started.

Now you may be wondering at this point, what kind of an architecture does simtrax simulate. The answer is a number of different configurations of the architecture we call TRaX (for Threaded Ray eXecution), which is designed specifically for throughput processing of a ray tracing application. As such, the simulator is not well suited to a large number of application spaces, but does show quite good results for ray tracing, and would perform well on other similar applications.

In particular, the limitations built in to the TRaX architecture which are assumed by the simulator include the following:

• No cache coherence – at present the memory is kept coherent, but no simulation penalty is added to maintain coherence. We depend on code being written to not use coherence.
• No write caching – writes are assumed to write around the cache, and the lines are invalidated if they were cached, but again, no coherence messages are sent to the other caches in the system.
• Small stack sizes – each thread has a small local store for the program call stack. Recursion and deep call stacks can cause overflow or excessive thread-context size.
• A single global scene data structure – only load relevant data when it is needed by the thread.

The architecture we simulate is hierarchical in nature. First there are a number of independent, in-order, scalar thread processors. These are grouped in sets of (usually 32) that compose what is called a Threaded Multiprocessor (TM). While each thread processor has a few independent execution units, some of the larger, less-frequently-used units are shared among the threads in the TM. In addition, the TM shares a single L1 data cache and a number of instruction caches, both of which have multiple independent banks, which allows for independent fetching of distinct words. 

A number of TMs are grouped together to share access to an L2 data cache, which then manages the connection to the off-chip global memory. In a large chip there may be as many as 4 separate L2 data caches, while a smaller chip might do away with the L2 data cache altogether. The final piece of the puzzle is a small global register file with support for an atomic increment operation, which is used to give out thread work assignments.

This simulator has been in development for a number of years and has had a number of contributors involved in the project. In addition, we have taught a course using the simulation and compiler tools, and published 4 conference and journal articles, with more in progress.

We hope this simulation tool can be useful and intend to do what we can to support it. Feel free to email us and post bug reports on the google code page.

USIMM

We've just released the simulation infrastructure for the Memory Scheduling Championship (MSC), to be held at ISCA this year.

The central piece in the infrastructure is USIMM, the Utah SImulated Memory Module.  It reads in application traces, models the progression of application instructions through the reorder buffers of a multi-core processor, and manages the memory controller read/write queues.  Every memory cycle, USIMM checks various DRAM timing parameters to figure out the set of memory commands that can be issued in that cycle.  It then hands control to a scheduler function that picks a command from this candidate set.  An MSC contestant will only have to modify the scheduler function, i.e., restrict all of your changes to scheduler.c and scheduler.h.  This clean interface makes it very easy to produce basic schedulers.  Each of my students produced a simple scheduler in the matter of hours; these have been included in the code distribution as examples to help get one started.

In the coming weeks, we'll release a number of traces that will be used for the competition.  The initial distribution includes five short single-thread traces from PARSEC that people can use for initial testing.

The competition will be judged in three different tracks: performance, energy-delay-product (EDP), and performance-fairness-product (PFP).  The final results will be based on the most current version of USIMM, as of June 1st 2012.

We request that contestants focus on scheduling algorithms that are easily implementable, i.e., doable within a few processor cycles and within a 68 KB storage budget.  A program committee will evaluate the implementability of your algorithm, among other things.

We'll post updates and bug fixes in the comments section of this blog post as well as to the usimm-users@cs.utah.edu mailing list (sign up here).  Users are welcome to use the blog or mailing list to post their own suggestions, questions, or bug reports.  Email usimm@cs.utah.edu if you have a question for just the code developers.

Code Updated on 04/17/2012:

Code download: http://www.cs.utah.edu/~rajeev/usimm-v1.3.tar.gz

Changes in Version 1.1: http://www.cs.utah.edu/~rajeev/pubs/usimm-appA.pdf
Changes in Version 1.2: http://www.cs.utah.edu/~rajeev/pubs/usimm-appB.pdf
Changes in Version 1.3: http://www.cs.utah.edu/~rajeev/pubs/usimm-appC.pdf

USIMM Tech Report: http://www.cs.utah.edu/~rajeev/pubs/usimm.pdf

The contest website: http://www.cs.utah.edu/~rajeev/jwac12/

Users mailing list sign-up:  http://mailman.cs.utah.edu/mailman/listinfo/usimm-users

A Case for Archer

Disclaimer : The opinions expressed in this post are my own, based on personal experiences.

Almost any computer architecture researcher realizes the importance of simulators to the community. Architectural level simulators allow us to model and evaluate new proposals in a timely fashion, without having to go through the pain of fabricating and testing a chip.

So, what makes for a good simulator? I started grad school in the good old days when Simplescalar used to be the norm. It had a detailed, cycle-accurate pipeline model and most importantly, it was pretty fast. Once you got over the learning curve, additions to the model were fairly easy. It did have a few drawbacks. There was little support for simulating CMP architectures, there was no coherence protocol in place, and a detailed DRAM model was missing. Moreover, interference of the operating system with an application's behavior was not considered. But, these issues were less important back then.

Soon, it was apparent that CMPs (chip multi-processors) were here to stay. The face of applications changed as well. Web 2.0-based, data-intensive applications came into existence. To support these, a number of server-side applications needed to be run on backend datacenters. This made the performance of multi-threaded applications, and that of main memory of paramount importance.

To keep up with these requirements, the focus of the architecture community changed as well. Gone were the days of trying to optimize the pipeline and extracting ILP. TLP, MLP, and memory system performance (caches, DRAM) became important. One also could no longer ignore the importance of interference from the operating system when making design decisions. The community was now on the lookout for a simulation platform that could take all of these factors into account.

It was around this time that a number of full-system level simulators came into being. Off the top of my head, I can count a number of these, popular with the community and with a fairly large user base - Wind River's Simics, M5, Zesto, Simflex, SESC, to name a few. For community wide adoption, a simulator platform needed to be fast, have a modular code base, and have a good support system (being cycle-accurate was a given). Simics was one of the first platforms that I tried personally and found their support to be extremely responsive, which also garnered a large participation from the academic community. Also, with release of GEMS framework from Wisconsin, I didn't need a reason to look any further.

In spite of all the options out there, getting the infrastructure (simulator, benchmark binaries, workloads and checkpoints) in place is a time consuming and arduous process. As a result, groups seem to have gravitated towards simulators that best suited their needs in terms of features and ease of use. The large number of options today also implies that different proposals on the same topic inevitably use different simulation platforms. As a result, it is often difficult to compare results across papers and exactly reproduce results of prior work. This was not as significant a problem before when nearly everyone used Simplescalar.

In some sub-areas, it is common practice to compare an innovation against other state-of-the-art innovations (cache policies, DRAM scheduling, etc.). Faithfully modeling the innovations of others can be especially troublesome for new grad students learning the ropes of the process. I believe a large part of this effort can be reduced if these models (and by model I mean code :-) were already publicly available as part of a common simulator framework.

The Archer project, as some of you might know, is a recent effort in the direction of collaborative research in computer architecture. From the project's website, they strive for a noble goal -

"To thoroughly evaluate a new computer architecture idea, researchers and students need access to high-performance computers, simulation tools, benchmarks, and datasets - which are not often readily available to many in the community. Archer is a project funded by the National Science Foundation CRI program to address this need by providing researchers, educators and students with a cyberinfrastructure where users in the community benefit from sharing hardware, software, tools, data, documentation, and educational material."

In its current format, Archer provides a large pool of batch-scheduled computing resources, a set of commonly used tools and simulators and some benchmarks and datasets. It also has support for sharing files via NFS and a wiki-based infrastructure to aggregate shared knowledge and experiences.

If widely adopted, this will provide a solution to many of the issues I listed above. It can help push the academic community towards a common infrastructure while at the same time reduce the effort to setup simulation infrastructure and to reproduce prior work.

Although Archer is a great initial step, I believe it still can be improved upon. If I had my wishes, I would like a sourceforge like platform, where the model for a particular optimization is owned by a group of people (say, the authors of the research paper), available to be checked out from a version-control system. Anyone using the Archer platform for their research, that results in a peer-reviewed publication would be obliged to release their model into the public domain under a GPL. Bug reports will be sent to the owners who will in turn release revised versions of the model(s).

In recent years, collaborative research efforts in computer science have been very successful. Emulab is a widely used resource by the networking community. The TCS community too has been involved in successful collaborative research, e.g. the polymath project and the recent collaborative review of Deolalikar's paper. I believe that there is certainly room for larger collaborative efforts within the computer architecture community.