LSI Semester Project List #1

Contact person for projects on this list: Siang-Yun Lee

Re-implementation Projects

The target of projects in this section is to re-implement one of these algorithms in mockturtle. The re-implementation does not have to be exactly the same as the original one, but it is expected to achieve a similar performance (efficiency and quality). Basic components in mockturtle may be reused, such as utility data structures and building-block algorithms. The contributed code should align with the philosophy and conventions of mockturtle. The result of the project may end as a pull request to mockturtle.

Combinational equivalence checking (CEC)

Reference implementation(s): ABC commands cec, &cec

Reference papers:

  • Mishchenko, A., Chatterjee, S., Brayton, R., & Een, N. (2006, November). Improvements to combinational equivalence checking. In 2006 IEEE/ACM International Conference on Computer Aided Design (pp. 836-843). IEEE.
  • Zhang, H. T., Jiang, J. H. R., Amarú, L., Mishchenko, A., & Brayton, R. (2021, December). Deep integration of circuit simulator and SAT solver. In 2021 58th ACM/IEEE Design Automation Conference (DAC) (pp. 877-882). IEEE.
Interpolation-based resubstitution for k-LUT network

Reference implementation: ABC command mfs

Reference paper:

  • Mishchenko, A., Brayton, R., Jiang, J. H. R., & Jang, S. (2011). Scalable don’t-care-based logic optimization and resynthesis. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 4(4), 1-23.
Inverter propagation/minimization for majority-inverter graph (MIG)

Reference papers:

  • Testa, E., Soeken, M., Zografos, O., Amaru, L., Raghavan, P., Lauwereins, R., … & De Micheli, G. (2016, July). Inversion optimization in majority-inverter graphs. In 2016 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH) (pp. 15-20). IEEE.
  • Testa, E., Zografos, O., Soeken, M., Vaysset, A., Manfrini, M., Lauwereins, R., & De Micheli, G. (2017, July). Inverter propagation and fan-out constraints for beyond-CMOS majority-based technologies. In 2017 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) (pp. 164-169). IEEE.
Resynthesis based on two-level minimization

Implement a node_resynthesis method in mockturtle based on deriving a two-level representation (SOP or POS) of the given function.

Reference: ESPRESSO

Unified Interfaces

The target of the following projects is to construct a unified interface for solving a certain well-defined class of problems, such that it becomes easy to experiment the performances of different tools solving the same problem. For example, in bill, a unified interface for solving SAT problems is provided and several widely-used SAT solvers are integrated. The outcome of these projects should result in a pull request to bill.

Unified interfaces of various BDD packages

Candidate BDD packages: CUDDBuDDy, Sylvan, BiDDy

Unified interfaces of various LP/ILP solvers

Candidate LP solvers: lp_solve, GLPK, CLP, Z3, (MINOS)

Adding Kissat SAT solver support into bill

Front-end interfaces for mockturtle

The target of these two projects is to build a user-friendly front-end for mockturtle. There are two independent possibilities:

  1. Command-line interface using alice. This integration has been done in cirkit, but it is not maintained and mockturtle has evolved a lot since the integration was done.
  2. Web-based interface (any web framework)

New network data structures in mockturtle

The goal of these projects is to implement a new network data structure in mockturtle. The contributed code should align with the philosophy and conventions of mockturtle. The result of the project may end as a pull request to mockturtle.

Threshold logic network

A threshold logic gate is a gate taking arbitrary number of binary-valued inputs x1, …, xn and outputs a binary value y. Each input xi is associated with an integer-valued weight wi, and the gate has an integer-valued threshold T. The output of the gate is 1 if and only if x1 · w1 + … + xn · wn ≥ T.