Структура описания свойств алгоритмов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 3: Строка 3:
 
Общая схема описания алгоритмов имеет следующий вид:
 
Общая схема описания алгоритмов имеет следующий вид:
  
[[ЧАСТЬ I. Описание свойств и структуры алгоритмов: общая часть]]<br />
+
=== ЧАСТЬ I. Описание свойств и структуры алгоритмов: общая часть ===
1.1. Словесное описание алгоритма<br />
+
Свойства алгоритмов никак не зависят от вычислительных систем, существующих сейчас или будущих, и с этой точки зрения данная часть имеет безусловную собственную ценность. Каждый раз, когда будет возникать задача эффективной реализации алгоритма на некотором компьютере, ответ на вопрос о потенциальных возможностях самого алгоритма будет содержаться в этой части. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах.
1.2. Математическое описание<br />
+
== 1.1. Словесное описание алгоритма ==
1.3. Вычислительное ядро алгоритма<br />
+
В данном разделе представляется самый первый вариант описания той задачи, для решения которой предназначен алгоритм. Описание словесное, в котором, поясняются все особенности как алгоритма, так и объектов, с которыми он работает. Если описание соответствует целому классу схожих по структуре алгоритмов, либо же посвящено описанию отдельного представителя некоторого класса, то это здесь указывается явно. Описываются математические свойства и структура входных данных. При необходимости, в словесном описании могут присутствовать формулы, а также даваться ссылки на описания других используемых алгоритмов. Данное описание должно быть достаточным для однозначного понимания сути решаемой задачи.
1.4. Макроструктура алгоритма<br />
+
== 1.2. Математическое описание ==
1.5. Описание схемы реализации последовательного алгоритма<br />
+
Приводится математическое описание решаемой задачи в виде совокупности формул и соотношений, как это принято в книгах и учебниках. По возможности, используются общепринятые обозначения и способы записи. Должны быть явно определены все использованные обозначения, а также предположения относительно свойств входных данных. Представленное описание должно быть достаточным для однозначного понимания постановки решаемой задачи для человека, знающего математику.
1.6. Последовательная сложность алгоритма<br />
+
== 1.3. Вычислительное ядро алгоритма ==
1.7. Информационный граф<br />
+
В описываемом алгоритме выделяется и описывается вычислительное ядро, т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то описываются все ядра. Описание может быть произвольным: словесным или с использованием языка математических формул, но достаточным для однозначного понимания вычислительных ядер алгоритма. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.
1.8. Описание ресурса параллелизма алгоритма<br />
+
== 1.4. Макроструктура алгоритма ==
1.9. Описание входных и выходных данных<br />
+
Если алгоритм использует в качестве составных частей другие алгоритмы данной библиотеки, то это указывается в данном разделе. Если в дальнейшем имеет смысл описывать алгоритм не в максимально детализированном виде, а давать только его макроструктуру, то здесь описывается структура и состав макроопераций, а также даются пояснения, необходимые для однозначной интерпретации излагаемого ниже материала.
1.10. Свойства алгоритма<br /><br />
+
== 1.5. Описание схемы реализации последовательного алгоритма ==
 +
Описываются все шаги, которые нужно выполнить для последовательной реализации данного алгоритма. Описание может быть выполнено в виде блок-схемы, последовательности математических формул, макроопераций, обращений к описанию других алгоритмов и т.п. Не обязательно все шаги детализировать до отдельных арифметических операций, отдельные шаги могут соответствовать крупным операциям или отдельным алгоритмам данной библиотеки. Описание может содержать пояснения, отражающие тонкие детали реализации.
 +
== 1.6. Последовательная сложность алгоритма ==
 +
Приводится оценка последовательной сложности алгоритма: число операций, которые нужно выполнить для получения результата работы алгоритма. Для каждого алгоритма понятие операции, в терминах которой оценивается его сложность, может различаться. Это могут быть операции для работы с вещественными числами, целыми числами, поразрядные операции, обращения в память, элементарные функции, макрооперации и т.п. Необходимо явно указать, какие операции учитываются при подсчете сложности алгоритма, и если выбор конкретного типа операций не очевиден, то привести обоснование сделанного выбора. В некоторых случаях можно приводить оценку не всего алгоритма, а его вычислительного ядра, в таком случае это нужно отметить, сославшись на п.3. Если в будущее будем вводить классификацию алгоритмов по классам сложности, то здесь это нужно указать.
 +
== 1.7. Информационный граф ==
 +
Приводится описание (изображение) информационного графа данного алгоритма (графа алгоритма). Для картинок с изображением графа будут составлены рекомендации по их формированию, чтобы все графы библиотеки можно было бы воспринимать и интерпретировать одинаково. Можно привести описание графа в терминах покрывающих функций. В данном разделе многое еще подлежит обсуждению: проекции, возможность повертеть граф при его отображении на экране компьютера, отражение на графе ярусно-параллельной формы и т.д. и т.п. Данный раздел очень важен, и он еще явно будет детализироваться в будущем. Главное – показать информационную структуру алгоритма так, чтобы стали понятны все его особенности.
 +
== 1.8. Описание ресурса параллелизма алгоритма ==
 +
Приводится оценка параллельной сложности алгоритма: число шагов, за которое можно выполнить данный алгоритм, в предположении доступности неограниченного числа необходимых исполнителей (процессоров, функциональных устройств, вычислительных узлов, нитей и т.п.). Иными словами, параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы. Необходимо указать, в терминах каких операций дается оценка. Необходимо описать сбалансированность параллельных шагов по числу и типу операций, что определяется шириной ярусов канонической ярусно-параллельной формы. В информационном графе необходимо указать ключевые параллельные ветви, которые определяют основную долю доступного параллелизма. Необходимо описать ресурс параллелизма в виде суперпозиции конечного и массового параллелизма.
 +
== 1.9. Описание входных и выходных данных ==
 +
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма. Векторы, матрицы, скаляры, множества… Плотные или разреженные. Объем. Предположения относительно диапазона значений (например, нули на диагонали, близость к машинному нулю, к максимально представимому числу, характер разреженности и т.п.).
 +
== 1.10. Свойства алгоритма ==
 +
В данном разделе описываются свойства алгоритма, которые могут оказаться важными на этапе реализации. Никакой привязки к какой-либо конкретной программно-аппаратной среде не предполагается. В частности, можно рассмотреть следующие свойства:
 +
* соотношение последовательной и параллельной сложности данного алгоритма,
 +
* вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных,
 +
* сбалансированность типов операций,
 +
* детерминированность алгоритма, которая может определяться:
 +
* * числом итераций,
 +
* * структурами данных (например, структура разреженности матриц),
 +
* * использование датчиков случайных чисел,
 +
* * использование другого порядка выполнения ассоциативных операций, что может привести к накоплению ошибок округления.
 +
* особенности семейств дуг информационного графа, регулярность, наличие "длинных" дуг в информационном графе,
 +
* интенсивность работы с данными, степень исхода вершин информационного графа,
 +
* известные компактные укладки графа (что важно, например, для проектирования специализированных процессоров или реализации алгоритма на ПЛИС).
  
[[ЧАСТЬ II. Описание свойств и структуры алгоритмов: программная реализация]]<br />
+
=== ЧАСТЬ II. Описание свойств и структуры алгоритмов: программная реализация ===
2.1. Особенности реализации последовательного алгоритма<br />
+
Данная часть рассматривает все составные части процесса реализации описанного выше алгоритма. Реализация последовательная и параллельная. Свойства программы и особенности архитектуры компьютера. Работа с памятью, локальность данных и вычислений. Особенности реализации параллелизма. Свойства параллельных программ: масштабируемость, эффективность. Привязка к классам архитектур.
[[2.2. Описание локальности данных и вычислений]]<br />
+
== 2.1. Особенности реализации последовательного алгоритма ==
2.3. Возможные способы и особенности реализации параллельного алгоритма<br />
+
Описываются особенности и варианты реализации алгоритма в виде последовательной программы, которые влияют на эффективность ее выполнения. Например, в данном разделе имеет смысл сказать о существовании блочных вариантов реализации алгоритма, дополнительно описав потенциальные преимущества или недостатки, сопровождающие такую реализацию. Важный вопрос – организация работы с данными, используемые структуры данных, временные массивы и т.п.
2.4. Масштабируемость алгоритма и его реализации<br />
+
== [[2.2. Описание локальности данных и вычислений]] ==
2.5. Динамические характеристики и эффективность реализации алгоритма<br />
+
Приводятся оценки степени локальности данных и вычислений в программе, причем рассматривается как временнáя, так и пространственная локальность. Отмечаются позитивные и негативные факты, какие ситуации и при каких условиях могут возникать. Исследуется, как меняется локальность при переходе от последовательной к параллельной реализации. Выделяются ключевые шаблоны взаимодействия с памятью. Отмечается взаимосвязь между используемыми конструкциями языков программирования и степенью локальности, которыми обладают результирующие программы (связь статики и динамики). Приводятся профили взаимодействия с памятью для вычислительных ядер и ключевых фрагментов.
2.6. Выводы для классов архитектур<br />
+
== 2.3. Возможные способы и особенности реализации параллельного алгоритма ==
2.7. Существующие реализации алгоритма
+
Раздел довольно обширный, в котором, в частности, предполагается описывать:
 +
* представленный иерархически ресурс параллелизма, опирающийся на структуру вхождения циклических конструкций и на структуру графа вызовов программы,
 +
* комбинацию (иерархию) массового параллелизма и параллелизма конечного,
 +
* возможные способы распределения операций между процессами/нитями,
 +
* возможные способы распределения данных,
 +
* оценку количества операций, объёма и количества пересылок данных (общего и в пересчёте на процесс).
 +
В дальнейшей работе данный раздел будет дополняться.
 +
== 2.4. Масштабируемость алгоритма и его реализации ==
 +
Все особенности реализации алгоритма, влияющие на масштабируемость, должны быть описаны в этом разделе. Полезно привести реальные показатели масштабируемости какой-либо модельной реализации алгоритма при изменении как числа процессоров, так и размера задачи. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки. Привести оценки или провести исследование сильной и слабой масштабируемости реализации/алгоритма.
 +
== 2.5. Динамические характеристики и эффективность реализации алгоритма ==
 +
Масштабный раздел, поскольку оценка эффективности реализации алгоритма требует комплексного подхода, вовлекающего все этапы от архитектуры компьютера до самого алгоритма. В любом случае, требуется оценить и прокомментировать эффективность работы с памятью (особенности профиля работы с памятью), эффективность использования заложенного в алгоритм ресурса параллелизма, эффективность использования коммуникационной сети (особенности коммуникационного профиля), эффективность операций ввода/вывода и т.п.
 +
== 2.6. Выводы для классов архитектур ==
 +
Пока не очень понятно, как в данный документ включать рекомендации для классов архитектур: все сводить в один текущий раздел или же соответствующие факты сразу включать туда, где они необходимы в расположенных выше разделах. Быть может, имеет смысл делать отдельные варианты главы II применительно к отдельным классам архитектур. Решение станет понятнее со временем, когда накопим критическую массу сведений, а сейчас все относящееся к данной теме сведения будем сводить сюда. Важно указывать и позитивные, и негативные факты по отношению к конкретным классам. Можно говорить о возможных вариантах оптимизации, ориентированных на целевые классы архитектур. Имеет смысл выделять и отдельных представителей в классах, если их архитектура обладает специфическими особенностями, влияющими на эффективность реализации.
 +
== 2.7. Существующие реализации алгоритма ==
 +
Данный раздел предназначен для того, чтобы описать основные уже существующие последовательные и параллельные реализации, доступные для использования сейчас. Дополнительно следует указать, является ли реализация коммерческой, свободной или же распространяется под какой-то специальной лицензией, привести местоположение дистрибутива и описаний, указать достоинства и недостатки различных реализаций.

Версия 12:58, 17 июля 2014

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

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

Содержание

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. Существующие реализации алгоритма

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