并行編程模型的確定性的證明方法及其應用.pdf

1、如何開發(fā)并行程序并保證其正確性是一個研究熱點。由于線程交錯執(zhí)行次序的不確定性，測試、調試工作不易覆蓋所有執(zhí)行情況、不易再現出錯的執(zhí)行，于是即使進行大量的測試、調試工作也不能完全保證程序是正確的。確定性并行技術保證程序在相同輸入下的的所有執(zhí)行是一致的并且能再現執(zhí)行，因而能簡化測試、調試工作。
　　由于對并行確定性現存的認識并不統(tǒng)一，而且在指導測試、調試工作時存在缺陷，因此本文以一個基于共享消息通道的確定性并行編程模型為例，深入研究確

2、定性的內涵、證明方法與以及如何更完善地指導測試、調試工作。
　　為此，本文探討并完成以下工作;
　　1、提出一種能較好的統(tǒng)一認識不同確定性的角度
　　本文指出各種確定性異同的核心因素在于:選擇哪些程序點進行觀察以及如何觀察程序的狀態(tài)。如何選擇兩者進行組合是主觀的，對應了不同的確定性。而一個程序是否滿足某確定性是客觀的，取決于程序的語義和存儲模型。
　　當選定兩個因素后，一個程序是確定的，當且僅當其任意兩次執(zhí)行到達

3、指定程序點的能力相同（都能到達觀察點或者都不能，兩者是對立的），而且（若可以）到達觀察點處時的狀態(tài)觀察起來相同。
　　例如，最終點確定性指在程序執(zhí)行的最終點，觀察整個程序的狀態(tài)。調試確定性指在程序執(zhí)行的斷點處，觀察被調試線程相關的狀態(tài)。
　　2、提出一般性的確定性證明框架，將其應用于一個基于共享消息通道的SPMC模型上并證明模型的最終點確定性和調試確定性
　　本文選定確定性并行編程模型SPMC(single-produ

4、cer-multiple-consumer)作為確定性的研究對象。給出模型的抽象語法、程序狀態(tài)定義和操作語義?；诖?，定義并證明兩種確定性分別用于指導測試、調試工作。由于同時理解形式化的復雜模型和其確定性證明并不容易，為此，本文的介紹思路是先研究一些足夠簡單的確定性并行編程模型，用它們展示證明模型確定性的普遍性框架，最后應用于SPMC模型的研究。
　　總之，本文對確定性的認識更具普遍性而且對測試、調試工作的指導更完善，對確定性的證