Reed's Ruminations: A Blog by Dan Reed

Exascale Software: Just a Few Orders of Magnitude

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

Petascale high-performance computing (HPC) is here, with multiple machines achieving more than ten petaflops on the Linpack (HPL) Top500 benchmark. These achievements have not been without teething problems, as the scale and complexity of the systems have made debugging, acceptance testing and application scaling ever more challenging. Nevertheless, these systems are now operational, and they are being used for scientific research and national security applications.

In many ways, it amazing that a decade ago we celebrated crossing the terascale threshold. When I christened the NSF Distributed Terascale Facility (DTF) as the TeraGrid in 2002, Ian Foster asked me if we should worry about embedding a performance level in a facility name. I responded that I was confident the capabilities and the name would evolve, and they have.

Planning is now underway for exascale computing, though both the depth of the technical challenges and the straitened economics of research funding have slowed progress. For detailed background on the technical challenges, I heartily recommend reading the 2008-2009 DARPA exascale hardware and software studies, chaired by Peter Kogge and Vivek Sarkar, respectively. Although some of the details have changed in the interim, the key findings are still relevant. (In full disclosure, I was one of several co-authors of the exascale software study.)

Among a plethora of design challenges highlighted by these two reports, three are especially relevant when considered with respect to petascale systems:

• Substantially reduced memory per floating point operation (i.e., reduced memory per processor core due to energy constraints)
• Dramatically higher energy efficiency per floating point operation with minimal data movement, given the high time and energy cost of off-chip data accesses.
• Frequent component failures, given the sheer number of chips required to reach the exascale performance target

Just a Few Orders of Magnitude

All currently envisioned exascale systems would require parallelism at unprecedented scale, and barring new, energy efficient memory technologies; they would be memory starved relative to current systems, even under a 20 MW system design point; and multilevel fault tolerance would be required to achieve acceptable systemic mean time to failure (MTBF). Extraordinary parallelism, unprecedented data locality and adaptive resilience: these are daunting architecture, system software and application challenges for exascale computing.

If we have learned anything in sixty years of software and hardware development, it is that orders of magnitude matter, whether in latencies and access times, bandwidths and capacities, software scale and complexity, or level of parallelism. From file system metadata bottlenecks when opening thousands of files to application performance losses from operating system jitter due to daemon activity, every order of magnitude brings new challenges. Only the naïve or inexperienced believe one can scale any computer system design by factors of ten without exposing unexpected issues.

Knowns and Unknowns

What can we expect at exascale? As always, there are the known knowns, the known unknowns and the unknown unknowns, to use a Rumsfeld phrase. The knowns, of both kinds, include the ever-present issues of scale and locality. Will variants of current scheduling and resource management techniques be effective and usable by application developers? Will the complexity of multilevel memory management, heterogeneous multicore and dark silicon shrink the cadre of ultra-high performance application developers even further, perhaps below a technically and politically viable threshold?

The unknowns are more deep and subtle. How can energy optimization be elevated to parity with performance optimization, both statically and dynamically. The dynamic aspect is crucial, as the hysteresis of thermal dissipation in dark silicon affects chip lifetimes. Equally importantly, how can energy usage be related to code in ways that highlight optimization choices? This is the energy analog of performance measurement and guidance for optimized code, where measurements must be related to the original code in ways that are meaningful and amenable to change.

Finally, there are important open questions about the future of operating system structures themselves. The fundamental lesson of cloud computing – the nearest equivalent in scale – is the importance of weak consistency and loose coordination. Given projected exascale communication costs (energy and time), and frequent component failures, might federated rather than synchronized operation be preferable? Is it time to revisit some of our most cherished HPC assumptions and imagine operating system structures and programming models not based on Linux variants, MPI and OpenMP?

Evolution or Revolution

The exascale hardware and software challenges are real. Do we pursue incremental extensions of current practices or step back and explore more radical and fundamental options? Each has different advantages and disadvantages, which suggests we should probably pursue both, recognizing the costs. To be sustainable, an exascale research and development program must lead to cost effective and usable systems that are an integral part of the mainstream of semiconductor and software industries.

Related articles

Bill Gropp: We Need to Stop Talking Just About Exascale

Data Movement At Exascale

Little’s Law in the Exascale Era

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

A substantial fraction of my professional life has been devoted to analyzing and optimizing the dynamic behavior of some of the world's largest high-performance computing (HPC) systems. During the past thirty years, spanning my time at Illinois, North Carolina, Microsoft and now Iowa, my students, post-doctoral associates, research staff and I have used and developed many performance, energy consumption, and reliability instrumentation and measurement tools and techniques, embodied them in scalable data capture and reduction software, and created correlation tools that connect measurements to potential remediation opportunities. Multiple instantiations of these tools have been released as part of the Pablo performance analysis toolkit and Autopilot toolkit for adaptive performance control.

Just a Couple of Weeks

Most of this work originated in a challenge from my Ph.D. thesis supervisor, Herb Schwetman, issued while we were both at Purdue. After listening to me expound excitedly about the virtues of yet another interconnection network for parallel systems, he challenged me to prove that the object of my excitement would deliver higher performance than other alternatives. I dutifully promised him that I would spend a few weeks on the performance analysis problem, then return to the core parallel systems design question.

What ensued changed my thesis direction dramatically, as the two-week project took three years to complete. Over thirty years later, I find myself still working to answer generalizations my advisor's basic question: "How fast is system A compared to system B and what are the bottlenecks in each?" These are beguilingly simply questions, but they cut to the heart of system design and optimization. They are also especially pertinent as we consider the design of putative exascale systems with billion-way parallelism, and millions of components that must operate reliability, all while consuming tens of megawatts of power.

It Seems Simple, But It Is Not

Beneath all this complexity is a simple, yet subtle law that that relates performance (throughput), delay (response time) and number of interacting units (customers). It has been my friend and nemesis throughout my research career.

Generally known as Little's Law, it relates throughput (X), response time (R) and customers (n) in a stable system in a linear way: n=XR. This general relationship holds for computers, airline reservation systems, store checkout lines, or any other system where entities (customers or computer jobs) compete for service from a resource-limited system.

Little's Law also says there is no free lunch. Optimizing for high system utilization leads to large wait times for customers, as anyone who has waited on a busy telephone reservation line knows all too well. Conversely, ensuring short waiting lines requires system utilization to be low. Simply put, one must choose between high system efficiency and short customer wait times. One cannot (in general) have both.

As simple as this may seem, in reality, the best optimization strategy depends on many other constraints and the broader environment. For many systems, the relative costs of the components providing and receiving service determine the appropriate optimization axis. When humans are involved, their psychology and expectations must be managed appropriately. That is why many telephone response lines provide waiting time estimates and periodic feedback during the wait. Those of us who have managed batch-scheduled HPC systems also know that users and system operators constantly balance system utilization against the product of queue wait time and parallelism.

Coming Full Circle

Exascale computing brings many of these issues into focus in new ways. When a multiple megawatt energy spike is imposed on the electrical grid, utility operators notice. Thus, exascale system energy requirements may constrain when parallel job execute, as jobs with high floating-point computation intensity draw more energy those dominated by pointer chasing. Likewise, component reliability may limit maximum parallelism within exascale jobs; the mean-time-to-failure (MTBF) of processors, memory and storage systems, and interconnect elements really matters. Although more job parallelism normally reduces execution time, component reliability bounds effective parallelism and maximum computation time without either resilience or recovery mechanisms.

Performance, delay and parallelism at large scale: Little's Law speaks to all of these issues and more. When performance optimization, reliability requirements, and energy management are convolved with component costs, device physics, system software services and application characteristics, the constraint-based optimization problems become dauntingly complex. Their solution is a bit more than a two-week project, especially at exascale.

Related articles

HPC, Big Data and the Peloponnesian War

John Barr on the European Strategy for HPC and Exascale

China moves to beat U.S. in exascale computing

Exascale unlikely before 2020 due to budget woes

2012 Cray, Kennedy and Fernbach Awards

This year, I again have the honor and privilege to chair the selection committee for the Seymour Cray and Sidney Fernbach awards. I will also be hosting the presentation ceremony at SC12 in Salt Lake City for these two awards, along with the Ken Kennedy award. (My former colleague at the University of Illinois, Professor David Padua, chaired the Kennedy award selection committee.)

These eponymously named awards recognize truly outstanding contributions to high-performance computing, in honor of three leaders of our field. The Seymour Cray award recognizes individuals whose innovative contributions to high performance computing systems best exemplify the creative spirit demonstrated by Seymour Cray. In turn, the Sidney Fernbach award is given to for outstanding contribution in the application of high-performance computers using innovative approaches. Finally, the Ken Kennedy award recognizes outstanding contributions to programmability or productivity in high-performance computing, together with significant community service or mentoring contributions.

I am delighted that the 2012 Seymour Cray Award will be presented to Peter Kogge, who is currently a professor at the University of Notre Dame. Early in his career, Peter developed parallel algorithms for recurrence solutions and parallel prefix operations, resulting in what is now known as the Kogge-Stone adder, the gold standard for fast addition. While at IBM, he also developed a series of HPC systems for military and space applications, including some that were key elements of the U.S. space shuttle. For many people, that would define a career. However, Peter has also been a pioneer in multicore and multithreaded processor design; he was also one of the creators of what we now call "Processor in Memory" (PIM) computing. Today, he is a leader in exascale initiatives. 

I am equally pleased that Professors Laxmikant "Sanjay" Kale and Klaus Schulten, developers of the NAMD biomolecular simulation software, are joint recipients of the 2012 Sidney Fernbach Award. Their collaboration combines the best of computer science and computational science. Utilizing Kale's insights in fine grained parallelism and load balancing, embodied in the CHARM++ library, and Schulten's insights into biophysics, NAMD transformed high-speed molecular dynamics simulations, allowing the motions of large biological systems to be simulated for longer periods of biological time than were previously feasible.

The third of these awards, the Ken Kennedy award, recognizes Professor Mary Lou Soffa for "contributions to compiler technology and software engineering, exemplary service to the profession, and lifelong dedication to mentoring and improving diversity in computing." As the award citation notes, her work spans optimizing compilers and software engineering. Among her many contributions are key insights into quantifying the value of code optimizations within a coherent framework and on register optimization. In addition to seminal contributions to compiler technology, Professor Soffa has also been instrumental in mentoring women in computing and raising awareness of the need for our culture to be more inclusive and supportive.

My thanks to Satoshi Matsuoka for the photographs of the plenary program award presentations.

HPC, Big Data and the Peloponnesian War

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

To appropriate a line from The Music Man, there is trouble here in River City, and anyone who cares about the future of scientific discovery and innovation should be worried. What is that trouble you say? It is the divide separating the land of high-performance computing (HPC) and big data, and the political and funding implications created by this divide.

Whether in the U.S., Europe or Japan, the competition for research and infrastructure funding is intense. In the midst of our lingering economic malaise, budgets are being stretched to the breaking point. Should we invest in a new telescope or a new accelerator, a new polar station or a new biology initiative? These are legitimate, though painful questions, borne of budget exigencies and fiscal realities.

Many of us are concerned that in this time of limited resources, we could face a similar funding competition that pits HPC, particularly exascale plans, against big data. This competition would be disastrous for science, for computing and computational science research, for infrastructure deployment and for global innovation and economic growth. Both HPC and big data are essential elements of the research portfolio. We must make sure this rumble in the policy halls does not take place.

Understanding Cultures, Preventing Conflict

Even those who have never heard the name of the philosopher George Santayana can parrot his famous dictum, "Those who cannot remember the past are condemned to repeat it." Thus, it is worth drawing a few lessons from the Peloponnesian war, which pitted two great Greek city-states, Athens and Sparta, against one another. Although Sparta was ultimately the military victor, the adverse social, economic and political effects devastated all of Greece, and the wars marked the end of the Greek golden age. We cannot afford to reprise the Peloponnesian war in the guise of big data versus HPC.

The root of this potential conflict is the differing norms of computer science and computational science. Big data and machine learning are the creations of the academic computing and business cultures, while computational science is more the offspring of science and engineering. Both share historical roots, and both are cross-fertilized by the other. They need not and should not be inimical, especially since many of the technical challenges are common to both.

Some see big data as an egalitarian opportunity, one that could readily benefit both big and small science and yield scientific and economic benefits very quickly. Let me be clear, this statement is unquestionably true. The unprecedented richness of scientific and engineering data being produced by large-scale instruments and ubiquitous sensors is ripe for harvest and correlation via advanced data mining. Implicit this is the need for investment in both new data analysis tools and techniques and in large-scale data repositories. (See My Scientific Big Data Are Lonely.)

Others see exascale computing system proposals as a quixotic quest for national bragging rights that will benefit only a few. Let me be equally clear, this statement is unquestionably false. Yes, there are elements of national and regional competition in the Top500 rankings. However, the underlying technology challenges and scientific opportunities are profound. Low power memory and processor designs, post-Dennard device scaling and the software and reliability challenges of large, complex systems all are at the forefront of 21^st century computing system design, which deep implications for the future of the information economy. Similarly, some of our most pressing scientific and social problems in climate change, energy and biomedicine are dependent on powerful, advanced computing capabilities. Implicit in this is the need for continued, balanced investment in technology research and high-end system deployment for HPC.

A Grand Concord

We need a concord and strategic research investment plan that recognizes the shared importance of HPC and big data. Both warrant investments in basic research, and both need investments in large-scale infrastructure deployments. (Make no mistake, though, research and infrastructure are different, as I noted in Research {preposition} Infrastructure.) In a time of straitened budgets, this will not be easy, and it will undoubtedly require political compromise.

Neither the proponents of big data and nor those of HPC may get all they want on the time scale they desire, but neither can be sacrificed for the other. If the proponents on each side adopt strategies that treat the other community as the enemy, the relevant lesson of the Peloponnesian wars is unmistakable -- in such a battle, there are only losers. That would be disastrous for us all, particularly when there is a win-win so tantalizingly close.

The IT Ecosystem and Global Competitiveness

I am a member of the U.S. National Academies Board on Global Science and Technology (BGST). As the name suggests, the role of BGST is to examine the shifting nature of the global science and technology enterprise and its implications. These include the global flow of intellectual talent and capital, the interplay of government policies, research and development priorities, innovation and technology transfer, and global competitiveness and security. This is a wide-ranging mandate, which is both exciting and challenging.

As a member of BGST, I recently chaired a study, commissioned by the U.S. Department of Defense, on the issues surrounding the end of Dennard scaling and its implications for U.S. industry, defense capabilities and national security. The report, The New Global Ecosystem in Advanced Computing: Implications for U.S. Competitiveness and National Security, was just released. It is a cautionary tale about the Gordian knot of intellectual and economic interdependencies, of epochal ecosystem shifts, and the global consequences of both.

Lest this seem mere academic punditry, remember that 30-40 percent of U.S. net economic growth in recent decades has been due to advances in information technology. This is not just a tale of Silicon Valley, but also one for the entire country's economy.

Beyond Dennard Scaling

Moore's Law, the notion that the number of transistors in a given silicon area doubles roughly every two years, is not a law or even a theorem. Rather, it was an empirical observation, originally made by Gordon Moore in 1965. For over forty years, it has continued to hold true by virtue of enormous intellectual effort, ongoing architectural and software innovation, and billions of dollars of investments in process technology and silicon foundries. In turn, consumers, businesses and governments have been the happy beneficiaries of faster microprocessors, more powerful, inexpensive and ubiquitous computing devices and a rich and varied suite of software applications.

However, there is bad news. The continued and seemingly miraculous improvement in general processor performance is now over, a consequence of physical limits on transistor shrinkage that was itself a happy consequent of Dennard scaling. To be clear, Moore's law continues, with the number of transistors on a chip continuing to double, but the transistors no longer become more energy efficient as they shrink. The result has been bounds on microprocessor clock rates due to energy dissipation constraints and the concomitant rise of multicore chips and function-specific accelerators such as GPUs. (See Battling Evil: Dark Silicon and Nothing Is Forever for a few reflections and details.)

This radical shift breaks a virtuous cycle of mutually reinforcing benefits, one where software developers created feature-filled applications and stimulated demand for faster general-purpose processors, which then drove the creation of even more advanced applications. Simply put, we are the reluctant, wide-eyed denizens of a brave new world, one where the cherished and popular expectation that applications would run faster without change each time a new backward-compatible processor appeared.

There is a technical way forward, but it means embracing application parallelism and retargeting software to each new generation of non-compatible, heterogeneous multicore processors. As over fifty years of research in parallel computing has shown, this is a path fraught with pain and difficulty. In turn, this has profound implications for the future of the silicon ecosystem and the nature and locus of continued innovation. It is the trillion-dollar inflection point, pivoting on chip performance, business models and global markets.

Ecosystem Implications    

The end of Dennard scaling and the emergence of heterogeneous multicore processors has coincided with another shift, the transition from an era dominated by PCs to one defined by smartphones and tablets. For much of the world, the smartphone is now the primary computing system, and in developing economies, the aspirational feature phone is the only computing device. More to the point, the majority of PC and smartphone users are not in the U.S., nor will they ever be again. Not surprisingly, these two phenomena, the end of Dennard scaling and the rise of smartphones and tablets are deeply interrelated.

The PC ecosystem has long been driven by the phenomenal success of the x86 microprocessor family and successive generations of processors from Intel and AMD, both U.S. companies. Conversely, the smartphone and tablet ecosystem is largely based on the ARM microprocessor family and low power systems-on-a-chip (SoCs) developed by ARM licensees around the world. Beyond the ongoing competition between PC and smartphone vendors, this is a battle of business models, pitting a closed x86 ecosystem with captive silicon foundries against fabless semiconductor design firms that mix and match function-specific accelerators with ARM cores and use Taiwan Semiconductor Manufacturing Company (TSMC) as a foundry.

Enormous resources are being invested in both silicon ecosystems, with x86 designers seeking to "grow down" by reducing power and integrating functionality on chip to compete in the smartphone and tablet market. Conversely, ARM designers are seeking to "grow up" by increasing performance and adding features to compete with x86 designs in the server market. This battle royal is not winner take all. Rather, it is a competition to define the global nexus of innovation, with profound implications for global IT dominance in the next decade.

Global Competitiveness and BGST

It is with this backdrop that the BGST committee examined the technical consequences from the end of Dennard scaling, the cultural and economic challenges of parallelism, the possible shifts of capital and talent, and national and regional investments in IT research. The report's broad conclusions include the following: (a) the U.S. still leads in basic IT research, but the global gap continues to shrink, (b) IT investment strategies and challenges differ markedly across countries and regions, (c) single chip performance is unlikely to continue as the predominate focus of innovation, (d) there are serious risks that growing international markets will diminish U.S. influence and (e) U.S. national security and defense readiness depends on continued rapid uptake and deployment of advanced IT.

I encourage you to download and read the complete BGST report for additional details and insights.

In IT and innovation circles, Gordon Moore is also famous for another dictum, "only the paranoid survive." What he really said is more nuanced and relevant to the global innovation competition, "Success breeds complacency. Complacency breeds failure. Only the paranoid survive." It is worth pondering as one considers the interplay of science and technology, economics, government policy, and business models.

Acknowledgments

I would be remiss if I did not express my sincere thanks to the members of the BGST report committee: Cong Gao (Nottingham), Tai Ming Cheung (UCSD), John Crawford (Intel), Dieter Ernst (East-West Center), Mark Hill (Wisconsin), Steve Keckler (NVidia), David Liddle (U.S. Venture Partners), and Kathryn McKinley (Microsoft). There were thoughtful, dedicated and indefatigable. Finally, all of the committee members are deeply indebted to Bill Berry, Ethan Chiang and Lynette Millett from the National Academies.