Вычислительная математика и структура алгоритмов

Вычислительная математика и структура алгоритмов

2-е издание, исправленное

Воеводин В.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Вычислительная математика и структура алгоритмов/ В.В. Воеводин - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2008-2016
(c) Воеводин В.В., 2008-2016

3

Введение

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

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

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

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

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

Заметим, что как самостоятельный раздел структура алгоритмов развивается уже около

4

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

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

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

В.В.Воеводин

5

Большие задачи и большие компьютеры

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

Если создают большие вычислительные системы, значит они для чего-то нужны. Это
что-то - большие задачи, которые постоянно возникают в самых различных сферах
деятельности. Практическая потребность или просто любознательность всегда ставили
перед человеком трудные вопросы, на которые нужно было получать ответы. Строится
высотное здание в опасной зоне. Выдержит ли оно сильные ветровые нагрузки и
колебания почвы? Проектируется новый тип самолета. Как он будет вести себя при
различных режимах полета? Уже сейчас зафиксировано потепление климата на нашей
планете и отмечены негативные последствия этого явления. А каким будет климат
через сто и более лет?

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

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

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

6

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

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

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

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

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

7

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

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

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

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

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

широте и долготе на всей поверхности земного шара и 40 слоями по высоте. Это дает
около 2,6x106 элементов. Каждый элемент описывается примерно 10 компонентами.

8

Следовательно, в любой фиксированный момент времени состояние атмосферы на
земном шаре характеризуется ансамблем из 2,6x107 чисел. Условия обработки
численных результатов требуют нахождения всех ансамблей через каждые 10 минут, т.
е. за период 100 лет необходимо определить около 5,Зx104 ансамблей. Итого, только за
один численный эксперимент приходится вычислять 1,4x1014 значимых результатов
промежуточных вычислений. Если теперь принять во внимание, что для получения и
дальнейшей обработки каждого промежуточного результата нужно выполнить 102-103

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

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

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

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

9

при климатическом прогнозе, что опять требует больших вычислительных мощностей.

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

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

Интересно отметить, что даже там, где натурные эксперименты являются привычным
инструментом исследования, большие вычислительные системы начинают активно
использоваться. Рассмотрим, например, проблему компоновки летательного аппарата,
обладающего минимальным лобовым сопротивлением, максимально возможными
значениями аэродинамического качества и допустимого коэффициента подъемной
силы при благоприятных характеристиках устойчивости и управляемости в
эксплуатационных режимах. Для ее решения традиционно использовались продувки
отдельных деталей аппарата или его макета в аэродинамических трубах. Но вот
несколько цифр. При создании в начале века самолета братьев Райт эксперименты в
аэродинамических трубах обошлись в несколько десятков тысяч долларов,
бомбардировщик 40-х гг. потребовал миллион, а корабль многоразового пользования
“Шатл” - 100 млн. долларов. Столь же сильно возрастает время продувки в расчете на
одну трубу - почти 10 лет для современного аэробуса. Однако несмотря на огромные
денежные и временные затраты, продувки в аэродинамических трубах не дают полной
картины обтекания хотя бы просто потому, что обдуваемый образец нельзя окружить
датчиками во всех точках. Для преодоления этих трудностей также пришлось
обратиться к численным экспериментам с математической моделью.

10