DOI: 10.17587/prin.14.225-231

Algorithms for Improving the Automatically Synthesized Instruction Set of an Extensible Processor

D. N. Sovietov, Associated Professor, sovetov@mirea.ru, MIREA — Russian Technological University, Moscow, 119454, Russian Federation

Corresponding author: Petr N. Sovietov, Associated Professor, MIREA — Russian Technological University, Moscow, 119454, Russian Federation, E-mail: sovetov@mirea.ru

Processors with extensible instruction sets are often used today as programmable hardware accelerators for various domains. When extending RISC-V and other similar extensible processor architectures, the task of designing specialized instructions arises. This task can be solved automatically by using instruction synthesis algorithms. In this paper, we consider algorithms that can be used in addition to the known approaches and improve the synthesized instruction sets by recomputing common operations (the result of which is consumed by multiple operations) of a program inside clustered synthesized instructions (common operations clustering algorithm), and by identifying redundant (which have equivalents among the other instructions) synthesized instructions (subsuming functions algorithm). Experimental evaluations of the developed algorithms are presented for the tests from the domains of cryptography and three-dimensional graphics. For Magma cipher test, the common operations clustering algorithm allows reducing the size of the compiled code by 9 %, and the subsuming functions algorithm allows reducing the synthesized instruction set extension size by 2 times. For AES cipher test, the common operations clustering algorithm allows reducing the size of the compiled code by 10 %, and the subsuming functions algorithm allows reducing the synthesized instruction set extension size by 2.5 times. Finally, for the instruction set extension from Volume Ray-Casting test, the additional use of subsuming functions algorithm allows reducing problem-specific instruction extension set size from 5 to only 2 instructions without losing its functionality.

Keywords: instruction set synthesis, extensible processors, RISC-V, high-level design, dependency graph analysis, graph clustering, SMT solver

pp. 225–231

For citation:
Sovietov P. N. Algorithms for Improving the Automatically Synthesized Instruction Set of an Extensible Processor, Programmnaya ingeneria, 2023, vol. 14, no. 5, pp. 225—231. DOI: 10.17587/prin.14.225-231 (in Russian).

References:

1. Hennessy J. L., Patterson D. A. A new golden age for computer architecture, Communications of the ACM 2019, vol. 62, no. 2, pp. 48—60. DOI: 10.1145/3282307.
2. Galuzzi C., Bertels K. The instruction-set extension problem: A survey, ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2011, vol. 4, no. 2, pp. 1—28. DOI: 10.1145/1968502.1968509.
3. Alippi C., Fornaciari W., Pozzi L., Sami M. A DAG-based design approach for reconfigurable VLIW processors, Proceedings of the confer­ence on design, automation and test in Europe. Association for Computing Machinery, NY, USA, 1999, pp. 57—es. DOI: 10.1145/307418.307504.
4. Solar-Lezama A. Program sketching, International Journal on Software Tools for Technology Transfer, 2013,vol. 15, no. 5, pp. 475—495. DOI: 10.1007/s10009-012-0249-7.
5. Sovetov P. Development of DSL compilers for specialized processors, Programming and Computer Software, 2021, vol. 47, no. 7, pp. 541—554. DOI: 10.1134/s0361768821070082.
6. Nery A. S., Nedjah N., Franca F. M., Jozwiak L., Corpo-raal H. Automatic complex instruction identification for efficient application mapping onto ASIPs, 2014 IEEE 5th latin american symposium on circuits and systems, IEEE, 2014, pp. 1—4. DOI: 10.1109/lascas.2014.6820291.
7. Cong J., Fan Y., Han G., Zhang Z. Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on field programmable gate arrays, 2004, pp. 183—189. DOI: 10.1145/968280.968307.
8. Peymandoust A., Pozzi L., Ienne P., De Micheli G. Automatic instruction set extension and utilization for embedded processors, Proceedings IEEE international conference on application-specific systems, architectures, and processors, ASAP 2003. IEEE, 2003, pp. 108—118. DOI: 10.1109/asap.2003.1212834.
9. Clark N. T., Zhong H., Mahlke S. A. Automated custom instruction generation for domain-specific processor acceleration, IEEE Transactions on Computer 2005, vol. 54, no. 10, pp. 1258—1270. DOI: 10.1109/tc.2005.156.
10. Pothineni N., Brisk P., Ienne P., Kumar A., Paul K. A high-level synthesis flow for custom instruction set extensions for application-specific processors, 2010 15th Asia and South Pacific design automation conference (ASP-DAC),IEEE, 2010, pp. 707—712. DOI: 10.1109/aspdac.2010.5419795.
11. Atasu K., Diindar G., Ozturan C. An integer linear programming approach for identifying instruction-set extensions, Proceedings of the 3rd IEEE/ACM/IFIP international conference on hardware/software codesign and system synthesis, 2005, pp. 172—177. DOI: 10.1145/1084834.1084880. .
12. Pozzi L., Atasu K., Ienne P. Exact and approximate algorithms for the extension of embedded processor instruction sets, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, vol. 25, no. 7, pp. 1209—1229. DOI: 10.1109/ tcad.2005.855950.
13. Pulli A., Galuzzi C., Gaydadjiev G. Towards domain-specific instruction-set generation, 2014 24th international conference on field programmable logic and applications (FPL), IEEE, 2014, pp. 1—4. DOI: 10.1109/fpl.2014.6927423.
14. Xiao C., Wang S., Liu W., Wang X., Casseau E. An optimal algorithm for enumerating connected convex subgraphs in acyclic digraphs, IEEE Transactions on Circuits and Systems II: Express Briefs., IEEE, 2020, vol. 68, no. 1, pp. 261—265. DOI: 10.1109/ TCSII.2020.3000297.