article

Free access

A static partitioning and mapping algorithm for conservative parallel simulations

Authors:

Azzedine Boukerche,

Carl TropperAuthors Info & Claims

ACM SIGSIM Simulation Digest, Volume 24, Issue 1

Pages 164 - 172

https://doi.org/10.1145/195291.182586

Published: 01 July 1994 Publication History

Abstract

In this paper, we consider the problem of partitioning a conservative parallel simulation for execution on a multi-computer. The synchronization protocol makes use of null messages [6]. We propose the use of a simulated annealing algorithm with an adaptive search schedule to find good (sub-optimal) partitions. The paper discusses the algorithm, its implementation and reports on the performance results of simulations of a partitioned FCFS queueing network model executed on iPSC/860 hypercube. The results obtained are compared with a random partitioning. They show that a partitioning which makes use of our simulated annealing algorithm results in a reduction of 25-35% of the running time of the simulations when compared to the running time of a random partition of the model.

References

[1]

Barnes, E. R., "An Algorithm for Partitioning the Nodes of a Graph", SIAM Journal of Algebraic and Discrete Methods, 3(4), 1982, pp. 541-550.

[2]

Bokhari, S. "On the Mapping Problem", IEEE Trans. on Comp., Vol. C-30, (3), March 1981, pp 207-214.

[3]

Bokhari, S. "Assignment Problems in Parallel and Distributed Computing", Kluwar Academic Publishers, Boston, 1987.

Digital Library

[4]

Boukerche A, Tropper C., "Parallel Simulation on the Hypercubic IPSC/1860", submiled to J. Dist. Compt.

Digital Library

[5]

Boukerche A., "Conservative Parllel Simulation with Clustered Processes: Principle and Practice". PhD Thesis, School of Computer Sciences, McGill University, 1994.

[6]

Chandy, K.M., and Misra, J., "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs", IEEE Trans. on Software Engineering, SE-5, Sept. 1979, pp 440-452.

Digital Library

[7]

Cgandy, K.M., and Misra, J. "Asynchronous Distributed Simulation via Sequence of Parallel Computations", CACM, Vol. 24, No. 4, April 1981, pp 198-206.

Digital Library

[8]

Corwin, L. J., Szczarba, R. H., "Multivariable Calculus", Serie of Monographs and Textbooks, Marcel Dekker, Inc. 1979.

[9]

Dunigan T. H., "Performance of the Intel IPSC/2 Hypercube", TR-ORNL/TM-11491, Oak Ridge Nat. Lab., Oak Ridge, TN.

[10]

Feng, T. Y. "A survey of Interconnection Networks", Computers, Special Issue on Intercon., Net., Dec. 1981, pp 12-27.

[11]

Fiduccia, C. M. and Mattheyses, R. M., "A Liner- Time Heuristic for Improving Network Partitions", Proc. of the 19th Design Automation Conf. 1982, pp 178-181, Las Vegas. (ACM/IEEE).

Digital Library

[12]

Fujimoto, R. M., "Parallel Discrete Event Simulation", in Proc. of the 1989 Winter Simul. Conf., 1989, 19-28.

Digital Library

[13]

Fujimoto, R. M., "Parallel Discrete Event Simulation", in CACM, Vol. 33, No. 10, Oct. 1990, pp 30-53.

Digital Library

[14]

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.

Digital Library

[15]

German, S., Geman, D., "Stochastic Relaxation, Gibbs Distributions, and Rayesian Restoration of Images", Presented at Workshop on Statistical Physics in Eng. and biology, IBM Watson Research Center, april 26-27, 1984.

[16]

Glover, F., "Tabu Search - Part I.", ORSA Jounal on Computing, Vol. 1, No. 3, 1986, pp 190-206.

[17]

Golden, B. and Skiscism, C., "Using Simulated Annealing to Solve Routing and Location Problems", Tech. Report, University of Maryland, College of Russian Administration, Jan. 1984.

[18]

Indurkhya, B. et. al., "Optimal Partitioning of Randomly Generated Distributed Programs", IEEE Trans. Software Eng., Vol. SE-12, March 1986.

Digital Library

[19]

Jefferson, D. R., "Virtual Time", ACM Trans. Prog. Lang. Syst. 77, (3), July 1985, pp. 405-425.

Digital Library

[20]

Johnson, D.S., Aragon, C. R., McGeoch, L. A. and Scheveon, C., "Optimization by simulated annealing: An Experimental Evaluation; Part 1, Graph Partitioning", Operations Research, Vol. 37, No. 6, 1989, pp 865-892.

Digital Library

[21]

Jones, D. W. "An Empirical Comparison of Priority-Quene and Event-Set Implementations", Comm. ACM, Vol. 29, No. 4, April 1986, pp. 300-311.

Digital Library

[22]

Kernighan, B. W. and Lin, S., "An Efficient Heuristic Procedure for Partitioning Graphs". The Bell System Technical Journal, Vol. 49, No. 2, Feb. 1970, pp. 291-307.

[23]

Kirkpatrick, S., Gelatt, C.D and Vecchi, M. P., "Optimization by Simulated annealing". Science. 220(4598), 1983, pp. 671-680.

[24]

Kravits, S. A. and Rulenbar, R., "Placement by Simulated Annealing on a Multiprocessor", IEEE Trans. Compt. Design, Vol. CAD-6, July 1987, pp. 534-549.

[25]

Lin, Y. B. and Lazowska, E. D., "Conservative Parallel Simulation for Systems with no Lookahead Prediction", TR 89-07-07, Dept. of Comp. Sc. and Eng., Univ. of Washington, 1989.

[26]

Livny, M., "a Study of Parallelism in Distributed Simulation", Proc. of the SCS Multiconf. on Distributed Simulation, Reynold (Editor), SCS Simulation Serie, Vol. 15, No. 2, Jan. 1985.

[27]

Misra, J., "Distributed Discrete-Event Simulation", ACM Computing Surveys, 18(1), March 1986, pp. 39-65.

Digital Library

[28]

Metropolis, N., A Rosenbuth, M. Rosenbulth, A. Teller and E. Teller, "Equation of state Calculations by Fast Computing Machines", J. of Checn. Physics, 21 (1953) 1087-1092.

[29]

Mitra, D., Romeo, F. and Sangiovanni-Vincentelli, "Convergence and Finite-Time Behavior of simulated Annealing". Tech. Report UCR/ERL M85/23, Univ. of Calif. Berkeley, March 1985.

[30]

Nahar, S., S. Sahni and E. Shragowitz, "Simulated Annealing and Combinatorial Optimization", Proc. 23rd Des. Auto. Conf., Las Vegas, June 1986, pp. 293-299.

Digital Library

[31]

Nandy, B. and Loucks, W. M., "An Algorithm for Partitioning and Mapping Conservative Parallel Simulation onto Multicomputer", Proc. of the SCS Multiconf. on Parallel and Distributed Simulation, SCS Simulation Serie, 1992, pp. 139-146.

[32]

Ni, L. et. al., "A Distributed Drafting Algorithm for Load Balancing", IEEE Trans. Sof. Eng., Vol. 11(10), 1985.

Digital Library

[33]

Nicol, D. M., "dynamic Remapping of Parallel Time-stepped Simulations", in Proc. of the SCS Multiconf. on Distributed Simulation, Vol. 21(2), March 1989.

[34]

Nicol, D.M. and Reynolds, P.F., "The automaed Partitioning of Simulations for Parallel Execution", Tech. Report. Tr-85-15, Univ. Virginia, August 1985.

[35]

Nicol, D.M., "Parallel Discrete-Event Simulation of FCFS Stochastic Quening Networks", in Proc. of the ACM SIGPLAN symp. on Parallel Prog. Env., Applications, and Languages, Yale University, July 1988.

Digital Library

[36]

Reed, D. A. and Malony, A. "Parallel Discrete Event Simulation: The Chandy-Misra Approach," In Proc. 1988 SCS Multiconf. on Dist. Simulation, 1988, pp. 8-13.

[37]

Righler, R. and Warland, J.V., "Distributed Simulation of Discrete Event Systems", Proc. of the IEEE, Vol. 77, No. 1, Jan. 1989, pp. 99-113.

[38]

Sechen, C., and Sangiovanni-Vincentelli, "TimberWolf 3.2: A new Standard Cell Placement and Global Routing Package", Proc. 23rd Des. Automation Conf., Las Vegas, June 1986, p. 432-439.

Digital Library

[39]

Shankar, M. S. and Palnwo, B. E., "The Effect of Synchronization Requirements on the Performance of Distributed Simulations", Proc. of the SCS Multiconf. on Parallel and Distributed Simulation, SCS Simulation Serie, Vol. 23, No. 1, 1993, pp. 151-154.

Digital Library

[40]

Sporrer, C. and Bauer, H., "Corolla Partitioning for Distributed Logic Simulation of VLSI-circuits", Proc. of SCS Multiconf. on Parallel and Distributed Simulation, SCS Simulation Serie, Vol. 23, No. 1, 1993, pp. 85-92.

Digital Library

[41]

Stankovic, J. and Sidhu, I., "An Adapative Bidding Algorithm for Processes, Clusters and Distributed Groups", Proc. 4th Int. Conf. Distributed Comput. Systems, 1984.

[42]

Witte, E. E., Chamberlain, R. D. and Franklin, M. A., "Task Assignment by Parallel Simulated Annealing", IEEE Trans on Parallel and Distributed Systems, 1991.

[43]

Wong, D.F. and C.L. Liu, "A New Algorithm Floor Plan Design", Proc. 23rd, Des. Automation Conf., Las Vegas, June 1986, pp. 101-107.

Digital Library

Cited By

Ibrahim MIqbal MAleem MIslam MVo N(2019)MAHA: Migration-based Adaptive Heuristic Algorithm for Large-scale Network SimulationsCluster Computing10.1007/s10586-019-02991-5Online publication date: 25-Sep-2019
https://doi.org/10.1007/s10586-019-02991-5
Bergero FKofman ECellier F(2012)A novel parallelization technique for DEVS simulation of continuous and hybrid systemsSIMULATION10.1177/003754971245493189:6(663-683)Online publication date: 15-Aug-2012
https://doi.org/10.1177/0037549712454931
Grande RBoukerche ARamadan H(2011)Distributed re‐arrangement scheme for balancing computational load and minimizing communication delays in HLA‐based simulationsConcurrency and Computation: Practice and Experience10.1002/cpe.180725:5(626-648)Online publication date: 28-Jul-2011
https://doi.org/10.1002/cpe.1807
Show More Cited By

Index Terms

A static partitioning and mapping algorithm for conservative parallel simulations
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Massively parallel and high-performance simulations
2. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

A static partitioning and mapping algorithm for conservative parallel simulations
PADS '94: Proceedings of the eighth workshop on Parallel and distributed simulation

In this paper, we consider the problem of partitioning a conservative parallel simulation for execution on a multi-computer. The synchronization protocol makes use of null messages [6]. We propose the use of a simulated annealing algorithm with an ...
An improved cost function for static partitioning of parallel circuit simulations using a conservative synchronization protocol
PADS '95: Proceedings of the ninth workshop on Parallel and distributed simulation

Distributing computation among multiple processors is one approach to reducing simulation time for large VLSI circuit designs. However, parallel simulation introduces the problem of how to partition the logic gates and system behaviors of the circuit ...
An improved cost function for static partitioning of parallel circuit simulations using a conservative synchronization protocol

Distributing computation among multiple processors is one approach to reducing simulation time for large VLSI circuit designs. However, parallel simulation introduces the problem of how to partition the logic gates and system behaviors of the circuit ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGSIM Simulation Digest

ACM SIGSIM Simulation Digest Volume 24, Issue 1

July 1994

192 pages

ISSN:0163-6103

DOI:10.1145/195291

Editors:
D. K. Arvind
Univ. of Edinburgh, Edinburgh, Scotland, UK
,
Rajive Bagrodia
Univ. of California, Los Angeles
,
Jason Yi-Bing Lin
Bellcore, Morristown, NJ

Issue’s Table of Contents

PADS '94: Proceedings of the eighth workshop on Parallel and distributed simulation
August 1994
196 pages
ISBN:1565550277
DOI:10.1145/182478
Editors:
D. K. Arvind
Univ. of Edinburgh, Scotland, UK
,
Rajive Bagrodia
Univ. of California, Los Angeles
,
Jason Yi-Bing Lin
Bellcore

Copyright © 1994 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1994

Published in SIGSIM Volume 24, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

67
Total Citations
View Citations
487
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)9

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ibrahim MIqbal MAleem MIslam MVo N(2019)MAHA: Migration-based Adaptive Heuristic Algorithm for Large-scale Network SimulationsCluster Computing10.1007/s10586-019-02991-5Online publication date: 25-Sep-2019
https://doi.org/10.1007/s10586-019-02991-5
Bergero FKofman ECellier F(2012)A novel parallelization technique for DEVS simulation of continuous and hybrid systemsSIMULATION10.1177/003754971245493189:6(663-683)Online publication date: 15-Aug-2012
https://doi.org/10.1177/0037549712454931
Grande RBoukerche ARamadan H(2011)Distributed re‐arrangement scheme for balancing computational load and minimizing communication delays in HLA‐based simulationsConcurrency and Computation: Practice and Experience10.1002/cpe.180725:5(626-648)Online publication date: 28-Jul-2011
https://doi.org/10.1002/cpe.1807
Wang GBölöni LTurgut DMarinescu D(2009)Time-parallel simulation of wireless ad hoc networks with compressed historyJournal of Parallel and Distributed Computing10.1016/j.jpdc.2008.06.00869:2(168-179)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1016/j.jpdc.2008.06.008
Wang GTurgut DBölöni LMarinescu D(2009)Time-parallel simulation of wireless ad hoc networksWireless Networks10.1007/s11276-007-0058-115:4(463-480)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1007/s11276-007-0058-1
D'Angelo GFerretti STan G(2019)Internet-Based Adaptive Distributed Simulation of Mobile Ad-hoc Networks2019 Winter Simulation Conference (WSC)10.1109/WSC40007.2019.9004796(2641-2652)Online publication date: Dec-2019
https://doi.org/10.1109/WSC40007.2019.9004796
Liu DDe Grande RBoukerche ADiallo STolk A(2015)An adaptive fault-tolerance scheme for distributed load balancing systemsProceedings of the 48th Annual Simulation Symposium10.5555/2876341.2876360(138-145)Online publication date: 12-Apr-2015
https://dl.acm.org/doi/10.5555/2876341.2876360
Sianati ABoukerche ADe Grande R(2015)Bundling communication messages in large scale cloud environmentsProceedings of the 2015 IEEE Symposium on Computers and Communication (ISCC)10.1109/ISCC.2015.7405610(788-795)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1109/ISCC.2015.7405610
Lingfeng Wang Yangdong Steve Deng (2013)Logic process merging for conservative parallel simulation of logic circuits2013 IEEE 4th International Conference on Software Engineering and Service Science10.1109/ICSESS.2013.6615484(1037-1040)Online publication date: May-2013
https://doi.org/10.1109/ICSESS.2013.6615484
De Grande RAlmulla MBoukerche A(2013)Autonomous Configuration Scheme in a Distributed Load Balancing System for HLA-Based SimulationsProceedings of the 2013 IEEE/ACM 17th International Symposium on Distributed Simulation and Real Time Applications10.1109/DS-RT.2013.26(169-176)Online publication date: 30-Oct-2013
https://dl.acm.org/doi/10.1109/DS-RT.2013.26
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents