WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 19 |
Г.И.ШПАКОВСКИЙ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ:

MPI, OpenMP, кластеры, грид, многоядерные процессоры, графические процессоры, квантовые компьютеры МИНСК 2011, сентябрь Справка о книге Шпаковский Г.И. Реализация параллельных вычислений: кластеры, многоядерные процесры, грид, квантовые компьютеры. – Минск, БГУ, 2010 г., 155 с.

Книга написана на основе лекций, которые в течение длительного времени читались студентам Белорусского государственного университета (г. Минск).

По тематике параллельных вычислений и сетей изданы фундаментальные работы [1 – 4], кроме того существует ряд сайтов по проблемам параллельных вычислений [5 - 7]. Настоящая же книга предназначены для первичного ознакомления с уровнями и механизмами параллельной обработки.

Книга разделена на два раздела: «Архитектура» и «Реализация».

В разделе «Архитектура» приведены примеры классической реализации различных архитектур для мелкозернистого и крупнозернистого параллелизма:

конвейерные системы, технологии MMX и VLIW, системы с общей и индивидуальной памятью, а так же системы программирования для них, в частности, MPI и OpenMP, даны оценки эффективности вычислений для этих архитектур.

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

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

2 Оглавление Предисловие --- 5 АРХИТЕКТУРА Глава 1. ПРИНЦИПЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ --- 7 1.1. Большие задачи 1.2. Методы повышения быстродействия 1.3. Формы параллелизма 1.4. Эффективность параллельных вычислений 1.5. Закон Мура и его перспективы 1.6. Основные этапы развития параллельной обработки Глава 2. МЕЛКОЗЕРНИСТЫЙ ПАРАЛЛЕЛИЗМ --- 2.1. Принципы распараллеливания и планирования базовых блоков 2.2. Классфикация Фишера для мелкозернистого параллелизма 2.3. Технология VLIW 2.4. Технология MMX 2.5. Расширение SSE Глава 3. КРУПНОЗЕРНИСТЫЙ ПАРАЛЛЕЛИЗМ --- 3.1. Классы крупнозернистых систем по Флинну 3.2. Арифметические конвейеры 3.3. Векторно-конвейрная ЭВМ CRAY 3.4. Многопроцессорные системы с общей памятью 3.5. Многопроцессорные системы с индивидуальной памятью Глава 4. СРЕДСТВА ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ --- 4.1. Параллельные алгоритмы 4.2. Стандарт MPI 4.3. Стандарт OpenMP РЕАЛИЗАЦИИ Глава 5. ВЫЧИСЛИТЕЛЬНЫЕ КЛАСТЕРЫ --- 5.1. Кластеры 5.2. Коммуникационные системы вычислительных кластеров 5.3. Метод Гаусса решения СЛАУ на кластере Глава 6. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ В ГРИД --- 6.1. Этапы развития IT технологий 6.2.1 Обеспечение безопасности 6.2.2. Управление исполнением заданий 6.3. Параллельные вычислени в ГРИД. Пакет G6.4. Пакет gLite Глава 7. МНОГОЯДЕРНЫЕ ПРОЦЕССОРЫ --- 7.1. Что такое МЯП процессоры. Закон Мура для ядер 7.2. Две архитектуры многоядерных процессоров 7.3. Процессор Nehalem 7.4. Процессоры с индивидуальной памятью 7.5. Процессор Polaris на 80 ядер 7.6. Процессор SCC на 48 ядер Глава 8. КВАНТОВЫЕ КОМПЬЮТЕРЫ --- 8.1. Классические и квантовые компьютеры 8.3. Квантовый регистр 8.4. Квантовые гейты 8.5. Квантовый компьютер 8.6. Алгоритм Гровера 8.7. Алгоритм Шора 8.7.1 Алглоритм создания открытого и секретных ключей в RSA 8.7.2. Алгоритм факторизации Шора 8.7.3. Алгоритма Шора на квантовом компьютере 8.8. Некоторые результаты 8.9. Словать терминов к главе Приложение 1. СуперЭВМ семейства СКИФ --- Приложение 2. Графические процессоры --- Источники информации --- ПРЕДИСЛОВИЕ Настоящая книга написана на основе лекций, которые в течение длительного времени читались студентам Белорусского государственного университета (г.

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

По тематике параллельных вычислений и сетей изданы фундаментальные работыты, в частности, книга В.В.Воеводина и Вл.В. Воеводина «Параллельные вычисления» [1], книга В.Г. Олифер и Н.А. Олифер «Комьютерные сети» [2 ], книга Дж. Ортеги «Введение в параллельные и векторные методы решения линейных систем» [3], книга М. Нильсена и И. Чанга «Квантовые вычисления и квантовая информатика» [4]. Кроме того существует ряд сайтов [5 – 7 ] по различным проблемам параллельных вычислений. Настоящая же книга предназначены для первичного ознакомления со уровнями и механизмами параллельной обработки.

Книга имеет два раздела: «Архитектура» и «Реализация».

В разделе «Архитектура» описываются способы повышения быстродействия ЭВМ. Их немного:

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

2. Параллельное или совмещенное выполнение команд или программ. Эти способы могут быть реализованы разными путями, но суть их при этом не меняеся. Эту неизменность можно назвать архитектурой.

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

конвейерные системы, технологии MMX и VLIW, системы с общей и индивидуальной памятью, а так же системы программирования для них, в частности, MPI и OpenMP, даны оценки эффективности вычислений для этих архитектур.



В разделе «Реализация» описаны четыре типа параллельных систем, с помощъю которых можно увеличить количество процессоров, так как это ведет к увеличению быстродействия:

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

2. Многояденые микропроцессоры находятся в стадии своего развития, и могут использоваться как автономно в персоналых ЭВМ, так и в качестве элементной базы для кластеров. Примеры приводятся в основном по при борам компании Intel, которые дают достаточно информации для илюстрации основных тем книги, поэтому материалы по другим крупным компаниям IBM, AMD, NVIDIA практически не используются.

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

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

В приложении коротко представлена суперкомпьютерная платформа СКИФ (Супер Компьютерная Инициатива Феникс), разрабатываемая в рамках программ Союзного государства Беларуси и России. Уже сегодня платформа позволилат создать высокопроизводительные компьютеры мирового уровня.

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

Р А З Д Е Л 1. АРХИТЕКТУРА Глава 1. ПРИНЦИПЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ 1.1 Большие задачи.

Все задачи принципиально можно разделить на две группы: P (Polinomial) и NP (Non Polinomial) задачи [3]. P задачи характеризуются объемом вычислений a p, где a – объем входных данных, p – полином невысокой степени. Такие задачи под силу современным многопроцессорным ЭВМ и называются «большими». NP задачи характеризуются выражением af(a) и современным машинам «не по зубам». Для решения таких задач могут использоваться квантовые ЭВМ, скорость вычислений которых пропорциональна объему данных.

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

Обозначение Величина Достигнутый уровень Единицы измерения Кило 103 Герцы, Мега байты, Гига 109 ПЭВМ до 5 Гфлопс Тера 1012 СуперЭВМ – тера и FLOP/S Пета 1015 петафлопсы Экза Эта система обозначений относится к измерению частоты (герцы), объему памяти (байты), к количеству плавающих операций в секунду (flops – float point operations per second).

Время решения «больших» задач определяется количеством вычислительных операций в задаче и быстродействием вычислительных машин. Естественно, с ростом быстродействия вычислительных машин растет и размер решаемых задач. Для сегодняшних суперЭВМ доступными являются задачи с числом 1012 -1015 операций с плавающей точкой.

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

Предположим, что моделирование обеспечивает период 100 лет [1]. При построении алгоритмов используется принцип дискретизации. Атмосфера разби вается сеткой с шагом 1 градус по широте и долготе на всей поверхности земного шара и 40 слоями по высоте. Это дает около 2.6106 элементов. Каждый элемент описывается примерно 10 компонентами. Следовательно, в любой фиксированный момент времени состояние атмосферы характеризуется ансамблем из 2.7107 чисел. Условия моделирования требуют нахождения всех ансамблей через каждые 10 минут, то есть за 100 лет нужно определить около 5.3104 ансамблей. Итого, за один численный экперимент приходится вычислять 1.41014 значимых результатов промежуточных вычислений. Если считать, что для получения каждого промежуточного результата требуется 102 - арифметических опрераций, то проведение одного эксперимента с моделью атмосферы требуется выполнить 1016 – 1017 операций с плавающей запятой.

Следовательно, расчет атмосферы на персональной ЭВМ займет многие тысячи часов. А для полной модели земли и множества вариантов моделирования время возрастет на порядки. Значит, проводить моделирование на ПЭВМ - утопия, но на суперЭВМ – можно.

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

По количеству операций такое моделирование соизмеримо с моделированием климата. Но это касается больших стран – США, Россия, Евросоюза. А зачем суперЭВМ, например, для Беларуси.

Большое количество вычислительных моделей строится на базе решения СЛАУ, при этом размеры решетки (число уравнений) может достигать многих тысяч. Например, при моделировании полупроводниковых приборов число уравнений может быть равно N=104. Известно, что решение такой системы требует порядка N3 вычислений по 102 плавающих операций для каждого вычисления. Тогда общее время расчета одного варианта моделирования будет порядка 1014 операций.





Ниже приведены времена выполнения некоторых больших задач на современной однопроцессорной системе Проблема Число операций Время счета (флопс) Модель атмосферы 1016 - 1017 годы Модель ядерного взрыва 1016 - 1017 годы Модель обтекания самолета 1015 - 1016 месяцы, недели Краш - тесты 1014 - 1015 месяцы, недели Промышленные конструкции 1014 - 1015 недели 1.2. Методы повышения быстродействия Естественно, для решения больших задач нужны все более быстрые компьютеры. Есть всего два основных способа повышения быстродействия ЭВМ:

1. За счет повышения быстродействия элементной базы (тактовой частоты).

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

2. За счет увеличения числа одновременно работающих в одной задаче ЭВМ, процессоров, АЛУ, умножителей и так далее, то есть за счет параллелизма выполнения операций. Это требует использования сложных систем параллельного программирования. Это крупный недостаток метода.

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

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

• Параллельные системы, когда множество команд одной программы одновременно выполняются множеством АЛУ или процессоров.

Рассмотрим примеры этих методов.

Тактовая частота (рис.1.1). Тактовая частота зависит от размеров конструктива, кристалла, на котором расположены арифметико-логические элементы. Ниже на рисунке представлена схема совпадения, которая срабатывает при одновременном появлении двух сигналов.

Плата 1м х 1м а с Г И 60 нс 10 1 м 1 м с 10 нс 10 нс И 10 10 10 t а f = 109 нс/60 нс 15 Мгц Плата 1м х Плата ПЭВМ 11х 1 нс f = 109 нс/6 нс 150 Мгц Кристалл 15х15 мм 1 нс 0.15 нс f = 109 нс/0.3 нс 3 ГГц 0.15 нс 0.15 нс Рис.1.1. Рост частоты синхронизации с умешением раззмеров схемы Один сигнал поступает непосредственно от генератора, другой – с задержкой, определяемой размером платы, на которой размещена схема. Учитыая скорость света, нетрудно вычислить задержку сигнала на входе схемы И. Кроме того, сигнал должен некоторое время держаться на выходе схемы. Таким образом, для большой платы период генератора составит 60 нс, а тактовая частота – 15 Мгц, соответственнно для платы ПЭВМ и кристалла СБИС частота будет 150 Мгц и 3Ггц. Повышение тактовой частоты является важным средством повышения быстродействия компьютеров, но ограничено фундаментальными физическими законами. Естественно, при переходе на расстояния внутри кристалла, соответственно вырастает и частота.

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

Конвейерные системы. Для примера рассмотрим конвейер команд известного микропоцессора Pentium (рис.1.2 ).

Кэш команд PF Dtk Dtp EXE WR Кэш данных tp

Он содержит следующие ступени:

• ступень предвыборки PF (Prefetch), которая осуществляет упреждающую выборку группы команд в соответствующий буфер;

• ступень декодирования полей команды D1 (Decoder 1);

• ступень декодирования D2 (Decoder 2), на которой производится вычисление абсолютного адреса операнда, если операнд расположен в памяти;

• на ступени исполнения EXE (Execution) производится выборка операндов из РОН или памяти и выполнение операции в АЛУ;

• наконец, на ступени записи результата WR (Write Back) производится передача полученного результата в блок РОН.

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

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

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

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

П П2 Пn Сеть обмена данными Вход Выход Рис.1.3. Схема параллельной ЭВМ В параллельных ЭВМ межпроцессрный обмен данными является принципиальной необходимостью, и при медленном обмене однопроцессорный вариант может оказаться быстрее многопроцессорного, поэтому количество процессоров в параллельной ЭВМ определяется скоростью сетей обмена.

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

Программные объекты A и B (команды, операторы, программы) являются независимыми и могут выполняться параллельно, если выполняется следующее условие:

Pages:     || 2 | 3 | 4 | 5 |   ...   | 19 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.