Encoding Custom Instruction Generation as Satisfiability Problem

Abstract:

The emergence of Application-specific Instruction-set Processor (ASIP) has encouraged the proliferation of tool-chains used to streamline its design flow. One of the features much sought-after in these tool-chains is notably the automatic generation of Application-specific Functional Units (AFUs) which, in turn, involves the custom instruction generation as a crucial step. Whereupon an additional step is assumed to pipeline the patterns identified for fulfilling the I/O constraint, custom instructions that correspond to maximal valid subgraphs are mostly beneficial to the speedup gain. Therefore, we present in this paper a propositional satisfiability approach to efficiently identify the custom instructions which contain a large number of valid nodes. Our approach is different substantially from the previous works where it uses an edge classification method to reduce the search space for convexity checking. The experiment results show that our method can, in a matter of few seconds, identify a set of custom instructions that speed up the application to a few times faster.

• Periodical: Advanced Materials Research (Volumes 403-408)
• Pages: 502-510
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.403-408.502
• Online since: November 2011
• Authors: Tingh Wee Wong, Bryan Ng, Chee Onn Wong
• Keywords: ASIP, Instruction-Set Extension, Propositional Satisfiability, SAT Solver

References

[1] N. Eén, and A. Biere, Effective Preprocessing in SAT Through Variable and Clause Elimination, in Lecture Notes in Computer Science, Springer, 2005, p.61. 75.

DOI: 10.1007/11499107_5

[2] M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, S. Malik, Chaff: engineering an efficient SAT solver, in Proceedings of the Design Automation Conference, IEEE Press, 2010, pp.530-535.

DOI: 10.1145/378239.379017

[3] M.N. Velev, Exploiting Hierarchy and Structure to Efficiently Solve Graph Coloring as SAT, in Proceedings of the International Confonference on Computer-Aided Design, IEEE Press, Nov. 2007, pp.135-142.

DOI: 10.1109/iccad.2007.4397256

[4] J. Cong, Y. Fan, G. Han, and Z. Zhang, Application-Specific Instruction Generation for Configurable Processor Architectures, in Proceedings of the ACM International Symposium on Field-Programmable Gate Arrays, ACM Press, Feb. 2004, pp.183-189.

DOI: 10.1145/968280.968307

[5] L. Pozzi and P. Ienne, Exploiting pipelining to relax register-file port constraints of instruction-set extensions, in Proceedings of the 2005 International Conference on Compilers, architectures and synthesis for embedded systems (CASES 05), ACM Press, Sep. 2005, p.2.

DOI: 10.1145/1086297.1086300

[6] J. Cong, Y. Fan, G. Han, A. Jagannathan, G. Reinman and Z. Zhang, Instruction Set Extension with Shadow Registers for Configurable Processors, in Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, ACM Press, Feb. 2005, pp.99-106.

DOI: 10.1145/1046192.1046206

[7] K. Karuri, A. Chattopadhyay, and M. Hohenauer, Increasing data-bandwidth to instruction-set extensions through register clustering, in Proceedings of the International Conference on Computer-Aided Design (ICCAD 07), IEEE Press, Nov. 2007, pp.166-171.

DOI: 10.1109/iccad.2007.4397261

[8] K. Atasu, O. Mencer, W. Luk, C. Özturan, and G. Dünda, Fast custom instruction identification by convex subgraph enumeration, in Proceedings of the IEEE International Conference on Application-specific Systems, Architectures and Processors, IEEE Press, Jul. 2008, p.1.

DOI: 10.1109/asap.2008.4580145

[9] A. K. Verma, P. Brisk, P. Ienne, Fast, Nearly Optimal ISE Identification With I/O Serialization Through Maximal Clique Enumeration, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 29, Mar. 2010, pp.341-354.

DOI: 10.1109/tcad.2010.2041849

[10] C. Galuzzi, D. Theodoropoulos, R. Meeuws, and K. Bertels, Algorithms for the automatic extension of an instruction-set, in Design, Automation & Test in Europe Conference & Exhibition (DATE 09), IEEE Press, Apr. 2009, p.548 – 553.

DOI: 10.1109/date.2009.5090724

[11] N. Pothineni, A. Kumar, and K. Paul, Application-specific datapath extension with distributed I/O functional units, in Proc. 20th Int. Conf. Very-Large-Scale Integration Des., Jan. 2007, p.551–558.

DOI: 10.1109/vlsid.2007.40

[12] T. Li, Z. Sun, W. Jigang, and X. Lu, Fast enumeration of maximal valid subgraphs for custom-instruction identification, in Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems (CASES 09), ACM Press, Apr. 2009, pp.29-36.

DOI: 10.1145/1629395.1629402

[13] L. N. Chakrapani, J. C. Gyllenhaal, W. mei W. Hwu, S. A. Mahlke, K. V. Palem, and R. M. Rabbah, Trimaran: An infrastructure for research in instruction-level parallelism., in Lecture Notes in Computer Science, Springer, 2004, p.32–41.

DOI: 10.1007/11532378_4

[14] D. Le Berre, and A. Parrain, The Sat4j library, release 2. 2, , Journal on Satisability, Boolean Modeling and Computation, vol. 7, 2010, pp.59-64.

DOI: 10.3233/sat190075

[15] C. Lee, M. Potkonjak, and W. H. Mangione-Smith, MediaBench: A tool for evaluating and synthesizing multimedia and communicatons systems, in Proceedings of the 30th Annual IEEE/ACM International Symposium on Microarchitecture, IEEE Press, Dec. 1997, p.330.

DOI: 10.1109/micro.1997.645830