Системы искусственного интеллекта


Оценки сложности задачи планирования - часть 3


Степень взаимодействия подзадач в этом примере равна трем. Процесс является типичной схемой планирования в пространстве задач .

Для планировщиков, работающих в "исчислении вычислительных задач;", синтез решения вычислительной задачи происходит за время hqrl/r!, где h - константа, l-длина записи задачи, определяемая как суммарное число вхождений имен используемых величин в F и H, q- общее число "различных" аргументов величин из "условия подзадач" в операторных зависимостях из H и "условий вариантов" в вариантных зависимостях из H, r-минимальная степень взаимодействия подзадач в исходной задаче . Эта оценка носит квазиоптимальный характер. Планировщик работает долго только на тех задачах, которые не являются естественными, так как требуют предельного переплетения между собой всех подзадач, на которые разбивается исходная задача. Эксперименты показывают, что для задач, встречающихся на практике, время работы планировщика является полиномиальным. Память, необходимая для работы планировщика в "исчислении вычислительных задач", оценивается величиной bl2, где Ь - константа. Если в Н нет вариантных зависимостей, то требуется линейный объем памяти dl, где d-константа .

В известных сейчас планировщиках получаемые программы далеки от оптимальных. Наблюдается тенденция ухудшения качества программ при уменьшении времени работы планировщика. При этом синтезировать оптимальные последовательные программы труднее, чем оптимальные параллельные программы. Это обстоятельство в связи с развитием ЭВМ новой архитектуры, ориентированной на параллельные процессы, может оказаться выгодным. Например, задача поиска минимальных по времени последовательного исполнения программ для решения вычислительных задач, у которых Db пусто, а Н состоит только из функциональных зависимостей W , оказывается NP-полной в сильном смысле . С другой стороны, в "исчислении вычислительных задач" при условии, что Db пусто, а Н состоит из функциональных и неявных зависимостей, можно за линейное время kl (k - константа) синтезировать программу, параллельное выполнение которой требует минимального для данной задачи времени .




- Начало -  - Назад -  - Вперед -