Развертки и граф-машина

Но вернемся к исследованию параллелизма с помощью разверток. Изучение параллельной структуры алгоритмов связано с отысканием множеств операций, которые можно выполнять независимо друг от друга. В терминах, связанных с графом алгоритма, это эквивалентно нахождению множеств его вершин, не связанных между собой ни дугами, ни путями графа. Рассмотрим непересекающиеся множества $$M_1,\ldots,M_p$$ вершин графа алгоритма $$G$$. Назовем эти множества параллельными по графу $$G$$ или просто параллельными, если любой путь, связывающий две вершины одного множества, целиком лежит в этом множестве и никакие две вершины из разных множеств не связаны ни дугой, ни путем графа $$G$$. Под параллельной структурой алгоритма или графа будем понимать совокупность сведений о параллельных множествах. Сюда же будем относить и сведения о тех преобразованиях, целью которых является либо выявление, либо изменение параллельных множеств. Говоря о параллелизме, обычно обсуждают два его вида: макропараллелизм и микропараллелизм. Макропараллелизм связан с ситуацией, когда все или хотя бы часть из параллельных множеств содержат много точек. Микропараллелизм имеет дело с теми случаями, при которых в каждом из параллельных множеств находится всего лишь несколько точек. Типичной для микропараллелизма является ситуация, когда все множества содержат только по одной точке.

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

Продемонстрируем подобное расщепление на примере использования обобщенных разверток. Докажем сначала два полезных факта. Пусть для графа алгоритма G построены обобщенные развертки $$f_1(x),f_(x)$$. Как следует из определения разверток, функционал $$f(x)=f_1(x)+f_2(x)$$ также будет обобщенной разверткой. Рассмотрим какую-нибудь поверхность уровня развертки $$f(x)$$, содержащую не менее двух вершин-точек $$х_1$$ и $$x_2$$. Допустим, что для этих точек $$f(x_1)=f(x_2)$$, но $$f_1(x_1)\neq f_1(x_2)$$. Предположим, например, что $$f_(x_1)>f_1(x_2)$$. Отсюда сразу же вытекает, что $$f_2(x_1)<f_2(x_2)$$. Если точки связаны путем графа $$G$$, то для любой развертки путь может идти лишь из точки с меньшим ее значением в точку с большим значением. Поэтому заключаем, что точки $$x_1$$ и $$x_2$$ не могут быть связаны путем графа $$G$$. Аналогичный вывод имеет место и в случае предположения $$f_1(x_1)<f_1(x_2)$$.

С другой стороны, при выполнении условий $$f(x_1)=f(x_2)$$ и $$f_1(x_1)=f_1(x_2)$$ будет также выполняться равенство $$f_2(x_1)=f_2(x_2)$$. Следовательно, точки $$х_, х_2$$ из одной поверхности уровня развертки $$f(x)$$ будут находиться и на каких-то поверхностях уровней разверток $$f_1(x)$$ и $$f_2(x)$$. Более того, при выполнении указанных равенств для любой пары точек $$х_1, х_2$$, принадлежащих любому фиксированному множеству из одной поверхности уровня развертки $$f(x)$$, все точки множества будут лежать на одной и той же поверхности уровня развертки $$f_1(x)$$ и на одной и той же поверхности уровня развертки $$f_2(x)$$. Действительно, пусть в рассматриваемом множестве имеется точка $$x$$, отличная от точек $$x_1, x_2$$. Тогда при выполнении условий $$f(x_1)=f(x)$$ и $$f_1(x_1)=f_1(x)$$ для пары точек $$x_1, x$$ будет выполняться и равенство $$f_2(x_1)=f_2(x)$$. Но значения $$f_1(x_1)$$ и $$f_2(x_1)$$ однозначно определяют поверхности уровней.

Конечно, в частном случае рассматриваемое множество может полностью совпадать со всей поверхностью уровня. Предположим, что каждая поверхность уровня развертки $$f(x)$$ содержится в какой-то поверхности уровня развертки $$f_1(x)$$ или $$f_2(x)$$. Все три развертки относятся к одному и тому же графу. Поэтому число всех вершин во всех поверхностях уровней для каждой развертки будет одним и тем же. Отсюда вытекает, что рассматриваемые как множества совокупности всех поверхностей уровней разверток $$f_1(x),f_2(x)$$ и $$f(x)$$ совпадают.

Пусть для графа алгоритма $$G$$ построены обобщенные развертки $$f_1(x),f2(x),\ldots,f_s(x)$$, где $$s\ge 2$$. Функционал $$F_k(x)=f_1(x)+f_2(x)+\ldots+f_k(x)$$ также будет обобщенной разверткой при любом $$к\ge 1$$. Теперь по развертке $$F_s(x)$$ в соответствии с ее поверхностями уровней расщепим множество вершин графа алгоритма на последовательно связанные между собой группы. Возьмем далее развертку $$F_(s-1)(x)$$ и в соответствии с ее поверхностями уровней расщепим каждую из групп на подгруппы. Каждая из подгрупп соответствует пересечению поверхностей уровней разверток $$F_s(x)$$ и $$F_{s-1}(x)$$. Допустим, что на поверхности уровня развертки $$F_s(x)$$ имеются такие точки $$х_1$$ и $$х_2$$, что $$F_{s-1}(x_1)\neq F_{s-1}(x2)$$. Согласно сказанному выше точки $$х_1$$ и $$x_2$$ не могут быть связаны путем графа $$G$$. Вследствие условия $$F_{s-1}(x_1)\neq F_{s-1}(x_2)$$ они заведомо принадлежат разным подгруппам. По этой причине любые две точки $$х_1$$ и $$x_2$$, взятые по одной из этих двух подгрупп, не могут удовлетворять условию $$F_{s-1}(x_1)=F_{s-1}(x_2)$$. Поэтому подгруппы оказываются параллельными.

Если на каждой поверхности уровня развертки $$F_s(x)$$ для любой пары точек $$x_1$$ и $$х_2$$ будет выполняться равенство $$F_{s-1}(x_1)=F_{s-1}(x_2)$$, то в соответствии со сказанным ранее это означает, что поверхности уровней разверток $$F_s(x), F_{s-1}(x)$$ и $$f_s(x)$$ совпадают. Следовательно, по сравнению с набором разверток $$f_(x), f_2(x),\ldots,f_{s-i}(x)$$ развертка $$f_s(x)$$ не добавляет новой информации в отношении распределения вершин-точек графа по поверхностям уровней и ее можно исключить из рассмотрения. В случае успешного использования развертки $$f_s(x)$$ далее пытаемся расщепить подгруппы на параллельные множества с помощью развертки $$F_{s-2}(x)$$ и т.д.

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

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

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

Будем по-прежнему считать, что граф алгоритма расположен в арифметическом пространстве X подходящей размерности. В этом случае без ограничения общности дуги графа можно рассматривать как векторы. С практической точки зрения целесообразно использовать самые простые развертки. Развертка задается функционалом, определенным на конечном множестве вершин-точек. Тем не менее, ничто не мешает рассматривать любые подходящие расширения функционалов на все пространство X. Ясно, что в первую очередь следует изучить возможность использования линейных функционалов.

Пусть векторы $$s_1,\ldots,s_p$$ описывают множество дуг графа. Предположим, что для некоторого вектора $$q$$ выполняются условия $$(s_i,q)>0\;((s_i,q)\ge 0)$$ для всех $$i$$. Будем называть граф строго направленным (направленным) относительно вектора $$q$$, а сам вектор $$q$$ - строго направляющим (направляющим) вектором графа. Рассмотрим в пространстве $$X$$ линейный функционал $$(x,q)$$ и его поверхности уровней $$(x,q)=c$$ для различных значений константы $$c$$. Если дуга $$s$$ графа идет из вершины $$u$$ в вершину $$v$$, то $$s=v-u$$. Согласно определению, для строго направленного (направленного) относительно вектора $$q$$ графа должно выполняться неравенство $$(v-u,q)>0\; ((v-u,q)\ge 0)$$ или $$(v,q)>(u,q)\; ((v,q)\ge (u,q))$$. Поэтому для строго направленного (направленного) относительно вектора $$q$$ графа функционал $$(x,q)$$ определяет строгую (обобщенную) развертку. Развертки вида $$(x,q)$$ будем называть линейными.

Уравнения $$(x,q)=c$$ при разных значениях $$c$$ задают в $$X$$ некоторое семейство гиперплоскостей. По отношению к дугам графа это семейство обладает важными свойствами, которые нагляднее всего описать геометрически. Именно, для строго направленного графа дуги могут проходить через любую гиперплоскость только из отрицательного (неположительного) полупространства в неотрицательное (положительное) полупространство. Никакие дуги не могут лежать на самой гиперплоскости, поскольку вершины графа на гиперплоскости представляют не что иное как поверхность уровня развертки $$(x,q)$$. Для направленного графа дуги могут проходить через гиперплоскость только из неположительного полупространства в неотрицательное полупространство. Какие-то дуги могут лежать на гиперплоскости. Но ни для какого направленного графа дуги не могут пересекать ни одну гиперплоскость в противоположных направлениях. Единственное, что допускается, - это нахождение каких-то дуг на каких-то гиперплоскостях и только для графа, направленного не строго относительно вектора $$q$$.

Выберем возрастающую последовательность чисел $$c_0,c_1,\ldots,c_m$$. Будем считать для определенности, что в отрицательном (неотрицательном) полупространстве гиперплоскости $$(x,q)=c_0\; ((x,q)=c_m)$$ нет ни одной вершины графа, а в каждом из полуслоев $$c_j\le(x,q)<c_{j+1}$$ для всех $$j,\; 1\le j\le m-1$$, имеется хотя бы по одной вершине. С позиций макровычислений полуслои похожи на "толстые" поверхности уровней обобщенных разверток. Допустим, что дуга связывает две вершины из разных полуслоев. Если $$j=1,\ldots,m-1$$ считать номером полуслоя, то любая дуга может идти лишь из полуслоя с меньшим номером в полуслой с большим номером. Это тривиальное замечание вскоре будет эффектно использовано. Очевидно, что соответствующие полуслоям операции алгоритма можно выполнять последовательно полуслой за полуслоем согласно росту номера $$j$$.

Пусть снова векторы $$s_1,\ldots,s_p$$ описывают все множество дуг графа. Но теперь предположим, что для графа найдено $$r\ge 2$$ линейно независимых векторов $$q_1,\ldots,q_r$$, строгой или нестрогой направленности. Для всех $$i,j$$ построим по описанным только что правилам гиперплоскости $$(x,q_i)=c_j^i$$ и полуслои $$c_j^i\le(x,q_i)<c_{j+1}^i$$. Перенумеруем относящиеся к векторам $$q_i$$ полуслои подряд натуральными числами $$\alpha_j^i$$, в соответствии с ростом номеров $$j$$. Пересечение любых $$r$$ полуслоев, соответствующих разным векторам $$q_i$$ представляет полуоткрытый параллелепипед. Поэтому все вершины графа оказываются распределенными по некоторой r -мерной системе непересекающихся полуоткрытых параллелепипедов, гранями которых являются построенные гиперплоскости. Внутри каждого параллелепипеда расположен некоторый подграф, описывающий какой-то фрагмент алгоритма. Тем самым получено разбиение на отдельные фрагменты всего алгоритма. Основной вопрос заключается в том, возможно ли правильно реализовать алгоритм в целом, выполняя в каком-либо порядке отдельные его фрагменты, и если возможно, то как это делать?

Каждый параллелепипед однозначно характеризуется r -мерной совокупностью своих номеров $$\alpha_1,\alpha_2,\ldots,\alpha_r$$. Рассмотрим два параллелепипеда с номерами $$\alpha_1,\alpha_2,\ldots,\alpha_r$$ и $$\beta_1,\beta_2,\ldots,\beta_r$$. По построению, дуга из первого параллелепипеда может идти во второй только в том случае, когда для всех $$i=1,2,\ldots,r$$ выполняются нестрогие неравенства $$\alpha_i\le\beta_i$$, и хотя бы для одного значения $$i$$, например, равного $$j$$, имеет место строгое неравенство $$\alpha_j<\beta_j$$. Просуммировав почленно все эти неравенства, заключаем, что необходимо должно выполняться суммарное неравенство $$\alpha_1+\alpha_2+\ldots+\alpha_r<\beta_1+\beta_2+\ldots+\beta_r$$. Разобьем параллелепипеды на группы, относя к одной группе те и только те из них, которые будут иметь одинаковые суммы номеров $$\alpha=\alpha_1+\alpha_2+\ldots+\alpha_r$$. Как вытекает из суммарного неравенства, в одной группе не могут существовать параллелепипеды, связанные между собой дугами графа. Из него же следует, что дуга не может идти из параллелепипеда с большей суммой номеров в параллелепипед с меньшей суммой номеров. Упорядочим группы по росту суммы номеров, начиная с $$\alpha=1$$. Возможно, некоторые из групп окажутся пустыми. Однако это не мешает выполнять группы фрагментов последовательно друг за другом в порядке роста суммы номеров. Внутри же каждой группы фрагменты не связаны между собой и их можно выполнять параллельно.

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

Пусть граф является строго направленным относительно какого-то вектора $$q$$. Из соображений непрерывности ясно, что всегда можно найти полный базис близких к $$q$$ векторов, по отношению к которым граф также является строго направленным. Однако их прямое использование не всегда бывает целесообразным или даже становится невозможным. Если среди дуг графа много таких, которые близки к ортогональным по отношению к вектору $$q$$, то это приводит к появлению сильно сжатых вдоль вектора $$q$$ параллелепипедов. Нередко такое сжатие оказывается тем сильнее, чем больше сам граф, что, в свою очередь, влечет за собой большие вычислительные и организационные трудности в реализации макроопераций. На практике более удобно иметь дело с направляющими векторами, близкими к ортогональным между собой, даже если по отношению к ним графы направлены и не строго.

Очень важно, что размеры всех макроопераций можно регулировать за счет выбора "толщины" полуслоев. Предположим, что макрооперации реализуются на отдельных процессорах многопроцессорной вычислительной системы. В общем случае, при увеличении параллелепипеда количество попавших в него операций алгоритма, т.е. время реализации макрооперации, растет как объем параллелепипеда. Количество же связей с другими макрооперациями, т.е. количество дуг, пересекающих грани параллелепипеда, растет как площадь его поверхности. Объем растет быстрее площади поверхности. Поэтому при увеличении макроопераций полезная загруженность процессоров будет увеличиваться, поскольку на выполнение собственно самих операций будет тратиться относительно больше времени, чем на обмен информацией с другими процессорами.

Одним из самых интересных классов алгоритмов, графы которых оказываются направленными, являются рекуррентные соотношения. Рассмотрим конечномерное пространство целочисленных вектор-индексов $$x$$ с лексикографическим порядком и в нем непустую область $$D$$. Соотношения вида$$u(x)=F_x(u(x-x_1),u(x-x_2),\ldots,u(x-x_r)),\;x\in D,$$ называются рекуррентными соотношениями с линейными индексами, если вектор-индексы $$x_1,\ldots,x_r$$ фиксированы, целочисленные и не зависят от $$x$$. Функции $$F_x$$ могут быть произвольными, в том числе как линейными, так и нелинейными. Выполняются эти соотношения в порядке лексикографического роста вектор-индекса $$x$$. Если какой-либо из векторов $$x-x_i$$ не принадлежит области $$D$$, то соответствующая переменная $$u(x-x_i)$$ считается заданной и представляет одно из входных данных алгоритма.

Будем размещать вершины графа алгоритма в точках области $$D$$ с целочисленными координатами. Вершине, задаваемой вектором $$x$$, поставим в соответствие функцию $$F_x$$. Если $$x\in D$$, то из рекуррентных соотношений вытекает, что в вершину $$x$$ будут входить дуги из вершин $$x-x_1,\ldots,x-x_r$$ и только из этих вершин. В случае, когда какой-то из векторов $$x-x_i$$ не принадлежит области $$D$$, вектор $$x-x_i$$ будет символизировать функцию ввода переменной $$u(x-x_1)$$. Построенный таким образом граф имеет очень простую структуру. Если дуги задавать векторами, то в каждую вершину из области $$D$$ будет входить один и тот же пучок дуг, который переносится параллельно от одной вершины к другой. Графы подобного вида называются регулярными, а образующие их векторы $$x_1, \ldots, x_r$$ - базовыми. Заметим, что при других размещениях вершин графа алгоритма регулярная структура дуг может нарушаться. Данный пример наглядно подтверждает важность согласования формы записи алгоритма с формой представления его графа.

Регулярные графы совсем не обязательно связывать с рекуррентными соотношениями. Важно лишь, чтобы вершины графов располагались в точках с целочисленными координатами. Тогда сами графы можно строить, просто перенося пучок заданных базовых векторов $$x_1,\ldots,x_r$$ от одной вершины к другой. В общем случае такие графы могут иметь контуры, т.е. не быть графами никаких алгоритмов. Однако доказано , что регулярный граф, вершины которого расположены в точках с целочисленными координатами, не имеет контуры тогда и только тогда, когда существует вектор $$q$$, относительно которого граф является строго направленным. Не ограничивая общности, вектор $$q$$ можно считать целочисленным. Поскольку все дуги графа описываются базовыми векторами $$x_1,\ldots,x_r$$, то должны выполняться строгие неравенства $$(x_1,q)>0,(x_2,q)>0,\ldots,(x_r,q)>0$$. В этом случае заведомо существует столько строгих независимых линейных разверток, какова размерность линейной оболочки векторов $$x_1,\ldots,x_r$$. Тем не менее, как уже отмечалось, использовать их можно лишь с определенной осторожностью. С практической точки зрения во многих случаях удобнее брать линейные обобщенные развертки, направляющие векторы которых совпадают с направляющими векторами граней выпуклого конуса, образованными векторами $$x_1,\ldots,x_r$$. В силу целочисленности координат базовых векторов, направляющие векторы разверток всегда можно выбрать целочисленными.

Допустим, что для регулярного графа найдена линейная развертка $$(x,q)$$ с целочисленным вектором $$q$$. Так как вершины графа расположены в точках с целочисленными координатами, то уравнение любой поверхности уровня $$(x,q)=с$$ есть уравнение гиперплоскости с целыми коэффициентами. Очевидно, что граф покрывается конечной системой таких гиперплоскостей. Расстояние между соседними гиперплоскостями не меньше, чем $$d\|q\|^{-1}_E$$, где $$d$$ - наибольший общий делитель модулей ненулевых координат вектора $$q,\; \|\cdot\|_E$$, - евклидова норма вектора . Желание минимизировать время реализации алгоритма приводит к минимизации числа гиперплоскостей, покрывающих граф. Если не принимать во внимание частные особенности графов, то вектор $$q$$ следует выбирать так, чтобы величина $$d\|q\|^{-1}_E$$ была максимальной.