Skip to main content
Erschienen in: Cluster Computing 3/2013

01.09.2013

A hierarchical parallel discrete event simulation kernel for multicore platform

verfasst von: Tang Wenjie, Yao Yiping, Zhu Feng

Erschienen in: Cluster Computing | Ausgabe 3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The development of CPU has stepped into the era of multicore. Current parallel simulation kernel utilizes multicore resource by multi-process, which leads to inefficiency on communication and synchronization. To fulfill this gap, we proposed a HPSK (hierarchical parallel simulation kernel) model, which schedules logical processes and executes events in parallel with multithread paradigm. Based on this model, three key algorithms were proposed to support high performance: (1) An event management algorithm was proposed to improve the efficiency of creation and release of events. It uses a lock-free creation and asynchronous commitment mechanism to decouple the relationship between threads, hence reduce the overhead of locks. (2) A pointer-based communication algorithm was proposed to improve efficiency of communication between threads. It uses a buffer mechanism to avoid interrupting the execution of target thread. The target thread will read events from the buffers when it needs. By using ring-structure buffers, synchronization between sending and receiving of threads can be annihilated. (3) An approximate method was proposed to compute LBTS (Lower Bound on Time Stamp). It uses an asynchronous mechanism to eliminate disturbing of thread execution and a two-level filter mechanism to reduce redundant LBTS computation. A series of experiments with a modified phold model show that HPSK can achieve good performance for applications on different conditions. It can run 8× faster than μsik when event locality and lookahead is low.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Asanovic, K., Bodik, R., Catanzaro, B., Gebis, J., Husbands, P., Keutzer, K., Patterson, D., Plishker, W., Shalf, J., Williams, S., Yelik, K.: The landscape of parallel computing research: a view from Berkley. Technical report, EECS Department, University of California at Berkley, UCB/EECS-2006-183 (2006) Asanovic, K., Bodik, R., Catanzaro, B., Gebis, J., Husbands, P., Keutzer, K., Patterson, D., Plishker, W., Shalf, J., Williams, S., Yelik, K.: The landscape of parallel computing research: a view from Berkley. Technical report, EECS Department, University of California at Berkley, UCB/EECS-2006-183 (2006)
2.
Zurück zum Zitat Akhter, S., Roberts, J.: Multi-Core Programming: Increasing Performance through Software Multi-threading. Intel Press, New York (2006) Akhter, S., Roberts, J.: Multi-Core Programming: Increasing Performance through Software Multi-threading. Intel Press, New York (2006)
3.
Zurück zum Zitat Law, M., Kelton, D.W.: Simulation Modelling and Analysis. McGraw-Hill, New York (2000) Law, M., Kelton, D.W.: Simulation Modelling and Analysis. McGraw-Hill, New York (2000)
4.
Zurück zum Zitat Fujimoto, R.M.: Parallel and Distributed Simulation Systems. Wiley, New York (2000) Fujimoto, R.M.: Parallel and Distributed Simulation Systems. Wiley, New York (2000)
5.
Zurück zum Zitat Steinman, J., Park, J., Delane, N., Walter, W.: The need for change in modeling and simulation. Chem-Bio Defense Quarterly 22–25 (2008) Steinman, J., Park, J., Delane, N., Walter, W.: The need for change in modeling and simulation. Chem-Bio Defense Quarterly 22–25 (2008)
6.
Zurück zum Zitat Steinman, J.: Introduction to parallel and distributed force modeling and simulation. In: Simulation Interoperability Workshop, Paper 09S-SIW-021 (2009) Steinman, J.: Introduction to parallel and distributed force modeling and simulation. In: Simulation Interoperability Workshop, Paper 09S-SIW-021 (2009)
7.
Zurück zum Zitat Yelick, K.: Hardware and software in the multicore era. In: HEPiX Meeting, Berkeley, California, October 26 (2009) Yelick, K.: Hardware and software in the multicore era. In: HEPiX Meeting, Berkeley, California, October 26 (2009)
8.
Zurück zum Zitat Steinman, J.: Speedes: a unified approach to parallel simulation. In: Proceedings of the 6th Workshop on Parallel and Distributed Simulation, pp. 75–83 (1992) Steinman, J.: Speedes: a unified approach to parallel simulation. In: Proceedings of the 6th Workshop on Parallel and Distributed Simulation, pp. 75–83 (1992)
9.
Zurück zum Zitat Das, S., Fujimoto, R., Panesar, K., Allison, D., Hybinette, M.: Gtw: a time warp system for shared memory multiprocessors. In: Proceedings of the 26th Conference on Winter simulation, pp. 1332–1339 (1994) CrossRef Das, S., Fujimoto, R., Panesar, K., Allison, D., Hybinette, M.: Gtw: a time warp system for shared memory multiprocessors. In: Proceedings of the 26th Conference on Winter simulation, pp. 1332–1339 (1994) CrossRef
10.
Zurück zum Zitat Carothers, C.D., Bauer, D., Pearce, S.: Ross: a high-performance, low memory, modular time warp system. Journal of Parallel and Distributed Computing 53–60 (2000) Carothers, C.D., Bauer, D., Pearce, S.: Ross: a high-performance, low memory, modular time warp system. Journal of Parallel and Distributed Computing 53–60 (2000)
11.
Zurück zum Zitat Bagrodia, R., Takai, M., Chen, Y., Zeng, X., Martin, J.: Parsec: a parallel simulation environment for complex systems. Computer 31, 77–85 (1998) CrossRef Bagrodia, R., Takai, M., Chen, Y., Zeng, X., Martin, J.: Parsec: a parallel simulation environment for complex systems. Computer 31, 77–85 (1998) CrossRef
12.
Zurück zum Zitat Yao, Y., Zhang, Y.: Solution for analytic simulation based on parallel processing. J. Syst. Simul. 20(24), 6617–6621 (2008) (in Chinese) MathSciNet Yao, Y., Zhang, Y.: Solution for analytic simulation based on parallel processing. J. Syst. Simul. 20(24), 6617–6621 (2008) (in Chinese) MathSciNet
13.
Zurück zum Zitat Perumalla, K.: μsik—a micro-kernel for parallel/distributed simulation systems. In: Proceedings of Workshop on Principles of Advanced and Distributed Simulation (PADS), pp. 59–68 (2005) CrossRef Perumalla, K.: μsik—a micro-kernel for parallel/distributed simulation systems. In: Proceedings of Workshop on Principles of Advanced and Distributed Simulation (PADS), pp. 59–68 (2005) CrossRef
14.
Zurück zum Zitat Su, N.-l., Wu, X.-y., Li, Q., Wang, W.-p., Zhu, Y.-f.: Optimistic parallel discrete event simulation based on multi-core platform. J. Syst. Simul. 22(4) (2010) (in Chinese) Su, N.-l., Wu, X.-y., Li, Q., Wang, W.-p., Zhu, Y.-f.: Optimistic parallel discrete event simulation based on multi-core platform. J. Syst. Simul. 22(4) (2010) (in Chinese)
15.
Zurück zum Zitat Steinman, J.: The WarpIV simulation kernel. In: Proceedings of the 2005 Principles of Advanced and Distributed Simulation Conference, pp. 161–170 (2005) Steinman, J.: The WarpIV simulation kernel. In: Proceedings of the 2005 Principles of Advanced and Distributed Simulation Conference, pp. 161–170 (2005)
16.
Zurück zum Zitat Miller, R.J.: Optimistic parallel discrete event simulation on a Beowulf cluster of multi-core machines. Master dissertation, Cincinnati University, July, 2010 Miller, R.J.: Optimistic parallel discrete event simulation on a Beowulf cluster of multi-core machines. Master dissertation, Cincinnati University, July, 2010
17.
Zurück zum Zitat Martin, D.E., McBrayer, T.J., Wilsey, P.A.: Warped: a time warp simulation kernel for analysis and application development. In: Proceedings of the 29th Hawaii International Conference on System Sciences. Software Technology and Architecture, vol. 1, pp. 383–386 (1996) CrossRef Martin, D.E., McBrayer, T.J., Wilsey, P.A.: Warped: a time warp simulation kernel for analysis and application development. In: Proceedings of the 29th Hawaii International Conference on System Sciences. Software Technology and Architecture, vol. 1, pp. 383–386 (1996) CrossRef
18.
Zurück zum Zitat Michael, M.M.: Scalable lock-free dynamic memory allocation. ACM SIGPLAN Not. 39(6), 35–46 (2004) CrossRef Michael, M.M.: Scalable lock-free dynamic memory allocation. ACM SIGPLAN Not. 39(6), 35–46 (2004) CrossRef
19.
Zurück zum Zitat Berger, E.D., McKinley, K.S., Blumofe, R.D., Wilson, P.R.: Hoard: a scalable memory allocator for multithreaded applications. In: Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 117–128 (2000) Berger, E.D., McKinley, K.S., Blumofe, R.D., Wilson, P.R.: Hoard: a scalable memory allocator for multithreaded applications. In: Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 117–128 (2000)
20.
Zurück zum Zitat Dice, D., Garthwaite, A.: Mostly lock-free malloc. In: Proceedings of the 2002 International Symposium on Memory Management, pp. 269–280 (2002) Dice, D., Garthwaite, A.: Mostly lock-free malloc. In: Proceedings of the 2002 International Symposium on Memory Management, pp. 269–280 (2002)
21.
Zurück zum Zitat Samadi, B.: Distributed simulation, algorithms and performance analysis. Ph.D. thesis, University of California, Los Angels (1985) Samadi, B.: Distributed simulation, algorithms and performance analysis. Ph.D. thesis, University of California, Los Angels (1985)
22.
Zurück zum Zitat Mattern, F.: Efficient algorithms for distributed snapshots and global virtual time approximation. J. Parallel Distrib. Comput. 18(4), 423–434 (1993) CrossRef Mattern, F.: Efficient algorithms for distributed snapshots and global virtual time approximation. J. Parallel Distrib. Comput. 18(4), 423–434 (1993) CrossRef
23.
Zurück zum Zitat Fujimoto, R.M., Hybinette, M.: Computing global virtual time in shared-memory multiprocessors. ACM Trans. Model. Comput. Simul. 7(4), 425–446 (1997) MATHCrossRef Fujimoto, R.M., Hybinette, M.: Computing global virtual time in shared-memory multiprocessors. ACM Trans. Model. Comput. Simul. 7(4), 425–446 (1997) MATHCrossRef
25.
Zurück zum Zitat Chen, D., et al.: Synchronization in federation community networks. J. Parallel Distrib. Comput. 70(2), 144–159 (2010) MATHCrossRef Chen, D., et al.: Synchronization in federation community networks. J. Parallel Distrib. Comput. 70(2), 144–159 (2010) MATHCrossRef
26.
Zurück zum Zitat Yao, Y., Zhang, Y., Chen, X., Ji, L.: Intersecting-information-based matching algorithm for dynamic DDM. Chin. J. Comput 32(7), 1375–1381 (2009) (in Chinese) CrossRef Yao, Y., Zhang, Y., Chen, X., Ji, L.: Intersecting-information-based matching algorithm for dynamic DDM. Chin. J. Comput 32(7), 1375–1381 (2009) (in Chinese) CrossRef
27.
Zurück zum Zitat Gang, L., Yao, Y., Peng, S.: EDEVS: a scalable DEVS formalism for event-scheduling based parallel and distributed simulations. In: Proceedings of 13th IEEE/ACM International Symposium on Distributed Simulation and Real-Time Applications (DS-RT 2009), pp. 239–242 (2009) Gang, L., Yao, Y., Peng, S.: EDEVS: a scalable DEVS formalism for event-scheduling based parallel and distributed simulations. In: Proceedings of 13th IEEE/ACM International Symposium on Distributed Simulation and Real-Time Applications (DS-RT 2009), pp. 239–242 (2009)
Metadaten
Titel
A hierarchical parallel discrete event simulation kernel for multicore platform
verfasst von
Tang Wenjie
Yao Yiping
Zhu Feng
Publikationsdatum
01.09.2013
Verlag
Springer US
Erschienen in
Cluster Computing / Ausgabe 3/2013
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI
https://doi.org/10.1007/s10586-012-0201-3

Weitere Artikel der Ausgabe 3/2013

Cluster Computing 3/2013 Zur Ausgabe