Golden Boy

A brief moment of humor (and pain) in the middle of deadline chaos (true story):

8am, Saturday. Productive grad student (aka Golden Boy) sends email: I am derailed because of this blinding pain in my elbow. Need to go to the ER.

    Prof: Ouch!  What's the diagnosis?

Golden Boy: Gave me some painkillers. repetitive stress injury. elbow is inflamed - will x-ray after the inflammation has gone down. can't keep the elbow at an angle -typing with left hand.

    Prof: Ouch!  First ISCA casualty in 10 years! :-)

Golden Boy: not giving up because of this. will continue the expts in the evening. might not happen. but still

    Prof: gasping out his last words... two at a time.. hindi movie style...

Golden Boy: :D ... from phone.

Golden Boy (1 minute later): how do we calculate [...] energy ? kshitij's model ?


Meanwhile, repurcussions around the world...

The Magical Paper Submission

Flipping my Classroom

I'll be experimenting with a "Flipped Classroom" model in my graduate computer architecture course this Fall.

I'll be recording key lectures beforehand and uploading them to YouTube.  I'll ask students to watch these lectures before class and use class time to solve problems and clarify doubts.

I buy the argument that a video (that can be paused, rewound, re-visited) is a more effective learning tool than listening to the same person speak in class.  I hope that the classroom experience will continue to be fun and interactive.  And I also hope that students have the discipline to listen to the videos before class.  If done right, this should lead to more effective and efficient learning -- more time spent outside class listening to lectures, but a lot less time spent outside class on assignments.

The videos will be in a screencast format: only showing the prepared slides and my run-time handwriting on them (no hands or face).  It won't be glitzy; I will fumble around at times.  If this model works for Khan Academy, it can't be a terrible idea :-).

If you're curious about the process: I'm using Powerpoint on my tablet-PC, combined with the Camtasia Studio Add-In.  So far, I've been willing to "accept" my videos after 4-6 takes.  I do very minor editing (cropping out the occasional cough).  Including prep time, I'm averaging about 3-4 hours of effort per video (note that I've taught this material many times).  In addition, I'll have to create new problems that I can use for discussion in class.

The videos can be found here (only the first six are ready as of today). 
The class website is here.

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

Trip Report -- NSF Workshop -- WETI

I was at an NSF-sponsored Workshop on Emerging Technologies for Interconnects (WETI) last week that was attempting to frame important interconnect research directions.  I encourage everyone to check out the talk slides; talk videos will also soon be posted.  In the coming months, a detailed report will be written to capture the discussion.  This post summarizes some personal take-home messages.

1. Applications of Photonics: An important conclusion in my view was that photonics offers little latency, energy, and bandwidth advantage for on-chip communication.  Its primary advantage is for off-chip communication.  It is also worthwhile to look at limited long-distance on-chip communication with photonics.  For example, if a photonic signal has entered a chip, you might as well take the signal to a point near the destination, thus reducing the cost of global wire traversal.  Nearly half the workshop focused on photonics; many of the challenges appeared to be at the device level.

2. Processing in Memory: Our group has some initial work on processing-in-memory (PIM) with 3D chip stacks.  It was re-assuring to see that many people believe in PIM.  Because it reduces communication distance, it is viewed as a vital ingredient in the march towards energy-efficient exascale computing.  However, to distinguish such ideas from those in the 1990s, it is best to market them as "processing near memory". :-)

3. Micron HMC: The talk by Gurtej Sandhu of Micron had some great details on the Hybrid Memory Cube (HMC).  An HMC-based system sees significant energy contributions from the DRAM arrays, the logic layer on the 3D stack, and the host interface (the memory controller on the processor).  SerDes circuits account for 66% of the power in the logic layer.

4. Electrical Interconnect Scaling: Shekhar Borkar's talk was interesting as always.  He reiterated that mesh NoCs are overkill and hierarchical buses are the way forward.  The wire energy for a 16 mm traversal matches the energy cost per bit for a router; frequent routers therefore get in the way of energy efficiency.  He pointed out that the NoC in the Intel 80-core Polaris contributed 28% to chip power because the computational units were so simple.  The NoC in Intel's SCC chip consumes more power than the NoC in Polaris, but the overall contribution is lower (10%), because the cores are more beefy and realistic.  In moving from 45 nm to 7 nm, compute energy will reduce by 6x; correspondingly, the electrical interconnect energy to travel a fixed length on-chip reduces by only 1.6x and the energy for off-chip interconnect reduces by less than 2x.  So the communication energy bottleneck will grow, unless we can reduce communication and communication distances.

5. Miscellaneous: There was a buzz about near threshold computing (NTC).  It appears to be one of the few big arrows left in the quiver for processor energy efficiency.  It was also one of many techniques that Patrick Chiang mentioned for energy-efficient communication.  He also talked about low-swing, transmission lines, and wireless interconnects.  Pradip Bose's talk had lots of interesting power breakdowns, also showing trends for the IBM Power series.

Waking Up to Bottleneck Realities!

NSF is organizing a workshop on Cross-Layer Power Optimization and Management (CPOM) next month.  The workshop will identify important future research areas to help guide funding agencies and the research community at large.  Below is my position statement for the same.  While the DRAM main memory system is a primary bottleneck in most platforms, the computer architecture community has been slow to react with innovations that look beyond the processor chip.


SPOT QUIZ:     What is an SMB?
Hint:  It consumes 14 W of power and there could be 32 of these in an 8-socket system.

FACTS:

Bottlenecks:

• The memory system accounts for 20-40% of total system power.  Significant power is dissipated in DRAM chips, on-board buffer chips, and the memory controller.
• Single DRAM chip power (Micron power calculator): 0.5 W.  On-board buffer chip power (Intel SMB datasheet): 14 W.  Memory controller power (Intel SCC prototype): 19-69% of chip power.
• Future memory systems: 3D stacks, more on-board buffering, higher channel frequencies, higher refresh overheads.
• And ... we have an off-chip memory bandwidth problem!  Pin counts have stagnated.

You Cannot Be Serious!!

(Exaggerated) State of Current Research: 

• Number of papers on volatile memory systems:  ~1 per conference.
• Number of papers on the processor-memory interconnect:  ~1 per year.
• Number of papers that have to define the terms "rank" and "bank":  all of them.
• Year of first processor paper to leverage DVFS: 2000.  Year of first memory paper to leverage DVFS: 2011.
• Percentage of readers that have to look up the term "SMB":  > 89%.  (ok, I made up that fact :-) ... but I bet I'm right)

For every 1,000 papers written on the processor, 20 papers are written on the memory system, and 1 paper is written on the processor-memory interconnect.  This is absurd given that the processor and memory are the two fundamental elements of any computer system and memory energy can exceed processor energy.  While the routers in an NoC have been heavily optimized, the community understands very little about the off-chip memory channel.  The memory system is a very obvious fertile area for future research.

QUIZ 1:  

Most ISCA attendees know what a virtual channel is, but most would be hard-pressed to answer 2 of the following 5 basic memory channel questions:

1. What is FB-DIMM?
2. What is an SMI?
3. Why are buffer chips placed between the memory controller and DRAM chips?
4. What is SERDES and why is it important?
5. Why do the downstream and upstream SMI channels have asymmetric widths?

QUIZ 2: 

Many ISCA attendees know the difference between PAp and GAg branch predictor configurations, but most will struggle to answer the following basic memory system questions:

1. How many DRAM sub-arrays are activated to service one cache line request?
2. What circuit implements the DRAM row buffer?
3. Where is a row buffer placed?
4. Why do DRAM chips not implement row buffer caches?
5. What is overfetch?
6. What is tFAW?
7. Describe a basic algorithm to implement chipkill.  (What is chipkill?)
8. What is scrubbing?

In early 2009 (before my foray into memory systems), I would have scored zero on both quizzes.  Such a level of ignorance is perhaps ok for esoteric topics... but unforgivable for a component that accounts for 25% of server power.

ACTION ITEMS FOR THE RESEARCH COMMUNITY:

• Identify a priority list of bottlenecks.  Step outside our comfort zone to learn about new system components.  Increase memory system coverage in computer architecture classes.
• Find ways to address obvious sources of energy inefficiencies in the memory system:  reduce overfetch, improve row buffer hit rates, reduce refresh power.
• Find ways to leverage 3D stacking of memory and logic.  Exploit 3D to take our first steps in the area of DRAM chip modifications (an area that has traditionally been off-limits).
• Understand the considerations in designing memory channels and on-board buffer chips.  Propose new channel architectures and new microarchitectures for buffer chips.
• Understand memory controller microarchitectures and design complexity-effective memory controllers.
• Design new architectures that integrate photonics and NVMs in the memory system.