Добрый день.

Есть набор заданий. Заданий конечное число. Время выполнения задания зависит от его номера. Чем больше номер, тем меньше выполняется задание. Зависимость времени выполнения задания от номера – прямолинейная. Параметры прямой заранее не известны.

Как этот факт можно использовать для балансировки нагрузки процессоров при распараллеливании подобной задачи?

Пока задания выдаю динамически: как только какой-то процессор закончил считать, получает следующее задание (если оно есть). При этом ускорение ведет себя «не очень»: при 4 процессорах всего в два раза.

Стоит ли смотреть, например, в сторону Guided из Open MP?

Если это общеизвестная проблема, буду признателен за какие-либо ссылки.

Здравствуйте, Аноним, Вы писали:

А>Пока задания выдаю динамически: как только какой-то процессор закончил считать, получает следующее задание (если оно есть). При этом ускорение ведет себя «не очень»: при 4 процессорах всего в два раза.

Интересно. По идее процессоры не простаивают, всё время делают что-то полезное. Если исключить издержки многопроцессорности и синхронизации, сосредоточившись на планировании, то единственная возможная причина, которую я вижу -- после того, как заканчиваются задания, остаётся длинный "хвост" на одном из процессоров. Но этот хвост не длиннее времени выполнения одного задания. И при этом уменьшается эффективность в два раза? Странно.

Так что я думаю дело всё же в издержках.

Здравствуйте, Аноним, Вы писали:

А>Добрый день.

А>Есть набор заданий. Заданий конечное число. Время выполнения задания зависит от его номера. Чем больше номер, тем меньше выполняется задание. Зависимость времени выполнения задания от номера – прямолинейная. Параметры прямой заранее не известны.

А>Как этот факт можно использовать для балансировки нагрузки процессоров при распараллеливании подобной задачи?

Задания зависят друг от друга?

Здравствуйте, <Аноним>, Вы писали:

А>Есть набор заданий. Заданий конечное число. Время выполнения задания зависит от его номера. Чем больше номер, тем меньше выполняется задание. Зависимость времени выполнения задания от номера – прямолинейная. Параметры прямой заранее не известны.
А>Как этот факт можно использовать для балансировки нагрузки процессоров при распараллеливании подобной задачи?

Т.к. пропорции времени выполнении всех заданий известны, то можно заранее спланировать работу.

1. Посчитаем среднее время работы процессора: сумма заданий / количество процессоров
2. Распределяем работу, чтобы каждому процессору достались задачи, общее время котороых равно п.1. Здесь возможны вариант, вот самый простой:
бежим по списку заданий — отдаем работы некоторому процессору пока их общее время не превысит среднего, затем переходим к следующему.
3. Выполняем выделенные работы для каждого процессора.

Дополнительные издержки только один раз в самом начале — на планирование работы.

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

B>Задания зависят друг от друга?

Нет, не зависят

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

Б>Т.к. пропорции времени выполнении всех заданий известны, то можно заранее спланировать работу.
...
Б>Дополнительные издержки только один раз в самом начале — на планирование работы.

В общем случае — погружение графа заданий в заданную архитектуру.

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

SH>Интересно. По идее процессоры не простаивают, всё время делают что-то полезное. Если исключить издержки многопроцессорности и синхронизации, сосредоточившись на планировании, то единственная возможная причина, которую я вижу -- после того, как заканчиваются задания, остаётся длинный "хвост" на одном из процессоров. Но этот хвост не длиннее времени выполнения одного задания. И при этом уменьшается эффективность в два раза? Странно.

SH>Так что я думаю дело всё же в издержках.

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

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

SH>Интересно. По идее процессоры не простаивают, всё время делают что-то полезное. Если исключить издержки многопроцессорности и синхронизации, сосредоточившись на планировании, то единственная возможная причина, которую я вижу -- после того, как заканчиваются задания, остаётся длинный "хвост" на одном из процессоров. Но этот хвост не длиннее времени выполнения одного задания. И при этом уменьшается эффективность в два раза? Странно.

Зависимость не точно прямолинейная, времена выполнения заданий «скачут» относительно прямой.

Здравствуйте, Аноним, Вы писали:

SH>>Интересно. По идее процессоры не простаивают, всё время делают что-то полезное. Если исключить издержки многопроцессорности и синхронизации, сосредоточившись на планировании, то единственная возможная причина, которую я вижу -- после того, как заканчиваются задания, остаётся длинный "хвост" на одном из процессоров. Но этот хвост не длиннее времени выполнения одного задания. И при этом уменьшается эффективность в два раза? Странно.

А>Зависимость не точно прямолинейная, времена выполнения заданий «скачут» относительно прямой.

А какая разница? Моё замечание остаётся в силе в общем виде. В данном случае есть только одна форма неэффективности: процессор простаивает или занимается чем-то другим. При динамическом распределении заданий процессоры не простаивают, за исключением момента, когда все ждут последнего. Значит либо слишком долго ждут, либо слишком много занимаются другим.

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

Б>Т.к. пропорции времени выполнении всех заданий известны, то можно заранее спланировать работу.

Б>1. Посчитаем среднее время работы процессора: сумма заданий / количество процессоров
Б>2. Распределяем работу, чтобы каждому процессору достались задачи, общее время котороых равно п.1. Здесь возможны вариант, вот самый простой:
Б>бежим по списку заданий — отдаем работы некоторому процессору пока их общее время не превысит среднего, затем переходим к следующему.
Б>3. Выполняем выделенные работы для каждого процессора.

Б>Дополнительные издержки только один раз в самом начале — на планирование работы.

Примерно так я и делал, когда точно знал параметры прямой (т.е. сначала определял время выполнения каждого задания в последовательном алгоритме, а потом его уже распараллеливал).

Возможно я Вас не понял, но каким образом это можно сделать, если я не знаю параметры прямой?

Здравствуйте, <Аноним>, Вы писали:

Попробуй самый тупой метод:
Случайно перемешай все задания и раздай процессорам поровну.
Если заданий много получишь весьма равные части.

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

WH>Здравствуйте, <Аноним>, Вы писали:

WH>Попробуй самый тупой метод:
WH>Случайно перемешай все задания и раздай процессорам поровну.
WH>Если заданий много получишь весьма равные части.

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

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

PD>С, может быть, не слишком вероятными, но довольно крупными выбросами. Я не математик, так что пусть лучше математики скажут, какое здесь распределение и какое у него может среднеквадратичное отклонение получиться и какова его вероятность.
Худший случай это когда процессору достанутся все самые тяжолые задания.
В прочем это можно легко исключить разбив не на N (число процессоров) частей, а скажем на 16 * N.
Получение очередной партии задач один InterlockedIncrement.

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

PD>>С, может быть, не слишком вероятными, но довольно крупными выбросами. Я не математик, так что пусть лучше математики скажут, какое здесь распределение и какое у него может среднеквадратичное отклонение получиться и какова его вероятность.
WH>Худший случай это когда процессору достанутся все самые тяжолые задания.

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

WH>В прочем это можно легко исключить разбив не на N (число процессоров) частей, а скажем на 16 * N.
WH>Получение очередной партии задач один InterlockedIncrement.

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