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