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).

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

Research Competitions

Almost every year, The Journal of ILP has conducted a research competition at one of our top conferences.  For example, researchers are asked to develop a branch predictor that yields the highest prediction accuracy on a secret input data set.  I think such competitions are a great idea.  If you teach an advanced architecture class, you might want to consider tailoring your class projects in that direction.  An international competition could be a strong motivating factor for some students.  Besides, the competition organizers usually release a piece of simulation infrastructure that makes it easy for students to write and test their modules.  Recent competitions have been on cache replacement, data prefetching, and branch prediction.  The 3rd branch prediction championship will be held with ISCA this year.  I am slated to organize a memory scheduling championship with ISCA next year (2012).  The evaluation metric could be row buffer hit rates, overall throughput, energy, fairness, or combinations of these.  I have a grand 12 months to plan this out, so please feel free to send in suggestions regarding metrics, simulators, and workloads that you think would work well.