Разработка и оценка сложности алгоритмов, находящих применение в аппаратном и программном обеспечении многопроцессорных систем

В настоящее время постоянно увеличивающийся спрос на облачные вычисле- ния приводит к росту крупномасштабных центров обработки данных (ЦОД). Современные ЦОД содержат сотни тысяч узлов, соединенных между собой се- тью. Топология такой сети, т.е. способ соединения узлов, является ключевым звеном, от которого зависит быстродействие, отказоустойчивость, надежность и другие характеристики ЦОД. По этой причине проектирование сети является очень важной задачей, включающей в себя поиск моделей графов, которые име- ют хорошие топологические свойства и позволяют использовать эффективные алгоритмы маршрутизации. Этими качествами обладают графы Кэли, имею- щие такие привлекательные топологические свойства как высокая симметрия, иерархическая структура, рекурсивная конструкция, высокая связность и от- казоустойчивость [60]. Определение графа Кэли подразумевает, что вершины графа являются элементами некоторой алгебраической группы. Выбор группы и ее порождающих элементов позволяет получить граф, отвечающий необходи- мым требованиям по диаметру, степени вершин, количеству узлов и т. д. [65].
Пусть G := ⟨X⟩ – конечная группа, порожденная упорядоченным мно- жеством X := {x1 ≺ x2 ≺ … ≺ xm}, которое также называют алфавитом. Множество всех слов (строк) над алфавитом X будем обозначать X∗. Пусть w := x1x2 …xl – слово над X и |w| := l – его длина. На множестве X∗ так- же определим отношение порядка. Пусть v и w – два произвольных слова в алфавите X. Тогда v ≺ w, если |v| < |w|, а в случае равенства длин слов, 3 4 меньшее слово будет определяться согласно введенному лексикографическому порядку на порождающих. Если необходимо подчеркнуть, что строка v ∈ X∗ соответствует элементу g ∈ G, то мы будем писать vg. Строку v будем назы- вать минимальным словом элемента g, если для всех других w ∈ X∗, таких что vg = wg, будет выполняться v ≺ w. Очевидно, что каждому g ∈ G соответству- ет уникальное минимальное слово. Длиной элемента группы g будем называть длину его минимального слова v, т. е. |g| := min{|vg| : vg ∈ X∗}. Заметим, что в общем случае задача по определению минимального слова является NP- сложной [56]. Графом Кэли Γ := Cay(G,X) группы G относительно X называют ори- ентированный невзвешенный помеченный граф с множеством вершин V (Γ) := {g | g ∈ G}имножествомреберE(Γ) := {(g,gx) | x ∈ X,g ∈ G}. Пусть (g,gx) ∈ E(Γ), тогда генератор x называют меткой данного ребра. Ес- ли X = X ∪ X−1, то граф Γ будет неориентированным. Будем считать, что единичный элемент e ∈/ X, т. е. в Γ нет петель. Как известно [61], кратчай- шее расстояние между двумя произвольными вершинами графа g и h, которое мы обозначим d(g,h), равно длине минимального слова элемента g−1h, т. е. d(g, h) := |g−1h|. Остановимся на известных к настоящему времени алгоритмах маршрути- зации на графах Кэли. Традиционные методы, такие как алгоритмы Дейкстры или Беллмана-Форда, могут использоваться на графах любого вида, но тре- буют значительных пространственных и временных ресурсов [78]. Для неко- торых семейств графов Кэли существуют особые алгоритмы маршрутизации, которые в отличие от традиционных методов, используют топологические ха- рактеристики графа, уменьшая при этом временную и/или пространственную сложность. Сюда можно отнести такие семейства графов как гиперкуб [83], бабочка [84] и звездный граф [62], которые являются графами Кэли. В рабо- те [51] представлен алгоритм маршрутизации для pancake и звездных графов, основанный на сортировке перестановок. Однако этот подход не обеспечива- 5 ет маршрутизацию по кратчайшему пути. К. Тэнг и Б. Арден доказывают [85], что все конечные графы Кэли могут быть представлены обобщенными хордальными кольцами, а затем предлагают итерационный алгоритм маршру- тизации, основанный на таблице поиска. Пространственная сложность такого алгоритма составляет O(|G|2), а временная – O(D), где |G| и D – размер и диаметр сети соответственно. Л. Вэнг и К. Тэнг в [88] для поиска кратчайших путей на графе Бореля предлагают алгоритм, который сначала вычисляет в автономном режиме таблицу маршрутизации от одного узла ко всем осталь- ным; затем, используя свойство транзитивности графа Кэли, создает таблицу маршрутизации для всех узлов. Вычислительная сложность данного алгорит- ма ограничена O(log4 |G|), а пространственная – O(|G|2D). В [71] представлен распределенный отказоустойчивый алгоритм маршрутизации на графе Бореля. Этот двухфазный алгоритм использует два типа таблиц маршрутизации: ста- тическую и динамическую. В статье [80] представлен алгоритм маршрутизации для специального класса графов Кэли, используемых в качестве топологии сети беспроводного ЦОД. Данный алгоритм является двухуровневым: для отправки сообщений между серверами в одной стойке и серверами в разных стойках. В работах [63, 26, 27, 28, 64, 25] исследуются графы Кэли конечных групп Берн- сайда периода 3, 4, 5 и 7. Монография [57] представляет собой фундаментальную работу о взаимо- связи алгебраических групп и конечных автоматов. В этом случае на группе G = ⟨X⟩ определяется автоматная структура специального вида, используя которую, можно вычислить минимальное слово для любого элемента груп- пы. Согласно [57] конечный автомат группы A считывает произвольное сло- во wg ∈ X∗, обрабатывает его и выдает минимальное слово элемента g. При этом время T0 обработки слова w будет пропорционально квадрату его длины, т. е. T0 = O(|w|2). Используя данный результат, в работе [53] был предложен алгоритм поиска кратчайшего пути на графе Кэли (обозначим его A–0), при этом его вычислительная сложность ограничена O(D2), а пространственная – 6 M0 = O(|X| · |G| + |A|), где |A| – число состояний автомата группы. Заметим также, что при построении больших сетей будет выполняться |X| ≪ |G|, отсюда следует, что O(|X| · |G|) = O(|G|). Отметим, что все представленные выше алгоритмы маршрутизации могут быть отнесены в одну из следующих категорий: а) те, которые предназначены для конкретных графов Кэли; б) универсальные с высокой пространственно- временной сложностью и в) с низкой сложностью, которые не обеспечивают кратчайших путей. Для многопроцессорных вычислительных систем (МВС) актуален ряд на- правлений исследований. Одним из них являются исследования, связанные с перспективными языками программирования, которые могут разрабатываться в дальнейшем для обеспечения работы с МВС. Практически все известные в настоящее время языки программирова- ния являются контекстно–свободными языками (кс–языками), порождёнными контекстно–свободными грамматиками (кс–грамматиками). Рассмотрим необ- ходимые определения. Исходным объектом в теории программирования, а также теории кс– языков и грамматик, заложенной в работах выдающегося лингвиста Н. Хом- ского и других исследователей [48, 49, 50], является алфавит, который удобно разделять на две группы символов: z1,...,zn,x1,...,xm. Обычно символы x1, . . . , xm из второй группы называются терминальны- ми символами и образуют словарь контекстно–свободного языка [13, 18, 19]. Применительно к языкам программирования к терминальным символам отно- сятся цифры, буквы, вспомогательные знаки, а также состоящие из них «бло- ки», обозначающие, например, операторы языка программирования. Такие опе- раторы могут обозначаться в виде некоторой последовательности букв и других символов, но сами рассматриваются как неделимые символы (например, в неко- торых языках программирования операторы GOTO, RETURN и др., которые 7 сами рассматриваются как неделимые символы алфавита) [30, 33, 32, 34, 38, 47]. Символы другой группы z1, . . . , zn называются нетерминальными. Они иг- рают вспомогательную роль, не присутствуя явно в тексте программ, и нужны для задания грамматики — совокупности грамматических правил, порождаю- щих кс–язык. По правилам грамматики формируются мономы от терминальных симво- лов x1, . . . , xm, которые интерпретируются как правильные предложения языка [10, 11, 12, 72]. Такие мономы рассматриваются как корректные, в отличие от произвольных мономов, которые могут не соответствовать правилам грамма- тики и, таким образом, являются некорректными. Над символами алфавита определены три операции: 1) некоммутативная операция формального умножения — операция конкатенации; 2) коммутатив- ная операция формальной суммы (вместе с этими операциями алфавит образует такую алгебраическую структуру как полукольцо); 3) дополнительная комму- тативная операция умножения элементов алфавита, а значит, и мономов на числа (обычно достаточно рассматривать действительные числа, но в некото- рых исследованиях нужны комплексные числа) [12, 52, 58, 72]. Далее, над полукольцом можно рассматривать символьные многочлены и формальные степенные ряды (ФСР) с числовыми коэффициентами. Кс–языком называется такой ФСР, членами которого являются все корректные мономы, ко- торые порождены данной грамматикой [12, 72]. Таким образом, язык представ- ляет собой совокупность всех возможных (корректных мономов) правильных предложений, порождённых его грамматикой. Важно отметить, что в теории кс–языков имеется эффективный инстру- мент исследования — система уравнений с многочленами специального вида от символов алфавита, называемая (собственной) системой уравнений Хомского — Шютценберже. А именно, система уравнений Хомского — Шютценберже имеет вид zj = Qj(z,x), j = 1,...,n, (1) 8 при этом многочлены в правых частях удовлетворяют естественно объясни- мым требованиям: во-первых, Qj(0,0) = 0, во-вторых, многочлены Qj(z,0) не содержат линейных членов, что означает отсутствие в правилах грамматики простого переобозначения нетерминальных символов [9, 8, 11, 12, 72]. Предполагается, что указанная система решается относительно нетерми- нальных символов (z1,...,zn) = z, а решение ищется в виде ФСР от терми- нальных символов (x1,...,xm) = x : z = z(x) = (z1(x),...,zn(x)), эти ФСР, будучи подставленными в систему уравнений Хомского — Шютцен- берже, дадут верные равенства. Символ z1 играет особую роль как начальный символ в данном языке: стартовый для написания программы, либо обозначающий начало предложе- ния в естественном языке. По этой причине его выражение в виде ФСР z1(x) и есть кс–язык, который порождён грамматикой, записанной в виде системы уравнений Хомского — Шютценберже [11, 12, 72]. Вообще заметим, что именно из начального символа z1 при помощи правил подстановки (продукций) выводятся все корректные мономы языка, интерпретируемые применительно к естественным языкам как правильные предложения, а к языкам программирования — как правильные программы [1, 3, 4, 5, 6, 7, 31]. Для того, чтобы сформулировать расширенную проблему синтаксическо- го анализа (разбора), нужно конкретизировать структуру правых частей систе- мы уравнений Хомского — Шютценберже с точки зрения правил грамматики. Для этого рассмотрим грамматику кс–языка, которая является совокуп- ностью правил подстановки (продукций): zj → qj1(z,x), ... ,zj → qjpj(z,x), j = 1, ... ,n, (2) где qjk(z,x) — мономом от некоммутативных символов алфавита с числовым коэффициентом, который равен 1. 9 Вывод корректных мономов осуществляется так. Продукции сначала сле- дует применить к начальному символу z1, а затем к другим получающимся мономам неограниченное число раз и в произвольном порядке, что позволяют продуцировать новые мономы от терминальных символов и нетерминальных символов — корректный моном языка. Все корректные мономы образуют соот- ветствующий кс–язык. Теперь можно отметить, что многочлены Qj(z,x), j = 1, ... ,n, стоящие в правой части системы уравнений Хомского — Шютценберже, имеют следую- щую структуру: Qj(z,x)= qj1(z,x)+ ··· +qjpj(z,x), j = 1, . . . , n. Итак, перейдём к проблеме синтаксического анализа мономов кс–языка. В монографии, написанной академиком В. М. Глушковым в соавторстве с Г. Е. Цейтлиным и Е. Л. Ющенко сказано: «Одной из важных проблем в разра- ботке современных систем программирования является проблема синтаксиче- ского анализа программ. Процесс синтаксического анализа программы состоит в распознавании правильности данной программы, т. е. её принадлежности к рассматриваемому алгоритмическому языку. Этот этап называется этапом син- таксического контроля программы. Одновременно с контролем осуществляется описание синтаксической структуры правильных программ, подобно тому как производится грамматический разбор предложений в естественных языках» [12, с. 234]. Таким образом, выделяют две составляющие проблемы синтаксическо- го анализа, первая часть, называемая проблемой принадлежности или этапом синтаксического контроля, состоит в том, чтобы определить, принадлежит ли моном данному кс–языку, т. е. может ли быть получен из начального символа z1 при помощи продукций. Одновременно с решением первой части проблемы синтаксического анализа решается и вторая часть проблемы — описание син- таксической структуры монома. 10 Такое описание понимается различными авторами по-разному. Например, в упомянутой монографии В. М. Глушкова, Г. Е. Цейтлина и Е. Л. Ющенко отмечено: «В математической лиигвистике широко распространён способ пред- ставления синтаксической структуры языковых объектов в виде деревьев грам- матического разбора» [12, с. 303]. Например, проблема синтаксического анализа ставится следующим обра- зом — требуется разработать алгоритм, для того чтобы: — установить, какие правила подстановки и сколько раз использовались при выводе данного монома, при этом порядок использования правил подста- новки не имеет значения [42, 43]; — установить, какие правила подстановки, сколько раз и в каком поряд- ке использовались при выводе этого монома, т. е. построить хотя бы один из возможных выводов монома [3]. Как видно, для полного решения проблемы синтаксического анализа воз- можен также подход, при котором необходимо построить сразу все возможные выводы монома, если таких несколько. Кроме того, отметим следующее важное обстоятельство, которому иссле- дователи уделяют большое внимание — разработать беступиковый (беспере- бойный, безостановочный, беспереборный) алгоритм синтаксического анализа мономов кс–языка. Так, в [12, с. 248] сказано: «С точки зрения практических приложений значительный интерес представляют формализмы для описания языков, допускающие беступиковый (беспереборный) синтаксический анализ». Если алгоритм таков, что может приводить к тупикам, то он дол- жен предусматривать возвраты с анализом определённой предыстории алго- ритма, что значительно усложняет алгоритм. Однако, для произвольной кс– грамматики беступикового алгоритма синтаксического анализа на основе свёрт- ки или развёртки не существует, отмечается лишь, что «важным классом од- нозначных кс–грамматик, допускающих беступиковый анализ разверткой, яв- ляются LL(k)–грамматики» [12, с. 259]. 11 Таким образом, во–первых, имеющиеся алгоритмы достаточно сложные, во–вторых, могут решать ограниченные задачи, например, нахождения одного из возможных выводов монома. Далее, будем называть расширенной проблемой синтаксического анали- за мономов кс–языка проблему разработки беступикового алгоритма, который позволяет установить, может ли быть выведен моном при помощи системы про- дукций кс–языка (решить проблему принадлежности), а также найти сразу все выводы этого монома. Вывод монома можно представить следующим образом: определить, ка- кие продукции, сколько раз и в каком порядке применяются для вывода этого монома — именно в таком виде будем искать описание возможных выводов. Нахождение вывода в таком виде, очевидно, равносильно построению дерева вывода. Подчеркнём, что такие алгоритмы в настоящее время не известны, по- скольку для произвольных кс–грамматик разработанные известные алгоритмы (свёрткой–развёрткой и др.) могут приводить к тупикам [12]. Естественно, при разработке алгоритмов синтаксического анализа произ- вольного кс–языка значительный интерес представляет вопрос об их сложности [2, 41, 66, 79, 86, 70]. Для произвольной кс–грамматики одним из эффективных алгоритмов яв- ляется алгоритм Кока — Янгера — Касами (CYK – алгоритм или CKY – алго- ритм), позволяющий установить, можно ли в заданной кс–грамматике вывести заданную строку, и если да, то предоставить один из её выводов. Пусть дан моном (программа) w степени (длины) N. Обычно сложность алгоритма синтаксического анализа выражают через число длину монома N в виде O(f(N)), где f(N) — некоторая функция от N. Для многих алгоритмов в теоретической информатике функция f(N) яв- ляется мономом (в этом случае говорят, что сложность полиномиальная, она считается небольшой) либо экпонента (тогда сложность считается значитель- 12 ной) [2, 66, 86]. Некоторые алгоритмы, естественно, имеют сложность, которая больше, чем экспоненциальная. В процессе разработки языка программирования может понадобиться проводить синтаксический анализ тестовых программ, которые удобно рассмат- ривать как мономы кс–языка, порождаемого системой продукций. Алгоритм Кока — Янгера — Касами является универсальным в том смыс- ле, что он применим к кс–грамматике в нормальной форме Хомского, к которой можно привести произвольную кс–грамматику. Сложность алгоритма Кока — Янгера — Касами — полиномиальная и равна N3 [86]. Однако, с точки зрения разработки перспективных языков программиро- вания, в том числе для МВС, известные алгоритмы синтаксического анализа не применимы. Как правило, известные алгоритмы реализованы в виде специ- альных программ (парсеров), предназначенных для анализа выражений, напи- санных на определённом языке программирования. Однако, в ситуации, когда разрабатывается новый язык программирова- ния, никаких парсеров, естественно нет. В случае, когда необходимо провести синтаксический анализ (разбор) некоторого выражения относительно совокуп- ности грамматических правил, находящихся в стадии разработки, могут быть полезными различные алгоритмы, в том числе имеющие высокую сложность. Как правило, тестируются выражения ограниченной длины, и потому высо- кая сложность алгоритма в такой ситуации не играет роли — важно, чтобы алгоритм был простым в программной реализации и вполне конструктивным. Сложность такого алгоритма может быть даже выше экспоненциальной, что вполне допустимо для случаев, когда длина программы N не слишком велика. Таким образом, разработка беступиковых конструктивных алгоритмов для решения расширенной проблемы синтаксического анализа является доста- точно актуальной задачей [23, 55, 69, 75, 87].