Suggestions of algorithms to implement for the programming challenge

Following are some suggestions for possible algorithms. These suggestions should not constrain you. Feel free to implement anything which is useful for the new synthesis flow. You are especially welcomed to implement your own research on OpenAccess.

Technology Independent Optimization

The decomposition and factorization of Boolean expressions, R. K. Brayton, C. McMullen, Proc. ISCAS, 1982

Global Flow Optimization in Automatic Logic Design, C. L. Berman, L. H. Trevillyan, IEEE Transactions on Computer-Aided Design, Vol. 10, No. 5, May 1991, pp. 557-564.

Preferable is a new algorithm which uses an efficient SAT solver, which combines redundancy removal with rewiring.

Technology Mapping

OA Gear has currently a very simple mapper. It shows how to use the functional package. The simple mapper does not do any optimization. It just takes the and-inverter graph and maps it directly to and, inverter and sequential gates, using just three different types of gates in the library.

Logic decomposition during technology mapping, E. Lehman, Y. Watanabe, J. Grodstein, H. Harkness, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 8, August 1997, pp. 813-834.

Wavefront Technology Mapping, L. Stok, M.A. Iyer, A. J. Sullivan, Design, Automation and Test in Europe Conference and Exhibition (DATE), March 1999, Munich, Germany, pp. 531-536.

Technology Dependent Optimization

Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation, C. P. Chen, C. N. Chu, D. F. Wong, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 7, July 1999, pp. 1014-1025.

Gate Sizing for Constrained Delay/Power/Area Optimization, Oliver Coudert, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 5, No. 4, December 1997, pp. 465-472.

Equivalence Checking

Robust Boolean Reasoning for Equivalence Checking and Functional Property Verification, A. Kuehlmann, M. Ganai, F. Krohm, V. Paruthi, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21. No. 12, December 2002, pp. 1377-1394.

Retiming

Retiming synchronous circuitry, C. E. Leiserson, J. B. Saxe, Algorithmica, Vol. 6, No. 1, 1991, pp. 5-35.