Оценка загрузки

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

В основном такая база данных состоит из двух типов данных:

- Данные о работе процессора (информация уровня процессора). Эти данные включают: загрузку процессора, время простоя процессора, фоновую загрузку процессора, скорость передачи информации по линиям связи и т.д.

- Данные о работе распределенного приложения. Данные включают время выполнения отдельной задачи, время простоя, интенсивность обмена информацией и т.д.

Очень важно владеть такой информацией как коммуникационная модель.

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

Необходимо учитывать два типа связей между объектами: двухточечные коммуникации и коллективные коммуникации.

При распределении задач между процессорами производится оценка коммуникаций. Затраты на двухточечную связь между двумя задачами могут быть определены через объем передаваемых данных (b – объём сообщений в байтах) и частоту коммуникации (n – количество сообщений за единицу времени). Используя величины затрат процессора на каждое сообщение и каждый байт, можно оценить общие затраты на коммуникацию между двумя задачами: a * n + b* b, где b – общий объем всех n сообщений.

Оценка загрузки процессора и объекта может быть произведена несколькими способами. Один из способов (аналитический), обычно используемый при статической балансировке загрузки и состоит в приблизительной оценке загрузки каждого объекта на основе знаний о приложении. К этим знаниям относятся:

- функция от размера объема данных, отражающая сложность алгоритма

- модель коммуникаций между задачами.

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

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

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