On-chip logic minimization

ABSTRACT

While Boolean logic minimization is typically used in logic synthesis, logic minimization can be useful in numerous other applications. However, many of those applications, such as Internet Protocol routing table and network access control list reduction, require logic minimization during the application's runtime, and hence could benefit from minimization executing on-chip alongside the application. On-chip minimization can even enable dynamic hardware/software partitioning. We discuss requirements of on-chip logic minimization, and present our new on-chip logic minimization tool, ROCM. We compare with the well-known Espresso logic minimizer and show that ROCM is 10 times smaller, executes 10-20 times faster, and uses 3 times less data memory, with a mere 2% quality penalty, for the routing table and access control list applications. We show that ROCM solves real-sized problems on an ARM7 embedded processor in just seconds.

REFERENCES

• 1: Advanced RISC Machines Ltd. ARM7. http://www.arm.com/armtech/ARM7_Thumb/, 2002.
• 2: Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
• 3: Roberto Cordone , Fabrizio Ferrandi , Donatella Sciuto , Roberto Wolfler Calvo, An efficient heuristic approach to solve the unate covering problem, Proceedings of the conference on Design, automation and test in Europe, p.364-371, March 27-30, 2000, Paris, France [doi>10.1145/343647.343799]
• 4: Hayashi, T., T. Miyazaki, High-Speed Table Lookup Engine for IPv6 Longest Prefix Match. Proc. IEEE Globecom, Vol. 2, pp. 1576--1581, 1999.
• 5: Jan Hlavička , Petr Fišer, BOOM: a heuristic boolean minimizer, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 6: Huan Liu, Routing Table Compaction in Ternary CAM, IEEE Micro, v.22 n.1, p.58-64, January 2002 [doi>10.1109/40.988690]
• 7: McAuley, A. P. Francis. Fast Router Table Lookup Using CAMs. Proc. Infocom, Vol. 3, pp. 1382--91, 1993.
• 8: McCluskey, E. Minimization of Boolean Functions. Bell System Technical Journal, pp. 1417-1444, NY, 1959.
• 9: McGeer, P., J. Sanghavi, A. Sangiovanni-Vincentelli. Espresso-Signature: A New Exact Minimizer for Logic Functions. IEEE Transactions on VLSI, Vol. 1, No. 4, pp. 432--440, 1993.
• 10: Merit Network, Inc. Internet Routing Table Statistics, http://www.merit.edu/ipma/routing_table/, 2002.
• 11: Greg Stitt , Roman Lysecky , Frank Vahid, Dynamic hardware/software partitioning: a first approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775896]
• 12: Svoboda, A., D.E. White. Advanced Logical Circuit Design Techniques. Garland Press, New York, 1979.
• 13: Triscend Corporation. A7 CSoC Family. http://www.triscend.com, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Performance

Keywords:
dynamic optimization, embedded systems, logic minimization, on-chip logic minimization, on-chip synthesis, system-on-a-chip