Output details
11 - Computer Science and Informatics
Royal Holloway, University of London
Algorithms for generating convex sets in acyclic digraphs
<08> This paper presents an optimal algorithm for enumerating the convex sets in a program’s data dependency graph. The paper has led to further research from the same group on input-output constrained convex sets, published at WG 2008, EUC 2009 and as an invited paper in J. Discrete Algorithms 13 (2012). Applications include customisable processors in embedded computing where candidate sub-programs for single-cycle evaluation form convex sets in the data dependency graph; e.g. the recent paper 'Isomorphism-Aware Identification of Custom Instructions With I/O Serialization' by Ahn and Choi in IEEE Trans. Computer-Aided Design of Integrated Circuits and Sys.