Исследование оптимальности реализации технологического картографирования на ПЛИС типа FPGA

Abstract

Эта статья призвана определить оптимальность алгоритмов технического картографирования FPGA технологий. Разрабатывается алгоритм, основанный на технологии SAT (Boolean satis f ability), который позволяет преобразовать маленькую подсхему с минимально возможным использованием числа генераторов логических функций (LUTs - Look Up Table ). Эта технология применена к маленьким частям схем, которые уже были преобразованы при помощи лучших алгоритмов картографирования FPGA. В большинстве случаях, оптимальное преобразование (картографирование) подсхем позволило использовать меньшее количество LUT, по сравнению с исходным алгоритмом преобразования. Показывается, что для некоторых схем суммарное усовершенствование занимаемого пространства может достигать 67%.

This article aims to define FPGA technology technical mapping algorithms optimality. The algorithm is developed that based on SAT technology (Boolean satis f ability), which allows to convert a small sub-circuit with the lowest possible number of logic functions generators (LUTs - Look Up Table). This technology is applied to small schemes parts which have been converted using the best FPGA mapping algorithms. In this paper we present a novel method for constructing arbitrarily large circuits that have known optimal solutions after technology mapping. Using these circuits and their derivatives (called LEKO and LEKU, respectively), we show that although leading FPGA technology mapping algorithms can produce close to optimal solutions, the results from the entire logic synthesis flow (logic optimization + mapping) are far from optimal. The best industrial and academic FPGA synthesis flows are around 140 times larger in terms of area on average, and in some cases as much as 500 times larger on LEKU examples. These results clearly indicate that there is much room for further research and improvement in FPGA synthesis. In most cases, the optimal subcircuits transformation (mapping) makes possible to use a smaller number of the LUT, compared with the initial conversion algorithm. It is shown that for some schemes the total occupied space improvement can reach 67%.