臺灣博碩士論文加值系統

這份論文敘述以平行化事件模擬來完成蟲洞路由. 這個模擬是以Pthread及MPI函式庫來完成並以平行化執行. 同時討論以平行及分散式來執行事件模擬.

This dissertation describes a parallel implementation of a discrete event simulation for the wormhole routine. The simulation is implemented in both Posix threads and MPI message passing library and executed in parallel. The implementation uses conservative logical process simulation, which applies conservative time windows and carrier null-massage protocol to guarantee the correctness of the simulation. We also develop techniques for improving the the parallel execution efficiency for wormhole routing. We also discuss the issue of parallel and distributed execution of discrete event simulation and
their impacts on the code designs. Performance data on a dual CPU personal computer are also presented.

1 Introduction . . . . . . . . . . . . . . . . . . . . . .5
2 Discrete Event Simulation . . . . . . . . . . . . . . . .7
2.1 The Simulation Model . . . . . . . . . . . . . . . . . 7
2.1.1 Discrete and Continuous Domains .. . . . . . . . . . 7
2.1.2 Event Driven and Time Driven . . .. . . . . . . . . . 8
2.1.3 A Formal Model . . . . . . . . . .. . . . . . . . . . 9
2.2 Parallel Discrete Event Simulation . . . . . . . . . . 9
3 Wormhole Routing . . . . . . . . . . . . . . . . . . . .12
3.1 Wormhole Routining Simulations . . . . . . . . . . . . 13
4 Implementation Details . . . . . . . . . . . . . . . . .16
4.0.1 Pthread library . . . . . .. . . . . . . . . . . . . 16
4.0.2 MPI library . . . . . . . . . . . . . . . . . . . . 18
4.1 Implementation Issues . . . . . . . . . . . . . . . . 19
4.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . 19
4.1.2 Issues . . . . . . . . . . . . . . . . . . . . . . . 21
4.1.3 Input/Output Buers . . . . . . . . . . . . . . . . 24
4.1.4 Expected Arrival Time . . . . . . . . . . .. . . . . 25
4.1.5 Parallel Simulation Acceleration . . . . . . . . . . 28
5 Experimental Result . . . . . . . . . . . . . . . . . .31
5.1 Experimental Environment . . . . . . . . . . . . . . . 31
5.2 Experimental Method . . . . . . . . . . . .. . . . . . 31
5.3 Experimental Results . . . . . . . . . . . . . . . . . 32
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . .35

[1] D. Baik and B. P. Zeigler. Performance evaluation of hierarchical dis-tributed simulators. In Proc. of the 1985 Winter Simulation Conference, pages 421{427. SCS, 1985.
[2] L. M. Sokol D. P. Briscoe and A. P. Wieland. Mtw: a strategy for scheduling discrete simulation events for concurrent execution. In Proc. of the SCS Multiconf. on Distributed Simulation, pages 34{42, 1988.
[3] R. E. Bryant. A switch-level model and simulator for mos digital sys-tems. IEEE Transactions on Computer, C-33:160{177, Feb 1984. 2.
[4] K.M Chandy and J. Misra. Distributed simulation : A case study in design and verication of distributed programs. IEEE Trancations on Software Engineering, SE-5:440{452, Sep 1979. 5.
[5] Alois Ferscha and Satish K. Tripathi. Parallel and distributed simulation of discrete event systems.
[6] E Fleury and Fraigniaud. A general theory for deadlock avoidance in wormhole-routed networks. Parallel and Distributed System, IEEE Transactions, 1998.
[7] R. M. Fujimoto. Parallel discrete event simulation. In Communications of the ACM, volume 33, pages 30{53, October 1990. 10.
[8] Greenberg R. I. and Hyeong cheol Oh. Universal wormhole routing. Parallel and Distributed System, IEEE Transactions, 1997.
[9] D. A. Jeerson. Virtual time. ACM Transaction on Programming Lan- guages and Systems, 7:404{425, July 1985. 3.
37
[10] L. Lamport. Time, clocks, and the ordering of events in distributed systems. Communications of the ACM, 21:558{565, Jul 1978. 7.
[11] Yi-Bing Lin and Paul A. Fishwick. Asynchronous parallel discrete event simulation. IEEE Transactions On System, Man and Cybernetics, 1995.
[12] K. Venkatesh T. Radhakrishnan and H. F. Li. Discrete event simulaiton in a distributed system. IEEE COMPSAC, pages 123{129, 1986.
[13] Rhonda Righter and Jean C. Walrand. Distributed simulation of discrete event system. Proceedings Of The IEEE, 77, 1989.
[14] Lixin Tao. An on-line simulator for wormhole routing networks. Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 1998.
[15] B. D. Lubachevsky. In: B. Unger and D. Jeerson. Bounded lag distributed discrete event simulation. In Proceedings of the SCS, Multiconference on Distributed Simulation, 19 (3), pages 183{191. SCS, February 1988.
[16] Boppona R. V. and Chalasani S. A framework for designing deadlock-free wormhole routing algorithm. Parallel and Distributed System, IEEE Transactions, 1996.
[17] K.Peacock J. W. Wong and E. G. Manning. Distributed simulation using a network of processors. Computer Networks, 3:44{56, 1979. 1.
[18] B. P. Zeigler. Multifacetted modelling and discrete event simlation. 1984.