Разработка компиляторов предметно-ориентированных языков для спецпроцессоров

В составе современных вычислительных систем все чаще используются аппаратные спецпроцессоры, программируемые на предметно-ориентированных языках. Популярность набирает подход compiler-in-the-loop, предполагающий совместную разработку спецпроцессора и компилятора. При этом традиционный инструментарий (GCC и LLVM) оказывается недостаточным для быстрой разработки оптимизирующих компиляторов, порождающих целевой код нерегулярной архитектуры со статическим параллелизмом операций. В статье предлагается использовать методы решения NP-полных задач для реализации машинно-зависимых фаз компиляции. Фазы осуществляются на основе сведения к задаче SMT, что дает возможность избавиться при построении компилятора от эвристических и приближенных подходов, требующих трудоемкой программной реализации. В частности, с использованием SMT-решателя предлагается реализовать синтез правил машинно-зависимой оптимизации, выбор команд, планирование команд и распределение регистров. Обсуждаются вопросы апробации разработанных методов и алгоритмов на примере компилятора для спецпроцессора с набором команд, ускоряющим реализации алгоритмов низкоресурсных шифров из области Интернета вещей. Полученные результаты компиляции и программного моделирования для 8 криптоалгоритмов и 3 вариантов спецпроцессора (CISC, VLIW и вариант delayed load) демонстрируют практическую применимость предложенного подхода.

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.