Evaluation of Accelerator Designs for Subgraph Isomorphism Problem

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.