A Graph Covering Algorithm for a Coarse Grain Reconfigurable System

Guo, Yuanqing and Smit, Gerard J.M. and Heysters, Paul M. and Broersma, Hajo (2003) A Graph Covering Algorithm for a Coarse Grain Reconfigurable System. In: ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2003, June 11-13, 2003, San Diego, USA.

PDF
Restricted to UT campus only: Request a copy
402Kb

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.
Item Type:	Conference or Workshop Item
Copyright:	© 2003 ACM
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Computer Architecture for Embedded Systems (CAES) Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/46372
Official URL:	http://dx.doi.org/10.1145/780732.780760
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 214809