Reed's Ruminations: A Blog by Dan Reed

Cray and Fernbach Awards

This year, I have the honor and privilege to chair the selection committee for the Seymour Cray and Sidney Fernbach awards, both of which will be presented at SC09 in Portland, Oregon. These eponymously named awards recognize truly outstanding contributions to high-performance computing, in honor of two early leaders of our field.

Specifically, the Seymour Cray award recognizes individuals whose innovative contributions to high performance computing systems best exemplify the creative spirit demonstrated by Seymour Cray. The list of previous winners is a who's who of high-performance computer architecture, with Steve Wallach being the most recent winner.

In turn, the Sidney Fernbach award is given to an individual for outstanding contribution in the application of high-performance computers using innovative approaches. The 2008 winner was Bill Gropp, the latest in a series of distinguished awardees recognized for algorithms and applications.

The deadline for submitting nominations is July 1, 2009. I encourage you to think about our colleagues who have made major contributions to high-performance computing and submit nominations. You can access the IEEE awards nomination page here.

I also encourage you to nominate worthy individuals for the inaugural Ken Kennedy award, which recognizes substantial contributions to programmability and productivity in computing and substantial community service or mentoring contributions. Many of us worked to ensure the creation of this award, in honor of our late friend.

Thank you!

Escaping from Flatland

In 1884 (no, that's not a typographical error), Edwin Abbott wrote a satire about Victorian England and its social hierarchy, in the guise of a mathematical story about life in a two-dimensional world, whence the whimsical title, Flatland: A Romance of Many Dimensions. If one can look beyond Abbott's misogyny to the crux of the mathematical story, it is an illuminating introduction to geometry in one, two and three dimensions, with some generalizing hints about higher dimensional geometries. (You can read a copy at the Internet Archive, or purchase a hardcopy).

The story is told from the perspective of a square, a resident of Flatland, who receives a visit from an inhabitant of a three-dimensional world – Spaceland. In Flatland, of course, the sphere is perceived only as a circle whose diameter varies based on the sphere's orientation to the plane. The sphere preaches the existence of higher dimensions, but the Flatlander leaders attempt to suppress all such information.

Denizens of Waferland

In fine recursive fashion, the Flatland story is itself a metaphor for our tenacious embrace of our two-dimensional world of semiconductors, particularly as it relates to memory technologies. We are deeply entangled in the angst, ennui, despair and perhaps even the clinical depression related to our encounter with the limits of instruction level parallelism (ILP), sequential execution semantics and the microprocessor power wall.

As a community, we have grudgingly and guardedly recognized the need for multicore processors (See Three Views on Multicore and Manycore: Able Was I Ere I Saw Elba.) However, we are still clinging tenaciously to our dual in-line memory module (DIMM), two-dimensional packaging and double data rate (DDR) memory designs. We need a visitor from the third dimension, preaching the gospel of chip stacking to the denizens of chip waferland.

Chip Stacking: Beyond DDR

We are approaching scaling limits for our pin-based interfaces. Each generation, we have dropped voltages, increased clock rates and doubled the number of words transferred. DDR memory first operated at 2.5V and up to 400 Mb/s, dropped to 1.8V and increased to 800 Mb/s for DDR2, and is at 1.5V and 1600 Mb/s for DDR3. We can see DDR4 on the horizon, perhaps in 2012 at ~1V.

It is time – long past time – for us to move to the third dimension and stack our chips. With chip (die) stacking, need not be constrained by connections to the perimeters of our chips, but can exploit connectivity across a larger fraction of their area. IBM, Intel, Samsung and others are exploring variations of this idea, as this smattering of press releases and articles illustrates.

With lower power, multicore designs, through silicon vias (TSVs), and wafer thinning for heat dissipation, we can crack the memory wall that has plagued us for so long. More to the point, those of us in the big iron/fast iron camp could learn a few things from our compatriots in the embedded systems world, where innovative packaging is a fundamental market driver.

Make no mistake; this will not be easy, as it requires new approaches to via fabrication, as well changing our ecosystem of chipsets and interface standardization processes. We may not have tachyon-based hyperspatial communication, but surely we can escape from Flatland.

When Petascale Is Just Too Slow

N.B. I also write for the Communications of the ACM (CACM). The following essay recently appeared on the CACM blog.

It seems as if it were just yesterday when I was at NCSA and we deployed a one teraflop Linux cluster as a national resource. We were as excited as proud parents by the configuration: 512 dual processor nodes (1 GHz Intel Pentium III processors), a Myrinet interconnect and (gasp) a stunning 5 terabytes of RAID storage. It achieved a then astonishing 594 gigaflops on the High-Performance Linpack (HPL) benchmark, and it was ranked 41^st on the Top500 list.

The world has changed since then. We hit the microprocessor power (and clock rate) wall, birthing the multicore era; vector processing returned incognito, renamed as graphical processing units (GPUs) ; terabyte disks are available for a pittance at your favorite consumer electronics store; and the top-ranked system on the Top500 list broke the petaflop barrier last year, built from a combination of multicore processors and gaming engines. The last is interesting for several reasons, both sociological and technological.

Petascale Retrospective

On the sociological front, I remember participating in the first petascale workshop at Caltech in the 1990s. Seymour Cray, Burton Smith and others were debating future petascale hardware and architectures, a second group debated device technologies, a third discussed application futures, and a final group of us were down the hall debating future software architectures. (I distinctly remember talking to Seymour about his "parity is for farmers" comment regarding memory ECC.) All this was prelude to an extended series of architecture, system software, programming models, algorithms and applications workshops that spanned several years and multiple retreats.

By the way, you can read the original report here; it is fascinating to look back. Paul Messina, Thomas Sterling and others deserve our thanks for launching the seminal activity.

At the time, most of us were convinced that achieving petascale performance within a decade would require some new architectural approaches and custom designs, along with radically new system software and programming tools. We were wrong, or at least so it superficially seems. We broke the petascale barrier in 2008 using commodity x86 microprocessors and GPUs, Infiniband interconnects, minimally modified Linux and the same message-based programming model we have been using for the past twenty years.

However, as peak system performance has risen, the number of users has declined. Programming massively parallel systems is not easy, and even terascale computing is not routine. Horst Simon explained this with an interesting analogy, which I have taken the liberty of elaborating slightly. The ascent of Mt. Everest by Edmund Hillary and Tenzing Norgay in 1953 was heroic. Today, amateurs still die each year attempting to replicate the feat. We may have scaled Mt. Petascale, but we are far from making it pleasant or even routine weekend hike.

This raises the real question, were we wrong in believing different hardware and software approaches were needed to make petascale computing a reality? I think we were absolutely right that new approaches were needed. However, our recommendations for a new research and development agenda were not realized. At least in part, I believe this is because we have been loathe to mount the integrated research and development needed to change our current hardware/software ecosystem and procurement models.

Exascale Futures

I recently participated in the International Exascale Software Project Workshop (IESP), the first in a series of meetings designed to explore organizational and technical approaches to exascale system design and construction. The workshop built on several earlier meetings and studies, including the DARPA exascale hardware study and the forthcoming exascale software study (in which I participated), as well as the DOE exascale applications study. Complementary analyses are underway in the European Union and in Asia.

Evolution or revolution, it's the persistent question. Can we build reliable exascale systems from extrapolations of current technology or will new approaches be required? There is no definitive answer, as almost any approach might be made to work at some level with enough heroic effort. The bigger question is what design would enable the most breakthrough scientific research in a reliable and cost effective way?

My personal opinion is that we need to rethink some of our dearly held beliefs and take a different approach. The degree of parallelism required at exascale, even with future manycore designs, will challenge even our most heroic application developers, and the number of components will raise new reliability and resilience challenges. Then there are interesting questions about manycore memory bandwidth, achievable system bisection bandwidth and I/O capability and capacity. There are just a few programmability issues as well!

I believe it is time for us to move from our deus ex machina model of explicitly managed resources to a fully distributed, asynchronous model that embraces component failure as a standard occurrence. To draw a biological analogy, we must reason about systemic, organism health and behavior rather than cellular signaling and death, and not allow cell death (component failure) to trigger organism death (system failure). Such a shift in world view has profound implications for how we structure the future of international high-performance computing research, academic-government-industrial collaborations and system procurements.

Doctoral Comedy: Which Way Is The Door?

One of the great lessons of sociology is the power of shared experience, whether positive or negative, to create deep and lasting human bonds. From the horror and misery of war and abduction (Stockholm syndrome) through the fun and excitement of athletic camaraderie and competition to the caffeine and adrenalin fueled pressure of a "ship or die" venture-funded startup, shared experiences can define one's life. This even extends to pursuing a Ph.D., where the long, sometimes strange and unpredictable journey can create its own ethos and breed a certain gallows humor.

This is why I am enjoying the great comic strip, Piled Higher and Deeper, also known as PhDComics, drawn by Jorge Cham. As an aside, the phrase "piled higher and deeper," of course, is an old and hoary wordplay on the progression from B.S. through "more of the same" (M.S.) to – all together now – "piled higher and deeper." (Ph.D.) If you ever spent Saturday night working in the lab, and every graduate student has, you understand the stable cleaning analogy.

The first time I saw the PhDComics strip, I knew that Jorge must have been a Ph.D. student, because only someone who has experienced graduate school and faculty life, particularly in a technical discipline, could have that much insight regarding the joy and misery of graduate student life and the trials and foibles of faculty members. I spent thirty years in that world, and I recognize myself, my friends and my colleagues in the strip. (No, not thirty as a graduate student, though it certainly seemed so at the time!) Perhaps the following anecdotes will trigger some memories of your own.

The Netherworld

As a graduate student, you live in a netherworld, not quite a student nor a faculty member either. The undergraduate students see you as faculty, especially if you are a teaching assistant, and the faculty members see you as a student, especially if you have not yet crossed the River Styx, otherwise known as the Ph.D. qualifying examination. From the university's bureaucratic perspective, you are a chameleon, classified as either a student (see parking privileges and health benefits) or staff (see student discounts and athletic tickets) when convenient.

One of my Illinois Ph.D. students came to our weekly group meeting absolutely furious. He'd driven to the Digital Computer Laboratory (DCL) about 3 A.M. that morning to check on the progress of some research simulations. When he returned to his car about 15 minutes later, he found a ticket on his windshield. My student was absolutely adamant that it was unfair and that he would not pay the fine. It looked like a mano-a-mano smackdown – irate graduate student versus implacable bureaucracy.

I was sympathetic; after all, Urbana at 3 A.M. has a surfeit of parking places. I asked him on which of the streets near DCL he'd parked his car. He asked why it mattered. I patiently explained that some of the streets were within the jurisdiction of the university police, whereas others were within the jurisdiction of the city of Urbana. The city – and by extension, the U.S. government – might have the power to fine him, jail him or even deport him, but the university wielded a far more important power over his fate and future. It could prevent him from graduating by simply encumbering his records for failure to pay a parking ticket. Because he had parked on a university street, he had no choice; he wanted a Ph.D.; he paid the fine. Final score: university 1; graduate student 0.

The Weekly Meetings

If you have been a graduate student or a faculty member, you remember the weekly meetings with your advisor (advisees) and the group meetings and seminars. Each brings certain perspectives, and they become conjoined over time, whether it be foraging for free seminar food, trying to impress people by asking questions or simply staying awake and trying to look interested.

One my first Ph.D. students, a truly fantastic researcher who is now a very successful computer science faculty member himself, once asked me at a professional conference if there had ever been intervals where I had wondered if he were doing anything useful in the lab. After confessing that it had crossed my mind a time or two, he laughed and said he understood, as he now wondered the same about his own students.

How Many Years?

At some point during my graduate career at Purdue, I was having dinner with the parents of a friend of mine. Her mother asked when I expected to graduate, and I said, "In a year or so, I think." She replied, "That's what you said last year." In fact, I had said the same thing the year before, and both times I had been hoping it was true. Of course, she didn't know that asking a graduate student when they will finish their thesis is a bit like asking someone about their weight or their income. As the PhDComics strip notes, it's best not discussed in polite company.

In that spirit, I also distinctly remember leaving a Friday night, midnight campus showing of The Deer Hunter, thinking the odds were high that my tombstone would list me as an A.B.D. graduate student with the epitaph, "Felled by one last thesis revision." That one sentence captures so many elements of the graduate experience. First, I left the movie alone and on foot, because I had no date and no car. Second, I was attending a midnight $1 movie because I living on rather miniscule graduate fellowship stipend with little discretionary money. (See my previous comment about having no date and no car.) Third, it was The Deer Hunter, a great movie but a truly depressing moral meditation on war and death, perhaps not the best choice for a midnight screening, especially for a graduate student. Without hesitation, I walked directly back to my office in the Purdue Mathematical Sciences building and worked all night on my dissertation. I had to graduate, and I did!

Crazy Thesis Topics

My dissertation was on a wild and crazy idea – building parallel computers using large numbers of microprocessors and programming them via message passing. Like most dissertations, nothing came of it, because we all recognized the importance of purpose-built parallel systems that balanced computation, communication and I/O and that were programmed using new languages and tools that focused on human productivity. A long-term, industry-government-academic partnership in the early 1990s produced the balanced, highly productive, near-exascale systems we use today for breakthrough computational science and national defense.

What's that you say? You mean we are using commodity microprocessors and message passing for parallel computing? Bummer! I must have confused this reality with a parallel earth in a many worlds quantum interpretation.

Shared Experiences

Like most humor, the rueful elements of truth are what make PhDComics fun. I formed some of my most intense, lifelong friendships in graduate school, both with my fellow students and with faculty, especially my thesis advisor. (Yes, we called him Herb, and he was a great guy) The highs and lows, the parties, the late nights in the lab, the uncertainty and the satisfaction – they are what make research in academia a special place.

PhDComics captures all of this. It's a smash hit in the academic community, with appearances in Science, Nature and a host of other places. Here's to Jorge and continued success. (Hint, buy the books and read the strip.)