Кризис параллельного мира

Сергей Кузнецов

Обзор декабрьского 2009 г. номера журнала Computer (IEEE Computer Society, V. 42, No 12, декабрь, 2009).

Авторская редакция.
Также обзор опубликован в журнале "Открытые системы"

Темой декабрьского номера журнала Computer в этом году являются инструменты и среды для архитектур мультиядерных (multicore) и многоядерных (many-core) процессоров («Tools and Environments for Multicore and Many-Core Architectures»). У тематической подборки имеются приглашенные редакторы Ву-чун Фенг и Паван Баладжи (Wu-chun Feng, Virginia Tech., Pavan Balaji, Ohio State University), публикуется их небольшая вводная заметка и пять больших статей. Заметка редакторов называется так же, как и тема номера.

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

С появлением чипов с несколькими ядрами – от традиционных мультиядерных (multicore) процессоров компаний AMD и Intel до более экзотичного мультиядерного процессора Cell и многоядерных (many-core) графических процессоров AMD/ATI и NVIDIA – необходимыми стали параллельные вычисления с использованием нескольких ядер в одном чипе. Однако написание параллельных приложений представляет собой существенную проблему.

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

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

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

Первую из основных статей тематической подборки написали Скотт Шнейдер, Джей-Сын Ём и Димитриос Николопулос (Scott Schneider, Jae-Seung Yeom, Virginia Tech, Dimitrios S. Nikolopoulos, FORTH-ICS and University of Crete), она называется «Программирование мультипроцессоров с явно управляемыми иерархиями памяти» («Programming Multiprocessors with Explicitly Managed Memory Hierarchies»).

Мультиядерные процессоры с явно управляемыми иерархиями памяти (explicitly managed memory, EMM) происходят из области компьютерных игр и графики, а теперь выступают в качестве высокопроизводительных вычислительных платформ общего назначения. Недавно аналогичные разработки начали выполняться и поставщиками процессоров для рынка массовых компьютеров, компаниями Intel и AMD. Во всех этих процессорах в качестве ускорителей используются компоненты, параллельные по данным. Это ускорение достигается на основе применения скалярных и SIMD-ядер, поддержки высокой пропускной способности внутри чипов и явной передачи данных между быстрой локальной памятью и внешней динамической памятью (DRAM). Явная пересылка данных дает возможность программистам использовать оптимальные политики кэширования и организовывать несколько буферов потоковой передачи данных, позволяющих совмещать вычисления с выполнением операции передачи данных.

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

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

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

Статью «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 – это инфрастуктура, которая предназначается для исследования оптимизаций времени компиляции, направленных на автоматическое распараллеливание. Эта инфраструктура поддерживает преобразования на уровне исходного текста, ориентирована на пользователей, проста в применении и опирается на наиболее важные методы параллелизации. Инфраструктурный проект Cetus является преемником проекта Polaris, в котором, вероятно, была разработана наиболее развитая инфраструктура для оптимизирующих компиляторов для параллельных машин. В то время как инфраструктура Polaris была ориентирована на язык Fortran, Cetus преобразует C-программы. Проект Cetus начинался как учебный проект, который впоследствии был продолжен несколькими студентами-энтузиастами. В настоящее время университет получил финансирование от Национального научного фонда США, что позволит довести результаты проекта до уровня ресурса сообщества.

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

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

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

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

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

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

Последнюю статью тематической подборки написали Теренс Келли, Йин Ванг, Сефан Лафортюн и Скотт Малке (Terence Kelly, Yin Wang, Hewlett-Packard Laboratories, Stéphane Lafortune, Scott Mahlke, University of Michigan). Статья называется «Устранение ошибок параллелизма с использованием техники управления» («Eliminating Concurrency Bugs with Control Engineering »).

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

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

Проблема состоит в том, что параллельное программирование гораздо труднее последовательного программирования. Учесть все аспекты параллелизма очень трудно даже при многопоточном программировании с использованием разделяемой памяти (хотя в этом подходе частично сохраняется стиль последовательного программирования) из-за многочисленных возможных чередований базовых операций. Недоучет каких-либо аспектов может привести к ошибкам («гонке данных», data race) или незавершаемости программы (синхронизационный тупик, deadlock). Такие дефекты могут не выявляться при тестировании программного обеспечения и приводить к катастрофическим результатам во время его эксплуатации. Например, коварные ошибки параллелизма в тщательно протестированном программном обеспечении привели к широко известным несчастным случаям при использовании аппарата лучевой терапии Therac-25. Практика консервативного программирования с применением, например, грубых блокировок, снижает риск появления ошибок в новом программном обеспечении, но приводит к снижению уровня параллелизма и, тем самым, к ухудшению производительности, что сводит на нет все преимущества параллелизма. Наконец, на многоядерной аппаратуре могут проявиться застарелые ошибки параллелизма у унаследованных многопоточных программ, которые успешно выполнялись на однопроцессорных компьютерах.

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

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

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

Несколько лет назад была образована группа, включающая специалистов в области теории управления, системного программного обеспечения и разработки компиляторов. Задачей группы было изучение возможностей применения теории управления к параллельному программному обеспечению. Последние попытки скрещивания параллельного программного обеспечения с методами управления системами нашли отражение в проекте Gadara. В Gadara используется дискретная теория управления (discrete control theory, DCT) для анализа параллельных программ и автоматического устранения важного класса ошибок параллелизма: синхронизационные тупики, возникающие при использовании стандартных синхронизационных примитивов.

Вне тематической подборки опубликована статья Серджио Торала, Мануэля Варгаса и Федерико Барреро (Sergio L. Toral, Manuel Vargas, Federico Barrero, University of Seville, Spain) «Встраиваемые мультимедийные процессоры для оценки параметров дорожного движения» («Embedded Multimedia Processors for Road-Traffic Parameter Estimation»).

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

Одна из наиболее популярной и экономически целесообразных разновидностей систем обработки мультимедиа основывается на архитектуре «система на кристалле» (system-on-chip, SoC) с использованием RISC-процессоров общего назначения. В таких системах отсутствие специальной поддержки мультимедийных приложений компенсируется наличием набора внешнего оборудования, такого как видео- и аудио-порты, устройства сжатия и обработки видеоданных, а также интерфейсы к популярным устройствам внешней памяти, клавиатурам и LCD- и CRT-мониторам.

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

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

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

Министерство транспорта США представляет отличные отчеты о приложениях ITS. Они демонстрируют средний уровень интеграции оборудования ITS с реальной средой. Например, технологии выявления происшествий, основанные на техническом зрении и позволяющие приложениям собирать различные данные о движении транспорта, используются примерно на 39% регулируемых светофорами пересечениях дорог. Большая часть этих американских коммерческих ресурсов основывается на специализированных процессорах обработки видеоизображений (www.autoscope.com, www.traficon.com) или встраиваемых PC (www.citilog.com).

Авторы разработали прототип системы для демонстрации целесообразности использования в основе ITS мультимедийных процессоров. Предлагаемое решение обеспечивает производительность, аналогичную производительности встраиваемых PC, но с меньшими расходами.

Всего вам хорошего, Сергей Кузнецов.