Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Трифонов П.Ф. Информатика. Построение и анализ алгоритмов - файл fastalgorithms.doc


Трифонов П.Ф. Информатика. Построение и анализ алгоритмов
скачать (840.2 kb.)

Доступные файлы (2):

fastalgorithms.doc4089kb.27.10.2009 00:47скачать
fastalgorithms.pdf788kb.26.09.2007 18:00скачать

содержание
Загрузка...

fastalgorithms.doc

  1   2   3   4   5   6   7   8
Реклама MarketGid:
Загрузка...
Информатика. Построение и анализ алгоритмов.


П. В. Трифонов
8 августа 2007 г.


Оглавление

1 Введение
2 Архитектура вычислительных систем

3
5

2.1 Основные компоненты ЭВМ . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Архитектура процессора . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.2 Оперативная память . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Параллельные вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Классификация параллельных систем . . . . . . . . . . . . . . . . . 9

2.2.2 Параллельные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . 13

2.3 Реализация вычислительных алгоритмов . . . . . . . . . . . . . . . . . . . 17

2.3.1 Влияние характеристик процессора на скорость вычислений . . . . 17

ЛР № 1: Исследование возможностей процессора . . . . . . . . . . . . . 28

2.3.2 Другие приемы повышения производительности . . . . . . . . . . . 29

ЛР № 2: Реализация вычислительного алгоритма . . . . . . . . . . . . . . 33


3 Алгоритмы компьютерной алгебры
35

3.1 Анализ сложности алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1.1 Метод подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1.2 Метод итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 Операции над матрицами . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.1 Умножение произвольных матриц . . . . . . . . . . . . . . . . . . . 37

3.2.2 Умножение двоичных матриц . . . . . . . . . . . . . . . . . . . . . . 38

3.2.3 Алгоритмы работы с разреженными матрицами . . . . . . . . . . . 38

3.3 Операции над многочленами . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.1 Билинейные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.2 Алгоритмы Карацубы и Тоома-Кука вычисления свертки . . . . . . 41

3.3.3 Алгоритм Винограда . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.3.4 Перенос алгоритмов на поля другой природы . . . . . . . . . . . . . 44

3.3.5 Гнездовые алгоритмы свертки . . . . . . . . . . . . . . . . . . . . . 46

3.3.6 Итеративные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . 47

3.3.7 Деление многочленов . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.3.8 Вычисление значений многочленов . . . . . . . . . . . . . . . . . . 54

3.3.9 Интерполяция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1



ЛР № 3: Реализация быстрого алгоритма свертки в виде линейной

программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

ЛР № 4: Реализация итерированного быстрого алгоритма свертки . . . . 59

ЛР № 5: Распараллеливание быстрого алгоритма свертки . . . . . . . . . 59

3.4 Дискретное преобразование Фурье . . . . . . . . . . . . . . . . . . . . . . 60

3.4.1 Преобразование Фурье в дискретном и непрерывном случаях . . . 60

3.4.2 Общие алгоритмы быстрого преобразования Фурье . . . . . . . . . 62

3.4.3 Алгоритмы БПФ в конечных полях . . . . . . . . . . . . . . . . . . 69

3.4.4 Применение БПФ для вычисления свертки . . . . . . . . . . . . . . 79

3.4.5 Алгоритм Шёнхаге-Штрассена . . . . . . . . . . . . . . . . . . . . 79

ЛР № 6: Реализация алгоритма БПФ в виде линейной программы . . . . . 83

ЛР № 7: Реализация алгоритма БПФ большой размерности . . . . . . . . 84

ЛР № 8: Реализация параллельного алгоритма БПФ большой

размерности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.5 Операции над целыми числами . . . . . . . . . . . . . . . . . . . . . . . . . 85

3.5.1 Представление целых чисел в ЭВМ . . . . . . . . . . . . . . . . . . 85

3.5.2 Сложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.5.3 Умножение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.5.4 Деление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.5.5 Возведение в степень . . . . . . . . . . . . . . . . . . . . . . . . . . 90

3.6 Основные результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

3.7 Задания для курсовых работ . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2
^ Глава 1

Введение


Современные фундаментальные и прикладные исследования и инженерная

деятельность характеризуются постоянным ростом размерности и сложности решаемых

задач. Несмотря на постоянное увеличение производительности вычислительных

систем, среднее время расчетов, необходимых для решения типовых научно-

технических задач, имеет тенденцию к возрастанию. В связи с этим возникает

задача повышения эффективности вычислительных ядер существующего и вновь

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

производительности вычислительных систем:
1. Применение более быстрого процессора. При этом необходимо учитывать, что в

настоящее время совершенствование процессоров происходит в основном за счет

реализации различных форм параллелизма, эффективное использование которых

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

оказывается, что классическая теория быстрых алгоритмов не учитывает многих

особенностей современных процессоров, что приводит к снижению эффективности

программной реализации быстрых алгоритмов.
3. Применение параллельных вычислений. При реализации параллельных программ

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

доступа к общим данным. Кроме того, не все алгоритмы допускают эффективное

распараллеливание.
В большинстве случаев приходится комбинировать вышеприведенные методы

повышения производительности.

Данный курс в основном посвящен классической теории быстрых алгоритмов

[20, 16, 6]. При этом дополнительно рассматриваются возможности их параллельной

реализации. Курс сопровождается набором лабораторных работ, которые позволяют

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

предлагается выполнить курсовую работу. Выполнение курсовой работы предполагает

3


использование дополнительной литературы, ссылки на которую приведены в тексте

задания.

Данный курс был разработан при поддержке компании Intel. Автор выражает

благодарность А. Исакову, А. Дедовой и М. Димашовой за многочисленные

конструктивные замечания.
4
^ Глава 2

Архитектура вычислительных систем


В данном разделе рассматриваются архитектура и принципы работы основных

компонентов современных ЭВМ с точки зрения разработчика вычислительного

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

на полноту. Приведенные здесь сведения используются в дальнейшем при исследовании

практической эффективности различных алгоритмов.

2.1 Основные компоненты ЭВМ
2.1.1 Архитектура процессора

Понятие архитектуры вычислительного процессора включает в себя набор (систему)

команд и компонентов процессора, доступных для использования программами,

выполняемыми на данном процессоре. Наиболее важным компонентом процессора,

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

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

процессора понимается совокупность технических приемов, использованных

разработчиком процессора для достижения заданных требований к производительности

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

различные микроархитектурные реализации. Система команд практически всех

процессоров включает в себя следующие группы команд:
1. Арифметические команды, включающие инструкции сложения, вычитания и

побитовых операций (И, ИЛИ, сдвиг и т.п.). Некоторые процессоры могут не иметь

команд умножения и деления.
2. Команды сравнения, условного и безусловного перехода, вызова подпрограмм и

возврата управления.
3. Команды пересылки данных из памяти в регистры общего назначения и обратно.


5


4. Системные команды, используемые операционной системой для реализации

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

непосредственно значение операнда, указан номер регистра, содержащего операнд,

указан адрес ячейки оперативной памяти, в которой находится операнд, или задано

выражение, с помощью которого может быть вычислен этот адрес.

Выполнение каждой команды включает в себя следующие основные этапы:
1. Выборка команды из ячейки памяти, задаваемой счетчиком инструкций.

Достаточно часто оказывается, что различные инструкции занимают различное

количество байт. В связи с этим устройству выборки приходится динамически

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

может занять существенное время, поэтому при написании или генерации

машинного кода целесообразно избегать их использования. После выборки

инструкции счетчик команд увеличивается на длину команды. Команды условного и

безусловного перехода, вызова подпрограмм и возврата из них, а также системные

команды могут модифицировать значение счетчика команд.
2. Декодирование выбранной команды, т.е. генерирация последовательности

управляющих сигналов для отдельных узлов процессора, ответственных за

выполнение операции, задаваемой командой. В некоторых случаях инструкция

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

выбранную команду. Эти микрооперации обрабатываются далее аналогичным

образом. Различные команды используют различные наборы узлов процессора и

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

сказываться на времени их выполнения.
3. Выполнение декодированной команды (или микрокоманды) состоит в коммутации

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

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

этим каждая команда характеризуется задержкой выполнения (latency), равной числу

тактов процессора, требуемых для выполнения всех микрокоманд, составляющих

данную инструкцию, и временем выполнения (throughput), равным минимальному

числу тактов, которое должно пройти, прежде чем процессор будет готов повторно

запустить на выполнение эту же команду. Время выполнения команд, как правило,

меньше задержки их выполнения. Большинство современных процессоров использует

конвейерный принцип обработки команд, т.е., например, одновременно с декодированием

одной инструкции может осуществляться выборка другой инструкции. Благодаря

этому в идеальном случае производительность процессора определяется временем

выполнения команд. Однако в реальных программах могут встречаться инструкции
6


условных переходов. Они вызывают простои конвейера, т.к. до момента выполнения

собственно инструкции перехода неизвестно, какие инструкции должны выполняться

далее. После того, как инструкция перехода будет выполнена, пройдет некоторое

количество тактов прежде чем будут подготовлены к исполнению новые инструкции. В

связи с этим многие современные процессоры используют предсказание ветвлений на

основе собранных статистических данных о ранее выполненных инструкциях условного

перехода. Однако предсказание ветвлений не всегда бывает успешным. Поэтому

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

фрагментах программы.

Простои конвейера могут происходить как при обработке инструкций с большим

временем выполнения, так и в том случае, когда очередная команда требует обращения к

внешнему медленному устройству, например оперативной памяти. Для снижения потерь

некоторые процессоры имеют возможность переупорядочивать команды. Это возможно

в том случае, когда эти инструкции не имеют зависимостей по данным. Например,

последовательность операций A = B[i] + C; D = E + C может быть преобразована

в D = E + C; A = B [i] + C, что позволит избежать простоя исполнительного

устройства процессора во время загрузки из памяти значения B [i], которое может

производиться одновременно с вычислением D = E +C. Зависимости по данным делятся

на истинные (например, A = B + C; D = A ∗ E) и ложные (A = B + C; B =

C + D). Для борьбы с последними процессор может динамически переименовывать

регистры, используемые в обрабатываемых командах. Действительно, последний пример

может быть преобразован к виду A = B + C; E = C + D, что дает возможность

исполнять эту последовательность команд в любом порядке. В дальнейшем все ссылки

на регистр B также должны быть заменены на регистр E. На микроархитектурном

уровне это реализуется с помощью набора (банка) регистров, на которые динамически

отображаются архитектурные регистры.

Если система команд процессора допускает множество различных схем адресаций,

содержит составные инструкции и в целом является сложной и запутанной (Com-

plicated instruction set computer, CISC), задача динамического переупорядочения

команд и переименования регистров становится весьма нетривиальной, что приводит к

существенному снижению производительности. Примером CISC-процессоров является

семейство Intel x86. На практике многие “сложные” команды используются достаточно

редко. В связи с этим получила широкое распространение концепция RISC-процессоров

(reduced instruction set computer), в которых система команд сведена к абсолютному

минимуму (Sun SPARC, PowerPC, PA-RISC). Это позволяет увеличить количество

доступных регистров и упростить обработку команд. Некоторые CISC-процессоры

содержат RISC-ядро, осуществляя динамическое преобразование потока команд.

Некоторые процессоры допускают параллельное исполнение команд, не имеющих

зависимостей по данным (параллелизм на уровне машинных команд). Суперскалярные

процессоры (например, Intel Pentium Pro+, AMD Athlon) не предполагают, что

программа в терминах машинных команд содержит какие-либо указания о возможном

параллелизме. Задача обнаружения параллелизма полностью возлагается на

оборудование процессора, что приводит к его резкому усложнению. Альтернативой
7


этому подходу является концепция VLIW (Very large Instruction Word), состоящая в

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

выявления параллелизма в данном случае возлагается на компилятор, т.е. реализуется

однократно на программном уровне.

^ 2.1.2 Оперативная память

Главным требованием к оперативной памяти является обеспечение малого времени

доступа к ней. Это является достаточно сложной технической задачей, поэтому

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

ростом объема подсистемы памяти:

1. Регистровая память. Регистры располагаются непосредственно на процессоре,

могут быть подключены напрямую к его устройствам обработки, что дает

возможность использовать их в качестве операндов команд.
2. Кеш-память. Кеш-память располагается на процессоре или в непосредственной

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

использованных участков оперативной памяти. Кеш-память может иметь

многоуровневую структуру.
3. Оперативное запоминающее устройство. ОЗУ может рассматриваться как кеш-

память для часто используемых участков виртуальной памяти системы.
4. Виртуальная память. Виртуальная память реализуется средствами операционной

системы во взаимодействии с центральным процессором. С помощью данного

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

объем памяти, при этом наиболее часто используемые фрагменты (страницы)

располагаются в ОЗУ, а редко используемые — выгружаются на некоторое

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

процессоров поддерживают аппаратную трансляцию адресов виртуальной памяти

в адреса физической памяти. Виртуальная память позволяет также организовать

безопасное выполнение нескольких процессов на одной ЭВМ.
5. Внешняя память. В некоторых случаях приходится прибегать к распределенной

обработке данных, при которой может потребоваться обращение к данным

физически расположенным на другой ЭВМ. В этом случае обращение к различным

участкам памяти производится различными методами (Non-uniform memory access,

NUMA).
Эффективная реализация обменов между различными типами оперативной памяти

базируется на следующих основных правилах: обращаться к медленной памяти как

можно реже, переносить за обмен как можно больше и при каждом переносе

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

предполагают, что выполняется свойство локальности вычислений, состоящее в том, что
8


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

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

производительности ЭВМ.

^ 2.2 Параллельные вычисления
2.2.1 Классификация параллельных систем

В данном разделе рассмотрены несколько подходов к классификации вычислительных

систем. Необходимо учитывать, что в большинстве современных систем могут

присутствовать признаки сразу нескольких классов.
^ Классификация Флинна

Наиболее известной классификацией вычислительных систем является классификация

Флинна [7, 1]:
1. SISD (single instruction stream/single data stream) —одиночный поток команд

и одиночный поток данных. К этому классу относятся последовательные

компьютерные системы, которые имеют один центральный процессор, способный

обрабатывать только один поток последовательно исполняемых инструкций.

В настоящее время практически все высокопроизводительные системы имеют

более одного центрального процессора, однако каждый из них выполняет

несвязанные потоки инструкций, что делает такие системы комплексами SISD-

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

обработки команд и скорости выполнения арифметических операций может

применяться конвейерная обработка. Примерами компьютеров с архитектурой

SISD могут служить процессоры x86, не поддерживающие набор инструкций

MMX.
2. MISD (multiple instruction stream / single data stream) –– множественный поток

команд и одиночный поток данных. Теоретически в этом типе машин множество

инструкций должно выполняться над единственным потоком данных. В настоящее

время отсутствует единое мнение о том, какие архитектуры процессоров могут

быть отнесены к этому классу. Среди возможных вариантов рассматриваются

суперскалярные процессоры, сигнальные процессоры, системы с аппаратной

избыточностью и т.п.
3. SIMD (single instruction stream / multiple data stream) —- одиночный поток команд

и множественный поток данных. Эти системы обычно имеют некоторое количество

процессоров, которые могут выполнять одну и ту же инструкцию относительно

разных данных в жесткой конфигурации. Единственная инструкция параллельно

выполняется над многими элементами данных. Примерами SIMD-машин являются

9



Проц 1

Проц 2

Общая физическая память


Проц 3

Ввод/

вывод


Рис. 2.1: SMP-система
системы CPP DAP, Gamma II и Quadrics Apemille. Другим подклассом SIMD-

систем являются векторные компьютеры. Векторные компьютеры манипулируют

массивами сходных данных подобно тому, как скалярные машины обрабатывают

отдельные элементы таких массивов. Это делается за счет использования

специально сконструированных векторных центральных процессоров. Когда

данные обрабатываются посредством векторных модулей, результаты могут быть

выданы на один, два или три такта частотогенератора (такт частотогенератора

является основным временным параметром системы). При работе в векторном

режиме векторные процессоры обрабатывают данные практически параллельно,

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

Примерами векторных процессоров являются Intel-совместимые процессоры,

поддерживающие наборы инструкций MMX, SSE[2,3].
4. MIMD (multiple instruction stream / multiple data stream) –– множественный поток

команд и множественный поток данных. Эти машины параллельно выполняют

несколько потоков инструкций над различными потоками данных. В отличие

от упомянутых выше многопроцессорных SISD-машин, команды и данные

связаны, потому что они представляют различные части одной и той же задачи.

Например, MIMD-системы могут параллельно выполнять множество подзадач с

целью сокращения времени выполнения основной задачи. Большое разнообразие

попадающих в данный класс систем делает классификацию Флинна не полностью

адекватной.
^ Классификация по способу организации памяти

Параллельные компьютеры могут быть дополнительно классифицированы по

способу организации памяти. SMP (symmetric multiprocessing) –– симметричная

многопроцессорная архитектура. Главной особенностью систем с архитектурой SMP

является наличие общей физической памяти, разделяемой всеми процессорами (см.

рис. 2.1). Память служит, в частности, для передачи сообщений между процессорами,

при этом все вычислительные устройства при обращении к ней имеют равные права и

одну и ту же адресацию для всех ячеек памяти. Поэтому SMP-архитектура называется
10



симметричной. Последнее обстоятельство позволяет очень эффективно обмениваться

данными с другими вычислительными устройствами. Наиболее известными SMP-

системами являются SMP-cерверы и рабочие станции на базе процессоров Intel,

AMD, IBM, HP и др. В настоящее время стали доступны многоядерные SMP-системы,

содержащие несколько вычислительных ядер в одной микросхеме.

Основные преимущества SMP-систем:
• простота и универсальность для программирования. Архитектура SMP не

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

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

все процессоры работают независимо друг от друга. Однако можно реализовать

и модели, использующие межпроцессорный обмен. Использование общей памяти

увеличивает скорость такого обмена, пользователь также имеет доступ сразу

ко всему объему памяти. Для SMP-систем существуют довольно эффективные

средства автоматического распараллеливания;
• простота эксплуатации. Как правило, SMP-системы используют систему

кондиционирования, основанную на воздушном охлаждении, что облегчает их

техническое обслуживание;
• относительно невысокая цена.
Недостатки:
• системы с общей памятью плохо масштабируются. Этот существенный недостаток

SMP-систем не позволяет считать их по-настоящему перспективными. Причиной

плохой масштабируемости является то, что в данный момент шина способна

обрабатывать только одну транзакцию, вследствие чего возникают проблемы

разрешения конфликтов при одновременном обращении нескольких процессоров

к одним и тем же областям общей физической памяти. Вычислительные

элементы начинают друг другу мешать. Когда произойдет такой конфликт,

зависит от скорости связи и от количества вычислительных элементов. В

настоящее время конфликты могут происходить при наличии 8-24 процессоров.

Кроме того, системная шина имеет ограниченную (хоть и высокую) пропускную

способность (ПС) и ограниченное число слотов. Все это очевидно препятствует

увеличению производительности при увеличении числа процессоров и числа

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

32 процессоров.
Для построения масштабируемых систем на базе SMP используются кластерные

или NUMA-архитектуры. При работе с SMP-системами используют так называемую

парадигму программирования с разделяемой памятью (shared memory paradigm).

MPP (massive parallel processing) – массивно-параллельная архитектура. Главная

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

11



Процессор

Оперативная

память

Коммуникационная

сеть
Процессор

Оперативная

память


Рис. 2.2: MPP-система
В этом случае система строится из отдельных модулей, содержащих процессор1,

локальный банк операционной памяти (ОП), коммуникационные процессоры (рутеры)

или сетевые адаптеры, иногда – жесткие диски и/или другие устройства ввода/вывода.

По сути, такие модули представляют собой полнофункциональные компьютеры (см.

рис. 2.2). Доступ к банку ОП из данного модуля имеют только процессоры

(ЦП) из этого же модуля. Модули соединяются специальными коммуникационными

каналами. Пользователь может определить логический номер процессора, к которому он

подключен, и организовать обмен сообщениями с другими процессорами. Используются

два варианта организации работы операционной системы (ОС) на машинах MPP-

архитектуры. В одном полноценная ОС работает только на управляющей машине (front-

end), на каждом отдельном модуле функционирует сильно урезанный вариант ОС,

обеспечивающий работу только расположенной в нем ветви параллельного приложения.

Во втором варианте на каждом модуле работает полноценная UNIX-подобная ОС,

устанавливаемая отдельно.

Главным преимуществом систем с раздельной памятью является хорошая

масштабируемость: в отличие от SMP-систем, в машинах с раздельной памятью

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

возникает необходимости в потактовой синхронизации процессоров. Практически все

рекорды по производительности на сегодня устанавливаются на машинах именно такой

архитектуры, состоящих из нескольких тысяч процессоров (ASCI Red, ASCI Blue

Pacific).

Недостатки:
• отсутствие общей памяти заметно снижает скорость межпроцессорного обмена,

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

между процессорами. Требуется специальная техника программирования для

реализации обмена сообщениями между процессорами;
• каждый процессор может использовать только ограниченный объем локального

банка памяти;

1В некоторых случаях модули представляют собой SMP-системы, оснащенные несколькими

процессорами. Но в этом случае уже нельзя говорить о чистой MPP-системе.
12



• вследствие указанных архитектурных недостатков требуются значительные

усилия для того, чтобы максимально использовать системные ресурсы. Именно

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

параллельных систем с раздельной памятью
^ 2.2.2 Параллельные алгоритмы

Под параллельными алгоритмами понимаются алгоритмы, некоторая часть которых

может выполняться одновременно на различных вычислительных устройствах. Это

определение включает в себя все возможные типы параллелизма, описанные в разделе

2.2.1. Всякий алгоритм, не содержащий условных операторов, может быть представлен

в виде последовательности операций. Сопоставим каждой операции узел в графе.

Если результат операции A используется операцией B, проведем дугу от A к B.

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

соответствуют исходным данным, а вершины без исходящих узлов — результатам

вычислений. Реальные программы могут содержать условные операторы или иным

образом изменять свое поведение в зависимости от своих параметров, т.е. граф алгоритма

может быть недетерминированным. Но для большинства вычислительных алгоритмов

условные операторы могут быть погружены в некоторые макрооперации, а графы,

получаемые для различных значений параметров, имеют сходную структуру. Поэтому в

дальнейшем будут рассматриваться детерминированные графы.

Разметим узлы графа числами v(Ai) таким образом, что если существует дуга из Ai

в Aj, то v(Ai) < v(Aj). Размеченный таким образом граф носит название строгой

параллельной формой алгоритма. Она может быть построена следующим образом:

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

их индексом 0.

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

их индексом 1.

4. Удалить помеченные вершины.
5. Действовать аналогично до исчерпания всех вершин графа.

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

меткой v(Ai). Существует строгая параллельная форма, в которой максимальная из длин

путей, оканчивающихся в вершине с индексом k, равна k. Среди таких параллельных

форм существует такая, для которой все входные вершины находятся в группе с

одним индексом, равным 0. Данная параллельная форма носит название канонической

параллельной формы. Каноническая параллельная форма единственна.

Пример 2.1. Рассмотрим следующий алгоритм (Карацубы) вычисления произведения

многочленов первой степени c0+ c1x + c2x2 = (a0+ a1x)(b0+ b1x):
13

a0

c0


a1

c1
-
-
*
+
+
*

*


b0

c2


b1


8

7
6

5
4
3
2
1
0


a0


c0
*
+
a1


c1
-
-
*
+
b0


c2
*


b1


a0


c0
*
+
+
a1


c1
-
*
+
b0


c2
*


b1

(a) Строгая неканоническая форма (b) Каноническая параллельная (c) КПФ модифицированного

форма

алгоритма

1. c0= a0b0

2. c2= a1b1

3. t1= a0+ a1

4. t2= b0+ b1

5. t3= t1t2

6. t4= t3− c0

7. c1= t4− c2
Рис. 2.3: Параллельные формы алгоритма Карацубы

Заметим, что последние два шага могут быть заменены на t4= c2+ c0и c1= t3− t4. На

рисунке 2.3 представлены несколько параллельных форм этого алгоритма.

Ярусом параллельной формы называется группа вершин с одинаковыми номерами.

Предполагая, что все операции выполняются за одно и то же время и в наличии имеется

достаточно большое число процессоров, получим, что номер яруса указывает момент

окончания соответствующих операций. Максимальное число узлов в ярусе называется

шириной параллельной формы. Число ярусов называется высотой параллельной формы.

Параллельная форма минимальной высоты называется максимальной. Данное название

связано с тем, что уменьшение высоты формы достигается, как правило, за счет

увеличения ее ширины. Каждая параллельная форма соответствует определенной

реализации заданного алгоритма. Например, параллельная форма, представленная на
14



рисунке 2.3(a), соответствует реализации алгоритма Карацубы на последовательном

компьютере, в то время как форма на рисунке 2.3(b) соответствует реализации на ЭВМ с

четырьмя независимыми исполнительными устройствами.

Удобной теоретической моделью для анализа параллельных алгоритмов

является концепция неограниченного параллелизма. В рамках данной концепции

предполагается, что имеется бесконечно большое число процессоров, способных

выполнять любые операции, требуемые алгоритмом Процессоры работают синхронно

и способны обмениваться информацией мгновенно и без конфликтов. Ясно, что в этом

случае минимальное время выполнения достигается при использовании алгоритма с

минимальной высотой.
Теорема 2.1. Пусть функция существенно зависит от n переменных и

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

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

операций не может быть меньше logpn

Доказательство. Пусть на нулевом ярусе параллельной формы расположены

вершины, соответствующие входным переменным алгоритма. На верхнем ярусе должна

находиться единственная вершина, соответствующая выходной переменной. В каждую

вершину графа может входить не более p дуг. Если параллельная форма содержит s

ярусов, то нижний из них не может иметь более ps вершин. С другой стороны, известно,

что он содержит ровно n вершин. Таким образом, n ≤ psи s ≥ logpn.

^ Реальной производительностью вычислительного устройства или их системы

называется количество операций, реально выполненных в среднем за единицу времени

при решении некоторой фиксированной задачи. ^ Пиковой производительностью

называется максимальное число операций, которое может быть выполнено тем

же устройством/системой за единицу времени при отсутствии связей между

функциональными узлами. Стоимостью работы называется время последовательной

реализации всех рассматриваемых операций на заданном устройстве. Загруженностью

устройства на данном отрезке времени называется отношение стоимости реально

выполненной работы к максимально возможной стоимости. В параллельных

вычислительных системах часто встречается ситуация, при которой в силу структуры

используемого алгоритма невозможно загрузить полезной работой некоторые

исполнительные устройства. Если система состоит из l устройств, имеющих пиковые

производительности π1, . . . , πl, работающих с загруженностями p1, . . . , pl, то реальная

производительность r системы равна
∑l

r = piπi(2.1)

i=1

Целесообразность применения параллельных вычислительных систем для решения

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

15


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

l

R =

i=1pi

maxiπi

(2.2)

Таким образом, при использовании l вычислительных устройств максимальное

возможное ускорение равно l. Оно достигается при полной загрузке всех устройств, что

требует использования соответствующего алгоритма.

Теорема 2.2. Пусть высота параллельной формы равна s и всего в алгоритме

выполняется N операций. Максимально возможное ускорение вычислений при их

параллельной реализации по сравнению с последовательной равно N/s

Доказательство. Пусть система состоит из l устройств пиковой производительности

π. Предположим, что за время T реализации алгоритма на i-м устройстве выполняется

Niопераций. Следовательно, загруженность этого устройства равна πTNi . Таким образом,

ускорение системы равно R =

l

i=1

π

Ni

πT π

=N

πT . Время реализации одного яруса

пареллельной формы равно 1/π. Поэтому время реализации алгоритма удовлетворяет

T ≥ s/π, откуда и вытекает утверждение теоремы.

Минимально возможное число l устройств, необходимое для достижения предельного

ускорения, равно ширине алгоритма. В реальности редко удается обеспечить одинаковое

время выполнения всех операций параллельной формы, что снижает производительность

системы.

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

приходится выполнять последовательно, т.е. соответствующие ярусы параллельной

формы имеют ширину 1. Отношение β =Nn называется долей последовательных

вычислений.

Теорема 2.3 (Закон Амдала). Пусть система состоит из l одинаковых

универсальных вычислительных устройств. Предположим, что при выполнении

параллельной части алгоритма все устройства загружены полностью. Тогда

максимально возможное ускорение равно

l

R =

βl + (1 − β)

(2.3)

Доказательство. Пусть π — пиковая производительность отдельного

вычислительного устройства. Если всего выполняется N операций, βN из них

выполняются последовательно, например, на первом устройстве, и (1 − β)N

операций выполняются параллельно на l устройствах по (1 − β)N/l на каждом. Всего

алгоритм реализуется за время T1= βN+(1π−β)N/l . На параллельной части алгоритма

работают как первое, так и остальные устройства в течение Ti=(1−βπ)N/l, i= 2..l.

(1−β)N/l

Таким образом, ρ1= 1 и ρi=

βN+(1−β)N/l, i≥ 2. Согласно (2.2), получим

R = 1 + ∑li=2 βl+(11−β−β)=(l−1)(1βl−+(1β)+−βlβ+(1) −β)=

l

lβ+(1−β)


16



Приведенные теоремы позволяют оценить максимально возможный выигрыш,

достижимый за счет распараллеливания вычислений. Известно достаточно большое

число алгоритмов, построенных согласно концепции неограниченного параллелизма.

Однако большинство таких алгоритмов характеризуется численной неустойчивостью,

огромными требованиями к числу процессоров и сложной схемой обмена данными, что

делает эти алгоритмы практически бесполезными. Тем не менее, полученные результаты

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

алгоритмов.

В связи с этим возникает необходимость поиска внутреннего параллелизма

в существующих вычислительных алгоритмах. Если построена параллельная форма

некоторого вычислительного алгоритма и ее ярусы имеют достаточно большую ширину,

существует принципиальная возможность его параллельной реализации. Поиск хорошей

параллельной формы может потребовать некоторых алгебраических преобразований,

как это было сделано при построении параллельной формы на рисунке 2.3(c), где за счет

использования свойств операции сложения удалось уменьшить число ярусов.

Многие вычислительные алгоритмы компьютерной алгебры строятся по принципу

“разделяй и властвуй”, т.е. исходная задача разбивается на p аналогичных подзадач

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

объединяются с помощью какой-либо сравнительно простой операции. Разбиение

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

дерево разбиения, которое может рассматриваться как граф алгоритма. На k-ом уровне

разбиения ширина графа равна pk. Полная загрузка всех процессоров будет обеспечена2,

если выполняется условие l|pk.
  1   2   3   4   5   6   7   8



Скачать файл (840.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru