Массовая многопоточность

Открывает номер вводная заметка приглашенных редакторов Стефена Кеклера (Stephen Keckler) и Стивена Рейнхарда (Steven Reinhardt). Модель фон Неймана доминировала в компьютерной области более 50 лет — приложения и модели программирования ориентировались на однопоточное исполнение, а разработчики аппаратуры стремились повышать производительность обработки одного потока команд. Параллельные компьютеры разрабатывались в расчете на использование в ограниченном числе прикладных областей и в течение последних двадцати лет в основном создавались путем агрегирования множества высокопроизводительных последовательных процессоров, а программировались на уровне крупных структурных единиц с применением моделей типа MPI или OpenMP.

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

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

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

Тематическая подборка включает четыре регулярные статьи. Первая написана Джоном Стретоном (John Stratton), Кристофером Родригесом (Christopher Rodrigues), И-Джуй Сунгом (I-Jui Sung), Ли-Вен Чангом (Li-Wen Chang), Нессером Анссари (Nasser Anssari), Генгом Лиу (Geng Liu), Вен-мей Хву (Wen-mei Hwu), Неди Обейдом (Nady Obeid) и называется «Алгоритмы и методы оптимизации данных для перехода к использованию массово-многопоточных систем» (“Algorithm and Data Optimization Techniques for Scaling to Massively Threaded Systems”). В современных многоядерных процессорах аппаратно поддерживаются сотни потоков управления, и для масштабирования к такому большому числу потоков требуется не только распараллелить задачи, но и обеспечить требуемую пропускную способность — этот ресурс в высокопроизводительных системах становится все более ограниченным по сравнению с обеспечиваемой ими вычислительной мощностью. Для многих приложений требуется также обеспечить контролируемый доступ к совместно используемым данным. Таким образом, для многоядерных многопоточных систем на передний план выходит проблема масштабирования параллельной производительности. Программисты могут достичь масштабируемой производительности приложений путем настройки алгоритмов для работы с большими объемами внутрикристальной памяти потоков, а кэши и другая внутрикристальная память помогут справиться с локальностью. Однако проблема в том, что для применения этих методов требуются внутрикристальные ресурсы памяти, индивидуальные для потоков, тогда как возможности обеспечения таких ресурсов сокращаются в массово-многопоточных системах, и эта тенденция, по-видимому, сохранится в будущем.

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

Авторами статьи «Модель программирования графических процессоров с распараллеливанием на уровне задач на основе разрешения зависимостей» (“A GPU Task-Parallel Model with Dependency Resolution”) являются Стенли Ценг (Stanley Tzeng), Джон Оуэнс (John Owens) и Брендон Ллойд (Brandon Lloyd). В существующих языках программирования графических процессоров используется модель распараллеливания по данным. Пользователь пишет ядро приложения и специфицирует объем работ, которые оно будет выполнять на графическом процессоре. Затем внутренний аппаратный планировщик графического процессора определяет, как следует распределить отдельные блоки работ по ядрам потокового мультипроцессора. В последние годы эта модель успешно использовалась при разработке вычислительно сложных приложений общего назначения. Ключевая особенность этой модели состоит в том, что блоки, распределяемые по ядрам графического процессора, независимы. Это обеспечивает свободу планировщику для эффективного распределения работы по ядрам, однако не позволяет обрабатывать широкий класс нерегулярных рабочих нагрузок, в которых присутствуют зависимости. В рабочей нагрузке с зависимостями имеется по крайней мере одна единица работы, которая должна завершиться до начала выполнения других единиц.

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

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

Статью «Можно ли освободить программирование от проблемы параллелизма по данным?» (“Can GPGPU Programming Be Liberated from the Data-Parallel Bottleneck”) представили Бенедикт Гастер (Benedict Gaster) и Ли Хоус (Lee Howes). В последние годы существенно увеличилась гибкость моделей программирования графических процессоров, часть из которых — например, OpenCL (Open Computing Language) и CUDA (Compute Unified Device Architecture) — в некоторой степени поддерживают программирование неоднородных платформ. Для обеспечения возможности выполнения кода на разных целевых платформах в этих моделях используется методология распараллеливания по данным со слабыми гарантиями коммуникаций, однако это приводит к появлению ряда фундаментальных проблем, среди которых:

• необходимость комбинирования программирования в стиле SPMD (single program, multiple data — одна программа, много данных) с исполнением в стиле SIMD (single instruction, multiple data — одна команда, много данных);
• необходимость отслеживания разветвленного параллелизма (braided parallelism);
• допустимость композиции операций.

Основные усилия по облегчению программирования неоднородных платформ сегодня сводятся к упрощению интерфейсов прикладного программирования, однако модели программирования, к числу которых, в частности, относятся CUDA, C++ AMP (Accelerated Massive Parallelism) и OpenACC, хотя и облегчают жизнь программистов, но не решают отмеченных фундаментальных проблем. Описываемая в статье модель HPP (heterogeneous parallel primitives) является объектно-ориентированной, она основана на стандарте C++11 и позволяет решить эти проблемы при программировании и традиционных процессоров, и графических ускорителей. Модель полностью поддерживает возможность композиции путем определения абстракций с применением распределенных массивов и ограждающих объектов (barrier object). Гибкость выполнения программ обеспечивается за счет использования разветвленного параллелизма.

Авторами последней статьи тематической подборки — «Проектирование многопоточных архитектур для нерегулярных приложений» (“Designing Next-Generation Massively Multithreaded Architectures for Irregular Applications”) — являются Антонио Тумео (Antonino Tumeo), Симоне Секки (Simone Secchi) и Оресте Вилья (Oreste Villa). Современные системы высокопроизводительных вычислений (High-Performance Computing, HPC) ориентированы на поддержку рабочих нагрузок с большим числом вычислений с плавающей точкой. Системы HPC создаются главным образом для обеспечения возможности научного моделирования, которое характеризуется высокой степенью плотности и локальностью вычислений, а также наличием регулярных, хорошо разделяемых структур данных. Однако приложения из ряда активно развиваемых областей (например, биоинформатики, выявления сообществ, обнаружения знаний, обработки текстов на естественных языках, распознавания образов, анализа социальных сетей и т. д.) обладают нерегулярной природой. В них используются структуры данных, основанные на использовании указателей (несбалансированные деревья, неструктурированные сетки и графы). Таким структурам данных свойственна слабая пространственная и временная локальность. Кроме того, они часто изменяются динамически во время выполнения приложений.

Cray XMT — многоузловой суперкомпьютер, созданный специально для поддержки разработки и выполнения нерегулярных приложений. Его архитектура базируется на трех главных принципах: глобальное адресное пространство, мелкозернистая синхронизация и многопоточность. Глобальное совместно используемое адресное пространство равномерно отображается на очень мелком уровне структурности на основную память разных узлов. В каждом узле имеется специальный процессор ThreadStorm, который переключается на уровне тактов между многочисленными потоками управления. Это позволяет сгладить задержки при доступе к локальной памяти соответствующего узла и доступе к сети, если требуются данные из памяти других узлов. В отличие от современных систем HPC, для XMT реализована общесистемная модель программирования, облегчающая написание приложений, которые работают с памятью большого объема, без потребности в оптимизации для обеспечения локальности обращений к памяти.

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

Вне тематической подборки опубликована одна крупная статья — «Cinefile: основанный на категориях аналитический браузер» (“Cinefile: A Category-Based Analytic Browser”), авторы которой Стефен Дэвис (Stephen Davies), Стейси Эйлор Сил (Stacey Aylor Seal) и Джесс Хэтфилд (Jesse Hatfield). Технология реляционных баз данных является одной из самых значительных новаций XX века, что частично обосновывается мощностью и гибкостью декларативного языка запросов. Язык SQL, специально разработанный для управления данными в реляционных базах, позволяет анализировать огромные наборы данных различными способами, включая те, которые не предусматривались проектировщиками базы данных. Например, при наличии крупной базы данных популярных фильмов SQL может помочь выбрать «все фильмы, принесшие доход больше 20 миллионов долларов», «актеров, сыгравших главные роли в фильмах компании Paramount Pictures» или «директоров по крайней мере двух фильмов, в которых в главной роли снялась Джулия Робертс и которые были выпущены в уикенды в 90-е». Такие запросы называются точными, поскольку, независимо от сложности, на них могут быть получены полные и неоспоримые ответы. Но в некоторых случаях пользователи хотят исследовать базу данных по-другому. Они могут естественным образом сгруппировать объекты, используя известные признаки сходства между ними. Возможно, некоторые фильмы можно было бы отнести к эпическим драмам, другие счесть детективами, а третьи — эксцентрическими комедиями старой школы. Эти абстрактные категории трудно описать словами и невозможно свести до уровня атрибутов объектов. И тем не менее подобные классификации представляют реальное понимание объектов. Пользователи могут не суметь точно определить, что такое трагикомедия, но они сумеют отнести к этой категории соответствующий фильм, когда увидят его.

Идея пользовательской категоризации как способа представления знаний восходит к временам Аристотеля. Хотя ученые опровергли многие классические идеи относительно категорий, психологи относятся к этому понятию, как к одному из основных способов понимания мира человеком. Аристотель представлял категории как группы с четко обозначенными границами, определяемые строгими характеристиками, наличие которых у объекта является необходимым и достаточным условием вхождения в соответствующую группу. Однако философ Людвиг Витгенштейн, а после него когнитивные психологи Элеанор Рош и Джордж Лакофф убедительно доказали, что границы между категориями могут быть размытыми. У каждой категории имеются прототипные объекты, являющиеся более сильными примерами именно этой категории, а не каких-то других. И определение категории часто приходится основывать не на значениях набора атрибутов объектов, а на подобии: объекты одной и той же категории обладают общими чертами, не все черты таких объектов являются общими и ни одна черта не является общей для всех объектов. Однако никто не оспаривает утверждение Аристотеля, что категории являются основой человеческого понимания мира.

Принимая во внимание, что люди естественным образом классифицируют объекты мира, стоит задуматься о том, как использовать эту идею в интерфейсе с базой данных. У пользователей мог бы возникнуть естественный вопрос: «Сколько денег приносят создателям эксцентрические комедии старой школы по сравнению с романтическими комедиями?». Этот запрос невозможно выразить на языке SQL, поскольку в нем используются расплывчатые понятия. Никакие конкретные атрибуты какого-либо объекта базы данных не означают, что он соответствует эксцентрической комедии старой школы. Описание требуемого формируется в голове пользователя на основе паттернов, полученных при просмотре десятков других фильмов. Такие запросы называются абстрактными. Реляционная система баз данных сможет быстро ответить на вопрос об эксцентрических комедиях, но только в том случае, когда сможет как-то проинтерпретировать смысл этого понятия.

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

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

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

До новой встречи, с уважением, Сергей  Кузнецов.