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

      Комментарии к записи Виды параллелизма отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #3873

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Литература

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

Для ответа в этой теме необходимо авторизоваться.