Víceprocesorové plánování - Multiprocessor scheduling

v počítačová věda, multiprocesorové plánování je optimalizační problém zahrnující plánování výpočetních úloh v a víceprocesorový životní prostředí.[1] Prohlášení o problému zní: „Vzhledem k množině J pracovních míst, kde práce ji má délku li a řada procesorů m, jaký je minimální možný čas potřebný k naplánování všech úloh v J na m procesory tak, aby se žádné nepřekrývaly? "[2] Problém se často nazývá minimální problém s výrobou: makespan plánu je definován jako čas, který systému trvá, než dokončí všechny procesy, a cílem je najít plán, který minimalizuje výrobní náklady. Problém má mnoho variant.

Algoritmy

V nejjednodušším případě jsou to procesory identické (tj. mají stejnou rychlost) a úlohy jsou nezávislý (tj. žádná úloha nevyžaduje výstup jiného procesu). V tomto případě je problém plánování s více procesory variantou rozdělení vícecestného čísla problém. V obou problémech je cílem rozdělit čísla na podmnožiny s téměř stejným součtem. Víceprocesorové plánování se stejnými stroji je speciální případ, ve kterém je cílem minimalizovat největší součet. K dosažení tohoto cíle lze použít mnoho algoritmů pro rozdělování vícecestných čísel, přesných i přibližných.

Složitějším případem je situace, kdy to mají procesory různé rychlosti: při práci i je naplánováno na procesor j, dokončení trvá velikost (i) / rychlost (j). Tento případ vyžaduje pečlivější analýzu.

  • Volal jednoduchý algoritmus chamtivé rozdělení čísel, nebo Algoritmus LPT (Nejdelší doba zpracování), seřadí úlohy podle jejich délky, nejdéle nejdříve a poté je přiřadí k procesoru s dosud nejstarším časem ukončení. I když byl původně vyvinut pro identické procesory, má dobré asymptotické konvergenční vlastnosti i při různých rychlostech.[3]
  • Hochbaum a Shmoys,[4] kteří vyvinuli PTAS pro identické procesory, rozšířili svůj PTAS tak, aby zpracovával procesory s různými rychlostmi.
  • Epstein a Sgall[5] zobecnil tento PTAS na zpracování obecnějších objektových funkcí. Nechat si (pro i mezi 1 a k) být výrobcem procesoru i v daném rozvrhu. Namísto minimalizace objektivní funkce max (si), lze minimalizovat objektivní funkci max (F(si)), kde F je libovolná pevná funkce. Podobně lze minimalizovat součet objektivních funkcí (F(si)).

Nejsložitějším případem je situace, kdy mohou být úlohy závislé. Vezměte například případ čtení pověření uživatele z konzoly, pak jej použijte k ověření a poté, pokud je ověření úspěšné, zobrazte některá data v konzole. Je zřejmé, že jeden úkol závisí na druhém. Toto je jasný případ, kdy nějaký druh objednávání mezi úkoly existuje. Ve skutečnosti je jasné, že se dá modelovat pomocí částečné objednání. Podle definice pak sada úkolů tvoří a příhradová struktura. To přidává další komplikaci problému plánování s více procesory.

Statický versus dynamický

Algoritmy plánování více procesorů jsou statické nebo dynamické. Algoritmus plánování je statický pokud rozhodnutí o plánování, jaké výpočetní úkoly budou přiděleny tomu, jaké procesory jsou provedeny před spuštěním programu. Algoritmus je dynamický pokud je přijata za běhu. Pro statické plánovací algoritmy je typickým přístupem pořadí úkolů podle jejich prioritních vztahů a použití techniky plánování seznamu k jejich naplánování na procesory.[6]

Viz také

  • Plánování práce, podobný problém pro plánování úloh na strojích. Některé varianty plánování více procesorů a plánování dílny jsou rovnocennými problémy.

Reference

  1. ^ Kompendium problémů s optimalizací NP. Redakce: Pierluigi Crescenzi a Viggo Kann
  2. ^ Garey, Michael R .; Johnson, David S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W. H. Freeman and Company. str.238. ISBN  978-0716710448.
  3. ^ Frenk, J. B. G .; Rinnooy Kan, A. H. G. (01.05.1987). „Asymptotická optimita pravidla LPT“. Matematika operačního výzkumu. 12 (2): 241–254. doi:10,1287 / měsíc 12. 2. 241. ISSN  0364-765X.
  4. ^ Hochbaum, Dorit S .; Shmoys, David B. (01.06.1988). „Schéma polynomiální aproximace pro plánování na jednotných procesorech: použití přístupu dvojí aproximace“. SIAM Journal on Computing. 17 (3): 539–551. doi:10.1137/0217033. ISSN  0097-5397.
  5. ^ Epstein, Leah; Sgall, Jiří (01.05.2004). „Aproximační schémata pro plánování rovnoměrně souvisejících a identických paralelních strojů“. Algorithmica. 39 (1): 43–57. doi:10.1007 / s00453-003-1077-7. ISSN  1432-0541.
  6. ^ Kwok, Yu-Kwong; Ahmad, Ishfaq (01.12.1999). Msgstr "Statické plánovací algoritmy pro přidělování grafů směrovaných úkolů více procesorům". ACM Computing Surveys. 31 (4): 406–471. CiteSeerX  10.1.1.322.2295. doi:10.1145/344588.344618. ISSN  0360-0300.