Evaluating a Dynamic and a Modulo Scheduling-based Static Approach for Configuration Generation in CGRA Accelerators
Keywords:
software pipelining, modulo scheduling, loops, reconfigurable architecturesAbstract
With the increasing complexity of the applications, there is an urgent need for solutions to improve the performance
of these applications. It is noted that the loops present in some of them are responsible for up to 71% of the code execution time. So, optimizing the loop’s execution it is possible to accelerate the execution of the whole application. This performance gain can be obtained with the use of software pipelining. This work proposes RENOIR, a tool that uses software pipelining technique through the implementation of the modulo scheduling algorithm, developed in software, that acts in the generation of configurations for a coarse-grained reconfigurable architecture (CGRA). RENOIR is implemented in a compiler, which receives an application and generates a code that can run on a gem5 implementation of a CGRA that includes a RISC-V microprocessor and a thin reconfigurable array. The results show that all the applications tested achieved an improvement in performance, reaching a gain of 2,32x in certain applications.
Downloads
References
H. Park, Y. Park, and S. Mahlke, “Polymorphic pipeline array: A flexible multicore accelerator with virtualized execution for mobile multimedia applications,” in Proceedings of the 42Nd Annual IEEE/ACM International Symposium on Microarchitecture, ser. MICRO 42. New York, NY, USA: ACM, 2009, pp. 370–380. [Online]
A. Hatanaka and N. Bagherzadeh, “A modulo scheduling algorithm for a coarse-grain reconfigurable array template,” in 2007 IEEE International Parallel and Distributed Processing Symposium, March 2007, pp. 1–8.
V. H. Allan, R. B. Jones, R. M. Lee, and S. J. Allan, “Software pipelining,” ACM Comput. Surv., vol. 27, no. 3, pp. 367–432, Sep. 1995. [Online]. Available: http://doi.acm.org/10.1145/212094.212131
B. R. Rau, “Iterative modulo scheduling: An algorithm for software pipelining loops,” in Proceedings of the 27th Annual International Symposium on Microarchitecture, ser. MICRO 27. New York, NY, USA: ACM, 1994, pp. 63–74. [Online]. Available: http://doi.acm.org/10.1145/192724.192731
J. V. Couto and S. R. Fernandes, “Generating optimized code for parallelism exploitation to an unconventional architecture,” IEEE Latin America Transactions, vol. 15, no. 10, pp. 1967–1976, 2017
B. Mei, S. Vernalde, D. Verkest, H. D. Man, and R. Lauwereins, “Dresc: a retargetable compiler for coarse-grained reconfigurable architectures,” in 2002 IEEE International Conference on Field-Programmable Technology, 2002. (FPT). Proceedings., Dec 2002, pp. 166–173.
R. Gnanaolivu, T. S. Norvell, and R. Venkatesan, “Mapping loops onto coarse-grained reconfigurable architectures using particle swarm optimization,” in 2010 International Conference of Soft Computing and
Pattern Recognition, Dec 2010, pp. 145–151.
H. Park, K. Fan, S. Mahlke, T. Oh, H. Kim, and H. s. Kim, “Edge-centric modulo scheduling for coarse-grained reconfigurable architectures,” in 2008 International Conference on Parallel Architectures and Compilation Techniques (PACT), Oct 2008, pp. 166–176.
T. Oh, B. Egger, H. Park, and S. Mahlke, “Recurrence cycle aware modulo scheduling for coarse-grained reconfigurable architectures,” in Proceedings of the 2009 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, ser. LCTES
’09. New York, NY, USA: ACM, 2009, pp. 21–30. [Online]. Available: http://doi.acm.org/10.1145/1542452.1542456
M. Hamzeh, A. Shrivastava, and S. Vrudhula, “Epimap: Using epimorphism to map applications on cgras,” in DAC Design Automation Conference 2012, June 2012, pp. 1280–1287.
L. Chen and T. Mitra, “Graph minor approach for application mapping on cgras,” in 2012 International Conference on Field-Programmable Technology, Dec 2012, pp. 285–292.
R. Ferreira, V. Duarte, W. Meireles, M. Pereira, L. Carro, and S. Wong, “A just-in-time modulo scheduling for virtual coarse-grained reconfigurable architectures,” in 2013 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation(SAMOS), July 2013, pp. 188–195.
R. Ferreira, W. Denver, M. Pereira, J. Quadros, L. Carro, and S. Wong, “A run-time modulo scheduling by using a binary translation mechanism,” in 2014 International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS XIV), July 2014, pp. 75–82.
K. Telschig and A. Knapp, “Towards safe dynamic updates of distributed embedded applications in factory automation,” in 2017 22nd IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), 2017, pp. 1–4.
——, “Synchronous reconfiguration of distributed embedded applications during operation,” in 2019 IEEE International Conference on Software Architecture (ICSA), 2019, pp. 121–130.
M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown, “Mibench: A free, commercially representative embedded benchmark suite,” in Proceedings of the Fourth Annual IEEE
International Workshop on Workload Characterization. WWC-4 (Cat. No.01EX538), 2001, pp. 3–14.
W. R. Azevedo Dias and E. D. Moreno, “Code compression using huffman and dictionary-based pattern blocks,” IEEE Latin America Transactions, vol. 13, no. 7, pp. 2314–2321, 2015.
W. R. Azevedo Dias, E. D. Moreno, and R. da Silva Barreto, “Architectural characterization and code compression in embedded processors,” IEEE Latin America Transactions, vol. 10, no. 4, pp. 1865–1873, 2012.
F. Silva Junior, J. P. S. Patrocinio, I. S. Silva, and R. P. Jacobi, “Design space exploration of a reconfigurable accelerator in a heterogeneous multicore,” in 33rd Symposium on Integrated Circuits and Systems
Design, 2020.
A. Podobas, K. Sano, and S. Matsuoka, “A survey on coarse-grained reconfigurable architectures from a performance perspective,” IEEE Access, vol. 8, pp. 146 719–146 743, 2020.
E. S. CARVALHO, “Cognite - um framework para construc¸ao de geradores de codigo para arquiteturas multi-core,” Master’s thesis, Universidade ´Federal do Piau´ı, Piau´ı, 2018.
H. Singh, Ming-Hau Lee, Guangming Lu, F. J. Kurdahi, N. Bagherzadeh, and E. M. Chaves Filho, “Morphosys: an integrated reconfigurable system for data-parallel and computation-intensive applications,” IEEE Transactions on Computers, vol. 49, no. 5, pp. 465–481, May 2000.
T. J. Callahan and J. Wawrzynek, “Adapting software pipelining for reconfigurable computing,” in Proceedings of the 2000 International Conference on Compilers, Architecture, and Synthesis for Embedded
Systems, ser. CASES ’00. New York, NY, USA: ACM, 2000, pp. 57–64. [Online]. Available: http://doi.acm.org/10.1145/354880.354889
J. R. Hauser and J. Wawrzynek, “Garp: a mips processor with a reconfigurable coprocessor,” in Proceedings. The 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines Cat. No.97TB100186), 1997, pp. 12–21.
F. Silva Junior, I. S. Silva, and R. P. Jacobi, “Evaluation and proposal of a lightweight reconfigurable accelerator for heterogeneous multicore,” IEEE Latin America Transactions, Early Access. [Online]. Available:
https://latamt.ieeer9.org/index.php/transactions/article/view/3717
D. A. Patterson and J. L. Hennessy, Computer Architecture: A Quantitative Approach. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1990.
N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti, R. Sen, K. Sewell, M. Shoaib, N. Vaish, M. D. Hill, and D. A. Wood, “The gem5 simulator,” SIGARCH Comput. Archit. News, vol. 39, no. 2, pp. 1–7, Aug. 2011.
[Online]. Available: http://doi.acm.org/10.1145/2024716.2024718
