Cache Efficient Value Iteration Value Iteration (VI) is a powerful, though time consuming, approach to solve Markov Decision Processes (MDPs). Exisitng 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 backups. We demonstrate experimentally that the strategies proposed by us, in this paper, to improve the cache efficiency of VI result in speedups of up to a factor of 3.7 when incorporated into stateoftheart VI software.

Evaluation of a Practical Markov modelbased Methodology for Energy Efficiency in Multicore Systems Greedy heuristic methodologies perform the dynamic voltage and frequency scaling (DVFS) on multicore systems based on the localized system performance data. The characteristics of applications such as their floatingpoint operations and memory loads can vary largely during the runtime. As such, the heuristicbased prediction of Voltage and Frequency (VF) is suboptimal and leads to performance degradation in applications with widely varying computational demands. This work develops a new approach, Markovbased DVFS (MDVFS), which formulates a Hidden Markov Model (HMM) for predicting core utilizations (states) and VF levels based on the observable execution times of cores across application time intervals. MDVFS uses the wellknown Kmeans algorithm for defining states and observation levels of HMM. For solving the HMM problem, MDVFS uses the Viterbi algorithm to find a sequence of VF levels that most likely generate the execution time sequence. This paper uses EnergyDelay2 Product (ED2 P) for measuring system energy efficiency and compares the performance of MDVFS to 2 predictive algorithms, history and feedback controller, on multiple applications. Experimental results show that for 5 out of 6 applications MDVFS, on the average, obtains up to 34% faster execution runtime and improves ED2 P by 24% compared to the history and the feedback controller.