Многопоточность сегодня

[Эта заметка писалась в 2007 году, поэтому в некотором смысле её можно назвать "Многопоточность вчера" :)]

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

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

— Можно произвольным образом распределить работу по потокам. Т.к. всё равно всё выполняется на одном ядре, то это не имеет значения.

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

— Можно произвольным образом разделять данные между потоками. Т.к. процессор один, то это никак не влияет на производительность и масштабируемость. Фактически система работает так, как будто поток один, просто он выполяет то одну функцию, то другую.

Всё это я называю «многопоточность на одном ядре». Фактически система, построенная по таким принципам, образно является «однопоточной с кооперативной многозадачностью».

И всё это становится кардинально не верным с появлением массовых многоядерных процессоров. Во второй половине следующего года Intel намерена выпустить процессор с 16 аппаратными потоками: здесь

И через 5 лет они собираются выпустить процессор с 80 ядрами! (Представть свои программы на 80 ядрах! Есть идеи как их использовать?)

Что бы эффективно использовать новые аппаратные платформы, нужны совершенно новые принипы и подходы. Нужна «многопоточность на множестве ядер». Под эффективностью я подразумеваю, что бы программа на 8 ядрах выполнялась хотя бы не медленнее, чем на одном. Шутка шуткой, а на форумах посвящённым многопоточности сейчас один из самых распространённых вопросов «Почему моя программа, которая делает Х, на 4-ёх ядерной машине работает медленнее, чем на 1-ядерной?»

Потому что старые принципы многопоточности патологически не работают в новом контексте! Я уверен, что значительная часть многопоточных систем «старой школы» будут быстрее работать на многоядерном процессоре, если банально привязать все потоки программы к одному ядру! Т.к. синхронизация всё равно убивает потенциальный параллелизм, а разделение данных вносит коллосальные пенальти.

Некоторое время назад я был свидетелем следующей ситуации. Серверное ПО запустили на двух-процессорной машине (в надежде, что оно будет работать в 2 раза быстрее. ха-ха). Оно стало работать в 10 (!) раз медленнее (как потом оказалось причиной было постоянное разделение модифицируемых данных между двумя потоками).

Сейчас наиболее общий рецепт выглядит примерно следующим образом:

— Создать кол-во потоков по кол-ву аппаратных потоков. Как следствие — кол-во потоков не должно быть «зашито» в программу, т.к. она может выполняться на разных платформах. И как второе следствие – управление кол-вом потоков не должно быть заботой прикладного программиста (ну по крайней мере того же программиста, но когда он играет роль прикладного

).

— Работа должна быть распределена по потокам [примерно] равномерно. Соотв. это тоже не получится зашивать в программу и поручать прикладному программисту, т.к. кол-во потоков и кол-во и содержание работы меняться.

— Нельзя экстенсивно применять мьютесы/синхронизацию/блокировки. Т.к. это фактически заставит систему сериализоваться и выполняться «на одном ядре». Ни о какой масштабируемости тут не может быть и речи.

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

Если выразить это более кратко: *каждое* ядро должно быть обеспечено *своей* работой и *своими* данными, и работать над ними *независимо*.

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

Естественно могут иметь место и частные случаи. Например, приложение по обработке изображений или CAD/CAM/CAE/CASE. Тут скорее всего имеет смысл эффективно распараллеливать только одну основную функцию, например, обработку изображения, или рассчёт параметров модели (все остальные функции — графический интерфейс, фоновые задачи — по прежнему могут быть реализованы по старым принципам). Тут сейчас ситуация обстоит немного лучше. Тут (и только тут) на помощь могут придти такие средства как OpenMP, RapidMind, Intel TBB, Java Fork/Join и тд.:

www.openmp.org

www.rapidmind.com

osstbb.intel.com

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:

http://www.thinkingparallel.com/2007/08/14/an-interview-with-dr-jay-hoeflinger-about-automatic-parallelization/

Подытожу. Мы сейчас находимся на перегибе развития. Что бы поспеть за развитием, а не попасть в кювет, надо многое переосмыслить и смотреть на вещи по новому. Новые принципы и подходы только формируются, ни у кого пока нет *универсальных* решений. Всё, что сейчас выдают за таковые, за универсальные решения для многоядерности (OpenMP, RapidMind, Intel TBB) — маркетинг. Ну, возможно, это лишь строительные блоки, но ни как не решение. Сейчас всё зависит исключительно от компетентности конкретного программиста, разрабатывающего конкретную систему.

Дополнительные ссылки для интересующихся:

Фундаментальная работа на тему, почему процессоры *не* будут становится всё быстрее и быстрее, и что делать теперь:

The Landscape of Parallel Computing Research: A View from Berkeley

Если кто ещё не читал — популярные заметки Герба Саттера:

The Free Lunch Is Over

The Pillars of Concurrency

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?