检索结果-内蒙古大学图书馆

An Experimental Analysis of self-adjusting computation

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2009年第1期32卷 3-3:53页

作者： Acar, Umut A. Blelloch, Guy E. Blume, Matthias Harper, Robert Tangwongsan, Kanat Toyota Technol Inst Chicago IL USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

Recent work on adaptive functional programming (AFP) developed techniques for writing programs that can respond to modifications to their data by performing change propagation. To achieve this, executions of programs are represented with dynamic dependence graphs (DDGs) that record data dependences and control dependences in away that a change-propagation algorithm can update the computation as if the program were from scratch, by re-executing only the parts of the computation affected by the changes. Since change-propagation only re-executes parts of the computation, it can respond to certain incremental modifications asymptotically faster than recomputing from scratch, potentially offering significant speedups. Such asymptotic speedups, however, are rare: for many computations and modifications, change propagation is no faster than recomputing from scratch. In this article, we realize a duality between dynamic dependence graphs and memoization, and combine them to give a change-propagation algorithm that can dramatically increase computation reuse. The key idea is to use DDGs to identify and re-execute the parts of the computation that are affected by modifications, while using memoization to identify the parts of the computation that remain unaffected by the changes. We refer to this approach as self-adjusting computation. Since DDGs are imperative, but (traditional) memoization requires purely functional computation, reusing computation correctly via memoization becomes a challenge. We overcome this challenge with a technique for remembering and reusing not just the results of function calls (as in conventional memoization), but their executions represented with DDGs. We show that the proposed approach is realistic by describing a library for self-adjusting computation, presenting efficient algorithms for realizing the library, and describing and evaluating an implementation. Our experimental evaluation with a variety of applications, ranging from simple list pr

关键词： Languages Performance Algorithms computational geometry dynamic algorithms dynamic dependence graphs memoization performance self-adjusting computation

来源：评论

学校读者我要写书评

暂无评论

A Cost Semantics for self-adjusting computation 09

A Cost Semantics for Self-Adjusting Computation

引用

36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Ley-Wild, Ruy Acar, Umut A. Fluet, Matthew Carnegie Mellon Univ Pittsburgh PA 15213 USA Toyota Technol Inst Chicago IL USA

ISBN: (纸本)9781605583792

self-adjusting computation is an evaluation model in which programs can respond efficiently to small changes to their input data by using a change-propagation mechanism that updates computation by re-building only the parts affected by changes. Previous work has proposed language techniques for self-adjusting computation and showed the approach to be effective in a number of application areas. However, due to the complex semantics of change propagation and the indirect nature of previously proposed language techniques, it remains difficult to reason about the efficiency of self-adjusting programs and change propagation. In this paper, we propose a cost semantics for self-adjusting computation that enables reasoning about its effectiveness. As our source language, we consider a direct-style lambda-calculus with first-class mutable references and develop a notion of trace distance for source programs. To facilitate asymptotic analysis, we propose techniques for composing and generalizing concrete distances via trace contexts (traces with holes). We then show how to translate the source language into a self-adjusting target language such that the translation (1) preserves the extensional semantics of the source programs and the cost of from-scratch runs, and (2) ensures that change propagation between two evaluations takes time bounded by their relative distance. We consider several examples and analyze their effectiveness by considering upper and lower bounds.

关键词： Languages self-adjusting computation cost semantics

来源：评论

学校读者我要写书评

暂无评论

Functional Programming for Dynamic and Large Data with self-adjusting computation 14

Functional Programming for Dynamic and Large Data with Self-...

引用

19th ACM SIGPLAN International Conference on Functional Programming (ICFP)

作者： Chen, Yan Acar, Umut A. Tangwongsan, Kanat Max Planck Inst Software Syst Saarbrucken Germany Carnegie Mellon Univ Pittsburgh PA 15213 USA INRIA Villers Les Nancy France Mahidol Univ Int Coll Salaya Nakhon Pathom Thailand

ISBN: (纸本)9781450328739

Combining type theory, language design, and empirical work, we present techniques for computing with large and dynamically changing datasets. Based on lambda calculus, our techniques are suitable for expressing a diverse set of algorithms on large datasets and, via self-adjusting computation, enable computations to respond automatically to changes in their data. To improve the scalability of self-adjusting computation, we present a type system for precise dependency tracking that minimizes the time and space for storing dependency metadata. The type system eliminates an important assumption of prior work that can lead to recording spurious dependencies. We present a type-directed translation algorithm that generates correct self-adjusting programs without relying on this assumption. We then show a probabilistic-chunking technique to further decrease space usage by controlling the fundamental space-time tradeoff in self-adjusting computation. We implement and evaluate these techniques, showing promising results on challenging benchmarks involving large graphs.

关键词： self-adjusting computation information-flow type system granularity control incremental graph algorithms performance

来源：评论

学校读者我要写书评

暂无评论

Traceable Data Types for self-adjusting computation 10

Traceable Data Types for Self-Adjusting Computation

引用

ACM SIGPLAN Conference on Programming Language Design and Implementation

作者： Acar, Umut A. Blelloch, Guy Ley-Wild, Ruy Tangwongsan, Kanat Turkoglu, Duru Max-Planck Institute for Software Systems Kaiserslautern Germany Carnegie Mellon University Pittsburgh PA USA University of Chicago Chicago IL USA

ISBN: (纸本)9781450300193

self-adjusting computation provides an evaluation model where computations can respond automatically to modifications to their data by using a mechanism for propagating modifications through the computation. Current approaches to self-adjusting computation guarantee correctness by recording dependencies in a trace at the granularity of individual memory operations. Tracing at the granularity of memory operations, however, has some limitations: it can be asymptotically inefficient (e.g., compared to optimal solutions) because it cannot take advantage of problem-specific structure, it requires keeping a large computation trace (often proportional to the runtime of the program on the current input), and it introduces moderately large constant factors in practice. In this paper, we extend dependence-tracing to work at the granularity of the query and update operations of arbitrary (abstract) data types, instead of just reads and writes on memory cells. This can significantly reduce the number of dependencies that need to be kept in the trace and followed during an update. We define an interface for supporting a traceable version of a data type, which reports the earliest query that depends on (is changed by) revising operations back in time, and implement several such structures, including priority queues, queues, dictionaries, and counters. We develop a semantics for tracing, extend an existing self-adjusting language, Delta ML, and its implementation to support traceable data types, and present an experimental evaluation by considering a number of benchmarks. Our experiments show dramatic improvements on space and time, sometimes by as much as two orders of magnitude.

关键词： self-adjusting computation traceable data types

来源：评论

学校读者我要写书评

暂无评论

Imperative self-adjusting computation

Imperative Self-Adjusting Computation

引用

35th ACM-SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Acar, Umut A. Ahmed, Amal Blume, Matthias Toyota Technol Inst Chicago IL USA

ISBN: (纸本)9781595936899

self-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can change over time in modifiable references and to let computations construct traces that can drive change propagation. After changes have occurred, change propagation updates the result of the computation by re-evaluating only those expressions that depend on the changed data. Previous approaches to self-adjusting computation require that modifiable references be written at most once during execution - this makes the model applicable only in a purely functional setting. In this paper, we present techniques for imperative self-adjusting computation where modifiable references can be written multiple times. We define a language SAIL (self-adjusting Imperative Language) and prove consistency, i.e., that change propagation and from-scratch execution are observationally equivalent. Since SAIL programs are imperative, they can create cyclic data structures. To prove equivalence in the presence of cycles in the store, we formulate and use an untyped, step-indexed logical relation, where step indices are used to ensure well-foundedness. We show that SAIL accepts an asymptotically efficient implementation by presenting algorithms and data structures for its implementation. When the number of operations (reads and writes) per modifiable is bounded by a constant, we show that change propagation becomes as efficient as in the non-imperative case. The general case incurs a slowdown that is logarithmic in the maximum number of such operations. We describe a prototype implementation of SAIL as a Standard ML library. © 2008 ACM.

关键词： self-adjusting computation incremental computation step-indexed logical relations imperative programming change propagation memoization mutable state

来源：评论

学校读者我要写书评

暂无评论

Memory Management for self-adjusting computation 08

Memory Management for Self-Adjusting Computation

引用

International Symposium on Memory Management

作者： Hammer, Matthew A. Acar, Umut A. Toyota Technol Inst Chicago IL USA

ISBN: (纸本)9781605581347

The cost of reclaiming,pace with traversal-based garbage collection is inversely proportional to the amount of free memory, i.e., O(1 /(1 - f)), where f is the fraction of memory that is live. Consequently, the cost of garbage collection can be very high when the size of the live data remains large relative to the available free space. Intuitively, this is because allocating it small amount of memory,pace will require the garbage collector to traverse a fraction of the memory only to discover little garbage. This is unfortunate because in some application domains the size of the memory-resident data can be generally high. This can cause high GC overheads, especially when generational assumptions do not hold. One Such application domain is self-adjusting computation, where computations use memory-resident execution traces ill order to respond to changes to their state (e.g., inputs) efficiently. This paper proposes memory-management techniques for self-adjusting computation that remain efficient even when the size of the live data is large. More precisely, the proposed techniques guarantee O(1) amortized cost for each reclaimed memory object. We propose it set of primitives for self-adjusting computation that support the proposed memory management techniques. The primitives provide in operation for allocating memory: we reclaim unused memory automatically. We implement it library for supporting the primitives in the C language and perform an experimental evaluation. Our experiments show that the approach can be implemented with reasonably small constant-factor overheads and that the programs written using the library behave optimally. Compared to previous implementations, We measure up to all order of magnitude improvement in performance and up to it 75% reduction in space usage.

关键词： self-adjusting computation memory management garbage collection memoization dynamic dependence graphs dynamic algorithms computational geometry performance

来源：评论

学校读者我要写书评

暂无评论

CEAL: A C-Based Language for self-adjusting computation 09

CEAL: A C-Based Language for Self-Adjusting Computation

引用

ACM SIGPLAN Conference on Programming Language Design and Implementation

作者： Hammer, Matthew A. Acar, Umut A. Chen, Yan Toyota Technol Inst Chicago Chicago IL USA

ISBN: (纸本)9781605583921

self-adjusting computation offers a language-centric approach to writing programs that can automatically respond to modifications to their data (e.g., inputs). Except for several domain-specific implementations, however, all previous implementations of self-adjusting computation assume mostly functional, higher-order languages such as Standard ML. Prior to this work, it was not known if self-adjusting computation can be made to work with low-level, imperative languages such as C without placing undue burden on the programmer. We describe the design and implementation of CEAL: a C-based language for self-adjusting computation. The language is fully general and extends C with a small number of primitives to enable writing self-adjusting programs in a style similar to conventional C programs. We present efficient compilation techniques for translating CEAL programs into C that can be compiled with existing C compilers using primitives supplied by a run-time library for self-adjusting computation. We implement the proposed compiler and evaluate its effectiveness. Our experiments show that CEAL is effective in practice: compiled self-adjusting programs respond to small modifications to their data by orders of magnitude faster than recomputing from scratch while slowing down a from-scratch run by a moderate constant factor. Compared to previous work, we measure significant space and time improvements.

关键词： self-adjusting computation compilation control and data flow dominators tail calls trampolines performance

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Parallel Dynamic Tree Contraction via self-adjusting computation 17

Brief Announcement: Parallel Dynamic Tree Contraction via Se...

引用

29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Acar, Umut A. Aksenov, Vitaly Westrick, Sam Carnegie Mellon Univ Pittsburgh PA 15213 USA INRIA Paris France ITMO Univ St Petersburg Russia

ISBN: (纸本)9781450345934

Dynamic algorithms are used to compute a property of some data while the data undergoes changes over time. Many dynamic algorithms have been proposed but nearly all are sequential. In this paper, we present our ongoing work on designing a parallel algorithm for the dynamic trees problem, which requires computing a property of a forest as the forest undergoes changes. Our algorithm allows insertion and/or deletion of both vertices and edges anywhere in the input and performs updates in parallel. We obtain our algorithm by applying a dynamization technique called self-adjusting computation to the classic algorithm of Miller and Reif for tree contraction.

关键词： change propagation tree contraction dynamic parallel self-adjusting computation

来源：评论

学校读者我要写书评

暂无评论

self-adjusting computation 09

Self-Adjusting Computation

引用

ACM Special Interest Group on Programming Languages Symposium on Partial Evaluation and Semantics-Based Program Manipulation

作者： Umut A. Acar Toyota Technological Institute at Chicago

ISBN: (纸本)9781605583273

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 some recent advances.

关键词： Incremental computation self-adjusting computation Compilers Run-Time Systems Memory Management computational Geometry Scientific Computing Machine Learning computational Biology Languages Design Algorithms Performance Experimentation Bioinformatics experimentation Machine Learning Language Incremental Store management algorithms Artificial Intelligence arithmetic computational geometry compilers Scientific computing data dependency computational Biology

来源：评论

学校读者我要写书评

暂无评论

Kinetic 3D convex hulls via self-adjusting computation 07

Kinetic 3D convex hulls via self-adjusting computation

引用

23rd Annual Symposium on computational Geometry, SCG'07

作者： Acar, Umut A. Blelloch, Guy E. Tangwongsan, Kanat Toyota Technological Institute Chicago IL Japan Carnegie Mellon University Pittsburgh PA United States

No abstract available

ISBN: (纸本)1595937056

No abstract available

关键词： convex hulls self-adjusting computation kinetic data structures

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：