Hlavní navigace

Názor ke zprávičce Qualcomm se naváží do MediaTeku: Osm jader? K ničemu! od Karel - Nikoliv. Quicksort nefunguje právě kvůli komplikované dělbě práce....

  • Aktualita je stará, nové názory již nelze přidávat.
  • 2. 9. 2013 17:31

    Karel (neregistrovaný)

    Nikoliv. Quicksort nefunguje právě kvůli komplikované dělbě práce. Dokud neprovedete první roztřídění, tak jedete v jednom vláknu. Teprve pak dostanete dvě úlohy, z nichž každou může dostat jiné vlákno. Teprve až ta dvě vlákna dokončí svou práci, tak se to opět bude dělit. Je to krásný příklad problému, u kterého nejvíce výkonu ztratíte organizací práce a nikoliv tím, jak dobře HW komunikuje mezi vlákny.

    Oproti tomu mergesort je paralelizovatelný dobře. Můžete už na samém počátku rozdělit vstupní data na N segmentů a pak je zpracovávat jeden po druhém. Pokud si někdo řekne o práci, tak mu řeknete rozmezí od-do a necháte ho to setřídit. Nakonec budete mít N setříděných fragmentů, které musíte spojit. Pak se dělá, že když máte setříděný fragment X a X+1, tak to dáte někomu jako jiný typ zadanání (merge místo sort). Prostě v každé chvíli budete mít snadno dostupný seznam balíků práce a předání úlohy spočívá v zadání typu (sort vs merge) a rozmezí od - do (případně pro úlohu merge i začátek druhého fragmentu). Samotný sort na fragmentu X pak může probíhat libovolnou metodu, klidně quicksortem - protože se tahle úloha se už dále nedělí. Pokud bych ji chtěl dále dělit, tak se buď musí zkomlikovat komunikace (slave se ptá mastera, zda má práci, a ten mu buď práci dá, nebo mu řekne jiný slave, který dostal nedávno nějakou práci, ať se s ním domluví na rozdělení), nebo se spíše použije stromová struktura - jeden master a pod ním X slave vláken. Vybraná slave vlákna jsou masterem pro svoje další slave vlákna atd.

    Rekapitulace: u quicksortu ztratíte plno času a úsilí ve snaze generovat úlohy pro slave vlákna, případně snahou uřídit síť peer-to-peer. Úzkým místem je pak vaše řízení paralelní úlohy, nikoliv HW. U mergesortu existuje snadný a nenáročný systém řízení slave vláken, takže zde bude úzkým místem HW, respektive OS a jeho mezivláknová komunikace, případně sdílení paměti. Quicksort si neříká o vícevlákno, ale o Chocholouška.