Заморочился таким вопросом. С каждым днем количество ядер в одном процессоре растет. Языки программирования требуют, чтобы программист сам распределял нагрузку на них. Предположим у нас имеется 4294967295 каких-то операций, нужно это операции распределить по всем ядрам. И я значит делю количество операций на количество ядер таким образом:



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

Во-первых, вы рассуждаете о технологиях будущего, насильно привязывая к ним технологию настоящего (овер9000 ядер и создание потоков циклами(имея очевидно ввиду, что цикл почему-то будет выполняться на одном процессоре)). Во-вторых, очень многие задачи (особенно когда речь идет математике, как в вашем примере, или цикла, который создаст тысячи потоков) отлично распараллеливаются автоматически. Итого: компилятор создает "массив задач" и дает команду процессору, который каждую из них пихает в ядро.

Про ОС я специально не упомянал, чтобы проще изложить мысль.

Наверное будет как-то так.

Если говорить о настоящем, то компилятор gcc 4.4.0 ничего не распараллеливает и долго выполняющийся цикл работает только на одном ядре, в итоге в диспетчере задач WindowsXP видна загрузка процессора 50% и один из двух графиков (по количеству ядер) работает на 100% в то время как другой ничего не делает. Если потоки создавать вручную через API ос, то все работает как надо. Если говорить о будущем, то вот эта новость заставляет уже задуматься: http://www.overclockers.ru/hardnews/22739.shtml



127 операций, которые нужно раскидать.

ИМХО все формулы лучше писать в символьном представлении, а потом делать (или не делать) пример, а то голова трещит от таких цифр.   
Если я правильно понял из 


(пытался понять первый пост, но получил вместо представления о вопросе еще гору вопросов и боль в голове)

вы приводите пример с 4294967295 задачами и 128 ядрами и получаете 127 задач как остаток.

Итак, если я правильно понял вопрос, то на основании того, что 33554431 >> 1 можно сделать вывод, что конкретный способ распределения оставшихся задач не имеет разницы.

ЗЫ Приведенная формула несколько наивна потому, что:
1) Мало таких областей, где все задачи обрабатываются за некоторое определенное и равное время.
2) Определить список задач, выполняемых за некоторое известное время и использовать его при распределении вычислений между ядрами будет довольно трудно в силу большого числа вариантов и наличия необходимости обслуживания такого алгоритма, сводящее увеличение производительности "на нет".

Для таких вычислений гораздо лучше масштабировать кластерную систему, чем многоядерную (ИМХО, т.к. проблема синхронизации).

SABROG, надумана проблема. Чего думать, как распределить остаток, если этот оставшийся объем действий (в данном случае) значительно меньше, чем объем действий, попадающий на каждый проц? На любой проц/ядро кинуть этот остаток - и ни выигрыша в скорости, ни проигрыша, ибо это копейки (повторяю - для указанного числа операций).

Да и распределять "равным" образом - вообще-то не всегда наилучший вариант. Т.к. какой-то проц/ядро притормозит из-за отсутствия данных в памяти, какой-то - из-за многозадачности операционки (которая к этому процу привяжет поток другой задачи), да и в самой программе в зависимости от значений данных потребуется или не потребуется пройти по каким-то веткам условий... Поэтому даже если абсолютно равно распределите - абсолютно одновременно все процы у вас закончат считать в очень и очень редком случае.
Я сам объем обрабатываемых данных по нескольким потокам жестко не делю - "индекс" следующего необработанного блока данных управляется через функцию InterlockedIncrement (мгновенно срабатывающую), потоки сами запрашивают с её помощью индекс след.блока для обработки, всё это приводит к тому, что добивающий остаток данных "запоздавший" поток (в отсутствии его притормаживания со стороны операционки) "запаздывает" именно на время, равное времени обработки ОДНОГО последнего куска данных.

"Новость" совершенно не заставляет задумываться. Запись датируется 2006 годом. Но с большой долей уверенности можно скзать, что к N-ому году, если не появится новой концепции построения процессоров, ядер таки станет 128. Только что об этом задумываться?

Хинт1: уже давным давно есть мультипроцессорные системы, софт под которые успешно пишется или берется готовый;
Хинт2: не знаю, как в gcc 4.4.0, но в 4.4.2 есть поддержка автоматизированной многопоточности openMP;
Хинт3: см. функциональные ЯП, не сиськами едины.

И самое главное! Размышления о gcc 4.4.0 просто превосходно подходят к вопросу "что будет через сто лет, когда может быть появится 2147483648-ядерный проц?!".

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

Моя цель в другом. Я хочу, чтобы программа использовала все доступные процессоры в системе, где бы она не выполнялась, поэтому хочу написать функцию, которая могла бы оперировать значениями типа x = количество операций, y = количество процессоров. На выходе хочу получать распределенный список. Запускать остаток от деления в отдельный (третий) поток не хочу. С моей точки зрения это не правильно, особенно при остатке меньше 10. Правильней - раскидать остаток на доступные процессоры.

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



Это всё-равно, что сказать выкинь исходники, которые писал последнюю неделю на Си++ и перепиши их на другом языке потому, что там есть вещь, которая сделает что-то за тебя. Меня сейчас интересует не работоспособность программы, она уже есть. Хочу оптимизации, потому эта тема скорее для математиков. Может быть есть у кого какая формула, которая даст распределение без топорной итерации и прибавления по одному, мало ли.

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

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

Это сообщение отредактировал(а) fry - 28.12.2009, 23:42

А это, вообще говоря, не такой плохой совет.   Писать подобные вещи на C++ дольше, чем выкинуть уже написанный код, разобраться с чем-нибудь более подходящим и написать на нем код "с нуля".

4 триллиона(!!!!!) процессоров, общего назначения, видимо потомков какого-нибудь Pentium-a или Athlon-a, а еще все они программируются вручную, код генерируется компилятором, используется task based параллелизм, автор - отсыпь  
да в современных процессорах транзисторов меньше на порядок

SABROG, я придерживаюсь идеи высказанной VictorTsaregorodtsev. Только я позволю ее немного переформулировать в классическую. Есть очередь задач. Есть N обработчиков, которые выполняют задачи. Как только обработчик свободен, он берет из очереди задачу и начинает ее выполнять. В итоге, происходит автоматическое оптимальное распределение задач по потокам. В худшем случае, N-1 поток будет ждать выполнения последней задачи одним потоком все время ее исполнения (т.е. когда все потоки завершатся одновременно, а в очереди будет только одна задача). Но это маловероятно.

Вот только Intel пока не в курсе   По моим данным работы над проектом ManyCore (именно к ним относились упомянутые процессоры) были свернуты где то года 2 назад.   

Как бы там ни было я написал свою функцию распределения нагрузки и она получилась такая:



Если будут предложения по оптимизации/усовершенствовании, то буду рад услышать.

bsa, это не худший случай, а банальный простой. 

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

Добавлено @ 00:17
Функторы сами по себе и задача и обработчик одновременно.

Это сообщение отредактировал(а) Леопольд - 30.12.2009, 00:21

SABROG, код у тебя не очень читабельный получился... Через пару недель сам будешь плеваться