A Graph Covering Algorithm for a Coarse Grain Reconfigurable System

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

doi:10.1145/780732.780760

A Graph Covering Algorithm for a Coarse Grain Reconfigurable System

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

48 Downloads (Pure)

Abstract

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 language	Undefined
Title of host publication	Proceedings of LCTES 2003
Place of Publication	New York
Publisher	Association for Computing Machinery
Pages	199-208
Number of pages	10
ISBN (Print)	1-58113-647-1
DOIs	https://doi.org/10.1145/780732.780760
Publication status	Published - Jun 2003
Event	ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2003 - San Diego, United States Duration: 11 Jun 2003 → 13 Jun 2003 Conference number: LCTES 2003

Publication series

Name
Publisher	ACM

Conference

Conference	ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2003
Country/Territory	United States
City	San Diego
Period	11/06/03 → 13/06/03

Keywords

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

Access to Document

10.1145/780732.780760

guo_lctes03

Cite this

@inproceedings{93442af1daf34fba921382de64a2a5c8,

title = "A Graph Covering Algorithm for a Coarse Grain Reconfigurable System",

abstract = "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.",

keywords = "CAES-EEA: Efficient Embedded Architectures, IR-46372, EWI-1512, METIS-214809",

author = "Y. Guo and Smit, {Gerardus Johannes Maria} and P.M. Heysters and Broersma, {Haitze J.}",

note = "Imported from CHAMELEON.xml; null ; Conference date: 11-06-2003 Through 13-06-2003",

year = "2003",

month = jun,

doi = "10.1145/780732.780760",

language = "Undefined",

isbn = "1-58113-647-1",

publisher = "Association for Computing Machinery",

pages = "199--208",

booktitle = "Proceedings of LCTES 2003",

}

Guo, Y, Smit, GJM, Heysters, PM & Broersma, HJ 2003, A Graph Covering Algorithm for a Coarse Grain Reconfigurable System. in Proceedings of LCTES 2003. Association for Computing Machinery, New York, pp. 199-208, ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2003, San Diego, California, United States, 11/06/03. https://doi.org/10.1145/780732.780760

TY - GEN

T1 - A Graph Covering Algorithm for a Coarse Grain Reconfigurable System

AU - Guo, Y.

AU - Smit, Gerardus Johannes Maria

AU - Heysters, P.M.

AU - Broersma, Haitze J.

N1 - Conference code: LCTES 2003

PY - 2003/6

Y1 - 2003/6

N2 - 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.

AB - 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.

KW - CAES-EEA: Efficient Embedded Architectures

KW - IR-46372

KW - EWI-1512

KW - METIS-214809

U2 - 10.1145/780732.780760

DO - 10.1145/780732.780760

M3 - Conference contribution

SN - 1-58113-647-1

SP - 199

EP - 208

BT - Proceedings of LCTES 2003

PB - Association for Computing Machinery

CY - New York

Y2 - 11 June 2003 through 13 June 2003

ER -