4511
правок
Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 12:17, 12 сентября 2018
, 12 сентября 2018→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 129: | Строка 129: | ||
== Применение == | == Применение == | ||
Алгоритм FlowMap использовался как центральный структурный компонент более сложных алгоритмов синтеза логики ППВМ и технологического отображения. Существует множество различных вариантов, подходящих для удовлетворения различных потребностей практических приложений. Некоторые из них вкратце описаны далее. Более детальное изложение вариантов и приложений можно найти в работах [1, 3]. | |||
'''Более сложные модели задержки''' | |||
С минимальными изменениями алгоритм может быть применен для модели с неединичными задержками, в которой задержки вершин и/или ребер могут различаться, оставаясь статичными. Модели с динамическими задержками, в которых задержка сети определяется ее структурой после отображения, неприменимы к данному алгоритму. Оптимальное по задержке отображение с использованием динамической модели задержки на деле является NP-полным [3]. | |||
'''Более сложные архитектуры''' | |||
Алгоритм может быть адаптирован к более сложным архитектурам ППВМ, нежели гомогенные массивы таблиц K-LUT. К примеру, отображение для ППВМ с двумя размерами таблиц LUT может быть выполнено посредством вычисления конуса для каждого размера и динамического выбора лучшего варианта. | |||
'''Несколько целей оптимизации''' | |||
Алгоритм ориентирован на минимизацию задержки, однако можно использовать его для минимизации площади (в терминах количества выбранных конусов) и других целей при помощи адаптации критерия выбора разреза. Исходный алгоритм решает задачу минимизации площади при помощи максимизации объема разрезов; значительно более сильная минимизация может быть достигнута за счет рассмотрения большего количества K-допустимых разрезов и осуществления рациональных выборов – например, допущения разрезов большей высоты вдоль некритических путей и т. п. Однако нахождение оптимальной площади является NP-полной задачей. | |||
'''Интеграция с другими техниками оптимизации''' | |||
Алгоритм может сочетаться с другими типами оптимизации, включая ресинхронизацию, повторный логический синтез и физический синтез. | |||
== См. также == | |||
* [[Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока]] | |||
* [[Кластеризация на основе эффективности]] | |||
* [[Технологическое отображение последовательных схем]] | |||
== Литература == | |||
Алгоритм FlowMap в более детальном виде и с экспериментальными результатами представлен в работе [2]. Общею информацию о ППВМ можно найти в [5]. Понятия и алгоритмы расчета сетевого потока адекватно изложены в [4]. Комплексный обзор подходов к автоматизации проектирования ППВМ, включающий множество вариаций и способов применения алгоритма FlowMap и других алгоритмов, можно найти в [1, 3]. | |||
1. Chen, D., Cong, J., Pan, P.: FPGA design automation: a survey. | |||
Foundations and Trends in Electronic Design Automation, vol 1, no 3. Now Publishers, Hanover, USA (2006) | |||
2. Cong, J., Ding, Y.: An optimal technology mapping algorithm for delay optimization in lookup-table based FPGA designs, Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 48-53. San Jose, USA (1992) | |||
3. Cong, J., Ding, Y.: Combinational logic synthesis for LUT based field programmable gate arrays. ACM Trans. Design Autom. Electron. Sys. 1(2): 145-204 (1996) | |||
4. Tarjan, R.: Data Structures and Network Algorithms. SIAM. Philadelphia, USA (1983) | |||
5. Trimberger, S.: Field-Programmable Gate Array Technology. Springer, Boston, USA (1994) | |||