PhD Thesis Defense: Joshua Russell, Threshold Logic Technology Mapping and Optimization
Content
Speaker:
Abstract:
The steady progress of complementary metal-oxide-semiconductor (CMOS) technology under Moore's law has made integrated circuits extraordinarily effective at realizing Boolean functions with ever-improving power, performance, and area. 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 algorithmic methods for constructing and optimizing threshold-logic circuits, with emphasis on structural measures that affect simulation efficiency, mapping quality, and physical realizability. The first part considers polynomial representations of Boolean functions that support a two-level view of threshold-logic optimization. It characterizes when weighted-norm objectives for these representations are invariant under negation-permutation-negation (NPN) transformations. This identifies when optimized polynomial threshold representations can be transferred among NPN-equivalent Boolean functions while preserving the weighted-norm objective.
The second part develops algorithms for mapping Boolean networks into neural-network-style threshold-logic circuits. These algorithms optimize neuron count, connection count, and fanin under depth constraints while preserving functional equivalence. This setting is motivated by simulation-oriented applications in which structural reductions can improve throughput.
The third part introduces a theoretical and algorithmic framework for technology mapping based on the generalized notion of a supergate. The framework encompasses recent and well-known mapping algorithms as special cases, including methods for standard-cell ASICs, lookup-table-based FPGAs, and emerging nanotechnologies. It is used to design delay-oriented mapping algorithms for fanin-bounded threshold-logic circuits, exposing practical tradeoffs among optimization objectives and computational resources.
The final part studies physically realizable mappings for memristive implementations of threshold logic. Under assumptions about device programmability and noise, it derives sufficient conditions for robust functional equivalence and incorporates these conditions into technology mapping. It is shown experimentally that improved device parameters can expand the space of robust threshold-logic structures and improve targeted mapping objectives. Together, these contributions advance threshold-logic technology mapping across theoretical, simulation-oriented, and hardware-oriented settings.
Advisor:
Hava Siegelmann