Практический анализ алгоритмов и эффективность параллельных вычислений
Покупка
Новинка
Тематика:
Программирование и алгоритмизация
Издательство:
Пробел-2000
Автор:
Баканов Валерий Михайлович
Год издания: 2023
Кол-во страниц: 198
Дополнительно
Вид издания:
Научно-популярная литература
Уровень образования:
Профессиональное образование
ISBN: 978-5-98604-911-3
Артикул: 889086.01.99
В книге представлены результаты работ по применению традиционных и современных методов организации параллельных вычислений на логическом уровне, основанных на анализе информационной структуры алгоритмов и выполненных в ходе процесса преподавания в высших учебных заведениях России. Особенностью работы является применение авторского программного обеспечения, свободно устанавливаемого на персональный компьютер пользователя и позволяющего исследовать произвольные алгоритмы на наличие внутреннего параллелизма. После формального выявления параллелизма решается задача определения рациональных (эффективных по заданным критериям) параметров выполнения исследуемых алгоритмов на заданном поле параллельных вычислителей.
Книга предназначена для студентов, аспирантов и любителей естествознания из произвольных общественных групп - от школьников выпускных классов до любых субъектов, обладающих свойством быть «исследователями в глубине души́ своей».
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Памяти Геннадия Зеленко – создателя первого в СССР воистину персонального компьютера РК, МИКРОША) (Радио-86 В.М.Баканов ПРАКТИЧЕСКИЙ АНАЛИЗ АЛГОРИТМОВ И ЭФФЕКТИВНОСТЬ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Москва «Пробел-2000» 2023
УДК 681.3 ББК 22.18 Б19 Баканов, Валерий Михайлович Б19 Практический анализ алгоритмов и эффективность параллельных вычислений. – Москва : Пробел-2000, 2023. – 196 с. : ил. ISBN 978-5-98604-911-3 В книге представлены результаты работ по применению традиционных и современных методов организации параллельных вычислений на логическом уровне, основанных на анализе информационной структуры алгоритмов и выполненных в ходе процесса преподавания в высших учебных заведениях России. Особенностью работы является применение авторского программного обеспечения, свободно устанавливаемого на персональный компьютер пользователя и позволяющего исследовать произвольные алгоритмы на наличие внутреннего параллелизма. После формального выявления параллелизма решается задача определения рациональных (эффективных по заданным критериям) параметров выполнения исследуемых алгоритмов на заданном поле параллельных вычислителей. Книга предназначена для студентов, аспирантов и любителей естествознания из произвольных общественных групп – от школьников выпускных классов до любых субъектов, обладающих свойством быть «ис следователями в глубине души́ своей». УДК 681.3 ББК 22.18 ISBN 978-5-98604-911-3 © Баканов В.М., 2023 © «Пробел-2000», 2023
СОДЕРЖАНИЕ ОБРАЩЕНИЕ К ЧИТАТЕЛЯМ ............................................ 6 1. ЧТО ТАКОЕ ПАРАЛЛЕЛИЗМ ПРИ ВЫЧИСЛЕНИЯХ И КАКИМ ЦЕЛЯМ ОН СЛУЖИТ ..................................... 12 2. ТРУДНОСТИ ПЕРЕХОДА ОТ ПОСЛЕДОВАТЕЛЬНОГО ОПИСАНИЯ АЛГОРИТМА К ПАРАЛЛЕЛЬНОМУ ЕГО ВЫПОЛНЕНИЮ ............ 20 3. ВОПРОСЫ АРХИТЕКТУРЫ ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ................................ 36 4. ПРОГРАММНАЯ СИСТЕМА D-F (Data-Flow) ДЛЯ ОПРЕДЕЛЕНИЯ ПАРАМЕТРОВ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ АЛГОРИТМОВ ................................... 47 5. ИССЛЕДОВАНИЯ ПРОЦЕССА ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ АЛГОРИТМОВ С ИСПОЛЬЗОВАНИЕМ ПРОГРАММНОГО ИНСТРУМЕНТА D-F ...................................................... 71 5.1. Исследование свойств алгоритмов с помощью инструмента D-F ............................................................... 75 5.1.1. Принцип неограниченного параллелизма и определение минимально необходимого для заданного алгоритма числа параллельных вычислителей ............. 75 5.1.2. Получение и анализ планов (расписаний) параллельного выполнения алгоритмов ....................... 79 5.1.3.Управление динамикой процесса вычислений в потоковом вычислителе ................................................... 85 5.1.4. Определение параметров алгоритмов в условиях неограниченного параллелизма ...................................... 92 5.1.5. Определение времени выполнения алгоритмов в зависимости от числа параллельных вычислителей ..... 94 5.2. Выводы по главе и продолжение исследований ......... 98
6. ОПРЕДЕЛЕНИЕ РАЦИОНАЛЬНЫХ МЕТОДОВ ПОСТРОЕНИЯ ПЛАНОВ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ АЛГОРИТМОВ С ИСПОЛЬЗОВАНИЕМ ПРОГРАММНОГО ИНСТРУМЕНТА SPF .................................................... 100 6.1. Система SPF@home и её место в общем исследовательском инструментарии ........................... 100 6.2. Принципы функционирования системы SPF ............ 103 6.2.1. Ручной режим работы системы SPF........................ 113 6.2.2. Программные средства представления и преобразования информации в системе SPF ............... 117 6.3. Общее и разное в подходах построения планов параллельного выполнения с использованием модели D-F потокового вычислителя и инструмента SPF...... 139 6.4. Характер кривой интенсивности вычислений .......... 142 6.5. Исследование пространственной и временно́й сложности алгоритмов ................................................... 145 6.6. Получение рациональных планов параллельного выполнения алгоритмов с помощью целенаправленного изменения ярусно-параллельной формы графа алгоритма .......................................................................................... 147 6.6.1. Получение планов параллельного выполнения алгоритмов для исполнения их на минимальном числе вычислителей за кратчайшее время ............................. 148 6.6.2. Получение планов выполнения алгоритмов для выполнения на заданном числе параллельных вычислителей при возможности увеличения времени исполнения ...................................................................... 150 6.6.3. Получение планов выполнения алгоритмов с максимальной плотностью кода ................................... 154 6.6.4. Построение расписания выполнения параллельных программ на заданном поле гетерогенных вычислителей .......................................................................................... 164 6.7. Выводы по главе и продолжение исследований ....... 170
7. ВРЕМЯ СУЩЕСТВОВАНИЯ ПРОМЕЖУТОЧНЫХ ДАННЫХ И ИХ РАЗМЕР ............................................. 172 8. ПОСТРОЕНИЕ ПЛАНОВ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ПРОГРАММ ПРИ ЗНАЧИТЕЛЬНОМ РАЗМЕРЕ ГРАНУЛ ПАРАЛЛЕЛИЗМА .................... 178 9. ВОЗМОЖНЫЕ ЦЕЛИ ОПТИМИЗАЦИИ ПЛАНОВ ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ ПРОГРАММ .. 185 10. ВЫВОДЫ ПО ИССЛЕДОВАНИЯМ И ДАЛЬНЕЙШИЕ ДЕЙСТВИЯ..................................................................... 188 ЗАКЛЮЧИТЕЛЬНОЕ СЛОВО К ЧИТАТЕЛЯМ ............ 191 ЛИТЕРАТУРА ..................................................................... 193
ОБРАЩЕНИЕ К ЧИТАТЕЛЯМ
Лучший способ в чём-то разобраться до
конца – это попробовать научить этому
компьютер.
Дональд Кнут
Вокруг использования параллелизма в вычислениях
много лет формировалась а́ура как чего-то запредельно
сложного и требующего воистину академического уровня
инструментов для исследований. О параллелизме писалось
много и подробно… но десятилетия назад! Это был период
усиленного технического развития страны (время “бури и
натиска” в технологиях, в т.ч. вычислительных). Далее
начался естественный процесс - идеи “ушли вниз – в народ”;
были разработаны огромные универсальные библиотеки для
использования в прикладном программировании, позволяющие “получить результат нажатием кнопки”. Уровень эффективности 1 применения аппаратной и программной
компонент, реализованный посредством этих библиотек,
сплошь и рядом известен не полностью (следствие разобщённости фирм-разработчиков, зачасту́ю даже об использованном алгоритме упоминается глухо). Если такое состояние дел можно считать удовлетворительным при создании
массового прикладного программного обеспечения для
процессоров традиционных архитектур, то по мере введения в использование новых вычислительных архитектур (а
они практически всегда рассчитаны на использование параллелизма) задачи эффективности вычислений приходится
решать на новом уровне. В конце концов, кому-то всё равно
1 Согласно формальному определению эффективность (она ж результативность) определяется отношением результата (эффекта) и затрат
на его реализацию.
придётся для этих систем разрабатывать распараллеливающие интерпретаторы/компиляторы (известные алгоритмыто an mass последовательные)! Надо помнить, что собственно анализ внутренней структуры алгоритмов с целью выявления параллелизма – вещь приятная и общеполезная, но самое важное – уметь этот (выявленный) параллелизм использовать в вычислительных практиках. Сказанное особенно важно в период, когда Россия в рамках импортонезависимости разрабатывает собственные, напряму́ю ориентированные на параллельную обработку данных, процессоры серии ЭЛЬБРУС. Если ранее обсуждаемые вопросы (напр., анализ алгоритмов) являлись неким табу́ для “простых пользователей”, то с появлением персональной вычислительной техники практически в каждом доме открывается возможность вовлечения достаточно широких кругов пользователей в область этих проблем (что, как надеется, автор, будет способствовать расширению числа Исследователей и углу́блению самих исследований). Любой читатель (после ознакомления с материалами книги) имеет возможность “скача́ть из cети InterNet”, инсталлировать на своей “персоналке” и, прочитав не слишком сложное руководство по эксплуатации, провести серию доступных вычислительных экспериментов. Именно в этой возможности заключается сокровенная надежда автора на ненасильственный рекрутинг новых исследователей в данную область человеческих знаний. В конце концов, “игра с Природой” (а так вполне можно рассматривать практически любую Исследовательскую работу по познанию человеком окружающего Мира) много сложнее, глубже и изощрённее, нежели противостояние неуёмно-суетливым персонажам, созданным мыслительными способностями команды разработчиков компьютерных игр! К тому же не будем забывать, что единственный способ объективно оценить свой собственный уровень в
любом начина́нии – сравнить его с уровнем противника… а что может быть выше Законов Природы? Алгоритм является результатом разумной деятельности человечества и отражает в себе (в опосре́дованном виде, конечно) наиболее глуби́нные, фундаментальные законы развития Природы. Одно это является основанием необходимости исследования характеристик алгоритмов. Автору импонирует метафора ассоциации алгоритма с дровами (топливом) для печи, а исполнительной вычислительной системы – с собственно печью, которая дрова превращает “в нечто полезное” для людей (тепло). Целевым утверждением здесь служит понятие о совместимости (или “не-”) первого со вторым, без этого эффективность обогрева будет небольшой даже при отличных ви́димых качествах обоих компонент процесса по отдельности. Наиболее де́йственным путём достижения цели (получение максимума тепла) является, конечно, разработка эффективных способов сжига́ния дров в печи (использование параллелизма при вычислениях является аналогом этого). Развитие области знаний “вычислительная математика” помогает реализации указанной цели. В глубокой молодости автора поразила сентенция (коей безыскусность он понял много позднее) об отсутствии потребностей развития дифференциального и интегрального исчислений в случае изобретения вычислительной техники ранее наступления эпохи (великого) Ньютона… Удивительно (нечасто так бывает в человеческой деятельности), что сама возможность реализации суперкомпьютеров (огромных цифровых систем обработки информации с миллионами совместно действующих отдельных вычислителей) стала возможной лишь при разработке методов анализа (в направлении наличия внутреннего параллелизма и его рационального использования) структуры алгоритмов! Особенностями параллельных вычислений является
то, что по одному и тому же алгоритму они могут быть проведены огромным количеством вариантов, поэтому вопрос эффективности (в части скорости решения задачи, использования ресурсов вычислительной системы и др.) обработки данных стоит на первом месте. При повествовании автор стремится возможно шире использовать возможность совместного с Читателем экспериментального исследования обсуждаемых вопросов с помощью авторского полностью свободно доступного программного обеспечения, являющегося фактически частью данной публикации (не зря слово “практический” вынесено в название книги). Автору всегда хотелось максимально подробно показать Читателю, каким именно образом “получаются” конкретные результаты, представленные в исследовательских работах. Этому соответствует подробное техническое описание проводи́мых вычислительных экспериментов; освоивший методику исследований самостоятельно поставит новые задачи (а базовая техника исследований будет к тому моменту уже известна и её можно практически применять и даже усовершенствовать). И пусть размер рассматриваемых в книге обрабатываемых данных невелик (несравни́м с обрабатываемыми суперкомпьютерами), методика обработки остаётся той же самой. Конечно, “вхожде́ние в предмет” (любой) всегда сопряжено с некоторой болезненностью. В первую очередь придётся вспомнить о (ключевом) понятии алгоритма (да и восстановить в памяти несколько образцов этой удивительной сущности, возникшей вследствие выбора цели и разработки планов её реализации), основных принципах функционирования вычислителей, несложных вопросах математики, основах использования гра́фов (именно последнее почти всегда вызывает наибольшие проблемы, хотя собственно идея выражения сложных причинно-следственных отношений между объектами в форме графов априори
зало́жена - автор уверен в этом - в сознании каждого человека).
Читатель должен также понимать, что данная книга
посвящена логическому уровню решения задачи о разработке эффективных параллельных программ, при этом вопросы конкретных технологий аппаратно-программных реализаций рассматриваются только в случае необходимости.
Литературы по технологиям реализаций параллельных вычислений (в т.ч. языко́вых осуществлений) предостаточно.
Однако технологический этап всё же является вторичным
относительно определения общих подхо́дов и приёмов рассмотрения конкретной проблемы на логическом уровне и не
может быть эффективным без её обозначения и разрешения 2.
При желании максимально расширить и углу́бить знания читателю следует использовать дополнительные материалы (литературные источники, ресурсы сети InterNet).
Каждый график в книге сопровождается данными, достаточными для повторения исследований; Читатель (автор
иногда будет называть его Исследователем) может повторить опыты с иными алгоритмами из предоставленной библиотеки для подтверждения (уточнения, расширения) данных. Результаты зависимости интересующей Исследователя величины (о́тклика) от исследуемого параметра (в
определённом диапазоне, конечно) даются в наиболее показательной и компактной графической форме представле́ния данных. Характер полученных плоских кривых
даёт возможность анализировать процессы, скрывающиеся
за приведёнными количественными показателями.
2 “Стратегия без тактики – это самый медленный путь к победе. Тактика без стратегии – это просто суета перед поражением”. Сунь-цзы
– славнейший китайский страте́г и мыслитель, автор знаменитого
трактата о военной стратегии “Искусство войны”, VI век до н.э.