Равномерное разделение смежных последовательностей чисел

Частая задача при параллельном распараллеливании N неприемлемо параллельных рабочих блоков между K работниками состоит в использовании следующего алгоритма для разделения в псевдокоде:

acc = 0
for _ in range(K):
    end = acc + ceil(N/K)
    emit acc:end
    acc = end

Это создаст K смежных раздела, как правило, размером N/K и отлично работает для больших N. Однако, если K приблизительно равно N, это может привести к дисбалансу, потому что последний работник получит очень мало предметов. Если мы определим дисбаланс как максимальную абсолютную разницу между размерами разделов, то оптимальным будет итеративный алгоритм, который начинается с любого случайного раздела и уменьшает потенциал до тех пор, пока максимальная разница не станет равной 1 (или 0, если K делит N).

Мне кажется, что следующее может быть более эффективным способом получить тот же ответ, выполнив «перепланирование» онлайн. Есть ли у этого алгоритма имя и доказательство оптимальности?

acc = 0
workers = K
while workers > 0:
    rem = N - acc
    end = acc + ceil(rem/workers)
    emit acc:end
    acc = end
    workers -= 1

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


parallel-processing partitioning algorithm
person VF1    schedule 01.01.2018    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Простой способ разделения диапазона:

for i in range(K):
  emit (i*N // K):((i+1)*N // K)

Это имеет то преимущество, что само по себе можно распараллелить, поскольку итерации не нужно выполнять по порядку.

Легко доказать, что каждый раздел имеет либо floor(N/K), либо ceil(N/K) элементов, и очевидно, что каждый элемент будет ровно в одном разделе. Поскольку пол и потолок отличаются не более чем на 1, алгоритм должен быть оптимальным.

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

Другой способ разделения диапазонов, который можно выполнять параллельно, — использовать диапазон start(N, K, i):start(N, K, i+1), где start(N, K, i) равен (N//K)*i + min(i, N%K). (Обратите внимание, что N//K и N%K нужно вычислить только один раз.) Этот алгоритм также оптимален, но распределяет дисбаланс так, что первые разделы являются большими. Это может быть или не быть полезным.

person rici    schedule 01.01.2018

arrow_upward
0
arrow_downward

Вот более простой подход. У вас есть floor(N/K) задачи, которые можно идеально распределить между рабочими, оставив N mod K оставшихся задач. Чтобы регионы были непрерывными, вы можете поместить оставшиеся задачи на первых N mod K рабочих.

Здесь в императивном стиле. Чтобы было ясно, я нумерую задачи {0..(N-1)} и выдаю наборы смежных номеров задач.

offset = 0
for 0 <= i < K:
  end = offset + floor(N/K)
  if i < N mod K:
    end = end + 1
  emit {c | offset <= c < end}
  offset = end

И в более декларативном стиле:

chunk = floor(N/K)
rem = N mod K

// i == worker number
function offset(i) =
  i * chunk + (i if i < rem else rem)

for 0 <= i < K:
  emit {c | offset(i) <= c < offset(i+1)}

Доказательство оптимальности на данный момент довольно тривиально. Работнику i назначено offset(i+1) - offset(i) задач. В зависимости от i это либо floor(N/K), либо floor(N/K) + 1 задач.

person Sam Westrick    schedule 01.01.2018