4511
правок
Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 11:25, 28 августа 2018
, 28 августа 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
== Основные результаты == | == Основные результаты == | ||
Алгоритм FlowMap работает в два этапа. На первом этапе он для каждой не являющейся первичным входом вершины определяет предпочтительный K-допустимый конус в качестве кандидата для покрытия; конусы вычисляются таким образом, что в случае их использования они дают оптимальное по глубине решение отображения. Это основной этап алгоритма. На втором этапе выбираются конусы, необходимые для формирования покрытия для получения решения отображения. | |||
'''Структура оптимальных по глубине K-покрытий''' | |||
Обозначим за M(v) K-покрытие (или эквивалентное решение отображения на K-LUT) исходной сети Nv вершины v. Если v является первичным входом, M(v) состоит только из самой вершины v. (Для простоты далее M(v) будет называться K-покрытием v). Имеет место следующая лемма. | |||
Лемма 1. Если Cv является K-допустимым конусом вершины v в K-покрытии M(v), то M(v) = fCvg+SfM(u): u 2 input(Cv)g, где M(u) – определенное K-покрытие вершины u. Соответственно, если Cv K-допустимым конусом вершины v и для каждой вершины u 2 input(Cv) множество M(u) является K-покрытием u, то M(v) = fCvg + SfM(u): u 2 input(Cv)g является K-покрытием v. | |||
Иными словами, K-покрытие состоит из K-допустимого конуса и K-покрытия каждой входной точки конуса. Заметим, что для u1 2 input(Cv), u2 2 input(Cv), множества M(u1) и M(u2) могут перекрываться, и фрагмент, попавший в такое перекрытие, может быть покрыт таким же образом или не быть покрыт; вышеприведенное объединение включает все отдельные конусы на всех путях. Заметим также, что для заданного конуса Cv могут существовать различные K-покрытия v, содержащие Cv, в зависимости от выбора ofM(u) для каждой u 2 input(Cv). | |||
Обозначим за d(M(v)) глубину of M(v). Тогда выполняется следующая лемма. | |||
Лемма 2. Для K-покрытия M(v) = fCvg + SfM(u): u 2 input(Cv)g, d(M(v)) = maxfd(M(u)): u 2 input(Cv)g+1. | |||
В частности, обозначим за M*(u) K-покрытие вершины u с минимальной глубиной. Тогда d(M(v)) > max{d(M*(u)): u 2 input(Cv)g+1; равенство имеет место в случае, когда каждое покрытие M(u) в M(v) имеет минимальную глубину. | |||
Вспомним, что Cv определяет K-допустимый разрез (X, X0), где X0 = Cv, X = Nv - Cv. Обозначим за H(X, X0) высоту разреза (X, X0), определяемую как H(X;X0) = max{d(M*(u)): и 2 input(X0)g + 1. Очевидно, что H(X, X0) обеспечивает минимальную глубину для любого K-покрытия вершины v, содержащего Cv = X0. Кроме того, за счет подходящего выбора разреза можно минимизировать высоту H(X, X0), что позволяет получить K-покрытие с минимальной глубиной: | |||
Теорема 1. Если K-допустимый разрез (X, X0) v имеет минимальную высоту среди всех K-допустимых разрезов v, то K-покрытие M*{v) = fX0g + \J{M*(u): u 2 input(X0)g имеет минимальную глубину среди всех K-покрытий v. | |||
Иначе говоря, K-допустимый разрез минимальной высоты определяет K-покрытие с минимальной глубиной. Таким образом, основной задачей оптимального по глубине технологического отображения становится вычисление K-допустимого разреза минимальной высоты для каждой вершины, являющейся первичным выходом. | |||
По определению, высота разреза зависит от (глубин) K-покрытий с минимальной глубиной вершин из множества Nv - {v}. Для этого можно использовать процедуру динамического программирования, следующую топологическому порядку, так что к моменту, когда необходимо определить K-покрытие v с минимальной глубиной, K-покрытие каждой вершины из Nv - {v} с минимальной глубиной уже известно, и высоту разреза можно легко определить. Именно так работает первый этап алгоритма FlowMap. | |||
'''Вычисление K-допустимого разреза минимальной высоты''' | |||