Моделирование поиска в системах с несколькими вычислителями.

Одной из основных задач информатики является проблема сокращения времени обработки данных, и создание быстрых алгоритмов, в частности, быстрых алгоритмов поиска — это шаги на этом пути. С появлением многопроцессорных вычислительных систем возникла принципиально новая возможность сокращения времени работы алгоритмов. Возникло, так называемое параллельное программирование [105,164], при котором создаваемые программы (алгоритмы), используют в своей работе несколько процессоров (исполнителей).

Существует два типа моделей исследования процессов, происходящих в многопроцессорных системах: асинхронные и параллельнопоследовательные. В асинхронном программировании [60] все действия (операторы) программы изначально считаются независимыми, параллельно исполняемыми, а формирование вычислительных процессов организуется с помощью ограничений, налагаемых на порядок исполнения действий. Наиболее распространенной моделью, используемой с асинхронном программировании, являются сети Петри

[59, 97, 191). Проблематика сетей Петри в основном связана с исследованием качественных вопросов, таких как эквивалентность программ, проблемы безопасности, ограниченности, консервативности, устойчивости, достижимости и т. п. Тогда как нас интересуют количественные характеристики программ, такие как время работы и объем памяти. Основу параллельно-последовательного программирования составляют последовательность параллельных операторов или параллельно исполняемые последовательные ветви (процессы). Если из параллельно-последовательной программы удалить дополнительные средства распарал л сливания, то программа становиться обычной последовательной.

При выборе модели параллельных вычислений выделяются два подхода.

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

Второй подход связан с реальными моделями вычислительных систем, т. е. моделями, в которых число процессоров ограничено, память имеет несколько уровней иерархии, время выполнения различных операций различно, существуют конфликты по доступу к памяти, необходимы дополнительные действия для синхронизации процессов и т. п. [46, 49, 54, 71, 108, 176).

Предлагаемую в данной работе модель параллельных алгоритмов поиска можно скорее отнести к параллельно-последовательным, чем к асинхронным, и в ней сочетаются некоторые свойства как идеальных, так и реальных моделей. Основу предлагаемой модели составляет ИГ, но мера сложности определяется специальным образом. Для этого вводится такой алгоритм обхода, который предполагает блуждание по сети сразу нескольких исполнителей. Для разрешения конфликтов при таком блуждании используется окрашивание графа каждым исполнителем и нумерация исполнителей, которая определяет порядок исполнения действий исполнителями при одновременном попадании нескольких исполнителей в одну вершину информационного графа. Строгое формальное описание алгоритма параллельного обхода, приводится во втором разделе третьей главы. Данная модель относится к параллельно-последовательным поскольку подобна последовательным алгоритмическим системам (типа конечного автомата [63]), для которых характерен последовательный способ функционирования: система последовательно переходит из состояния в состояние в соответствии с заданной функцией перехода и осуществляет очередной шаг алгоритма. Хотя кажется, что каждый исполнитель независимо осуществляет свой алгоритм обхода информационного графа, но это не так, поскольку действия исполнителя на каждом шагу определяются общим состоянием системы (текущей раскраской ребер графа). С реальными моделями предлагаемую модель роднит наличие конечного числа процессоров (исполнителей), учет конфликтов между исполнителями, а с идеальными — одинаковое время выполнения операций, отсутствие временных затрат на синхронизацию действий.

В параллельном программировании существует как минимум два подхода. Первый предполагает разделение данных между исполнителями и дальнейшую независимую обработку каждым исполнителем своей части данных. Второй подход предполагает кооперативное (совместное) владение данными всеми исполнителями и сложную систему регулировки отношений между исполнителями в процессе обработки совместных данных. Первый подход мы в дальнейшем будем называть сепаративным, а второй — кооперативным. Понятно, что кооперативный подход более сложен в реализации, но поскольку он более общий, то, вообще говоря, должен давать лучшие результаты.

В смысле распараллеливания алгоритмы поиска могут считаться легкими, поскольку для них сепаративный подход вполне приемлем, т. е. множество объектов поиска можно раз и навсегда поделить между исполнителями, и затем при осуществлении очередного поиска каждый из исполнителей будет вести поиск в своей части данных, после чего остается только объединить результаты поиска. Возникает вопрос насколько оправдан такой подход?

В данном разделе предлагается математическая модель параллельных алгоритмов поиска и в рамках этой модели исследуется параллельное решение задачи поиска с отношением поиска вида линейного предпорядка. Описан способ оптимального разделения данных при использовании сепаративного подхода для данной задачи, и показано, что в общем случае сепаративный подход не дает оптимального решения, т. е. приведен пример таких задач поиска с отношением линейного предпорядка, для которых кооперативный подход дает лучшие результаты.

Результаты данного раздела были анонсированы в [34] и опубликованы в [39, 161].

В качестве модели параллельных алгоритмов поиска предлагается использовать информационные графы (ИГ), но сложность ИГ предлагается вводить по-другому, так чтобы она отражала сложность параллельных алгоритмов.

Итак, пусть нам даны множество записей У, множество запросов X, некоторое базовое множество Т функций над множеством запросов X, некоторый ИГ U над базовым множеством Т, и пусть имеется некоторое число исполнителей. Исполнителя можно воспринимать как некоторый автомат, который будет обходить наш ИГ. Будем считать, что все исполнители как автоматы одинаковы, т. е. имеют одинаковое поведение, и это поведение мы опишем, описав процедуру обхода исполнителем ИГ U. Причем, будем считать, что все исполнители осуществляют обход графа одновременно, т. е. в параллельном режиме. Пусть число исполнителей равно тп. Прежде чем описать процедуру обхода сделаем следующие предположения.

  • • Будем считать, что каждому ребру графа U мы можем временно приписывать номер, который назовем путевым.
  • • Будем считать, что мы можем помечать листья графа, в которые мы уже заходили, причем в начальный момент все листья непомеченные.
  • • Будем считать, что каждому из исполнителей сопоставлено некое целое число j (1 ^ j ^ т), которое будем называть порядковым номером исполнителя. Причем, различным исполнителям соответствуют различные номера.
  • • Будем считать, что помимо порядкового номера каждый исполнитель j (j = l,m) имеет свой цвет Cj, с помощью которого он может окрашивать ребра и переключательные вершины графа, которые он просмотрел. Причем будем полагать, что различным исполнителям соответствуют различные цвета.
  • • Будем считать также, что до начала работы процедуры ребра и переключательные вершины ИГ были окрашены в некий цвет Соу который назовем нейтральным, причем этот цвет не совпадает ни с одним из цветов Ci,... ,Cm.
  • • Положим также, что имеется некоторый цвет ст+1, который не совпадает ни с одним из цветов Со, Сь... ,Ст.
  • • Назовем множество ребер, исходящих из одной вершины, пучком и будем считать, что в каждом пучке определен порядок следования ребер, т. е. существует ребро первое, второе и т. д.
  • • Будем считать, что каждый исполнитель совершает свои действия (просмотр окрестности, перекрашивание ребер, движение к следующей вершине) за 1 такт. Но поскольку у нас сразу несколько исполнителей обходят граф, то чтобы разрешать спорные ситуации, связанные с порядком действий, при одновременном попадании нескольких исполнителей в одну вершину, будем считать, что исполнитель с порядковым номером j начинает обход графа в момент времени такта. Это простейший способ

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

Теперь мы можем перейти к описанию процедуры обхода графа U. Входными данными процедуры Л будут информационный граф U

и запрос хX. Выходными данными — множество записей, входящих в ответ на запрос я, и набор натуральных чисел Т,... ,Тт, показывающих нам сколько предикатов и переключателей было вычислено каждым из исполнителей в процессе обхода графа U на запросе х.

Сначала опишем процедуру обхода графа U на запросе х 6 X j-м исполнителем (j = 1 ,m).

  • 1. (Инициализация процесса обхода.)
  • (a) Объявим текущей вершиной корень графа U.
  • (b) Присвоим начальное значение счетчику путевых номеров

sj = 1.

  • (c) Присвоим начальное значение счетчику вычисленных функций tj = 0.
  • (d) Перейдем к пункту 2.
  • 2. (Прямой ход.)
  • (a) Если текущая вершина — непомеченный лист графа U, то помечаем ее и добавляем к множеству У запись, принадлежащую текущей вершине.
  • (b) Если текущая вершина есть точка переключения, то:

i. если текущая вершина окрашена не в нейтральный цвет, то идем к пункту 3; й. окрашиваем текущую вершину в цвет Cj

iii. вычисляем значение переключателя, приписанного текущей вершине, на запросе х (пусть это значение равно п);

iv. увеличиваем на 1 значение счетчика вычисленных функций: tj = tj + 1;

v. если среди ребер, исходящих из текущей вершины, нет ребра с номером п, то переходим к пункту 3;

vi. ребру с номером п, исходящему из текущей вершины, приписываем путевой номер Sj, окрашиваем его в цвет Cj, объявляем конец этого ребра текущей вершиной, присваиваем Sj = sj + 1 и возвращаемся к пункту 2.

(c) Если текущая вершина не является точкой переключения, то:

i. если из текущей вершины не исходит ни одно ребро, или же среди ребер, исходящих из текущей вершины, есть ребро, окрашенное в цвет Cj, или же среди ребер, исходящих из текущей вершины, нет ни одного, имеющего нейтральный цвет, тогда переходим к пункту 3; й. выбираем первое по порядку следования нейтральное ребро;

iii. окрашиваем выбранное ребро в цвет Cj

iv. величину tj увеличиваем на 1;

v. приписываем выбранному ребру путевой номер Sj

vi. присваиваем Sj = $_, + !;

vii. объявляем конец просматриваемого ребра текущей вершиной;

viii. если значение предиката, соответствующего выбранному ребру, на запросе х равно 1, то идем к пункту 2, иначе — к пункту 3.

  • 3. (Обратный ход)
  • (а) Если текущая вершина есть переключательная вершина, окрашенная в цвет Cj, то окрашиваем ее в цвет Cm+i.

S Уменьшаем значение счетчика путевых номеров: Sj=Sj — 1. Если Sj = 0, то присваиваем числу Tj значение счетчика вычисленных функций tj и завершаем работу процедуры,

  • (d) Если Sj > 0, то существует ребро, входящее в текущую вершину и имеющее путевой номер Sj и цвет Cj, выбираем его.
  • (е) Окрашиваем выбранное ребро в цвет Cm+i.
  • (f) Объявляем текущей вершиной начало выбранного ребра,
  • (g) Если текущая вершина является точкой переключения, то возвращаемся к пункту 3, иначе возвращаемся к пункту 2.

Теперь описать процедуру обхода Л графа U на запросе х всеми исполнителями очень просто.

  • 1. Присвоим начальное значение множеству У = 0.
  • 2. Запускаем по очереди в моменты времени процедуру обхода графа U на запросе х j-ът исполнителем (j = l,m).
  • 3. Считаем, что работа процедуры обхода Л полностью завершена тогда и только тогда, когда каждый из исполнителей завершил работу своей процедуры.

Легко убедиться, что данная процедура обхода позволяет посетить все вершины, функции фильтров которых принимают значение 1 на запросе х, и, следовательно, полученное на выходе процедуры множество У совпадает с ответом Ju(x) графа U на запрос х, что говорит о корректности определения процедуры обхода. На выходе процедуры обхода мы также получим множество {7i,...,Tm}, где для любого j € {l,m} величину Tj можно трактовать как время, затраченное исполнителем с порядковым номером j.

В принципе можно также учитывать время обратного хода, изменяя соответствующим образом значение tj счетчика времени на шаге 3 процедуры. Но в данной работе мы рассматриваем такое приближение к реальному времени вычисления, при котором мы пренебрегаем всеми затратами времени, кроме времени вычисления предикатов и переключателей, причем считаем, что каждый из них вычисляется за время, равное одному такту.

В завершение описания процедуры обхода ИГ, заметим, что данная процедура позволяет использовать конкретный ИГ U более чем один раз. Для повторного обхода графа U достаточно объявить цвета Со

И Cm+i нейтральными и положить, что при обратном ходе каждый исполнитель должен использовать некоторый цвет Сш+2 вместо используемого им ранее цвета Ст+1* Причем, цвет Ст+2 полагаем отличным от любого из цветов Со, Сь... у Cm+i- Кроме того надо изменить число, которым помечаются листья, посещенные процедурой обхода.

На основе описанной выше процедуры обхода, которая по сути является описанием соответствующего графу алгоритма параллельного поиска, мы можем ввести понятие сложности ИГ.

Сначала определим понятие сложности ИГ на запросе.

Пусть нам дан некий ИГ U и произвольно взятый запрос х. Пусть Л — определенная ранее процедура обхода, причем, число исполнителей, реализующих процедуру обхода Л, равно га ^ 1, и пусть {7 = = Ti(t/,ra,x),... ,Тт = Тт(?/, га,я)} — множество тех самых чисел, полученных на выходе процедуры, которые указывают на число вычисленных каждым из исполнителей функций, при работе процедуры Л на запросе х. Тогда сложностью ИГ U на запросе х для га исполнителей (га-сложностью на запросе) назовем величину

Понятие сложности ИГ введем как среднее значение сложности ИГ на запросе, взятое но множеству всех запросов.

Напомним, что на множестве запросов X задано вероятностное пространство (Х,а, Р), где с — некоторая алгебра подмножеств множества Ху Р — вероятностная мера на о.

Если U — ИГ над базовым множеством Ту с = (а,/3) — некоторое ребро графа U, /с — функция проводимости ребра с, а функция фильтра вершины а, то предикат ?с(х) = /с(я) & 4>а(х) назовем функцией состояния ребра с.

Если C(U) = {ci,... yCq} — произвольным образом упорядоченное множество всех ребер графа U, то вектор-функцию (?с, (я), • • •, Ссч(я)) назовем вектором состояния графа U.

При фиксации запроса хX полученный булевский вектор (CcifaO, • • • >Сс,(я)) будем называть вектором состояния графа U на запросе х.

Справедлива следующая лемма.

Лемма 33. Если базовое множество Т = (F, G) измеримое, то для любого натурального числа га и для любого ИГ U над базовым множеством Т функция Tu{Uy га, х), как функция от х, является случайной величиной.

Доказательство. Пусть число исполнителей га ^ 1 у нас фиксировано.

Нам необходимо доказать, что для любого ИГ U над базовым множеством Т и любого действительного числа г множество

X: 7п(?/,га,х) < г} € а.

Пусть 7?(С/), C(U) — множества всех вершин и ребер графа {/, соответственно.

Покажем сначала, что для любой вершины & ? 7?(С/) справедливо Nvgа.

Пусть для каждой € B,(U) Ср — множество всех ориентированных цепей графа С/, ведущих из корня в вершину С — некоторая цепь, с — некоторое ребро, /с — функция проводимости ребра с. Так как по определению для любого с € С выполнено /с 6 F U G, то Л//с 6 6 сг и

и, следовательно, для любого ребра с 6 C(U) N^e = 7Vv,a П7У/С € а, где a — начало ребра с.

Пусть после некоторого упорядочения C(U) = {cj,..., cq}.

Пусть uj = {u/i,..., a)q} — произвольный булев вектор длины q, т. е.

Wi 6 {0,1}, i = 17

Пусть

т. е. это множество таких запросов, вектор состояния графа на которых равен и.

Очевидно, что для любых Х,Х2Х% справедливо

Нетрудно видеть, что если uj ф ?2, то Х%1 П Х^7 = 0, причем (J Х% = X, где В4 — единичный булев куб размерности q. сзевч

Легко заметить, что

причем для любого i 6 {l,g}

значит, Х„ 6 о.

Возьмем произвольное действительное число г.

Обозначим

Таким образом, лемма доказана.

Тогда

Далее всюду будем предполагать, что мы находимся в условиях леммы 33.

Сложностью ИГ U для т исполнителей (т-сложностью графа) назовем величину

Скажем, что ИГ U разрешает ЗИП I = (X, V,p), если для любого запроса х € X ответ на этот запрос содержит все те и только те записи из V, которые удовлетворяют запросу х, т. е.

Пусть нам дана некая ЗИП I и число исполнителей т ^ 1. Сложностью задачи I при базовом множестве Т для т исполнителей назовем число

где U(I,T) — множество всех ИГ над базовым множеством Т разрешающих ЗИП /.

Если существует такой информационный граф U ? U(I,T), что Tn(U,m) = Тц(1,Т,т), то ИГ U будем называть т-оптимальным для ЗИП I.

Пусть U — некоторый ИГ, хX — некоторый запрос, т — некоторое натуральное число, /? — некоторое предикатное ребро (некоторая переключательная вершина) графа U. Обозначим через пр(х,т) число, равное 0, если в результате применения процедуры обхода с т исполнителями к графу U на запросе х ребро (вершина) (5 остается окрашенным (окрашенной) в нейтральный цвет, и равное j, если в процессе работы процедуры обхода с т исполнителями к графу U на запросе х перед тем как быть окрашенным (окрашенной) в цвет Сщ+1 ребро (вершина) & было окрашено (была окрашена) в цвет Cj, т.е. функция, соответствующая р вычислялась j-ым исполнителем.

Скажем, что предикатное ребро (переключательная вершина) 0 т-сепаративно (т-сепаративна), если для любых х,хгX справедливо

Скажем, что ИГ U т-сепаративен, если любое предикатное ребро и любая переключательная вершина графа U т-сепаративны.

Легко видеть, что га-сепаративные ИГ соответствуют параллельным алгоритмам поиска, относящимся к сепаративному подходу, при котором все данные делятся на части и при просмотре всего множества запросов каждая часть данных обрабатывается только одним исполнителем.

Обозначим через Us(I,T,m) — множество всех т-сепаративных ИГ над базовым множеством Т разрешающих ЗИП 7.

Встает вопрос сравнения величин

Если существует такой информационный граф U 6 US{I, Т, га), что ТП(С/, га) = inf{Tn((/, га) : UUS(I, Т, га)}, то ИГ U будем называть оптимальным для ЗИП I в классе т-сепаративных.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >