Studies on Stochastic Dynamic Programming Based on Parametric Multi-stage Estimation

基于参数多阶段估计的随机动态规划研究

• 批准号: 12680448
• 负责人: KIUIWA Jun
• 金额: $ 2.18万
• 依托单位: Kobe University of Commerce
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12680448/
• 关键词: LRU stack; Operating System; Dynamic Programming; Optimal Reconstruction; Monotone Property; LRUスタック; dynamic table(動的な表); dynamic programing(動的計画法); 最適戦略; オンラインアルゴリズム; 插入・削除リクエスト; メモリの使用効率; ならし解析; データ構造

We investigate an optimal reconstruction method for an implementation of LRU stacks. The LRU stack is a linear list in which elements are stored in the least recently used order. If it were implemented by using an array and the accessed element were moved to the front for each time, the total cost would be very large. Barriga and Ayani proposed an effective method where the moving of elements is delayed until ascending/descending access pattern is violated. However, this method is not effective when the access pattern is irregular. So we present our implementation of an LRU stack, where an array and a linked list are mixedly used. Then an effective way of reconstructing the stack can be considered by using the lazy update technique proposed by Barriga and Ayani. Next we formulate the expected costs with remaining n requests by dynamic programming. Analyzing the equations, we can obtain an optimal reconstruction timing of the stack, and some monotone results. We make the same analysis of different two types of access patterns, that is, the uniform and the truncated geometric distributions of requests. In particular, if requests are uniformly distributed, it turns out that we have to wait the reconstruction until the maximum accessed index exceeds 5N/7, where N is the total number of elements.

我们研究了一种实现LRU堆栈的最佳重建方法。 LRU堆栈是一个线性列表，其中元素以最近使用的顺序存储。如果使用阵列实现并每次将访问的元素移到前面，则总成本将非常大。 Barriga和Ayani提出了一种有效的方法，即延迟元素的移动，直到违反上升/降序访问模式。但是，当访问模式不规则时，此方法无效。因此，我们介绍了LRU堆栈的实现，其中使用了数组和链接列表。然后，可以使用Barriga和Ayani提出的懒惰更新技术来考虑重建堆栈的有效方法。接下来，我们通过动态编程通过剩余的N请求来制定预期的成本。分析方程式，我们可以获得堆栈的最佳重建时间，并获得一些单调结果。我们对两种类型的访问模式进行相同的分析，即请求的统一和截断的几何分布。特别是，如果请求统一分布，则事实证明，我们必须等待重建，直到最大访问的索引超过5N/7，其中n是元素的总数。

项目成果

J. Kiuiwa, K. Kikuta, M. Tamaki and T. Hamada: "An optimal reconstruction strategy of LRU stacks"Kobe. University of Commerce Working Paper. No. 188. (2002)

J. Kiuiwa、K. Kikuta、M. Tamaki 和 T. Hamada：“LRU 堆栈的最优重建策略”Kobe。

J.Kiniwa, K.Kikuta, M.Tamaki, T.Hamada: ""An optimal reconstruction strategy of LRU stacks""Kobe University of Commerce, Working Paper. No.188. (2002)

J.Kiniwa、K.Kikuta、M.Tamaki、T.Hamada：““LRU 堆栈的最优重建策略””神户商业大学，工作论文。

Jun Kiniwa, Kensaku kikuta, Mitsushi Tamaki, Toshio Hamada: "An optimal reconstruction strategy of LRU stacks"Kobe University of Commerce, Working Paper No.188. 188. (2002)

Jun Kiniwa、Kensaku kikuta、Mitsushi Tamaki、Toshio Hamada：“LRU 堆栈的最优重建策略”神户商业大学，工作论文第 188 号。