@techreport{TR-IC-03-18,
  number = {IC-03-18},
  author = {Nahri Moreano and Guido Araujo and Cid C. de Souza},
  title = {{CDFG} Merging for Reconfigurable Architectures},
  month = {October},
  year = {2003}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 9 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       Reconfigurable systems have been proved to achieve significant
       performance speedup through architectures that map the most
       time-consuming application kernel modules or inner-loops to a
       reconfigurable datapath.  As each portion of the application
       starts to execute, the system reconfigures the datapath so as
       to perform the corresponding computation.  The reconfigurable
       datapath should have as few and simple hardware blocks and
       interconnections as possible, in order to reduce its cost,
       area, power consumption, and reconfiguration overhead.  Thus
       hardware blocks and interconnections should be reused across
       the application as much as possible.  We represent each piece
       of the application as a control/data-flow graph (CDFG) and
       merge them together, synthesizing a single reconfigurable
       datapath.  The CDFG merging process enables the reuse of
       hardware blocks and interconnections by identifying
       similarities among the CDFGs, and producing a resulting
       datapath that can be dynamically reconfigured to work for each
       CDFG and has a minimum area cost, when considering both
       hardware blocks and interconnections.  In this report we
       formalize the CDFG merge problem and we present a proof that it
       is NP-complete, by reducing the subgraph isomorphism problem to
       it.
  }
}