Структура описания свойств алгоритмов

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

Общая схема описания алгоритмов имеет следующий вид:

1 ЧАСТЬ I. Описание свойств и структуры алгоритмов: общая часть

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

2 1.1. Словесное описание алгоритма

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

3 1.2. Математическое описание

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

4 1.3. Вычислительное ядро алгоритма

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

5 1.4. Макроструктура алгоритма

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

6 1.5. Описание схемы реализации последовательного алгоритма

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

7 1.6. Последовательная сложность алгоритма

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

8 1.7. Информационный граф

Приводится описание (изображение) информационного графа данного алгоритма (графа алгоритма). Для картинок с изображением графа будут составлены рекомендации по их формированию, чтобы все графы библиотеки можно было бы воспринимать и интерпретировать одинаково. Можно привести описание графа в терминах покрывающих функций. В данном разделе многое еще подлежит обсуждению: проекции, возможность повертеть граф при его отображении на экране компьютера, отражение на графе ярусно-параллельной формы и т.д. и т.п. Данный раздел очень важен, и он еще явно будет детализироваться в будущем. Главное – показать информационную структуру алгоритма так, чтобы стали понятны все его особенности.

9 1.8. Описание ресурса параллелизма алгоритма

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

10 1.9. Описание входных и выходных данных

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

11 1.10. Свойства алгоритма

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

• соотношение последовательной и параллельной сложности данного алгоритма,
• вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных,
• сбалансированность типов операций,
• детерминированность алгоритма, которая может определяться:
• * числом итераций,
• * структурами данных (например, структура разреженности матриц),
• * использование датчиков случайных чисел,
• * использование другого порядка выполнения ассоциативных операций, что может привести к накоплению ошибок округления.
• особенности семейств дуг информационного графа, регулярность, наличие "длинных" дуг в информационном графе,
• интенсивность работы с данными, степень исхода вершин информационного графа,
• известные компактные укладки графа (что важно, например, для проектирования специализированных процессоров или реализации алгоритма на ПЛИС).

11.1 ЧАСТЬ II. Описание свойств и структуры алгоритмов: программная реализация

Данная часть рассматривает все составные части процесса реализации описанного выше алгоритма. Реализация последовательная и параллельная. Свойства программы и особенности архитектуры компьютера. Работа с памятью, локальность данных и вычислений. Особенности реализации параллелизма. Свойства параллельных программ: масштабируемость, эффективность. Привязка к классам архитектур.

12 2.1. Особенности реализации последовательного алгоритма

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

13 2.2. Описание локальности данных и вычислений

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

14 2.3. Возможные способы и особенности реализации параллельного алгоритма

Раздел довольно обширный, в котором, в частности, предполагается описывать:

• представленный иерархически ресурс параллелизма, опирающийся на структуру вхождения циклических конструкций и на структуру графа вызовов программы,
• комбинацию (иерархию) массового параллелизма и параллелизма конечного,
• возможные способы распределения операций между процессами/нитями,
• возможные способы распределения данных,
• оценку количества операций, объёма и количества пересылок данных (общего и в пересчёте на процесс).

В дальнейшей работе данный раздел будет дополняться.

15 2.4. Масштабируемость алгоритма и его реализации

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

16 2.5. Динамические характеристики и эффективность реализации алгоритма

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

17 2.6. Выводы для классов архитектур

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

18 2.7. Существующие реализации алгоритма

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