« 一只熟睡的咪 | Blog首页 | 《深入浅出Oracle》一书修订进度 »

Donald Knuth:串行并行、单线程及多线程

在7月号的程序员杂志上刊登了一篇Donald Knuth的访谈录，其中关于并行与串行，单线程以及多线程的探讨颇引起了我的兴趣，程序员网站上提供了部分中文版译文，英文在这里。学习且记录一下。

首先是Andrew的提问：
Andrew: One of the emerging problems for developers, especially client-side developers, is changing their thinking to write programs in terms of threads. This concern, driven by the advent of inexpensive multicore PCs, surely will require that many algorithms be recast for multithreading, or at least to be thread-safe. So far, much of the work you've published for Volume 4 of The Art of Computer Programming (TAOCP) doesn't seem to touch on this dimension. Do you expect to enter into problems of concurrency and parallel programming in upcoming work, especially since it would seem to be a natural fit with the combinatorial topics you're currently working on?
Andrew：对于开发者，尤其是客户端开发者，正在面临一个日渐明显的问题，即改变他们的思考方式，从线程的角度去编写程序。这个问题是由廉价的多核PC的出现导致的。它一定需要很多算法进行多线程化的改造，至少也需要做到线程安全的。到目前为止，从你已经发布的《计算加程序设计的艺术》（TAOCP）第4卷的大部分内容来看，还没有涉及到这方面内容。你接下来的工作会和并发与并行程序设计有关么？尤其是这个问题天生就与你现在研究的组合算法非常适合。

Donald: The field of combinatorial algorithms is so vast that I'll be lucky to pack its sequential aspects into three or four physical volumes, and I don't think the sequential methods are ever going to be unimportant. Conversely, the half-life of parallel techniques is very short, because hardware changes rapidly and each new machine needs a somewhat different approach. So I decided long ago to stick to what I know best. Other people understand parallel machines much better than I do; programmers should listen to them, not me, for guidance on how to deal with simultaneity.
Donald：组合算法的研究领域非常庞杂，而我将有幸在三或四卷书中介绍它串行方面的内容，我认为串行方法的重要性不会降低。相反，并行技术的"半衰期"其实非常短，因为硬件总在快速地变化，每一个新的机器都需要一些不同的方法。所以，很久以前我就决定在书中保留我最了解的内容。有很多人比我更了解并行机器，他们可以指导你如何面对同时性的问题；程序员应该听听他们的建议，而不是我的。

Andrew: Vendors of multicore processors have expressed frustration at the difficulty of moving developers to this model. As a former professor, what thoughts do you have on this transition and how to make it happen? Is it a question of proper tools, such as better native support for concurrency in languages, or of execution frameworks? Or are there other solutions?
Andrew：很多多核处理器的供应商都在帮助开发者转移到多核模型的过程中，表现得力不从心。做为一名著名的教授，你对于这种转变有什么看法？什么因素才能促使这种转变？如果有更好的工具可以解决问题么，比如在语言中加入对并发更好的本地支持，或者使用框架？或者还有其他的方案么？

Donald: I don't want to duck your question entirely. I might as well flame a bit about my personal unhappiness with the current trend toward multicore architecture. To me, it looks more or less like the hardware designers have run out of ideas, and that they're trying to pass the blame for the future demise of Moore's Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won't be surprised at all if the whole multithreading idea turns out to be a flop, worse than the "Itanium" approach that was supposed to be so terrific--until it turned out that the wished-for compilers were basically impossible to write.
Donald：我不想回避你的问题。也许我个人的一些观点会为当前流行的多核架构趋势泼一盆冷水。在我看来，这种现象或多或少是由于硬件设计者已经无计可施了导致的，他们将Moore定律失效的责任推脱给软件开发者，而他们给我们的机器只是在某些指标上运行得更快了而已。如果多线程的想法被证明是失败的，我一点都不会感到惊讶，也许这比当年的Itanium还要糟糕----人们基本上无法开发出它所需要的编译器。

Let me put it this way: During the past 50 years, I've written well over a thousand programs, many of which have substantial size. I can't think of even five of those programs that would have been enhanced noticeably by parallelism or multithreading. Surely, for example, multiple processors are no help to TeX.[1]
这么说吧：在过去的50年间，我编写过一千多个程序，其中有很多规模都很可观。但是如果说哪些程序的性能可以在并行或多核环境下有明显的改进，我恐怕连五个都说不来。比如，多核处理器对TeX肯定没有什么帮助。

How many programmers do you know who are enthusiastic about these promised machines of the future? I hear almost nothing but grief from software people, although the hardware folks in our department assure me that I'm wrong.
你听说过有多少程序员对这种未来一片光明的机器抱有强烈的兴趣？我几乎没有听说过，除了他们的诉苦。尽管我们学院那些搞硬件的家伙一直想让我相信我是错的。

I know that important applications for parallelism exist--rendering graphics, breaking codes, scanning images, simulating physical and biological processes, etc. But all these applications require dedicated code and special-purpose techniques, which will need to be changed substantially every few years.
我知道有很多重要的应用依赖于并行----图形渲染、密码破解、图像扫描、物理与生物过程模拟等等。但是这些应用需要非常专业的代码以及特定用途的技术，而这些技术无疑每隔若干年都要变化。

Even if I knew enough about such methods to write about them in TAOCP, my time would be largely wasted, because soon there would be little reason for anybody to read those parts. (Similarly, when I prepare the third edition of Volume 3 I plan to rip out much of the material about how to sort on magnetic tapes. That stuff was once one of the hottest topics in the whole software field, but now it largely wastes paper when the book is printed.)
即使我对那些方法非常了解，可以把它们写入TAOCP中，这对于我的时间也是巨大的浪费，因为过不了多久，这部分内容就没有什么价值值得别人去读它了。（类似地，当我在准备第3卷的第三版时，也打算删除掉关于如何在磁带上排序的内容。这些内容曾经是软件领域里最热门的主题，现在再把它印在书中就是巨大的浪费了。）

The machine I use today has dual processors. I get to use them both only when I'm running two independent jobs at the same time; that's nice, but it happens only a few minutes every week. If I had four processors, or eight, or more, I still wouldn't be any better off, considering the kind of work I do--even though I'm using my computer almost every day during most of the day. So why should I be so happy about the future that hardware vendors promise? They think a magic bullet will come along to make multicores speed up my kind of work; I think it's a pipe dream. (No--that's the wrong metaphor! "Pipelines" actually work for me, but threads don't. Maybe the word I want is "bubble.")
我今天所用的机器有两个处理器。而我只有在同时运行两个独立的作业时，才会用到这两个处理器；这样很好，不过每周这种情况只会发生几分钟而已。如果我有四个、八个甚至更多的处理器，我同样得不到任何好处，想一想我是做什么的----我几乎每天每时每刻都在使用计算机。所以，我为什么要为硬件供应商承诺的未来而高兴？他们认为多核的到来可以为我的工作提速，我认为这是"白日梦"（pipe dream）。（不----这个比喻不准确！我是会用"Pipeline"的，但是不会用线程。也许我应该说这是个"泡影（bubble）"）

From the opposite point of view, I do grant that web browsing probably will get better with multicores. I've been talking about my technical work, however, not recreation. I also admit that I haven't got many bright ideas about what I wish hardware designers would provide instead of multicores, now that they've begun to hit a wall with respect to sequential computation. (But my MMIX design contains several ideas that would substantially improve the current performance of the kinds of programs that concern me most--at the cost of incompatibility with legacy x86 programs.)
不过，我认为Web浏览器可能会由于多核的出现而有所改变。我是从技术性的工作，而不是消遣的角度在说。我也承认我还没有什么很好的想法，到底硬件设计者应该给我们除多核以外什么样的产品，不过他们现在在串行计算上的确遇到了麻烦。（但是我的MMIX设计中包含了很多考量，可以有效地提高我最关注的一些程序当前的性能----代价是与遗留的x86程序无法兼容。）

By eygle on 2008-07-14 10:42 | Comments (0) | OraNews | 1972 |

News