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

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

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

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