Увеличение производительности ЭВМ, за счет чего?

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

Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира - EDSAC, появившемся в 1949 году в Кембридже и имевшем время такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*n арифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметических операций в секунду. Сравним с одним вычислительным узлом современного суперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды (1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметических операций в секунду.

Что же получается? За полвека производительность компьютеров выросла более, чем в семьсот миллионов раз. При этом выигрыш в быстродействии, связанный с уменьшением времени такта с 2 микросекунд до 1.8 наносекунд, составляет лишь около 1000 раз. Откуда же взялось остальное? Ответ очевиден -- использование новых решений в архитектуре компьютеров. Основное место среди них занимает принцип параллельной обработки данных, воплощающий идею одновременного (параллельного) выполнения нескольких действий.

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

Параллельная обработка . Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут - принцип параллельности в действии!

Кстати, пионером в параллельной обработке потоков данных был академик А.А.Самарский, выполнявший в начале 50-х годов расчеты, необходимые для моделирования ядерных взрывов. Самарский решил эту задачу, посадив несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была расчитана эволюция взрывной волны. Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал. Это, можно сказать, и была первая параллельная система. Хотя расчеты водородной бомбы были мастерски проведены, точность их была очень низкая, потому что узлов в используемой сетке было мало, а время счета получалось слишком большим.

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

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то действуя по аналогии с предыдущим примером надо набрать тысячу бригад, каждая из которых (1) в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и (2) сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка...

4 курс, 1 и 2 потоки, 7-й семестр

лекции (34 часа), зачет

Кафедра, отвечающая за курс : АСВК

Составитель программы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.,

Лекторы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.

Аннотация

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

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

Программа

1. Большие задачи и суперкомпьютеры. Параллельная и конвейерная обработка данных. Параллелизм и конвейерность в архитектуре современных высокопроизводительных компьютеров. Скалярные и векторные команды. Скалярные, конвейерные и векторные устройства. Иерархия памяти в компьютерах как средство повышения скорости выполнения программ, локальность вычислений и локальность использования данных. Закон Амдала и его следствия, суперлинейное ускорение.

2. Основные классы современных параллельных вычислительных систем. Компьютеры с общей памятью, примеры, причины снижения производительности на реальных программах. Архитектуры SMP, NUMA, ccNUMA. Коммутация процессоров и модулей памяти, шина, матричный коммутатор, омега-сеть. Векторно-конвейерные вычислительные системы, примеры, причины снижения производительности. Компьютеры с распределенной памятью, примеры, причины снижения производительности. Топология связи между процессорами: звезда, решетка, трехмерный тор, двоичный гиперкуб, их свойства. Вычислительные кластеры, примеры, латентность и пропускная способность различных коммуникационных технологий. Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность.

3. Технологии параллельного программирования. Традиционные последовательные языки и распараллеливающие компиляторы, проблемы. Спецкомментарии и директивы компилятору, расширения существующих языков. Специальные языки параллельного программирования. Программирование с использованием библиотек и интерфейсов передачи сообщений. Параллельные предметные библиотеки, специализированные пакеты и программные комплексы высокого уровня. Технологии параллельного программирования MPI, OpenMP, Linda.

4. Производительность параллельных вычислительных систем. Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM и NPB.

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

6. Неоднородные распределенные вычислительные системы. Метакомпьютеры и метакомпьютинг, существующие метакомпьютерные проекты. Отличительные свойства метакомпьютеров. Понятие GRID, базовые компоненты и сервисы, существующие проекты GRID-сегментов, понятие виртуальной организации.

Литература

1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ Петербург, 2002. - 608 с.

2. Королев Л.Н. Архитектура процессоров электронных вычислительных машин. – М.: Изд. факультета ВМК МГУ, 2003.

3. В.В.Корнеев. Параллельные вычислительные системы. – М.: Изд-во "Нолидж", 1999. – 320с.

4. Материалы информационно-аналитического центра по параллельным вычислениям Parallel.ru.

Дополнительная литература

1. Антонов А.С. Параллельное программирование с использованием технологии

MPI: Учебное пособие. – М.: Изд-во МГУ, 2004. - 71 с.

Сообщения

• Параллельная и конвейерная обработка

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

  Параллельная обработка

  При выполнении устройством одной операции за единицу времени, можно сказать, что тысячу операций устройство выполнит за тысячу единиц. Если предположить, что есть пять независимых устройств, работающих одновременно, то ту же тысячу операций такая система устройств может выполнить уже за двести единиц времени. По аналогии система из N устройств ту же работу выполнит за 1000/N единиц времени. К реальной жизни это также применимо, например:

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

  Самарский А.А., выполнявший в начале 50-х годов расчеты для моделирования ядерных взрывов был пионером в параллельной обработке потоков данных. Самарский интересным способом рассчитал эволюцию взрывной волны — он посадил несколько десятков человек с арифмометрами за столы, заставив их передавать данные друг другу просто на словах и откладывать необходимые цифры на арифмометрах. Можно сказать, что это
  и была первая параллельная система. Не смотря на то, что расчеты водородной бомбы были мастерски проведены, их точность была довольно низка, потому что используемая сетка имела мало узлов, а время счета было слишком большим.

  Конвейерная обработка

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

  Суть конвейерной обработки состоит в выделении отдельных этапов выполнения общей операции. Каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию данных. Совмещение прежде разрозненных во времени операций определенно положительно влияет на скорость обработки. Например, в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени.
  Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обрабатывает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находиться первые пять пар аргументов, а весь набор из ста пар будет обработан за 104 (5+99) единицы времени — ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

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

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

  Современные параллельные системы

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

  Векторно-конвейерные компьютеры

  Особенности таких машин заключаются в наборе векторных команд и конвейерных функциональных устройствах. В отличие от традиционного подхода, векторные команды способны оперировать целыми массивами независимых данных, а значит появляется возможность эффективно загружать доступные конвейеры, т.е. команда вида А=В+С может означать не сложение двух чисел, а двух массивов. Характерный представитель данного направления — семейство векторно-конвейерных компьютеров CRAY.

  Массивно-параллельные компьютеры с распределенной памятью.

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

  Однако, существует значительный минус, превосходящий многие плюсы. В данных компьютерах межпроцессорное взаимодействие идет намного медленнее, чем происходит локальная обработка данных самими процессорами. В связи с этим, очень сложно написать эффективную программу для таких компьютеров, для некоторых алгоритмов иногда просто невозможно. Примеры таких компьютеров: Intel Paragon, IBM SP1, Parsytec, в некоторой степени IBM SP2 и CRAY T3D/T3E, хотя влияние указанного минуса в этих компьютерах значительно меньше. Сети компьютеров, которые все чаще рассматривают как достаточно дешевую альтернативу крайне дорогим компьютерам, так же можно отнести к этому же классу.

  Параллельные компьютеры с общей памятью

  Вся оперативная память данных компьютеров разделяется несколькими одинаковыми процессорами. Проблемы предыдущего класса решены, но добавились новые — нельзя по технически причинам сделать большим число процессоров, которые имели бы доступ к общей памяти. Примерами данного направления многие многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar и Sun StarFire.

  Комбинированные системы

  Последнее направление скорее не самостоятельное, а просто комбинация предыдущих трех. Сформируем вычислительный узел из нескольких процессоров (традиционных или векторно-конвейерных) и общей для них памяти. При нехватке вычислительной мощности, можно объединить несколько узлов высокоскоростными каналами. Подобная архитектура называется кластерной. По данному принципу построены Sun StarFire, NEC SX-5, CRAY SV1, HP Exemplar, последние модели IBM SP2 и другие.

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

  Уровни параллелизма

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

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

  Уровень потоков . Задачи разбиваются на части, которые могут выполняться параллельно (потоки). Данный уровень достигается на параллельных ВС.

  Уровень команд . Несколько команд выполняются параллельно, в процессоре размещаются сразу несколько конвейеров. Характерен для суперскалярных процессоров.

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

  Понятие уровня параллелизма тесно связано с понятием гранулярности. Гранулярность — мера отношения объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Степень гранулярности варьируется от мелкозернистой до крупнозернистой. Закон Амдала ориентирован на крупнозернистый
  параллелизм.

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

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

  Литература

  1. Баденко В.Л. Высокопроизводительные вычисления. Учебное пособие. - СПб.: Изд-во Политехн. ун-та, 2010. — 180 с.
  2. Барский А.Б. Параллельные информационные технологии: Учебное пособие/А.Б. Барский.-М.: Интернет-университет информационных технологий; БИНОМ. Лаборатория знаний, 2007.-503 с.: ил.,таб.-(серия «Основы информационных технологий»)- с.20-28, с.56-58.
  3. Корнеев В.В. Вычислительные системы.-М.:Гелиос APB, 2004.-512с., ил.- с. 34-46
  4. Лацис А.О. Параллельная обработка данных. М.: Академия, 2010. - 336 с.
  5. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. Учебник для вузов. - СПб.: Питер, 2004. - 668 с.

Сообщения

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

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

2. Обеспечение высокой надежности ВС за счет дублирования вычислительной аппаратуры.

Рис. 5.1. Уровни параллелизма

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

Параллельная обработка информации может производиться на нескольких уровнях (рис. 5.1).

Очевидно, что чем ниже уровень, тем мельче дробление программных процессов, тем мельче, как принято говорить, «зерно параллелизма ». В общем случае возможно реализовать параллелизм как на отдельном уровне, так и на нескольких одновременно. Независимая однопроцессорная обработка реализует параллелизм на уровне 1. Векторная обработка заключается в параллельном выполнении циклов на уровне 2 и может производиться как на одном, так и нескольких процессорах. Уровни 3 и 4 соответствуют многопроцессорным ВС. Параллелизм уровня 5 характерен для многомашинных вычислительных комплексов.

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

· совмещение во времени этапов решения разных задач;

· одновременное решение различных задач или частей одной задачи;

Первый путь - совмещение во времени этапов решения разных задач - это мультипрограммная обработка информации. Мультипрограммная обработка уже давно и широко применяется для повышения производительности ЭВМ и ВС. Подробное рассмотрение мультипрограммной обработки относится к теме «Операционные системы» и выходит за рамки настоящего учебника.

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

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

1. Естественный параллелизм независимых задач.

2. Параллелизм объектов или данных.

3. Параллелизм ветвей задачи или программы.

Рассмотрим эти типы параллелизма.

1. Естественный параллелизм независимых задач зак­лючается в том, что на вход ВС поступает непрерывный поток не связанных между собой задач, т.е. решение лю­бой задачи не зависит от результатов решения других за­дач. В этом случае использование нескольких обрабатыва­ющих устройств при любом способе комплексирования (объ­единения в систему) повышает производительность систе­мы.

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

2. Параллелизм объектов или данных имеет место тогда, когда по одной и той же (или почти по одной и той же) программе должна обрабатываться некоторая сово­купность данных, поступающих в систему одновременно.

Это могут быть, например, задачи обработки сигна­лов от радиолокационной станции: все сигналы обрабаты­ваются по одной и той же программе. Другой пример - об­работка информации от датчиков, измеряющих одновременно один и тот же параметр и установленных на нескольких однотипных объектах.

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

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

· ни одна из выходных вели­чин этих ветвей задачи не является входной величиной для другой такой ветви (отсутствие функциональных связей);

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

Хорошее представление о параллелизме ветвей дает ярусно-параллельная форма(ЯПФ) програм­мы, пример которой приведен на рис. 5.2.

Программа представлена в виде совокупности ветвей, расположенных на нескольких уровнях - ярусах. Кружками с цифрами внут­ри обозначены ветви. Длина ветви представляется цифрой, стоящей около кружка и говорящей, сколько временных единиц выполняется данная ветвь. Стрелками показаны входные данные и результаты обработки. Входные данные обозначаются символом X, выходные данные - символом Y. Символы Х имеют нижние цифровые индексы, обозначающие номера входных величин; символы Y имеют цифровые индек­сы и внизу, и вверху; цифра вверху соответствует номеру ветви, при выполнении которой получен данный результат, а цифра внизу означает порядковый номер результата, по­лученного при реализации данной ветви программы. На одном ярусе размещаются независимые ветви задачи, не связанные друг с другом, т.е. результаты решения ка­кой-либо ветви данного яруса не являются входными дан­ными для другой ветви этого же яруса.

Рис. 5.2. Пример ярусно-параллельной формы программы

Изображенная на рис. 5.2 программа содержит 9 вет­вей, расположенных на 3 ярусах. На примере этой, в общем, достаточно простой прог­раммы, можно выявить преимущества вычислительной систе­мы, включающей несколько обрабатывающих устройств, и проблемы, которые при этом возникают.

Примем, что длина i -й ветви представляется числом временных единиц t i , которые требуются для ее исполнения. Тогда нетрудно подсчитать, что для исполнения всей программы на 1 процессоре потребуется время T 1 :

T 1 =S (10+20+15+30+55+10+15+25+15)=195

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

Рассмотрим, например, такой вариант выполнения программы, представленной на рис. 5.2. Пусть процессор 1 выполняет ветви 1-3-4-6-7-9, а процессор 2 выпол­няет ветви 2-5-8. На рис. 5.3 представлены временные диаграммы выполнения процессорами ветвей программы.

Рис. 5.3. Разложение ветвей программы по 2 процессорам

Нетрудно подсчитать, что процессор 1 затрачивает 105, а процессор 2 - 100 единиц времени. При этом имеется два промежутка времени, когда один из процессоров вынужденно простаивает – П1 длительностью 10 единиц и П2 длительностью 5 единиц времени. Промежуток П1, во время которого работает только процессор 2, образовался из-за того, что ветвь 7 зависит от ветви 5 (к моменту завершения ветви 6 еще не готовы данные Y 5 1). Промежуток П1, во время которого работает только процессор 1, образовался по причине окончания счета процессором 2.

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

Коэффициент распараллеливанияизменяется от 0 до 1 (от 0 до 100%) и отражает эффективность использования вычислительных ресурсов. В нашем примере нетрудно посчитать, что ускорение S = 195/105 = 1,86, а коэффициент распараллеливания K п = 0,93. Как видим, по причине простоев одного из процессоров ускорение счета значительно меньше 2, т.е. количества используемых процессоров. Заметим, что в нашем примере не учитывались временные задержки, связанные с переключением контекстов программы (смены ветвей) и передачи данных от одной ветви к другой. Тем не менее, в силу алгоритмических особенностей программы, часть вычислений в промежутки П1 и П2 производится только одним процессором, т.е. фактически последовательно.

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

Данное соотношение носит название закона Амдала . На примере программы рис. 5.2 мы можем видеть, что доля последовательных вычислений составляет f = 15/195. Подставляя эту величину в формулу закона Амдала, получаем для системы из двух процессоров максимальное ускорение 1,86 раза, что соответствует ранее рассчитанному значению.

Для иллюстрации действия закона Амдала приведем следующий пример. Пусть доля последовательных вычислений в некоторой программе составляет 10%. Тогда максимальное ускорение счета на 100 процессорах не превысит 9,2. Коэффициент распараллеливания составит всего лишь 9,2%. На 10 процессорах ускорение составит 5,3, а коэффициент распараллеливания ‑ 53%. Нетрудно видеть, что даже такая небольшая доля последовательных вычислений уже на теоретическом уровне, без учета неизбежных задержек в реальной ВС, серьезно ограничивает возможности масштабирования программы.

Определим, какая должна быть максимальная доля f последовательных вычислений в программе, чтобы было возможно получить наперед заданное ускорение счета S с максимальным коэффициентом распараллеливания K п . Для этого выразим из закона Амдала долю последовательных вычислений:

Соотношение (5.6) определяет очень важное следствие из закона Амдала. Для того, чтобы ускорить программу в q раз, необходимо ускорить не менее, чем в q раз не менее, чем () -ю часть программы . Например, чтобы получить ускорение в 100 раз, необходимо распараллелить 99,99% всей программы.

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

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

Параллельная обработка данных

Информатика, кибернетика и программирование

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

Лекция 1

Параллельная обработка данных

План

1. Ярусно-параллельная форма алгоритма.

2. Автоматическое обнаружение параллелизма.

3. Степень и уровни параллелизма.

4. Виды параллелизма.

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

Производительность параллельных ВС зависит от многих факторов и в значительной степени от архитектуры и структуры системы (рисовать структуру параллельной системы и объяснять):

От степени и уровня параллелизма в системе;

От организации передачи данных между параллельно работающими процессорами;

От системы коммутации;

От взаимодействия процессоров и памяти;

От соотношения между аппаратной и программной реализацией макрооперации.

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

Пространственный параллелизм;

Временной параллелизм:

1. Конвейеризация.
2. Векторизация.
3. Матричный.
4. Систолический.
5. Организация структуры обработки потока данных.
6. Организация системы на основе структуры гиперкуб.
7. Динамическая перестройка структуры ВС.

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

1. Ярусно-параллельная форма алгоритма

Наиболее общей формой представления алгоритмов является информационно-управляющий граф алгоритма, который отражает зависимость по данным между операторами алгоритма и безусловные и условные переходы в программе. Такой граф в неявной форме содержит все виды параллелизма для выбранного метода решения задачи. Более определенной формой представления параллелизма задач является аппарат ярусно-параллельной формы (ЯПФ).

Алгоритм в ярусно-параллельной форме представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви) независящие друг от друга.

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

При построении ЯПФ опираются на базовый набор примитивных операций (БНО). Ярусно-параллельная форма характеризуется следующими параметрами :

1. Длина графа (количество ярусов) – L .

2. Ширина i -го яруса - b i .

3. Ширина графа ярусно-параллельной формы – B = max (b i ).

4. Средняя ширина графа ЯПФ – В ср – .

5. Коэффициент заполнения i -го яруса – k i – .

6. Коэффициент разброса операций в графе - Q j i – , j БНО , где - количество j -го типа операций в i -м ярусе.

7. Минимальное необходимое количество вычислителей (из БНО) для реализации алгоритма, представленного данным графом в ЯПФ.

8. Минимальное время решения алгоритма (сумма времен срабатывания вычислителей с максимальным объемом вычислений по каждому ярусу) – Т min .

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

2. Автоматическое обнаружение параллелизма

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

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

Характер изменения степени параллелизма при подготовке машинной программы показан на рис. 2.2.

потенциальный параллелизм

Метод

решения

Исходный текст

Машинная программа

Рис. 2.2. Изменение потенциального параллелизма при разработке программы:

1 – система параллельного программирования;

2 – последовательное программирование и

векторизующий компилятор

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

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

При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R и выходных (записываемых) переменных W каждого процесса.

Явная параллельная обработка может быть обнаружена среди процессов i и j (i ≠ j ), удовлетворяющих следующим условиям:

входные данные одного процесса не должны модифицироваться (записываться) другим процессом

никакие два процесса не должны модифицировать общие переменные

а) R i W j =;

б) W i R j =;

в) W i W j =;

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

а) уменьшение высоты деревьев арифметических выражений (рис.2.3). Для арифметических выражений с n переменными или константами уменьшение высоты дерева позволяет достигнуть ускорения обработки порядка O (n / log 2 n ) при использовании O (n ) процессоров;

б) преобразование линейных рекуррентных соотношений;

((a + b) + c) + d

(a + b)+ (c + d )

Рис. 2.3. Уменьшение высоты дерева

в) замена операторов;

г) преобразование блоков условных переходов и циклов к каноническому виду;

д) распределение циклов.

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

При преобразовании параллелизма программы учитывают: 1) схему размещения данных в памяти; 2) адресацию памяти (индексирование); 3) выбор маршрута данных (способ соединения процессоров и ЗУ).

Рис.2.4. Хранение

матрицы со сдвигом

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

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

3. Степень и уровни параллелизма

Степень параллелизма (D ) – это порядок числа параллельно работающих устройств в системе при реализации алгоритма задач, при условии, что количество процессоров (обрабатывающих устройств) не ограничено. (Есть иное определение степени параллелизма – это число процессоров многопроцессорной системы, параллельно участвующих в выполнении программы в каждый момент времени t.)

1) Низкая степень: от 2 до 10 процессоров.

2) Средняя степень: от 10 до 100 процессоров.

3) Высокая степень: от 100 до 10 4 процессоров.

4) Сверхвысокая степень: от 10 4 до 10 6 процессоров.

Рис. 2.5. Профиль параллелизма

Графическое представление параметра D (t ) как функции времени называют профилем параллелизма программы . Изменения в уровне загрузки процессоров за время наблюдения зависят от многих факторов (алгоритма, доступных ресурсов, степени оптимизации, обеспечиваемой компилятором и т.д.). На рис. 2.5 показан типичный профиль параллелизма.

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

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

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

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

1. Уровень заданий:

а) между заданиями;

б) между фазами заданий.

2. Программный уровень:

а) между частями программы (части одной задачи выполняются на множестве вычислителей);

б) в пределах циклов.

(Если отдельные итерации в цикле на зависят друг от друга. Например: For I:=1 to N do A(I):=B(I) + C(I))

3. Командный уровень:

а) между фазами выполнения команд.

4. Арифметический и разрядный уровень:

а) между элементами векторной операции;

б) внутри логических схем АЛУ.

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

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

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

1. На уровне логических вентилей и элементов памяти. Это низший уровень – уровень транзисторов. Здесь из логических вентилей строят параллельные логические схемы (ЛС ) (например: параллельный сумматор).

2. Уровень логических схем и простых автоматов с памятью. Из логических схем строят параллельный элементарный автомат (ЭА ).

3. Уровень регистров и интегральных схем памяти. На элементарных автоматах получают параллельные схемы микропроцессоров (МП ).

4. Уровень элементарных микропроцессоров. Из микропроцессоров строят параллельные макропроцессоры для выполнения среднеблочных операций (МАП ).

5 . Уровень макропроцессоров, реализующих крупные операции. Здесь реализуется параллелизм макроопераций. На макропроцессорах строят параллельные многопроцессорные системы (МПС ).

6. Уровень вычислительных машин, процессоров и программ. Высший уровень параллелизма – из многопроцессорных систем получают параллельные вычислительные системы (ВС ).

4. Виды параллелизма

4.1. Естественный параллелизм и

параллелизм множества объектов

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

Задача обладает естественным параллелизмом , если в её исходной постановке она сводится к операции над многомерными векторами, многомерными матрицами или над решётчатыми функциями (рис.2.6). Здесь не используются промежуточные результаты задач. Каждая задача программируется независимо от других. Этот вид параллелизма не требует объединения ЭВМ в комплексы. Однако увеличение числа независимых задач в СОД повышает пропускную способность системы. Например: обработка транзакций к БД на многопроцессорных серверах.

1 задача

2 задача

Рис. 2.6. Информационный граф задания, характеризующегося естественным параллелизмом

Орi

Орi

Орi

Орi

Орi+1

Орi+1

Орi+1

Орi+1

у 1

у 2

у 3

у 4

Рис. 2.7. Информационный граф

задачи, характеризующейся

параллелизмом множества объектов

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

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

включает два типа операций: попарное произведение компонент векторов и затем "интегральную операцию" (операция над n-мерным вектором) суммирование между собой всех компонент этого вектора.

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

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

Параллелизм множества объектов характеризуется следующими параметрами :

1. Суммарная длина программы L – суммируются длины всех операторов по всем ветвям.

2. Средняя длина программы L ср – вычисляется исходя из ранга задачи.

Основной количественной характеристикой распараллеливаемой задачи является ранг задачи r (®) это количество параметров, по которым должна вестись параллельная обработка (например, количество компонент вектора, количество точек, в которых задана функция).

3. Величина расхождения задачи D

Если программа обработки информации по всем r объектам в точности одинакова, то D =1 и чем сильнее между собой отличаются программы разных объектов, тем больше D .

4.2. Параллелизм независимых ветвей

Суть параллелизма независимых ветвей состоит в том, что в программе решения задачи могут быть выделены независимые части, называемые ветвями. При наличии в ВС соответствующих аппаратных средств ветви могут выполняться параллельно (рис.2.8).

Ветвь программы Y не зависит от ветви X , если:

Рис. 2.8. Информационный граф задачи, характеризующейся

параллелизмом независимых ветвей

между ними нет функциональных связей , т.е. ни одна из входных переменных ветви Y не является выходной переменной ветви X либо какой-нибудь ветви, зависящей от X;

1. между ними нет связи по рабочим полям памяти ;
2. они должны выполняться по разным программам ;
3. независимы по управлению , т.е. условие выполнения ветви Y не должно зависеть от признаков, вырабатываемых при выполнении ветви X или ветви, от нее зависящей.

4.3. Параллелизм смежных операций или

локальный параллелизм

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

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

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

2. Вероятность того, что, начиная от данной операции, имеется цепочка длиной не менее l l

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

4. Глубина параллелизма смежных операций L ПСО – это математическое ожидание длины цепочки операций, которые можно выполнять одновременно

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

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

________________________________________________________________________________________________

Курс «Организация ЭВМ»

10 -

(курсовой проект)

А также другие работы, которые могут Вас заинтересовать
54055.		Урочисте відкриття тижня Логіки	149.5 KB
	Учень. Відкрити тиждень логіки дозволяю Капітанів прошу представити команди і здати рапорти команди здають рапорти 1 учень. Увага Увага 2 учень. Доброго дня дорогі діти і гості 1 учень.
54056.		Інтегрування змісту навчальних предметів та логіки	120.5 KB
	Дітям необхідно знати правила і закони логіки у них мають бути сформовані логічні вміння розвинуте логічне мислення. Особливо виразно продуктивність застосування інтегрованого підходу можна побачити на уроках логіки. Знання учителя основних правил і законів логіки дає змогу користуватися логічними прийомами під час розвязування проблемних ситуацій з будь якої освітньої галузі; розвивати в учнів вміння застосовувати правила і закони логіки щодо аналізу подій явищ оцінки своїх і чужих думок формулювати і приймати обґрунтовані рішення під...
54057.		Межпредметная интеграция как средство активизации учебного процесса	135.5 KB
	В специализированных школах с углубленным изучением иностранного языка межпредметная интеграция должна занимать не последнее место. В этой связи совместные уроки математики и английского языка могут быть очень интересными.
54058.		АЛГЕБРА ВЫСКАЗЫВАНИЙ. ОСНОВНЫЕ ОПЕРАЦИИ АЛГЕБРЫ ВЫСКАЗЫВАНИЙ	1.77 MB
	Таблица истинности - это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.
54059.		Логика	81.18 KB
	Знаешь ли ты этого человека запутанного в плащ Нет. А между прочим это твой отец. Объект логики это то на что направлен интерес ученого в логике это мышление на человекомышление. Логика это наука не о всем мышлении а о правильном мышлении о правильном рациональном мышлении которое можно выразить в знаково символической форме словами.
54061.		Ліс. Дерева. Кущі. Ягоди. Розвиток зв’язного мовлення	40 KB
	Мета: Збагачувати словник дітей на основі знань, уявлень про довкілля. Учити перераховувати якості, властивості предметів, намагатись давати їм характеристику, формувати вміння найбільш точно застосовувати слова, що підходять до конкретної ситуації або опису.
54062.		Пригоди веселих кошенят	44.5 KB
	Під музичний супровід діти разом із логопедом заходять до музичної зали. Логопед: Доброго ранку доброго дня Хай плещуть долоньки Хай тупають ніжки Хай ротик співає Та сяють усмішки. Піпіпі куди це я потрапила Логопед.
54063.		Логопсихокорекція у роботі з дітьми з порушеннями мовлення	67.5 KB
	Ігри і вправи на розвиток емоційної сфери Казка-гра: Про рибака та рибку Логопед читає уривок з казки О. Гра із шишками напруження та розслаблення мязів рук. Гра з бджілкою напруження та розслаблення мязів ніг. Ведмедиця кличе золоту бджілку погратися з ведмежатами.