Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Memristor Fundamentals Read chapter Read first chapter

2016 | OriginalPaper | Chapter

8. Memristive Computing for NP-Hard AI Problems

Authors : Ioannis Vourkas, Georgios Ch. Sirakoulis

Published in: Memristor-Based Nanoelectronic Computing Circuits and Architectures

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Reported properties of network configurations of memristors, as presented in Chap. 7, showed that composite memristive systems significantly improve the efficiency of logic operations via massive analog parallelism. The sparse nature of such network-based computations, though, resembles certain operational features and computing capabilities of Cellular Automata (CA), a powerful parallel computational model which leads to scalable hardware (HW) architectures with very high device densities. When CA-based models are implemented in HW, the circuit design reduces to the design of a single cell and the overall layout results regular with exclusively local inter-connections. Moreover, the models are executed fast by exploiting the parallelism of the CA structure. This chapter focuses on a circuit-level CA-inspired approach for in-memory computing schemes using memristors and composite memristive components. A generalized CA cell circuit design methodology is described, which facilitates the implementation of CA-based computing algorithms, exploiting the threshold-type resistance switching behavior of memristors and of multi-state memristive components. Several CA cell example structures are designed and employed in array-like circuit geometries, where computations regarding classic NP-hard problems of various areas of artificial intelligence (AI) take place. The main contribution of this methodology consists in the combination of unconventional computing with CA and the unique circuit properties of memristors, aiming to set off parallel computing capabilities and improve CA-based hardware accelerators for NP-hard AI problems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
previous chapter Networks of Memristors and Memristive Components
Literature
1.
2.
3.
S. Park, J. Park, S. Kim, W. Lee, B.H. Lee, H. Hwang, Programmable analogue circuits with multilevel memristive device. IET Electron Lett 48(22), 1415–1417 (2012)CrossRef
4.
V. Ntinas, I. Vourkas, G. C. Sirakoulis, LC filters with enhanced memristive damping, in IEEE Int. Symp. Circuits Syst. (ISCAS), Lisbon, 2015
5.
M. Di Ventra, Y.V. Pershin, The parallel approach. Nat. Phys. 9, 200–202 (2013)CrossRef
6.
D.B. Strukov, K.K. Likharev, CMOL FPGA: a reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices. Nanotechnology 16(6), 888–900 (2005)CrossRef
7.
A.A. El-Slehdar, A.H. Fouad, A.G. Radwan, Memristor based N-bits redundant binary adder. Microelectron. J. 46(3), 207–213 (2015)CrossRef
8.
Y. Pershin, M. Di Ventra, Practical approach to programmable analog circuits with memristors. IEEE Trans. Circ. Syst. I Regul. Pap. 57(8), 1857–1864 (2010)MathSciNetCrossRef
9.
S. Shin, K. Kim, S. Kang, Memristor applications for programmable analog ICs. IEEE Trans. Nanotechnol. 10(2), 266–274 (2011)CrossRef
10.
E.A. Vittoz, Future of analog in the VLSI environment, in IEEE Int. Symp. Circuits Syst. (ISCAS), New Orleans, LA, USA, 1990
11.
M. Laiho, E. Lehtonen, Arithmetic Operations within Memristor-Based Analog Memory, in 12th International Workshop on Cellular Nanoscale Networks and Their Applications (CNNA), Berkeley, CA, 2010
12.
Y.V. Pershin, M. Di Ventra, Solving mazes with memristors: a massively parallel approach. Phys. Rev. E 84, 046703 (2011)CrossRef
13.
Y. Leblebici, H. Ozdemir, A. Kepkep, U. Cilingiroglu, A compact high-speed (31, 5) parallel counter circuit based on capacitive threshold logic gates. IEEE J. Solid State Circuits 31(8), 1177–1183 (1996)CrossRef
14.
M. Halbach, R. Hoffmann, Implementing cellular automata in FPGA logic, in 18th International Parallel and Distributed Processing Symposium (IPDPS), Santa Fe, New Mexico, 2004
15.
I. Vourkas, G.C. Sirakoulis, On the generalization of composite memristive network structures for computational analog/digital circuits and systems. Microelectron. J. 45(11), 1380–1391 (2014)CrossRef
16.
G. Papandroulidakis, I. Vourkas, N. Vasileiadis, G.C. Sirakoulis, Boolean Logic Operations and Computing Circuits Based on Memristors. IEEE Trans. Circ. Syst. II Express Briefs 61(12), 972–976 (2014)
17.
I. Vourkas, D. Stathis, G.C. Sirakoulis, Massively parallel analog computing: Ariadne’s thread was made of memristors. IEEE Trans. Emerg. Top. Comput. (2015 in press). doi: 10.​1109/​TETC.​2015.​2420353
18.
B. Chopard, Cellular automata modeling of physical systems, in Computational Complexity, ed. by R.A. Meyers (Springer International Publishing, New York, NY, 2012), pp. 407–433CrossRef
19.
S. Wolfram, Cellular Automata and Complexity, Reading (Addison Wesley, MA, 1994)MATH
20.
21.
K. Charalampous, A. Amanatiadis, A. Gasteratos, Efficient Robot Path Planning in the presence of dynamically expanding obstacles, in 10th International conference on Cellular Automata for Research and Industry (ACRI), Santorini island, Greece, 2012
22.
I. Georgoudas, G.C. Sirakoulis, E.M. Skordilis, I. Andreadis, A cellular automaton simulation tool for modelling seismicity in the region of Xanthi. Environ. Model Softw. 22(10), 1455–1464 (2007)CrossRef
23.
I. Georgoudas, P. Kyriakos, G.C. Sirakoulis, I. Andreadis, An FPGA implemented cellular automaton crowd evacuation model inspired by the electrostatic-induced potential fields. Microprocess. Microsyst. 34(7–8), 285–300 (2010)CrossRef
24.
I. Karafyllidis, A model for the prediction of oil slick movement and spreading using cellular automata. Environ. Int. 23(6), 839–850 (1997)CrossRef
25.
I. Karafyllidis, A. Thanailakis, A model for predicting forest fire spreading using cellular automata. Ecol. Model. 99, 87–97 (1997)CrossRef
26.
C. Mizas, G.C. Sirakoulis, V. Mardiris, I. Karafyllidis, N. Glykos, R. Sandaltzopoulos, Reconstruction of DNA sequences using genetic algorithms and cellular automata: towards mutation prediction? Biosystems 92(1), 61–68 (2008)CrossRef
27.
G.C. Sirakoulis, I. Karafyllidis, A. Thanailakis, A cellular automaton model for the effect of population movement on epidemic propagation. Ecol. Model. 133(3), 209–223 (2000)CrossRef
28.
M.-A. Tsompanas, G.C. Sirakoulis, Modeling and hardware implementation of an amoeba-like cellular automaton. Bioinspir. Biomim. 7, 036013 (2012)
29.
I. Vourkas, G.C. Sirakoulis, FPGA based cellular automata for environmental modeling, in 19th IEEE International Conf. Electronics, Circuits, and Systems (ICECS), Seville, Spain, 2012
30.
P. Progias, G.C. Sirakoulis, An FPGA processor for modelling wildfire spread. Math. Comput. Model. 57(5–6), 1436–1452 (2013)MathSciNetCrossRef
31.
J. von Neumann, Theory of self-reproducing automata, Urbana (University of Illinois, IL, 1966)
32.
S. Golzari, M.R. Meybodi, A maze routing algorithm based on two dimensional cellular automata, in 7th International Conference of Cellular Automata for Research and Industry (ACRI), Perpignan, France, 2006
33.
M. Itoh, L.O. Chua, Memristor cellular automata and memristor discrete-time cellular neural networks. Int. J. Bifurcat. Chaos 19(11), 3605–3656 (2009)MathSciNetCrossRefMATH
34.
I. Vourkas, G.C. Sirakoulis, A novel design and modeling paradigm for memristor-based crossbar circuits. IEEE Trans. Nanotechnol. 11(6), 1151–1159 (2012)CrossRef
35.
36.
D. Stathis, I. Vourkas, G.C. Sirakoulis, Shortest path computing using memristor-based circuits and cellular automata, in 11th International Conference on Cellular Automata for Research and Industry (ACRI), Krakow, Poland, 2014
37.
38.
A. Ben-Dor, R. Shamir, Z. Yakhini, Clustering gene expression patterns. J. Comput. Biol. 6(3–4), 281–297 (1999)CrossRef
39.
J. Cong, M.L. Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, in 30th International Design Automation Conference, New York, NY, 2003
40.
V. Spirin and L.A. Mirny, Protein complexes and functional modules in molecular networks. Proc. Nat. Acad. Sci. U.S.A. 100(21), 12123–12128 (2003)
41.
42.
Y.S. Reddy, Solving max-clique using cellular neural network, in 9th International Workshop on Cellular Neural Networks and Their Applications (CNNA), Hsinchu, Taiwan, 2005
43.
D.E. Knuth, The art of computer programming, 2nd ed., vol. 3. Sorting and Searching, Reading, MA: Addison-Wesley (1998)
44.
J.L. Gordillo, J. V. Luna, Parallel sort on a linear array of cellular automata, in IEEE International Conference on Systems, Man, and Cybernetics, Humans, Information and Technology, San Antonio, TX, 1994
45.
I. Vourkas, D. Stathis, G.C. Sirakoulis, Memristor-based parallel sorting approach using one-dimensional cellular automata. IET Electron. Lett. 50(24), 1819–1821 (2014)
46.
R. Lewis, A general-purpose hill-climbing method for order independent minimum grouping problems: a case study in graph colouring and bin packing. Comput. Oper. Res. 36(7), 2295–2310 (2009)MathSciNetCrossRefMATH
47.
E.G. Coffman Jr, J. Csirik, G. Galambos, S. Martello, D. Vigo, Bin packing approximation algorithms: survey and classification, in Handbook of Combinatorial Optimization, ed. by P.M. Pardalos, D. Du, R.L. Graham (Springer International Publishing, New York, NY, 2013), pp. 455–531CrossRef
48.
49.
D. Stathis, I. Vourkas, G.C. Sirakoulis, Solving AI problems with memristors: a case study for optimal “bin packing”, in 18th Panhellenic Conference on Informatics (PCI), Athens, Greece, 2014
50.
51.
G. Dosa, The tight bound of first fit decreasing bin-packing algorithm is FFD(I) ≤ 11/9OPT(I) + 6/9, in Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, ed. B. Chen, M. Paterson, G. Zhang. Lecture Notes in Computer Science, vol. 4614 (Springer, 2007), pp. 1–11
52.
H. Kellerer, U. Pferschy, D. Pisinger, in Knapsack Problems (Springer, Berlin, 2004)
53.
S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementation, New York (John Wiley and Sons, NY, 1990)MATH
54.
55.
Metadata
Title
Memristive Computing for NP-Hard AI Problems
Authors
Ioannis Vourkas
Georgios Ch. Sirakoulis
Copyright Year
2016
Book
Memristor-Based Nanoelectronic Computing Circuits and Architectures

Print ISBN: 978-3-319-22646-0

Electronic ISBN: 978-3-319-22647-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-22647-7_8