COBAYA: Closing the compilation gap between algorithms and coarse-grained reconfigurable array architectures

[October 1st, 2007-March 31st, 2011]

	Abstract
	Embedded systems are playing an increasingly important role in nowadays life. They can be seen in a myriad of devices such as PDAs, cell phones, etc. New computer science disciplines have emerged focusing features and concepts related to the fact that small devices are becoming powerful mobile computing platforms. Such platforms are likely to rely on system-on-a-chip (SoCs) devices to give the required low energy consumption and computing demands. One of the most promising technologies to support SoCs are reconfigurable computing architectures (e.g., FPGAs) since they can implement single- or multi-processor software solutions together with dedicated hardware tailored to the application to be executed. Those architectures also provide the programming flexibility needed to upgrade applications during the life time of the product and to efficiently execute different applications. Coarse-grained reconfigurable array architectures are an important SoC component. The shorter reconfiguration times and better energy and performance efficiency on mapping computational structures make coarse-gained arrays more suitable for certain applications than “gate-level” reconfigurable architectures. Coarse-grained arrays can also be an important target template for easier mapping of algorithms on complex FPGAs, as array softcores implemented by programming the FPGA resources. Although designing reconfigurable hardware is softening, there is still the need to master digital system design in order to accomplish most requirements. However, the increasingly complexity of the architectures, the time-to-market pressures, the need for design upgrades and modifications in requirements, strongly indicate the necessity to program reconfigurable architectures at high-levels of abstraction. Efforts on compiling from software programming languages have been done for several years. However, the lack of support on FPGAs to help software compilation, their too close to gate-level basic elements, the clock frequency too dependent on place and route, seem to hamper the needed breakthrough advancements. Bearing in mind the above referred issues, this project focuses on compiler techniques and architectural schemes that can be used to bridge the gap between software programming languages and reconfigurable computing architectures. Major research efforts on reconfigurable architectures seem to have been performed without the full attention on how algorithms are coded in software programming languages and without strong evidences about the design decisions taken. We focus on the foundations established by our previous work on a supportive environment to accomplish specific array architectures that can be coupled to a microprocessor in order to complement it with more efficient support for some computing behaviors and offering an easier path to map loop kernels to those arrays. We will make research efforts to reduce the mapping difficulties by providing the array architecture with some support for dynamic scheduling, loop control schemes, data-driven behavior, etc. Compilation techniques targeted for array architectures will also be researched. An intermediate representation model will be researched. That model will use the dynamic reconfiguration capabilities of some FPGA devices both to program an architectural template during runtime execution of an application and to switch templates based on the application requirements. We also plan that certain resources of each architectural template can be conditionally configured, based on its usage by the task being executed. For validating our research we will use applications from mobile robotics as they exhibit most embedded system requirements and expose many challenges not being currently addressed. Mobile robotics need high-performance, real-time behavior, energy savings, etc. It usually demands miniaturization, frequently leading to a SoC solution. It typically needs hardware/software co-design, since for most robotic kernels using software implementations alone does not permit to achieve the required performance. Since an evaluation of the computational engines generated for mobile robotics algorithms require in-the-field experiences (due, e.g., to environment changes and real-time behavior) we will use a prototype mobile robot (consisting of FPGA boards, camera, sensors, etc) to benchmark the specified application repository.
Main Achievements
- The design of two new domain-specific languages (DSLs) - LALP and Cofi - to program FPGA-based accelerators; - An aggressive scheme for loop pipelining; - Novel techniques both at the compiler and at the hardware levels that make the mapping of computations to Coarse-Grained Reconfigurable Arrays (CGRAs) with faster; - The Megablock, a single path, repeated, trace region for great potential of optimizations and acceleration when mapped to CGRAs; - Mining of codes to identify suitable features for acceleration engines;
Funding:
- Fundação para a Ciência e a Tecnologia (FCT): http://www.fct.mctes.pt - FCT reference: PTDC/EEA-ELC/70272/2006
Contact:
João M. P. Cardoso Universidade do Porto Faculdade de Engenharia (FEUP) Departamento de Engenharia Informática Rua Dr. Roberto Frias, s/n 4200-465 Porto Portugal Email: jmpc@acm.org http://www.fe.up.pt/~jmpc

Participants

Publications

PhD, MSc Thesis, and Technical Reports

Members:

- João M. P. Cardoso, FEUP, jmpc@acm.org

- João Bispo, IST/INESC-ID, PhD student

- Rui Marcelino, U.Algarve/INESC-ID, PhD student

- Adriano Sanches, IST/INESC-ID, PhD student

- Horácio Neto, IST/INESC-ID, researcher

- Mário Véstias, researcher, ISEL/INESC-ID

- Manuel Reis, FEUP, junior researcher

- Alfredo Silvestre, FEUP, junior researcher

- Ali Azarian, FEUP, assistant researcher

Consultants:

- Eduardo Marques, USP, Brasil

- Denis Wolf, USP, Brasil

Collaborators:

- Pedro C. Diniz, ISI/USC, EUA

- Ricardo Menotti, USP/ICMC, PhD Student

- Ricardo Ferreira, Universidade de Viçosa, Brasil

- Marcio Merino Fernandes, Universidade Federal de São Carlos, Brasil

Books:

1. João M. P. Cardoso, and Pedro C. Diniz, Compilation Techniques for Reconfigurable Architectures, Springer, 234 p., Outubro de 2008, ISBN 978-0-387-09670-4. http://www.springer.com/computer/communications/book/978-0-387-09670-4

Book Chapters:

2. Pedro C. Diniz, and João M. P. Cardoso, Code Transformations for Embedded Reconfigurable Computing Architectures, in Generative and Transformational Techniques in Software Engineering III, International Summer School, GTTSE 2009, Braga, Portugal, July 6-11, 2009, Revised Papers, Fernandes, J.M.; Lämmel, R.; Visser, J.; Saraiva, J. (Eds.), LNCS 6491, Springer, Heidelberg, 2011, pp. 322-344.

3. João M. P. Cardoso, João Bispo, and Adriano K. Sanches, The Role of Programming Models on Reconfigurable Computing Fabrics, Chapter XII in the book: Behavioral Modeling for Embedded Systems and Technologies: Applications for Design and Implementation, Luís Gomes, João M. Fernandes (eds.), IGI Global, ISBN: 978-1-60566-750-8, July 2009, pp. 290-316.

Articles related to Tutorials:

4. Pedro C. Diniz, João M. P. Cardoso, “Compilation for Embedded Reconfigurable Computing Architectures,” GTTSE 2009: Pre-proceedings, Generative and Transformational Techniques in Software Engineering, João M. Fernandes, Ralf Lammel, João Saraiva, Joost Visser (eds.), June, 2009, Braga, Portugal, pp. 293-314.

Journal Papers:

5. João M. P. Cardoso, Pedro Diniz, and Markus Weinhardt, Compiling for Reconfigurable Computing: A Survey, ACM Computing Surveys (CSUR), Vol. 42, No. 4, Article 13, June 2010, pp. 1-65.

6. Ricardo Menotti, João M. P. Cardoso, Marcio M. Fernandes, and Eduardo Marques, “LALP: A Language to Program Custom FPGA-based Acceleration Engines,” in International Journal of Parallel Programming, Springer, to appear.

7. Ricardo S. Ferreira, João M. P. Cardoso, Alex Damiany, Julio Vendramini, and Tiago Teixeira, “Fast Placement and Routing by extending Coarse-Grained Reconfigurable Arrays with Omega Networks,” in Journal of Systems Architecture (JSA), Elsevier, In Press, Accepted Manuscript, Available online 15 April 2011.

International Conference/Workshop Papers:

8. João Bispo, and João M. P. Cardoso, “On identifying and optimizing instruction sequences for dynamic compilation,” in International Conference on Field-Programmable Technology (FPT’2010), Beijing, China, 8-10 Dec. 2010, pp. 437–440.

9. João Bispo, and João M. P. Cardoso, “On Identifying Segments of Traces for Dynamic Compilation,” in 20th International Conference on Field Programmable Logic and Applications (FPL’10), PhD Forum, Milano, Italy, Aug. 31st - Sept. 2nd, 2010, pp. 263-266.

10. Adriano Sanches, and João M. P. Cardoso, “On Identifying Patterns in Code Repositories to Assist the Generation of Hardware Templates,” in 20th International Conference on Field Programmable Logic and Applications (FPL’10), PhD Forum, Milano, Italy, Aug. 31st - Sept. 2nd, 2010, pp. 267-270.

11. Ricardo Menotti, João M. P. Cardoso, Marcio M. Fernandes, Eduardo Marques, “On Using LALP to Map an Audio Encoder/Decoder on FPGAs,” in IEEE International Symposium on Industrial Electronics (ISIE-2010), Bari, Italy, July 4-7, 2010.

12. Rui Marcelino, Horacio Neto, and João M. P: Cardoso, “Unbalanced FIFO Sorting for FPGA-Based Systems,” in 16th IEEE International Conference on Electronics, Circuits and Systems (ICECS’09), 13-16 December 2009, Yasmine Hammamet, Tunisia, pp. 431-434.

13. Rui Marcelino, Horacio Neto, and João M. P: Cardoso, “A Comparison of Three Representative Hardware Sorting Units,” in the 35th Annual Conference of the IEEE Industrial Electronics Society (IECON’2009), Alfandega Congress Center, Porto, Portugal, 3-5 November 2009, pp. 2805-2810.

14. R. Menotti, J. M. P. Cardoso, M. M. Fernandes, and E. Marques, “LALP: A Novel Language to Program Custom FPGA-based Accelerator Architectures,” in 21st International Symposium on Computer Architecture and High Performance Computing (SBAC–PAD’2009), Sao Paulo, Brazil, October 28-31, 2009, IEEE Computer Society Press, pp. [winner of the Julio Salek Aude Award 2009 - Best Paper of the Conference].

15. Ricardo Ferreira, Alex Assis, Tiago Teixeira, Julio Vendramini, João M. P. Cardoso, “On Simplifying Placement and Routing by Extending Coarse-Grained Reconfigurable Arrays with Omega Networks,” in International Workshop on Applied Reconfigurable Computing (ARC 2009), 16-18 March 2009, Karlsruhe, Germany, Springer LNCS 5453, pp. 145-156.

16. Carlos Morra, João Bispo, João M. P. Cardoso, and Juergen Becker, “Combining Rewriting-Logic, Architecture Generation, and Simulation to Exploit Coarse-Grained Reconfigurable Architectures,” in The Sixteenth Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM’08), Stanford, Palo Alto, CA, USA, April 14-15, 2008, IEEE Computer Society Press, pp.

17. Carlos Morra, João M. P. Cardoso, João Bispo, and Juergen Becker, “Retargeting, Evaluating, and Generating Reconfigurable Array-Based Architectures,” in 6th IEEE Symposium on Application Specific Processors (SASP 2008), 8-9 June 2008, Anaheim Convention Center, Anaheim CA, USA, pp. 34–41.

18. Rui Marcelino, Horácio Neto, João M. P. Cardoso, "Sorting Units for FPGA-Based Embedded Systems," in IFIP Working Conference on Distributed and Parallel Embedded Systems (DIPES'08), Milano, Italy, September 7-10, 2008, IFIP International Federation for Information Processing, Springer, Boston, Distributed Embedded Systems: Design, Middleware and Resources; Bernd Kleinjohann, Lisa Kleinjohann, Wayne Wolf (eds.), Volume 271, Springer, July 2008, pp. 11-22.

19. João Bispo, and João M. P. Cardoso, “A Preliminary Idea for Adapting Programs to Parallel Environments,“ In Proceedings of ACACES 2008 Poster Abstracts: Advanced Computer Architecture and Compilation for Embedded Systems, Academia Press, Ghent, Belgium, 2008. pp. 231-234.

20. Adriano K. Sanches, and João M. P. Cardoso, “Pattern-Mining over Repositories of Benchmarks to Identify and Suggest Reconfigurable Functional Units: A Preliminary Step”, In Proceedings of ACACES 2008 Poster Abstracts: Advanced Computer Architecture and Compilation for Embedded Systems, Academia Press, Ghent, Belgium, 2008. pp. 227-230.

National Conference Papers:

21. Alfredo Silvestre, and João M. P. Cardoso, “Cofi: A CFG to FSMD Programming Language and Tool,” in VII Jornadas sobre Sistemas Reconfiguráveis (REC’2011), Faculdade de Engenharia de Universidade do Porto, 3-4 de Fevereiro de 2011. (artigo longo)

22. João Bispo, and João M. P. Cardoso, “Using the MegaBlock to Partition and Optimize Programs for Embedded Systems at Runtime,” in 2º Simpósio Nacional na Área da Informática (INForum’10), 9 e 10 de Setembro de 2010, Braga – Portugal. Sessão: Sistemas Embebidos e de Tempo-Real.

23. Manuel Reis, João M. P. Cardoso, João Canas Ferreira, “The Performance Impact for Optimizing Mapping Algorithms on an FPGA-based Mobile Robot,” in VI Jornadas sobre Sistemas Reconfiguráveis (REC'2010), Universidade de Aveiro / IEETA, 4-5 de Fevereiro de 2010, pp. (artigo longo)

24. Ricardo Menotti, João M. P. Cardoso, Márcio M. Fernandes, Eduardo Marques, “Uma Linguagem para Geração Automática de Arquitecturas Baseadas em Computação Reconfigurável,” in VI Jornadas sobre Sistemas Reconfiguráveis (REC'2010), Universidade de Aveiro / IEETA, 4-5 de Fevereiro de 2010, pp. (artigo longo)

25. Tiago Teixeira, Ricardo Ferreira, João M. P. Cardoso, “Explorando com Meta-Heurística o Espaço de Projeto de Arquiteturas Reconfiguráveis de Grão Grosso,” in V Jornadas sobre Sistemas Reconfiguráveis - REC'2009, Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa, Monte de Caparica, Portugal, 5-6 Fevereiro 2009.

26. Ricardo Ferreira, Alex Damiany, Julio Vendramini, João M. P. Cardoso, “Mapeamento em Arquitecturas Reconfiguráveis de Grão Grosso com Redes Multiestágios,” in V Jornadas sobre Sistemas Reconfiguráveis - REC'2009, Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa, Monte de Caparica, Portugal, 5-6 Fevereiro 2009.

PhD Thesis:

27. Ricardo Menotti, LALP: uma linguagem para exploração do paralelismo de loops em computação reconfigurável, Doutorado pelo ICMC da USP do Brasil. Supervisor: Prof. Eduardo Marques (ICMC/USP, São Paulo, Brasil). Co-supervisor: João M. P. Cardoso, May 2010.

MSc Thesis:

28. Manuel Luís Campos Reis, “Robô com Unidade de Processamento Principal implementada em FPGAs,” Co-adviser: Prof. João Canas Ferreira, Final MSc Project, Mestrado Integrado em Engenharia Electrotécnica e de Computadores (MIEEC), Faculdade de Engenharia de Universidade do Porto (FEUP), Porto, July 2009.

29. Tiago José Rocha Alves da Costa, “Methods for Dynamic Identification of Program Control-Flow Structures for FPGA-based Systems,” Co-adviser: Prof. João Canas Ferreira, Final MSc Project, Mestrado Integrado em Engenharia Electrotécnica e de Computadores (MIEEC), Faculdade de Engenharia de Universidade do Porto (FEUP), Porto, July 2009.

Technical Reports:

1. Alfredo Silvestre, and João M. P. Cardoso, “Cofi: A CFG to FSMD Programming Language and Tool,” Technical Report, COBAYA Project, Universidade do Porto, Faculdade de Engenharia (FEUP), February 2011.

2. Ali Azarian, and João M. P. Cardoso, “Pipelining Producer-Consumer Tasks using Custom Multi-Core Architectures,” Technical Report, COBAYA Project, Universidade do Porto, Faculdade de Engenharia (FEUP), March 2011.

3. Manuel Reis, COBAYA ROBOT: COBAYA-R, User’s Manual, Technical Report, COBAYA Project, Universidade do Porto, Faculdade de Engenharia (FEUP), December 2009.

4. Manuel Reis, The Performance Impact for Optimizing Mapping Algorithms on an FPGA-based Mobile Robot, Technical Report, COBAYA Project, Universidade do Porto, Faculdade de Engenharia (FEUP), December 2009.

5. João M. P. Cardoso, Ricardo Menotti, Alfredo Silvestre, Marcio M. Fernandes and Eduardo Marques, Comparing Loop Pipelining Alternatives for Reconfigurable Hardware, Technical Report, COBAYA Project, Universidade do Porto, Faculdade de Engenharia (FEUP), December 2009.

6. João Bispo, A 1-D Coarse-Grained Reconfigurable Array with Floating-Point Units, Technical Report, COBAYA Project, Universidade do Porto, Faculdade de Engenharia (FEUP), May 2009.