Dr. Dobb's Journal November 2007
"Compilers are the underpinnings of the most important software," says James Reinders, Chief Evangelist and Director of Marketing and Business Development for Intel Software Products. "They build operating systems, all the infrastructure, most of the programming languages, millions of applications." These crucial tools of the programming craft are getting smarter, but certain developments in hardware and software mandate that they get a lot smarter.
First, evidence that compilers are getting smarter: "This week's news about a company named Tilera focused on two fronts: It is an MIT spin-off and its first release is a 64-core-processor called the 'Tile64.' But focusing on these two issues somewhat misses the point. The real news about Tilera is the software—specifically, its Multicore Development Environment." (Dr. Dobb's Report, August 21, 2007.) What makes Tilera's MDE big news is its multitiered approaches to parallelism, including SIMD compiler intrinsics to enable fine-grain parallelism across those 64 cores.
Second, why compilers need to get a lot smarter: In a widely cited paper earlier this summer, researchers at the University of Illinois at Urbana-Champaign presented a programming model for thousand-core microprocessors. "In such a model," they argue, "compilers and related tools require much more advanced program analysis capabilities and programmer assertions than what are currently available...to drive automatic or interactive parallel code generation tools." ("Implicitly Parallel Processing Models for Thousand-Core Microprocessors," Hwu et al., DAC 2007.)
In short, if multicore processors are the future, compilers are going to need to get smarter.
But are multicore processors the future?
Microsoft's David Tarditi (Principal Researcher, Advanced Compiler Technology group) thinks so. "Multicore computing, and more generally parallelism, is really going to be important," he says. "Clock speeds aren't increasing. Most of the performance increase is going to have to come from parallelism."
Intel's Geoff Lowney, director of Compiler and Architecture Advanced Development, agrees: "The most significant technological advance we will see in compilers in the next few years will be the widespread support for parallelism. Almost all future processors will have multiple cores. Over the next few years, almost all languages will develop extensions to deal with parallelism, and compilers will focus on the problem of mapping computation across multiple cores." Hardware and software parallelism that was formerly the exclusive province of scientific computing and GPU programming is the future of software development generally.
So can we expect super-smart compilers in a few years that efficiently and automatically parallelize your algorithms and legacy code? Probably not. The consensus of those we spoke with seems to be that compilers can't possibly be smart enough. "It is very unlikely," in Lowney's opinion, that "compilers will be able to parallelize serial programs automatically; the compiler will rely on the programmer to express parallelism explicitly, using new language constructs."
At least, that's the view from the compiler research labs. Lowney works in research at Intel. Reinders, also at Intel, takes a more near-term, pragmatic view. Because compilers are the underpinnings of our most important software, he says, in the short term any drastic change in the way compilers work is off the table. "We don't want radical change for users. Our users tell us 'don't make us edit our Makefiles!' We are trying hard to move to parallelism without radical compiler changes. The real work needs to be 'under the hood' or elsewhere (other than compilers)."
Got it: Compilers must get drastically smarter to deal with tomorrow's (and today's) multicore processors, and drastic change in compiler technology is disruptive. Clearly, there is a bumpy ride ahead.
The emergence of multicore processors is only one of the challenges driving significant smartness advances in compiler technology, although the consensus of those we polled is that it is the most important. Reliability is another biggie; more about that later. In a sense, though, these challenges and the advances they are driving are nothing new.
It seems strange today to realize that the very idea of compiling code was once controversial. But the prevailing view some 50 years ago was that these automatic-programming gimmicks couldn't possibly be smart enough to do the job.
"To them," John Backus wrote in 1980—"them" being the people he called the priesthood of early computing—"it was obviously a foolish and arrogant dream to imagine that any mechanical process could possibly perform the mysterious feats of invention required to write an efficient program." ("Programming in America in the 1950s: Some Personal Impressions," in A History of Computing in the Twentieth Century, Metropolis, 1980.)
Although Grace Hopper is rightly credited as the inventor of the compiler, when John Backus and his team invented Fortran they challenged conventional wisdom on compilation, articulated the bottom-line case for compilers, and came up with many key compiler optimizations in use today, such as moving computations out of inner loops, dead code elimination, and using expected frequency of execution estimates to optimize register allocation.
But "our plans and efforts," he wrote, "were regarded with a mixture of indifference and scorn until the final checking out of the compiler..."
The scenario of processors hitting a speed limit and a solution being offered in the form of multiprocessor machines with parallel-savvy compilers is not new, either. That's what Illiac IV was all about, with its 256 processors and massive parallelism supported by several parallel-optimized Fortran compilers. In the late 1970s, for problems that could be parallelized, Illiac was the fastest computer in the world. It did have a little problem with reliability, which, as mentioned, is another big issue today.
From the earliest Fortran compilers, developers were working to make them smart, to take up more of the slack from programmers. Today, competition drives compilers toward more smarts. "A landmark in compiler technology," Reinders says, "was the global optimizer in GCC 4.0 [in 2005]. It marked the end of the era of 'nonoptimizing compilers.' Every compiler needs to be very complex to compete these days."
In 1986, one programmer summed up the contemporary view of compilers: "People still get great satisfaction out of the fact that a compiler...can't write code as well as a human being. But...I think that within the next five years we'll have tools that will be able to do as good a job as a human programmer." (Bill Gates, Programmers at Work, Microsoft Press, 1986.)
Bill was too optimistic about how smart compilers would get, but the satisfaction (smugness?) he referred to is probably not a big factor today. We don't run into too many software developers who are obsessing over being smarter than their tools. There is resistance to putting parallelization smarts into compilers, though, when the result is to make the programmer's work harder.
And that's why those looking seriously at the future of compilers see a multitiered approach to parallelization.
"What we won't see," Reinders says, "is automatic parallelism [realizing] the dream of some to have the compiler do it all." The Holy Grail, Reinders says, would be "to let me express my parallelism without coding the details."
Tackling parallelism will require multiple approaches, Tarditi thinks, and the compiler research efforts he leads at Microsoft are in fact pursuing multiple tracks. "Compiler extensions for parallelism, new programming languages for scalable parallelism, better ways to extract parallelism" from code are all part of the solution, he says. Microsoft's research efforts are focusing on two concepts: data parallelism and transactional memory.
In data parallelism, their idea is to provide a new library that supports data parallelism at runtime. Operators, reminiscent of APL code, only work over entire arrays of data, not individual variables. Tarditi sees this approach as well suited for programming GPUs, but not for all applications, although he says, "my belief is we ought to be able to use it [productively] on multicore computers." While others (IBM, for example) are looking at new programming languages for parallelism, Microsoft's approach is more modest, Tarditi says. They'll be building support for data parallelism onto C#.
Transactional memory treats memory operations like database transactions, locking them so that "either everything happens or nothing happens." Integrating the transactional model into a programming language and applying it to main memory gives you a parallel programming model that is familiar and easier to use. Again, Microsoft's target for implementing this parallelism is C#, but these research ideas are being tested in the Bartok compiler for Microsoft's Singularity research OS. Tarditi also works on Phoenix, Microsoft's next-generation compiler and programming tools infrastructure, "the basis for all future Microsoft compiler technologies."
Intel is pursuing something similar, a fact that became clear to Tarditi when he and an Intel team both presented papers on transactional memory at last year's ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation.
Reinders also sees multiple approaches to parallelism in the near future, and predicts that it will be exciting. "I think we'll see more experimentation than we have in a long time. Things like transactional memory, thread pools, domain-specific extensions, heterogeneous targets—[but] exciting as it is, it won't represent a fundamental change in compiler technology—just an amazing number of sophisticated additions."
But parallelism is not the only force driving compilers to get more sophisticated.
"This is not on everyone's mind yet," Tarditi says, "but we're working to improve the reliability of software. Hackers are moving up the software food chain. We need language constructs and compiler support for more reliable software." Phoenix and Singularity are both active testbeds for developing the tools for building more reliable software at Microsoft, particularly focusing on ahead-of-time compilation for typesafe languages. In Phoenix, the compiler and tools are tightly integrated with one another.
"What would it take," Tarditi asks, "to use, in practice, more modern languages for system programming?" Languages with type checking, array bounds checking, and the like. Microsoft is not only exploring this in-house, but it makes Singularity available to academic researchers for such basic research.
"A little farther out," Tarditi says, they're looking into typed assembly language. The sales pitch for Java when it first came out was Java applets in verifiable bytecode; what if you could have that trustworthiness in distributed native machine code? "The next three to four years is my near term," Tarditi points out. "This might be farther out than five years."
Microsoft is serious about tackling reliability at the compiler and tools and OS level, but it is not alone in recognizing the seriousness of the problem. "At Intel," Reinders says, "I see how reliable silicon needs to be, and it amazes me how far all software is from this level of quality. It is a problem begging to be solved."
Researchers at Microsoft and elsewhere are aggressively looking for solutions to the reliability problem as well as exploring compiler strategies for dealing with parallelism.
Some of this research is bringing products to market right now.
Flashback to MIT in 1990: The Alewife project, under the leadership of Professor Anent Agarwal, had as its goal to demonstrate that a parallel computer system could be made both scalable and easily programmable. The large-scale shared-memory supercomputer that the Alewife team built provided many insights about parallel programming that fed into Agarwal's RAW project, whose goal was "to provide performance that is comparable to that provided by scaling an existing architecture, but that can achieve orders of magnitude more performance for applications in which the compiler can discover and statically schedule fine-grain parallelism."
RAW led to the RAW Compiler Project, which took away all responsibility for optimization from the hardware and gave it to the compiler, making the compiler smarter about parallelism. All of this led Agarwal in turn to found a spin-off company, Tilera, which you will recall from the beginning of this article.
Interesting times lie ahead.