Здравствуйте.

Представляю вам свой ответ на многопоточность. Ознакомится можно здесь http://groups.google.com/group/asynclib?hl=en
В кратце библиотека представляет из себя микс между TBB (где работа task'ифицируется через интеловские примитивы и выполняется на фиксированном количетсве рабочих потоков) и windows threads (где каждый поток имеет свой контектс, который OS в любой момент может сменить на контекст другого потока). В терминологии создателя данной темы получается «многопоточность с кооперативной многозадачностью».
Другими словами, вы вашу работу разбиваете на задачи (чтение из файла/сокета, обработка чего-либо другого — без ограничений здесь), чем меньше гранулярность, тем лучше (поскоку распаллелизовываться будет лучше). Тело задачи не имеет ограничений, кроме одного условия — необходимо использовать примитивы синхронизации предоставленные библиотекой (использование стандартных примитивов не воспрещается). Далее, когда рабочий поток выполняя одну из ваших задач натыкается на блокирующее условие (например — мутекс залочен другой задачей, или ввод/вывод еще не закончился) рабочий поток автоматически переключается на следующую задачу из вашего списка задач, обеспечивая тем самым максимальный throughput ваших задач на заданном количестве рабочих потоков.

Из плюсов данного подхода можно отметить следующие:
— автоматическое скалирование на многоядерных машинах
— уменьшение времени синхронизации задач (так как происходит смена более легковесного контекста задачи, в отличие от контекста потока) и уменьшение contention'а ваших данных (поскоку в любой момент выполняется количество задач не большее чем количество рабочих потоков)
— в целом классе задач отпадает необходимость писать стейтмашины (в данном случае стейт сохраняется вместе с контекстом вашей задачи)
— более легковесные примитивы синхронизации чем нативные (самый маленький примитив занимает 2 бита)


Eсли есть вопросы, пишите.





Здравствуйте, remark, Вы писали:

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

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

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

Автор: remark
Дата: 20.09.07

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

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

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

R>Сейчас наиболее общий рецепт выглядит примерно следующим образом:
R> — Создать кол-во потоков по кол-ву аппаратных потоков. Как следствие — кол-во потоков не должно быть «зашито» в программу, т.к. она может выполняться на разных платформах. И как второе следствие – управление кол-вом потоков не должно быть заботой прикладного программиста (ну по крайней мере того же программиста, но когда он играет роль прикладного ).
R> — Работа должна быть распределена по потокам [примерно] равномерно. Соотв. это тоже не получится зашивать в программу и поручать прикладному программисту, т.к. кол-во потоков и кол-во и содержание работы меняться.
R> — Нельзя экстенсивно применять мьютесы/синхронизацию/блокировки. Т.к. это фактически заставит систему сериализоваться и выполняться «на одном ядре». Ни о какой масштабируемости тут не может быть и речи.
R> — По возможности надо элиминировать разделяемые данные. Совместная работа над одними модифицируемыми данными сейчас работает ооочень медленно и становится одним из важнейших новых боттлнеков аппаратной платформы, на ряду с тактами ядра, шиной к памяти, диском, сетью. И никаких изменений в лучшую сторону тут не предвидится. Только в худшую. (Это не относится к константным данным, их можно и нужно разделять между потоками)

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

R>Естественно могут иметь место и частные случаи. Например, приложение по обработке изображений или CAD/CAM/CAE/CASE. Тут скорее всего имеет смысл эффективно распараллеливать только одну основную функцию, например, обработку изображения, или рассчёт параметров модели (все остальные функции — графический интерфейс, фоновые задачи — по прежнему могут быть реализованы по старым принципам). Тут сейчас ситуация обстоит немного лучше. Тут (и только тут) на помощь могут придти такие средства как OpenMP, RapidMind, Intel TBB, Java Fork/Join и тд.:
R>www.openmp.org
R>www.rapidmind.com
R>osstbb.intel.com
R>gee.cs.oswego.edu/dl/papers/fj.pdf
R>К сожалению все эти средства подходят для очень ограниченного круга задач, и не подходят для реализации более общих и не типовых задач. И всё равно они не снимают с программиста основной задачи — что конкретно и как конкретно должно быть распараллелено. Это по прежнему должен решать программист, и он по прежнему должен обеспечить достаточное кол-во потенциального параллелизма, возможность для независимой работы потоков без разделяемых данных и т.д.

R>Есть ещё 2 вещи стоящие упоминания в данном контексте: готовые высокооптимизированные библиотеки и автоматическое распараллеливание кода.

R>Для решения типовых задач имеется ряд высокооптимизированных библиотек. Например можно посмотреть на:
R>Intel Integrated Performance Primitives (IPP):
R>http://www.intel.com/cd/software/products/asmo-na/eng/219767.htm
R>И AMD Performance Library (APL):
R>http://developer.amd.com/apl.jsp
R>Задачи, которые они могут решать включают:
R> — обработка/кодирование/декодирование видео
R> — обработка/кодирование/декодирование изображений
R> — обработка/кодирование/декодирование аудио
R>- операции над матрицами/векторами/строками
R>и т.д.
R>Понятно, что на общее решение такие библиотеки не тянут. Однако, если решаемая задача укладывается в возможности библиотеки, то имеет большой смысл применять такую библиотеку (Intel — платная, AMD — бесплатная).

R>Автоматическое распараллеливание кода.
R>Здесь не на что смотреть! Проходите, не задерживаетесь!
R>Сейчас автоматические распараллеливатели могут очень мало и очень конкретного. И вам всё равно придётся убеждаться, что распараллелилось то, что надо, так, как надо, и оно не ломается при последующих модификациях кода (напоминает борьбу с оптимизатором БД ). Фактически правильнее считать, что автоматического распараллеливания кода *нет*. Сейчас и в ближайшую декаду. Если кто-то утверждает обратное, то он либо не разбирается в вопросе, либо хочет вам что-то продать
R>За подробностями смотрите интервью с Джеем Хоефлингером, который занимается автоматическим распараллеливанием с середины 80:
R>http://www.thinkingparallel.com/2007/08/14/an-interview-with-dr-jay-hoeflinger-about-automatic-parallelization/


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


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

R>Фундаментальная работа на тему, почему процессоры *не* будут становится всё быстрее и быстрее, и что делать теперь:
R>The Landscape of Parallel Computing Research: A View from Berkeley

R>Если кто ещё не читал — популярные заметки Герба Саттера:
R>The Free Lunch Is Over
R>The Pillars of Concurrency
R>How Much Scalability Do You Have or Need?

R>OpenMP Does Not Scale — Or Does It?. В очень забавной форме показываются проблемы, связанные с написанием параллельных программ.

R>How-to Split a Problem into Tasks. Как выявлять параллелизм в системе (подходит в основном для HPC).

R>Ещё интересные заметки Michael Suess:
R>Is the Multi-Core Revolution a Hype?
R>Moore’s Law is Dead — Long Live Moore’s Law!
R>How Much of the Industry Will Go Parallel?
R>Parallel Programming is Entering the Mainstream — or isn’t it?


R>