Эффективное параллелирование независимых задач

Question

У меня есть [; N;] рабочие единицы, [; w_n;], которые эффективно смущающе распараллеливаются. Каждый из них занимает приблизительно определенный отрезок времени, [; t_n;], который мы знаем заранее.

Учитывая, что мне нужно, возможно, потребуется обработать некоторое подмножество рабочих единиц и ограничение, что я могу использовать максимум [; P;] процессов, каждый на отдельных процессорах, как эффективно распределять рабочие единицы , заранее, к процессам, таким образом, чтобы все процессы заканчивались как можно ближе друг к другу (по времени)?

Answer 1

A) Если все они являются статистически одинаковыми, и вы не можете контролировать, как долго любой из них работает, я бы предположил, что в среднем вы не можете сделать лучше, чем «процессор при завершении работы блок, выполняет любую незавершенную рабочую единицу и выполняет ее до завершения ». Среднее время выполнения - это сумма (1..N, t_n)/P.

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

C) Если вы настаиваете на статическом расписании, выбранном заранее, запустите алгоритм B) в автономном режиме и предварительно назначьте рабочие единицы для процессов. Это, скорее всего, даст вам более длительное время автономной работы, чем динамическое расписание, что может в значительной степени учитывать фактическое изменение.