臺灣博碩士論文加值系統

　　在我們的系列研究中，我們著重於為了改進二維度網狀連結網路支援單程式多資料計算的通訊路由效能，而發展出一種新的多步驟、非最短路徑之適應性即時路由方法。在此論文研究中，我們進一步研究了對此路由方法的效能模擬器設計與效能模擬實驗及評估的規劃，此模擬器設計包含以下各路由功能的模擬設計：
　　˙ 漸進式緩衝區佔用容量控制之模擬
　　˙ 動態優先權計算之模擬
　　˙ 直接輸出路由方法之模擬
　　˙ 主動性的重新路由方法之模擬
　　˙ 被動性的重新路由方法之模擬
　　˙ 優先權的重新計算與排列之模擬　
　　對於此系統模擬，我們採用了具有硬體描述行為和一般相容性的程式語言來規劃。目前我們已經完成此效能模擬器的設計，並規劃實驗方法，未來將進行一系列應用於二維度網狀連結網路的通訊路由實驗，並做最後的整體效能評估。以其證實我們的系列研究不僅能改進單程式多資料分散式計算的執行效率，更能符合一般即時通訊系統的傳輸要求。

　　In our previous research, we design a new routing method, called the multi-phase, non-minimal adaptive real-time routing method, which can improve routing performance of packet communication to enhance the execution speed of SPMD computation in two-dimensional mesh. In this thesis research, we designed the performance simulator and planed an experiment of the routing method. The performance simulator design task consists of the following items :
　　˙ the simulation design of gradual buffer size control
　　˙ the simulation design of dynamic priority calculation
　　˙ the simulation design of bypass routing
　　˙ the simulation design of active re-routing
　　˙ the simulation design of passive re-routing
　　˙ the simulation design of priority re-calculation and re-scheduling
　　We programmed the performance simulator in a simulation programming language. Currently, we complete the design of the performance simulator and the planning of the experiment. In the future, we will carry out the experiment and evaluate the performance to verify that the routing method can improve the speed of SPMD distributed computation and match the need of real-time communication.

第一章 導論
1-1. 研究動機
1-2. 研究背景
1-3. 研究目的
1-4. 論文組織
第二章 網狀網路即時路由方法與路由器
2-1. 路由方法流程與路由器架構介紹
2-2. 管線化、可搶先的傳輸模式
2-3. 漸進式緩衝區佔用容量控制
2-4. 動態優先權調整
2-5. 多步驟、非最短路徑之適應性路由方法
2-5-1. 直接輸出路由
2-5-2. 優先權佇列的插入
2-5-3. 主動性的重新路由
2-5-4. 被動性的重新路由
2-5-5. 優先權重新計算
2-5-6. 路由執行時間的分配
2-5-7. 路由演算法
2-6. 直接輸出路由實作設計
2-7. 優先權佇列實作設計
第三章 網狀連結網路通訊模式時間分析
3-1. 網狀連結網路架構
3-2. 單程式多資料之計算分配
3-3. 單程式多資料之通訊距離分析與即時通訊時間需求分析
第四章 效能模擬器的設計
4-1. 模擬語言簡介
4-2. 管線化、可搶先的傳輸模式的模擬設計
4-3. 緩衝區容量控制的模擬設計
4-4. 模擬器系統設計
4-5. 模擬模組的演算法
4-5-1. 行為SEND演算法
4-5-2. 行為RECEIVE演算法
4-5-3. 行為PROCESSOR演算法
4-5-4. 行為ROUTING演算法
4-5-5. 行為NODE演算法
4-5-6. 行為MESH演算法
第五章 實驗規劃
5-1. 即時通訊系統的實驗規劃
5-2. 單程式多資料分散式計算的實驗規劃
第六章 結論
參考文獻

[1] T. Lee, A Mesh Routing Method for SPMD Communication, Tech. Rep. No 99-06-02, CAD Lab., Dept. of Electrical Engineering, Univ. of National Sun Yat-Sen, June, 1999
[2] D. Sima, et al., Advanced Computer Architecture, Addison-Wesley, 1997
[3] K. Hwang, Advanced Computer Architecture, McGraw-Hill, 1993
[4] P. Patterson and J. Hennessy, Computer Architecture: A Quantitative Approach, Morgan Kaufman Publishers, 1993
[5] F. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufman Publishers, 1992
[6] G. Almasi and A. Gottlieb, Highly Parallel Computing, Benjamin/Cummings Publishing Co., 1989
[7] J. Duato and P. Lopez, "Performance Evaluation of Adaptive Routing Algorithms for k-ary n-Cubes," in the Proc. of the 1st Int'l Workshop on Parallel Computer Routing and Communication, pp. 45-59, May 1994
[8] H.L. Chen, and C.T. King, "Efficient Dynamic Processor Allocation for k-ary n-Cube Massively Parallel Processors," in Computers Mth. Applic., Vol. 33, No. 8, pp. 59-73, 1997
[9] S. Heller, "Congestion-Free Routing on the CM-5 Data Router," in the Proc. of the 1st Int'l Workshop on Parallel Computer Routing and Communication, pp. 174-182, May 1994
[10] Chlamtac, et al., "An HIPPI Interconnection System," in IEEE Trans. on Computers, Vol. 42, No. 2, pp. 138-149, Feb. 1993
[11] S.L. Chang, et al., "Enhanced PVM Communications over a High-Speed LAN," in IEEE Parallel and Distributed Technology, Vol. 3, No. 3, 1995
[12] J. Hsieh, et al., "HIPPI over ATM Networks: Extending Connections for Distributed Compuing," in IEEE Concurrency, Vol. 5, No. 4, 1997
[13] S. Johnson and S. Scott, "A Supercomputer System Interconnect and Scalable IOS," in the Proc. of the 14th IEEE Symp. on Mass Storage Systems, 1995
[14] Plaat, et al., "Sensitivity of Parallel Applications to Large Differences in Bandwidth and Latency in Two-Layer Interconnects," in the Proc. of the 5th Int'l Symposium on High Performance Computer Architecture, 1999
[15] R. Hoare and H. Dietz, "A Case for Aggregate Networks," in the Proc. of the 12th Int'l Parallel Processing Symposium, 1998
[16] Q.P. Gu and J. Gu, "Two Packet Routing Algorithms on a Mesh-Connected Computer," in IEEE Trans. on Parallel and Distributed Systems, Vol. 6, No. 4, pp. 436-440, Apr. 1995
[17] D. Chinn, et al., "Minimal Adaptive Routing on the Mesh with Bounded Queue Size," in Journal of Parallel and Distributed Computing, Vol. 34, pp. 154-170, 1996
[18] D. Cotter and M.C. Tatham, "Dead Reckoning - A Primitive and Efficient Self-Routing Protocol for Ultrafast Mesh Networks," in IEE Proc. Communication, Vol. 144, No. 3, pp. 135-141, June 1997
[19] D. Makedon and A. Symvonis, "An Efficient Heuristic for Permutation Packet Routing on Meshes with Low Buffer Requirements," in IEEE Trans. on Parallel and Distributed Systems, Vol 4., No.3, Mar. 1993, pp. 270-276
[20] Y.J. Suh and S. Yalamanchili, "All-To-All Communication with Minimum Start-Up Costs in 2D/3D Tori and Meshes," in IEEE Trans. on Parallel and Distributed Systems, Vol. 9, No. 5, pp. 442-458, May 1998
[21] D. Chinn, "The Performance of Adaptive Routers on Worst Case Permutations," in IEEE Trans. on Parallel and Distributed Systems, Vol. 9, No. 5, pp. 60-71, May 1998
[22] T.D. Nguyen and L. Snyder, "Performance Analysis of A Minimal Adaptive Router," Dept. of Computer Science and Engineering, Univ. of Washington, Seattle, WA 98195
[23] G.L. Frazier, "Buffering and Flow Control in Communication Switches for Scalable Multicomputer," Ph.D. Dissertation, Univ. of California
[24] D. Chinn, Packet Routing in Multiprocessor Networks, Ph.D. Dissertation, Univ. of Washington, 1995
[25] W.C. Feng and K. Shin, "Impact of Selection Functions on Routing Algorithm Performance in Multicomputer Networks", Dept. of EECS, Univ. of Michigan, 1995
[26] Y. Yang and J. Wang, "Efficient All-To-All Broadcast in All-Port Mesh and Torus Networks," in the Proc. of the 5th Int'l Symposium on High Performance Computer Architecture, 1999
[27] P. Panaite, "Routing Permutations on a 2D Grid with One-Way Edges," in Parallel Processing Letters, Vol. 7, No.3, pp. 225-235, 1997
[28] W. Ligon III and U. Ramachandran, "Toward a More Realistic Performance Evaluation of Interconnection Networks," in IEEE Trans. on Parallel and Distributed Systems, Vol. 8, No. 7, pp. 681-694, July 1997
[29] M. Herbordt, The Evaluation of Massively Parallel Array Architectures, Ph.D. Dissertation, Dept. of Computer Science, Univ. Of Massachusetts, Amherst, 1994
[30] J Zhu, et al. Syntax and Semantics of the SpecC Language, Dept. of Information and Computer Science, Univ. of California, Irvine, CA 92697-3425, USA