November 2005
E-Infrastructure: Europe Meets the e-Science Challenge
Craig Mundie, CTO – Microsoft Corporation

Moore’s Law and the need for new algorithms

Another area where I think we can make a difference is to explore how some of our research on algorithms in a number of different areas of Computer Science could be used in other areas of science. The breakthroughs that can come from radical concepts in the algorithmic space can be quite dramatic. Several years ago some of the most passionate researchers working to develop a vaccine for AIDS approached some researchers at Microsoft Research. They showed our researchers the algorithms that their community had been using to work with the genomic data over the past six years. They were frustrated with the level of progress that had been made and wanted our researchers’ opinions about how they might better work with the data to progress more quickly in producing a vaccine.

The Microsoft Research scientists, whose areas of expertise include machine learning and machine vision, studied the algorithmic concepts the group was using. They found the algorithms were sound and said that they might be able to show the group how to make the algorithms work a little better. But they also said that a whole new class of algorithms had recently been developed to work in the realm of searching in high-dimensional spaces. Not only did the scientists help the group implement the newer algorithms, but because they also were part of a group within Microsoft Research that researches the building of powerful visualization tools, they helped the group develop a suite of visualization tools that they could use along with the algorithms. The AIDS research team was able to reprocess in six weeks the same gene data that had previously taken them six years to process. Without even changing the underpinnings of the hardware or anything else they were using, the group now approaches their research in whole new ways. These new algorithms could materially accelerate the development of an effective vaccine for AIDS.

Finally, there is another challenge ahead for all of us. Since the early days of supercomputers, exploitation of parallelism has been limited by Amdahl’s Law, which basically says that it is the little part of the problem that is not parallelizable that will come back to haunt you. If you have a problem that is 90% parallelizable, even if you use 1000s of processors so this parallelizable part is done blindingly fast, you are still left with the 10% that runs at the speed of one processor and a maximum speed-up of 10. We are now entering a new era of silicon technology, one in which scalar processor performance will not improve significantly. Such a statement has never been true since the invention of digital computing as we know it, but it is one that is now likely to be true for the foreseeable future. This will herald a fundamental change for the whole IT industry.

The reason is as follows. Until there is some radical change in how we physically build transistors and design computers, we have now run into a brick wall. The problem is that everybody thinks Moore’s Law has really been driving the performance gains we have seen over the last thirty years. But Gordon, when he defined Moore’s Law, actually only talked about the fact that there would be the ability to double the number of transistors on a chip at an exponential rate. And this phenomenon is still going to continue for awhile. But this in itself was not what actually brought all of us faster computing. The thing that actually made it happen, and made a lot of other things go faster, was raising the clock rate. But raising the clock rate was only possible because we could lower the voltage. Now we cannot lower the voltage anymore because we are down into electron volts. There is just no more room to keep shrinking the voltage. If you cannot lower voltage, you cannot raise the clock rate materially. Therefore, even though we could have lots more transistors, there will no longer be chips with higher clock rates. This has a very profound effect. Up to now, that last 10% of the code that you could not parallelize was manageable because you have been the beneficiary of orders of magnitude improvement in scalar performance. Now such easy gains are over–or they will be in your lifetime.

So there are some very big challenges that we will all have to face. I contend that one of them is that we are all going to have to think at some level about new algorithms. One aspect of the future is already becoming clear. We will need to learn how best to exploit new multi-core CPU architectures and develop tools to support software development on such architectures. This is a real challenge to the parallel computing community. To benefit from these new machines we may have to change our programming methodology in more radical ways than we have really been comfortable doing in the past. We think about this in Microsoft every single day as we look out on a 10-20 year horizon. If you are not already thinking about this you should be. If you layer this problem on top of all the other ones, then the challenges ahead for the world’s Computer Science research community are amplified quite dramatically. All of these things are what led Bill Gates and I to believe that it is strategically important, no matter what your field of software expertise, to know and think deeply about high performance computing. It is this community that will be at the forefront of examining these hard problems and in finding solutions.

Pages: 1 2 3

Reference this article
Mundie, C. "The Next Decade in HPC ," CTWatch Quarterly, Volume 1, Number 4, November 2005. http://www.ctwatch.org/quarterly/articles/2005/11/the-next-decade-in-hpc/

Any opinions expressed on this site belong to their respective authors and are not necessarily shared by the sponsoring institutions or the National Science Foundation (NSF).

Any trademarks or trade names, registered or otherwise, that appear on this site are the property of their respective owners and, unless noted, do not represent endorsement by the editors, publishers, sponsoring institutions, the National Science Foundation, or any other member of the CTWatch team.

No guarantee is granted by CTWatch that information appearing in articles published by the Quarterly or appearing in the Blog is complete or accurate. Information on this site is not intended for commercial purposes.