Dynamizing static algorithms, with applications to dynamic trees and history independence
Dynamizing static algorithms, with applications to dynamic trees and history independence
复制标题
动态化静态算法，应用于动态树和历史独立性
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Maverick Woo
中科院分区：
文献类型：
--
作者：
Umut A. Acar;G. Blelloch;R. Harper;Jorge L. Vittes;Maverick Woo
我们描述了一种用于自动动态静态算法的机器模型，并将其应用于与历史无关的数据结构。在此模型中表达的静态程序是通过以动态依赖图的形式跟踪代码和数据之间的依赖性来自动动态的。为了研究这种自动动态算法的性能，我们提出了基于痕量稳定性的分析技术。作为模型使用的一个示例，我们动态了Miller和Reif的平行树收缩算法，以获得Sleator和Tarjan动态树问题的独立于历史的数据结构。
We describe a machine model for automatically dynamizing static algorithms and apply it to history-independent data structures. Static programs expressed in this model are dynamized automatically by keeping track of dependences between code and data in the form of a dynamic dependence graph. To study the performance of such automatically dynamized algorithms we present an analysis technique based on trace stability. As an example of the use of the model, we dynamize the Parallel Tree Contraction Algorithm of Miller and Reif to obtain a history-independent data structure for the dynamic trees problem of Sleator and Tarjan.