Cvičení 10. 11. 2021: Keše

Př. 1: Transpozice

Na přednášce jsme viděli cache-aware transpozici matice pomocí bloků/kachlíků a cache-oblivious transpozici pomocí rekurze.
  1. Připomeňte si cache-aware algoritmus a jeho analýzu. Rozumíte tomu, proč funguje a hlavně proč to děláme zrovna takhle? Odsimulujte si algoritmus na matici 8x8 s \(B = 3\).
  2. Cache-aware algoritmus vyžaduje tall-cache assumption , přesněji řečeno \(M > B^2\). Proč tento předpoklad potřebujeme a bude nám vlastně stačit s kachlíky \(B\times B\)? A co když máme jen \( M > 1/2 B^2 \)? Můžeme algoritmus upravit tak, abychom zachovali složitost \( \mathcal{O}(N^2/B) \)?
  3. Připomeňte si cache-oblivious algoritmus a jeho analýzu. Rozumíte tomu, proč funguje a hlavně proč to děláme zrovna takhle? Odsimulujte si algoritmus na matici 8x8 s \(B = 3\).
  4. Oblíbenou chybou v cache-oblivious algoritmu je provedení transpose-and-swap doslova. Tedy, nejdřív obě podmatice prohodit a pak je obě rekurzivně ztransponovat. Zanalyzujte časovou složitost tohoto algoritmu a poté i I/O složitost (ten počet přenesených bloků).
  5. V cache-oblivious algoritmu, jsme tak nějak předpokládali, že \(N\) je mocnina dvojky. Co se stane, pokud není? Ukažte, že potom jsou všechny podmatice v průběhu algoritmu skoro čtvercové, to jest, počet řádků a sloupečků se liší nejvýš o jedna. Potom nahlédněte, že tato vlastnost nijak algoritmus nerozbije.

Př. 2: Třídění

  1. Analyzujte I/O složitost Quicksortu a Mergesortu. Jak velkou keš algoritmy potřebují?
    Hint: U mergesortu se může hodit uvažovat nerekurzivní verzi, která postupně merguje kusy velikosti 1, 2, 4, ...
  2. Dá se ukázat, že nejde třídit s lepší I/O složitostí než \(\mathcal{O}(N/B \log_{M/B}(N/B))\) (jsou-li prvky blackboxy, které umíme jen porovnávat a přesouvat vcelku). Navrhněte cache-aware algoritmus s touto složitostí. Jako základ použijte mergesort, který upravte tak, že bude opravdu využívat všechni keš, kterou má k dipozici.