并行方向文獻(xiàn)綜述

1、遼寧師范大學(xué)本科生畢業(yè)論文(設(shè)計(jì))文獻(xiàn)綜述表格填寫說(shuō)明論文題目整數(shù)線性規(guī)劃匈牙利法多核并行算法研究綜述完成時(shí)間年 月曰學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)(師范)學(xué)生蘇元賀學(xué)號(hào) 20081807010105指導(dǎo)教師鄭曉薇職稱教授查 閱 的 主 要 文 獻(xiàn)多核系列教材編寫組.多核程序設(shè)計(jì).清華大學(xué)出版社，2007.9周偉明，多核計(jì)算與程序設(shè)計(jì)M.武漢.華中科技大學(xué)出版社,2008.陳國(guó)良，安虹，陳凌等.并行算法實(shí)踐.北京：高等教育出版社，2004 年奎因著，陳文光，武永衛(wèi)等譯.MPI與OpenMP并行程序設(shè)計(jì)：C語(yǔ)言版.清華大學(xué)出版社，2004.10于秀林.多元統(tǒng)計(jì)分析.北京：中國(guó)統(tǒng)計(jì)出

2、版社，1999林齊寧.決策分析.北京：北京郵電大學(xué)出版社，2003楊麗英，吳成東等.多目標(biāo)追逐問(wèn)題的一種混合整數(shù)線性規(guī)劃解.機(jī)械工 程學(xué)報(bào)，2008.10張?zhí)禚Q.整數(shù)線性規(guī)劃問(wèn)題解法探究.湖州職業(yè)技術(shù)學(xué)院學(xué)報(bào)， 2005, 4文獻(xiàn)綜述1介紹1.1并行計(jì)算：并行計(jì)算(parallel computing) 是指，在并行機(jī)上，將個(gè)應(yīng)用分解成多個(gè)子任務(wù)， 分配給不同的處理器，各個(gè)處理器之間相互協(xié)同，并行地執(zhí)行子任務(wù)，從而達(dá)到加速求 解速度，或者求解應(yīng)用問(wèn)題規(guī)模的目的。由此，為了成功開(kāi)展并行計(jì)算，必須具備三個(gè)基本條件：并行機(jī)。并行機(jī)至少包含兩臺(tái)或多處理機(jī)，這些處理機(jī)通過(guò)互連網(wǎng)絡(luò)相互連接，互 通信。應(yīng)用

3、問(wèn)題必須具有并行度。也就是說(shuō)，應(yīng)用可以分解為多個(gè)子任務(wù)，這些子任務(wù)可 以并行地執(zhí)行。將一個(gè)應(yīng)用分解為多個(gè)子任務(wù)的過(guò)程，稱為并行算法的設(shè)計(jì)。并行編程。在并行機(jī)提供的并行編程環(huán)境上，具體實(shí)現(xiàn)并行算法，編制并行程序， 并運(yùn)行該程序，從而達(dá)到并行求解應(yīng)用問(wèn)題的目的。1.2什么是整數(shù)線性規(guī)劃：1)整數(shù)規(guī)劃(Integer Programming):要求全部或部分決策變量的取值為整數(shù)的規(guī)劃問(wèn) 題。整數(shù)線性規(guī)劃(Integer Linear Programming ILP):要求全部或部分決策變量的取 值為整數(shù)的線性規(guī)劃問(wèn)題。全(純)整數(shù)規(guī)劃：全部決策變量的取值都為整數(shù)?；旌险麛?shù)規(guī)劃則僅要求部分決策變量的取

4、值為整數(shù)。0-1整數(shù)規(guī)劃:要求決策變量只取0或1值。-1 -例題：設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為X1和x2。顯然，x1、x2都要求為整數(shù)，于是可建立整數(shù)規(guī)劃模型如下： TOC o 1-5 h z max z = 20 x1+10 x2(1)5x1+4x2W24(2)2x1+5x2W13(3)x1, x230(4)x1, x2為整數(shù)(5)1.3整數(shù)線性規(guī)劃的匈牙利算法根據(jù)題干的到效率矩陣步驟一：產(chǎn)生每行的零元素。方法：從每行中找出最小的元素，與對(duì)應(yīng)的每行元素相減步驟二：產(chǎn)生位于每列的零元素方法：再找出矩陣每列的最小元素，再分別從各列中減去。步驟三：判斷零元素是否位于不同行、不同列。方法：首先從行

5、開(kāi)始試指派，只有一個(gè)零元素時(shí)，對(duì)零元素打括號(hào)，并對(duì)所在列畫直 線。而有多個(gè)零元素，或零元素已被畫去，則轉(zhuǎn)下一行；行分析完畢后，然后從列開(kāi)始 試指派，對(duì)每列只有一個(gè)零元素時(shí)，打括號(hào)，并畫去其所在的行。步驟四：繼續(xù)創(chuàng)造零元素。方法：從未被畫去的元素中，找到一個(gè)最小的元素虹對(duì)行的操作：選擇行位勢(shì)ui，如果行被直線覆蓋，則ui=0；如果未被覆蓋，ui=k；列的操作：列位勢(shì)vj，如果列被直線覆蓋，vj=-k；如果未被覆蓋，vj=0。產(chǎn)生新的效率矩陣：bij= aij -ui-vj步驟五：繼續(xù)判斷零元素是否位于不同行、不同列。方法：首先從行開(kāi)始試指派，只有一個(gè)零元素時(shí)，對(duì)零元素打括號(hào)，并對(duì)所在列畫直 線。

6、而有多個(gè)零元素，或零元素已被畫去，則轉(zhuǎn)下一行；行分析完畢后，然后從列開(kāi)始 試指派，對(duì)每列只有一個(gè)零元素時(shí)，打括號(hào)，并畫去其所在的行。步驟六：獲得最后結(jié)果。方法：對(duì)于打括號(hào)的零元素處進(jìn)行指派，即可獲得最短時(shí)間。并行程序設(shè)計(jì)的不足及原因由上述的并行程序設(shè)計(jì)方法中可以得知，設(shè)計(jì)一種新語(yǔ)言雖然有比較強(qiáng)的并行性描 述能力，但是兼容性不好，不易推廣，因此現(xiàn)在采用該方法的系統(tǒng)較少。對(duì)現(xiàn)有的順序 語(yǔ)言加以擴(kuò)展，提供并行性描述機(jī)制，該方法具有兼容性好、編程簡(jiǎn)便等特點(diǎn)，現(xiàn)在常 常被采用。不改變現(xiàn)有順序語(yǔ)言，而由用戶提供的函數(shù)庫(kù)、類庫(kù)或并行化編譯系統(tǒng)等方 法實(shí)現(xiàn)并行程序設(shè)計(jì)。該方法簡(jiǎn)單靈活，易于推廣。2.1現(xiàn)狀：并

7、行軟件的發(fā)展落后于并行硬件；和串行系統(tǒng)的應(yīng)用軟件相比，現(xiàn)今的并行系統(tǒng)應(yīng)用軟件甚少且不成熟；并行軟件的缺乏是發(fā)展并行計(jì)算的主要障礙；而且這種狀態(tài)仍在繼續(xù)。2.2原因是并行程序設(shè)計(jì)不但包含了串行程序設(shè)計(jì)，而且還包含了更多的富有挑戰(zhàn)性的問(wèn)題。串行程序設(shè)計(jì)僅有一個(gè)普遍被接受的馮*諾依曼模型，而并行計(jì)算模型雖有好多，但 沒(méi)有一個(gè)被共同認(rèn)可。并行程序設(shè)計(jì)對(duì)環(huán)境工具的要求遠(yuǎn)比串行程序設(shè)計(jì)先進(jìn)得多。串行程序設(shè)計(jì)比較適合于自然習(xí)慣，且人們?cè)谶^(guò)去積累了大量的編程知識(shí)和寶貴的 軟件財(cái)富。至今并行算法范例不能被很好地理解和廣泛地接受；并行程序設(shè)計(jì)是建立在 不同的計(jì)算模型上的，而它們沒(méi)有能像馮.諾依曼模型那樣被普遍接受和認(rèn)可。發(fā)展趨勢(shì)及應(yīng)用前景隨著時(shí)代的進(jìn)步，我們需要不斷調(diào)整研究方向。目前并行算法研究的新走向是：并 行算法研究?jī)?nèi)容不斷拓寬，并行計(jì)算被納入研究范疇；與廣大用戶領(lǐng)域結(jié)合，注重應(yīng)用， 強(qiáng)調(diào)走到用戶中去，為用戶解決問(wèn)題；重視新的、非常規(guī)計(jì)算模式，如神經(jīng)計(jì)算、量子 計(jì)算等，這些模式能夠解決某類特定問(wèn)題，有其自身的優(yōu)越性。目前并行編程類型逐漸匯聚于兩類:用于PVP，SMP和DSW的共享變量的單地址空間 模型和用于MPP和機(jī)群的消息傳遞的多地址空間模型。并行編程模型逐漸匯聚于三類標(biāo) 準(zhǔn)模型:數(shù)據(jù)并