【正文】 ........................................................................................................ 22 常見的兩 種分支限界法 .................................................................................... 22 分支限界法的設(shè)計(jì)思路 .................................................................................... 22 旅行商問題分支限界法的程序?qū)崿F(xiàn) ................................................................ 22 程序的運(yùn)行和正確性 .................................................................................................. 26 程序的運(yùn)行 ....................................................................................................... 26 程序的正確性 ................................................................................................... 30 測(cè)試、記錄、分析與結(jié)論 .......................................................................................... 30 測(cè)試、記錄與分析 ........................................................................................... 30 結(jié)論 ................................................................................................................... 34 目錄 III 小結(jié) .............................................................................................................................. 34 第 6 章 結(jié)語 ............................................................................................................................... 35 總結(jié) .............................................................................................................................. 35 展望 .............................................................................................................................. 35 致謝 ............................................................................................................................................. 37 參考文獻(xiàn) ..................................................................................................................................... 38 目錄 IV 第 1 章 緒論 1 第 1 章 緒論 隨著現(xiàn)代計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展和進(jìn)步，人們對(duì)于高性能計(jì)算機(jī)的需求越來越強(qiáng)烈，但在物理?xiàng)l件和現(xiàn)有的計(jì)算機(jī)體系結(jié)構(gòu)下，單純的通過提高處理器計(jì)算能力的方法已到達(dá)了極限。 并行計(jì)算是指同時(shí)利用多種計(jì)算資源來解決計(jì)算問題的方法，是提高計(jì)算機(jī)計(jì)算速度和處理能力的一種十分有效手段。并行計(jì)算系統(tǒng)可以指專門設(shè)計(jì)的、含有多個(gè)處理器的超級(jí)計(jì)算機(jī)，也可以是以某種方式互連的若干臺(tái)的獨(dú)立計(jì)算機(jī)構(gòu)成的集群。 .NET Remoting 技術(shù)是 .NET Framework 提供的 一種優(yōu)秀的分布式應(yīng)用開發(fā)技術(shù)，具有高效、可擴(kuò)展、易于配置、支持多事務(wù)、可與其它分布式應(yīng)用技術(shù)協(xié)作、能在 Inter上運(yùn)行等特點(diǎn)。 隨著人類科學(xué)技術(shù)的 不斷進(jìn)步，有很多大型的、復(fù)雜的問題需要人們?nèi)ソ鉀Q。在現(xiàn)代計(jì)算機(jī)的體系結(jié)構(gòu)和物理?xiàng)l件下，解決這些問題需要非常長(zhǎng)的計(jì)算時(shí)間，計(jì)算效率非常低下，這樣很不合理。大型復(fù)雜的問題的處理就變得很高效和低成本了。為此， Windows 平臺(tái)下的 .NET Framework Remoting 技術(shù)為并行計(jì)算程序的編寫提供了簡(jiǎn)單、靈活編程手段，大大降低了編程難 度。 國(guó)內(nèi)外研究現(xiàn)狀 并行計(jì)算 并行計(jì)算是指同時(shí)利用多種計(jì)算資源來解決計(jì)算問題的方法，是提高計(jì)算機(jī)計(jì)算速度和處理能力的一種十分有效手段。 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 2 現(xiàn)在，并行計(jì)算算法的設(shè)計(jì)一般以 MIMD 類為主流，并且需要有可移植性和可擴(kuò)展性。只有兼顧了這兩個(gè)方面，才能真正發(fā)揮微處理器和互聯(lián)網(wǎng)絡(luò)所構(gòu)成的并行計(jì)算系統(tǒng)的潛在性能。 并行計(jì)算是相對(duì)于串行計(jì)算來說的，所謂并行計(jì)算分為時(shí)間上的并行和 空間上的并行。 空間上的并行導(dǎo)致了兩類并行機(jī)的產(chǎn)生，按照 Flynn 的說法分為：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流（ SIMD）和多指令流多數(shù)據(jù)流（ MIMD）。MIMD 類的機(jī)器又可分為以下常見的五類：并行向量處理機(jī)（ PVP）、對(duì)稱多處理機(jī)（ SMP）、大規(guī)模并行處理機(jī)（ MPP）、工作站機(jī)群（ COW）、分布式共享存儲(chǔ)處理機(jī)（ DSM）。從微軟的產(chǎn)品角度來看，可以說 Remoting就是 DCOM的一種升級(jí)，它改善了很多功能，并極好的融合到 .Net 平臺(tái)下。在 Remoting 中是通過通道（ channel）來實(shí)現(xiàn)兩個(gè)應(yīng)用程序域之間對(duì)象的通信的。這就提供一種可能性，即以服務(wù)的方式來發(fā)布服務(wù)器對(duì)象。 在 Remoting 中，對(duì)于要傳遞的對(duì)象，設(shè)計(jì)者除了需要了解通道的類型和端口號(hào)之外，無需再了解數(shù)據(jù)包的格式。 開發(fā)工具及技術(shù) VS20xx Visual Studio 是微軟公司推出的開發(fā)環(huán)境。 Visual Studio 20xx 集成開發(fā)環(huán)境（ IDE）的界面被重新設(shè)計(jì)和組織 ，變得更加簡(jiǎn)單明了。除了 Microsoft SQL Server，它還支持 IBM DB2 和 Oracle 數(shù)據(jù)庫(kù)。 除了上述功能外還在以下方面進(jìn)行了改進(jìn)：增強(qiáng)和完善了 Visual Studio IDE。同時(shí)還包括一種新的 .NET Framework 語言： F。改進(jìn)了對(duì) WPF和 Silverlight應(yīng)用程序的開發(fā) 。 Visual Studio 20xx 能成為新一代的經(jīng)典開發(fā)工具的特點(diǎn)有如下幾個(gè)： （ 1）未來代碼管理工具比平臺(tái)更重要； （ 2）靈活高效的全新 IDE； （ 3）助力 Azure 平臺(tái)，強(qiáng)化云計(jì)算能力； （ 4) 提升并行計(jì)算，應(yīng)對(duì)多核趨勢(shì)； （ 5）快速開發(fā)，跨越開發(fā)周期協(xié)作； MySql MySQL 是一個(gè) 關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng) ，由瑞典 MySQL AB公司開發(fā)，目前屬于 Oracle公司。 MySql 的系統(tǒng)特性有：（ 1)支持 多線程 ，充分利用 CPU 資源；（ 2)優(yōu)化的 SQL 查詢算法，有效地提高查詢速度；（ 3)既能夠作為一個(gè)單獨(dú)的 應(yīng)用程序 應(yīng)用在 客戶端服務(wù)器 網(wǎng)絡(luò)環(huán)境中，也能夠作為一個(gè)庫(kù)而嵌入到其他的軟件中；（ 4)提供多語言支持，常見的 編碼 如中文的 GB 231 BIG5，日文的 Shift_JIS等都可以用作數(shù)據(jù)表名和數(shù)據(jù)列名；（（ 5)提供 TCP/IP、ODBC 和 JDBC 等多種 數(shù)據(jù)庫(kù) 連接途徑；（ 6)提供用于管理、檢查、優(yōu)化數(shù)據(jù)庫(kù)操作的 管理工具 ；（ 7)支持大型的 數(shù)據(jù)庫(kù) 。 小結(jié) 本章 對(duì) . Remoting技術(shù)的背景原因及它的意義 進(jìn)行了介紹 ，闡述了 . Remoting技術(shù)在國(guó)內(nèi)外的發(fā)展現(xiàn)狀。 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 4 第 2 章 并行計(jì)算 5 第 2 章 并行計(jì)算 并行計(jì)算是伴隨并行機(jī)的出現(xiàn)，在近 30年來發(fā)展較迅速的一門交叉學(xué)科，涵蓋的內(nèi)容非常廣泛?？煞譃闀r(shí)間上的并行和空間上的并行。 它的基本思想是用多個(gè)處理器來協(xié)同求解同一問題，即將被求解的問題分解成若 干個(gè)部分，各部分均由一個(gè)獨(dú)立的處理機(jī)來并行計(jì)算。通過并行計(jì)算集群完成數(shù)據(jù)的處理，再將處理的結(jié)果返回給用戶。 并行計(jì)算是相對(duì)于串行計(jì)算來說的，所謂并行計(jì)算分為時(shí)間上的并行和空間上的并行。 2. 基本體系結(jié)構(gòu) 并行計(jì)算科學(xué)中主要研究的是空間上的并行問題。一般來說，因?yàn)閿?shù)據(jù)并行主要是將一個(gè)大任務(wù)化解成相同的各個(gè)子任務(wù)，比 任務(wù)并行 要容易處理。我們常用的串行機(jī)也叫做單指令流單 數(shù)據(jù)流 （ SISD）。 并行計(jì)算的主要研究目標(biāo)和研究?jī)?nèi)容 并行計(jì)算的主要研究目標(biāo) 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 6 對(duì)于具體的應(yīng)用問題，采用并行計(jì)算技術(shù)的主要目的在于以下 2 個(gè)方面： （ 1）加快求解問題的速度，縮短求解問題所需的時(shí)間。 并行計(jì)算之所以必需，主要在于，當(dāng)前的單處理器性能不可能滿足大規(guī)模科學(xué)與工程計(jì)算及商業(yè)應(yīng)用的需求，并行計(jì)算是目前唯一能滿足實(shí)際大規(guī)模計(jì)算需求的支撐技術(shù)。近兩年內(nèi) ，微處理器的峰值性能也不會(huì)超過 100 億次 /秒。 綜上所述，并行計(jì)算的主要目標(biāo)在于在并行機(jī)上，解決一批具有重大挑戰(zhàn)性計(jì)算任務(wù)的科學(xué)、工程及商業(yè)計(jì)算問題，滿足不斷增長(zhǎng)的應(yīng)用問題對(duì)速度和內(nèi)存資源的需求。 （ 2）并行算法設(shè)計(jì)與分析。 （ 4）并行應(yīng)用。需要說明的是，并行計(jì)算不同于分布式計(jì)算。但是，它無法達(dá)到并行計(jì)算所倡導(dǎo)的提高求解同一個(gè)應(yīng)用的速度，或者提高求解同一個(gè)應(yīng)用的問題規(guī)模的目的 。并行算法作為應(yīng)用程序開發(fā)的基礎(chǔ)，在并行計(jì)算機(jī)應(yīng)用中具有舉 足輕重的地位。 根據(jù)并行進(jìn)程間相互執(zhí)行順序關(guān)系的不同可分為： （ 1）同步并行算法，進(jìn)程間由于運(yùn)算執(zhí)行順序而必須相互等待的并行算法； （ 2）異步并行算法，進(jìn)程間執(zhí)行相對(duì)獨(dú)立，不需要相互等待的一種算法； （ 3）獨(dú)立并行算法，進(jìn)程間執(zhí)行是完全獨(dú)立的，計(jì)算的整個(gè)過程不需要任何通信。 在這里，我使用的并行算法也是當(dāng)前并行算法的主流算法，也就是大粒度并行算法。在這種計(jì)算方式下，其最大的特點(diǎn)就是在網(wǎng)絡(luò)中傳輸數(shù)據(jù)。如圖 21 所示： 圖 21 多臺(tái)計(jì)算機(jī)并行計(jì)算連機(jī)交互示意 圖 在網(wǎng)絡(luò)中傳輸數(shù)據(jù)，原本有很多復(fù)雜的步驟，對(duì)編程者有著很高的要求，但是微軟的 .NET Remoting 技術(shù)，將消息的傳遞機(jī)制都封裝的很好，大大降低了編程者對(duì) Remoting編程的難度。 在多計(jì)算機(jī)的分布式并行計(jì)算中，一般一臺(tái)計(jì)算機(jī)含有一個(gè) CPU，當(dāng)然也可以含有多個(gè) CPU，日常生活中多 CPU 的計(jì)算機(jī)并不常見。 單計(jì)算機(jī)的并行計(jì)算 計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)論文 8 單計(jì)算機(jī)的并行計(jì)算，一般指同一臺(tái)機(jī)器上的多線程并行計(jì)算。 由于多線程并行計(jì)算仍是處于同一個(gè)操作系統(tǒng)中的，所以線程之間的協(xié)調(diào)有更加靈活的控制機(jī)制：可以使用系統(tǒng)內(nèi)部的消息傳遞機(jī)制，也可以使用全局變量作為標(biāo)記來識(shí)別，還可以通過自定義事件來響應(yīng)各個(gè)線程的運(yùn) 行。 要注意的是，當(dāng)一個(gè)線程完成計(jì)算任務(wù)之后，并不會(huì)自動(dòng)釋放該實(shí)例，需要在程序中調(diào)用方法釋放內(nèi)存。多個(gè) CPU 分別處理大型復(fù)雜任務(wù)的一個(gè)或幾個(gè)子任務(wù)，最后將結(jié)果匯總得出答案。但是這對(duì)計(jì)算機(jī)的硬件要求比較苛刻。 多核 CPU 比單核 CPU 的計(jì)算速度快，原因是單核 CPU 只能利用僅有的一個(gè)核處理一個(gè)指令，而多核 CPU 可以利用 CPU 內(nèi)部多個(gè)核同時(shí)處理一條指令，從而加快計(jì)算機(jī)的運(yùn)算速度。 單 CPU 多 核的計(jì)算機(jī)，也可以啟用多個(gè)線程進(jìn)行并行計(jì)算，但是這種計(jì)算是有瓶頸的。當(dāng)處理的任務(wù)非常大時(shí)，單 CPU 就無法再通過增加線程數(shù)量來提高計(jì)算效率了。 小結(jié) 這一章先講了并行計(jì)算的概念，接著講了并行計(jì)算的研究目標(biāo)和研究?jī)?nèi)容，按照不同的對(duì)象將并行算法進(jìn)行分類，最后對(duì)分布式并行計(jì)算的幾種方式進(jìn)行了分析，在這里我主要研究的 就是多計(jì)算機(jī)的并行計(jì)算問題。 第 3 章 .NET Remoting 技術(shù) 9 第 3 章 .NET Remoting 技術(shù) .NET Remoting 技術(shù)的簡(jiǎn)介 .NET Remoting 是微軟隨 .NET 推出的一種分布式應(yīng)用解決方案，被譽(yù)為管理應(yīng)用程序域之間的 RP