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

Abstract

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

EN: 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%.