×

An algorithm for finding input-output constrained convex sets in an acyclic digraph. (English) Zbl 1248.05078

Summary: A set \(X\) of vertices of an acyclic graph is convex if any vertex on a directed walk between elements of \(X\) is itself in \(X\). We construct an algorithm for generating all input-output constrained convex (IOCC) sets in an acyclic digraph, which uses several novel ideas. We show that the time complexity of our algorithm significantly improves the best one known from the literature. IOCC sets of acyclic digraphs are of interest in the area of modern embedded processor technology.

MSC:

05C20 Directed graphs (digraphs), tournaments
52A15 Convex sets in \(3\) dimensions (including convex surfaces)
68M99 Computer system organization
68R10 Graph theory (including graph drawing) in computer science

Software:

MiBench
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Atasu, G. Dunbar, C. Ozturan, An integer linear programming approach for identifying instruction-set extensions, in: CODES+ISSSʼ05: Proc. 3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, 2005, pp. 172-177.; K. Atasu, G. Dunbar, C. Ozturan, An integer linear programming approach for identifying instruction-set extensions, in: CODES+ISSSʼ05: Proc. 3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, 2005, pp. 172-177.
[2] Balister, P.; Gerke, S.; Gutin, G.; Johnstone, A.; Reddington, J.; Scott, E.; Soleimanfallah, A.; Yeo, A., Algorithms for generating convex sets in acyclic digraphs, J. Discrete Algorithms, 7, 509-518 (2009) · Zbl 1213.05241
[3] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer · Zbl 1170.05002
[4] P. Bonzini, L. Pozzi, Polynomial-time subgraph enumeration for automated instruction set extension, in: DATE 2007, pp. 1331-1336.; P. Bonzini, L. Pozzi, Polynomial-time subgraph enumeration for automated instruction set extension, in: DATE 2007, pp. 1331-1336.
[5] Chen, X.; Maskell, D. L.; Sun, Y., Fast identification of custom instructions for extensible processors, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 26, 359-368 (2007)
[6] N. Clark, H. Zhong, S. Mahlke, Processor acceleration through automated instruction set customization, in: MICRO 36: Proc. 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, p. 129.; N. Clark, H. Zhong, S. Mahlke, Processor acceleration through automated instruction set customization, in: MICRO 36: Proc. 36th Annual IEEE/ACM International Symposium on Microarchitecture, 2003, p. 129.
[7] J. Cong, Y. Fan, G. Han, Z. Zhang, Application-specific instruction generation for configurable processor architectures, in: Proc. FPAGʼ02, 2004, pp. 183-189.; J. Cong, Y. Fan, G. Han, Z. Zhang, Application-specific instruction generation for configurable processor architectures, in: Proc. FPAGʼ02, 2004, pp. 183-189.
[8] M.R. Guthaus, J.S. Ringenberg, D. Ernst, T.M. Austin, T. Mudge, R.B. Brown, MiBench: A free, commercially representative embedded benchmark suite, in: Proceedings of the WWC-4, 2001 IEEE International Workshop on Workload Characterization, 2001, pp. 3-14.; M.R. Guthaus, J.S. Ringenberg, D. Ernst, T.M. Austin, T. Mudge, R.B. Brown, MiBench: A free, commercially representative embedded benchmark suite, in: Proceedings of the WWC-4, 2001 IEEE International Workshop on Workload Characterization, 2001, pp. 3-14.
[9] Gutin, G.; Johnstone, A.; Reddington, J.; Scott, E.; Soleimanfallah, A.; Yeo, A., An algorithm for finding connected convex subgraphs of an acyclic digraph, (Algorithms and Complexity in Durham, 2007 (2008), College Publications) · Zbl 1248.05078
[10] Gutin, G.; Johnstone, A.; Reddington, J.; Scott, E.; Yeo, A., An algorithm for finding input-output constrained convex subgraphs of an acyclic digraph, (Broersma, H.; Erlebach, T.; Friedetzky, T.; Paulusma, D., Graph-Theoretic Concepts in Computer Science, WG 2008. Graph-Theoretic Concepts in Computer Science, WG 2008, LNCS, vol. 5344 (2008), Springer) · Zbl 1248.05078
[11] Pozzi, L.; Atasu, K.; Ienne, P., Exact and approximate algorithms for the extension of embedded processor instruction sets, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 25, 1209-1229 (2006)
[12] J. Reddington, Improvements to instruction identification for custom instruction set design, PhD thesis, Royal Holloway, University of London, 2008.; J. Reddington, Improvements to instruction identification for custom instruction set design, PhD thesis, Royal Holloway, University of London, 2008.
[13] J. Reddington, G. Gutin, A. Johnstone, E. Scott, A. Yeo, Better than optimal: fast identification of custom instruction candidates, in: Proc. 7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC-09), 2009, pp. 17-24.; J. Reddington, G. Gutin, A. Johnstone, E. Scott, A. Yeo, Better than optimal: fast identification of custom instruction candidates, in: Proc. 7th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing (EUC-09), 2009, pp. 17-24.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.