Article

A non-fragmenting partitioning algorithm for hierarchical models

Authors:

Jan Himmelspach,

Adelinde M. UhrmacherAuthors Info & Claims

WSC '06: Proceedings of the 38th conference on Winter simulation

Pages 848 - 855

Published: 03 December 2006 Publication History

Abstract

The simulation system JAMES II is aimed at supporting a range of modeling formalisms and simulation engines. The partitioning of models is essential for distributed simulation. A suitable partition depends on model, hardware, and simulation algorithm characteristics. Therefore, a partitioning layer has been created in JAMES II which allows to plug in partitioning algorithms on demand. Three different partitioning algorithms have been implemented. In addition to the well known Kernighan-Lin algorithm and a geometric approach, a partitioning algorithm for hierarchically structured models has been developed whose performance is evaluated.

References

[1]

Bailey, M. L., J. V. J. Briner, and R. D. Chamberlain. 1994. Parallel logic simulation of vlsi systems. ACM Comput. Surv. 26 (3): 255--294.]]

Digital Library

[2]

Boukerche, A., and C. Tropper. 1994. A static partitioning and mapping algorithm for conservative parallel simulations. In PADS '94: Proc. of the 8th workshop on Parallel and distributed simulation, 164--172. New York, NY, USA: ACM Press.]]

Digital Library

[3]

Cuthill, E., and J. McKee. 1969. Reducing the bandwidth of sparse symmetric matrices. In Proceedings Of The 1969 24th National Conference, 157--172. New York, NY, USA: ACM Press.]]

Digital Library

[4]

Edmonds, B. 1999. The evolution of complexity, Chapter What is Complexity? - The philosophy of complexity per se with application to some examples in evolution. Dordrecht: Kluwer.]]

[5]

Fjällström, P.-O. 1998. Algorithms for graph partitioning: A survey. In Linkoping Electronic Atricles in Computer and Information Science, 3.]]

[6]

Gamma, E., R. Helm, R. Johnson, and J. Vlissides. 1994. Design patterns: elements of reusable object-oriented software. Addison-Wesley, Reading, MA, USA.]]

Digital Library

[7]

Himmelspach, J., and A. M. Uhrmacher. 2004a. A component-based simulation layer for JAMES. In Proc. of the 18th Workshop on Parallel and Distributed Simulation (PADS), May 16--19, 2004, Kufstein, Austria, 115--122.]]

Digital Library

[8]

Himmelspach, J., and A. M. Uhrmacher. 2004b, October. Processing dynamic PDEVS models. In Proc. of the 12th IEEE Int'l Symposium on MASCOTS, ed. D. DeGroot and P. Harrison, 329--336. Volendam, The Netherlands: IEEE Computer Society.]]

Digital Library

[9]

Karypis, G., and V. Kumar. 1995. Metis: Unstrctured graph partitioning and sparse matrix ordering system, version 2.0.]]

[10]

Kernighan, B. W., and S. Lin. 1970. An efficient heuristic procedure for partitioning graphs. Bell System Tech. Journal 49.]]

[11]

Kim, K. H., Y. R. Seong, T. G. Kim, and K. H. Park. 1995. Distributed optimistic simulation of hierarchical devs models. In Summer Computer Simulation Conference 95, 32--37. Ottawa, Canada.]]

[12]

Lemeire, J., B. Smets, P. Cara, and E. Dirkx. 2004. Exploiting symmetry for partitioning models in parallel discrete event simulation. In PADS '04: Proc. of the 18th workshop on Parallel and distributed simulation, 189--194. New York, NY, USA: ACM Press.]]

Digital Library

[13]

Li, L., H. Huang, and C. Tropper. 2003. Dvs: An object oriented framework for distributed verilog simulation. In 17th Workshop on Parallel and Distributed Simulation, 173--180. San Diego: IEEE Computer Society Press.]]

Digital Library

[14]

Nicol, D. M. 1998. Scalability, locality, partitioning and synchronization pdes. In Proc. of the 12th Workshop on Parallel and distributed simulation, 5--11: IEEE Computer Society.]]

Digital Library

[15]

Park, S., and B. P. Zeigler. 2003. Distributing simulation work based on component activity: A new approach to partitioning hierarchical DEVS models. In 1st International Workshop on Challenges of Large Applications in Distributed Environments, 124.]]

Digital Library

[16]

Schloegel, K., G. Karypis, and V. Kumar. 2000. Graph partitioning for high performance scientific simulations.]]

Digital Library

[17]

Uhrmacher, A., M. Röhl, and J. Himmelspach. 2003. Unpaced and paced simulation for testing agents. In Simulation in Industry, 15th European Simulation Symposium, 71--80. Delft: SCS-European Publishing House.]]

[18]

Zeigler, B., H. Praehofer, and T. Kim. 2000. Theory of modeling and simulation. London: Academic Press.]]

Digital Library

Cited By

Bahulkar KWang JAbu-Ghazaleh NPonomarev D(2012)Partitioning on Dynamic Behavior for Parallel Discrete Event SimulationProceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2012.32(221-230)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1109/PADS.2012.32
Wang BYao YHimmelspach JEwald RUhrmacher ADunkin AIngalls R(2009)Experimental analysis of logical process simulation algorithms in JAMES IIWinter Simulation Conference10.5555/1995456.1995619(1167-1179)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995619
Himmelspach JEwald RUhrmacher AJefferson TFowler JIngalls R(2008)A flexible and scalable experimentation layerProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516895(827-835)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.5555/1516744.1516895
Show More Cited By

Recommendations

Hierarchical partitioning for field-programmable systems
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

This paper presents a new recursive bipartitioning algorithm for a hierarchical field-programmable system. It draws new insights into relating the quality of the bipartitioning algorithm to circuit structures by the use of the partitioning tree (Hagen ...
Cost-based partitioning for distributed simulation of hierarchical modular devs models
A concurrency preserving partitioning algorithm for parallel simulation of hierarchical, modular discrete event models
HPC-ASIA '97: Proceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '97

The paper presents a concurrency preserving partitioning algorithm for the optimistic parallel simulation of hierarchical, modular discrete event models. The proposed algorithm pursues the following three goals to achieve the overall objective of a ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '06: Proceedings of the 38th conference on Winter simulation

December 2006

2429 pages

ISBN:1424405017

Editors:
L. Felipe Perrone
Bucknell University
,
Barry G. Lawson
University of Richmond
,
Jason Liu
Colorado School of Mines
,
Frederick P. Wieland
Sensis Corporation
,
General Chair:
David Nicol
University of Illinois, Urbana-Champaign
,
Program Chair:
Richard Fujimoto
College of Computing, Georgia Tech

Sponsors

IIE: Institute of Industrial Engineers
ASA: American Statistical Association
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE-CS\DATC: The IEEE Computer Society
SIGSIM: ACM Special Interest Group on Simulation and Modeling
NIST: National Institute of Standards and Technology
(SCS): The Society for Modeling and Simulation International
INFORMS-CS: Institute for Operations Research and the Management Sciences-College on Simulation

Publisher

Winter Simulation Conference

Publication History

Published: 03 December 2006

Check for updates

Qualifiers

Article

Conference

WSC06

Sponsor:

IIE
ASA
IEICE ESS
IEEE-CS\DATC
SIGSIM
NIST
(SCS)
INFORMS-CS

WSC06: Winter Simulation Conference 2006

December 3 - 6, 2006

California, Monterey

Acceptance Rates

WSC '06 Paper Acceptance Rate 177 of 252 submissions, 70%;

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bahulkar KWang JAbu-Ghazaleh NPonomarev D(2012)Partitioning on Dynamic Behavior for Parallel Discrete Event SimulationProceedings of the 2012 ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2012.32(221-230)Online publication date: 15-Jul-2012
https://dl.acm.org/doi/10.1109/PADS.2012.32
Wang BYao YHimmelspach JEwald RUhrmacher ADunkin AIngalls R(2009)Experimental analysis of logical process simulation algorithms in JAMES IIWinter Simulation Conference10.5555/1995456.1995619(1167-1179)Online publication date: 13-Dec-2009
https://dl.acm.org/doi/10.5555/1995456.1995619
Himmelspach JEwald RUhrmacher AJefferson TFowler JIngalls R(2008)A flexible and scalable experimentation layerProceedings of the 40th Conference on Winter Simulation10.5555/1516744.1516895(827-835)Online publication date: 7-Dec-2008
https://dl.acm.org/doi/10.5555/1516744.1516895
Himmelspach JEwald RLeye SUhrmacher AAdes M(2007)Parallel and distributed simulation of parallel DEVS modelsProceedings of the 2007 spring simulation multiconference - Volume 210.5555/1404680.1404720(249-256)Online publication date: 25-Mar-2007
https://dl.acm.org/doi/10.5555/1404680.1404720

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten