001. Анализ информационной структуры алгоритмов. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

Итак, мы начинаем..! Автор предста́вленной серии статей полагает, что время для публикаций на данную (достаточно непростую) тему подошло́ как раз сейчас – появляется всё больше людей, интересующихся не только сиюсеку́ндными, сугубо пове́рхностными чувствами и событиями, но и более глубокими вопросами окружающей любого из нас действи́тельности. В широком смысле серия публикаций предназначена для любителей естествознания из произвольных общественных групп – от школьников выпускных классов до любых субъектов, обладающих свойством быть “Исследователями в глубине души́ своей”.

Данная публикация является первой в списке из таковы́х, при́званных вы́разить взгляд автора на обсуждаемую проблему. Эта статья, пожалуй, наиболее длинная среди предлага́емых 20-ти штук и связано это с необходимостью введе́ния Читателей вовнутрь предмета исследований. Предмет этот весьма обши́рен и методы достиже́ния решений в этой области простира́ются от хорошо формализуемых методик до методик, которые можно охарактеризовать термином “приёмы” и “пра́ктики” (неформальные).

● Важным является собственно сам подход к исследованию алгоритмов, постулирующий возможность исследования логической структуры о́ных без поддержки исполня́ющей системы (компьютерного “железа”). Для многих это представля́ется в высшей степени необычным и “стра́нным”… Однако создатель данной публикации склонен к расширению темы в сторону практического анализа алгоритмов, поэтому без учёта (хотя бы частичного!) архитектуры вычислительных систем обойтись не может (напр., см. публикацию #016 о примени́мости анализа для процессоров сверхдлинного машинного слова).

● Автор потра́тил немало времени на разъяснение отличий понятий “алгоритм” и “программа” и доказательство эффективности исследования свойств именно АЛГОРИТМА.

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

Кстати, название авторского канала представляет собой англизированное словосочетание (с добавлением буквы “r”) из произведения Братьев Стругацких ПОНЕДЕЛЬНИК НАЧИНАЕТСЯ В СУББОТУ (1964, дополнительно см. здесь).

Автор не чура́ется использования повто́ров (в самых разнообразных вариантах), понимая истинность старинных латинских пословиц “Repetiljo est inaier studiorum” и “Festina lente”. В соответствие со сказанным первая публикация будет полностью посвящена роли и значению АЛГОРИТМА в современной жизни (при наличие ссылок в сторону конкретных тем данной серии публикаций).

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

• Понятие АЛГОРИТМА относится к числу фундаментальных математических понятий и является объектом исследования специального раздела математики – теории алгоритмов; в настоящее время это одно из основных понятий информатики. Соответственно АЛГОРИТМЫ необходимо исследовать и одним из наиболее интересных является анализ информационной структуры алгоритмов. Анализ информационной структуры алгоритмов предполагает изучение алгоритмов без их выполнения (или симуляции) на реальной вычислительной системе, при этом упор делается на исследование информационный связей в алгоритме (фактически его структуры). Наиболее часто используемый инструмент для таких исследований - представле́ние алгоритмов в форме гра́фов алгоритмов; используются также сети Петри (как один из вариантов графа).
• Анализ информационной структуры алгоритмов располагается на более охватывающем уровне в стеке методов исследований преобразования информации и даёт возможность (при использовании конкретизации) определять параметры вычислительной архитектуры, обеспечивающие наилучшее выполнение заданных алгоритмов. Данный метод исследования не тождественен способу программной симуляции аппаратуры вычислительных систем, но выступает обязательным и эффективным предшественником её использования.
• Архитектуры вычислительных систем меняются (и будут меняться!) значительно чаще, чем алгоритмы; поэтому необходимо уметь “подгонять” последние к первым (а для этого жизненно важно изучение алгоритмов).

Кстати, а какие (кроме нахожде́ния потенциала параллелизма) задачи решаются при анализе информационных графов алгоритмов? Ответ “навски́дку” (существенно неполный, конечно, но строго в интересах задач вычислительных практик):

● Поиск в графах ци́клов (нахожде́ние программных циклов – включая вло́женные) и их параметров; см. здесь и статью Н.А.Лиходеда тут etc.

● Противоположное - поиск “цу́гов” (последовательно исполняющихся потоков команд внутри единого процессорного ядра); см. тут - иде́и Волконского В.Ю (тут, правда, мы опять ска́тываемся к предмету параллелизации вычислений).

● Определение критического пути (CPM - Critical Path Method) в графе (параллельной вычислительной сложности алгоритма, оценка минимального времени выполнения алгоритма).

© В марте 2025 автором получено решение определения рационального (близкого к оптимальному) числа слотов отдельных команд в общем сверхдлинном слове процессоров VLIW-архитектуры (о таких процессорах см. публикацию #016). При этом очень важно, что результат получен исключительно на основе анализа алгоритмов (обработка которых является основным назначением любой вычислительной системы), языко́вые и схемотехнические же особенности функционирования процессора (являющиеся фактически вспомогательными средствами для достижения основной цели) при анализе не учитывались вообще.

Использование понятия АЛГОРИТМ (вследствие отстране́ния от представле́ния информации, несущественного для данного уровня абстракции) чрезвычайно удобно при “взгляде сверху” на действия вычислительной системы; исходный код программы (и, уж конечно, исполняемый код) таким свойством не обладают по причине чрезме́рной (по необходимости) детализации. Однако многие алгоритмы зачасту́ю плохо сопряга́ются с параметрами реальной вычислительной системы, на которой им суждено выполняться (вариант семантического разры́ва).

Поэтому стоит задача целенаправленных преобразований алгоритмов с целью “подго́нки” их под архитектуру конкретных вычислительных систем (включая использующие параллелизм при вычислениях). При таких преобразованиях алгоритмов критически важно не нарушить их внутреннюю информационную структуру (связи типа “операторы → операнды” – т.е. фактически причи́нно-сле́дственные). Именно поэтому упор в исследованиях делается именно на анализ информационной структуры алгоритмов; анализ алгоритмов в этом случае реализу́ет исследовательско-рекогносциро́вочные функции (“что и каким образом целесообразно модифицировать?”). Для подобных преобразований применяются различные (математические) методы.

До неда́вних пор существовало (формальное) препятствие – в школах не преподавалась теория гра́фов (а на этом базируются ключевые элементы анализа информационной структуры алгоритмов). После включе́ния в ФГОС ООО 2021 основных элементов теории графов в содержание предмета ИНФОРМАТИКА в 9 классе школьникам вполне досту́пно понима́ние проблем, рассматриваемых на данном канале (конкретизацию см. здесь, тут и вот здесь).

Последние новости канала:

1. Добавлены ссылки на статьи создателя канала https://dzen.ru/electromozg (см. публикацию #016). Т.к. блогер Электромозг часто пишет о проблемах процессоров архитектуры ЭЛЬБРУС (см. здесь и тут), in addition подбо́рка публикаций на эту тему.
2. Добавлена информация о докладе автора “Построение планов параллельного выполнения программ для процессоров со сверхдлинным машинным словом” (тезисы, презентация) на XX конференции разработчиков свободных программ 4÷6.10.2024 в Институте программных систем имени А.К.Айламазяна РАН, г. Переславль-Залесский · (доклады предыдущих лет - см. публикацию #020).
3. В исследовательском инструменте SPF@home (см. публикацию #013) начиная c версии 2025 г. в качестве встро́енного скрипто́вого языка для разработки методов целенаправленных эквивалентных преобразований графов алгоритмов будет применяться Lua 5.4.7 от 13.06.2024 (ранее использовалась версия Lua 5.3 от 06.01.2015).
4. Добавлена информация о докладе автора ”Использование метода анализа структуры и целенаправленных преобразований алгоритмов в задачах повышения эффективности параллельных вычислений” (тезисы, презентация) на XX юбилейной конференции “Свободное программное обеспечение в высшей школе” 7÷9.02.2025 в Институте программных систем имени А.К.Айламазяна РАН, г. Переславль-Залесский (доклады предыдущих лет - см. публикацию #020).
5. Вышла из печати статья автора в ПРОГРАММНОЙ ИНЖЕНЕРИИ: Формирование планов организации параллельных вычислений на процессорах со сверхдлинным машинным словом. // Журнал “Программная инженерия". — М.: 2025, том 16, #3, c. 115-121. DOI: 10.17587/prin.16.115-121. – EDN HWCPMI.
6. Добавлен пример использования ма́кросов псевдомассивов при применении ПРАКТИКУМА DF (программный имитатор граф-машины с заде́йствованием принципа вычислителя пото́ковой архитектуры и предика́тным управлением условностью выполнения) для реализации итерационных процессов на примере численного решения произвольного уравнения методом бисекции (она ж дихотомия) и операций линейной алгебры (действия с матрицами); см. публикацию #011.
7. В публикации #016 приведена схема реализации геометрической многозадачности (параллелизма) для процессоров со сверхдлинной машинной командой (VLIW-архитектура).

Предлагающиеся к рассмотрению вопросы формально существенно проще задач изучения конкретных языков программирования; фактически необходимо лишь осмысле́ние причинно-следственных взаимосвязей (отношений предше́ствования) в АЛГОРИТМАХ, однако находятся они на значительно более глубоких уровнях позна́ния сути Информационных Технологий.

● Нахожде́ние в алгоритмах внутреннего (обычно скры́того – т.е. неуловимого при поверхностном взгляде) параллелизма – лишь одна из сторо́н анализа алгоритмов (впрочем, пожалуй, наиболее практически ценная и, уж точно, максимально привлека́тельная для теоретического анализа.

● Автор убеждён, что роль анализа алгоритмов в будущем будет только увеличиваться (особенно при применении в ква́нтовых вычислительных системах).

Современные операционные системы (ОС) не поддерживают функции распараллеливания программ; это миссия инструментального программного обеспечения (трансляторов с языков высокого уровня). Фактически имеется всего две возможности разработки программ с распараллеливанием – использование (созданного “добрым дядей”) распараллеливающего компилятора/интерпретатора или “ручное программирование” (с использованием специализированных библиотек – которые в итоге используют вызовы всё той же операционной системы). У “простого” (среднестатистического) программиста чаще всего нет желания (да и необходимости!) заниматься распараллеливанием самостоятельно – он полага́ется на штатный компилятор для целевой вычислительной системы.

Заметим, что формальное освоение технологий поддержки параллелизма в языках высокого уровня (“как распараллеливать”) практически бесполезно без определения “что можно и нужно распараллеливать”.

• Напр., при использовании многоядерных процессоров первый вопрос, который должен задать себе Исследователь – какого размера (в простейшем случае – сколько операторов языка высокого уровня) целесообразно поместить в блоки, которые нужно распределить между отдельными вычислителями (процессорными ядрами или узлами вычислительного кла́стера)? Один простой оператор – это вряд ли выгодно - время обмена данными буквально “убъёт” суммарную производительность… Десяток операторов? Сотню? Тысячу? А может быть, некоторый зако́нченный логический блок?.. Возможно, полностью некий цикл (если имеем гнездо циклов – то какой-то из внутренних циклов). Как только размер блока (гра́нулы параллелизма) выбран, встаёт следующий вопрос – какие именно операторы поместить в каждый блок...
• Из самых общих соображений следует, что размер (в единицах времени) блоков (гра́нул) параллелизма должен быть как можно больши́м (между тем свойства алгоритмов обычно препятствуют этому), одновременно крайне желательно иметь размер блоков примерно одинаковым и обеспечить распределение их по процессорным ядрам максимально равномерным. При грубых отклонениях от этих рекомендаций время выполнения приложения (на одной и той же вычислительной системе) может отличаться на многие порядки! Не менее многозна́чная ситуация возникает при реализации параллельных вычислений на многомашинных (кла́стерных) системах. Как раз ответ на подобные (крайне противоречивые) требования даёт возможность получить АНАЛИЗ информационной структуры АЛГОРИТМОВ..!

Интересно, что примени́мость данного метода для анализа параллельных вычислительных систем архитектуры SIMD (Single Instruction stream / Multiple Data stream – арифметические ускорители фирм NVIDIA Corp. и AMD) ограничена – всё равно все ядра таких систем выполняют одинаковые
(ну ладно… почти одинаковые.. с учётом усло́вности выполнения – включая этот материал) вычисления…

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

1. Основное (“леж́ащее на поверхности”) преимущество Исследователь получает в виде возможности значительного увеличения производительности разрабатываемого приложения (не менее чем в разы́ - при наличии технических средств параллельной обработки на уровне отдельного процессора).
2. Решение специфических вопросов вычислений (нахожде́ние внутренних циклов в алгоритме, минимизация размеров вре́менных данных, балансировка нагрузки между вычислительными узлами и подобные) для последовательного или параллельного вариантов выполнения приложения.
3. Заключительная (намного более глубокая по сути) перспектива заключается в возможности использования архитектур вычислительных систем, отли́чных от изнача́льно запроектированных для приложения (в простейшем случае – на ином поле параллельных вычислителей).

Однако “халявы” тут ждать не приходится - решение поставленных задач требует применения определённых логических и математических методов и приёмов - собственно, о применении этих приёмов и идёт речь в данной серии публикаций (причём автор подробно рассказывает о нескольких наиболее эффективных – остальные Читатель легко найдёт самостоятельно благодаря множеству ссылок в тексте). Естественным итогом применения указанных методов являются полученные автором количественные данные.

В узком смысле серия публикаций является свободным переложе́нием цикла занятий со студентами НИУ ВШЭ и РТУ МИРЭА (дисциплина “Параллельные вычисления”; в последнем дополнительно проводились мастер-классы для школьников) по введению в методы исследования и преобразования алгоритмов с упором на параллелизм, проведённых автором в период 2018÷2023 г.г. Автор искренне надеется, что этими публикациями (начального уровня, конечно) будет дан импульс для дальнейшего совершенствования Читателей в области параллельных вычислений, имеющих определя́ющее значение для современных технологий – начиная от уровня “люби́тельского программирования” до профессиональных методов суперкомпьютерных и распределённых вычислений.

• Особенностью цикла публикаций является совместное использование авторского программного обеспечения, свободно устанавливаемого на персональный компьютер Читателя и позволяющего в привычных домашних условиях получать удовольствие от занятий исследовательской деятельностью (или хотя бы прикоснуться к ней). Прилагаемое программное обеспечение (не зря именуемое ПРА́КТИКУМ) позволяет исследовать произвольные алгоритмы на наличие внутреннего (скры́того) параллелизма и, после необходимых преобразований, решить чисто практическую задачу - построить рациональные планы их выполнения на заданном поле параллельных вычислителей (основной параметр вычислительной системы). Разработанное программное обеспечение является превосходным способом реализовать студенческий ПРА́КТИКУМ по заявленной теме. Книга автора (см. нижнюю часть страницы) служит существенным дополнением к публикациям и призвана расширить мировоззрение Читателей.

Автор ещё с последних курсов ВУЗ’а начал использовать принцип математического моделирования (с последующей компьютерной реализацией) для симуляции сложных технических процессов, результат показал свою продуктивность (во всех случаях такой подход помогал быстрее и глубже разобраться в проблеме). Сразу после обраще́ния к вопросам параллельных вычислений автор продолжил этот подход; в данный момент предлагается два авторских программах продукта (оба в формате инсталляционных файлов, GUI, Win’32; общее описание см. публикацию #011):

® исследовательский инструмент ПРА́КТИКУМ DF - вы́грузка здесь (подробнее см. публикацию #010)

® исследовательский инструмент ПРА́КТИКУМ SPF - вы́грузка тут (подробнее см. публикацию #013)

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

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

● Метод анализа алгоритмов путём получения определённых сече́ний графов (метод получения Ярусно-Параллельной Формы о́ных) также использовал в своих работах акад. Гермоге́н Поспелов (см. здесь, здесь и тут).

Каждая публикация этого цикла будет именоваться “NNN. Анализ информационной структуры алгоритмов. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ”, где NNN – номер публикации (её подраздел). Слово “информационный” подчёркивает тот факт, что приоритет отдаётся анализу информационных связей (связи типа “операторы → операнды”, т.е. фактически причинно-следственных) в алгоритмах. Не следует считать, что заниматься мы будем исключительно анализом структуры алгоритмов – в ходе выкладок придётся довольно часто обращаться и к схемам реальных вычислительных систем (невозможно компьютерную логику объяснить совершенно без обращений к технике) – но с упором именно на сказанное. Важно, что все процессы в жизни протекают во времени – параметры времени при анализе также всегда будут учитываться.

Начиная с публикации #013 название трансформируется в “NNN. Целенаправленные преобразования алгоритмов. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ”, что отражает факт начала изложения второй части серии публикаций, посвящённой описанию процессов целенаправленных модификаций алгоритмов (разумеется, при сохранении информационных связей в последних).

С конца XX века (при возраста́нием мощности вычислительных систем) появилась возможность программно-ориентированной симуляции (имитации) выполнения набора машинных команд (системы Simics, Ski, варианты сетей Петри etc).

● Однако алгоритмико-ориентированный подход к анализу алгоритмов продолжает оcтаваться не менее результативным. Причина в том, что алгоритмический подход базируется на более глубоких (относительно уровня языков программирования) принципах информатики и поэтому обладает бо́льшей гибкостью в применении. Наличествует WEB-сайт в Сети, полностью посвящённый алгоритмам - AlgoWiki (“ВикиПедия по алгоритмам”) и описание программной системы AlgoView. Ознакомьтесь с ними – найдёте немало интересного!..

Дисциплина ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ в большинстве Университетов РФ спланирована так, что первенство отдаётся программно-ориентированным симуляторам (что, по мнению автора, неправильно в принципе) – в этом случае мы “ставим телегу впереди лошади”… Такие симуляторы представляют огромное количество информации, имеющей ценность в очень специфических случаях (эффект, описанный “па́ном Стани́славом” в ‘Путешествие шестом, или как Трурль и Клапауций демона второго рода создали, дабы разбойника Мордона одолеть’). Один из важных недостатков (вытекающий, впрочем из достоинств) подобных систем – привя́занность к конкретной архитектуре вычислительной системы (и соответствующему набору машинных команд).

Алгоритмико-ориентированный подход даёт возможность (ценой конкретных упрощений) абстрагироваться (в определённой степени, конечно!) от особенностей архитектуры и получить требуемое решение за значительно более короткой срок. В последние годы интерес к алгоритмико-ориентированному подходу постепенно снижался (в немалой степени благодаря “эффекту Мордона” - эйфори́и от чувства мни́мого всемогущества в результате технических достижений), однако он (этот подход) более чем достоин для использования в качестве “первого при́ступа” при анализе. С методической точки зрения существенно понимание обучающимися ва́жности внутреннего наполне́ния сущности АЛГОРИТМ.

На самом деле проблема (как обычно) лежит в области затра́т времени и человеческих ресурсов. Программно-ориентированный подход требует значительно больше времени и труда. Даже моделирование с помощью сетей Петри (автор отно́сит этот метод к программно-ориентированным благодаря повышенной детализации решения - несмотря на явную принадлежность методики к графоаналити́ческим) потребует изменения структуры сети при желании определить хотя бы рациональную (близкую к оптимальной) архитектуру параллельной вычислительной системы (напр., количество и параметры узлов поля параллельных вычислителей); при этом определять внутренний потенциал параллелизма и строить план параллельного выполнения алгоритма всё равно придётся заранее. Описанный же в предлагаемой серии публикаций метод анализа информационной структуры алгоритмов позволяет достичь результата много быстрее (хотя при ме́ньшем уровне детализации; см. реальный пример анализа в публикации #016). Исходя из этого общие правила анализа такие - для поиска подробных стати́ческих (когда архитектура вычислительной системы окончательно определена́) решений целесообразно применять программно-ориентированные приёмы, для поиско́вых исследований - алгоритмико-ориентированный метод. Автор определённо тяготе́ет к исследовательскому направлению (и желает, чтобы “все такими были”) и поэтому убеждён, что первый этап исследований должен быть именно алгоритмико-ориентированным!..

• Важным недостатком программно-ориентированного подхода является поте́ря “взгляда сверху” на сущность понятия АЛГОРИТМ как ба́зовую основу информационных технологий; симуляторы кода хороши́ именно на окончательной стадии анализа – исследования и оптимизации именно машинного кода как этапа реализации алгоритма. В этом смысле не прошедшим стадию алгоритмизации следует уподо́бить “младенцам в джунглях”, бреду́щим по ча́ще дремучего леса с исключительно локальными целями при поте́ре целей глобальных. Критическим здесь является отсутствие иерархического подхода при реализации сложных проектов – на практике оказывается невозможным (или с маловероятным успехом) проектирование структурно-ма́лых объектов без предварительного решения вопросов общего назначения.

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

Кстати, на сайте AlgoWiki имеется специальный подраздел “Профиль обращения в память” и подразделы определения специальных оценок взаимодействия программ с памятью – gaps (gaps estimation) и cvg (cvg estimation).

• Существенным является то, что при алгоритмико-ориентированном подходе (далее АОП) упор исследований делается на анализ информационных (читай – причинно-следственных) связей в программе (собственно действия обычно даже не выполняются). · Можно сказать, что АОП делает упор на информационную составляющую алгоритма (“Структура важнее содержимого!”). Если Читателю не надоело моя апологе́тика “пана Стани́слава” (Стани́слава Лема), то он (автор) берёт на себя труд рекомендовать перечита́ть весьма содержательный роман ‘Непобедимый’ (там – помните? Подобными соображениями руководствовались пресловутые “му́шки” при соединении в “ту́чу”)… Кстати, аналогичный подход используется технологиями Нейронных Сетей.. тут же Умная Пыль!..
• Программно-ориентированный подход в отдельных случаях (напр., при необходимости параллелизации вычислений) в любом случае требует разработки плана (расписания) параллельного выполнения программы (что затруднительно предста́вить без этапа алгоритмизации). Даже в том случае, когда для создания исполняемого кода используется некий распараллеливающий транслятор – всё равно он создавался с применением алгоритмического подхода..!

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

Поэтому в этой серии публикаций мы будем максимально абстрагироваться от программно-аппаратных средств осуществления собственно вычислительного процесса (тем более что количество литературы по этой теме запредельно велико и каждый ищущий найдёт желаемое). Термин “максимально абстрагироваться” означает именно то, что означает (и ничего больше). Автор прекрасно понимает, что полностью абстрагироваться невозможно – наверняка придётся упомянуть и архитектуру вычислительных систем и особенности выполнения программ на них и многое-многое другое; однако...

• …Автор в своё время отдал немало сил этапу работы с программно-аппаратными средствами; имеет опыт в инсталляции, настройке и эксплуатации программно-аппаратной технологии MPI (Message Passing Interface) на Linux-кла́стерах - см. здесь, здесь, тут и здесь (а также об “эпохе великого кластерострое́ния” и одного из её результатов). Многопоточностью практически (исключая несколько экспериментов с графическими картами – см. тут) не занимался; но из этой области лично автору нравятся ресурсы, размещённые здесь и тут. Всё же технологический этап же является вторичным относительно общих подходов и приёмов рассмотрения проблемы на логическом уровне и не может быть эффективным без её обозначения и разрешения.

Надо понимать, что анализ алгоритмов (даже несмотря на несовершенство методов исследования в этой области) в большинстве случаев покажет бо́льший потенциал параллелизма, чем удастся реализовать в реальной вычислительной системе (архитектура её, сколь бы изощрёнными создатели не были бы, накладывает серьёзные ограничения на возможности). Т.о. показывается уровень, к которому стремиться надо!..

● Именно поэтому анализ алгоритмов столь привлекателен для Исследователей – всегда хочется сначала разглядеть перспективы (а уж следующий по́мысел - выяснить практические возможности каждой реализации – конкретной вычислительной архитектуры).

В сущности, автор пытается довести до Читателей схему, подобную нижеприведённой. Здесь показан переход от этапа алгоритмико-ориентированного анализа к программно-ориентированному. Этот переход связан с определённой деградацией в реализации параллелизма (показана стрелкой); жаль, автор не может “навски́дку” количественно определить о́ной величину.

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

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

Разработанное программное обеспечение является превосходным способом реализовать студенческий ПРА́КТИКУМ по заявленной теме и является составно́й частью предлагаемых “методи́чек” – см. здесь, тут и здесь).

• Программный модуль ПРА́КТИКУМ DF (см. публикацию #010) принимает в качестве входной информации последовательный вариант программы в императивном стиле на ассемблероподобном языке (фактически уровень ILP – Instruction Level Parallelism, слой машинных команд); последовательность команд в программе не определена, выполнение определяется критерием “гото́вности к выполнению” (вариант Data-Flow архитектуры), реализуется режим единокра́тного присваивания при реализации статической модели вычислительной системы. Условность выполнения отдельных выражений осуществляется предика́тным методом, отсутствие вершин-переключателей в информационном графе алгоритма компенсируется развёртыванием (loop-unrolling) циклов c использованием специальных ма́кросов (рекурсия моделируется также итерационными циклами). Модуль ПРА́КТИКУМ DF позволяет производить ограниченные эксперименты над конкретными алгоритмами (определять зависимость времени выполнения от размеров гомогенного вычислительного поля, исследовать влияние на быстродействие выполнения программ приоритета выборки команд из буфера). После отладки программы модуль ПРА́КТИКУМ DF даёт возможность экспортировать алгоритм программы в формат языка описания графов DOT (акро́ним "Dag Of Tomorrow").
• Программный модуль ПРА́КТИКУМ SPF (см. публикацию #013) на вход принимает файл алгоритма в формате DOT и под управлением встроенного скриптового языка Lua осуществляет целенаправленные эквивалентные (не изменяющие информационные связи в алгоритме) преобразования алгоритма (в основном служащие целям максимального соответствия алгоритмам архитектуре параллельных вычислительных систем – количеству вычислителей, гомогенной или гетерогенной структурам etc). Набор API-функций (которых обёртками являются Lua-вызовы) позволяет проводить преобразования алгоритмов любой сложности; для реализации некоторых приёмов (напр., обслуживание методов получения и модификации специальных сечений информационных графов) подготовлены высокоуровневые API-вызовы. Дальнейшее расширение списка API-сервисов является чисто механической процедурой и планируется к реализации в форме плаги́нов (dll-формат). Для программного пакета ПРА́КТИКУМ SPF размер гра́нулы параллелизма не имеет значения – в публикации #018 рассматривается пример обработки (построения рационального плана параллельного выполнения) в условиях макропараллелизма.

Т.к. использование встроенного скриптового языка позволяет реализовывать стратегии (“эвристики”) модификации алгоритмов практически неограниченной сложности, широта постановочных задач также малоограничена (подробнее см. публикацию #020). Напр., классической приоритетной задачей часто является достижение максимальной скорости выполнения программ, построенных на основе конкретных анализируемых алгоритмов; в более широком смысле – соответствие алгоритма конкретным параметрам заданной вычислительной архитектуры. Обычно начальному исследованию подлежит потенциал параллелизма (в условиях неограниченного параллелизма), зависимость параллельной вычислительной сложности алгоритма (фактически времени выполнения) от размера вычислительного поля etc. Обычно минимум этой величины соответствует максимальной плотности кода (минимуму временны́х и простра́нственных лаку́н при выполнении всех гранул параллелизма).

С использованием этих программных систем выполнены численные исследования информационной структуры алгоритмов; анализу подвергались алгоритмы (программы) из библиотеки, представленной в публикации #010. Напр., в публикации #012 приведены результаты анализа с помощью исследовательского инструмента ПРА́КТИКУМ DF, в публикации #015 и публикации #016 – с использованием инструмента ПРА́КТИКУМ SPF (дополнительно см. публикации #017, #018 и #019).

На каком уровне процесса количественного моделирования удобнее выявля́ть потенциал параллелизма при вычислениях ?

Возникает естественный вопрос – а на каком уровне процесса количественного моделирования явлений природы удобнее всего выявлять потенциал параллелизма при вычислениях? Логичен ответ – на наиболее верхнем из имеющихся, но допуска́ющем полноце́нно количественный анализ (посре́дством операций над графами).

В упрощённом виде стек процесса количественного моделирования явлений природы показан на миниатюре снизу; по мере возрастания конкретизации (ужесточение ограничений реализации происходит снизу вверх; представле́ние в виде пирамиды наве́яно, конечно, идеей “пирамиды Маслоу́”) возможности (потенциал) параллелизации предсказу́емо снижается. Для нас важно, что главе́нствующим в цепочке преобразований информации является понятие АЛГОРИТМА как некоторого шаблона (“па́ттерна”) осмы́сленных (целенаправленных) действий. Собственно АЛГОРИТМ является промежуточной стадией в процессе моделирования между математической моделью и созданием исходного кода программы (и первой стадией, допуска́ющей количественный анализ!) и поэтому находится в логическом стеке этапов количественного моделирования глубже этапа разработки исходного кода (“программирования” в узком смысле этого слова); соответственно выявле́ние потенциала параллелизма на этом уровне должно́ показать максимальные значения.

Логический стек этапов процесса количественного моделирования явлений природы

О зна́чимости сущности АЛГОРИТМ

На рис. 1 показаны гра́ни сущности АЛГОРИТМ. Наряду с традиционными она включает как довольно давно исследуемые (“Вычислительная трудоёмкость”), так и (относительно) недавно ставшие необходимостью (напр., “Внутренний параллелизм”). Часто упоминают при этом о “скрытом” (нефиксируемом про поверхностном взгляде) параллелизме (в самом деле – для нахождения этого параллелизма приходится применять специальные математические приёмы).

Рисунок 1. Гра́ни сущности АЛГОРИТМ

Любой понимает, что процесс преобразования данных является результатом взаимодействия АЛГОРИТМА (и его конкретизации - ПРОГРАММЫ) с ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМОЙ (неважно, на каком принципе та основана – от механики до квантовых принципов).

С другой стороны ВНУТРЕННИЙ ПАРАЛЛЕЛИЗМ изначально является свойством сущности АЛГОРИТМ и существует независимо от возможностей его выявления с помощью исполняющей вычислительной системы. Значит – его можно исследовать независимо от наличия исполняющей системы (т.е. без выполнения машинного кода).

Единицы измерения степени параллелизма

А любое исследование начинается с определения единиц измерения (чтобы иметь возможность сравнивать различные варианты и выбирать лучшее). Напр., при использовании информационных графов удобными и зна́чащими единицами измерения уровня параллелизма являются высота и ширина его Ярусно-Параллельной Формы (понятие ЯПФ графа и метод её получения вводятся в публикации #009) и более сложные параметры, учитывающие, напр., статистику распределения шири́н ЯПФ по ярусам.

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

Удивительно, что практически в течение жизни одного поколения сменилось два этапа (уровня, друг друга диалектически дополняющих) исследования свойств сущности “алгоритм”  – определение вычислительной сложности и внутреннего параллелизма обсуждаемого объекта. Оба этапа были вызваны желанием наиболее эффективного использования алгоритмов в вычислительных практиках. Имеются ли более глубокие свойства алгоритмов, которые можно использовать в дальнейшем (естественно, для достижения той же цели)? Найдётся ли ещё одна гра́нь у фигуры на рис. 1? Автор данной публикации искренне надеется (локально в отношении алгоритма) на истинность известного Ле́мовского посы́ла  “Я твёрдо верю в то, что не прошло ещё время ужасных чудес”! Желаем мы или нет, но с течением времени методы описания окружающего Мира (а познание его  является, пожалуй, единственной не скомпрометированной пока целью существования человека) непрерывно  усложняются…

Связь между исследовательскими и общегосударственными задачами

Президент России В.В.Путин 18.01.2024 года (и повторно 01.04.2024) поручил правительству нарасти́ть мощности суперкомпьютеров в России. "К 2030 году совокупная мощность отечественных суперкомпьютеров должна быть увеличена не менее чем в десять раз. Это реалистичная задача", – сообщил глава государства. // Из послания Президента Федеральному собранию РФ 29.02.2024.

Не мне полемизировать с Президентом моей страны, но СУПЕРКОМПЬЮТЕРЫ – всего лишь экзотическая “железка”, с которой подавляющему большинству Читателей зна́ться скорее всего не придётся (хотя автору и его аспиранту привело́сь во благовре́мении). Важно другое (впрочем, тесно корреспонди́рующееся с первым) – суперкомпьютерные технологии немы́слимы без анализа алгоритмов (в данном случае имеется в виду одна из ипоста́сей этого анализа – нахожде́ние в алгоритмах потенциала параллелизма и, в дальнейшем, его рациональное использование в вычислительных практиках)..! А это – “заветная цель” многих программистов, желающих максимально использовать вычислительный потенциал процессора (точнее, его я́дер) своего компьютера…

• В рамках обеспечения импортонезависимости России разрабатываются микропроцессоры ЭЛЬБРУС c архитектурой сверхдлинного машинного слова (VLIW - Very Long Instruction Word), области применения которых - государственные и оборонные структуры, высокопроизводительные вычислительные системы (суперкомпьютеры).

Чем отличаются понятия АЛГОРИТМ и ПРОГРАММА

Итак, мы широко используем слово (термин) алгоритм. Начнём с интересного вопроса – чем чем отличается понятие алгоритм от программы (компьютерной программы)? Для нашего обсуждения это будет важно.

• Алгоритм. Наиболее часто встречающиеся определение алгоритма “формализованное описание порядка элементарных действий по выполнению некоего действия большего масштаба”. Здесь важен (не так давно появившийся термин “порядок” вместо “последовательность”), что является следствием того, что алгоритм может выполняться необязательно последовательно (а в некоторых случаях параллельно).

Ключевое слово здесь – “формализованный”. Одна из граней этого определения – "очищенный от всего лишнего, второстепенного" (правда, от чего именно - не уточняется; в каждом конкретном случае "лишним" может оказаться совсем разное).

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

Методов представле́ния алгоритмов множество – псевдокод (русско – или англоязычное текстовое описание совершаемых действий), структурные диаграммы (это такие прямоугольнички-треугольнички со стрелками) и графы и даже (иногда) лямбда-представле́ния

Считая алгоритм “формализованным описанием порядка действий”, анализ алгоритмов вполне естественно (особенно вспоминая Гарвардскую архитектуру вычислительных систем, где постулируется разделение методов обработки программного кода и данных) отнести́ к области Data Science (со специфическими, конечно, инструментами анализа и обработки); дополнительно может быть поставлена и выполнена задача целенаправленной модификации кода.

Кстати, очень часто при преобразовании программы в алгоритм незна́чимые параметры программы опуска́ют. Обычно это временны́е параметры (длительность выполнения операторов и время передачи данных между ними); эти параметры принимаются нулевыми или одинаковыми. Обычно опускаются и несущественные (с точки зрения именно алгоритма) действия по взаимосвязи программы с памятью (естественно, если речь не идёт прямо об исследованиях операций взаимодействия с последней). Неучёт временны́х параметров - в основном не времени выполнения отдельных машинных команд, а времени до́ступа к памяти по чтению/записи (особенно малопредсказу́емость этой величины вследствие широко применяемой технологии расслое́ния памяти) – основной недостаток алгоритмико-ориентированного подхода (в исследовательском инструменте ПРА́КТИКУМ SPF предприняты некоторые действия в сторону сглаживания этого несовершенства – вершины и дуги графа снабжены ме́рами, толку́емыми, напр., как параметры времени выполнения операций).

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

Особый вопрос – а как из ПРОГРАММЫ получить (ей соответствующий) АЛГОРИТМ ? Вообще говоря, после па́рсинга программы транслятором сделать это несложно (к тому же нет смысла подобное производить для всей программы – иногда логично выполнять это отдельно для каждой библиотечной процедуры). Здесь ключево́е (лука́вое!) понятие “вообще говоря” – на самом деле в реальных случаях придётся серьёзно поразмыслить.

● Анализ исходного кода затруднён приближе́нием его к человеческому разуме́нию (преслову́тым “синтаксическим сахаром”), исполняемый код сверх меры загру́жен особенностями аппаратной реализации. Но уж таков уде́л программистов - смогли же специалисты NVIDIA создать CUDA Graphs...

● У автора есть надежда на использование практик функционального программирования… однако что-то говорит ему, что панацеи ожидать не приходится..!

Предупреждение. Автор иногда имеет склонность (особенно в пылу дискуссии) сваливаться в ересь, заключающуюся в идентификации понятий алгоритма и программы, хотя обычно он предпочитает использовать лукавый приём “программа, соответствующая данному алгоритму” (и наоборот). Отслеживайте это и предупреждайте его (автора)..!

Идеального (удовлетворяющих всех) понятия сущности АЛГОРИТМ до сих не существует. А какое определения для этой сущности предложили бы Вы?..

Что-то забыли? А где ИСХОДНЫЙ КОД (Source Code) ПРОГРАММЫ (он же ИСХОДНЫЙ ТЕКСТ) ?

А он – посредине между АЛГОРИТМОМ и ПРОГРАММОЙ..! Для чего служит – не мне объяснять, но к какой сущности (из ранее названных) он ближе? Автор склонен считать, что к ПРОГРАММЕ, ибо вынужден включать в себя множество формальных (необходимых для конкретизации АЛГОРИТМА) и неформальных (напр., “синтаксический сахар”) компонент.

Автору (субъективно, конечно!) кажется, что пространство между АЛГОРИТМОМ и ИСХОДНЫМ КОДОМ больше разры́ва между ИСХОДНЫМ КОДОМ и ПРОГРАММОЙ (сказанное подтверждает приоритет АЛГОРИТМА). Хотя имеется такая штука, как ПСЕВДОКОД, используемый при описании АЛГОРИТМОВ… однако от приста́вки ПСЕВДО никуда не деться!

• Автор склонен принижа́ть значение исходного кода – слишком много языков программирования высокого уровня (ЯПВУ) было разработано и слишком мало по-настоящему нового сделано!.. Повторное использование кода, усиленная поддержка многозадачности, минимизация проблем с динамическим распределением памяти etc (специалисты без труда сопоста́вят вы́сказанные новшества с конкретными ЯПВУ) - всё на́званное полезно, однако это лишь ча́стности… “сахаро́чек”, в общем-то… “Его Величество АЛГОРИТМ” остаётся непревзойдённой основой Информационных Технологий!

Частичный антагонизм ПРОГРАММЫ и АЛГОРИТМА

“Милые браня́тся - только те́шатся”… подобное можно сказать и о взаимоотношениях АЛГОРИТМА и ПРОГРАММЫ. При создании исходного кода программ на языке высокого (или не очень) уровня, разработчик фактически отдаля́ется от сущности АЛГОРИТМ - последний заменяется множеством необязательных для последнего конкре́тик. Каким же образом транслятор (компилятор или интерпретатор) может восстановить АЛГОРИТМ (например, в форме информационного графа алгоритма)? Арифметико-логические действия и информационные зависимости, конечно, присутствуют в коде. Программисту – создателю транслятора придётся освободиться от множества ненужных алгоритму частностей (напр., обраще́ний в память различного уровня etc), провести целенаправленные изменения графа алгоритма, а затем выполнить обратную процедуру (преобразование “информационный граф → исполняемый код”), но уже для архитектуры целевой вычислительной системы (напр., с заданным числом параллельных вычислителей).

Практическое применение метода анализа и целенаправленного преобразования алгоритмов при создании распараллеливающих компиляторов

После целенаправленного изменения ЯПФ распараллеливающий пост-процессор рекомпилирует программу, использую модифицированную ЯПФ в качестве каркаса (skeleton) вновь создаваемого параллельного приложения (укрупнённая схема внизу, отсы́л к пояснению вновь вводи́мых терминов чуть ниже). Анализ причинно-следственных связей (т.е. построе́ние информационного графа алгоритма) может быть проведён и на уровне исполняемого кода (после дизассемблирования).

Особенно эффективно применение метода целенаправленного изменения ЯПФ при разработке компиляторов для процессоров со сверхдлинным машинным словом (VLIW-архитектуры) - вследствие логи́чности сопоставле́ния каждого яруса ЯПФ собственно сверхдлинному слову (т.к. все отдельные машинные команды этого слова стартуются на исполнение одновременно - синхро́нно).

Во время реализации могут встретиться трудности при получении информационного графа алгоритма (сущность, включающая только операторы изменения данных и информационные связи между ними) – непременный лексический и синтаксический анализ исходного кода дают возможность это сделать. Этап генерации ЯПФ (Ярусно-Параллельной Формы, см. публикацию #009) по ИГА (Информационному Графу Алгоритма, см. ту же публикацию) не должен представлять чрезмерных затруднений. На последнем этапе встря́нет огромное количество фактически малозна́чимых для стратегии, но критически важных для программной реализации особенностей (для SMP-систем - конфликтов при работе с памятью в связках атома́рных инструкций Load/Store, известные проблемы использования указателей etc). Подобный уровень ремесла предполагает наличие достаточно высокой квалификации разработчика.

Интересный вопрос – а зачем вообще нужен Source Code? Разве нельзя по АЛГОРИТМУ создать ПРОГРАММУ?.. Вроде бы в АЛГОРИТМЕ имеется вся информация для этого… Это предмет обсуждения для Читателей..!

Удивительное прозре́ние важности АЛГОРИТМА “паном Стани́славом”

Автор, являясь вечным почита́телем “пана Стани́слава” (Станислава Германа Лема), не может удержаться от изображения и соответствующей цитаты (сла́вящих “Его величество АЛГОРИТМ” устами “великих механикусов Трурля и Клапауция”; материалы студии Render.ru):

Суть сказанного проста – мы будем (в подавляющем большинстве) иметь дело с алгоритмами! Это естественно для человека – всегда полезно отсекать незначимое (а это и есть “формализировать” сложные понятия перед их разбором). “Понять – значит упростить!” – сказали (словами легендарного писателя Дмитрия Строгова) когда-то Братья Стругацкие. Позднее выяснилось, что эти слова (непредумышленно) взяты из повести Михаила Анчарова (и произнесены в ходе дискуссии по поводу высказывания Шекспира “Понять - значит простить”). Так вот и упрощаем..!

Кстати, чуть ли не идеальным математическим аппаратом для анализа алгоритмов являются графы. Графы (напра́вленные) прекрасно описывают сложные причинно-следственные отношения между объектами (“одно событие не может произойти раньше конкретного другого”) и просто констатируют незыблемость одностороннего хода времени. Гра́фов студенты (зачастую) побаиваются (как я в своё время), но “просто привыкнуть” надо..!

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

Ничто не препятствует Читателю обратиться и к более изощрённым методам построения планов параллельного выполнения программ - напр. :

① защита диссертации А.Н.Черных (словами соискателя “работа носит теоретический характер”),

② хорошее (с подробным описанием методов планирования) учебно-методическое руководство предлагает А.А.Прихожий (Минск, БНТУ),

③ в книгах И.Е.Федотова (дополнительно здесь) имеется вполне вне́млемое перечисление приёмов выявления в алгоритмах скрытого потенциала параллелизма.

Т.о. выявляется триеди́ная напра́вленность данной работы:

1. Слушатели глубже понимают роль АЛГОРИТМА при разработке реальных программ и знакомятся со стандартными алгоритмами обработки данных.
2. Осознаю́т ПОТЕНЦИАЛ ВНУТРЕННЕГО ПАРАЛЛЕЛИЗМА как неотъемлемую часть (грань) сущности АЛГОРИТМ (природу понятия, его основные параметры, единицы измерения, специфику применения).
3. Естественным образом воспринимают принципиальную возможность целенаправленных эквивалентных преобразований алгоритмов с целью наилучшего использования их в вычислительных практиках (в смысле приспособленности к конкретным вычислительным системам) и разрабатывают эффективные процедуры ("эвристики") таких преобразований (творческий компонент работы).

Информация о канале вообще и его оглавление…

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

В.М.Баканов. Практический анализ алгоритмов и эффективность параллельных вычислений. ISBN 978-5-98604-911-3. 2023. LitRes.ru

#наука #исследования #научная_работа #образование #преподавание #теория #эксперимент #НИУ_ВШЭ #РТУ_МИРЭА #анализ_алгоритмов #информационные_технологии #программное_обеспечение #open_source #параллельные_вычисления #информационный_граф_алгоритма #ярусно_параллельная_форма #выявление_параллелизма #эквивалентные_преобразования_графа_алгоритма #целенаправленные_преобразования_графа_алгоритма jl