Технологическое отображение ППВМ: различия между версиями

Перейти к навигации Перейти к поиску
Строка 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-допустимого разреза минимальной высоты'''
Источник — http://pco.iis.nsk.su/wega/index.php/Технологическое_отображение_ППВМ