Partitioning Algorithm Based on Simulated Annealing for Reconfigurable Systems-on-Chip

 
Chochaev R., Khvatov V.M., Gavrilov S.V., Zheleznikov D.A. (IPPM RAS)
 
Abstract - Partitioning is one of the most significant steps in the reconfigurable systems-on-chip design flow. High-quality partitioning ensures effective placement and routing steps. The goals of circuit partitioning are following: a) achieving the high density by minimizing the number of groups; b) decreasing time delays by localizing time-critical connections within a group and using fast local routing resources. There are several popular partitioning problem solutions, such as top-down decomposition algorithms, bottom-up clustering and different heuristic algorithms. In this paper we present a simulated annealing approach for partitioning optimization for the reconfigurable system-on-chip (RSoC) based on the “Almaz-14” FPGA. This RSoC contains more than twenty thousand logic elements arranged into groups of size 256. It has typical island architecture with rich local and poor global routing resources therefore partitioning step becomes vital for successful placement and routing. In our work we use simulated annealing for optimization the initial solution generated by iRAC clustering algorithm. The cost function is based on Rent's rule and it is a function of: (1) Rent’s exponent of each cluster, (2) number of LE in each cluster, (2) total number of LE in the circuit and (3) total number of clusters. Such parameters as annealing schedule, initial and final temperature values were obtained experimentally. We analyze and compare our algorithm with three popular approaches: basic clustering; Kernighan-Lin partitioning algorithm; clustering algorithm iRAC. Each method was verified on the set of benchmark circuits ISCAS-85 and ISCAS-89. The algorithms were configured in such way to divide the benchmark circuits into an equal number of clusters. Benchmark circuits were placed using the algorithm based on the simulated annealing method with modified cost function and routed by using the modified algorithm A* with stop at the first iterations of rip-up and reroute procedure. Experimental results demonstrate that presented algorithm with initial placement generated by iRAC algorithm has comparable effectiveness to other partitioning algorithms.

Keywords - design automation; clustering; Rent’s rule; Kernighan-Lin algorithm; Simulated Annealing.

Алгоритм декомпозиции на основе метода имитации отжига для реконфигурируемых систем на кристалле

 
Чочаев Р., Хватов В.М., Гаврилов С.В., Железников Д.А. (Институт проблем проектирования в микроэлектронике РАН, г. Зеленоград)
 
Аннотация - Этап декомпозиции является одним из ключевых в маршруте проектирования схем в базисе реконфигурируемых систем на кристалле (РСнК). Декомпозиция позволяет повысить эффективность последующих этапов размещения элементов и трассировки межсоединений. На этапе декомпозиции решаются следующие задачи: а) повышение плотности компоновки за счет уменьшения количества создаваемых подсхем, б) уменьшение временных задержек за счет локализации критических путей внутри подсхем и использования быстрых локальных коммутационных ресурсов. На данный момент можно выделить следующие группы алгоритмов декомпозиции: (1) нисходящие алгоритмы, (2) восходящие или алгоритмы кластеризации, (3) различные эвристические алгоритмы. В данной работе представлен алгоритм на основе метода имитации отжига для оптимизации результатов декомпозиции в маршруте проектирования схем в базисе РСнК «Алмаз-14» с целевой оценочной функцией, основанной на правиле Рента. Приведено численное сравнение предложенного алгоритма со следующими тремя популярными методами: базовым алгоритмом кластеризации, алгоритмом Кернигана-Лина и алгоритмом кластеризации iRAC. Результаты численных экспериментов на наборах тестовых схем ISCAS-85 и ISCAS-89 показывают, что представленный алгоритм оптимизации в комбинации с алгоритмом iRAC имеет лучшую эффективность по сравнению с другими алгоритмами декомпозиции.

Ключевые слова - автоматизация проектирования; кластеризация; правило Рента; алгоритм Кернигана-Лина; имитация отжига.