1294
правки
Ресинхронизация схемы: инкрементный подход: различия между версиями
Материал из WEGA
Ресинхронизация схемы: инкрементный подход (посмотреть исходный код)
Версия от 04:15, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 101: | Строка 101: | ||
<math>\exist \; (u, v) \in E: r[u] - r[v] > w[u, v]</math> | <math>\exist \; (u, v) \in E: r[u] - r[v] > w[u, v]</math> | ||
<math>\to r[v] := r[u] - w[u, v]</math> | <math>\to r[v] := r[u] - w[u, v]</math> | ||
<math>od \{ P0 \and P1 \and P2 \and P3 \} \;</math> | <math>od \{ P0 \and P1 \and P2 \and P3 \}. \;</math> | ||
| Строка 107: | Строка 107: | ||
|- | |- | ||
! Название | ! Название | ||
! Кол-во | ! Кол-во | ||
! colspan="2" | Длительность такта | ! colspan="2" | Длительность такта | ||
! <math>\sum r</math> | ! <math>\sum r</math> | ||
! Кол-во | ! Кол-во | ||
! Время | ! Время | ||
! colspan="2" | ASTRA | ! colspan="2" | ASTRA | ||
|- | |- | ||
! | ! | ||
! | ! вентилей | ||
! до | ! до | ||
! после | ! после | ||
! | ! | ||
! | ! обновлений | ||
! | ! | ||
! A(s) | ! A(s) | ||
| Строка 229: | Строка 229: | ||
Для завершения разработки алгоритма осталось реализовать проверку <math>\neg P3</math>. Из предыдущего обсуждения мы уже знаем, что из <math>\neg P3</math> следует, что существует такая вершина u, что <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math> после каждого увеличения r[v]. Это означает, что <math>max_{v \in V} \; r[v] - r'[v]</math> не будет увеличиваться. Иначе говоря, существует по меньшей мере одна вершина v, у которой r[v] не будет меняться. До увеличения r[v] имеет место соотношение <math>w_{u \rightsquigarrow v} - r[u] + r[v] \le 0 \;</math>, где <math>w_{u \rightsquigarrow v} \ge 0 \;</math> – исходное количество регистров на | Для завершения разработки алгоритма осталось реализовать проверку <math>\neg P3</math>. Из предыдущего обсуждения мы уже знаем, что из <math>\neg P3</math> следует, что существует такая вершина u, что <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math> после каждого увеличения r[v]. Это означает, что <math>max_{v \in V} \; r[v] - r'[v]</math> не будет увеличиваться. Иначе говоря, существует по меньшей мере одна вершина v, у которой r[v] не будет меняться. До увеличения r[v] имеет место соотношение <math>w_{u \rightsquigarrow v} - r[u] + r[v] \le 0 \;</math>, где <math>w_{u \rightsquigarrow v} \ge 0 \;</math> – исходное количество регистров на одном пути из u в v, в результате чего неравенство <math>r[v] - r[u] \le 1 \;</math> остается верным даже после увеличения r[v]. Из этого следует, что будет по меньшей мере i + 1 вершин, у которых r не превышает i для <math>0 \le i < |V| \;</math>. Иными словами, алгоритм может по-прежнему увеличивать r, и когда какое-либо значение r достигнет |V|, это покажет, что условие P3 удовлетворяется. Таким образом, полный алгоритм имеет следующую форму: | ||
<math>r, t, \phi := 0, d, \infty \;</math> | <math>r, t, \phi := 0, d, \infty \;</math> | ||
do {P1} | do {P1} | ||
<math>\exist (u, v) \in E: r[u] - r[v] = w[u, v]</math> | <math>\exist \; (u, v) \in E: r[u] - r[v] = w[u, v]</math> | ||
<math>\and \; t[v] - t[u] < d[v] \to t[v] := t[u] + d[v]</math> | <math>\and \; t[v] - t[u] < d[v] \to t[v] := t[u] + d[v]</math> | ||
<math>(\forall \; v \in V: r[v] < |V|)</math> | <math>(\forall \; v \in V: r[v] < |V|)</math> | ||
| Строка 240: | Строка 240: | ||
<math>\and \; \exist \; v \in V: t[v] \ge \phi \to r[v], t[v] := r[v] + 1, d[v]</math> | <math>\and \; \exist \; v \in V: t[v] \ge \phi \to r[v], t[v] := r[v] + 1, d[v]</math> | ||
<math>P0 \and P2 \and \phi > max(t) \to \phi := max(t)</math> | <math>P0 \and P2 \and \phi > max(t) \to \phi := max(t)</math> | ||
<math>\exist (u, v) \in E: r[u] - r[v] > w[u, v]</math> | <math>\exist \; (u, v) \in E: r[u] - r[v] > w[u, v]</math> | ||
<math>\to r[v] := r[u] - w[u, v]</math> | <math>\to r[v] := r[u] - w[u, v]</math> | ||
<math>od \{ P0 \and P1 \and P2 \and P3 \} \;</math>. | <math>od \{ P0 \and P1 \and P2 \and P3 \} \;</math>. | ||
| Строка 254: | Строка 254: | ||
== Применение == | == Применение == | ||
В базовом алгоритме оптимальность P3 проверяется условием <math>r[v] \ge |V| \;</math>. Однако в большинстве случаев условие оптимальности можно обнаружить намного раньше. Поскольку при каждом возрастании r[v] должна существовать «вершина-хранитель» u, такая, что после выполнения действия будет верно неравенство <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math>. | В базовом алгоритме оптимальность P3 проверяется условием <math>r[v] \ge |V| \;</math>. Однако в большинстве случаев условие оптимальности можно обнаружить намного раньше. Поскольку при каждом возрастании r[v] должна существовать «вершина-хранитель» u, такая, что после выполнения действия будет верно неравенство <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math>. Следовательно, если ввести указатель из v на u при увеличении r[v], указатели не смогут образовать цикл согласно <math>\neg P3</math>. Фактически указатели образуют лес, в котором корни имеют значение r = 0, а потомок может иметь значение r, не более чем на 1 превышающее значение его предка. Использование цикла указателей как свидетельство верности P3 вместо <math>r[v] \ge |V| \;</math>, можно значительно повысить практическую эффективность алгоритма. | ||
== Открытые вопросы == | |||
Ресинхронизация обычно используется для оптимизации длительности цикла либо количества регистров в схеме. Описанный алгоритм решает только задачу ресинхронизации с достижением минимальной длительности. Задачу ресинхронизации с достижением минимального количества регистров для заданной длительности цикла решили Лейзерсон и Сакс [1], она представлена в соответствующей статье. Их алгоритм сводит задачу к двойственной проблеме поиска сетевого потока с минимальной стоимостью в плотном графе. Остается открытым любопытный вопрос – можно ли разработать эффективный итеративный алгоритм для решения задачи о минимальном количестве регистров, схожий с алгоритмом Чжоу. | |||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Результаты были опубликованы Чжоу [3] по итогам сравнения времени выполнения алгоритма с эффективной эвристикой под названием ASTRA [ ]. Результаты прогона на эталонных тестах ISCAS89 представлены в таблице 1 из работы [3]; столбцы A и B таблицы отражают время выполнения двух этапов ASTRA. | Результаты были опубликованы Чжоу [3] по итогам сравнения времени выполнения алгоритма с эффективной эвристикой под названием ASTRA [2]. Результаты прогона на эталонных тестах ISCAS89 представлены в таблице 1 из работы [3]; столбцы A и B таблицы отражают время выполнения двух этапов ASTRA. | ||
== См. также == | == См. также == | ||
| Строка 274: | Строка 271: | ||
3. Zhou, H.: Deriving a new efficient algorithm for min-period retiming. In: Asia and South Pacific Design Automation Conference, Shanghai, China, January 2005 | 3. Zhou, H.: Deriving a new efficient algorithm for min-period retiming. In: Asia and South Pacific Design Automation Conference, Shanghai, China, January 2005 | ||
[[Категория: Совместное определение связанных терминов]] | |||
