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

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

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

Первую из основных статей тематической подборки написали Скотт Шнейдер (Scott Schneider), Джей Сын Ем (Jae-Seung Yeom) и Димитриос Николопулос (Dimitrios Nikolopoulos), она называется «Программирование мультипроцессоров с явно управляемыми иерархиями памяти» (Programming Multiprocessors with Explicitly Managed Memory Hierarchies). Мультиядерные процессоры с явно управляемой иерархией памяти (explicitly managed memory, EMM) изначально использовались в машинной графике, а теперь выступают в качестве высокопроизводительных вычислительных платформ общего назначения. Во всех таких процессорах Intel и AMD в качестве ускорителей используются компоненты, параллельные по данным, а ускорение достигается за счет применения скалярных и SIMD-ядер, поддержки высокой пропускной способности внутри чипов и явной передачи данных между быстрой локальной памятью и внешней динамической памятью DRAM. Явная пересылка данных дает возможность программистам использовать оптимальные политики кэширования и организовывать несколько буферов потоковой передачи данных, позволяющих совмещать вычисления с выполнением операции передачи данных.

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

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

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

Статью «Cetus: инфраструктура компилятора из исходного текста в исходный текст для мультидарных процессоров» (Cetus: A Source-to-Source Compiler Infrastructure for Multicores) представили Чираг Дэйв (Chirag Dave), Хансанг Бэй (Hansang Bae), Сын Джей Мин (Seung-Jai Min), Сейонг Ли (Seyong Lee), Рудольф Эйгенман (Rudolf Eigenmann) и Сэмюел Мидкифф (Samuel Midkiff). С появлением многоядерных архитектур особо важную роль стала играть технология автоматического распараллеливания. В то время как классические параллельные машины представляли интерес для относительно небольшого сообщества пользователей, многоядерные процессоры нацелены на массовый рынок, для которого требуются ориентированные на пользователей высокопродуктивные средства программирования. Кроме того, многоядерные процессоры заменяют сложные суперскалярные процессоры, параллелизм которых несомненно учитывался компиляторами. Аналогичная модель желательна и для нового поколения процессоров.

В представленном авторами описании современного состояния средств автоматического распараллеливания программ для многоядерных процессоров используется инструмент Cetus – инфраструктура для исследования оптимизаций времени компиляции. Эта инфраструктура поддерживает преобразования на уровне исходного текста, ориентирована на пользователей, проста в применении и опирается на наиболее важные методы параллелизации. Инфраструктурный проект Cetus является преемником проекта Polaris (polaris.cs.uiuc.edu/polaris/polaris-old.html), в котором была разработана развитая инфраструктура оптимизирующих компиляторов параллельных машин. В то время как инфраструктура Polaris была ориентирована на язык Фортран, инструмент Cetus преобразует программы на Cи. Проект Cetus начинался как учебный проект, а сейчас он получил финансирование от Национального научного фонда США.

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

Статья «Выявление проблем производительности при вычислениях с децентрализованным планированием» (Identifying Performance Bottlenecks in Work-Stealing Computations) представлена Натаном Таллентом (Nathan Tallent) и Джоном Меллором-Грамми (John Mellor-Crummey). При постоянном росте тактовой частоты процессоров существенной проблемой стало рассеивание мощности, что вызвало интерес к процессорам со все большим числом ядер, однако, чтобы это принесло пользу программному обеспечению, в нем необходимо использовать параллелизм потоков управления, для чего, в свою очередь, требуются модели программирования, способствующие разработке эффективных многопотоковых программ. Но даже при использовании новых моделей программирования многие алгоритмы, рассчитанные на разделяемую память и восемь ядер, вряд ли смогут масштабироваться к машинам следующего поколения с десятками многопотоковых ядер. Поскольку многие проблемы масштабирования трудно диагностировать, для поддержки труда программистов требуются инструментальные средства анализа производительности. Но наиболее перспективные модели многопотокового программирования имеют сложные характеристики времени выполнения, что препятствует применению традиционных стратегий анализа производительности для выявления проблем.

Aвторы разработали стратегию профилирования для выявления проблемных участков в программах, опирающихся на децентрализованное планирование (work stealing) – мощный и практически важный метод планирования для динамического отображения многопотоковых вычислений на многоядерные процессоры. Хотя при децентрализованном планировании обеспечивается хорошая балансировка нагрузки, до недавнего времени отсутствовали какие-либо способы выявления проблем масштабирования и обеспечения понимания их причин на уровне пользователей.

Стратегия, реализованная на основе HPCToolkit (hpctoolkit.org), позволяет количественно оценить продолжительность простоев потоков управления и накладные расходы, когда в потоках управления выполняется не прикладной код. Затем выявляются те участки пользовательских приложений, в которых требуется больший и меньший уровень параллелизма (для сокращения времени простоя или накладных расходов соответственно), а также участки, для которых параллелизм бесперспективен (велики и время простоя, и накладные расходы). Существовавшие ранее профилировщики обеспечивали менее понятные показатели и не отличали исходный код от кода планировщика. Наконец, накладные расходы самой стратегии не отличаются от накладных расходов обычных профилировщиков, основанных на отборе образцов (от 1% до 5%).

Последнюю статью тематической подборки написали Теренс Келли (Terence Kelly), Йин Ванг (Yin Wang), Стефан Лафортюн (Stephane Lafortune) и Скотт Малке (Scott Mahlke). Статья называется «Устранение ошибок параллелизма с использованием техники управления» (Eliminating Concurrency Bugs with Control Engineering). Для устранения ошибок в программном обеспечении требовалось огромное время, и распространенным явлением были провалы дорогостоящих проектов, однако со временем процесс обычного последовательного программирования был несколько облегчен за счет совершенствования языков программирования, средств разработки и обучения. К 2004 году продуктивность и компетентность средних программистов не слишком отличались от соответствующих качеств специалистов в других технических областях. Но последние тенденции развития аппаратных средств грозят подорвать надежность программного обеспечения, продуктивность программистов и показатели экономической эффективности программной индустрии.

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

Учесть все аспекты параллелизма очень трудно даже при многопоточном программировании с использованием разделяемой памяти из-за многочисленных возможных чередований базовых операций. Недоучет каких-либо аспектов может привести к ошибкам («гонки» – data race) или незавершаемости программы (синхронизационные тупики – deadlock). Такие дефекты могут не выявляться при тестировании и приводить к катастрофическим результатам. Например, коварные ошибки параллелизма в тщательно протестированном программном обеспечении привели к широко известным несчастным случаям при использовании аппарата лучевой терапии Therac-25 (http://www.osp.ru/os/1998/06/179592). Практика консервативного программирования с применением, например, грубых блокировок, снижает риск возникновения ошибок, но приводит к снижению уровня параллелизма и тем самым к ухудшению производительности, что сводит на нет все преимущества параллелизма. Наконец, на многоядерной аппаратуре могут проявиться застарелые, но еще не обнаруженные ошибки параллелизма в унаследованных многопоточных программах, успешно выполнявшихся на однопроцессорных компьютерах.

Необходимость параллельного программирования и связанные с ним трудности представляют серьезную проблему компьютерной индустрии, и если проблемы параллельного программирования окажутся непреодолимыми, то новые версии программного обеспечения не будут более надежными, более быстрыми и, следовательно, более полезными, чем их предшественники. То же относится и к аппаратуре. Кто захочет менять 32-ядерный компьютер на 64-ядерный, если программное обеспечение на нем работает ничуть не лучше? Удлинение цикла замены аппаратно-программных средств приводит к соответствующему снижению темпов роста прибыльности компьютерной индустрии.

Наблюдаемый кризис параллелизма состоит в том, что многоядерная аппаратура приводит к повсеместной распространенности многопотокового программного обеспечения, а средние программисты получают возможность делать нечто такое, чего им раньше никогда не приходилось: писать большой объем правильного и эффективного многопотокового кода с разумными временными и материальными расходами. Ведущие обозреватели видят в этом серьезную угрозу для всей ИТ-отрасли и призывают к поиску революционных решений (cacm.acm.org/magazines/2009/10/42368-a-view-of-the-parallel-computing-landscape/fulltext).

По мнению авторов, для решения проблем параллельного программирования может быть полезной технология автоматического управления (control engineering). Классическая теория управления обеспечивает эффективный контроль над сложными и потенциально опасными системами, такими как нефтеперабатывающие предприятия и электронные системы самолетов. Эта теория успешно используется в течении более ста лет для построения промышленных приложений, и теперь она проникает в потребительские приложения, используемые в повседневной жизни людей. Традиционная теория управления больше всего подходит для физических систем с непрерывными пространствами состояний, описываемых системами дифференциальных уравнений. Такие системы, конечно, мало напоминают параллельное программное обеспечение, однако менее известная и более современная ветвь теории управления имеет дело уже с дискретными пространствами состояний и динамикой, управляемой событиями, что ближе к программированию.

Попытки скрещивания параллельного программного обеспечения с методами управления системами нашли отражение в проекте Gadara (www.usenix.org/event/osdi08/tech/full_papers/wang/wang.pdf). В Gadara используется дискретная теория управления (discrete control theory) для анализа параллельных программ и автоматического устранения синхронизационных тупиков, возникающих при использовании стандартных синхронизационных примитивов.

Вне тематической подборки опубликована статья Серджио Торала (Sergio Toral), Мануэля Варгаса (Manuel Vargas) и Федерико Барреро (Federico Barrero) «Встраиваемые мультимедийные процессоры для оценки параметров дорожного движения» (Embedded Multimedia Processors for Road-Traffic Parameter Estimation). Непрерывный прогресс полупроводниковой технологии, повсеместность цифровых технологий и коммуникаций, а также развитие сложных методов искусственного зрения формируют новую ситуацию на рынке, в которой возникает потребность во встраиваемых мультимедийных процессорах, предназначенных для создания и распространения цифровой мультимедийной информации. Одна из наиболее популярных и экономически целесообразных разновидностей систем обработки мультимедиа основывается на архитектуре «система на кристалле» (system-on-chip, SoC) с использованием RISC-процессоров общего назначения. В таких системах отсутствие специальной поддержки мультимедийных приложений компенсируется наличием набора внешнего оборудования, такого как видео- и аудиопорты, устройства сжатия и обработки видеоданных, а также интерфейсы к популярным устройствам внешней памяти, клавиатурам и жидкокристаллическим и ЭЛТ-мониторам.

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

Мультимедийные процессоры, основанные на технологии SoC, хорошо пригодны для многих мультимедийных приложений, что полностью относится к системам контроля и управления дорожным движением. Такие системы начинались как системы видеонаблюдения, но сегодня они превращаются в интегрированные интеллектуальные системы (intelligent transportation system, ITS), включающие новые технологии и дополнительные полезные службы. Основой ITS служит сеть, способная распространять обширную информацию, в том числе данные и видео в реальном времени.

Министерство транспорта США широко использует ITS, интегрированные с реальной средой. Например, технологии выявления происшествий, основанные на техническом зрении и позволяющие собирать различные данные о движении транспорта, используются на 39% регулируемых светофорами пересечениях дорог страны. Авторы разработали прототип системы для демонстрации целесообразности использования в основе ITS мультимедийных процессоров.

Всего вам хорошего, Сергей Кузнецов (kuzloc@ispras.ru).


Аппаратура и программное обеспечение мультимедийного процессора: a) аппаратура; б) ядро и другие программные компоненты

Поделитесь материалом с коллегами и друзьями