Analog Solutions of Discrete Markov Chains via Memristor Crossbars

• Published in: IEEE transactions on circuits and systems. I, Regular papers Regular papers, 2021-12, Vol.68 (12), p.4910-4923
• Main Authors: Zoppo, Gianluca, Korkmaz, Anil, Marrone, Francesco, Palermo, Samuel, Corinto, Fernando, Williams, R. Stanley
• Format: Article
• Language: English
• Subjects: Accuracy; Analog circuits; analog computation; Circuits; Computational modeling; Configuration management; crossbars; discrete Markov chains; Eigenvectors; Electronic circuits; Errors; Feedback; Iterative methods; Linear algebra; Linear systems; Markov analysis; Markov chains; Markov processes; Mathematical models; Matrix algebra; Matrix methods; memristor; Memristors; Multiplication; pagerank; Power consumption; Power efficiency; precision; Precision engineering; Random access memory; Thermal noise
• ISSN: 1549-8328; 1558-0806
• DOI: 10.1109/TCSI.2021.3126477

Problems involving discrete Markov Chains are solved mathematically using matrix methods. Recently, several research groups have demonstrated that matrix-vector multiplication can be performed analytically in a single time step with an electronic circuit that incorporates an open-loop memristor crossbar that is effectively a resistive random-access memory. Ielmini and co-workers have taken this a step further by demonstrating that linear algebraic systems can also be solved in a single time step using similar hardware with feedback. These two approaches can both be applied to Markov chains, in the first case using matrix-vector multiplication to compute successive updates to a discrete Markov process and in the second directly calculating the stationary distribution by solving a constrained eigenvector problem. We present circuit models for open-loop and feedback configurations, and perform detailed analyses that include memristor programming errors, thermal noise sources and element nonidealities in realistic circuit simulations to determine both the precision and accuracy of the analog solutions. We provide mathematical tools to formally describe the trade-offs in the circuit model between power consumption and the magnitude of errors. We compare the two approaches by analyzing Markov chains that lead to two different types of matrices, essentially random and ill-conditioned, and observe that ill-conditioned matrices suffer from significantly larger errors. We compare our analog results to those from digital computations and find a significant power efficiency advantage for the crossbar approach for similar precision results.