PhD Dissertation Proposal: Joshua Russell, Algorithms for Threshold-Logic Technology Mapping
Content
Speaker:
Abstract:
The steady progress of CMOS technology under Moore's law has made integrated circuits extraordinarily effective at realizing Boolean functions with ever-improving power, performance, and area (PPA). As conventional scaling approaches fundamental limits, however, emerging nanotechnologies motivate a search not only for new devices, but also for logic paradigms better aligned with their physical operating characteristics. Threshold logic is one such paradigm. Inspired by neuronal computation, a threshold logic gate computes a weighted sum of Boolean inputs and compares the result against a threshold, providing a natural abstraction for device technologies that more readily support weighted accumulation than conventional switching logic.
This dissertation studies the algorithmic construction of threshold-logic circuits for Boolean functions, with emphasis on structural measures of the resulting representations. Because threshold gates are naturally described by weighted sums, multilinear pseudo-Boolean polynomials provide a useful language for analyzing and optimizing such constructions. The first part of the dissertation develops this perspective by characterizing weighted p-norm criteria on pseudo-Boolean polynomials that remain invariant under negation-permutation-negation (NPN) transformations, thereby identifying symmetry conditions that support efficient classification and optimization.
Building on these theoretical foundations, the second part develops algorithms for mapping Boolean networks into neural-network-style threshold-logic circuits, optimizing structural properties such as node count, connection count, and in-degree while preserving functional equivalence and, when required, satisfying depth constraints. This setting is motivated by simulation-oriented applications, such as functional verification, where throughput is the primary objective and structural reductions can directly improve simulation efficiency. The final part will investigate physically realizable mappings under technology constraints, including bounded fan-in, limited weight precision, and device-level nonidealities, with particular attention to memristive implementations. Together, these contributions aim to advance the algorithmic foundations of threshold-logic technology mapping across simulation-oriented and hardware-oriented settings.
Advisor:
Hava Siegelmann