Cache efficient Value Iteration using clustering and annealing
Cache efficient Value Iteration using clustering and annealing
复制标题
使用聚类和退火来缓存高效的值迭代
DOI：
10.1016/j.comcom.2020.04.058
复制
发表时间：
2020
影响因子：
6
通讯作者：
Sahni, Sartaj
中科院分区：
文献类型：
--
作者：
Jain, Anuj;Sahni, Sartaj
值迭代（VI）是一种强大的，但耗时的方法来解决马尔可夫决策过程（MDP）。现有的算法VI招致大量的缓存未命中。动机的观察，在现代计算机上，高速缓存未命中的成本是两到三个数量级以上的算术运算，我们探索的可能性，提高性能的VI通过减少高速缓存未命中的数量，可能在增加的算术运算的数量为代价。通过对MDP状态空间的分区执行VI来获得高速缓存效率，该分区适合于代码将在其上运行的计算平台的最低级别高速缓存。进一步的性能改善，动机的使用MDP分区，获得使用聚类方案来构建分区和退火时间表收敛到目标精度。我们通过实验证明，将分区，聚类和退火到最先进的VI软件中，在我们的计算平台上加速高达8.1倍。
Value Iteration (VI) is a powerful, though time consuming, approach to solve Markov Decision Processes (MDPs). Existing algorithms for VI incur a large number of cache misses. Motivated by the observation that, on modern computers, the cost of a cache miss is two to three orders of magnitude more than that of an arithmetic operation, we explore the possibility of improving the performance of VI by reducing the number of cache misses, possibly at the expense of increasing the number of arithmetic operations. Cache efficiency is obtained by performing VI on partitions of the MDP state space that fit in the lowest level cache of the computational platform on which the code is to run. Further performance improvement, motivated by the use of MDP partitions, is obtained using a clustering scheme to construct the partitions and an annealing schedule to converge to the target accuracy. We demonstrate experimentally that incorporating partitioning, clustering, and annealing into state-of-the-art VI software result in speedups of up to a factor of 8.1 on our computational platforms.
登录
查看更多内容
预算受限马尔可夫决策过程的高效算法
影响因子：
6.8
作者：
C. Caramanis;N. Dimitrov;D. Morton
通讯作者：
D. Morton
DOI：
--
发表时间：
1973
期刊：
影响因子：
--
作者：
V. Rao;L. Thomas
通讯作者：
L. Thomas
加速 MDP 求解器的优先级划分方法
影响因子：
6
作者：
D. Wingate;Kevin Seppi
通讯作者：
Kevin Seppi
DOI：
--
发表时间：
1986
期刊：
23rd ACM/IEEE Design Automation Conference
影响因子：
--
作者：
S. Nahar;S. Sahni;E. Shragowitz
通讯作者：
E. Shragowitz
Nussinov RNA 折叠的缓存和节能算法
影响因子：
3
作者：
Chunchun Zhao;S. Sahni
通讯作者：
S. Sahni