Scheduling of Iterative Algorithms with Matrix Operations for Efficient FPGA Design—Implementation of Finite Interval Constant Modulus Algorithm

0075925 - ÚTIA 2007 RIV NL eng J - Journal Article
Šůcha, P. - Hanzálek, Z. - Heřmánek, Antonín - Schier, Jan
Scheduling of Iterative Algorithms with Matrix Operations for Efficient FPGA Design—Implementation of Finite Interval Constant Modulus Algorithm.
[Rozvrhování iterativních algoritmů s maticovými operacemi pro efektivní FPGA návrh - Implementace Finite interval Constant Modulus algoritmu.]
Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology. Roč. 46, č. 1 (2007), s. 35-53. ISSN 0922-5773
R&D Projects: GA AV ČR(CZ) 1ET300750402; GA MŠMT(CZ) 1M0567; GA MPO(CZ) FD-K3/082
Institutional research plan: CEZ:AV0Z10750506
Keywords : high-level synthesis * cyclic scheduling * iterative algorithms * imperfectly nested loops * integer linear programming * FPGA * VLSI design * blind equalization * implementation
Subject RIV: BA - General Mathematics
Impact factor: 0.449, year: 2007
http://www.springerlink.com/content/t217kg0822538014/fulltext.pdf

This paper deals with the optimization of iterative algorithms with matrix operations or nested loops for hardware implementation in FPGA, using Integer Linear Programming (ILP). The method is demonstrated on an implementation of the FI-CMA. Two arithmetic libraries were used in the FPGA implementation: one based on the logarithmic number system, the other using floating-point number system in the IEEE format. Both libraries use pipelined modules. Traditional approaches to the scheduling of nested loops lead to a relatively large code, which is unsuitable for FPGA design. This paper presents a new high-level synthesis methodology, which models both, iterative loops and imperfectly nested loops, by means of the system of linear inequalities. Moreover, memory access is considered as an additional resource constraint. Since the solutions of ILP formulated problems are known to be computationally intensive, an important part of the article is devoted to the reduction of the problem size.

Článek se zabývá optimalizací iterativních algoritmů s maticovými operacemi nebo vnořenými smyčkami pro efektivní implementaci na FPGA pomocí ILP metod. Metoda je demonstrována na příkladu FI-CMA algoritmu. Pro implementaci byli použity dvě různé aritmetické knihovny: logaritmický numerický systém a standardní IEEE floating point knihovna. Obě knihovny používají pipelinovaná makra. Tento příspěvek presentuje novou metodologii návrhu, která modeluje jak vnořené tak i nedokonale vnořené smyčky použitím systému nerovnic. Navíc počet přístupů do paměti je zadán jako dodatečné omezení. Jelikož řešení pomocí ILP metod je známo svojí výpočetní náročností, podstatná část příspěvku je věnována redukci velikosti problému
Permanent Link: http://hdl.handle.net/11104/0143157