company_banner

Знакомство с уровнями распараллеливания

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


    Распараллеливание на уровне задач

    image
    Часто распараллеливание на этом уровне является самым простым и при этом самым эффективным. Такое распараллеливание возможно в тех случаях, когда решаемая задача естественным образом состоит из независимых подзадач, каждую из которых можно решить отдельно. Хорошим примером может быть сжатие аудио-альбома. Каждая запись может обрабатываться отдельно, так как она никак не связана с другими.

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

    Другими примерами распараллеливания на этом уровне абстракции является параллельная компиляция файлов в Visual Studio 2008, обработка данных в пакетных режимах.

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

    Уровень параллелизма данных

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

    Хотя геометрический параллелизм может показаться похожим на распараллеливание на уровне задач, он является более сложным в реализации. В случае задач моделирования необходимо передавать данные получаемые на границах геометрических областей другим ядрам. Часто используются специальные методы повышения скорости расчета, за счет балансировки нагрузки между вычислительными узлами.
    image
    В ряде алгоритмов скорость вычисления, где активно протекают процессы, занимает больше времени, чем там, где среда спокойна. Как показано на рисунке, разбив счетную область на неравные части можно получить более равномерную загрузку ядер. Ядра 1, 2, и 3 обрабатывают маленькие области, где движется тело, а ядро 4 обрабатывает большую область, которая еще не подверглось возмущению. Все это требует дополнительного анализа и создания алгоритма балансировки.

    Наградой за такое усложнение является возможность решать задачи длительного движения объектов за приемлемое время расчета. Примером может служить старт ракеты.
    image

    Уровень распараллеливания алгоритмов

    Следующий уровень, это распараллеливание отдельных процедур и алгоритмов. Сюда можно отнести алгоритмы параллельной сортировки, умножение матриц, решение системы линейных уравнений. На этом уровне абстракций удобно использовать такую технологию параллельного программирования, как OpenMP.
    image
    OpenMP (Open Multi-Processing) — это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах. В OpenMP используется модель параллельного выполнения «ветвление-слияние». Программа OpenMP начинается как единственный поток выполнения, называемый начальным потоком. Когда поток встречает параллельную конструкцию, он создает новую группу потоков, состоящую из себя и некоторого числа дополнительных потоков, и становится главным в новой группе. Все члены новой группы (включая главный поток) выполняют код внутри параллельной конструкции. В конце параллельной конструкции имеется неявный барьер. После параллельной конструкции выполнение пользовательского кода продолжает только главный поток. В параллельный регион могут быть вложены другие параллельные регионы.

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

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

    Параллелизм на уровне инструкций

    Наиболее низкий уровень параллелизма, осуществляемый на уровне параллельной обработки процессором нескольких инструкций. На этом же уровне находится пакетная обработка нескольких элементов данных одной командой процессора. Речь идет о технологиях MMX, SSE, SSE2 и так далее. Этот вид параллельности иногда выделяют в еще более глубокий уровень распараллеливания – параллелизм на уровне битов.

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

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

    Вместо заключения

    Этот текст не претендует на полноту рассказа об уровнях параллельности, а просто показывает многогранность вопроса использования многоядерных систем. Для тех, кто интересуется разработкой программ, хочу предложить несколько ссылок на ресурсы, посвященные вопросам параллельного программирования:
    1. Сообщество разработчиков программного обеспечения. Я не сотрудник Intel, но очень рекомендую этот ресурс как член этого сообщества. Очень много интересных статей, записей в блогах и обсуждений, касающихся параллельного программирования.
    2. Обзоры статей по параллельному программированию с использованием технологии OpenMP.
    3. http://www.parallel.ru/ Все о мире суперкомпьютеров и параллельных вычислений. Академическое сообщество. Технологии, конференции, дискуссионный клуб (форум) по параллельным вычислениям.
    Intel
    186,00
    Компания
    Поделиться публикацией

    Комментарии 26

      0
      Сюда ещё можно ещё добавить облачные вычисления, которые все более и более популярны,
      и задачи — которые они позволяют решать.

      Распараллеливание не сводится к расчету турбулентных завихрений — есть как и более абстрактные задачи (проект S.E.T.I.), так и просчет рендеринга сложной сцены на группе машин.

      И просчет с помощью шейдеров видео-карт (CUDA например).
        0
        да, забыл ссылку ru.wikipedia.org/wiki/MISD — тоже про уровни — раздение по высислительному процессу, по данным, и отдельно — оба вместе.
          +1
          Все технологии связанные с параллельной обработкой в 1 статью не запихнешь.(в мфти неделя с занятиями по 10-12 часов в день 2 группы было. я после еще месяц допонимал многое с тех курсов. в ННГУ на школе по параллельным вычислениям был недельный курс по 7 различным направлениям. одно перечисление тем это на пару статей выйдет)

          Облачный вычисления это в зависимости от типа и реализации это по большому счете: Распараллеливание на уровне задач и Уровень параллелизма данных.
          Тем более что, статья называется «Знакомство с уровнями распараллеливания» а не полный курс по паралельным вычислениям.
          А свою тематику статья выдерживает полностью! Автору спасибо за труд!
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            CUDA не использует шейдеры. Она производит вычисления на тех же ядрах графпроцессора, но не имеет издержек, связанных с шейдерами.

            Например, vertex shader всегда получает координаты вершины.

            Будьте осторожнее с терминологией, пожалуйста.
            0
            Ускорение при параллельных вычислениях во многом еще зависят от эффективности распределении нагрузки на ядра/процессоры (масштабируемости вычислений). И в целом, зависимость ускорения от количество ядер/процессоров не линейка, а скорей 2^n, где n — количество процессоров. Также стоит упомянуть об эффекте «затухания», который наблюдается при большом количестве вычислительных ядер.
              +1
              Можешь привеcти хоть 1 пример задачи с зависимостью 2^n? Естественно, при оптимальном написании 1-поточной версии. По-моему, более чем линейного прироста получить невозможно.
                +1
                Более чем линейный прирост возможен (www.google.ru/search?q="парадокс параллелизма"), но это ДАЛЕКО не 2^n. И то, достигается он при определённых условиях (особые классы задач; «эффект памяти», который будет заметен лишь на многотысячепроцессорных ВС, а не на 4-х ядерных процессорах)
                  0
                  В приведенных Вами ссылках ни о каком асимптотическом ускорении речи не идет (зависимость все равно линейная, просто коеффициент больше единицы). Тем не менее за информацию спасибо, примеры интересные…
                    0
                    Ну да, я про коэффициент ускорения, а не асимптотику :). Именно его обычно имеют в виду, когда говорят о сверхлинейном росте производительности.
                      0
                      Вот тут, кстати, тоже про это упомянуто: закон Амдаля.

                      Если приложение имеет ускорение, превосходящее P (что в нашей модели невозможно из-за рабочих ограничений, но может существовать в моделях, учитывающих кэширование и другие функции процессора), то мы будем говорить, что приложение имеет суперлинейное ускорение.
                    0
                    Очень интересно. Не припомните, где вы об этом прочли?
                      +1
                      Мне не трудно припомнить, у меня через пару дней экзамен по этому. Прочитать об этом можно у Хорошевского В. Г. «Архитектура вычислительных систем» — этот человек более 40 лет занимается разработкой ВС, руководит ислледованиями в этой области в Институте математики им. С. Л. Соболева СО РАН.
                    0
                    Да, наверное я сильно погорячился насчет 2^n. Просто видел график — результаты решения реальных задачах на кластере, так вот та часть графика до выполаживания кривой ускорения наиболее точно описывалась зависимостью 2^n.
                    +1
                    Согласен. Распределение нагрузки весьма важная задача. В одном из следующих постов я затрону данную тематику. Также еще можно вспомнить про закон Амдаля. А вот откуда взялось 2^n вообще не понятно… :)
                    +1
                    Распараллеливание с помощью инструкций SSE активно применяется при низкоуровневых оптимизациях. В некоторых удобных случаях удавалось достичь более чем десятикратного ускорения (правда за счет снижения точности результата) в задачах с векторами, матрицами, кватернионами и тп. Компилятору это обычно не под силу (Intel C++ compiler мы не проверяли, но я сильно сомневаюсь что ситуация сильно изменится...)
                      0
                      Это весьма интересный и редкий опыт. Можете рассказать поподробнее? Если хотите, мы можем пообщаться по почте на тему написания совместной статьи. Или можете кратко рассказать здесь. Об SSE всем часто приходится слышать, но вот о практическом использовании почти ничего нет.
                        +1
                        Задача была довольно специфическая, вектора длины 4, матрица 4х4, кватернионы. Точность не критична (GameDev). SSE (или SSE1) хорошо подходит для таких задач — одной операцией обрабатываем сразу все компоненты вектора. Писали на SSE интринсиках (обертка над SSE функциями).
                        Из практических советов могу сказать, что
                        1) между вызовами SSE функций не должно быть обычных x86 конструкций (даже if и подобные), это приводит к падению производительности. Чем дольше наш вектор хранится в SSE регистре, тем лучше.
                        2) часто для достижения большей производительности выгодно писать функции, обрабатывающие сразу по 4 вектора, или делающие по 4 операции над 1 вектором.
                        3) в SSE есть операции для аппроксимации вычисления обратного числа и обратного корня. Они работают значительно быстрее, но с пониженной точностью. С ними нужно обращаться предельно аккуратно.
                          0
                          Были эксперименты сравнения алгоритмов на Си++ с их реализацией на SSE в плане производительности? Сохранились ли какие-то числовые результаты?
                            +1
                            Конечно, каждая функция сравнивалась с базовой имплементацией на С++. К сожалению, конкретных цифр у меня не осталось, а провести эксперименты сейчас не представляется возможным (я там больше не работаю).
                            По памяти могу сказать, что ускорение было от 2-х до ~15-ти раз (обычно ~2-4 раза). Медленнее работало все, что на входе или выходе имело скалярные величины.
                            Для PS3 и XBox360 (процессор PowerPC, расширение VMX) цифры были аналогичными.
                        0
                        Компилятор Интел тоже видимо не знает о математических оптимизациях. Пока я не видел ни одного компилятора, который способен a*b+a*c преобразовать в (a+b)*c. В мейнстримовых компиляторах возможности добавить что-то в этом роде вообще-то и нет, поскольку у этих двух вариантов разная точность вычислений и результат может быть совсем не таким, как ожидал пользователь.
                          0
                          Наверное, имелось в виду (b + c) * a. Но вы сами ответили, почему выражение не оптимизируется подобным образом. Эти выражения не эквиваленты и результат их вычисления различен. Более того, в языке Си++ часто A+B != A-(-B). :)
                            0
                            Это ничего не значит. Мы можем найти такие случаи, когда это можно сделать. А для компилятора все равно какие абстракции представляет C++ — он работает уровнем ниже.

                            А еще Вы не упомянули о вот такой вот вещи en.wikipedia.org/wiki/Simultaneous_multithreading
                              0
                              Относительно того что по ссылке. Или я, или автор не совсем понимает проблемы. Если b — dword. То компилятор его автоматически преобразует в qword в данном случае. gcc, по крайней, мере так делает.
                                +1
                                Автор — Я. Так что можно обсудить. :)
                                А проблема простая. Программы, которые содержали (некорректный) код вида:
                                unsigned Index = -1;  
                                Array[Index] = Z;
                                работали в 32-битном режиме и перестают работать в 64-битном. Простой перекомпиляции недостаточно. Необходимо еще выявить ошибки.
                          +3
                          Для параллельных вычислений нужен отдельный блог. И статьи в виде лекций, знакомящие людей с основами (таких статей только с 10 наберется, и это только основы я повторюсь)

                          Только вот вычитали семестр лекций в ДНУ на 4-м курсе. При всем желании и умении лектора и заинтересованности отдельных студентов смогли осилить только 3\4 курса.

                          Это очень интересная тема, спасибо

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

                          Самое читаемое