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

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

Обзор августовского, 2012 г. номера журнала Computer (IEEE Computer Society, V. 45, No 8, Август 2012).

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

Тематическая подборка августовского номера журнала в этом году посвящена массивно многопоточным вычислительным системам. Так же («Massively Multithreaded Computing Systems») называется и вводная заметка приглашенных редакторов, которыми являются Стефен Кеклер и Стивен Рейнхард (Stephen W. Keckler, Nvidia, Steven K. Reinhardt, Advanced Micro Devices).

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

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

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

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

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

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

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

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

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

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

Для каждого из описываемых методов была реализована, по крайней мере, одна версия тестового набора Parboil, в котором не применялся этот метод, но который был хорошо оптимизирован во всех других отношениях. Эта реализация сравнивалась с реализацией, доступной авторам и демонстрирующей наивысшую скорость выполнения. Подавляющее число результатов, приводимых в статье, было получено для графического ускорителя Nvidia GeForce 480 GTX.

Авторами статьи «Модель программирования графических процессоров с распараллеливанием на уровне задач на основе разрешения зависимостей» («A GPU Task-Parallel Model with Dependency Resolution») являются Стенли Ценг, Джон Овенс и Брендон Ллойд (Stanley Tzeng, John D. Owens, University of California, Davis, Brandon Lloyd, Microsoft).

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

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

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

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

Статью «Можно ли освободить программирование от проблемы параллелизма по данным?» («Can GPGPU Programming Be Liberated from the Data-Parallel Bottleneck?») представили Бенедикт Гастер и Ли Хоус (Benedict R. Gaster, Lee Howes, Advanced Micro Devices).

Существующие модели программирования ориентированы на частичное удовлетворение разнообразных требований неоднородных платформ. В последние годы существенно увеличилась гибкость моделей программирования графических процессоров. Наиболее популярные модели 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, Pacific Northwest National Laboratory).

Современные высокопроизводительные (high-performance computing, HPC) вычислительные системы ориентированы на поддержку рабочих нагрузок с большим числом вычислений с плавающей точкой. Системы HPC создаются, главным образом, для обеспечения возможности научного моделирования, которое характеризуется высокой степенью плотности и локальностью вычислений, а также наличием регулярных, хорошо разделяемых структур данных. Такие потребности приложений ведут к разработке быстрых арифметических устройств в стиле SIMD, а также к использованию глубоких иерархий кэш-памяти, позволяющих сократить время задержки при доступе к памяти.

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

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

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

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

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

Вне тематической подборки опубликована одна крупная статья – «Cinefile: основанный на категориях аналитический браузер» («Cinefile: A Category-Based Analytic Browser»),

написанная Стефен Дэвис, Стейси Эйлор Сил и Джесс Хэтфилд (Stephen Davies, University of Mary Washington, Stacey Aylor Seal, Jesse Hatfield, George Mason University).

Технология реляционных баз данных является одной из самых значительных инноваций 20-го века. Частично это обосновывается мощностью и гибкостью декларативного языка запросов. Язык SQL, специально разработанный для управления данными в реляционных базах данных позволяет анализировать огромные наборы данных различными способами, включая те, которые не предусматривались проектировщиками базы данных. Например, при наличии крупной базы данных популярных фильмов SQL может помочь выбрать «все фильмы, принесшие доход больше 20 миллионов долларов», «актеров, сыгравших главные роли в фильмах компании Paramount Pictures» или даже «директоров, по крайней мере, двух фильмов, в которых в главной роли снялась Джулия Робертс, и которые были выпущены в викенды в 1990-е гг.». Такие запросы называются точными, поскольку, независимо от сложности, на них могут быть получены полные и неоспоримые ответы.

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

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

Аристотель представлял категории как группы с четко определенными границами, разделяемые строгими характеристиками, наличие которых у объекта является необходимым и достаточным условием вхождения в соответствующую группу. Однако философ Людвиг Витгенштейн (Ludwig Wittgenstein), а после него когнитивные психологи Элеанор Рош (Eleanor Rosch) и Джордж Лакофф (George Lakoff) убедительно доказали, что дела с категориями не так просты.

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

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

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

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

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