Многоядерные процессы и программирование

Идея «честного» распараллеливания еще проще. Пример про обработку видео я уже приводил. Суть же проста: мы разбиваем задачу на количество подзадач равное числу ядер процесса. Опять же оговорюсь, что это "идеальное" распараллеливание, и разбиение в большей степени относится к обрабатываемым данным, нежели самим алгоритмам. Такое распараллеливание можно применить к обработке изображений, видео или звука, когда на каждом из ядер дублируется алгоритм обработки, но занимается он только своей, определённой частью данных.

 

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

• специализация (применение внутри процессоров блоков, оптимизированных под определенный вид вычислений, например математических сопроцессоров);
• кэширование;
• спекулятивные вычисления.

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

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

1. Алгоритм должен допускать распараллеливание.
2. При вычленении параллельных участков, как правило, приходится придавать алгоритму специальную форму. Компактно записать параллельный вариант не всегда является возможным. В общем случае приведение алгоритма к форме, позволяющей сократить время вычислений, означает отход от формы, обеспечивающей наиболее наглядное представление, так называемую «читаемость» кода.
3. В многопроцессорной системе разбиение на слишком крупные части не позволяет равномерно загрузить процессоры и добиться минимального времени вычислений. То есть возможна проблема с неравномерным разбиением, в таком случае процессор, чья задаче была меньше, будет простаивать, и общее время выполнения алгоритма будет отсчитываться по завершении расчётов самым загруженным процессором. А излишне мелкая «нарезка» означает рост непроизводительных расходов на связь и синхронизацию.
4. Физическому параллелизму присуща зависимость глобальной структуры алгоритма от топологии вычислительной платформы. Процесс создания максимально эффективного алгоритма практически не автоматизируется и связан с большими трудозатратами на поиск специфической структуры алгоритма, оптимальной для конкретной топологии целевой системы. Найденная структура обеспечит минимальное время получения результата, но, скорее всего, будет неэффективна для другой конфигурации. Более суровое следствие зависимости структуры алгоритма от вычислительной платформы — тотальная непереносимость не только исполняемых кодов, но и самого исходного текста.

Данная зависимость легко демонстрируется на классическом примере сортировки. При O (N) сравнениях, необходимых для сортировки массива из N элементов, стоимость параллельных алгоритмов сортировок равна O (N2). В то же время быстрые последовательные алгоритмы сортировок обеспечивают стоимость O (N log N). Таким образом, чтобы отсортировать массив из 1 тыс. чисел на десяти вычислителях, надо разбить его на десять частей, отсортировать их с помощью эффективного последовательного алгоритма, а затем параллельно слить эти части в общий список (стоимость параллельного слияния — O (N)).

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

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

Преимущества «мелкозернистого» логического параллелизма

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

«Мелкозернистый» логический параллелизм эффективен в задачах управления сложным промышленным оборудованием. Необходимость отражения параллелизма процессов, осуществляемых на объекте управления, требует создания по меньшей мере сотни параллельно исполняемых процессов. Например, эквивалентное монолитное решение в виде одного процесса, предназначенное для управления выращиванием монокристаллического кремния, приводит к рассмотрению 1030 различных ситуаций. Сжатие информации достигается при логическом параллелизме за счет упрощенного описания комбинаций независимых случаев: описание алгоритма как набора независимых частей — это описание суммы ситуаций, а монолитное описание — это описание произведения ситуаций. Невообразимое число ситуаций (1030) можно получить лишь из сотни параллельно исполняемых компонентов с двумя состояниями, в то время как независимое описание алгоритма подразумевает рассмотрение всего 200 уникальных случаев. 
 Логический параллелизм на уровне операционных систем является многозадачным; при этом имеется выделенная задача (планировщик), которая занимается переключением процессора с одной задачи на другую. Алгоритмы переключений могут быть как примитивными, так и весьма сложными. Самый простой — алгоритм разделения по времени. Планировщик работает с очередью задач и активизируется по прерываниям от таймера с некоторым заданным периодом. После активизации он сохраняет контекст текущей задачи, ставит ее в конец очереди, восстанавливает контекст следующей задачи из очереди и запускает ее на исполнение.

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

Логический и физический параллелизм

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

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

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

 

 

 

 

 

 

 

 

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

1. Расчёт увеличения производительности за счет распараллеливания процессов.

 

Для расчета увеличения производительности используют закон Амдала. Закон Амдала гласит, что прирост производительности (S) системы зависит от количества процессоров (N) и доли последовательных операций (c) в программе:

S≤1/(с+(1-с)/N).

Граничные значения (c) соответствуют полностью параллельным (c=0) и полностью последовательным (c=1) программам. Если лишь 1/10 часть программы выполняется последовательно, то в принципе невозможно ускорение в десять раз вне зависимости от числа используемых процессоров (ядер). Важное следствие закона Амдала состоит в том, что максимальный рост производительности (в N раз при N процессорах) недостижим. В противном случае последовательно исполняемая часть программы должна быть равна нулю, что невозможно. Еще одно следствие закона таково: чем меньше доля последовательно исполняемой части программы, тем больше прирост производительности.

Сегодня только небольшая часть программного обеспечения может выполняться на многоядерных процессорах, что подтверждают результаты тестов синтетических и предназначенных для конкретных классов приложений. Реальный рост производительности дают лишь программы, оптимизированные под много поточность, такие как Adobe Premiere Pro 1.5 и 3DMax. Очень важны разработка и внедрение драйверов устройств, поддерживающих многопоточность. При переходе с одноядерных процессоров на многоядерные приходится принимать во внимание проблему последовательного выполнения.

 

 

 

 

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

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

Блокировки возникают из-за невозможности одновременного доступа приложений на разных ядрах к жесткому диску, к устройствам ввода/вывода или данным приложений. Очень часто параллельные процессы, выполняемые на разных ядрах, нужно синхронизировать в определенные моменты. Например, приложение на одном из ядер должно использовать промежуточные данные, которые получает приложение на другом ядре. Первое приложение не может продолжить работу до получения этих данных, то есть находится в состоянии ожидания. В такой ситуации неизбежны накладные расходы на синхронизацию приложений, выполняемых на разных ядрах. В свою очередь, это обусловливает снижение эффективности параллельной работы, что находит отражение в сетевом законе Амдала. Возникает необходимость в поддержке согласованности кэш-памяти для всех ядер при использовании разделяемой памяти.

Можно упомянуть об исследованиях Intel, посвященных динамическому регулированию интенсивности выполнения инструкций (energy per instruction, EPI) в зависимости от степени параллелизма реализации программного обеспечения. Специалисты корпорации опытным путем показали эффективность регулирования тактовой частоты асимметричной многопроцессорной системы в зависимости от активности вычислительных ядер.

 

 

 

 

 

 

 

 

3. Инструментальные средства многоядерных систем

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

Компиляторы

Чтобы получить максимальную выгоду от использования многоядерной архитектуры требуется поддержка на уровне компилятора. Так, в 2005 году Intel выпустила версию 9.0 компилятора языков C++ и Фортран для платформ Linux и Windows. Этот компилятор позволяет эффективно использовать возможности технологии Hyper-Threading и многоядерных процессоров. Он поддерживает возможность автопараллелизма, то есть автоматического обнаружения в приложениях возможности создания множества параллельных потоков с поддержкой спецификации OpenMP 2.5.

Благодаря поддержке стандарта OpenMP компилятор Microsoft Visual C++ 2005 обеспечивает параллельную многопоточную обработку. Следует упомянуть и набор компиляторов EKOPath компании PathScale, предназначенных для 64-разрядных систем на базе Linux (AMD64 и EM64T).

Программные отладчики

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

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