I-O密集型并行應(yīng)用性能預(yù)測的研究.pdf

1、計算機領(lǐng)域的一個發(fā)展趨勢是 CPU運算速度的提升要大大快于磁盤的數(shù)據(jù)傳輸效率的改進，它們之間的差距不斷擴大，逐漸成為分布式計算中不可忽視的一個因素。在這個背景下，對并行程序的I/O行為做出準(zhǔn)確的性能預(yù)測就顯得尤其重要，它在發(fā)現(xiàn)系統(tǒng)瓶頸、評估程序性能等方面都有著重要意義。
　　本文獲取運行日志的方式是利用 PMPI接口編寫封套函數(shù)，在封套函數(shù)內(nèi)截獲原始程序的信息，這些封套函數(shù)被編譯為一個動態(tài)庫，它們可以在不重新編譯原始程序的情況下獲

2、得原始程序的運行信息。本文還設(shè)計了一系列規(guī)整化運行日志的方法，以助于后續(xù)的合并、壓縮操作。
　　針對原始程序各個進程的運行日志的內(nèi)容基本一致的特點，本文提出了三種合并算法有效的去除這些冗余信息，并對它們的效果進行了詳盡的分析。其中的基本合并算法在實際應(yīng)用中效率很高，但通用性不佳；基于后綴樹的算法具有最好的時間復(fù)雜度，但實驗表明其效率要低于其他的算法；基于最長公共子序列的合并算法擁有近乎線性的時間復(fù)雜度，具有較好的通用性，并在實驗中

3、表現(xiàn)了不錯的效率，本文最后選用的合并算法是基于最長公共子序列的合并算法。
　　并行程序的運行日志相當(dāng)于將原始程序中的循環(huán)全部展開，導(dǎo)致記錄下來的日志十分龐大。日志中的這類循環(huán)結(jié)構(gòu)可以由本文的循環(huán)收縮算法全部發(fā)現(xiàn)并收縮。日志中的循環(huán)識別問題可以抽象為字符串中的連續(xù)重復(fù)子串識別問題，本文的循環(huán)收縮算法是基于后綴樹的，其最壞時間復(fù)雜度為 O(nlogn)，這一算法的性能要優(yōu)于以往的日志循環(huán)收縮算法，實驗表明本文收縮算法的性能是次優(yōu)算法的