Семинар 12. Параллельные алгоритмы

The Myth of RAM: доступ к памяти занимает O(sqrt N). Эксперимент: обход связного списка (результаты). Кэши и память. Теоретическое обоснование. Одновременные запросы к памяти: latency и inverse throughput. CPU pipeline и out-of-order execution. Latency hiding. Параллельность на уровне инструкций. Hyper-threading.

Параллельные алгоритмы. Алгоритм редукции за O(log N), алгоритм вычисления префиксных сумм за O(log N), сжатие потока за O(log N). Сортирующие сети. Пример: сеть сортировки выборкой и сортировки вставками. Лемма о монотонной функции, 0-1 принцип корректности. Битоническая последовательность. Сеть half-cleaner для битонической последовательности. Битонический сортировщик глубиной O(log N), слияние. Сортирующая сеть для произвольного входа глубиной O(log^2 N).