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

我们研究了一种实现LRU堆栈的最佳重构方法。LRU堆栈是一个线性列表，其中的元素按最近最少使用的顺序存储。如果它是通过使用数组实现的，并且每次访问的元素都被移到前面，那么总成本将非常大。Barriga和Ayani提出了一种有效的方法，将元素的移动延迟到上行/下行访问模式被破坏。但是，当访问模式不规则时，该方法效果不佳。因此，我们给出了LRU堆栈的实现，其中数组和链表混合使用。然后，利用Barriga和Ayani提出的延迟更新技术，可以考虑一种有效的堆栈重建方法。接下来，通过动态规划的方法，给出了剩余n个请求的期望成本。通过对这些方程的分析，我们可以得到一个最优的堆栈重构时间，以及一些单调的结果。我们对两种不同类型的访问模式进行了相同的分析，即请求的均匀几何分布和截断几何分布。特别是，如果请求是均匀分布的，那么我们必须等待重建，直到最大访问索引超过5N/7，其中N是元素的总数。

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.