Аппаратный параллелизм и программисты: кто кого сборет?

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

Обзор мартовского, 2010 г. номера журнала Computer (IEEE Computer Society, V. 43, No 3, March 2010).

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

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

Первая статья тематической подборки называется «Параллелизм на основе использования многопотоковых и многоядерных процессоров» («Parallelism via Multithreaded and Multicore CPUs») и написана Анжелой Содан, Джекобом Мэчина, Арашем Десмехом, Кевином Макнотоном и Брайаном Есбауфом (Angela C. Sodan, Jacob Machina, Arash Deshmeh, Kevin Macnaughton, Bryan Esbaugh, University of Windsor).

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

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

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

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

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

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

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

Разработчики массового программного обеспечения могут опираться на широко распространенную в области высокопроизводительных вычислений модель программирования c использованием общей памяти OpenMP (http://openmp.org/wp). Другим перспективным направлением является использование транзакционной памяти (http://www.citforum.ru/programming/digest/transactional_memory/), упрощающей координацию доступа к данным на основе автоматических механизмов установки контрольных точек и откатов транзакций. Во многих случаях наиболее экономичным подходом является использование библиотек уже распараллеленных программ, например, библиотеки BLAS (Basic Linear Algebra Subprograms).

Группа авторов из компании Intel (первый в списке – Мойше Бах (Moshe (Maury) Bach)) представила статью «Анализ параллельных программ с использованием Pin» («Analyzing Parallel Programs with Pin»).

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

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

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

Pin2 (www.pintool.org) – это программная система, производящая бинарное инструментирование во время выполнения приложений для Linux и Microsoft Windows. Целью Pin является обеспечение платформы инструментовки для построения разнообразных средств анализа, называемых pintool. За счет обеспечения инструментирования во время выполнения приложений Pin устраняет потребность в изменении и повторной компиляции исходного кода приложений. Инструментирование производится с использованием динамически генерируемого кода.

Название следующей статьи – «Auto-Pipe: организация потокового выполнения приложений в архитектурно разнотипных системах» («Auto-Pipe: Streaming Applications on Architecturally Diverse Systems »). Ее написали авторы из Вашингтонского университета в Сент-Луисе; первым в длинном списке авторов стоит Роджер Чемберлейн (Roger D. Chamberlain).

Выявление и последующее использование потоковой семантики данных в приложениях может упростить процесс разработки. Использование парадигмы потоковых данных позволяет проще выявить возможности параллелизма, сократить число конфликтов и ошибок синхронизации и с меньшими усилиями добиться корректного выполнения приложений. Примерами языков, поддерживающих непосредственное выражение семантики потоковых данных, являются Brook и StreamIt. Вычислительные блоки, называемые ядрами (kernel) в Brook и фильтрами (filter) в StreamIt, связываются посредством явно определенных соединений (edge), через которые перемещаются блоки данных в некоторой фиксированной топологии, заданной во время компиляции. Семантика потоковых данных свойственна многим, хотя и не всем приложениям,

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

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

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

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

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

Авторами последней статьи тематической подборки «Инструментальные средства для очень быстрого сопоставления регулярных выражений» («Tools for Very Fast Regular Expression Matching») являются Давиде Пасетто, Фабрицио Петрини и Вират Агарвал (Davide Pasetto, IBM Computational Science Center, Ireland, Fabrizio Petrini, Virat Agarwal, IBM T.J. Watson Research Center, Yorktown).

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

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

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

Вне тематической подборки опубликованы две большие статьи. Статья «Верификация контрактов интерфейсов Web-сервисов во время выполнения» («Runtime Verification of Web Service Interface Contracts») представлена Сильвайном Халле, Тевфиком Бултаном, Грехэмом Хафсом, Муатом Алкалафом и Роджером Виллимейром (Sylvain Hallé, Tevfik Bultan, Graham Hughes, Muath Alkhalaf, University of California, Santa Barbara, Roger Villemaire, Université du Québec à Montréal).

Ajax (Asynchronous JavaScript and XML) – это набор технологий, используемых для разработки развитых интерактивных Web-приложений. Типичный Ajax-клиент локально выполняется в Web-браузере пользователя и обновляет свой интерфейс на лету в соответствии с данными, вводимыми пользователем.

Популярные Ajax-приложения, такие как Google Maps и Facebook общаются с сервером в фоновом режиме. Когда пользователь вводит информацию на портал Facebook, приложение должно послать ее в свою удаленную базу данных. Когда пользователь перемещается по карте Google Maps, приложение требует от сервера новую часть изображения.

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

Авторы статьи экспериментировали с Web-сервисом AWS-ECS (Amazon Web Services – Amazon E-Commerce Service) компании Amazon. Эти эксперименты продемонстрировали преимущества модельного подхода к тестированию и отслеживанию Web-сервисов во время их выполнения. После создания формальной модели поведения Web-сервиса можно выполнять различные аналитические задачи без вмешательства пользователей.

На первом шаге можно убедиться в правильности понимания документации путем автоматической генерации тестовых последовательностей, выполняемых над реальной реализацией Web-сервиса. Затем разработанный авторами легковесный монитор Ajax-приложений (http://beepbeep.sourceforge.net) может обеспечить соблюдение контрактов интерфейсов на стороне клиента, предупреждая пользователей о нарушениях контракта и препятствуя отправке ошибочных сообщений серверу.

Взаимодействие между Ajax-приложением и Amazon E-Commerce Service

Использование этого метода по отношению к AWS-ECS позволило автоматически сгенерировать тестовые последовательности и менее чем за три минуты тестирования выявить два отклонения в реализации сервиса от соответствующей документации. Кроме того, разработана инфраструктура, позволяющая отслеживать соблюдение контракта со стороны и клиента, и сервера с минимальными изменениями существующего кода Ajax-приложения. Накладные расходы составили примерно 10 миллисекунд на каждое входящее и исходящее сообщение. Разработанные инструментальные средства являются общими, позволяющими применить подход к любому клиенту и сервису.

Последняя статья мартовского номера написана Суманом Мандалом, Раби Нахапатрой, Правеном Бходжвани и Сараджу Моханти (Suman K. Mandal, , Rabi N. Mahapatra, Texas A&M University, Praveen S. Bhojwani, Sun Microsystems, Saraju P. Mohanty, University of North Texas) и называется «IntellBatt: на пути к более интеллектуальным батареям» («IntellBatt: Toward a Smarter Battery»).

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

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

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

Авторы разработали новую батарею IntellBatt, экономящую больше энергии и более безопасную, чем традиционные интеллектуальные батареи. IntellBatt отличается наличием интеллектуального массива элементов батареи (intelligent battery cell array, IBCA) с менеджером, функции которого выходят за пределы простого мониторинга. Этот менеджер активно планирует использование элементов для оптимизации времени жизни батареи, а также обеспечивает надежность и устойчивость питания. Более точно, IBCA:

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

Поскольку в IntellBatt не требуется знание особенностей устройства, батарея пригодна для использования в любом переносном электронном оборудовании. Батарею можно использовать в автономном режиме или с применением метода BATS для повышения эффективности.

Как показывает рисунок, в IntellBatt имеются три основных компонента: массив элементов, схема переключения элементов (cell switching circuit, CSC), соединяющая массив элементов с основными клеммами, и менеджер IBCA, управляющий элементами и определяющий их взаимосвязи на основе потребностей устройства.

Всего доброго, до следующей встречи, Сергей Кузнецов.