Prednáška

Abstrakt

Ako optimálne rozdeliť nezávislé úlohy medzi procesory tak, aby bol celkový čas výpočtu čo najkratší? Je dokázané, že toto je NP-ťažký problém, ak dĺžky trvania úloh sú vopred známe. Prakticky zaujímavé je uvažovať online algoritmy, ktoré úlohu riešia napriek tomu, že o dĺžkach trvania úloh majú len čiastočnú, či dokonca žiadnu informáciu. V tomto prípade sa nedá minimalizovať celkový čas výpočtu; dá sa však minimalizovať ich neefektivita vzhľadom na offline algoritmus, ktorý má vopred k dispozícii všetky informácie o danom vstupe. Budeme skúmať tri (deterministické) online algoritmy. Ukážeme, že chunking algoritmus je optimálny v prípade, že vopred poznáme dĺžku najdlhšej úlohy. Factoring algoritmus je optimálny v prípade, že je vopred známy podiel dĺžok najdlhšej a najkratšej úlohy. Work-stealing algoritmus nevyžaduje žiadnu informáciu, dovoľuje však prerozdeliť úlohy, ktoré už raz boli pridelené. Prekvapujúce je, že napriek nulovej informácii je tento algoritmus lepší než predošlé dva algoritmy, ktoré prerozdelenie nerobia.

Videozáznam z prednášky

Súbory k prednáške

Plagát k prednáške (128 kB)

Slajdy z prednášky (14 MB)

Fotografie z prednášky na Facebook-u

Videozáznam z prednášky

Fotografie z prednášky