ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2012, № 2, с. 121-129
КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 519
МОДЕЛЬ ОРГАНИЗАЦИИ ВЫЧИСЛИТЕЛЬНОЙ СТРУКТУРЫ РЕШЕНИЯ ЗАДАЧИ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ С НЕЗАВИСИМОЙ ОТ ЕЕ РАЗМЕРНОСТИ
АЛГОРИТМИЧЕСКОЙ СЛОЖНОСТЬЮ* © 2012 г. Л. Закшевский1, А. А. Третьяков2, Г. С. Хулап3
1,2Poland, Warszawa, System Research Institute of the Poland Academy of Sciences, 1Biala Podleska, Pope John Poul II State School of Higher Vocatirnal Education, Institute of Computer Sciences; 2Siedlce, University of Natural Sciences and Humanities, Institute of Mathematics and Physics; 2Россия, Москва, ВЦ РАН; 3Институт новых технологий Поступила в редакцию 31.03.11 г., после доработки 07.07.11 г.
Предлагается новая концепция организации вычислительного процесса таким образом, что количество последовательных одновременных тактовых операций (или число векторных операций) не зависит от числа n — размерности задачи. При этом архитектура вычислительной среды адаптирована под конкретную решаемую задачу и вычисление осуществляется без обмена информацией между элементарными вычислительными устройствами — элементарными процессорами, число которых зависит от n. Описан алгоритм реализации данной идеологии на примере решения задачи многоэкстремальной оптимизации (или выбора максимального из n заданных чисел), а также алгоритм решения задачи коммивояжера [1—4].
Введение. В последнее время все больше внимания специалисты различных областей знаний уделяют необходимости решения больших и сложных задач эффективными и надежными средствами. Однако естественно заложенное в проблему "проклятие" последовательной обработки информации резко ограничивает возможности исследователя. Даже использование новых технологий, таких, как параллельные вычисления, многопроцессорные системы и т.д., не дают полной универсальности и так или иначе зависят от сложности решаемой задачи, которую в дальнейшем мы будем называть размерностью и обозначать через п.
Обработка больших массивов однотипной информации требует существенных вычислительных затрат, связанных с многими причинами, в числе которых одной из главных является необходимость обмена информацией между элементарными процессорами. В данной работе предлагается математическая модель организации вычислительного процесса таким образом, что отсутствует обмен информацией между элементарными процессорами и количество параллельных арифметических операций не зависит от числа п. Основная идея подхода излагается на примере решения задачи глобальной максимизации на отрезке, хотя все рассуждения и выводы справедливы и для задачи максимизации на п-мерном параллелепипеде. Следует отметить, что идея глобальной обработки информации использовалась ранее в [5, 6] для решения ряда задач теплофизики и телекоммуникаций.
1. Модель глобальной вычислительной архитектуры. Пусть имеется следующая задача оптимизации:
тах ф(х), х е [а, Ь] (1.1)
где функция ф(х) задана своими значениями в п точках: хх = а,х2,..., х„_ъхп = Ь (см. рис. 1).
Теперь представим себе, что мы хотим "увидеть" сразу поведение всей поверхности исследуемой функции (на отрезке). Здесь "поверхность" понимается в смысле совокупности точек ее задания — п точек, т.е. мы хотим "увидеть" сразу весь ансамбль {ф(х;-)} значений функции ф в п точках и, не перебирая последовательно значения функции в точках х, сразу охватить единым взглядом всю картину "глобального" поведения многоэкстремальной поверхности с точки зрения выявления нужного нам свойства — в данном случае поиска глобального максимума.
* Работа выполнена при финансовой поддержке РФФИ (грант № 11-01-00786-а) и Программы Президента РФ поддержки научных школ НШ-4096.2010.1.
ф*
ф(Ь)
а х2 хз хи_1 Ь
Рис. 1. Ансамбль {ф(х;)| значений функции ф(х) в п точках х.
Рис. 2. Модель глобальной вычислительной архитектуры нахождения максимального элемента из п чисел
Описываемый подход можно проиллюстрировать на модельном примере с "забором", у которого заменим одну "старую", темную доску на светлую, "новую". Выявление светлой ("новой") доски осуществляется сразу, без перебора всех досок. Чтобы отыскать "новую" доску (глобальный максимум), мы не будем перебирать все "старые", темные доски (сравнивать все значения функции в точках х1), а сразу отреагируем — по другому признаку — и укажем "новую" доску (см. [4, 7]).
Таким образом, задача состоит в построении математической модели вычисления (выбора) максимального элемента из п значений {ф(хк)} функции ф(х) в точках хк со сложностью, не зависящей от п. Обозначим Ик = ф(хк), к = 1,2,..., п, и рассмотрим задачу определения максимального элемента
= тах .
(1.2)
к = 1,,
Здесь п (число величин Ик) — размерность данной задачи. Для простоты изложения предположим, что все Ик — целые положительные числа и N1 Ф Nу, I ф у, у = 1, п. Отметим, что сложность традиционных алгоритмов решения этой задачи с использованием параллельных вычислений (п процессоров) будет порядка 0(^2 п). В нашей модели мы также будем использовать п элементарных идентичных процессоров Ргк для вычисления значений ф(хк) (или чисел Ык), к = 1, п. Считаем, что каждый элементарный процессор Ргк преобразует значение N в световой сигнал соответствующей высоты Нк = Nk = ф(хк), к = 1, п (см. рис. 2).
Ф
Имеется главный процессор МР, который реагирует только на световой сигнал от элементарных процессоров (не важно, от какого) и управляет подвижным блокирующим вертикальным экраном, который может двигаться либо вверх, либо вниз на заданную величину (см. рис. 2). Если высота экрана больше Нк, то свет от источников Ргг, таких, что Нг < Нк, г е {1, п}, блокируется и не доходит до главного процессора МР.
Модель работает следующим образом. Главный процессор МР осуществляет поднятие экрана до тех пор, пока есть световой сигнал хотя бы от одного источника Ргк. Если светового сигнала нет, т.е. все источники блокированы, главный процессор МР останавливает экран и осуществляет его движение вниз на величину 5 (точность получаемого решения). В нашем случае 8 = 1/2. Световой сигнал появляется снова, но уже только от одного источника Ргр, соответствующего максимальному значению Щ (см. рис. 2).
Такая модель вычислительной архитектуры позволяет одновременно передавать информацию о номере р и максимальном значении Щ вместе со световым сигналом и базируется на двух аналоговых операциях:
1) поднятие экрана до тех пор, пока световой сигнал есть;
2) остановка поднятия экрана при отсутствии светового сигнала и опускание экрана на величину 5.
В дальнейшем будем за одну базовую операцию в данной модели считать
1) поднятие (опускание) экрана до момента детекции света (либо свет есть, либо света нет);
2) поднятие (или опускание) экрана на заданную величину.
Число операций (сложность) в данной модели не зависит от величины п. Общее время вычислений зависит от величины максимального элемента Щ и будет определяться числом операций
поднятия экрана для достижения точки Нр = Nр.
2. Алгоритм глобального типа определения максимального элемента из массива. Пусть имеется
массив Б из п натуральных чисел а1,..., ап, где а1 > 0, г = 1, п. Требуется определить £* — максимальное значение ар из массива Б, т.е.
£* = тах а г = ар.
г = 1, п
Будем использовать модель глобальной вычислительной архитектуры, описанную выше, с использованием световой детекции.
Обозначим 5 = тт{| а1 - а;- || г,у е {1,..., п},а1 Ф а у}. Алгоритм вычисления максимального элемента из массива на основе глобальной вычислительной архитектуры будет следующим [1, 4, 8].
Алгоритм 1 (Метод удвоений [9, 10]).
Шаг 1. Полагаем £0 = 0, £1 > 0, где £0,£ 1 — высоты экрана, выбранные таким образом, что при высоте £ 1 свет есть, а при высоте экрана 2£ 1 нет детекции света. Предположим, что при т = 1, к свет есть при высоте £ т и света нет при высоте £ т + (£ т - £ т-1). Вычисляем следующее £к+1, т = к + 1.
Шаг к + 1. Проверяем, выполнено ли неравенство
^к -1к-1 <8/2. (2.1)
Если неравенство выполнено, то полагаем К = к + 1 и 8ТОР. В противном случае полагаем % = 1 и идем на А2.
А1. Вычисляем
£ = £ к + к^Аы. к 2
А2. Проверяем, есть ли световой сигнал для высоты экрана £ .
Если света нет, то $к = $к + 1 и идем на А1.
Если свет есть, то £к+1 = £ , к = к + 1 и идем на шаг к + 1.
Пусть К — число операций, необходимых описанному выше алгоритму для достижения максимального элемента ар, т.е. выполнено условие (2.1) \£к+1 - £к| < 5/2, гарантирующее, что максимальный элемент £* = ар локализован за К = к + 1 итераций (шагов). Для оценки асимптотической сложности К алгоритма будет верна следующая теорема.
Теорема 1. Пусть А = 2-Р. Тогда число операций К в алгоритме 1 будет К ~ 1о§2 А.
О
Замечание 1. Число операций К не зависит от п.
Доказательство. Без ограничения общности рассмотрим случай Бк = 1 для любых к. Общий случай рассматривается аналогично. В соответствии с алгоритмом при высоте экрана I к есть свет, а при I к + (£ к - I к-1) — нет. По построению мы имеем
' к-1-' к£ ^ и ' к < '*£' к +" к-' ^ Аналогично
-к+1 *-k —
<■- i -Iо< A - 2 к - 2 к •
Ближайшее а1 отличается от £* на величину, превосходящую или равную 5, поэтому номер шага К для определения £* должен удовлетворять соотношению
4 (2.2)
2К 2
Учитывая целочисленность К, находим, что число шагов (операций) для выполнения неравенства (2.2) может быть взято равным
K =
2 A о _
+1,
т.е. K ~ log2 A.
о
Замечание 2. В реальной ситуации значение 5 больше, чем машинно-возможное предста-вимое число в компьютерной архитектуре, т.е. "машинный ноль" 0M. В нашей модели мы можем взять 1*/Ь < M, где Mсоответствует числу 1/0M. Поэтому общее число операций Kбудет не более
- log2 2A ^ lo§2^ = log2 4M.
8 £*
Заметим, что число M не зависит от п.
Замечание 3. Для проблемы Кука мы имеем булеву функцию f(x) от переменной x = (x1, ..., xn), принимающую только на одном наборе x* = (x*, ..., x*) значение 1: f (х*) = 1 и значение 0 на остальных, т.е. f (x) ф 0, если x ф x*. Проблема состоит в отыскании числа х*. Если предположить, что мы имеем п! элементарных процессоров Prk, каждый из которых вычисляет f (xik), ..., x(Jk)), то
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.