Многопроцессность vs Многопоточность и с чем их едят

>Какая именно информация требуется?

Собственно, оригинальное техзадание, со всеми вытекающими.

>Я прекрасно понимаю, что универсального решения не существует. А вот оптимальное существовать должно.

Несомненно.

К сожалению я не могу предоставить полное техзадание, тк оно - коммерческая тайна, а начальство на ЛОР иногда заходит пофлудить, тк БСДшники. Но скажу сразу. Оригинальное техзадание почти не содержит информации по выполняемой задаче (кроме платформы), но там присутствует некоторая математика, которая уже является собственностью предприятия. В основном описание самой задачи - крайне абстрактное, т.е. на уровне идеи с небольшим математическим обоснованием (и то, и другое - коммерческая тайна).

Как вариант - могу выложить псевдокод тестовой программы, но только в понедельник, тк отслеживается вынос информации с работы.

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

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

>Как вариант - могу выложить псевдокод тестовой программы, но только в понедельник, тк отслеживается вынос информации с работы.

Чисто на твоё усмотрение. Разумеется, было бы интересно, но.. Ты сам понимаешь.

> чтобы в понедельник либо извиниться перед начальником, либо стоять до последнего, доказывая, что его методика неоптимальна.

Тогда у тебя есть целый день на то, чтобы "распараллелить внешний цикл" (вручную или OpenMP). Если загрузишь ядра процентов на 50 - это уже доказательство твоей правоты.

И нужно таки выяснить, почему начальство хочет именно процессы - они ветераны ИНМОС, или знают больше, чем говорят?

>У меня только один вопрос - вы написали, что для ~1000 - 10000 операций с интами даже не стоит и думать о вызове OpenMP

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

В вашем случае, допустим 5е5 операций, 16 нитей, -> ~3e4 операций достанется каждому ядру, что весьма сопоставимо с накладными расходами. Лучше конечно такой анализ проведите сами, я всех подробностей вашего кода не знаю, но принцип оценки примерно такой(см. далее).

>свёртка ~10000 элементов вектора с некоторым одномерным ядром - это не 1е4 операций, а не менее 1е5 и вплоть до 5е5 операций в зависмости от ядра свёртки.

Вот это кстати весьма неплохо в контексте переиспользования памяти. Возможно с ускорением вам более-менее повезет.

>Может, вы посоветуете литературу по данному вопросу (параллелизму и его теории)

Тут врядли особо много могу посоветовать(wikipedia/дока по выбранной технологии), наиболее важное с точки зрения применимой теории - закон Амдала, а точнее такого рода анализ своего кода. Просто как 2 копейки, но весьма применимо при анализе выдачи профайлера(использую valgrind, конкретнее callgrind/cachegrind). Очень советую вам поработать с valgrind-ом, он поможет понять какие функции у вас дороги и позволит контроллировать долю последовательных вычислений, фигурирующую в законе Амдала.

Хорошие статьи из википедии:

http://en.wikipedia.org/wiki/Amdahl's_Law

http://en.wikipedia.org/wiki/Parallel_programming

http://en.wikipedia.org/wiki/Data_parallelism

http://en.wikipedia.org/wiki/Message_Passing_Interface

http://en.wikipedia.org/wiki/OpenMP

> Простите за оверквотинг, но ещё один вопрос, если таки выяснится, что мы сможем уложиться в нужное время с использованием одного узла, то каковы будут ваши рекоммендации?

Imho в вашем случае скорее OpenMP, с меньшим приоритетом TBB.

немного офтоп.

если бы не было обязательного требования - фряха с указаным железом - то как вариант GPGPU (http://en.wikipedia.org/wiki/GPGPU и http://www.gpgpu.org/). У NVidia - есть платформа CUDA - которая позволяет выполнять задачи, которые хорошо паралелятся, на видеокартах последних серий (там не 4 процессора, а несколько сотен, но упрощенной RISC архитектуры).

Например: http://www.gpgpu.org/cgi-bin/blosxom.cgi/Scientific%20Computing/index.html

Также у Nvidia есть специальный мини-суперкомпьютер Tesla (http://www.nvidia.com/object/personal_supercomputing.html). еную

На одном из форумов читал, что математики пытались использовать и добивались отличных результатов.

Так, что если поставленую задачу не сможите решить на тех условиях, что указало начальство - посмотрите в эту сторону.

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

(вероятно, в openMP можно как-то указать "не использовать потоки вообще", и делать всё одним потоком).

У вас 4 ядра. Во сколько раз увеличилась производительность при включении openMP?

По личному опыту могу сказать, что скалярное произведение векторов начинает параллелиться в лучшем случае с размера векторов 1e5. На машине 2x4core Xeon 5462 2.8GHz и ускоряется не более, чем 2.5 раза. Просто память быстрее не работает.

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

Кластер и MPI вам помогут только, если будет мало обменов и ваш алгоритм действительно хорошо параллелится.

Больше потоков чем есть ядер не нужно.

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

Если не кластер то лучше все таки оставаться в общей памяти - следовательно потоки тут больше подходят чем процессы.

Возникла мысль, что начальство возможно намекало использовать fork - что может оказаться неплохим вариантом.

Я слегка погуглил на тему fork, но не понял, почему высчитаете этот вариант неплохим. Поясните пожалуйста.

Попытаюсь завтра выложить. Псевдокод написан на матлабе. Сможете разобраться или привести его в более понятный вид?

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

Завтра после кровопролитной битвы на моём докладе по данному вопросу, надеюсь, решение будет вынесено в мою пользу.

> Возникла мысль, что начальство возможно намекало использовать fork - что может оказаться неплохим вариантом.

О, еще один "процессник". Объясни, чем процессы хороши (или даже лучше нитей)?

~4-5 раз. Т.е., как по мне, прирост существенный.

Кстати, случайно узнал в интернете, возможную причину, почему начальство так стоит горой за многопроцессность и всё оказалось просто. Мы заранее предупреждали, что FreeBSD - далеко не самое оптимальная система для решения нашей задачи, тк есть проблемы с софтом и ФС (раз мы потеряли работу за 2 дня, тк редко бэкапились и не было ещё SVN, а потом, при неожиданном выключении компьютера одного из программистов данные просто исчезли и никакими средствами их наши админы возвратить не сумели). Так вот, возможно, что ратование за процессы происходит, тк FreeBSD обеспечивала возможность работы только с процессной моделью (unix BSD обеспечивает только еёё, а фряха, если я правильно понимаю - преемница, поэтому сейчас гуглю на этот счёт).

Кстати, распараллелили внешний цикл чуточку. Ускорение в 3 раза есть точно.

Ещё вот такой вопрос возник: "Если использовать гибридную технологию OpenMP + MPI, то это что-нибудь даст?"

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

Про FreeBSD не очень давно пробегала новость вида "до 7.0 с нитями все было совсем плохо, теперь - совсем хорошо", так что возможно действительно с этим связана позиция начальства.

Про гибридную модель могу сказать, что она предназначена для тех случаев когда с одной стороны для уменьшения обменов приходится заранее распределять данные и работу по процессорам(данных много, потом не перекинешь) а с другой стороны заранее предсказать сложность алгоритмов на каждом из процов не получается(сложность зависит не только от кол-ва входных данных но и от их значений). В таком случае имеет смысл заранее все распределить по узлам кластера с использованием MPI(1 процесс на узел), а внутри каждого узла использовать OpenMP и динамическое распределение работы по потокам. В вашем случае - не знаю насколько предсказуемы затраты при распределении данных(например следует ли из равного кол-ва строк матрицы отданного 2 процессам что время расчета на них будет одинаково?). Если такой проблемы нет - достаточно одной технологии.

Да. При равном количестве строк матрицы, отданным 2м процессам, время расчёта на них будет приблизительно одинаковым.

Ага. Это всё равно кластер нужен. Я очень надеюсь, что без него получится обойтись)

Но на всякий случай буду иметь в виду.

Джаст 2 цента, сумбурно.

Силиконовская нума которая альтикс позволяет иметь нити(и естественно процессы) на сотнях и тысячах процессоров. Такой гибрид mpi кластера и SMP.

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

цикл внутри которого обрабатываается кадр - стандартное место если надо паралелить обработку, а на уровень выше кадра (те по процессору на кадр) алгоритм выйти не дает.

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

>> У вас 4 ядра. Во сколько раз увеличилась производительность при включении openMP?

> ~4-5 раз.

> Кстати, распараллелили внешний цикл чуточку. Ускорение в 3 раза есть точно.

это как, 4 ядра ускорили программу в 12-15 раз?! Хотел бы я посмотреть на такую программу ;)

>О, еще один "процессник". Объясни, чем процессы хороши (или даже лучше нитей)?

Процессы не лучше, но fork быстр из за copy-on-write. Возможно он тут подойдет.

ИМХО, из-за copy-on-write fork и сольёт многопоточности. Каждый copy-on-write это page fault с переключение в контекст ядра, поиском свободной страницы и т.д. Задача счётная, ИМХО, там много памяти нужно под промежуточные результаты.

Автору топика не позавидуешь, фактически выбор многопоточность/многопроцессность должен быть сделан в техзадании, а ещё начальство, которое знате как нужно делать, и программисты, которые знаю что нужно делать по-другому :)

Но не быстрее потока, ибо там даже копи-он-врайт нет.
P.S. В BSD тоже копи-он-врайт?

> Псевдокод написан на матлабе. Сможете разобраться или привести его в более понятный вид?

Сможем.

Дык а кто заставляет писать результат в ту же память?

Я так понимаю что есть большой массив входных данных - каждый процесс берет себе из них некоторую часть и делает свою часть расчетов - потом через какое то IPC отдает главному что насчитал - и главный процесс мержит это все в конечные выходные данные.

При это с форком входные данные не будут копироватся так как читаются только. Промежуточные данные у всех свои. А результат собирает один процесс без всяких page fault'ов.

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

> При это с форком входные данные не будут копироватся так как читаются только. Промежуточные данные у всех свои. А результат собирает один процесс без всяких page fault'ов.

С page fault'ами. Флеймили уже об этом: http://www.linux.org.ru/jump-message.jsp?msgid=3424009&cid=3432116

Создание нити в любом случае быстрее. Другое дело, что в данном случае это неважно :)