隨著系統(tǒng)規(guī)模的增加,大規(guī)模并行計算機的平均故障間隔時間遠低于許多大規(guī)�？茖W應用的運行時間,因此大規(guī)模科學應用必須能夠容忍硬件錯誤。傳統(tǒng)的回滾恢復協(xié)議是目前大規(guī)模系統(tǒng)中常用的容錯技術(shù),在恢復時失效進程上的計算全部在一個處理器上重算。這是對計算資源的浪費,也使得恢復時間不可能小于前一個檢查點和故障發(fā)生時刻之間的時間間隔。 為了縮短故障恢復時間,本文提出了一種新的容錯方法:容錯并行算法。文章從容錯并行算法的理論基礎、概念、設計方法及支撐工具等幾個方法對容錯并行算法進行了深入的研究,并對容錯并行算法的性能進行了分析和測試。本文所做的創(chuàng)新工作主要體現(xiàn)在以下幾點: 1、給出了并行計算在系統(tǒng)出現(xiàn)故障的情況下的可靠性定義,并基于任務依賴圖給出了并行計算可靠性的定量分析方法;基于此分析方法,分析和比較了時間冗余和空間冗余的容錯技術(shù)對并行計算可靠性的影響。 2、為了縮短故障恢復時間,有效提高并行計算的可靠性,提出了一種新的容錯方法:容錯并行算法。容錯并行算法執(zhí)行時在數(shù)據(jù)保存段保存計算的中間狀態(tài)以保證故障時正確的復算;發(fā)生故障時未發(fā)生故障的處理器通過在線的方式感知故障處理機的故障,并自動通過并行復算恢復故障...

【文章頁數(shù)】：136 頁

【學位級別】：博士

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 大規(guī)模系統(tǒng)的可靠性問題
        1.1.1 單芯片處理器制造工藝不斷發(fā)展
        1.1.2 大規(guī)模系統(tǒng)的規(guī)模不斷增加
        1.1.3 大規(guī)模系統(tǒng)的可靠性受到挑戰(zhàn)
        1.1.4 軟件實現(xiàn)的硬件容錯
    1.2 容錯研究基礎
        1.2.1 基本概念
        1.2.2 并行程序的故障類型
    1.3 課題研究內(nèi)容
        1.3.1 課題來源
        1.3.2 課題研究重點
        1.3.3 課題研究難點
    1.4 相關(guān)研究工作
        1.4.1 Checkpointing 技術(shù).
        1.4.2 消息日志
        1.4.3 MPI 容錯
        1.4.4 基于算法的容錯
        1.4.5 其它工作
    1.5 本文的主要工作和創(chuàng)新
    1.6 論文結(jié)構(gòu)
第二章 并行計算的可靠性分析
    2.1 面向可靠性分析的并行程序任務依賴圖模型
        2.1.1 任務依賴圖模型的提出
        2.1.2 并行程序的任務依賴圖模型
        2.1.3 任務依賴圖的組成
    2.2 并行計算的可靠性計算
        2.2.1 規(guī)則和定律
        2.2.2 任務結(jié)點可靠度的計算
        2.2.3 并行計算可靠度的計算
    2.3 并行計算的容錯技術(shù)分析
        2.3.1 時間冗余技術(shù)
        2.3.2 空間冗余技術(shù)
        2.3.3 冗余技術(shù)討論
    2.4 小結(jié)
第三章 容錯并行算法的概念與設計方法
    3.1 基本思想
        3.1.1 一個例子
        3.1.2 與傳統(tǒng)方法的比較
    3.2 容錯并行算法的概念
    3.3 設計方法
        3.3.1 程序段的劃分
        3.3.2 故障檢測段的設計方法
        3.3.3 數(shù)據(jù)保存段的設計方法
        3.3.4 復算段的設計方法
    3.4 小結(jié)
第四章 容錯并行算法的設計與分析
    4.1 容錯并行算法的分類
    4.2 矩陣LU 分解的容錯并行算法.
        4.2.1 矩陣LU 分解的算法描述.
        4.2.2 矩陣LU 分解的容錯并行算法設計與分析.
    4.3 快速傅里葉變換的容錯并行算法
        4.3.1 快速傅里葉變換的算法描述
        4.3.2 FFT 的容錯并行算法設計與分析
    4.4 排序算法的容錯并行算法
        4.4.1 桶排序的算法描述
        4.4.2 桶排序的容錯并行算法設計與分析
    4.5 小結(jié)
第五章 容錯并行算法的編譯輔助工具
    5.1 程序段選擇的實現(xiàn)
    5.2 故障檢測段的實現(xiàn)
    5.3 狀態(tài)保存段的實現(xiàn)
        5.3.1 控制流分析
        5.3.2 數(shù)據(jù)流分析
        5.3.3 保存代碼生成
    5.4 復算段的實現(xiàn)
        5.4.1 恢復數(shù)據(jù)代碼生成
        5.4.2 并行復算代碼生成
    5.5 小結(jié)
第六章 容錯并行算法的性能分析與實驗
    6.1 容錯并行算法的開銷來源
    6.2 容錯并行算法的性能度量
        6.2.1 執(zhí)行時間
        6.2.2 加速比
        6.2.3 效率
    6.3 系統(tǒng)參數(shù)對容錯并行算法性能的影響
        6.3.1 程序段的運行時間對性能的影響
        6.3.2 數(shù)據(jù)保存開銷對性能的影響
        6.3.3 故障率對性能的影響
        6.3.4 并行復算加速比對性能的影響
    6.4 實驗配置
    6.5 實驗性能
    6.6 實驗結(jié)論
    6.7 小結(jié)
第七章 結(jié)束語
    7.1 工作總結(jié)
    7.2 研究展望
致謝
參考文獻
攻讀博士學位期間已發(fā)表和待發(fā)表的論文
攻讀博士學位期間參與的科研項目



本文編號：3848146