Recent advances in wireless data communications tech nology have spawned an increasing demand for various types of services over wireless and wireline networks. As a result, we are witnessing an explosive growth of research and development efforts in the field of wireless and personal communication systems (PCS). Parallel simulation techniques have been investigated in studies to decrease the execution times of PCS simulations. In this paper, we present a partitioning algorithm for SWiMNet, a two-stage PCS parallel simulation testbed which makes use of a conservative scheme at Stage 1, and Time Warp at Stage 2. The partitioning algorithm focuses on statically distributing the load of the simu lation evenly in order to decrease the rollback overhead in Stage 2. The algorithm is based on an estimation of the loads involved by the model components. This paper discusses the algorithm, its implementation on a work station cluster, and the performance results of the simu lation of a real suburban area serviced by an FCA-based PCS network. The results are compared with a round- robin partitioning algorithm. The results show that the investigated partitioning algorithm can achieve a re duction of up to 60% in the rollback message overhead.
Chandy, K.M. and Misra, J. "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs." IEEE Transactions on Software Engineering, Vol. SE-5, pp 440-452, September 1979.
2.
Fujimoto, R.M. "Parallel Discrete Event Simulation." Communications of the ACM, Vol. 33, No. 10, pp 30-53, October 1990.
3.
Jefferson, D.R. "Virtual Time." ACM Transactions on Programming Languages and Systems, Vol. 7, No. 3, pp 404-425, July 1985.
4.
Carothers, C. , Fujimoto, R.M., Lin, Y.-B. and England, P. "Distributed Simulation of Large-Scale PCS Networks." Proceedings of the 2nd Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'94) , pp 2-6, 1994.
5.
Liljenstam, M. and Ayani, R. "A Model for Parallel Simulation of Mobile Telecommunication Systems." Proceedings of the 4th Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'96), 1996.
6.
Meyer, R.A. and Bagrodia, R.L. "Improving Lookahead in Parallel Wireless Network Simulation." Proceedings of the 6th Workshop on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'98), pp 262-267, 1998.
7.
Boukerche, A. , Das, S.K., Fabbri, A., and Yildiz, O. "Exploiting Model Independence for Parallel PCS Network Simulation." Proceedings of the 13th Workshop on Parallel and Distributed Simulation, PADS'99, pp 166-173.
8.
Bokhari, S., Assignment Problems in Parallel and Distributed Computing. Kluwer Academic Publishers, Boston, 1987.
9.
Ni, L. , et al. "A Distributed Drafting Algorithm for Load Balancing." IEEE Transactions on Software Engineering , Vol. 11, No. 10, 1985.
10.
Stankovic, J. and Sidhu, I. "An Adaptive Bidding Algorithm for Processes, Clusters and Distributed Groups." Proceedings of the 4th International Conference on Distributed Computer Systems, 1984.
11.
Garey, M.R. and Johnson, D.S.Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979.
12.
Kleinrock, L. and Nilson A. "On Optimal Scheduling Algorithms for Time-Shared Systems." J. Assoc. Compt., Vol. 28, No. 3, pp 477-486, July 1981.
13.
Saltz, J.H. , Naik, V.K. and Nicol, D.M. "Reduction of the Effects of the Communication Delays in Scientific Algorithms on Message Passing MIMD Architectures." SIAM Journal of Scientific and Statistical Computing, Vol. 8, No. 1, pp 118-134, January 1987.
14.
Nicol, D.M. "Dynamic Remapping of Parallel Time-Stepped Simulations." Proceedings of the SCS Multiconference on Distributed Simulation, Vol. 21, No. 2, March 1989.
15.
Nicol, D.M. and O'Hallaron, D.R. "Improved Algorithms for Mapping Parallel and Pipelined Computations." IEEE Transactions on Computers , Vol. 40, No. 3, pp 295-306, 1991.
16.
Berger, M. and Bokhari, S. "A Partitioning Strategy for Uniform Problems on Multiprocessors." IEEE Transactions on Computers, Vol. C-36, No. 5, pp 570-580, May 1987.
17.
Kim, S. and Brown, J. "A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures." Proceedings of the International Conference on Parallel Processing, Vol. 3, pp 1-8, 1988.
18.
Sarkar, V.Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors . MIT Press, 1989.
19.
Yang, T. and Gerasoulis, A. "A Dominant Sequence Clustering Heuristic Algorithm For Scheduling DAGs on Multiprocessors." Tech. Report, Dept. of Computer Science, Rutgers University, 1991.
20.
Wu, M.Y. and Gajski, D. "A Programming Aid for Hypercube Architecture ." Journal of Supercomputing, Vol. 2, pp 349-372, 1988.
21.
Tao, L., Narahari, B. and Zaho, Y.C. "Partitioning Problems in Heterogeneous Computing." Workshop on Heterogeneous Processing, pp 23-28, April 1993 .
22.
Kling, R. and Banerjee, P. "Optimization by Simulated Evolution with Applications to Standard Cell Placement." 27th ACM/IEEE Design Automation Conference, 1990.
23.
Kernighan, B.W. and Lin, S. "An Efficient Heuristic Procedure for Partitioning Graphs." The Bell System Technical journal, Vol. 49, No. 2, pp 291-307, February 1970.
24.
Schweikert, D.G. and Kernighan, B.W. "A Proper Model for the Partitioning of Electrical Circuits." 9th Design Automation Workshop , pp 57-62, 1972.
25.
Fiduccia, C.M. and Mattheyses, R.M. "A Linear-Time Heuristic for Improving Network Partitions." Proceedings of the 19th Design Automation Conference, Las Vegas, pp 175-181, 1982.
26.
Krishnamurthy, B. "An Improved Mincut Algorithm for Partitioning VLSI Networks." IEEE Transactions on Computers, Vol. C-33, pp 438-446, May 1984.
27.
Sanchis, L.A. "Multi-Way Partitioning Network Partitioning ." IEEE Transactions on Computers, Vol. 38, No. 1, pp 62-81, January 1989.
28.
Ching-Wei, Y. and Chung-Kuan, C. "A General Purpose Multiple Way Partitioning Algorithm." 28th ACM/IEEE Design Automation Conference , pp 421-426,1991.
29.
Nicol, D.M. and Reynolds, P.F. "The Automated Partitioning of Simulations for Parallel Execution." Tech. Report, TR-85-15, University of Virginia, August 1985.
30.
Nandy, B. and Loucks, W.M. "An Algorithm for Partitioning and Mapping Conservative Parallel Simulation onto Multicomputer." Proceedings of the SCS MultiConference on Parallel and Distributed Simulation, SCS Simulation Series, pp 139-146, 1992.
31.
Boukerche, A. and Tropper, C. "A Static Partitioning and Mapping Algorithm for Conservative Parallel Simulations." Proceedings of the 8th Workshop on Parallel and Distributed Simulation, pp 164-172, 1994.
32.
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A. and Teller, E. "Equation of State Calculations by Fast Computing Machines." J. of Chem. Physics, Vol. 21, pp 1087-1092, 1953.
33.
Boukerche, A. and Das, S.K. "Efficient Dynamic Load Balancing Algorithms for Conservative Parallel Simulations." PADS'97 .
34.
Liljenstam, M. and Ayani, R. "Partitioning PCS for Parallel Simulation ." Proceedings of the 5th Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, pp 38-43, 1997.
35.
Rappaport, T.D.Wireless Communications: Principles and Practice . Prentice Hall, 1996.
36.
MPI Primer / Developing with LAM. Ohio Supercomputer Center , OhioState University, 1996.
