Recursive Algorithms in Memristive Logic Arrays

In memristive stateful logic memristors store logic values as their memristance states and perform logical operations on them. This form of logic has been studied intensively since it was first empirically demonstrated in the work of Borghetti , 2010. It has been previously noted that substantial parallelism in stateful computation is required to make this form of logic competetive with conventional logic computing paradigms. In this work we show how a certain class of vectorized recursive algorithms can be computed in a semiconductor/memristor hybrid array structure. This class of algorithms allows efficient computation of many practically important vector operations; examples considered in this paper include the binary sum of vectors, the parity of a vector, and the Hamming weight of a vector. We present theoretical analysis of the time and space complexity of this class of operations, and show examples of this computing method using circuit-level simulations. We also discuss possible applications of these operations in massively parallel memristive array computing.