Self-adjusting computation: (an overview)
Self-adjusting computation: (an overview)
复制标题
自调整计算：（概述）
DOI：
10.1145/1480945.1480946
复制
发表时间：
2009
影响因子：
--
通讯作者：
Umut A. Acar
中科院分区：
文献类型：
--
作者：
Umut A. Acar
许多应用程序需要响应对数据的增量修改。由于是增量的，这种修改通常需要对输出进行增量修改，因此可以比从头开始重新计算更快地对它们做出渐进响应。因此，在许多情况下，利用增量特性可以显著提高性能，特别是在输入大小增加时。作为一个参考框架，请注意，在并行计算中，加速比受到处理器数量的限制，通常是一个（小）常数。
然而，设计和开发响应增量修改的应用程序是一项挑战：它通常涉及开发高度特定的复杂算法。自调整计算为这个问题提供了一种语言方法。在自调整计算中，程序通过跟踪计算的动态数据依赖性并根据需要递增地更新其输出来自动有效地响应对其数据的修改。在这次特邀演讲中，我介绍了自调整计算的概述，并简要讨论了开发该方法的进展，并介绍了一些最新进展。
Many applications need to respond to incremental modifications to data. Being incremental, such modification often require incremental modifications to the output, making it possible to respond to them asymptotically faster than recomputing from scratch. In many cases, taking advantage of incrementality therefore dramatically improves performance, especially as the input size increases. As a frame of reference, note that in parallel computing speedups are bounded by the number of processors, often a (small) constant.
Designing and developing applications that respond to incremental modifications, however, is challenging: it often involves developing highly specific, complex algorithms. Self-adjusting computation offers a linguistic approach to this problem. In self-adjusting computation, programs respond automatically and efficiently to modifications to their data by tracking the dynamic data dependences of the computation and incrementally updating their output as needed. In this invited talk, I present an overview of self-adjusting computation and briefly discuss the progress in developing the approach and present some recent advances.