World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Shortest Path Computing in Directed Graphs with Weighted Edges Mapped on Random Networks of Memristors

    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. J. Gomez, I. Vourkas and A. Abusleme, 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, ISIGoogle Scholar
    • 2. Knowm Inc. Neuromemristive Artificial Intelligence. [Online]. Available: https://knowm.org [Accessed: October 30, 2019]. Google Scholar
    • 3. Y. Zhang et al., Memristive model for synaptic circuits, IEEE Trans. Circuits Syst. II: Exp. Briefs 64(7) (2017) 767–771. Crossref, ISIGoogle Scholar
    • 4. L. V. Gambuzza et al., Memristor crossbar for adaptive synchronization, IEEE Trans. Circuits Syst. I, Reg. Papers 64(8) (2017) 2124–2133. CrossrefGoogle Scholar
    • 5. MemComputing Inc., Powerful Co-Processors with Speed Like No Other, [Online]. Available: http://memcpu.com [Accessed October 30, 2019]. Google Scholar
    • 6. M. Di Ventra and Y. V. Pershin, The parallel approach, Nature Phys. 9 (2013) 200–202. Crossref, ISIGoogle Scholar
    • 7. S. Stathopoulos et al., Multibit memory operation of metal-oxide bi-layer memristors, Scientific Reports 7 (2017) 17532. Crossref, ISIGoogle Scholar
    • 8. H. Li et al., Resistive RAM-centric computing: Design and modeling methodology, IEEE Trans. Circuits Syst. I, Reg. Papers 64(9) (2017) 2263–2273. CrossrefGoogle Scholar
    • 9. C. Li et al., Analogue signal and image processing with large memristor crossbars, Nature Electronics 1 (2018) 52–59. Crossref, ISIGoogle 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. M. A. Nugent and T. W. Molter, Thermodynamic-RAM technology stack, Int. Journal of Parallel, Emergent and Distributed Systems 33(4) (2018) 430–444. Crossref, ISIGoogle Scholar
    • 12. C. Nakagaki, H. Yamada and A. Toth, Maze-solving by an amoeboid organism, Nature 407 (2000) 470. Crossref, ISIGoogle Scholar
    • 13. Y. V. Pershin and M. Di Ventra, Self-organization and solution of shortest-path optimization problems with memristive networks, Phys. Rev. E 88(1) (2013) 013305. Crossref, ISIGoogle Scholar
    • 14. I. Vourkas, D. Stathis and G. Ch. Sirakoulis, Massively parallel analog computing: Ariadne’s thread was made of memristors, IEEE Trans. on Emerging Topics in Computing 6(1) (2018) 145–155. ISIGoogle Scholar
    • 15. I. Vourkas and G. Ch. Sirakoulis, Networks of memristors and memristive components, in Memristor-Based Nanoelectronic Computing Circuits and Architectures, 1st edn. (Springer Int. Publishing, Switzerland, 2016), pp. 173–198. CrossrefGoogle Scholar
    • 16. Z. Ye, S. H. M. Wu and T. Prodromakis, Computing shortest paths in 2D and 3D memristive networks, in eds. A. AdamatzkyL. Chua, Memristor Networks (Springer, Cham, 2014), pp. 537–552. CrossrefGoogle Scholar
    • 17. C. Fernandez and I. Vourkas, 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. A. Mizrahi et al., Scalable method to find the shortest path in a graph with circuits of memristors, Phys. Rev. Applied 10 (2018) 064035. Crossref, ISIGoogle Scholar
    • 19. Y. Pershin and M. Di Ventra, SPICE model of memristive devices with threshold, Radioengineering 22(2) (2013) 485–489. ISIGoogle Scholar
    • 20. C. Yakopcic et al., Memristor SPICE modeling, in eds. R. KozmaR. E. PinoG. E. Pazienza, Advances in Neuromorphic Memristor Science and Applications, Vol. 4 of Springer Series in Cognitive and Neural Systems (Springer, Dordrecht, 2012), pp. 211–244. CrossrefGoogle Scholar
    • 21. A. Ascoli et al., Memristor model comparison, IEEE Circ. Syst. Mag. 13(2) (2013) 89–105. Crossref, ISIGoogle Scholar
    • 22. D. B. Strukov et al., The missing memristor found, Nature 453 (2008) 80–83. Crossref, ISIGoogle Scholar
    • 23. Z. Biolek, D. Biolek and V. Biolkova, SPICE model of memristor with nonlinear dopant drift, Radioengineering 18(2) (2009) 210–214. ISIGoogle Scholar
    • 24. P. S. Georgiou et al., Window functions and sigmoidal behaviour of memristive systems, Int. J. Circ. Theor. Appl. 44(9) (2016) 1685–1696. Crossref, ISIGoogle Scholar
    • 25. A. Nugent and T. Molter, AHaH computing — From metastable switches to attractors to machine learning, PLoS ONE 9(2) (2014) e85175. Crossref, ISIGoogle Scholar
    • 26. Memristor Models in LTSpice. [Online]. Available: https://knowm.org/memristor-models-in-ltspice/ [Accessed: December 8, 2019]. Google Scholar
    • 27. C. Yakopcic et al., 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, ISIGoogle Scholar
    • 28. A. Sebastian et al., Tutorial: Brain-inspired computing using phase-change memory devices, Journal of Applied Physics 124(11) (2018) 111101. Crossref, ISIGoogle Scholar
    • 29. Z. Sun et al., Solving matrix equations in one step with cross-point resistive arrays, PNAS 116(10) (2019) 4123–4128. Crossref, ISIGoogle 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