Алгоритмы балансировки нагрузки и планирования

Question

так вот моя проблема:

У меня есть несколько разных конфигурационных серверов. У меня разные расчеты (задания); Я могу предсказать, как долго будет выполняться примерно каждая работа. Кроме того, у меня есть приоритеты. Мой вопрос заключается в том, как сохранить все машины, загруженные на 99-100%, и запланировать работу наилучшим образом.

Каждая машина может выполнять несколько расчетов за раз. Задания переносятся на машину. Центральная машина знает текущую нагрузку каждой машины. Кроме того, я хотел бы задать здесь какое-то машинное обучение, потому что я буду знать статистику каждой работы (начатую, завершенную, загрузку процессора и т. Д.).

Как я могу распределить рабочие места (расчеты) наилучшим образом, учитывая приоритеты?

Любые предложения, идеи или алгоритмы?

FYI: Моя платформа .NET.

Answer 1

Похоже, что это очень мало связано с .NET.

Но подумайте о своих машинах как «рабочих потоках», создайте «пул» доступных машин, заказанных на доступном CPU (или другом важном ресурсе), а затем используйте свои знания о каждой задаче, чтобы подтолкнуть каждую работу к наилучшей оборудованной машине ,

Если вы знаете все задания заранее, вы, вероятно, можете использовать алгоритм «наилучшего соответствия», чтобы запланировать их в правильном порядке на правильных машинах. Вы также можете посмотреть алгоритмы «режущего инструмента»; http://en.wikipedia.org/wiki/Cutting_stock_problem ...

Answer 2

1. Посмотрите на Dryad linq. Это уже в академическом выпуске и может быть полезным.
2. Win HPC server - корпоративное решение для распределенных вычислений от Microsoft.
3. code samples, который может помочь в построении балансировки нагрузки путем анализа счетчиков производительности.
4. Microsoft имеет StockTrader образец приложения (с источниками), который является примером распространяемой SOA с ручной балансировкой нагрузки RoundRobin.

Answer 3

Microsoft недавно опубликовала paper на своем планировщике quincy. Если вы просто оптимизируете использование ЦП, то очень простой решатель может найти глобальный оптимум. Если вам нужна оптимизация по большему количеству осей, то, очевидно, проблемное пространство будет более сложным.

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

Answer 4

В качестве альтернативного подхода вы можете использовать оценки максимального значения производительности каждой машины для планирования заданий. Это может быть очень эффективным только в том случае, если вы рассматриваете производительность выполнения системы с балансировкой нагрузки. С этим подходом пренебрегают вопросами, касающимися ввода-вывода, размера кластера, производительности сети, типа модели памяти и т. Д. Взгляните на http://dx.doi.org/10.1145/1513895.1513901

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