Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog.

v0.5.0 - 2023-03-30

Fiction is a way to challenge the status quo and to push the boundaries of conventional thinking. — unknown

Added

  • Technology:

    • Support for the SiDB Bestagon gate library, a standard-tile library for the SiDB technology based on hexagonal grids. Many thanks to Samuel Sze Hang Ng for the collaboration on the paper!

    • Support for charge states of SiDBs

  • Algorithms:
    • Electrostatic ground state simulation for SiDB cell-level layouts

      • Exhaustive simulation

      • Heuristic simulation

      • Energy calculations

    • Four established path-finding algorithms on arbitrary layouts with arbitrary clocking schemes

      • Recursive enumeration of all possible paths

      • A* for the shortest path

      • Jump Point Search (JPS) for the shortest path (proof-of-concept)

      • k shortest paths via Yen’s algorithm

    • Distance functions and functors for layouts

      • Manhattan distance

      • Euclidean distance

      • A* distance

    • Cost functions and functors for layouts

      • Unit cost

      • Random cost

    • Graph coloring with a selection of SAT solvers or heuristic algorithms

    • Efficient multi-path signal routing on gate-level layouts (based on this paper)

    • Specify a black list of tiles and gates to avoid in exact physical design

    • Generic function optimizer based on simulated annealing

  • Data types:

    • Obstruction layout to represent obstacles in a layout

    • Edge intersection graphs from enumerated routing paths

    • Charge distribution surface for SiDB layouts

    • Coordinate type siqad::coord_t representing signed SiDB coordinates as represented in SiQAD

  • I/O:

    • Molecular FCN support in the QLL writer for MagCAD and SCERPA (many thanks to Giuliana Beretta!)

    • SQD reader for the SiDB technology

  • Clocking Schemes:

    • CFE

  • Traits:

    • has_*_technology traits to check for specific cell technologies of layouts and libraries

  • Utils:

    • Routing utils

    • STL extensions

    • Truth table utils

  • Libraries:

    • phmap for faster hash maps (applied in many core data structures for performance reasons)

    • TinyXML2 for XML parsing

  • Continuous integration:

    • clang-tidy workflow for static code analysis

    • ClangFormat workflow for automatic code formatting

    • Release Drafter workflow to keep an up-to-date changelog for the next release

    • Docker image workflow to build Docker images for the latest release

  • Build and documentation:

    • Automatic linking with TBB for parallel algorithms

    • Dependabot to automatically keep the dependencies up-to-date

    • CodeQL to automatically scan the code for security vulnerabilities

    • GitHub templates for issues and pull requests

Changed

  • CLI:

    • Split exact’s and onepass’ parameter upper_bound into upper_x and upper_y

  • Clocking schemes:

    • Renamed ESP to ESR

  • Libraries:

    • Updated all libraries to the latest versions

    • Moved to the upstream version of Catch2 v3

  • Continuous integration:

    • Updated CI runners to the latest versions

    • Setup Z3 via a designated action. Many thanks to Lukas Burgholzer for his support!

    • Enabled Ccache for faster compilation in CIs

    • Activated experiments in CI builds to ensure that they are building correctly

    • Run CI only when relevant files have changed

    • Switched to single-threaded builds in CI to avoid out-of-memory issues

  • Build and documentation:

    • Refactored the CMake buildsystem

    • Improved the README and the documentation

Fixed

  • Compilation issues when a certain header was included multiple times

  • Exclusion of experiment compilation if Z3 is not found

  • Wrong DOT drawer in write_dot_layout

  • MSVC compilation issues

  • Performance issues with foreach_* functions on layout types

  • Performance issues with std::string where std::string_view was sufficient

  • Regex in the FQCA reader

  • Issue with clear_tile that would lose track of PI and PO count

  • Duplicate crossing cells in the iNML ToPoliNano library

  • Several I/O issues in the CLI

  • Excess template parameter in the restore_names utility function

  • Errors with the CMake build system if IPO was enabled through multiple sources

  • Linker errors and CMake name collisions

  • Warnings detected by CodeQL

Removed

  • LGTM badge as the service is no longer available

v0.4.0 - 2022-01-27

There are people who think that things that happen in fiction do not really happen. These people are wrong. — Neil Gaiman

Added

  • Technology:

    • Support for the Silicon Dangling Bond (SiDB) technology with SiQAD tool support. Many thanks to Samuel Sze Hang Ng for the collaboration!

    • Support for 3D QCA layouts with QCA-STACK tool support. Many thanks to Willem Lambooy for the collaboration!

  • Data types:

    • New coordinate type cube::coord_t representing signed cube coordinates

    • New layout type hexagonal_layout representing a grid of hexagonal tiles

    • New layout type shifted_cartesian_layout replacing the offset parameter of legacy fcn_layout

    • New layout type synchronization_element_layout replacing the clock_latch member of legacy fcn_layout

    • New layout types cartesian_layout, tile_based_layout, gate_level_layout, and cell_level_layout replacing various aspects of legacy fcn_layout, fcn_gate_layout, and fcn_cell_layout types

    • All layout types can be layered to expand their functionality, e.g., a clocked Cartesian layout type with offset coordinates results from clocked_layout<cartesian_layout<offset::ucoord_t>>

    • Support for arbitrary mockturtle logic networks as layout specifications

    • New logic network type technology_network replacing legacy logic_network type

    • New view types that can be layered on top of networks reverse_topo_view and out_of_place_edge_color_view refactoring aspects from the ortho algorithm out into their own data structures

  • Traits:

    • Added a trait system that can identify the appropriateness of a data type for the usage as parameter to an algorithm at compile time

    • Many traits are provided out-of-the-box like checks for the existence of certain functions or members, e.g., is_clocked_layout or has_foreach_tile

    • Some pre-defined types used within the CLI can be found in the types.hpp file

  • Algorithms:

    • convert_network as an extension of mockturtle::cleanup_dangling to convert between extended logic network types

    • apply_gate_library to provide an interface that generates any cell-level layout type from any gate-level layout type via the application of any gate library type

  • Clocking schemes:

    • Columnar

    • Row-based

    • ESP

  • Visualization:

    • Custom write_dot_layout function that creates Graphviz DOT files from gate-level layouts together with custom DOT drawers for various layout types

    • Custom technology_dot_drawer as an extension to mockturtle::gate_dot_drawer that supports more gate types

  • CLI:

    • Command map for technology mapping of logic networks using a given set of gate functions. Many thanks to Alessandro Tempia Calvino for his support!

    • Command sqd to write SiDB layouts to SiQAD files

    • Command qll to write iNML layouts to ToPoliNano & MagCAD files (complements the existing qcc command)

    • Command fqca to write QCA layouts to QCA-STACK files

    • Command blif to write logic networks to BLIF files

    • Added option --hex to exact and ortho instructing the algorithms to create a hexagonal layout instead of a Cartesian one. The option expects a hexagonal orientation that has to be one of the following odd_row, even_row, odd_column, or even_column

  • Utility:

    • Added utility functions for networks, layouts, placement, names, arrays, ranges, and hashing to the utils folder

  • Build and documentation:

    • Option to disable the CLI to be built

    • Option to enable tests to be built

    • Option to enable experiments to be built

    • Code coverage CI via Codecov

    • Online documentation via Readthedocs

    • Code quality analysis via LGTM. Many thanks to Stefan Hillmich for his support!

Changed

  • Architecture:
    • Reworked fiction into a platform that offers

      1. a header-only template library for use in external projects,

      2. a CLI built upon said library that provides the established functionality (plus the new additions),

      3. a framework for experiments that allows to quickly prototype ideas and compile them as stand-alone binaries built with fiction

    • Reworked the CMake build system to be simpler to use, yet more capable

    • Templatized all algorithms and data structures and switched to a trait-based API system. This allows for far more flexible system and the support of any type that implements certain functionality via duck typing

  • CLI:

    • Command read can now also parse BLIF and FQCA files

    • Command read can now create various types of logic networks from parsing input files. A flag determines which one to create, e.g., --aig, --mig, or --xag

    • Command gates supports more gate types now including the 3-input gates presented in Marakkalage et al.

    • exact --clock_latches/-l has been renamed to exact --sync_elems/-e

    • A technology flag --topolinano has been added to exact instructing it to respect ToPoliNano’s requirements for iNML layouts

    • The ToPoliNano clocking scheme has been renamed to Columnar

  • Continuous Integration:

    • Moved from Travis CI to GitHub Actions with CI builds and testing under ubuntu, macOS, and Windows

  • Build & Documentation:

    • Z3 is now an optional dependency that can be found automatically by fiction when -DFICTION_Z3=ON is passed to cmake. If it is not found, some algorithms are simply excluded from compilation

    • Trimmed README in favor of Readthedocs

Fixed

  • Compilation issues under Windows

  • SEGFAULT when using ortho under rare circumstances

Removed

  • Third-party dependencies:

    • Boost

    • Z3 (now optional)

    • cppitertools

  • Data types:

    • fcn_gate_layout (replaced with the is_gate_level_layout trait)

    • fcn_cell_layout (replaced with the is_cell_level_layout trait)

    • logic_network (replaced with the mockturtle::is_network_type trait)

  • CLI:

    • ortho -b flag because routing border I/Os is the default behavior now

v0.3.2 - 2021-01-06

Sometimes fiction is more easily understood than true events. — Young-ha Kim

Added

  • Command onepass for a combined SAT-based logic synthesis and physical design using Mugen. Thanks to Winston Haaswijk for cooperating with us on this project!

  • SVG output for irregular (cell-based) clocked fcn_cell_layouts (thanks to Sophia Kuhn!)

  • csv_writer for conveniently formatting experiments’ results

  • tt_reader for reading truth tables from a file format used by Alan Mishchenko

Changed

  • exact --asynchronous/-a has been renamed to exact --async/-a and exact --asynchronous_max/-A has been renamed to exact --async_max

  • outsourced Verilog and AIGER file handling into a distinct network_reader class so that it can be used in custom experiments

Fixed

  • Docker build that broke down due to updates to mockturtle and bill

v0.3.1 - 2020-06-04

There is no doubt fiction makes a better job of the truth. — Doris Lessing

Added

  • Command equiv for logical and delay equivalence checking of fcn_gate_layouts against a specification

  • Command energy to print and log energy dissipation of current fcn_gate_layout based on a physical model for the QCA-ONE library

  • Command area to print and log area usage in nm²

  • Parameter -a and flag -A to enable asynchronous parallelism for exact

  • Flag --minimize_wires/-w for exact to compute the minimum amount of wire segments needed

  • Flag -s for show -n for less detailed visualization of logic_network objects

  • Dockerfile and instructions for how to create an image using Docker (thanks to Mario Kneidinger!)

  • CMake option to toggle animated progress bars on command line

Changed

  • exact has been completely reworked to utilize true incremental SMT solving without push/pop mechanics (thanks to Alan Mishchenko for the inspiration!)

  • exact --artificial_latches/-a has been renamed to exact --clock_latches/-l

  • exact -m has been renamed to exact -c

  • Standard resolves for clocking scheme names to their commonly used variants, e.g., 2DDWave becomes 2DDWave4

  • Energy dissipation will no longer be logged using command ps -g; use new command energy instead

  • Command cell can be found in command class Technology now

  • Increased font size of clock numbers in SVG files by 2pt for better readability

  • Changed constructor parameter types for core data structures (network and layouts)

  • Changed std::size_t to fixed-size data types in lots of places

  • Use library caching for Travis builds to speed up build time

  • Moved to the latest releases of all libraries

Fixed

  • Python detection in CMake under different versions

  • Runtime logging in exact

  • Performance issues in ortho

  • SEGFAULTS caused by ortho on large networks when compiling with gcc

  • ortho -b losing bent wire connections

  • fcn_layout::random_face‘s index to coordinate mapping again, but for real now (thanks to Till Schlechtweg!)

  • logic_networks are deep-copied for each physical design call now to secure them from external changes

  • Gates and wires without directions assigned are mapped to standard rotations using QCA-ONE library now

  • Rotation issues with border gate-pin I/Os using QCA-ONE library

  • 3-output fan-outs are correctly printed as fan-outs when using print -g now

  • Testing ofstream‘s for is_open in writers now (thanks to DeepCode!)

  • Several compiler issues under MacOS and Windows (thanks to Umberto Garlando and Fabrizio Riente for pointing them out!)

  • Z3 build script error under Unix with CMake version <= 3.12.0

  • Z3 linking on MacOS (thanks to Daniel Staack!)

  • bibTeX citation information correctly handles last names and arXiv prefixes now

Removed

  • exact --limit_crossings/-c and exact --limit_wires/-w as they have been replaced by respective optimization flags

  • Legends in print -g/-c

v0.3.0 - 2019-11-22

Sometimes, fiction was so powerful that it even had reverberations in the real world. — Delphine de Vigan

Added

  • Support for iNML technology using ToPoliNano‘s gate library and clocking scheme. Thanks to Umberto Garlando for cooperating with us on this project!

  • Support for vertically shifted fcn_layouts to emulate column-based clocking schemes

  • Enhanced logic_network by incorporating mockturtle for logic representation

  • Truth table store (mnemonic -t) and command tt. Thanks to Mathias Soeken for granting permission to use code from CirKit!

  • Command simulate to compute truth_tables for logic_network and fcn_gate_layout objects. Thanks to Mathias Soeken for granting permission to use code from CirKit!

  • Command akers to perform Akers’ Majority synthesis to generate a logic_network from a truth_table

  • Command random to generate random logic_network objects

  • Command check to verify structural integrity of designed fcn_gate_layout objects

  • Command gates to list gate counts for each vertex type in the current logic_network

  • Command fanouts to substitute high-degree inputs into fan-out vertices in logic_networks using a given strategy

  • Command balance to subdivide logic_network edges to equalize path lengths by inserting auxiliary wire vertices

  • Command qcc to write iNML cell_layouts to component files readable by ToPoliNano and MagCAD

  • Capability to enforce straight inverter gates in exact with flag -n

  • Capability to minimize the number of used crossing tiles in exact with flag -m

  • Capability to parse AIGER (*.aig) files using read

  • Parameter -b for ortho

  • Progress bars for exact and ortho

  • show -n to display logic_network objects

  • Several convenience functions in the core data structures for easier access

  • An overview paper and a poster about the features of fiction. Please find citation information in the publication list

Changed

  • Moved to C++17

  • Moved to version 1.0 of cppitertools

  • Included latest updates for alice

  • Switched logic_network‘s CLI mnemonic to -n as it is no longer reserved by alice

  • Renamed pi/po_count to num_pis/pos

  • read does no longer substitute fan-outs automatically, exact and ortho do it instead if the user did not call fanouts

  • exact --path_discrepancy/-p has been renamed to exact --desynchronize/-d to express its use case better

  • exact --timeout/-t expects its parameter in seconds instead of milliseconds now

  • exact --fixed_size/-f expects its own parameter instead of using --upper_bound‘s one

  • Renamed version.h to version_info.h

  • Renamed Placement & Routing to Physical Design where appropriate to match the documentation

Fixed

  • Segfault when using ortho -i with certain compilers in release mode

  • Missing input ports for 3-output fan-out gates in QCA-ONE library

  • Wire vertices not handled properly by QCA-ONE library

  • Wrong clocking look-up for BANCS clocking in fcn_cell_layout

  • Tile directions when assigning and dissociating multiple edges

  • fcn_layout::random_face‘s index to coordinate mapping (thanks to Till Schlechtweg!)

  • Format issues with benchmark files

  • Constant outputs of some benchmark files

  • Additionally, there are several performance improvements in core data structures and algorithms

Removed

  • Submodule lorina as it is included in mockturtle

  • verilog_parser.h as mockturtle comes with its own one

  • print -n as it is replaced by show -n

  • operation::BUF; use operation::W instead

  • operation::CONST0, operation::CONST1, and operation::XOR

  • operator[x][y][z] for fcn_layouts as it was slow and therefore not used; use face/tile/cell{x,y,z} instead

v0.2.1 - 2019-05-02

Fiction is art and art is the triumph over chaos. — John Cheever

Added

  • Support for BANCS clocking and integration in exact

  • Name strings for fcn_clocking_scheme objects and corresponding name-based look-up

  • Version and build information accessible within the code by including util/version.h

  • Parameter -i for command ortho

  • shortcuts.fs with predefined flows

  • benchmarks/MAJ/ folder with some TOY benchmarks using MAJ gates

Changed

  • Calls to exact -s now need to name the desired clocking, e.g. exact -s use (case insensitive)

  • incoming/outgoing_information_flow_tiles have been renamed to incoming/outgoing_data_flow and handle multi wires now

  • Renamed diagonal clocking schemes to 2DDWAVE and gave proper credit

  • More verbose error messages

Fixed

  • TP calculation for layouts without designated I/O pins (thanks to Mario Kneidinger!)

  • I/O port orientation of PI/PO gates using QCA-ONE library

  • Usage of non-PI/PO MAJ gates in QCA-ONE library

  • Visualization of clock latches in show -c (thanks to Sophia Kuhn!)

  • Multi direction assignment to wires and gates in exact leading to physically impossible layouts

  • shrink_to_fit in fcn_gate_layout incorporates the BGL bug now. Minimum size in each dimension is 2. For more information, see https://svn.boost.org/trac10/ticket/11735

  • Parameters for exact no longer get stuck once set

Removed

  • Parameter -n for exact

v0.2.0 - 2019-03-21

Fiction reveals the truth that reality obscures. — Jessamyn West

Added

  • Export fcn_cell_layout objects as SVG using show -c. See README for more information

  • ps -g displays and logs critical path and throughput of fcn_gate_layout objects

  • Support for RES clocking and integration in exact

  • New TOY benchmarks in respective folder

  • New command clear to remove all elements from stores (as a shorthand for store --clear ...)

  • Information about how to build fiction for WSL

  • Functions to distinguish different logic_network types like AIGs/MIGs/…

  • Parameter -n for command ortho

Changed

  • Revised folder structure due to the increasing amount of source files

  • read_verilog is now called read and can process directories

  • gate_to_cell is now called cell

  • write_qca is now called qca and handles file names automatically if necessary

  • -u is not a required parameter for exact anymore

  • Richer output for print -w

  • Included latest bugfixes for alice

  • Included latest update for lorina

Fixed

  • Starting layout size for calls to exact -i was too low and has been corrected

  • Several code and comment inconsistencies

Removed

  • ITC99 benchmark files

v0.1.1 - 2018-12-29

Literature is a luxury; fiction is a necessity. — G. K. Chesterton

Added

  • Technology-specific energy model for fcn_gate_layout; supports QCA thus far

  • Support for print -c to write a textual representation of fcn_cell_layout objects

  • Information on nested fiction scripts and documentation generation in README

  • linguist flags in .gitattributes to prevent benchmark files from being viewed as source code

Changed

  • Moved to version 0.4 of alice

  • Moved to version 4.8.4 of Z3

  • fcn_gate_library objects now have name strings

  • print -g now displays incorrectly assigned directions by bidirectional arrows

  • “Release” is the standard build mode now

Fixed

  • Copy and move constructors of logic_network work properly now

  • Calculation of bounding_box size on fcn_gate_layout now handles empty layouts correctly

  • Several minor and rare bugs, code inconsistencies, and performance issues

Removed

  • Nothing

v0.1.0 - 2018-10-29

Let there be a fiction

This is the initial release. Please find a feature overview in the README.