Reversible computations have been widely studied from the functional point of view and energy consumption. In the literature, several authors have proposed various formalisms (mainly based on process algebras) for assessing the correctness or the equivalence among reversible computations. In this paper we propose the adoption of Markovian stochastic models to assess the quantitative properties of reversible computations. Under some conditions, we show that the notion of time-reversibility for Markov chains can be used to efficiently derive some performance measures of reversible computations. The importance of time-reversibly relies on the fact that, in general, the process’s stationary distribution can be derived efficiently by using numerically stable algorithms. This paper reviews the main results about time-reversible Markov processes and discusses how to apply them to tackle the problem of the quantitative evaluation of reversible computations

Reversible computations have been widely studied from the functional point of view and energy consumption. In the literature, several authors have proposed various formalisms (mainly based on process algebras) for assessing the correctness or the equivalence among reversible computations. In this paper we propose the adoption of Markovian stochastic models to assess the quantitative properties of reversible computations. Under some conditions, we show that the notion of time-reversibility for Markov chains can be used to efficiently derive some performance measures of reversible computations. The importance of time-reversibly relies on the fact that, in general, the process's stationary distribution can be derived efficiently by using numerically stable algorithms. This paper reviews the main results about time-reversible Markov processes and discusses how to apply them to tackle the problem of the quantitative evaluation of reversible computations.

Applying Reversibility Theory for the Performance Evaluation of Reversible Computations

BALSAMO, Maria Simonetta;CAVALLIN, FILIPPO;MARIN, Andrea;ROSSI, Sabina
2016

Abstract

Reversible computations have been widely studied from the functional point of view and energy consumption. In the literature, several authors have proposed various formalisms (mainly based on process algebras) for assessing the correctness or the equivalence among reversible computations. In this paper we propose the adoption of Markovian stochastic models to assess the quantitative properties of reversible computations. Under some conditions, we show that the notion of time-reversibility for Markov chains can be used to efficiently derive some performance measures of reversible computations. The importance of time-reversibly relies on the fact that, in general, the process’s stationary distribution can be derived efficiently by using numerically stable algorithms. This paper reviews the main results about time-reversible Markov processes and discusses how to apply them to tackle the problem of the quantitative evaluation of reversible computations
Proc. of 23rd International Conference on Analytical and Stochastic Modelling Techniques and Applications, ASMTA 2016
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso libero (no vincoli)
Dimensione 309.56 kB
Formato Adobe PDF
309.56 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/3682193
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact