Reed's Ruminations: A Blog by Dan Reed

Driving: Integers and Reals

In over twenty-five years of professional travel across the United States and the world, I have learned a few things, sometimes by experience, that have proven useful. They include

• If you can't lift your packed bags, discard things until you can, then repack. (Alternatively, visit the gym and work on your upper body strength. But – and this is really important – it must fit in that overhead compartment.)
• Checked baggage follows its own itinery, which only loosely resembles that of its putative owner.
• You can get a long way with a smile, pointing and gesturing, and the words "please" and "thank you" (even if they're the only words you can speak in the local language).
• If "please" and "thank you" seem overly limiting, learn how to say, "Sorry, I'm an idiot" or even better, "Sorry, I'm a dumb American" in the local vernacular. They have done wonders for me.
• You will get lost; it's part of the adventure, and you should try to enjoy it. (Remember, being lost and not knowing where you happen to be at the moment are not the same thing.)
• People really and truly are the same everywhere, with the same hopes and fears.

Integers and Reals

Despite the deep and broad similarities that transend regional and national cultures, uniting us as humans, I have observed wide variation in one one deeply individualistic trait. The frequency of this trait widely varies across regions of the United States, across countries and across cultures; it is preponderant in some, rare in others, but present everywhere. I speak, of course, about our philosophical approach to driving motorized vehicles.

I call the two extrema of this trait the integers and the reals, though there is a continuum between. Thought I have lived in both worlds, a deep chasm separates those who reside in the land of the integers (and who believe deeply in an integral number of lanes in the road) from the residents in the land of the reals (who believe equally deeply in a continuous, highly fluid number of proximate driving lanes).

The resident of integer land believes the road lane markings were created for good reasons, by thoughtful and knowledgable road engineers and government officials. Accordingly, they must be obeyed carefully, diligently and duitifully, even if there are no pedestrians or other motorized vehicles within 50 kilometers. Rules are, after all, rules, regardless of context, and they must be obeyed.

Conversely, the resident in real land believes equally passionately that lane markings were created by distant and uncaring bureaucrats who lack concern for the personal exigencies and superior skill of the vehicle driver. Accordingly, the markings are the merest suggestion that need not, indeed should not, interfere with the drivers freedom and flexibility. Indeed, even the sidewalks, should they exist, are available for use by vehicular transport, even if pedestrians might otherwise occupy them.

In integer land, the road lanes are discrete and denumerable, and traffic moves in integral multiples of lanes, with a one-to-one mapping of traffic steams to lanes. In real land, the road lanes are uncountably infinite, with a potentially unbounded number of traffic steams mappable to a single lane. Cantor would have been proud. (If you were wondering, you just experienced an example of situational learning, complete with set theory, an allusion to a diagionalization proof that the reals are uncountablly infinite, and a pointer to one of history's great mathematicians. Now back to our regularly scheduled programming.)

Canadian Integers

Many years ago in Canada, while attending a conference in Banff, Alberta, I was strolling down a street, taking in the scenery and architecture. I stopped at an intersection and waited for the light to change (this alone pegs me as an undisputed resident of integer land). I stepped off the curb with one foot, and then paused when something in the sky caught my eye. After a few moments, the silence interrupted my reverie, and I realized – to my chagrin – that I had paralyzed traffic at the intersection. With nary a car honk, the Canadians were waiting patiently for me to make a decision and move, for pedestrians always have the right of way. This is integer land in its purest form.

Savoring Indonesia

In the late 1980s, I was in Jakarta for three weeks to work with the University of Indonesia, as part of a World Bank program. While there, I was collaborating with the computer science faculty on curriculum issues. (I am delighted that one of my former Ph.D. students from the University of Illinois, Bobby Nazief, is now a member of that same computer science faculty and a senior IT advisor to the Minister of Finance in Indonesia.)

While in Indonesia, I stayed at the Hotel Indonesia in central Jakarta. Yes, it's the hotel that was famously the source for scenes from the Year of Living Dangerously book and movie. I had a truly delightful time in Indonesia. The people were incredibly friendly, the scenery was beautiful and food was fantastic – I learned to love nasi georing in all its forms.

After years spent living in the midwestern United States, though, I had become accustomed to the prairie, with open roads laid out on one mile squares. When I first stepped outside the hotel in Jakarta, I was both exhilarated and terrified by what I saw. (I was young and naive.) The traffic pattern looked like Brownian motion, but of course it was really a biased random walk – the steps were small but finite, and the vehicles were diverse.

(Ah, another teachable moment, Brownian motion is the continuous limit of a random walk, as the step size approaches zero. I have always loved the fact that the limiting probability of return to the origin is unity for one and two dimensional random walks, a result Polya proved many years ago. Here ends the second lesson.)

Drivin' the U.S of A.

Then there is my own, my native land, filled with integers and reals. We have the Boston left turn (edge into oncoming traffic, forcing it to stop, and then turn left) and the Michigan left turn (You wish to turn left, but all lanes are going right. You turn right, go one or two blocks, make a U-turn left, then you are pointed in the correct direction).

We are also blessed with the New York traffic jam, where you can learn English phrases that would make your mother cry and a Navy veteran blush. At the other extreme, we have the western states where the roads are straight and flat until they intersect the horizon, and drivers risk falling asleep because there are so few decisions to make.

Then there is Chicago, in my adopted home state, where you sometimes cannot even see the lanes due to the ice and snow. If it's Chicago and driving, you have to remember Jake and Elwood Blues and their "mission from God." You know where I'm going – work with me, here. Elwood says, "It's 106 miles to Chicago, we got a full tank of gas, half a pack of cigarettes, it's dark, and we're wearing sunglasses." Jake replies, "Hit it!" Prison, not surprisingly, followed.

Finally, there is Seattle, my current home. It's a place with lots of water and not enough bridges. Traffic backs up for miles on the bridges from Seattle to the eastside – Bellevue and Redmond – in ways that some days make the seven Bridges of Königsberg problem seem simple by comparison.

Look at the road ahead. Do you see a countable number of lanes or a continuous surface? Does your heart beat faster at the prospect of competition, or do you hope for carefree, laminar flow?

ManyCore: Able Was I Ere I Saw Elba

As I write this, I am attending the ETH
LASER summer school on concurrency, which is being held on the island of Elba. The island sits off the coast of Tuscany, a few miles from Pisa. It is perhaps best known as the place where Napoleon was exiled after his forced abdication and where he spent the interregnum before his final defeat at Waterloo. (Let me express my thanks to Bertrand Meyer for the invitation to speak at the summer school.)

As I prepare to deliver six lectures on multicore and cloud computing here on Elba, the geographic irony of grand ambition, hubris and ignominious defeat is not lost on me. We have been struggling for the past forty years to find elegant and efficient parallel and distributed programming paradigms, with modest success. To continue my 19^th century metaphor, we remain, as Matthew Arnold sadly put it, "Swept with confused alarms of struggle and flight, where ignorant armies clash by night."

The Virtuous Cycle

Metaphors aside, our struggle is real and extraordinarily important. The virtuous cycle that has long driven the computing industry is in flux, and if it is broken, we will struggle restart it – for deep economic reasons. The desire for new functionality leads to richer, more complex software, which imposes greater demands on extant hardware, with concomitant performance constraints. In turn, this stimulates demand for faster processors, and the cycle of innovation turns.

One interesting corollary of this cycle is that we demand new, faster processors at the same price, rather than the same performance at a lower price. This consumer demand generates the revenue needed to fuel commercial software development, power new chip designs and fund semiconductor fabrication line construction. These are multibillion dollar (U.S.) investments, ones only repaid if tens to hundreds of millions of units are sold. In turn, this creates deep partnerships among companies such as Microsoft, Intel,
AMD and the PC vendors. A similar virtuous cycle exists in the mobile telephone market.

ManyCore Directions

This ecosystem of software and hardware innovation is challenged by consumer parallelism, in the form of large-scale multicore (manycore) chips. No longer can we expect dramatic increases in single core performance, due to power and heat dissipation constraints on consumer devices. Perhaps more tellingly, all of us wonder what the next "killer app" will be that excites and incents consumers to buy new, manycore systems. Personally, I believe it will be some combination of graphics-intensive massively multiplayer games (MPGs) and contextually-adaptive, situationally-aware information spheres. (One can think of the latter as Vannevar Bush's
Memex reborn.)

Of course, as James Thornton (CDC) said many years ago, "Anyone who says he knows how computers should be built should have his head examined! The man who says it is either inexperienced or really mad." I'm too old to be inexperienced, so perhaps I am really mad after all!

The fundamental question is how large multicore (manycore) chips and development software will evolve. I see at least four architectural directions, at least two of which are already commercially prevalent. The first is the "cookie cutter" homogeneous multicore design, exemplified by today's Intel and AMD flagship x86 offerings, along with similar homogeneous multicore designs from SUN (Niagara) and IBM (Power5-7). Tilera's
TILE64 and Intel's Larrabee are other examples of this approach, combining standard cores (x86 and MIPS-derived, respectively) with a regular interconnect (mesh for Tilera and ring for Larrabee).

The second is ISA-compatible homogeneous, but performance heterogeneous multicore. In this case, one combines, for example, a smaller number of complex, out-of-order cores with a larger number of simpler, in-order cores. The motivations for this approach are simple – the implications of Amdahl's Law and the need to execute legacy code efficiently while still delivering some of the performance and power advantages of low-power multicore. In this same spirit, Mark Hill has recently written a great paper about the importance of performance heterogeneity in multicore design.

The third is functional heterogeneity, currently exemplified by chips such as the IBM Cell, AMD's announced Fusion chip and a host of embedded and domain-specific chips. I believe there are many opportunities for architectural innovation in this space, combining graphics, DSP, packet processing, cryptographic functions, SDR and a host of other functions with novel interconnects and memory sharing approaches.

The fourth is what I call non-traditional architectures that embody more radical alternatives. One great example of this class is Doug Burger's
TRIPS system, based on data graph execution. Doug recently joined Microsoft Research from the University of Texas at Austin, and I am excited about the collaboration possibilities.

Back to the War

I believe we are at an inflection point in parallel computing, with the economic impetus of consumer parallelism now driving us. Let us hope that we fare better than the warriors in another 19^th century war, the Battle of Balaclava during the Crimean War. As Tennyson wrote so well, the Light Brigade charged into the mouth of hell. With cannons to the right (multicore architecture), cannons to the left (programming models) and cannons in front (next-generation applications), we ride into an unknown future, one fraught with peril but also with opportunity.

Low Hanging Fruit: Memories of Childhood

Low hanging fruit – it's a metaphor native English speakers often use to denote an opportunity on which one can easily capitalize, a reward readily grasped without stretching. Yet I doubt most of us, particularly those in urban areas stop to consider the agrarian origins of such phrases, when hunter-gatherers quite literally foraged for food. For most of us, fruit is something purchased in a supermarket after having been transported from some far-flung agricultural processing area. For the adventurous, fruit might be something purchased at a farmer's market or a roadside stand.

As we consider the effects of rising energy costs on food production and distribution, it is worth remembering that this phenomenon is quite recent and (perhaps) transitory. Chilean grapes, Malaysian star fruit (carambola) and Chinese kumquats, we take these for granted, often failing to consider their true costs and global carbon footprint. Before we became a predominantly urban culture, almost all food was grown, processed and consumed locally, often by the growers themselves.

Getting My Hands Dirty

I was reflecting on all these trends as my wife Andrea and I picked wild blackberries along the small roads near our house in Redmond, Washington. Our house is surrounded by woods, and the small, one lane roads have created just enough clearing for the blackberry vines to flourish in the sunlight. (Yes, the sun does shine in greater Seattle, though not as often as we might like.) This is true, low hanging fruit, where one can forage and gorge oneself while standing still. Of course, we are not the only foragers. The local wildlife, including bears, shares the experience, and I have no desire to stand between a bear and berries.

In addition to instant gratification and stained hands, there is the culinary delight (nee deferred reward) that is blackberry cobbler. I had promised Andrea that I would help pick berries if she would make a cobbler. Knowing that Andrea is a truly wonderful cook, from my perspective, this was a "no lose" proposition. The tasting more than proved me prescient in that assessment.

Though not haute cuisine, blackberry cobbler captures the quintessential nature of simple, natural and tasty local ingredients. Parenthetically, how many times have you dined at a restaurant offering nouvelle cuisine, only to find that the length of the entrée's description rivaled the size of the entrée (that would be the main course for those not from the U.S. or English-speaking Canada) itself? Simplicity should not be pretentious. Leonardo Da Vinci may well have remarked, "Simplicity is the ultimate sophistication," but I was too busy with the spoon to wax overly philosophical.

Remembering My Father

Blackberry picking conjures memories of my childhood, when my father would come home from work with his lunch box filled with berries he had picked in the fields around where he worked. We were financially challenged (non-euphemistic translation – we were dirt poor), and living off the land was not a luxury, it was an absolute necessity. We grew what we could, and my father picked wild blackberries during the idle times between buying logs for a rural Arkansas sawmill that would fit all of one's backwoods stereotypes. (Yes, I worked there too before going to college, and it taught me some valuable lessons about hard work, the consequences of failure and the power of education. I must confess, though, that it was humbling to have tourists stop to take photographs.)

Happiness was seeing him walk in the back door with a bucket of blackberries. It meant we would be having berries in the future (frozen for use later in the winter – that deferred reward again) and blackberry cobbler as soon as my mother could wash and prepare the blackberries.

Picking berries this week with Andrea and anticipating the taste of cobbler took me back to my childhood, when life and family were defined by blackberry cobbler and a summer baseball game on the radio, sitting under a tree. Warm cobbler, with the crust floating atop the blackberries and juice, this is one of life's pure pleasures, feeding both body and soul.