Accelerating the Development of DSL Compilers for Specialized Processors
https://doi.org/10.15514/ISPRAS-2020-32(5)-3
Abstract
Specialized processors programmable in domain-specific languages are increasingly used in modern computing systems. The compiler-in-the-loop approach, based on the joint development of a specialized processor and a compiler, is gaining popularity. At the same time, the traditional tools, like GCC and LLVM, are insufficient for the agile development of optimizing compilers that generate target code of an exotic, irregular architecture with static parallelism of operations. The article proposes methods from the field of program synthesis for the implementation of machine-dependent compilation phases. The phases are based on a reduction to SMT problem which allows to get rid of heuristic and approximate approaches, that requires complex software implementation of a compiler. In particular, a synthesis of machine-dependent optimization rules, instruction selection and instruction scheduling combined with register allocation are implemented with help of SMT solver. Practical applications of the developed methods and algorithms are illustrated by the example of a compiler for a specialized processor with an instruction set that accelerates the implementation of lightweight cryptography algorithms in the Internet of Things. The results of compilation and simulation of 8 cryptographic primitives for 3 variants of specialized processor (CISC-like, VLIW-like and a variant with delayed load instruction) show the vitality of the proposed approach.
About the Author
Pyotr Nikolaevich SOVIETOV
MIREA – Russian technological university
Russian Federation
Senior lecturer in Department of Corporate Information Systems
Russian Federation
Senior lecturer in Department of Corporate Information Systems
References
1. Hennessy J.L., Patterson D.A. A new golden age for computer architecture. Communications of the ACM, vol. 62, no. 2), 2019, pp. 48-60.
2. Sampson A., Bornholt J., Ceze, L. Hardware-software co-design: not just a cliché. Leibniz International Proceedings in Informatics, vol. 32, 2015, pp. 262–273.
3. Roselli, S.F., Bengtsson K., Åkesson K. SMT solvers for job-shop scheduling problems: Models comparison and performance evaluation. In Proc of the IEEE 14th International Conference on Automation Science and Engineering (CASE), 2018, pp. 547-552.
4. Braun M., Buchwald S., Hack S., Leißa R., Mallon C., Zwinkau A. Simple and efficient construction of static single assignment form. Lecture Notes in Computer Science, vol. 7791, 2018, pp. 102-122).
5. Gulwani S., Jha S., Tiwari A., Venkatesan R. Synthesis of loop-free programs. ACM SIGPLAN Notices, vol. 46, no. 6, 2011, pp. 62-73.
6. Bjørner N., Phan A.D., Fleckenstein L. νz-an optimizing SMT solver. Lecture Notes in Computer Science, vol. 9035, 2015, pp. 194-199).
7. Sebastiani R., Tomasi S. Optimization in SMT with LA(ℚ) Cost Functions. Lecture Notes in Computer Science, vol. 7364, 2012, pp. 484-498.
8. Almeida J.B., Barbosa M. et al. Jasmin: High-assurance and high-speed cryptography. In Proc. of the ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1807-1823.
9. Елизаров С.Г., Марков Д.С., Советов. Арифметико-логическое устройство и способ преобразования данных с использованием такого устройства. Патент на изобретение № 2681702, Российская Федерация, МПК G06F 15/76, 2019 г. / Elizarov S.G., Markov D.S., Sovetov P.N. Councils. Arithmetic logic device and method for converting data using such a device. Patent for invention No. 2681702, Russian Federation, MPK G06F 15/76, 2019.
10. Biryukov A., Perrin L.P. State of the art in lightweight symmetric cryptography. Cryptology ePrint Archive: Report 2017/511, 2017, 55 p.
11. Massalin H. Superoptimizer: a look at the smallest program. ACM SIGARCH Computer Architecture News, vol. 15, no. 5, 1987, pp. 122-126.
12. Phothilimthana P.M., Jelvis T., Shah R., Totla N., Chasins S., Bodik R. Chlorophyll: Synthesis-aided compiler for low-power spatial architectures. ACM SIGPLAN Notices, vol. 49, no. 6, 2014, pp. 396-407.
13. Buchwald S. Optgen: A generator for local optimizations. Lecture Notes in Computer Science, vol. 9031, 2015, pp. 171-189.
14. Sasnauskas R., Chen Y. et al. Souper: A synthesizing superoptimizer. arXiv preprint arXiv:1711.04422, 2017.
15. Kjellin, M. Adapting a constraint-based compiler tool to a new VLIW architecture. Master’s thesis, Uppsala University, Sweden, 2018, 74 p.
16. Koes D.R., Goldstein S.C. Near-optimal instruction selection on dags. In Proc. of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization, 2008, pp. 45-54.
17. Buchwald S., Zwinkau A. Instruction selection by graph transformation. In Proc. of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems, 2010, pp. 31-40.
18. Blindell G.H., Carlsson M., Lozano R.C., Schulte C. Complete and practical universal instruction selection. ACM Transactions on Embedded Computing Systems (TECS), 2017, vol. 16, no. 5s, pp. 1-18.
19. Frolov N., Själander M., Larsson-Edefors P., McKee S.A. Declarative, SAT-solver-based Scheduling for an Embedded Architecture with a Flexible Datapath. In Proc. of the 11th Swedish System-on-Chip Conference, 2011, 4 p.
20. Wilken K., Liu J., Heffernan M. Optimal instruction scheduling using integer programming. ACM SIGPLAN Notices, vol. 35, no. 5, 2000, pp. 121-133.
21. Malik A.M., McInnes J., Van Beek P. Optimal basic block instruction scheduling for multiple-issue processors using constraint programming. International Journal on Artificial Intelligence Tools, vol. 17, no. 01, 2008, pp. 37-54.
22. Ершов А. П. Сведение задачи распределения памяти при составлении программ к задаче раскраски вершин графов. Доклады АН СССР, том 142, no. 4, 1962 г., стр. 785-787 / Ershov A.P. Reduction of the problem of memory allocation in programming to the problem of coloring the vertices of graphs. Soviet Mathematics, vol. 3, 1962, pp. 163-165.
23. Quintão Pereira F.M., Palsberg J. Register allocation by puzzle solving. In Proc. of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, 2008, pp. 216-226.
24. Fu C., Wilken K. A faster optimal register allocator. In Proc. of the 35th Annual IEEE/ACM International Symposium on Microarchitecture, 2002, pp. 245-256.
25. Buchwald S., Zwinkau A., Bersch T. SSA-based register allocation with PBQP. Lecture Notes in Computer Science, vol. 6601. 2011, pp. 42-61.
26. Вьюкова Н.И., Галатенко В.А., Самборский С.В. Генерация кода методом точного совместного решения задач выбора и планирования команд. Программная инженерия, no. 6, 2014 г., стр. 8-15 / Vyukova N.I., Galatenko V.A., Samborskij S.V. Code Generation by Exact Joint Solution of the Instruction Selection and Scheduling Tasks. Software Endineering, no. 6, 2014, pp. 8-15 (in Russian).
27. Chang C.M., Chen C.M., King C.T. Using integer linear programming for instruction scheduling and register allocation in multi-issue processors. Computers and Mathematics with Applications, 1997, vol. 34, no. 9, pp. 1-14.
28. Lozano R.C., Carlsson M., Blindell G.H., Schulte C. Combinatorial register allocation and instruction scheduling. ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 41, no. 3, 2019, pp. 1-53.
29. Eriksson M., Kessler C. Integrated code generation for loops. ACM Transactions on Embedded Computing Systems (TECS), vol. 11, no. 1, 2012, pp. 1-24.
Review
For citations:
SOVIETOV P.N. Accelerating the Development of DSL Compilers for Specialized Processors. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(5):35-56. (In Russ.) https://doi.org/10.15514/ISPRAS-2020-32(5)-3
Email this article 