Диссертация (Исследование и разработка методов автоматического вывода геометрических ограничений с использованием декларативного программирования и формальных методов), страница 13

i > i(K)3. K[i]i−1 = Ki ∩ Γ(vi )4. K≤i = C(K≤i ∩ Γ(vi ))≤iЕсли индекс i удовлетворяет указанным требованиям, тогда i являетсяродительским иденксом для K[i]. Таким образом, так как C(K) может бытьпостроено из клики K за O(m) шагов, то все клики могут быть найдены за O(nm)шагов. Алгоритм, описанный в работе [90], обходит дерево перечислений поискомв глубину, начиная от K0 и рекурсивно находит всех потомков, для чего требуетсяO(nm) времени и O(n+m) памяти. Алгоритм, представленный в работе [] строитклики в лексографическом порядке по убыванию, для чего требуется O(nm)времени и O(nN + m) памяти, N — число максимальных клик.Рассмотрим способ вычислениях всех таких индексов i, что K[i] являетсяпотомком K. Рассмотрим множества индексов I1 , I2 , I3 и I4 , которыеудовлетворяют условиям 1–4, соответственно.

I1 требует O(n) времени и O(n)для построения из K. Так как i(K) может быть вычислиен за O(n + m) времени,I2 может быть построено за O(n = m) времени и O(n + m) памяти.I3 может быть построен следующим образом. Если K — максимальнаяклика, то индекс i удовлетворяет условию 3 тогда и только тогда, когда ни одининдекс j не удовлетворяет следующим условиям:1. j < i2. vj ∈/ K≤i ∩ Γ(vi )583. вершина vj является смежной ко всем вершинам в K≤i ∩ Γ(vi ) ∪ {vi }Пусть матрица Ql — квадратная матрица размера n × n, в которой элемент(i, j) равен 1, если он удовлетворяет условию l выше; иначе его значение 0.Матрицы Q1 и Q2 могут быть построены за O(n2 ) времени и O(n2 ) памяти.Для вычисления матрицы Q3 предлагается следующий подход.

Пусть i–аястрока матрицы Q3 представляет собой вектор x(K≤i ∩ Γ(vi ) ∪ {vi }), где x —характеристический вектор заданного множества. Пусть A — матрица смежностиисходного графа G. В таком случае, элемент (, j) матрицы Q3 ∗ A являетсярезультатом скалярного произведения x(K≤i ∩ Γ(vi ) ∪ {vi }) и x(Γ(vi )). Такимобразом, вычисление матрицы Q3 сводится к вычислению Q ∗ A и требуетO(M (n)) времени и O(n2 ) памяти.Аналогично может быть построено множество I4 с учетом следующихнаблюдений. Если K — максимальная клика, то индекс i удовлетворяет условию4 тогда и только тогда, когда ни один индекс j не удовлетворяет следующимусловиям:1. j < i2. vj ∈/K3. вершина vj является смежной ко всем вершинам в K≤j4. вершина vj является смежной ко всем вершинам в K≤i ∩ Γ(vi ) ∪ {vi }В заключении отметим, что таким образом множество I = I1 ∩ I2 ∩ I3 ∩ I4 ,соответствующее всем индексам i, при которых K[i] является потомком K, можетбыть построено за O(M (n) шагов и требует O(n2 ) памяти.

Данный алгоритмиспользуется в диссертационной работе.2.3Задача минимизации логических функцийЗадача минимизации булевых функций является предметом активныхисследований уже много лет. Не смотря на то, что изначально перед методамиминимизации стояла задача поиска эффективной реализции логических функцийв виде ИС, сейчас эти методы используются и при решении задач кодированиясостояния, генерации тестовых наборов, оценки энергопотребления.

Такжепроблема минимизации логических функций возникает при решении задач, не59связанных с проектированием электроники, например, при анализе надежностии разработке систем искусственного интеллекта.Задача логической минимизации сводится к поиску такого покрытия дляфункции f , которое минимизирует заданную целевую функцию. Например, присинтезе интегральных схем такое покрытие может быть реализованно в видецифрового устройства минимального размера.

При таком подходе число кубов впокрытии выступает целевой функцией. также распространен подход, в которомминимизируется число литералов в покрытии.Классический алгоритм Куайна–Мак-Класки [96; 97] основан идее, чтоимпликанты, входящие в покрытие, могут быть только простыми.

Алгоритмвключает в себя два основных этапа: 1) генерация множества всех простыхимпликантов; 2) выбор минимального числа простых импликантов, которыевключают в себя все указанные минтермы из ON множества.В работе [98] рассматривается алгоритм SCHERZO, в основе котороголежит использование неявных методов минимизации, в частности, данныйалоритм опирается на использование таких структур хранения данных, какдвоичные деревья решений (BDD и ZBDD). Использование эффективныхструктур для манипуляций над большим числом объектов единовременнопозволило получить ускорение от 10 до 100 раз, в сравнении с другимиизвестными алгоритмами.Поиск точного решения задачи минимизации на практике может бытьосложнен комбинаторным взрывом.

В работе [99] предлагается эвристическийподход, названный BOOM, для поиска минимального покрытия. В отличие отдругих известных алгоритмов, в которых повышается размерность импликантовпутем исключения все большего числа литералов, в данной работе предлагаетсяпонижать размерность импликантов введением дополнительных литералов.Такой подход позволяет избежать случаев, когда итоговый результат минимизацииможет быть определен исходным покрытием. В предложенном алгоритменачальное описание покрытия практически не оказывает влияния на результат.В работе [100] рассматривается способ оптимизации алгоритма,описанного в работе [99].

Описанный алгоритм включает в себя две различныхэвристики, нацеленых на решение задач минимизаций различной природы.Комбинированный метод позволяет решать любые задачи минимизации, внезависимости от их размера и происхождения. Экспериментальные результаты60показывают, что полученное решение демонстрирует высокую степеньмасштабируемости в терминах требуемых вычислительных ресурсов и точностирезультата. Алгоритм может быть использован для функций, включающих в себябольше число как входных, так и выходных параметров.В работе [101] рассматривается метод минимизации булевых функций, воснове которого лежит алгоритм ESPRESSO-II, который оприается на решениезадачи SAT в процессе поиска минимального покрытия.

Не смотря на то,что стратегия минимизации осталась прежней, основные этапы ESPRESSOII значительно изменены. Экспериментальные результаты показывают, чтополученный алгоритм наход минимальное покрытие в 5–20 раз быстрее, чемESPRESSO-II, и в 3–5 раз быстрее, чем BOOM, в большинстве рассмотреныхпримерах.В работе [102] рассматривается метод минимизации, опирающийся наприменение GPU для выполнения вычислений. В работе рассматриваютсядетали реализации трех основных этапов, которые выполняются на GPU.Экспериментальные результаты демонстрируют, что данный подход позволяетвыполнять поиск минимального покрытия до 10 раз быстрее на NVIDIA TeslaGPU, в сравнении с выполнением на процессоре серии Xeon 5500.Одним из известных алгоритмов минимизации логических функцийявляется алгоритм ESPRESSO, основанный на использовании спецальнойэвристики.

В работах [103; 104]. Результатом работы алгоритма являетсяпрактически минимальное покрытие. В основе предлагаемого подхода лежитиспользование специальных операторов, которые итеративно минимизируютисходное покрытие. Основными операторами алгоритма являются EXPAND,IRREDUNDANT, REDUCE и ESSENTIALS.Оператор EXPAND увеличивает размерность указанного куба до техпор, пока не остануться только элементы OFF множества.

Иными словами,результатом работы данного оператора является простой импликант. Даннаяпроцедура включается в себя инвертирование каждого литерала в качествепроверки, входит полученный куб в ON или OFF множество. Результатом работыданной процедур является простое покрытие исходной функции, в которомниодин простой импликант не содержит никакого другого простого импликанта.Однако, некоторое подмножество простых импликантов также может являетсяпокрытием.61Следующий оператор, IRREDUNDANT, пытается уменьшить числопростых импликантов до минимально возможного так, чтобы не осталосьизбыточных импликантов, покрывающих заданную функцию. Простыеимпликанты при этом делятся на два множества: относительно важныеимпликанты, которые не могут быть опущены без нарушения покрытия,и избыточные импликанты. Последние также деляться на совершенноизбыточные и частично избыточные, для которых также выполняется построениеминимального покрытия.Результатом работы операторов EXPAND и IRREDUNDANT можетявляться решение, соответствующее локальному оптимому.

При этом важнопомнить, что задача поиска покрытия N P –полная и исследовать все решенияна практике не представляется возможным. Оператор REDUCE заменяет простоепокрытие в новое, заменяя каждый импликант меньшим, который в него входит.Эти три оператора является основой для эвристики ESPRESSO. Во времяработы алгоритма, данные три процедуры последовательно вызываются, начинаяс разных начальных позиций до тех пор, пока удается оптимизировать целевуюфункцию.

Если это становится невозможным, работа алгоритма прекращается.2.4 ВыводыЗа последние два десятилетия произошел значительный прогресс в методомрешения задачи SAT. Использование различных оптимизаций самого алгоритма,таких как обучение с конфликтами, нехронологический поиск с возратамии др., позволил существенно повысить производительность самой процедурыпоиск решения. Исследования показывают.