加速比性能模型与可扩展性分析课件.pptVIP

結論： 1.如果工作負載（問題規模）保持不變，那麼效率E隨機器規模的增大而迅速下降，其原因是開銷h比機器規模增加得快，為了使效率保持在一定的水準上，我們可以按比例增大機器規模和問題規模。 2.如果工作負載按指數增長模式，效率要保持恒定或保持良好的加速比，必須使問題規模猛增才行，這樣就會超過記憶體或I/O限制，而問題規模只允許在電腦記憶體可用的限度以內增長。並行電腦的應用模型如下圖：通信界限記憶體界限受限於記憶體模型工作負載（問題規模）機器規模固定負載模型固定時間模型第二章加速比性能模型與可擴展性分析 2.1加速比性能分析 2.2可擴展性分析 2.2.1可擴展性 2.2.2可擴展性分析2.2可擴展性分析 2.2.1可擴展性 1.可擴展性與可編程性增加可擴展性增加可編程性分佈存儲的消息傳遞型多電腦共用存儲型多處理機理想並行電腦 2.可擴展性指標 機器規模（n） 時鐘頻率（f） 問題規模（s） CPU時間（T） I/O需求（d） 存儲容量（m） 通信開銷（h） 電腦價格（c） 程式設計開銷（p） 3.可擴展性的直觀定義 對任意數量（n）的處理機和任意規模（s）的問題，若所有演算法的系統效率E=1，則系統是可擴展的。*加速比性能模型與可擴展性分析2.1加速比性能模型 2.1.1一般概念 1.處理機—時間積 處理機數目與處理時間的乘積用以度量這些處理機運行時的資源利用率。 若一程式在?P臺處理機上運行的時間為Tp，則此P臺處理機在Tp時間間隔內完成的工作最大數量為Tp*P。 可將處理機實際工作曲線對時間的積分看成是這些處理機完成的有效工作量。 效率為有效工作量與最大工作量之比。2.並行度（DegreeOfParallelism—DOP） 並行度（DOP）是在一定時間間隔內執行一個程式所用的處理機的數目。3.並行性分佈圖 執行一個給定的程式時DOP對時間的分佈圖。 DOP與對應時間的間隔之積即為處理機要完成的工作或工作負載。下圖所示為一個並行性分佈圖。DOPt1tt2並行性分佈圖2.1.2加速比1.絕對加速比 將最好的串行演算法與並行演算法相比較. 定義一（與具體機器有關）將最好的串行演算法在一臺上的運行時間與並行演算法在N臺運行的時間相比。 定義二（與具體機器無關）將最好的串行演算法在最快的順序機上的執行時間與並行演算法在並行機上的運行時間相比。2.相對加速比 同一並行演算法在單節點上運行時間與在多個相同節點構成的處理機系統上的運行時間之比。 這種定義側重於描述演算法和並行電腦本身的可擴展性。線性加速比：中間開銷小，通信少，弱耦合計算超線性加速比：當應用需要大記憶體時可能出現病態加速比：加速比遞減，可能是計算量太小2.1.3三種加速比性能模型 1.固定負載加速比性能模型—Amdahl定律 在許多即時應用領域，計算負載的大小常固定。在並行機中，此負載可分佈至多臺並行執行，獲得的加速比稱為fixed-loadspeedup。 一個問題的負載可表示如下：W=Ws+Wp 其中，Ws代表問題中不可並行化的串行部分負載， Wp表示可並行化的部分負載。 則n個節點情況下，加速比可以表示如下：設串行因數α為串行部分所占的比例。即代入即得Amdahl’law：不管採用多少處理機，可望達到的最好加速比：效率En可以表示為：處理機數目n越大，效率En越低。Amdahl定律告訴我們：系統中某一部件由於採用某種更快的執行方式後整個系統性能的提高與這種執行方式的使用頻率或占總執行時間的比例有關。加速比的兩個決定因素：1.電腦執行某個任務的總時間中可被改進部分的時間所占的百分比，即 可被改進部分佔用時間/改進前真個任務的執行時間， 記為Fe，它總小於1。2.改進部分採用改進措施後比沒有採用改進措施前性能提高的倍數，即 改進前改進部分執行時間/改進後改進部分執行時間， 記為Se。例1： 假設將某系統的某一部件的處理速度加快到10倍，但該部件的原處理時間僅為整個運行時間的40%，則整個系統的性能提高了多少？ 解：Fe=0.4，Se=10，例2： 採用哪種實現技術來求浮點數平方根FPSQR的操作對系統的性能影響較大。假設FPSQR操作占整個測試程式執行時間的20%。一種實現方法是採用FPSQR硬體，使FPSQR操作的速度加快到10倍。另一種方法是使所有浮點數據指令的速度加快，使FP指令的速度加快到2倍，還假設