A Graph Covering Algorithm for a Coarse Grain Reconfigurable System

Y. Guo, Gerardus Johannes Maria Smit, P.M. Heysters, Haitze J. Broersma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

62 Downloads (Pure)


The availability of high-level design entry tooling is crucial for the viability of any reconfigurable SoC architecture. This paper presents a graph covering algorithm. The graph covering is done in two steps: template generation and template selection. The objective of template generation step is to extract functional equivalent structures, i.e. templates, from a control data flow graph. By inspecting the graph, the algorithm generates all the possible templates and the corresponding matches. Using unique serial numbers and circle numbers, the algorithm can find all distinct templates with multiple outputs. The template selection algorithm shows how this information can be used in compilers for reconfigurable systems. The objective of the template selection algorithm is to find an efficient cover for an application graph with a minimal number of distinct templates and minimal number of matches.
Original languageUndefined
Title of host publicationProceedings of LCTES 2003
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)1-58113-647-1
Publication statusPublished - Jun 2003
EventACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2003 - San Diego, United States
Duration: 11 Jun 200313 Jun 2003
Conference number: LCTES 2003

Publication series



ConferenceACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2003
Country/TerritoryUnited States
CitySan Diego


  • CAES-EEA: Efficient Embedded Architectures
  • IR-46372
  • EWI-1512
  • METIS-214809

Cite this