Информатика, вычислительная техника и инженерное образование 2011, №1(3) эволюционное моделирование, генетические и бионические алгоритмы

ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ НОВОГО ПОКОЛЕНИЯ И НЕЙРОКОМПЬЮТЕРЫ УДК 004.021 П.Н. Филиппенко, А.А. Шашелов, С.В. Сеитова МАТЕМАТИЧЕСКИЕ ПРОБЛЕМЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ В статье рассмотрены математические проблемы больших вычислений. Приводится необходимость параллельного программирования и связанные с ним трудности. Показаны условия построения математически корректных быстрых параллельных алгоритмов. Рассмотрена информационная структура параллельных алгоритмов. Сте­пень па­ра­л­ле­лиз­ма, параллельная форма, зернистость задачи, ошибки округления. P.N. Filippenko, A.A. Shashelov, S.V. Seitova MATHEMATICAL PROBLEMS OF PARALLEL CACLULATION ALGORITHMS Mathematical problems of large calculations are discussed in the article. Necessity of parallel programming and related difficulties are given. Conditions for creating mathematically correct and robust parallel algorithms are shown. Informational structure of parallel algorithms is considered. Degree of parallelism, parallel form, task granularity, rounding errors. Введение Возможность быстрого решения задач на вычислительной технике вынуждает пользователей изменять весь привычный стиль взаимодействия с компьютерами. Сложность задач решаемых пользователем заставляет пересмотреть концепции разработки программного обеспечения (ПО). Это ведет к изменению, как ПО, так и аппаратных решений. По сравнению, например, с персональными компьютерами и рабочими станциями меняется практически всё: применяются другие языки программирования, видоизменяется большинство алгоритмов, от пользователей требуется предоставление многочисленных нестандартных и трудно добываемых характеристик решаемых задач, интерфейс перестает быть дружественным и т.п. Важным является то обстоятельство, что неполнота учета новых условий работы может в значительной мере снизить эффективность использования новой, достаточно дорогой техники. Для обычного пользователя инструментарий, т.е. техника и программное окружение, всегда является чем-то заданным. Если инструментарий и может быть изменен, то в ограниченных пределах. Остается подстраивать под его требования объекты, т.е. алгоритмы [1,2]. Математические проблемы параллельных вычислений Общий характер трудностей, сопровождающих развитие параллельных вычислений, в целом выглядит таким же, каким он был и во времена последовательных. Только для параллельных вычислений все трудности проявляются в более острой форме. Во многом из-за большей сложности самой предметной области. Но, главным образом, вследствие того, что к началу активного внедрения вычислительных систем параллельной архитектуры в практику решения больших прикладных задач не был построен нужный теоретический фундамент и не был развит математический аппарат исследований [1,3]. За время развития последовательных вычислений пришло довольно чёткое понимание, что такое последовательный алгоритм. Вокруг данного понятия сформировался большой раздел математики, называемый теорией алгоритмов, изучающий общие свойства последовательных вычислений. Уточнённое понятие алгоритма в терминах идеализированных вычислительных машин привело к важному понятию машины Тьюринга. По существу, этот автомат стал теоретическим прообразом первых ЭВМ. Присоединение к машине Тьюринга памяти сделало её весьма полезным и даже приближенным к реальности инструментом исследований. Но в основе всего лежали последовательные действия. Не удивительно поэтому, что и ЭВМ в течение длительного периода также развивались по пути реализации именно последовательных действий [1,3]. Общая направленность последовательного выполнения операций сохранялась долго, но в разработке вычислительной техники незаметно назревали изменения, приведшие, к пересмотру представлений о вычислениях. Причиной возникновения изменений стал параллелизм, внедряемый в вычислительную технику для повышения производительности. В определённый момент параллелизма в компьютере стало столь много, что его присутствие уже нельзя было прикрывать техническими решениями. И тогда от пользователя стало необходимо получать дополнительную информацию о структуре используемых им алгоритмов. Эта информация нужна для того, чтобы эффективно использовать заложенный в компьютер параллелизм [2,5]. К началу массового внедрения вычислительных систем параллельной архитектуры многие математические вопросы параллельных процессов оказались в зачаточном состоянии. Не было никакой целостной теории параллельных алгоритмов, аналогичной теории алгоритмов для последовательных вычислений. Существовали лишь отдельные разрозненные результаты. Не было даже сколько-нибудь ясного представления, что же нужно понимать под параллельным алгоритмом. Отсутствовал какой-либо формальный математический аппарат, который можно было бы назвать параллельным аналогом машины Тьюринга [3]. Эти причины привели к тому, что в течение долгого времени параллельные вычисления не удавалось сформировать как самостоятельную математическую науку, и рассматривались они как совокупность каких-то полуэвристических приемов приспособления алгоритмов к требованиям новой техники. Новые параллельные алгоритмы Интерес к их построению на основе математически эквивалентных преобразований возник в 60-70-х годах прошлого столетия в связи с появлением первых вычислительных систем параллельной архитектуры [6-8]. Чтобы оценить время реализации алгоритма на параллельной системе, алгоритм представляют в виде последовательно выполняемых ансамблей операций. В каждом ансамбле все операции не должны быть связаны друг с другом. Если архитектура параллельной системы позволяет реализовывать одновременно все операции каждого ансамбля, то без учёта времени на передачи данных время выполнения алгоритма будет пропорционально числу ансамблей. Число ансамблей называют высотой алгоритма. Алгоритмы, в которых высота меньше общего числа операций называют параллельными, а их представление через последовательность ансамблей из независимых операций – параллельной формой [3]. Очевидно, что в зависимости от структуры связей между операциями один и тот же алгоритм может быть представлен различными способами в виде совокупности ансамблей. В частности, обычная последовательная реализация означает, что в каждом ансамбле содержится только одна операция. Для большинства алгоритмов даже таких представлений может существовать очень много. Ясно, что для каждой задачи особый интерес представляет нахождение алгоритмов минимальной высоты. Согласно теории последовательных алгоритмов представления одного и того же алгоритма различными ансамблями необходимо рассматривать как разные алгоритмы, так как изменяется, как минимум, порядок выполнения операций. Следовательно, некоторые характеристики этих разных алгоритмов окажутся заведомо различными, но какие-то наверняка сохранятся [1,6]. Чтобы задача построения быстрых параллельных алгоритмов стала математически корректной, необходимо сделать какие-то предположения относительно свойств параллельной вычислительной системы. Они очень просты: система имеет бесконечно много параллельно работающих процессоров; все они работают синхронно под общим управлением и выполняют любую операцию точно и за одно и то же время; система имеет бесконечно большую память; все обмены информацией между процессорами и памятью, а также между самими процессорами осуществляются мгновенно и без конфликтов. Концепция построения алгоритмов для подобных параллельных систем получила название концепции неограниченного параллелизма. Она идеализирована, но полученные в её рамках результаты интересны и поучительны [3,7]. Рассмотрим обычный процесс суммирования n чи­сел а1… аn, когда на каждом шаге к частичной сумме прибавляется очередное слагаемое. Обыч­ный по­сле­до­ва­тель­ный ал­го­ритм: S ← а1, S←S+ аi, i = 2,…,n (1) не­при­го­ден для па­ра­л­лель­ных вы­чис­ле­ний. Од­на­ко за­да­ча мо­жет быть ре­ше­на дру­гим ме­то­дом. На ри­с. 1 по­ка­за­но, как мож­но осу­ще­ствить сум­ми­ро­ва­ние вось­ми чи­сел в три эта­па при по­мо­щи ал­го­рит­ма сдваи­ва­ния [8]. Задача суммирования разделена на меньшие подзадачи, которые могут решаться независимо. Для  n = 2q чисел алгоритм сдваивания состоит из q = log2n этапов; на первом этапе выполняются n/2 сложений, на втором – n/4, и т.д., пока на последнем этапе не будет выполнено единственное сложение. Общее число операций сложения равно n-1: такое же, как в последовательном алгоритме [8]. Рис. 1. Схе­ма ал­го­рит­ма сдваи­ва­ния[8] Очевидно, что на первом этапе степень параллелизма (число операций, ко­торые на данном этапе можно выполнять параллельно) равна n/2, на вто­ром – n/4, и так да­лее. По­доб­ный ал­го­ритм мо­жет быть при­ме­нён и для дру­гих це­лей, на­при­мер, для на­хож­де­ния мак­си­маль­но­го эле­мен­та в мас­си­ве и да­же для сор­ти­ров­ки [8]. Сло­же­ние ал­го­рит­мом сдваи­ва­ния име­ет ещё од­но пре­иму­ще­ство пе­ред по­сле­до­ва­тель­ным сло­же­ни­ем: он обес­пе­чи­ва­ет луч­шую (в сред­нем) точ­ность сум­ми­ро­ва­ния при ис­поль­зо­ва­нии чи­сел с пла­ваю­щей точ­кой. Сред­ней сте­пе­нью па­ра­л­ле­лиз­ма чис­лен­но­го ал­го­рит­ма на­зы­ва­ет­ся от­но­ше­ние об­ще­го чис­ла опе­ра­ций ал­го­рит­ма к чис­лу его эта­пов. Оче­вид­но, для ал­го­рит­ма сдваи­ва­ния сред­няя сте­пень па­ра­л­ле­лиз­ма рав­на [8]: S = . (2) Со сте­пе­нью па­ра­л­ле­лиз­ма так­же свя­за­но по­ня­тие зер­ни­сто­сти. Круп­но­зер­ни­стость за­да­чи озна­ча­ет на­ли­чие в ней боль­ших не­за­ви­си­мых под­за­дач, ко­то­рые мож­но об­ра­ба­ты­вать па­ра­л­лель­но. При­ме­ром мо­жет слу­жить за­да­ча ре­ше­ния не­сколь­ких раз­лич­ных боль­ших си­стем ли­ней­ных урав­не­ний, ре­ше­ния ко­то­рых ком­би­ни­ру­ют­ся на бо­лее позд­них ста­ди­ях вы­чис­ли­тель­но­го про­цес­са. Мел­ко­зер­ни­стость со­от­вет­ству­ет воз­мож­но­сти па­ра­л­лель­но­го вы­пол­не­ния ма­лых под­за­дач. Так, для сло­же­ния двух век­то­ров под­за­да­чей яв­ля­ет­ся сло­же­ние ком­по­нент, имею­щих оди­на­ко­вый но­мер. Круп­но­зер­ни­стые ал­го­рит­мы слож­но рас­па­рал­ле­лить на боль­шом чис­ле про­цес­со­ров [8]. Оба алгоритма основаны на реализации математически эквивалентных выражений суммирования чисел, но они имеют разные свойства, с точки зрения параллельных вычислений. У них много и других различий: они по-разному реагируют на ошибки округления, по-разному используют память и т.п. Поэтому эти алгоритмы следует считать принципиально различными, несмотря на то, что они математически эквивалентны [2]. Пусть какой-то алгоритм существенно зависит от n входных данных и реализуется через некоторую совокупность операций, имеющих не более p аргументов. Легко показать, что такой алгоритм не может иметь высоту меньше, чем logpn. Высота любого алгоритма ограничена сверху общим числом выполняемых операций. Эти две границы являются ориентирами для построения алгоритмов минимальной высоты. Например, сразу становится ясно, что суммирование чисел по принципу сдваивания относится к оптимальным алгоритмам. Другие задачи оказываются значительно сложнее [2,3]. Высота алгоритма является очень важной характеристикой, так как показывает потенциальную возможность быстрого решения задачи на вычислительной системе параллельной архитектуры. Однако пока параллельные алгоритмы малой высоты не вошли в практику использования сколько-нибудь широко. Причина: подавляющее большинство из них требует огромного числа процессоров, имеет сложные коммуникационные связи и катастрофически неустойчиво [3]. Среди всех быстрых параллельных алгоритмов заметным исключением являются только суммирование чисел по принципу сдваивания и некоторые его аналоги. Подобные алгоритмы используются на практике достаточно широко [1-3]. Предельная абстрагированность от реальности концепцией неограниченного параллелизма вычислительной техники сделала её привлекательной для математиков. Тем не менее, на сегодняшний день все достижения в рамках этой концепции скорее представляют набор отдельных изобретений в области численных методов, чем систематически развивающийся раздел математики. Практически все быстрые параллельные алгоритмы на могут рассматриваться как результат математически эквивалентных преобразований формульных выражений, описывающих хорошо известные последовательные алгоритмы. Ошибки округления Основой математически эквивалентных преобразований было предположение о точном выполнении операций. На всех без исключения компьютерах на представление любого числа отводится только конечное, строго фиксированное число разрядов. Поэтому после выполнения каждой операции результат “обрезается” до нужной длины. Эта процедура вносит в результат ошибку, которая называется ошибкой округления [1]. Сами по себе ошибки округления отдельных операций очень малы. Ни одна используемая на практике стандартная программная среда не имеет инструментальных средств контроля за распространением этих ошибок. А это распространение происходит. Важнейшим фактором, объясняющим влияние ошибок округления компьютерных операций на окончательный результат, является радикальное изменение свойств математических операций. Именно, на множестве чисел, представленных в компьютере в форме с плавающей запятой, все операции перестают обладать свойствами коммутативности, ассоциативности и дистрибутивности. Известно, что даже такая простая операция как перестановка слагаемых в суммах чисел может привести из-за ошибок округления к катастрофически большим различиям [3,11]. Информационная структура алгоритмов Вычислительные эксперименты показывают, что практически все новые параллельные алгоритмы, даже те из них, которые очень эффективны в теоретическом отношении, на практике не конкурентоспособны. Поэтому на текущий момент единственно надёжным источником создания параллельных программ является подходящая реструктуризация проверенных временем последовательных программ и математических описаний. Выбор этих форм записей объясняется тем, что только они позволяют описать алгоритмы более или менее точно. Формально реструктуризация сводится к математически эквивалентным заменам в записях всех или части формульных выражений с целью явно указать обнаруженные в алгоритмах скрытый параллелизм, возможность использования распределенной памяти и т.п. Ключевым моментом становится контроль над влиянием ошибок округления на результат. Нужно иметь эффективные технологии для выявления требуемых свойств алгоритмов. Очень важно, чтобы все такие технологии были максимально независимы от пользовательских знаний, касающихся решаемых задач и используемых алгоритмов [13]. Рассмотрим все математически эквивалентные записи какого-либо алгоритма. Пусть каждая из них сделана на своем языке и реализуется на своем компьютере. Будем лишь считать едиными правила приближенного выполнения операций над числами. Среди указанных записей заведомо существует какое-то множество, которое для одних и тех же входных данных будет давать при реализации один и тот же результат с учетом влияния всех ошибок округления. Естественно предположить, что у всего этого множества должно быть какое-то общее ядро. И тогда возникают вопросы, как оно выглядит, как его находить, как использовать и т.п. [1,12] Чтобы найти общее ядро, необходимо, прежде всего, очистить записи от всех языковых наслоений. После такой очистки остается лишь некоторая совокупность выполняемых операций, связанных между собой отношениями “результат-аргумент”. Это задает граф, получивший название граф алгоритма. Можно показать, что для того чтобы в одинаковых условиях разные записи алгоритмов приводили к одним и тем же результатам, необходимо и достаточно, чтобы были изоморфны их графы. Построенные графы описывают информационные сущности алгоритмов. Они не зависят ни от используемых языков описания, ни от применяемых вычислительных средств. Поэтому вполне естественно их считать информационными ядрами самих алгоритмов [3]. Граф алгоритма имеет очень прозрачный смысл. Поэтому его легко применять в теоретических исследованиях. Однако чтобы этот граф использовать в реальных приложениях, он должен быть явно задан в какой-либо форме, приемлемой для таких целей. На практике он никогда не бывает, известен в нужном виде, и граф алгоритма приходится находить с помощью специальных методик из описывающих сам алгоритм программ или математических соотношений [3,13]. В настоящее время решены различные связанные с реструктуризацией теоретические вопросы. Разработаны различные методы обнаружения параллельных ветвей вычислений. Предложены способы минимизации коммуникационных затрат при передачах информации между процессорами, а также между процессорами и памятью. Последнее имеет особое значение в связи с развитием распределенных вычислений. Всё это сформировало новую область исследований, называемую информационной структурой алгоритмов. В её основе лежит выделение из записей алгоритма его информационного ядра, очищенного от всех элементов описания. Доказаны очень важные утверждения, из которых следует, что для широкого класса алгоритмов информационное ядро может быть описано и исследовано с помощью конечных наборов простых функций, как правило, кусочно-линейных. Построены эффективные методы вычисления, исследования и использования таких функций. Параллельная структура программ является составной частью информационной структуры алгоритмов и может быть исследована с учетом всего сказанного выше [1-3,11-13].

Похожие:

	Информатика, вычислительная техника и инженерное образование. 2011. №2 (4) В настоящем выпуске размещены работы по проблемам филологии, педагогики и методике обучения иностранным языкам, а в следующем выпуске...		О. М. Топоркова информационные технологии Учебное пособие предназначено для студентов вузов, обучающихся по направлениям подготовки Информатика и вычислительная техника; Прикладная...
	Методические указания к практическим занятиям для студентов направления... Б90 Использование субд для создания программных систем и их компонентов: Методические указания к практическим занятиям для студентов...		Диплом государственного образца о неполном высшем «Информатика и вычислительная техника» 2 курс (заочное обучение, платные места)
	Методические указания ...		Методические указания по выполнению междисциплинарной курсовой работы... Методические указания по выполнению междисциплинарной курсовой работы студентами образовательной программы «Информатика и вычислительная...
	Краевая олимпиада обучающихся по группе специальностей 09. 00. 00... Правильный ответ помечается знаком × в бланке ответов. Исправления в бланке ответов не допускаются		Методические указания к практическим работам по дисциплине Информационные... Федерального государственного образовательного стандарта по специальности среднего профессионального образования, входящей в состав...
	Основная образовательная программа высшего профессионального образования... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования		Отчет по результатам самообследования основной образовательной программы... Федеральное государственное автономное образовательное учреждение высшего профессионального образования «национальный исследовательский...