Title | Semi-Synthetic Circuit Generation Using Graph Monomorphism for Testing Incremental Placement and Incremental Routing Tools |
Publication Type | Conference Paper |
Year of Publication | 2006 |
Authors | Grant, D., S. Chin, and G. Lemieux |
Conference Name | Field Programmable Logic and Applications, 2006. FPL '06. International Conference on |
Pagination | 1 -4 |
Date Published | aug. |
Keywords | benchmark circuits, combinational circuits, combinational loops, graph monomorphism, graph theory, incremental placement, incremental routing tools, logic CAD, network routing, replacement process, semisynthetic circuit generation, stitching process, synthetic circuit |
Abstract | FPGA architects are always searching for more benchmark circuits to stress CAD tools and device architectures. In this paper we present a new method to generate benchmark circuits by removing part of a real circuit and replacing it with a synthetic clone. This replacement or stitching process can easily introduce combinational loops if the synthetic circuit contains an input-to-output dependence that was not in the original subcircuit it is replacing. We show that this can be expressed as the graph monomorphism problem, and that a solution to that problem gives a precise stitching assignment that is cycle-free. This technique can be used to create new benchmark circuits that are identical to the original circuit except for small, local changes. The resulting semi-synthetic benchmarks are ideal for testing incremental place and route tools. |
URL | http://dx.doi.org/10.1109/FPL.2006.311300 |
DOI | 10.1109/FPL.2006.311300 |