publication . Conference object . 2012

A Model of Parallel Deterministic Real-Time Computation

Matthieu Lemerre; Emmanuel Ohayon;
Open Access English
  • Published: 01 Jan 2012
  • Publisher: HAL CCSD
  • Country: France
Abstract
International audience; This paper presents a model of computation based on real-time constraints and asynchronous message passing, and proves a sufficient and necessary condition for this model to be deterministic. The model is then extended with deterministic error handling, meaning that the same error yields the same consequences on the system. We consider two different error occurrence models: at a specific time, or at a specific instruction, and conclude that the "error at a specific time" model is more suitable for practical use. We proceed by presenting a concrete implementation of this model in the PharOS real-time system.
Persistent Identifiers
Subjects
free text keywords: [INFO]Computer Science [cs], Computation, Theoretical computer science, Specific time, Model of computation, Parallel computing, Determinism, Parallel processing, Message passing, Computer science, Asynchronous communication
Download fromView all 6 versions
Open Access
ZENODO
Conference object . 2012
Provider: ZENODO
null
Hal-Diderot
Conference object . 2012
Provider: Hal-Diderot
Restricted
http://xplorestaging.ieee.org/...
Conference object . 2013
Provider: Crossref
25 references, page 1 of 2

[1] M. Lemerre, E. Ohayon, D. Chabrol, M. Jan, and M. Jacques, “Method and tools for mixed-criticality real-time applications within PharOS,” in Proceedings of the 14th International ISORCW Symposium (AMICS Workshop). IEEE, 2011, pp. 41-48.

[2] C. Aussague`s, C. Cordonnier, M. Aji, V. David, and J. Delcoigne, “OASIS: a new way to design safety critical applications,” in 21st IFAC/IFIP Workshop on Real-Time Programming (WRTP'96), Gramado, Brazil, 1996.

[3] R. Bocchino Jr, V. Adve, S. Adve, and M. Snir, “Parallel programming must be deterministic by default,” in Proceedings of the First USENIX conference on Hot topics in parallelism. USENIX Association, 2009, pp. 4-4. [OpenAIRE]

[4] E. Lee, “The problem with threads,” IEEE Transactions on Computers, vol. 39, no. 5, pp. 33 - 42, 2006.

[5] H. Kopetz and G. Bauer, “The time-triggered architecture,” IEEE Special Issue on Modeling and Design of Embedded Software, January 2003. [OpenAIRE]

[6] M. Lemerre, V. David, C. Aussague`s, and G. Vidal-Naquet, “An introduction to time-constrained automata,” EPTCS: Proceedings of the 3rd Interaction and Concurrency Experience Workshop (ICE'10), 2010.

[7] T. LeBlanc and J. Mellor-Crummey, “Debugging parallel programs with instant replay,” IEEE Transactions on Computers, vol. 100, no. 4, pp. 471-482, 1987.

[8] P. Montesinos, L. Ceze, and J. Torrellas, “DeLorean: Recording and deterministically replaying shared-memory multiprocessor execution efficiently,” in Computer Architecture, 2008. ISCA'08. 35th International Symposium on. IEEE, 2008, pp. 289-300.

[9] G. Dunlap, D. Lucchetti, M. Fetterman, and P. Chen, “Execution replay of multiprocessor virtual machines,” in Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. ACM, 2008, pp. 121-130.

[10] A. Joshi, S. King, G. Dunlap, and P. Chen, “Detecting past and present intrusions through vulnerability-specific predicates,” ACM SIGOPS Operating Systems Review, vol. 39, no. 5, pp. 91-104, 2005.

[11] J. Devietti, B. Lucia, L. Ceze, and M. Oskin, “DMP: deterministic shared memory multiprocessing,” in ACM Sigplan Notices, vol. 44, no. 3, 2009, pp. 85-96.

[12] A. Aviram, S. Weng, S. Hu, and B. Ford, “Efficient systemenforced deterministic parallelism,” in 9th OSDI. USENIX Association, 2010, pp. 1-16.

[13] T. Bergan, N. Hunt, L. Ceze, and S. Gribble, “Deterministic process groups in dOS,” 9th OSDI, 2010.

[14] M. Olszewski, J. Ansel, and S. Amarasinghe, “Kendo: efficient deterministic multithreading in software,” in ACM Sigplan Notices, vol. 44, no. 3. ACM, 2009, pp. 97-108.

[15] H. Cui, J. Wu, C. Tsai, and J. Yang, “Stable deterministic multithreading through schedule memoization,” 9th OSDI, 2010.

25 references, page 1 of 2
Abstract
International audience; This paper presents a model of computation based on real-time constraints and asynchronous message passing, and proves a sufficient and necessary condition for this model to be deterministic. The model is then extended with deterministic error handling, meaning that the same error yields the same consequences on the system. We consider two different error occurrence models: at a specific time, or at a specific instruction, and conclude that the "error at a specific time" model is more suitable for practical use. We proceed by presenting a concrete implementation of this model in the PharOS real-time system.
Persistent Identifiers
Subjects
free text keywords: [INFO]Computer Science [cs], Computation, Theoretical computer science, Specific time, Model of computation, Parallel computing, Determinism, Parallel processing, Message passing, Computer science, Asynchronous communication
Download fromView all 6 versions
Open Access
ZENODO
Conference object . 2012
Provider: ZENODO
null
Hal-Diderot
Conference object . 2012
Provider: Hal-Diderot
Restricted
http://xplorestaging.ieee.org/...
Conference object . 2013
Provider: Crossref
25 references, page 1 of 2

[1] M. Lemerre, E. Ohayon, D. Chabrol, M. Jan, and M. Jacques, “Method and tools for mixed-criticality real-time applications within PharOS,” in Proceedings of the 14th International ISORCW Symposium (AMICS Workshop). IEEE, 2011, pp. 41-48.

[2] C. Aussague`s, C. Cordonnier, M. Aji, V. David, and J. Delcoigne, “OASIS: a new way to design safety critical applications,” in 21st IFAC/IFIP Workshop on Real-Time Programming (WRTP'96), Gramado, Brazil, 1996.

[3] R. Bocchino Jr, V. Adve, S. Adve, and M. Snir, “Parallel programming must be deterministic by default,” in Proceedings of the First USENIX conference on Hot topics in parallelism. USENIX Association, 2009, pp. 4-4. [OpenAIRE]

[4] E. Lee, “The problem with threads,” IEEE Transactions on Computers, vol. 39, no. 5, pp. 33 - 42, 2006.

[5] H. Kopetz and G. Bauer, “The time-triggered architecture,” IEEE Special Issue on Modeling and Design of Embedded Software, January 2003. [OpenAIRE]

[6] M. Lemerre, V. David, C. Aussague`s, and G. Vidal-Naquet, “An introduction to time-constrained automata,” EPTCS: Proceedings of the 3rd Interaction and Concurrency Experience Workshop (ICE'10), 2010.

[7] T. LeBlanc and J. Mellor-Crummey, “Debugging parallel programs with instant replay,” IEEE Transactions on Computers, vol. 100, no. 4, pp. 471-482, 1987.

[8] P. Montesinos, L. Ceze, and J. Torrellas, “DeLorean: Recording and deterministically replaying shared-memory multiprocessor execution efficiently,” in Computer Architecture, 2008. ISCA'08. 35th International Symposium on. IEEE, 2008, pp. 289-300.

[9] G. Dunlap, D. Lucchetti, M. Fetterman, and P. Chen, “Execution replay of multiprocessor virtual machines,” in Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. ACM, 2008, pp. 121-130.

[10] A. Joshi, S. King, G. Dunlap, and P. Chen, “Detecting past and present intrusions through vulnerability-specific predicates,” ACM SIGOPS Operating Systems Review, vol. 39, no. 5, pp. 91-104, 2005.

[11] J. Devietti, B. Lucia, L. Ceze, and M. Oskin, “DMP: deterministic shared memory multiprocessing,” in ACM Sigplan Notices, vol. 44, no. 3, 2009, pp. 85-96.

[12] A. Aviram, S. Weng, S. Hu, and B. Ford, “Efficient systemenforced deterministic parallelism,” in 9th OSDI. USENIX Association, 2010, pp. 1-16.

[13] T. Bergan, N. Hunt, L. Ceze, and S. Gribble, “Deterministic process groups in dOS,” 9th OSDI, 2010.

[14] M. Olszewski, J. Ansel, and S. Amarasinghe, “Kendo: efficient deterministic multithreading in software,” in ACM Sigplan Notices, vol. 44, no. 3. ACM, 2009, pp. 97-108.

[15] H. Cui, J. Wu, C. Tsai, and J. Yang, “Stable deterministic multithreading through schedule memoization,” 9th OSDI, 2010.

25 references, page 1 of 2
Any information missing or wrong?Report an Issue