Semi-Synthetic Circuit Generation Using Graph Monomorphism for Testing Incremental Placement and Incremental Routing Tools

TitleSemi-Synthetic Circuit Generation Using Graph Monomorphism for Testing Incremental Placement and Incremental Routing Tools
Publication TypeConference Paper
Year of Publication2006
AuthorsGrant, D., S. Chin, and G. Lemieux
Conference NameField Programmable Logic and Applications, 2006. FPL '06. International Conference on
Pagination1 -4
Date Publishedaug.
Keywordsbenchmark 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.

URLhttp://dx.doi.org/10.1109/FPL.2006.311300
DOI10.1109/FPL.2006.311300

a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949
Email:

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2018 The University of British Columbia