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