Shortest Path Computing in Directed Graphs with Weighted Edges Mapped on Random Networks of Memristors
Abstract
To accelerate the execution of advanced computing tasks, in-memory computing with resistive memory provides a promising solution. In this context, networks of memristors could be used as parallel computing medium for the solution of complex optimization problems. Lately, the solution of the shortest-path problem (SPP) in a two-dimensional memristive grid has been given wide consideration. Some still open problems in such computing approach concern the time required for the grid to reach to a steady state, and the time required to read the result, stored in the state of a subset of memristors that represent the solution. This paper presents a circuit simulation-based performance assessment of memristor networks as SPP solvers. A previous methodology was extended to support weighted directed graphs. We tried memristor device models with fundamentally different switching behavior to check their suitability for such applications and the impact on the timely detection of the solution. Furthermore, the requirement of binary vs. analog operation of memristors was evaluated. Finally, the memristor network-based computing approach was compared to known algorithmic solutions to the SPP over a large set of random graphs of different sizes and topologies. Our results contribute to the proper development of bio-inspired memristor network-based SPP solvers.
References
- 1. , Exploring memristor multi-level tuning dependencies on the applied pulse properties via a low cost instrumentation setup, IEEE Access 7(1) (2019) 59413–59421. Crossref, ISI, Google Scholar
- 2. Knowm Inc. Neuromemristive Artificial Intelligence. [Online]. Available: https://knowm.org [Accessed: October 30, 2019]. Google Scholar
- 3. , Memristive model for synaptic circuits, IEEE Trans. Circuits Syst. II: Exp. Briefs 64(7) (2017) 767–771. Crossref, ISI, Google Scholar
- 4. , Memristor crossbar for adaptive synchronization, IEEE Trans. Circuits Syst. I, Reg. Papers 64(8) (2017) 2124–2133. Crossref, Google Scholar
- 5. MemComputing Inc., Powerful Co-Processors with Speed Like No Other, [Online]. Available: http://memcpu.com [Accessed October 30, 2019]. Google Scholar
- 6. , The parallel approach, Nature Phys. 9 (2013) 200–202. Crossref, ISI, Google Scholar
- 7. , Multibit memory operation of metal-oxide bi-layer memristors, Scientific Reports 7 (2017) 17532. Crossref, ISI, Google Scholar
- 8. , Resistive RAM-centric computing: Design and modeling methodology, IEEE Trans. Circuits Syst. I, Reg. Papers 64(9) (2017) 2263–2273. Crossref, Google Scholar
- 9. , Analogue signal and image processing with large memristor crossbars, Nature Electronics 1 (2018) 52–59. Crossref, ISI, Google Scholar
- 10. F. Sheldon et al., Stress-testing memcomputing on hard combinatorial optimization problems, IEEE Trans. on Neural Networks and Learning Systems (2019), in press. Google Scholar
- 11. , Thermodynamic-RAM technology stack, Int. Journal of Parallel, Emergent and Distributed Systems 33(4) (2018) 430–444. Crossref, ISI, Google Scholar
- 12. , Maze-solving by an amoeboid organism, Nature 407 (2000) 470. Crossref, ISI, Google Scholar
- 13. , Self-organization and solution of shortest-path optimization problems with memristive networks, Phys. Rev. E 88(1) (2013) 013305. Crossref, ISI, Google Scholar
- 14. , Massively parallel analog computing: Ariadne’s thread was made of memristors, IEEE Trans. on Emerging Topics in Computing 6(1) (2018) 145–155. ISI, Google Scholar
- 15. ,
Networks of memristors and memristive components , in Memristor-Based Nanoelectronic Computing Circuits and Architectures, 1st edn. (Springer Int. Publishing, Switzerland, 2016), pp. 173–198. Crossref, Google Scholar - 16. ,
Computing shortest paths in 2D and 3D memristive networks , in eds. A. AdamatzkyL. Chua, Memristor Networks (Springer, Cham, 2014), pp. 537–552. Crossref, Google Scholar - 17. , Performance assessment of memristor networks as shortest path problem solvers, in 2020 IEEE Int. Symposium on Circuits & Systems (ISCAS),
Seville, Spain ,May 17–20 . Google Scholar - 18. , Scalable method to find the shortest path in a graph with circuits of memristors, Phys. Rev. Applied 10 (2018) 064035. Crossref, ISI, Google Scholar
- 19. , SPICE model of memristive devices with threshold, Radioengineering 22(2) (2013) 485–489. ISI, Google Scholar
- 20. ,
Memristor SPICE modeling , in eds. R. KozmaR. E. PinoG. E. Pazienza, Advances in Neuromorphic Memristor Science and Applications, Vol. 4 ofSpringer Series in Cognitive and Neural Systems (Springer, Dordrecht, 2012), pp. 211–244. Crossref, Google Scholar - 21. , Memristor model comparison, IEEE Circ. Syst. Mag. 13(2) (2013) 89–105. Crossref, ISI, Google Scholar
- 22. , The missing memristor found, Nature 453 (2008) 80–83. Crossref, ISI, Google Scholar
- 23. , SPICE model of memristor with nonlinear dopant drift, Radioengineering 18(2) (2009) 210–214. ISI, Google Scholar
- 24. , Window functions and sigmoidal behaviour of memristive systems, Int. J. Circ. Theor. Appl. 44(9) (2016) 1685–1696. Crossref, ISI, Google Scholar
- 25. , AHaH computing — From metastable switches to attractors to machine learning, PLoS ONE 9(2) (2014) e85175. Crossref, ISI, Google Scholar
- 26. Memristor Models in LTSpice. [Online]. Available: https://knowm.org/memristor-models-in-ltspice/ [Accessed: December 8, 2019]. Google Scholar
- 27. , Generalized memristive device spice model and its application in circuit design, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32(8) (2013) 1201–1214. Crossref, ISI, Google Scholar
- 28. , Tutorial: Brain-inspired computing using phase-change memory devices, Journal of Applied Physics 124(11) (2018) 111101. Crossref, ISI, Google Scholar
- 29. , Solving matrix equations in one step with cross-point resistive arrays, PNAS 116(10) (2019) 4123–4128. Crossref, ISI, Google Scholar
- 30. Memryx: Reconfigurable in-memory computing chips with unparalleled energy efficiency and compute density. [Online]. Available: https://www.memryx.com [Accessed: October 30, 2019]. Google Scholar


