Семинар 12. Параллельные алгоритмы
Алгоритмы и структуры данных, часть 1


Что: Семинар
Когда: Суббота, 15 декабря 2018, 16:20–17:40
Где: НГУ, ауд. 2128

Описание

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).

Видео