Описание проекта

Home
Описание проекта
Участники проекта
Текущее состояние
Документы

Задача балансировки загрузки

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

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

Для NP-полных задач существует немало приближенных методов решения, но все эти методы приемлемы лишь для некоторых частных случаев.

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

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

В рамках данного проекта предполагается построение системы распределения и перераспределения заданий для многомашинного вычислительного кластера, установленного в центре распределенных вычислений (к.312 главного корпуса НГУ). В настоящее время программное обеспечение кластера не предполагает переноса заданий с одной машины на другую; идут поиски решений, которые могли бы обеспечить возможность такого переноса. Главной проблемой при таком переносе оказывается воссоздание связей (TCP соединений), при помощи которых задание обменивается данными с другими процессами. .

Вернуться наверх

Copyright or other proprietary statement goes here.
For problems or questions regarding this web contact [Web Master].
Last updated: 20 Января, 2005.