A new approach to optimal cache scheduling

DOI10.1016/0020-0190(89)90231-7MaRDI QIDQ1122358zbMATH OpenOpenAlexFDO

Authors Carsten Vogt

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90231-7

zbMATH Keywords

cacheLRU-modelschedulingstorage hierarchy

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25) Algorithms in computer science (68W99)

Review text

An algorithm is presented to optimal cache scheduling in the field of register management for RISC machines or in the development of globally optimal strategies for multiple-stage storage hierarchies. This algorithm answers the following question: is there a sequence of loads and stores such that all blocks lie in the cache at their reference times? Although presented algorithm does not guarantee to yield a solution in all cases, experiments showed that it is powerful to solve problems occurring in practice.

Recommendations

• Periodic scheduling for cache-miss minimisation
• scientific article; zbMATH DE number 4049014
• scientific article; zbMATH DE number 2011837
• scientific article; zbMATH DE number 3991267
• Scheduling expression DAGs for minimal register need

Cites work

• DMIN: An Algorithm for Computing the Optimal Dynamic Allocation in a Virtual Memory Computer
• scientific article; zbMATH DE number 3473307 (Why is no real title available?)
• MIN—an optimal variable-space page replacement algorithm
• Optimal prepaging and font caching
• Principles of Optimal Page Replacement

Cited in

(6)

• Optimal timer-based caching policies for general arrival processes
• Periodic scheduling for cache-miss minimisation
• A dynamic scheduler for the infinite air-cache
• scientific article; zbMATH DE number 220159 (Why is no real title available?)
• Scheduling to Optimize Cache Utilization for Non-Volatile Main Memories
• Critical sizing of LRU caches with dependent requests

This page was built for publication: A new approach to optimal cache scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122358)