Распределение нагрузки - Рандомизированные алгоритмы

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

Задача

В некоторой системе m заданий поступают в потоковом режиме для немедленной обработки. Имеется группа из n идентичных процессоров, способных выполнять задания; требуется связать каждое задание с некоторым процессором так, чтобы равномерно распределить нагрузку между процессорами. Если в системе имеется центральный контроллер, который получает задания и передает их процессорам по кругу, он позволяет тривиально гарантировать, что за каждым процессором будет закреплено не более [m/n] заданий, — самое равномерное возможное распределение.

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

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

Анализ случайного распределения заданий

Как вы вскоре увидите, анализ процесса случайного распределения нагрузки зависит от относительных размеров m (количество заданий) и n (количество процессоров). Начнем с самого простого случая: m = n. На каждый процессор может быть назначено ровно одно задание, хотя это и маловероятно. Скорее всего, на некоторых процессорах заданий вообще не будет, а на других их будет несколько. Для оценки качества этой эвристики рандомизированного распределения нагрузки стоит проанализировать, сколько заданий может быть закреплено за процессором.

Обозначим X_i случайную переменную, равную количеству заданий, назначенных на процессор i (для i = 1, 2, ..., n). Ожидаемое значение X_i определяется легко; пусть Y_ij — случайная переменная, которая равна 1, если задание j назначено на процессор i, и 0 в противном случае. Тогда и а следовательно, Но нас интересует, насколько X_iможет отклониться выше своего ожидания: какова вероятность того, что X_i > с? Чтобы определить верхнюю границу, можно применить (13.42): X_i представляет собой сумму независимых случайных переменных {Y_ij}, принимающих значения 0 и 1; имеем μ = 1 и 1 + δ = с. Следовательно, следующее утверждение истинно.

Чтобы вероятность того, что какие-либо X_i превысят с, мы вычислим границу объединения по i = 1, 2, ..., n; следовательно, с необходимо выбрать достаточно большим, чтобы опустить Рr[Х_i > с] ниже 1/n для каждого i. Для этого необходимо рассмотреть знаменатель с^с в (13.44). Чтобы знаменатель был достаточно большим, необходимо понять, как эта величина растет с с; и для этого мы сначала зададимся вопросом: каким должно быть х, чтобы выполнялось x^х = n?

Предположим, такое число х будет обозначаться γ(n). Для γ(n) не существует выражения в замкнутой форме, но его асимптотическое значение можно определить следующим образом. Если x^х= n, то при взятии логарифма получаем х log х = log n; повторное взятие логарифма дает log х + log log х = log log n. Следовательно, имеем

2 log х > log х + log log х = log n > log х,

Используя это выражение для деления равенства х log х = log n, получаем

Таким образом,

Если теперь выбрать c = e γ(n), то из (13.44) следует

Итак, применение границы объединения к этой верхней границе для X₁, X₂, ..., X_n дает следующее утверждение:

(13.45) С вероятностью не менее 1 – n^-1 ни один процессор не получит более заданий.

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

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

Увеличение количества заданий

Границы Чернова помогут обосновать, что с введением в систему новых заданий нагрузка быстро “сглаживается”: количество заданий на разных процессорах быстро выравнивается в пределах постоянных множителей.

А конкретно, при m = 16n ln n заданий ожидаемая нагрузка на процессор составит μ = 16 ln n. Используя (13.42), мы видим, что вероятность превышения нагрузки любого процессора величины 32 ln n не превышает

Кроме того, вероятность того, что нагрузка любого процессора окажется ниже 8 ln n, не превышает

Применяя границу объединения, приходим к следующему результату.

(13.46) В системе с n процессорами и Ω(n log n) заданиями нагрузка на каждый процессор с высокой вероятностью находится в диапазоне от половины до удвоенной средней.