Problem Oriented Approach to Hardware-Assisted Algorithm Design in C: A Case Study for Scheduling, Placement and Routing

• Lucas Mucida Universidade Federal de Viçosa
• Vincius Lopes Universidade Federal de Viçosa
• Waldir Meireles Universidade Federal de Viçosa
• Ricardo Ferreira Universidade Federal de Viçosa

Resumo

This work presents a problem oriented approach to introduce the design of hardware assisted algorithms. A scheduling, placement and routing problem for coarse-grained reconfigurable architecture (CGRA) has been chosen to ilustrate our approach. The algorithm is implemented in C language by using simple rules and a finite state machine model. The algorithm's execution time is estimated by the number of clock cycles. For the proposed problem, the results have shown that the algorithm could be efficiently implemented in a FPGA to be used in runtime systems.

Palavras-chave: Hardware, Algorithm design and analysis, Software, Routing, Field programmable gate arrays, Pipelines, Pipeline processing