Background:
Processing-in-memory (PIM) solutions unite computation and memory to overcome the memory-wall, while also introducing ample opportunities for high-throughput operations. Memristive processing-in-memory is based on the memristor: an emerging fundamental device that is capable of both storage and logic by representing binary information through resistance. Efficient utilization of processing-in-memory requires rethinking many aspects of computing systems, including novel algorithmic techniques that can utilize the high-throughput of PIM.
Algorithmic Paradigm:
A memristive crossbar array consist of a grid of n x n memristors, each storing a single bit. Stateful logic techniques (e.g., MAGIC [1]) support row/column bit-wise operations in O(1) time complexity. For example, storing the bitwise NOR of two columns of binary data in a third column, in one clock cycle. Essentially, vectored operations across rows and columns are performed in constant time. Creative techniques are required to efficiently utilize this capability.
Recent works demonstrate massive improvement to a variety of algorithms, when stateful logic is utilized efficiently. For example, general-purpose matrix multiplication is performed in O(n2) time complexity rather than O(n2.807) with traditional solutions (Strassen’s algorithm).
Project:
In this project, you choose a theoretical problem that you would like to explore, and demonstrate an efficient solution based on stateful logic. Hopefully you will invent various creative algorithmic techniques, and present massive improvements over traditional solutions.
Prerequisites:
Data Structures 1 (234218) and Algorithms 1 (234247) or
Introduction to Data Structures and Algorithms (044268)
Theoretical background is encouraged.
Supervisor:
Orian Leitersdorf (orianl@campus.technion.ac.il)
References:
[1] S. Kvatinsky et al., “MAGIC—Memristor-Aided Logic,” in IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 61, no. 11, pp. 895-899, Nov. 2014, doi: 10.1109/TCSII.2014.2357292.