S. Ichikawa, H. Saito, L. Udorn, and K. Konishi

Proceedings of 10th Int'l Conf. on Field Programmable Logic and Applications (FPL 2000), LNCS 1896, Springer, pp. 729-738 (2000).

Abstract

Many applications can be modeled as subgraph isomorphism problems. However, this problem is generally NP-complete and difficult to compute. A custom computing circuit is a prospective solution for such problems. This paper examines various accelerator designs, and compares them quantitatively from two points of view: cost and performance. An algorithm that is suited for hardware implementation is also proposed. The hardware for the proposed algorithm is much smaller on logic scale, and operates at a higher frequency than Ullmann's design. The prototype accelerator operates at 16.5 MHz on a Lucent ORCA 2C15A, which outperforms the software implementation of Ullmann's algorithm on a 400 MHz Pentium II.