A Recursive Partition-Based In-Memory SIMD Computation Scheduler for Memory Footprint Minimization

In-memory computing (IMC) is a technique that enables memory to perform computation so that data transfer between processor and memory can be reduced, improving energy efficiency. A popular IMC design style is based on the single-instruction-multiple-data (SIMD) concept. The SIMD IMC can implement a high-level function by two steps: 1) synthesis and 2) scheduling. The former converts the high-level function into a netlist of the supported primitive logic operations, while the latter determines the execution sequence of the operations. To fully exploit the advantage of SIMD IMC, it is crucial to find a schedule for the given netlist with less memory usage, known as memory footprint (MF). In this work, we first propose an optimal scheduler that can minimize the MF for small netlists. It is at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$8\times $ </tex-math></inline-formula> faster than the state-of-the-art optimal method. For large netlists, we propose a recursive partition-based scheduler consisting of a scheduling-friendly bipartition algorithm and our optimal scheduler. Compared to four state-of-the-art heuristic methods, ours reduces the MF by 54.7%, 48.9%, 44.0%, and 25.5%, respectively, under the same runtime. Our experiments also demonstrate that our scheduler achieves good end-to-end performance when applied to various IMC architectures. The code of our scheduler is made open-source.