4551
правка
Технологическое отображение последовательной схемы: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение последовательной схемы (посмотреть исходный код)
Версия от 18:19, 11 апреля 2019
, 11 апреля 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 96: | Строка 96: | ||
'''Этап разметки''' | '''Этап разметки''' | ||
После получения всех K-разрезов алгоритм оценивает разрезы, основываясь на последовательном времени прихода (или l-значениях), представляющем собой расширение традиционного времени прихода, чтобы рассчитать эффект от ресинхронизации [6,8]. | |||
FindMinLabels(N) | |||
foreach node v in N do l(v) <^ w w,-ф | |||
while (имеются обновления меток) do | |||
foreach node v in N do | |||
l(v) ( minc2C(v)fmaxfl(u) – d ф + 1jud ec}} | |||
if v является PO и l(v) > ф, return неуспешно | |||
return успешно | |||
Рисунок 5. Технологическое отображение последовательной схемы. Процедура разметки | |||
0 \{а°} :0 fb0g : 0 {Р} :0 {х0} : -1 {У0}: О {z° } :- 1 fo0g :-1 | |||
1 \ {а0} : 1 z1g:0 0 ( 0 0 | |||
< Q Q z0g : 1 {о1 б1! :0 fz0g :0 | |||
Рисунок 6. Технологическое отображение последовательной схемы. Пример разметки | |||
Процедура разметки стремится найти метку для каждой вершины, как схематически показано на рис. 5, где wv обозначает вес кратчайших пар из первичных входов к вершине v. | |||
На рис. 6 изображены итерации вычисления меток для схемы на рис. 1 (1) в предположении, что целевая продолжительность цикла ф = 1 и вершины оцениваются в порядке i, x, y, z, o. В таблице отражены как текущая метка, так и соответствующий разрез для каждой вершины. В данном примере после первой итерации ни одна из меток не меняется, и выполнение процедуры завершается. | |||
Можно показать, что процедура разметки остановится после не более чем n(n - 1) итераций [ ]. Следующая лемма связывает метки и отображение: | |||
Лемма 2. N имеет отображение с продолжительностью цикла ' в том и только том случае, если процедура разметки возвращает значение «успех». | |||
'''Этап отображения''' | |||
После того успешного вычисления меток для всех вершин можно построить отображение, начиная с первичных выходов. В каждой вершине v процедура выбирает разрез, реализующий метку вершины, а затем переходит к выбору разреза для u, если ud входит в состав разреза, выбранного для v. На ребре, идущем из таблицы LUT для u к LUT для v, добавляется d триггеров. Для схемы на рис. 1 (1) сгенерированное отображение, основанное на метках, найденных на рис. 6, представляет собой сеть на рис. 2 (2). | |||
Для получения отображения с целевой продолжительностью цикла ' таблица LUT для v может быть ресинхронизирована на \l{v)l<p~\ — 1. Для схемы на рис. 1 (1) окончательное отображение после ресинхронизации представлено на рис. 2 (3). | |||
== Применение == | |||
Данный алгоритм может применяться для отображения технологически независимой булевой сети на сеть, состоящую из ячеек из библиотеки логических элементов целевой технологии. Концепция и структура являются достаточно общими для того, чтобы их можно было адаптировать для изучения других оптимизаций схем, таких как кластеризация и реструктуризация последовательных схем. | |||
== См. также == | |||
* [[Ресинхронизация схемы]] | |||
* [[Технологическое отображение ППВМ]] | |||
* [[Технологическое отображение]] | |||
== Литература == | |||
1. Cong, J., Ding, Y.: FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Trans. on Comput. Aided Des. of Integr. Circuits and Syst., 13(1), 1-12(1994) | |||
2. Cong, J., Wu, C.: FPGA Synthesis with Retiming and Pipelining for Clock Period Minimization of Sequential Circuits. ACM/IEEE Design Automation Conference (1997) | |||
3. Keutzer, K.: DAGON: Technology Binding and Local Optimization by DAG Matching. ACM/IEEE Design Automation Conference (1987) | |||
4. Leiserson, C.E., Saxe, J.B.: Retiming Synchronous Circuitry. Algorithmica6,5-35(1991) | |||
5. Mishchenko, A., Chatterjee, S., Brayton, R., Ciesielski, M.: An integrated technology mapping environment. International Workshop on Logic Synthesis (2005) | |||
6. Pan, P.: Continuous Retiming: Algorithms and Applications. IEEE International Conference on Computer Design, pp. 116-121. (1997) | |||
7. Pan, P., Lin, C.C.: A New Retiming-based Technology Mapping Algorithm for LUT-based FPGAs. ACM International Symposium on Field-Programmable Gate Arrays (1998) | |||
8. Pan, P., Liu, C.L.: Optimal Clock Period FPGA Technology Mapping for Sequential Circuits. ACM/IEEE Design Automation Conference, June (1996) | |||
9. Pan, P., Liu, C.L.: Optimal Clock Period FPGA Technology Mapping for Sequential Circuits. ACM Trans. on Des. Autom. of Electron. Syst., 3(3), 437-462 (1998) | |||