Многопоточность сегодня
[Эта заметка писалась в 2007 году, поэтому в некотором смысле её можно назвать "Многопоточность вчера" :)]
Уже достаточно давно программисты экстенсивно применяют многопоточность при реализации систем. При этом многопоточность применялась в основном для таких вещей как упрощение модели программирования, маскирование латентности блокирующих операций и т.д. И так же это всё происходило в подавляющем большинстве в контексте одного ядра/процессора. Соотв. распространены следующие принципы и подходы:
— Можно завести любое кол-во потоков. Иимеется в виду любое в пределах сотни. Т.е. кол-во потоков определяется исключительно потребностью архитектуры, но не аппаратной платформой.
— Можно произвольным образом распределить работу по потокам. Т.к. всё равно всё выполняется на одном ядре, то это не имеет значения.
— Можно и нужно экстенсивно применять мьютексы для синхронизации. Т.к. всё выполняется на одном ядре, то это практически не влияет на производительность и масштабируемость.
— Можно произвольным образом разделять данные между потоками. Т.к. процессор один, то это никак не влияет на производительность и масштабируемость. Фактически система работает так, как будто поток один, просто он выполяет то одну функцию, то другую.
Всё это я называю «многопоточность на одном ядре». Фактически система, построенная по таким принципам, образно является «однопоточной с кооперативной многозадачностью».
И всё это становится кардинально не верным с появлением массовых многоядерных процессоров. Во второй половине следующего года Intel намерена выпустить процессор с 16 аппаратными потоками: здесь
И через 5 лет они собираются выпустить процессор с 80 ядрами! (Представть свои программы на 80 ядрах! Есть идеи как их использовать?)
Что бы эффективно использовать новые аппаратные платформы, нужны совершенно новые принипы и подходы. Нужна «многопоточность на множестве ядер». Под эффективностью я подразумеваю, что бы программа на 8 ядрах выполнялась хотя бы не медленнее, чем на одном. Шутка шуткой, а на форумах посвящённым многопоточности сейчас один из самых распространённых вопросов «Почему моя программа, которая делает Х, на 4-ёх ядерной машине работает медленнее, чем на 1-ядерной?»
Потому что старые принципы многопоточности патологически не работают в новом контексте! Я уверен, что значительная часть многопоточных систем «старой школы» будут быстрее работать на многоядерном процессоре, если банально привязать все потоки программы к одному ядру! Т.к. синхронизация всё равно убивает потенциальный параллелизм, а разделение данных вносит коллосальные пенальти.
Некоторое время назад я был свидетелем следующей ситуации. Серверное ПО запустили на двух-процессорной машине (в надежде, что оно будет работать в 2 раза быстрее. ха-ха). Оно стало работать в 10 (!) раз медленнее (как потом оказалось причиной было постоянное разделение модифицируемых данных между двумя потоками).
Сейчас наиболее общий рецепт выглядит примерно следующим образом:
— Создать кол-во потоков по кол-ву аппаратных потоков. Как следствие — кол-во потоков не должно быть «зашито» в программу, т.к. она может выполняться на разных платформах. И как второе следствие – управление кол-вом потоков не должно быть заботой прикладного программиста (ну по крайней мере того же программиста, но когда он играет роль прикладного
).
— Работа должна быть распределена по потокам [примерно] равномерно. Соотв. это тоже не получится зашивать в программу и поручать прикладному программисту, т.к. кол-во потоков и кол-во и содержание работы меняться.
— Нельзя экстенсивно применять мьютесы/синхронизацию/блокировки. Т.к. это фактически заставит систему сериализоваться и выполняться «на одном ядре». Ни о какой масштабируемости тут не может быть и речи.
— По возможности надо элиминировать разделяемые данные. Совместная работа над одними модифицируемыми данными сейчас работает ооочень медленно и становится одним из важнейших новых боттлнеков аппаратной платформы, на ряду с тактами ядра, шиной к памяти, диском, сетью. И никаких изменений в лучшую сторону тут не предвидится. Только в худшую. (Это не относится к константным данным, их можно и нужно разделять между потоками)
Если выразить это более кратко: *каждое* ядро должно быть обеспечено *своей* работой и *своими* данными, и работать над ними *независимо*.
К сожалению пока никто не придумал как приготовить этот рецепт в общем виде... Т.е. что бы программист был занят только прикладными задачами, а всё остальное происходило как-то само собой.
Естественно могут иметь место и частные случаи. Например, приложение по обработке изображений или CAD/CAM/CAE/CASE. Тут скорее всего имеет смысл эффективно распараллеливать только одну основную функцию, например, обработку изображения, или рассчёт параметров модели (все остальные функции — графический интерфейс, фоновые задачи — по прежнему могут быть реализованы по старым принципам). Тут сейчас ситуация обстоит немного лучше. Тут (и только тут) на помощь могут придти такие средства как OpenMP, RapidMind, Intel TBB, Java Fork/Join и тд.:
gee.cs.oswego.edu/dl/papers/fj.pdf
К сожалению все эти средства подходят для очень ограниченного круга задач, и не подходят для реализации более общих и не типовых задач. И всё равно они не снимают с программиста основной задачи — что конкретно и как конкретно должно быть распараллелено. Это по прежнему должен решать программист, и он по прежнему должен обеспечить достаточное кол-во потенциального параллелизма, возможность для независимой работы потоков без разделяемых данных и т.д.
Есть ещё 2 вещи стоящие упоминания в данном контексте: готовые высокооптимизированные библиотеки и автоматическое распараллеливание кода.
Для решения типовых задач имеется ряд высокооптимизированных библиотек. Например можно посмотреть на:
Intel Integrated Performance Primitives (IPP):
http://www.intel.com/cd/software/products/asmo-na/eng/219767.htm
И AMD Performance Library (APL):
http://developer.amd.com/apl.jsp
Задачи, которые они могут решать включают:
— обработка/кодирование/декодирование видео
— обработка/кодирование/декодирование изображений
— обработка/кодирование/декодирование аудио
— операции над матрицами/векторами/строками
и т.д.
Понятно, что на общее решение такие библиотеки не тянут. Однако, если решаемая задача укладывается в возможности библиотеки, то имеет большой смысл применять такую библиотеку (Intel — платная, AMD — бесплатная).
Автоматическое распараллеливание кода.
Здесь не на что смотреть! Проходите, не задерживаетесь!
Сейчас автоматические распараллеливатели могут очень мало и очень конкретного. И вам всё равно придётся убеждаться, что распараллелилось то, что надо, так, как надо, и оно не ломается при последующих модификациях кода (напоминает борьбу с оптимизатором БД
). Фактически правильнее считать, что автоматического распараллеливания кода *нет*. Сейчас и в ближайшую декаду. Если кто-то утверждает обратное, то он либо не разбирается в вопросе, либо хочет вам что-то продать
За подробностями смотрите интервью с Джеем Хоефлингером, который занимается автоматическим распараллеливанием с середины 80:
Подытожу. Мы сейчас находимся на перегибе развития. Что бы поспеть за развитием, а не попасть в кювет, надо многое переосмыслить и смотреть на вещи по новому. Новые принципы и подходы только формируются, ни у кого пока нет *универсальных* решений. Всё, что сейчас выдают за таковые, за универсальные решения для многоядерности (OpenMP, RapidMind, Intel TBB) — маркетинг. Ну, возможно, это лишь строительные блоки, но ни как не решение. Сейчас всё зависит исключительно от компетентности конкретного программиста, разрабатывающего конкретную систему.
Дополнительные ссылки для интересующихся:
Фундаментальная работа на тему, почему процессоры *не* будут становится всё быстрее и быстрее, и что делать теперь:
The Landscape of Parallel Computing Research: A View from Berkeley
Если кто ещё не читал — популярные заметки Герба Саттера:
How Much Scalability Do You Have or Need?
OpenMP Does Not Scale — Or Does It?. В очень забавной форме показываются проблемы, связанные с написанием параллельных программ.
How-to Split a Problem into Tasks. Как выявлять параллелизм в системе (подходит в основном для HPC).
Ещё интересные заметки Michael Suess:
Is the Multi-Core Revolution a Hype?
Moore’s Law is Dead — Long Live Moore’s Law!
How Much of the Industry Will Go Parallel?
Parallel Programming is Entering the Mainstream — or isn’t it?