【正文】 X 0 0 處理器 B讀 X Cache缺失于 X 0 0 0 處理器 A向 X寫 1 對 X無效 1 0 處理器 B讀 X Cache 缺失于 X 1 1 1 ? 寫更新協(xié)議 在寫入數(shù)據(jù)項時更新該數(shù)據(jù)項的所有副本。因為寫更新協(xié)議必須將所有的寫操作廣播給共享Cache，從而需要更大的帶寬。因此，目前極大多數(shù)的對稱式共享存儲器多處理機都選擇執(zhí)行寫無效協(xié)議。 （ 2）目錄協(xié)議 把共享物理存儲器的共享狀態(tài)存放在一個地方，稱為目錄。目錄協(xié)議保存每個 Cache數(shù)據(jù)塊的狀態(tài)。目錄中的信息包括哪個 Cache擁有該塊的副本，是否處于無效狀態(tài)等 ? 全映象目錄 目錄項中有 N個處理機位和一個重寫位。處理機位表示相應處理機對應的 Cache塊的狀態(tài)。重寫位為“ 1”，且只有一個處理機位為“ 1”，則該處理機可以對該塊進行寫操作 ? 有限目錄： 每個目錄項的指針數(shù)固定。表中每項的標志位少于 N個。因此，限制了一個數(shù)據(jù)塊在各 Cache中能存放的副本數(shù)目。全映象目錄表和有限目錄表都是集中地存入在共享的主存之中，因此需要由主存向各處理機廣播。 ? 鏈式目錄 把目錄分散存放在各個 Cache中，主存只存有一個指針，指向一臺處理機。 通過維護個目錄指針鏈要查找所有放有同一個信息塊的 Cache時，先找到一臺處理機的 Cache，然后順鏈逐臺查找， 直到找到目錄表中的指針為空時為止。它不限制共享數(shù)據(jù)塊的拷貝數(shù)目，又保持了可擴展性。指針的長度以處理機數(shù)目的對數(shù)關系增長， Cache的每個數(shù)據(jù)塊的指針數(shù)目與處理機數(shù)目無關。 第四節(jié) 并行處理語言及算法 在多處理機系統(tǒng)中，并行性存在于不同的層次上，充分開發(fā)其并行性有較大難度，為此，必須從系統(tǒng)結構、操作系統(tǒng)、算法、語言、編譯各方面來統(tǒng)籌協(xié)調地開發(fā)。也就是說，在多處理機設計成功之后，還必須進行并行開發(fā)。本節(jié)將簡要介紹多處理機系統(tǒng)設計在并行性處理中遇到的挑戰(zhàn)以及所采用的并行性處理技術。 1. 并行處理遇到的挑戰(zhàn) 程序可獲得的并行度有限以及相對較高的通信開銷，成為并行處理應用的障礙。這可以用 Amdahl定律解釋，我們通過下面的例題來看。 Amdahl定律是 例題 1： 假設要用 100個處理機獲得 80倍的加速比，那么原來的計算中串行部分該占多大比例呢？ 假設程序僅有兩種執(zhí)行模式：一種是使用所有處理機的并行模式，另一種是僅利用一個處理機的串行模式。在這種簡化下，改進部分的加速比就簡化為處理機個數(shù)，而改進模式所占的比例就是在并行模式中花費的時間。代入上面的公式簡化后得到并行部分所占比例＝ 例題 2：假設一個應用程序在一個 32個處理機的多處理機系統(tǒng)上運行，該處理機訪問一個遠程存儲器需要 200ns。對于這個應用，假設除了涉及通信的存儲器訪問外，所有訪問都命中本地存儲系統(tǒng)。執(zhí)行遠程訪問時處理機會阻塞，處理機的時鐘頻率為 2GHz。如果基本 CPI是,那么多處理機在沒有遠程訪問時比只有 ％的指令涉及遠程訪問時能快多少？ 首先我們來計算 CPI，有 ％遠程訪問的多處理機的 CPI是 CPI=基本 CPI＋遠程請求率 遠程請求開銷 而遠程開銷是 經(jīng)過計算可以得到 CPI＝ += 全部為本地調用的多處理機將會快 。實際的性能分析會更加復雜，因為有些非遠程訪問可能會在本地存儲器系統(tǒng)層次中缺失，并且遠程訪問的時間也不一定會是固定值。 并行度低和遠程通信時延太長，是使用多處理機的兩個最大挑戰(zhàn)。只有在軟件中采用更好的并行算法才能克服并行度低的問題。要減少長時間遠程訪問的時延，可以通過系統(tǒng)結構實現(xiàn)，也可以通過程序員實現(xiàn)。例如，在硬件上緩存共享數(shù)據(jù)，或者在軟件上重新構造數(shù)據(jù)就能增加本地訪問，因而也就減少了遠程訪問的頻率。還可以使用多線程或者預取來減少時延的影響 2. 并行編程模型 ? 蘊式并行編程模型：程序員不顯示地說明并行性，而是讓編譯器和運行支持系統(tǒng)自動加以開發(fā)的編程模型。其最常用的方法是對順序程序實行自動并行化，由編譯器對順序程序的源代碼進行相關性分析，然后使用一組程序變換技術將順序代碼轉換成自然并行 Fortran代碼。 ? 數(shù)據(jù)并行模型：將數(shù)據(jù)分布于不同的處理單元 ,這些處理單元對分布數(shù)據(jù)執(zhí)行相同的操作。數(shù)據(jù)并行程序使用預先分布好的數(shù)據(jù)集。運算操作之間進行數(shù)據(jù)交換操作。數(shù)據(jù)并行操作的同步是在編譯而不是在運行時完成的。從本質上講，數(shù)據(jù)并行編程具有單控制線程且能在數(shù)據(jù)集一級開發(fā)大規(guī)模并行性。 ? 消息傳遞模型：程序中不同進程之間通過顯式方法 (如函數(shù)調用、運算符等 )傳遞消息來相互通信 ,實現(xiàn)進程之間的數(shù)據(jù)交換、同步控制等。消息包括指令、數(shù)據(jù)、同步信號等。因此 ,程序員不僅要關心程序中可并行成分的劃分 ,而且還需關心進程間的數(shù)據(jù)交換。消息的發(fā)送、接收處理將增加并行程序開發(fā)的復雜度。但是它適用于多種并行系統(tǒng) ,如多處理機、可擴展機群系統(tǒng)等 ,且具有靈活、高效的特點。 ? 共享變量模型：限定作用范圍和訪問權限的辦法 ,對進程尋址空間實行共享或限制 ,即利用共享變量實現(xiàn)并行進程間的通信。為了保證能有序地進行 IPC,可利用互斥特性保證數(shù)據(jù)一致性與同步。共享變量模型與傳統(tǒng)的順序程序設計有許多相似之處。程序員只需關心程序中的可并行進程 ,而無需關心進程間的數(shù)據(jù)交換問題。共享變量的數(shù)據(jù)一致性、臨界區(qū)的保護性訪問由編譯器與并行系統(tǒng)來維護。共享變量模型具有編程簡單、易于控制的特點 ,但在實現(xiàn)時則會導致系統(tǒng)開銷增大。 3. 并行語言 （ 1）設計全新的并行語言 可以完全擺脫串行語言的束縛 ,從語言成分上直接支持并行 ,這樣就可以使并行程序的書寫更方便、更自然 ,相應的并行程序也更容易在并行機上實現(xiàn) 缺點：沒有統(tǒng)一計算機模型 雖有并行語言，但每一個被普遍接納 （ 2）擴充已有的串行語言 在現(xiàn)有的程序設計語言的基礎上擴展出能表示并行進程的語句。若用原來的串行編譯器來編譯，標注的并行擴充部分將不起作用，仍將該程序作為一般的串行程序處理。若使用擴充后的并行編譯器來編譯，則該并行編譯器就會根據(jù)標注的要求，將原來串行執(zhí)行的部分轉化為并行執(zhí)行 （ 3）提供并行庫 為已有的串行語言提供并行運行庫。只需要在原來的串行程序中加入對并行庫的調用，就可以實現(xiàn)并行程序設計。如現(xiàn)在流行的 MPI（消息傳遞接口）并行程序設計就屬于這種方式。 （ 4）針對以上的方式實現(xiàn)并行語言，一般采用下述集中編譯器方法完成并行語言的編譯處理 ? 新語言編譯器 ? 預編譯處理 ? 并行函數(shù)與類庫 ? 并行化編譯系統(tǒng) 4. 并行算法 并行算法是指適合在各種并行計算機上求解問題的算法，它是一些可以同時執(zhí)行的進程的集合，這些進程之間相互作用，協(xié)調處理，從而實現(xiàn)對給定問題的求解 （ 1）并行算法的分類