Algorytmy równoważenia obciążenia i harmonogramowania

Question

, więc oto mój problem:

Mam kilka różnych serwerów konfiguracyjnych. Mam różne obliczenia (zadania); Mogę przewidzieć, ile czasu zajmie w przybliżeniu każde zlecenie, aby zostać zakwestionowanym. Mam także priorytety. Moje pytanie brzmi, jak zachować wszystkie maszyny załadowane w 99-100% i zaplanować zadania w najlepszy sposób.

Każda maszyna może wykonać kilka obliczeń naraz. Zadania są przekazywane do urządzenia. Centralna maszyna zna aktualne obciążenie każdej maszyny. Chciałbym również przypisać tutaj pewien rodzaj uczenia maszynowego, ponieważ będę znał statystyki każdego zadania (uruchamianie, kończenie, ładowanie cpu itd.).

Jak mogę dystrybuować zlecenia (obliczenia) w najlepszy możliwy sposób, pamiętając o priorytetach?

Wszelkie sugestie, pomysły lub algorytmy?

FYI: Moja platforma .NET.

Answer 1

Wygląda na to, że ma to niewiele wspólnego z .NET.

Uważaj jednak swoje maszyny za "wątki robocze", stwórz "pulę" dostępnych maszyn zamówionych na dostępnym procesorze (lub innym ważnym zasobie), a następnie wykorzystaj swoją wiedzę o każdym zadaniu, aby przekazać każde zadanie do najlepiej dopasowanej maszyny .

Jeśli znasz wszystkie zlecenia z góry, prawdopodobnie możesz użyć algorytmu "najlepszego dopasowania", aby zaplanować je we właściwej kolejności na właściwych urządzeniach. Można również przyjrzeć się algorytmom "cięcia zapasów"; http://en.wikipedia.org/wiki/Cutting_stock_problem ...

Answer 2

1. Spójrz na Dryad linq. Jest już w akademickim wydaniu i może być przydatne.
2. Win HPC server - rozwiązanie dla przedsiębiorstw do przetwarzania rozproszonego firmy Microsoft.
3. Niektóre code samples, które mogą pomóc w budowaniu równoważenia obciążenia poprzez analizowanie liczników wydajności.
4. Microsoft ma StockTrader przykładową aplikację (ze źródłami), która jest przykładem dystrybuowalnego architektury SOA z odręcznym równoważeniem obciążenia RoundRobin.

Answer 3

Firma Microsoft opublikowała niedawno na swoim harmonogramie quincy numer paper. Jeśli po prostu optymalizujesz wykorzystanie procesora, to bardzo prosty solver może znaleźć optymalne rozwiązanie. Jeśli potrzebujesz optymalizacji na więcej osi, to oczywiście przestrzeń problemu będzie bardziej skomplikowana.

Jak duża jest twoja gromada? Jak radzisz sobie z optymalizacją w przypadku awarii? Czy to ważne? Czy jest IO? Czy dane mają powinowactwo dyskowe? Czy istnieje więcej niż jedno miejsce do prowadzenia pracy? Wszystkie rzeczy do rozważenia.

Answer 4

Jako alternatywne podejście można użyć szacunków maksymalnego współczynnika wydajności każdego komputera do planowania zadań. Może to być bardzo skuteczne tylko wtedy, gdy rozważasz wydajność runtime CPU systemu równoważonego obciążeniem. Zagadnienia związane z I/O, rozmiarem klastra, wydajnością sieci, typami modelu pamięci itp. Są zaniedbywane dzięki temu podejściu. Rzuć okiem na: http://dx.doi.org/10.1145/1513895.1513901

Propozycją dla bardziej dokładnego (bliskiego obciążeniu obciążenia dystrybucji) podejścia będzie algorytm - architektura zależna od komputera. W takim przypadku zadanie o wyższym priorytecie można zaplanować na najlepszy serwer spełniający jego wymagania - ale najpierw należy określić optymalne odwzorowanie zadań na serwerze.Można również zastosować pewne metody algorytmów szeregowania OS na wieloprocesorach (nie jednoprocesorowych). Mam nadzieję, że okaże się to pomocne.