This book discusses the main tasks of Design Automation for Field-coupled Nanocomputing (FCN) technologies, in order to enable large-scale composition of elementary building blocks, that obtain correct systems from given function specifications. To this end, a holistic design flow is described, which covers exact and scalable placement & routing, one-pass logic synthesis, novel clocking mechanisms for data synchronization, and formal verification for obtained circuit layouts. Additionally, theoretical groundwork is presented that lays the foundation for any algorithmic consideration in the future. Furthermore, an open-source FCN design framework called fiction, which contains implementations of all proposed techniques, is presented and made publicly available. The approaches discussed in this book address obstacles that have existed since the conceptualization of the FCN paradigm and could not be resolved since then. As a result, this book substantially advances the state of the art in design automation for FCN technologies.
Author(s): Marcel Walter, Robert Wille, Frank Sill Torres, Rolf Drechsler
Publisher: Springer
Year: 2022
Language: English
Pages: 209
City: Cham
Preface
Acknowledgments
Contents
1 Introduction
2 Preliminaries
2.1 Logic Representations
2.1.1 Boolean Functions
2.1.2 Truth Tables
2.1.3 Logic Networks
2.2 Satisfiability Solvers
2.2.1 Boolean Satisfiability (Sat)
2.2.2 Satisfiability Modulo Theories (Smt)
2.3 Field-coupled Nanocomputing (FCN)
2.3.1 Cells
2.3.2 Gates
2.3.3 Clocking
2.3.4 Circuit Layouts
3 Theoretical Groundwork
3.1 FCN Placement and Routing Problem Definition
3.2 Intractability Proofs for FCN Placement and Routing
3.3 Summary and Future Work
4 Exact Placement and Routing
4.1 General Idea
4.2 Formulation as an Smt Problem
4.2.1 Global Synchronization
4.2.2 Predefined Clocking Schemes
4.2.3 Wire Crossings
4.2.4 Border I/O Pins
4.2.5 Secondary Optimization Criteria
4.3 Incremental and Parallel Solving
4.3.1 Incremental Solving
4.3.2 Parallel Solving
4.4 Experimental Results
4.4.1 Implementation and Setup
4.4.2 Quality Comparison Against State-of-the-Art Algorithms
4.4.3 Design Space Exploration
4.4.4 Benefit of Incremental Solving
4.5 Summary and Future Work
5 Scalable Placement and Routing
5.1 The Impact of Logic Network Preprocessing
5.2 Relation to Orthogonal Graph Drawing
5.3 Addressing FCN Design Constraints
5.4 Resulting Algorithm
5.5 Experimental Results
5.5.1 Implementation and Setup
5.5.2 Scalability Comparison Against State-of-the-Art Algorithms
5.6 Summary and Future Work
6 One-Pass Synthesis
6.1 Shortcomings of Two-Step Physical Design
6.2 General Idea
6.3 Formulation as a Sat Problem
6.4 Experimental Results
6.4.1 Implementation and Setup
6.4.2 Quality Comparison Against Placement and Routing
6.4.3 Generating a Design Library
6.4.4 Further Benefits of the One-pass Scheme
6.5 Summary and Future Work
7 Exploiting Clocks for Synchronization
7.1 Global Synchronization Revisited
7.1.1 Combinational Circuits
7.1.2 Sequential Circuits
7.2 Synchronization Elements
7.2.1 Basic Latch
7.2.2 D Latch
7.3 Experimental Results
7.3.1 Implementation and Setup
7.3.2 Relieving Global Synchronization
7.3.3 Adapting Conventional Methods to FCN
7.4 Summary and Future Work
8 Formal Verification
8.1 Problem Discussion and General Idea
8.2 Verification Approach
8.2.1 Miter Structure
8.2.2 Enforcing Proper Synchronization
8.2.3 Resulting Equivalence Checking Process
8.3 Experimental Results
8.3.1 Implementation and Setup
8.3.2 Validation of Physical Design Algorithms
8.4 Summary and Future Work
9 fiction: A Holistic Open-Source Framework
9.1 Related Work on FCN Design Tools
9.1.1 QCADesigner
9.1.2 ToPoliNano and MagCAD
9.1.3 NMLSim
9.1.4 Ropper
9.1.5 SiQAD
9.2 The User's Perspective
9.2.1 The Command-Line Interface
9.2.1.1 Commands
9.2.1.2 Store-Based Architecture
9.2.1.3 Interactive Mode
9.2.1.4 Script Mode
9.2.2 Specifications to Be Realized
9.2.3 Physical Design
9.2.4 Validation and Verification
9.2.5 Scripting for Experimental Evaluations
9.2.6 Full User Documentation
9.2.6.1 The Executable
9.2.6.2 Category: General
9.2.6.3 Category: I/O
9.2.6.4 Category: Logic
9.2.6.5 Category: Physical Design
9.2.6.6 Category: Verification
9.2.6.7 Category: Technology
9.3 The Developer's Perspective
9.3.1 Third-Party Libraries
9.3.2 Architecture and Data Types
9.3.2.1 Commands
9.3.2.2 Logic Networks
9.3.2.3 FCN Layouts
9.3.3 Implementing a Naive Placer
9.4 Summary and Future Work
10 Summary and Conclusions
References
