IEICE TRANSACTIONS on Information
Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems
Summary :
Many application programs can be modeled as a subgraph isomorphism problem. 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 for subgraph isomorphism problems based on Ullmann's algorithm and Konishi's algorithm. These designs are quantitatively evaluated from two points of view: logic scale and execution time. Our study revealed that Ullmann's design is faster but larger in logic scale. Partially sequential versions of Ullmann's algorithm can be more cost-effective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more cost-effective.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.7 pp.1250-1257
- Publication Date
- 2003/07/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- VLSI Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shuichi ICHIKAWA, Hidemitsu SAITO, Lerdtanaseangtham UDORN, Kouji KONISHI, "Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 7, pp. 1250-1257, July 2003, doi: .
Abstract: Many application programs can be modeled as a subgraph isomorphism problem. 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 for subgraph isomorphism problems based on Ullmann's algorithm and Konishi's algorithm. These designs are quantitatively evaluated from two points of view: logic scale and execution time. Our study revealed that Ullmann's design is faster but larger in logic scale. Partially sequential versions of Ullmann's algorithm can be more cost-effective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more cost-effective.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_7_1250/_p
Copy
@ARTICLE{e86-d_7_1250,
author={Shuichi ICHIKAWA, Hidemitsu SAITO, Lerdtanaseangtham UDORN, Kouji KONISHI, },
journal={IEICE TRANSACTIONS on Information},
title={Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems},
year={2003},
volume={E86-D},
number={7},
pages={1250-1257},
abstract={Many application programs can be modeled as a subgraph isomorphism problem. 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 for subgraph isomorphism problems based on Ullmann's algorithm and Konishi's algorithm. These designs are quantitatively evaluated from two points of view: logic scale and execution time. Our study revealed that Ullmann's design is faster but larger in logic scale. Partially sequential versions of Ullmann's algorithm can be more cost-effective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more cost-effective.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Trade-Offs in Custom Circuit Designs for Subgraph Isomorphism Problems
T2 - IEICE TRANSACTIONS on Information
SP - 1250
EP - 1257
AU - Shuichi ICHIKAWA
AU - Hidemitsu SAITO
AU - Lerdtanaseangtham UDORN
AU - Kouji KONISHI
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2003
AB - Many application programs can be modeled as a subgraph isomorphism problem. 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 for subgraph isomorphism problems based on Ullmann's algorithm and Konishi's algorithm. These designs are quantitatively evaluated from two points of view: logic scale and execution time. Our study revealed that Ullmann's design is faster but larger in logic scale. Partially sequential versions of Ullmann's algorithm can be more cost-effective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more cost-effective.
ER -
English
