自程式追蹤中萃取指令序列的方法

Extracting Frequent-Instruction Sequences from a Program Trace

傳統函式層側描方法所產生的資訊因過於簡略而不敷現代計算機微架構設計使用。雖然以編譯所得的指令序列為基礎的指令層側描方法可產生較傳統側描方法更為詳細的資訊，但是這些方法多需搭配高價的軟體套件或硬體平台使用。本文提出一個以軟體模擬執行所得的指令序列為基礎的指令層側描方法，稱為Melting。這個方法除了能產生微架構設計所需的詳細資訊外，也不需使用特殊軟硬體，更符合成本效益。我們提出的方法用於萃取出程式的指令動態追蹤中最常出現的指令序列。所得的指令序列資訊可協助快取記憶體及分支預測等計算機微架構設計參考。本文以Dijkstra 演算法為應用範例以説明Melting 的相關演算法及架構。 Classical function-level profiling approaches generate coarse-grained information that is inappropriate for micro-architectural designs. Although modern compilation-based instruction-level profiling approaches provide fine-grained information, they are often platform-dependent. This report presents a simulation-based instruction-level profiling approach that provides fine-grained profiling information. Furthermore, the proposed approach is platform-independent, easy to use and cost-effective. The proposed approach profiles frequent-instruction sequences from the run-time trace of a program. The derived sequence can be applied to facilitate micro-architectural designs. Dijkstra was selected as the target program for demonstration.