多處理器編程的藝術(shù)

前言

　　每逢我們?cè)诙嗵幚砥髌脚_(tái)上進(jìn)行編程時(shí)，往往會(huì)有這么一種感覺(jué)：即使已熟練掌握了系統(tǒng)提供的各種同步原語(yǔ)，但所編制的并行程序的實(shí)際性能似乎總有些差強(qiáng)人意，并不十分理想。究其原因，問(wèn)題的根結(jié)在于多處理器編程應(yīng)是一門(mén)科學(xué)和藝術(shù)完美結(jié)合的學(xué)科。若要在多處理器系統(tǒng)結(jié)構(gòu)上編制出性能良好的并行程序，要求設(shè)計(jì)者不僅要精通多處理器系統(tǒng)結(jié)構(gòu)，并行算法以及一些系統(tǒng)構(gòu)建工具，還應(yīng)能基于一種設(shè)計(jì)理念，充分發(fā)揮個(gè)人的想象空間，合理搭配這些知識(shí)和資源，從而和諧地構(gòu)建完整的系統(tǒng)，使設(shè)計(jì)者能比底層硬件和操作系統(tǒng)“做得更好”。也就是說(shuō)，在編寫(xiě)多處理器程序時(shí)，要能同時(shí)從宏觀和微觀兩種角度分析問(wèn)題，并能在這兩種角度之間靈活地轉(zhuǎn)換?！　∽?0世紀(jì)中葉第一臺(tái)通用電子計(jì)算機(jī)研制成功以來(lái)，程序的編制大多是基于順序計(jì)算模型的，程序的執(zhí)行過(guò)程是操作的有序序列。由于順序計(jì)算機(jī)能夠用圖靈機(jī)精確地描述，因此順序計(jì)算的編程能在一組易于理解且完備定義的抽象之上進(jìn)行，而不需要了解底層的細(xì)節(jié)。近年來(lái)，盡管單處理器仍在發(fā)展，但由于指令級(jí)并行的開(kāi)發(fā)空間正在減少，再加上散熱等問(wèn)題限制了時(shí)鐘頻率的繼續(xù)提高，所以單處理器發(fā)展的速度正在減緩，這最終導(dǎo)致了起源于在單獨(dú)一個(gè)晶片上設(shè)計(jì)多個(gè)內(nèi)核的多處理器系統(tǒng)結(jié)構(gòu)的出現(xiàn)。多處理器系統(tǒng)結(jié)構(gòu)允許多個(gè)處理器執(zhí)行同一個(gè)程序，共享同一程序的代碼和地址空間，并利用并行技術(shù)來(lái)提高計(jì)算效率。在這種計(jì)算模型中，并發(fā)程序的執(zhí)行可以看做是多個(gè)并發(fā)線程對(duì)一組共享對(duì)象的操作序列，為了在這種異步并發(fā)環(huán)境中獲得更好的性能，底層系統(tǒng)結(jié)構(gòu)的細(xì)節(jié)需要呈現(xiàn)給設(shè)計(jì)者?！　∽鳛橐幻麅?yōu)秀的程序設(shè)計(jì)員，在編寫(xiě)多處理器程序之前首先應(yīng)弄清楚多處理器計(jì)算機(jī)的能力和限制是什么，在異步并發(fā)計(jì)算模型中什么問(wèn)題是可解決的，什么問(wèn)題是不可解決的，是什么使得某些問(wèn)題很難計(jì)算，而又使另一些問(wèn)題容易計(jì)算。這要求設(shè)計(jì)者具備一定的多核并行計(jì)算理論基礎(chǔ)知識(shí)，掌握多處理器系統(tǒng)結(jié)構(gòu)上并發(fā)計(jì)算模型的可計(jì)算性理論及復(fù)雜性理論。其次，應(yīng)掌握基本的多核平臺(tái)上的并行程序設(shè)計(jì)技術(shù)，包括并行算法、同步原語(yǔ)以及各種多核系統(tǒng)結(jié)構(gòu)。　　Maurice Herlihy教授和Nir Shavit教授在并發(fā)程序設(shè)計(jì)領(lǐng)域具有很深的造詣，并擁有40年以上一起從事并發(fā)程序設(shè)計(jì)教學(xué)的合作經(jīng)驗(yàn)。他們對(duì)多處理器并行程序設(shè)計(jì)技術(shù)做出了巨大的貢獻(xiàn)，并因此而成為2004年ACM／EATCS G6del獎(jiǎng)的共同獲得者。這本由他們合著的專著致力于解決如何采用更好的并行算法來(lái)克服多核并發(fā)程序并行度低的問(wèn)題?！　mdahl定律早已明確地告訴我們，從程序本身可獲得的并行度是有限的，加速比的提高主要取決于程序中必須增加的串行執(zhí)行部分，而這部分又往往包含著具有相對(duì)較高開(kāi)銷(xiāo)的通信和協(xié)作。因此，在多處理器系統(tǒng)結(jié)構(gòu)上，如何提高程序中必須串行部分的并行度，以及降低并行處理器中遠(yuǎn)程訪問(wèn)的時(shí)延是我們目前面臨的兩大技術(shù)挑戰(zhàn)。對(duì)這些問(wèn)題的有效解決，必須依靠軟件技術(shù)和硬件技術(shù)的改進(jìn)和發(fā)展。本書(shū)則側(cè)重于對(duì)前一個(gè)挑戰(zhàn)的研究。　　作者先從宏觀的抽象角度出發(fā)，在一個(gè)理想化的共享存儲(chǔ)器系統(tǒng)結(jié)構(gòu)中研究各種并行算法的可計(jì)算性及正確性。通過(guò)對(duì)這些經(jīng)典算法的推理分析，向讀者揭示了現(xiàn)代協(xié)作范例和并發(fā)數(shù)據(jù)結(jié)構(gòu)中所隱藏的核心思想，使讀者學(xué)會(huì)如何分析饑餓和死鎖等微妙的活性問(wèn)題，深層次地研究現(xiàn)代硬件同步原語(yǔ)所應(yīng)具有的能力及其特性。隨后，從微觀的實(shí)際角度出發(fā)，針對(duì)當(dāng)今主流的多處理器系統(tǒng)結(jié)構(gòu)，設(shè)計(jì)了一系列完美高效的并行算法及并發(fā)數(shù)據(jù)結(jié)構(gòu)，并對(duì)各種算法的效率及其機(jī)理進(jìn)行了分析。所有的設(shè)計(jì)全部采用Java程序設(shè)計(jì)語(yǔ)言詳細(xì)地描述，可以非常容易地將它們擴(kuò)展到實(shí)際應(yīng)用中?！　”緯?shū)的前6章講述了多處理器程序設(shè)計(jì)的原理部分，著重于異步并發(fā)環(huán)境中的可計(jì)算性問(wèn)題，借助于一個(gè)理想化的計(jì)算模型來(lái)闡述如何描述和證明并行程序的實(shí)際執(zhí)行行為。由于其自身的特點(diǎn)，多處理器程序的正確性要比順序執(zhí)行程序的正確性復(fù)雜得多，書(shū)中為我們展現(xiàn)了一系列不同的輔助論證工具，令人有耳目一新之感。隨后的11章闡述了多處理器程序設(shè)計(jì)的實(shí)踐部分。由于在多處理器環(huán)境中編寫(xiě)程序時(shí)，底層系統(tǒng)結(jié)構(gòu)的細(xì)節(jié)并不像編寫(xiě)順序程序那樣被完全隱藏在一種編程抽象中，因此，本書(shū)在附錄B介紹了多處理器硬件的基礎(chǔ)知識(shí)。最后的第18章介紹了當(dāng)今并發(fā)問(wèn)題研究中最先進(jìn)的事務(wù)方法，可以預(yù)言這種方法在今后的研究中將會(huì)越來(lái)越重要。

內(nèi)容概要

　　《多處理器編程的藝術(shù)》從原理和實(shí)踐兩個(gè)方面全面闡述了多處理器編程的指導(dǎo)原則，包含編制高效的多處理器程序所必備的算法技術(shù)。此外，附錄提供了采用其他程序設(shè)計(jì)語(yǔ)言包（如C#、C及C++的PThreads庫(kù)）進(jìn)行編程的相關(guān)背景知識(shí)以及硬件基礎(chǔ)知識(shí)?！抖嗵幚砥骶幊痰乃囆g(shù)》適合作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)高年級(jí)本科生及研究生的教材，同時(shí)也可作為相關(guān)技術(shù)人員的參考書(shū)?！　∧壳埃嗵幚砥鞯木幊碳夹g(shù)受到廣泛關(guān)注，多處理器編程要求理解新型計(jì)算原理、算法及編程工具；至今很少有人能夠精通這門(mén)編程藝術(shù)?！　‖F(xiàn)今，大多數(shù)工程技術(shù)人員都是通過(guò)艱辛的反復(fù)實(shí)踐、求助有經(jīng)驗(yàn)的朋友來(lái)學(xué)習(xí)多處理器編程技巧。這本最新的權(quán)威著作致力于改變這種狀況，作者全面闡述了多處理器編程的指導(dǎo)原則，介紹了編制高效的多處理器程序所必備的算法技術(shù)?！抖嗵幚砥骶幊痰乃囆g(shù)》所涵蓋的多處理器編程關(guān)鍵問(wèn)題將使在校學(xué)生以及相關(guān)技術(shù)人員受益匪淺。

作者簡(jiǎn)介

　　Maurice Herlihy，哈佛大學(xué)的數(shù)學(xué)學(xué)士和麻省理工學(xué)院的計(jì)算機(jī)科學(xué)博士，目前為美國(guó)布朗大學(xué)計(jì)算機(jī)科學(xué)系教授，曾工作于卡內(nèi)基-梅隆大學(xué)和DEC劍橋?qū)嶒?yàn)室。他是美國(guó)ACM會(huì)士，2003年分布式計(jì)算Dijkstra獎(jiǎng)獲得者。

書(shū)籍目錄

出版者的話譯者序前言第1章 引言1.1 共享對(duì)象和同步1.2 生活實(shí)例1.3 生產(chǎn)者—消費(fèi)者問(wèn)題1.4 讀者—寫(xiě)者問(wèn)題1.5 并行的困境1.6 并行程序設(shè)計(jì)1.7 本章注釋1.8 習(xí)題第一部分 原理第2章 互斥2.1 時(shí)間2.2 1臨界區(qū)2.3 雙線程解決方案2.4 過(guò)濾鎖2.5 公平性2.6 Bakery算法2.7 有界時(shí)間戳2.8 存儲(chǔ)單元數(shù)量的下界2.9 本章注釋2.10 習(xí)題第3章 并發(fā)對(duì)象3.1 并發(fā)性與正確性3.2 順序?qū)ο?.3 靜態(tài)一致性3.4 順序一致性3.5 可線性化性3.6 形式化定義3.7 演進(jìn)條件3.8 Java存儲(chǔ)器模型3.9 評(píng)析3.10 本章注釋3.11 習(xí)題第4章 共享存儲(chǔ)器基礎(chǔ)4.1 寄存器空間4.2 寄存器構(gòu)造4.3 原子快照4.4 本章注釋4.5 習(xí)題笫5章 同步原子操作的相對(duì)能力5.1 一致數(shù)5.2 原子寄存器5.3 一致性協(xié)議5.4 FIFO隊(duì)列5.5 多重賦值對(duì)象5.6 讀—改—寫(xiě)操作5.7 Common2RMW操作5.8 compareAndSet()操作5.9 本章注釋5.10 習(xí)題第6章 一致性的通用性6.1 引言6.2 通用性6.3 一種通用的無(wú)鎖構(gòu)造6.4 一種通用的無(wú)等待構(gòu)造6.5 本章注釋6.6 習(xí)題第二部分 實(shí)踐第7章 自旋鎖與爭(zhēng)用7.1 實(shí)際問(wèn)題7.2 測(cè)試—設(shè)置鎖7.3 再論基于TAS的自旋鎖7.4 指數(shù)后退7.5 隊(duì)列鎖7.6 時(shí)限隊(duì)列鎖7.7 復(fù)合鎖7.8 層次鎖7.9 由一個(gè)鎖管理所有的鎖7.10 本章注釋7.11 習(xí)題笫8章 管程和阻塞同步8.1 引言8.2 管程鎖和條件8.3 讀者—寫(xiě)者鎖8.4 我們的可重入鎖8.5 信號(hào)量8.6 本章注釋8.7 習(xí)題第9章 鏈表：鎖的作用9.1 引言9.2 基于鏈表的集合9.3 并發(fā)推理9.4 粗粒度同步9.5 細(xì)粒度同步9.6 樂(lè)觀同步9.7 惰性同步9.8 非阻塞同步9.9 討論9.1 0本章注釋9.1 1習(xí)題笫10章 并行隊(duì)列和ABA問(wèn)題10.1 引言10.2 隊(duì)列10.3 部分有界隊(duì)列10.4 完全無(wú)界隊(duì)列10.5 無(wú)鎖的無(wú)界隊(duì)列10.6 內(nèi)存回收和ABA問(wèn)題10.7 雙重?cái)?shù)據(jù)結(jié)構(gòu)10.8 本章注釋10.9 習(xí)題第11章 并發(fā)棧和消除11.1 引言11.2 無(wú)鎖的無(wú)界棧11.3 消除11.4 后退消除棧11.5 本章注釋11.6 習(xí)題第12章計(jì)數(shù)、排序和分布式協(xié)作12.1 引言12.2 共享計(jì)數(shù)12.3 軟件組合12.4 靜態(tài)一致池和計(jì)數(shù)器12.5 計(jì)數(shù)網(wǎng)12.6 衍射樹(shù)12.7 并行排序12.8 排序網(wǎng)12.9 樣本排序12.10 分布式協(xié)作12.11 本章注釋12.12 習(xí)題第13章 并發(fā)哈希和固有并行13.1 引言13.2 封閉地址哈希集13.3 無(wú)鎖哈希集13.4 開(kāi)放地址哈希集13.5 本章注釋13.6 習(xí)題第14章 跳表和平衡查找14.1 引言14.2 順序跳表14.3 基于鎖的并發(fā)跳表14.4 無(wú)鎖并發(fā)跳表14.5 并發(fā)跳表14.6 本章注釋14.7 習(xí)題第15章 優(yōu)先級(jí)隊(duì)列15.1 引言15.2 基于數(shù)組的有界優(yōu)先級(jí)隊(duì)列15.3 基于樹(shù)的有界優(yōu)先級(jí)隊(duì)列15.4 基于堆的無(wú)界優(yōu)先級(jí)隊(duì)列15.5 基于跳表的無(wú)界優(yōu)先級(jí)隊(duì)列15.6 本章注釋15.7 習(xí)題笫16章 異步執(zhí)行、調(diào)度和工作分配16.1 引言16.2 并行分析16.3 多處理器的實(shí)際調(diào)度16.4 工作分配16.5 工作竊取雙端隊(duì)列16.6 本章注釋16.7 習(xí)題第17章 障礙17.1 引言17.2 障礙實(shí)現(xiàn)17.3 語(yǔ)義換向障礙17.4 組合樹(shù)障礙17.5 靜態(tài)樹(shù)障礙17.6 終止檢測(cè)障礙17.7 本章注釋17.8 習(xí)題第18章 事務(wù)內(nèi)存18.1 引言18.2 事務(wù)和原子性18.3 軟事務(wù)內(nèi)存18.4 硬事務(wù)內(nèi)存18.5 本章注釋18.6 習(xí)題第三部分 附錄附錄A軟件基礎(chǔ)附錄B硬件基礎(chǔ)參考文獻(xiàn)

章節(jié)摘錄

　　第1章　引言　　計(jì)算機(jī)產(chǎn)業(yè)正在經(jīng)歷著一場(chǎng)重大的結(jié)構(gòu)重組和巨變，在沒(méi)有其他變革之前，這個(gè)過(guò)程無(wú)疑將會(huì)繼續(xù)進(jìn)行。主要的芯片制造商，至少是現(xiàn)在，都紛紛放棄嘗試研制速度更快的處理器。雖然摩爾定律仍舊適用：每年集成在同樣大小空間中的晶體管數(shù)越來(lái)越多，然而，由于散熱問(wèn)題難于解決，它們的時(shí)鐘速度無(wú)法繼續(xù)得到提高。取而代之的做法是，制造商開(kāi)始轉(zhuǎn)向“多核”系統(tǒng)結(jié)構(gòu)的研制，由多個(gè)處理器（多核）共享硬件高速緩存直接進(jìn)行通信。通過(guò)將多個(gè)處理器同時(shí)分配給單一任務(wù)以獲得更高的并行性，從而提高計(jì)算的效率。　　多處理器系統(tǒng)結(jié)構(gòu)的普及對(duì)計(jì)算機(jī)軟件的發(fā)展帶來(lái)了深刻的影響。直至今日以前，技術(shù)的進(jìn)步意味著時(shí)鐘速度的提升，時(shí)鐘本身的加速導(dǎo)致了軟件執(zhí)行效率的提高。今天，這種搭便車(chē)的現(xiàn)象已不復(fù)存在，技術(shù)的進(jìn)步不再指時(shí)鐘速度的提升而是指并行度的提升，并行問(wèn)題已經(jīng)成為現(xiàn)代計(jì)算機(jī)科學(xué)的主要挑戰(zhàn)。　　本書(shū)著重講述共享存儲(chǔ)器通信方式下的多處理器編程技術(shù)。通常稱這樣的系統(tǒng)為共享存儲(chǔ)器的多處理器，現(xiàn)在稱之為多核。在各種規(guī)模的多處理器系統(tǒng)中都存在著不同的編程挑戰(zhàn)——對(duì)于小規(guī)模的系統(tǒng)來(lái)說(shuō)，需要協(xié)調(diào)單個(gè)芯片內(nèi)的多個(gè)處理器對(duì)同一個(gè)共享存儲(chǔ)單元的訪問(wèn)，對(duì)于大規(guī)模系統(tǒng)來(lái)說(shuō)，需要協(xié)調(diào)一臺(tái)超級(jí)計(jì)算機(jī)中各個(gè)處理器之間的數(shù)據(jù)路由。其次，現(xiàn)代計(jì)算機(jī)系統(tǒng)所固有的異步特征也給多處理器編程帶來(lái)了挑戰(zhàn)：在沒(méi)有任何警示的情形下，系統(tǒng)的活動(dòng)可以被各種不同的事件中止或延遲，例如中斷、搶占、cache缺失和系統(tǒng)故障等。這種延遲現(xiàn)象本身是無(wú)法預(yù)測(cè)的，時(shí)延的長(zhǎng)短也是不確定的：cache缺失可以造成不到十條指令執(zhí)行時(shí)間的時(shí)延，頁(yè)故障可能造成幾百萬(wàn)條指令執(zhí)行時(shí)間的時(shí)延，而操作系統(tǒng)搶占則會(huì)導(dǎo)致多達(dá)上億條指令執(zhí)行時(shí)間的時(shí)延。

編輯推薦

　　目前，多處理器的編程技術(shù)受到廣泛關(guān)注，多處理器編程要求理解新型計(jì)算原理、算法及編程工具；至今很少有人能夠精通這門(mén)編程藝術(shù)?！　‖F(xiàn)今，大多數(shù)工程技術(shù)人員都是通過(guò)艱辛的反復(fù)實(shí)踐、求助有經(jīng)驗(yàn)的朋友來(lái)學(xué)習(xí)多處理器編程技巧。這本最新的權(quán)威著作致力于改變這種狀況，作者全面闡述了多處理器編程的指導(dǎo)原則，介紹了編制高效的多處理器程序所必備的算法技術(shù)。本書(shū)所涵蓋的多處理器編程關(guān)鍵問(wèn)題將使在校學(xué)生以及相關(guān)技術(shù)人員受益匪淺。　　本書(shū)特色　　·循序漸進(jìn)地講述共享存儲(chǔ)器多線程編程的基礎(chǔ)知識(shí)?！　　ぴ敿?xì)解釋當(dāng)今多處理器硬件對(duì)并發(fā)程序設(shè)計(jì)的支持方式?！　　と婵疾熘髁鞯牟l(fā)數(shù)據(jù)結(jié)構(gòu)及其關(guān)鍵設(shè)計(jì)要素。　　·從簡(jiǎn)單的鎖機(jī)制到最新的事務(wù)內(nèi)存系統(tǒng)，獨(dú)立、完整地闡述了同步技術(shù)?！　　だ肑ava并發(fā)工具包編寫(xiě)的可完全執(zhí)行的Java實(shí)例?！　　じ戒浱峁┝瞬捎闷渌绦蛟O(shè)計(jì)語(yǔ)言和包（如C#、C及C++的PThreads庫(kù)）進(jìn)行編程的相關(guān)背景知識(shí)以及硬件基礎(chǔ)知識(shí)。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    多處理器編程的藝術(shù) PDF格式下載

---