Оценки сложности задачи планирования
Приведем ряд результатов, касающихся сложности решения задач планирования.
1. Анализ вычислительных задач оказывается PSPACE-полной проблемой даже при условии, что "пустых" величин W нет .
2. Для вычислительных моделей без функциональных величин, т. е. с пустыми Db и F, проблема анализа вычислительных задач оказывается: а) PSPACE-полной для Н, содержащих функциональные и операторные зависимости без W ; б) NP-полной для Н, содержащих только функциональные и вариантные зависимости без "пустой" величины W ; в) полиномиальной (по времени работы планировщика) для Н, содержащих только функциональные и неявные зависимости; г) можно построить планировщики с линейным временем работы для Н только с функциональными зависимостями без W и для Н с функциональными и неявными зависимостями .
В системе ПГИЗ Db и F пусты, а в Н имеются только функциональные и операторные зависимости без "пустой" величины W. В системе автоматического синтеза программ СПОРА используется исчисление предикатов, для которого разработана специальная стратегия вывода .
Дерево анализа для вычислительной задачи - это дерево из формул используемого исчисления, в корне которого находится формула, представляющая исходную задачу, каждая нетерминальная вершина дерева может быть получена по одному из правил вывода "исчисления вычислительных задач" из формул, расположенных в дереве непосредственно ниже, а терминальные (висячие) вершины не являются заключением ни одного из правил вывода "исчисления вычислительных задач".
Планировщик в таком исчислении работает следующим образом: для заданной задачи конструируется какое-нибудь дерево анализа. Если все его висячие вершины являются аксиомами, то по этому дереву "собирается" программа. В противном случае формируется обоснование того, что задача неразрешима. Отсутствие детерминизма при логическом выводе в исчислениях стандартного типа приводит к экспоненциальному перебору возможных ветвей. Обнаружение при таком переборе тупика оказывается бесполезным (или почти бесполезным) для поиска на других ветвях дерева вывода.
В " исчислении вычислительных задач" для полного решения задачи планировщику достаточно располагать каким-нибудь деревом анализа. При разумной стратегии построения деревьев анализа это позволяет получать сравнительно быстрые процедуры планирования .
В общем случае планировщику приходится решать PSPACE-полную задачу. Это означает, что все известные сейчас планировщики на почти всех вычислительных задачах работают экспоненциальное время. В реальности ситуация не столь плоха. Практически интересные задачи, как правило, допускают эффективное планирование. И хотя доля подобных задач с ростом параметров, определяющих их, стремится к нулю, именно они представляют интерес с точки зрения эффективности автоматического синтеза программ. Показателем практически интересных задач может служить степень взаимодействия подзадач в процессе решения исходной задачи . Понятия "подзадача" и "условия подзадачи" возникают уже на стадии наивной интерпретации следующих зависимостей.
Функциональной зависимости (F->Y1), где F -функциональная величина типа (X->-Y), предполагающей предварительный синтез процедуры вычисления F, входными параметрами которой являются величины из списка X.
Операторных зависимостей, предполагающих синтез т процедур с входами "условиями подзадач" X1, Х2, ..., Хь-
Вариантных зависимостей, предполагающих, что создаются две ветви вычислений: для первой известны значения всех величин из списка Y1, для второй - из списка У2.
Рассмотрим простой (но типичный) пример. Пусть имеют место функциональная зависимость D1: (A, В, СR Е) и операторные зависимости D2: ((СR Е ) R Е1), D3:(( BR Е1))R Е2)), D4: ((AR Е2 ) R Е3). Необходимо найти Ез. Для этого следует решить подзадачу (AR Е2 ). Если воспользоваться зависимостью D3, то придем к поиску решения новой подзадачи ( BR Е1). Если использовать зависимость D2, то придем к необходимости решения подзадачи ( CR Е), которая согласно D1 разрешима только тогда, когда A и В известны.
Степень взаимодействия подзадач в этом примере равна трем. Процесс является типичной схемой планирования в пространстве задач .
Для планировщиков, работающих в "исчислении вычислительных задач;", синтез решения вычислительной задачи происходит за время hqrl/r!, где h - константа, l-длина записи задачи, определяемая как суммарное число вхождений имен используемых величин в F и H, q- общее число "различных" аргументов величин из "условия подзадач" в операторных зависимостях из H и "условий вариантов" в вариантных зависимостях из H, r-минимальная степень взаимодействия подзадач в исходной задаче . Эта оценка носит квазиоптимальный характер. Планировщик работает долго только на тех задачах, которые не являются естественными, так как требуют предельного переплетения между собой всех подзадач, на которые разбивается исходная задача. Эксперименты показывают, что для задач, встречающихся на практике, время работы планировщика является полиномиальным. Память, необходимая для работы планировщика в "исчислении вычислительных задач", оценивается величиной bl2, где Ь - константа. Если в Н нет вариантных зависимостей, то требуется линейный объем памяти dl, где d-константа .
В известных сейчас планировщиках получаемые программы далеки от оптимальных. Наблюдается тенденция ухудшения качества программ при уменьшении времени работы планировщика. При этом синтезировать оптимальные последовательные программы труднее, чем оптимальные параллельные программы. Это обстоятельство в связи с развитием ЭВМ новой архитектуры, ориентированной на параллельные процессы, может оказаться выгодным. Например, задача поиска минимальных по времени последовательного исполнения программ для решения вычислительных задач, у которых Db пусто, а Н состоит только из функциональных зависимостей W , оказывается NP-полной в сильном смысле . С другой стороны, в "исчислении вычислительных задач" при условии, что Db пусто, а Н состоит из функциональных и неявных зависимостей, можно за линейное время kl (k - константа) синтезировать программу, параллельное выполнение которой требует минимального для данной задачи времени .
В системе ПРИЗ и ее модификациях вычислительная задача считается разрешимой, если соответствующая ей формула выводима в позитивном фрагменте интуиционистского исчисления высказываний , т. е. в том и только том случае, когда достигается успех планировщиком системы ПРИЗ. Для "исчисления вычислительных задач" возможны две семантики для разрешимости .
Предельно неконструктивная; вычислительная задача считается разрешимой, если в любой базе данных (любой интерпретации), удовлетворяющей всем ограничениям вычислительной модели, имеет место некоторая функция типа (XR Y);
предельно конструктивная: обобщенная стандартная схема программы считается решением вычислительной задачи, если в любой интерпретации, удовлетворяющей всем ограничениям вычислительной модели, имеет место функция типа (XR Y), вычисляемая программой П, получающейся из обобщенной стандартной схемы программы соответствующей конкретизацией предикатных и функциональных символов.
"Исчисление вычислительных задач" корректно и полно относительно обеих семантик. При первой семантике планировщик всегда выдает решение исходной задачи в виде правильной программы, при второй - класс всех пропозициональных формул, описывающих разрешимые вычислительные задачи, совпадает с классом всех формул, выводимых в интуиционистском исчислении высказываний. Это показывает, что "исчисление вычислительных задач" можно рассматривать как один из вариантов формализации предложенной в интерпретации интуиционистской логики как логики "задач".
Во многих ИС используются планировщики, возможности которых существенно шире, чем у планировщика системы ПРИЗ, или того, который применяется в "исчислении вычислительных задач". Исчисления, с которыми имеют дело многие планировщики систем автоматизированного проектирования, планирования и управления, шире интуиционистских исчислений высказываний. При этом используются эвристические соображения, не имеющие аналогов в тех соотношениях, в которых описывались вычислительные модели.Примером может служить планировщик системы МАВР, предназначенной для ИС автоматизированного проектирования . При его работе возникают ситуации, не разрешимые в теории, которая описывалась выше. Такие случаи заставляют искать иные пути построения системы для поиска планов действий.
