Урок 21: Оптимизация редукции: sequential addressing
На предыдущем уроке мы построили древовидную редукцию в разделяемой памяти: на каждом шаге половина потоков складывает пару значений, сжимая сумму до единственного значения. Но то, как мы выбираем, какие потоки активны и к каким индексам они обращаются, кардинально меняет производительность. В наивн
Представь 8 детей в ряд, которым нужно сложить числа. В плохом методе ты просишь работать детей 0, 2, 4 и 6 — один работает, один отдыхает, беспорядок. В хорошем методе ты просишь только первых 4 детей, каждый прибавляет число ребёнка напротив него во второй половине ряда. Та же сумма, но одна упорядоченная группа работает, пока другая отдыхает — без беспорядка.
- чередующаяся адресация (interleaved addressing)
- Схема редукции, в которой шаг растёт (s *= 2), а активный поток — 2*s*tid, поэтому активные потоки разбросаны — что вызывает дивергенцию warp и конфликты банков.
- последовательная адресация (sequential addressing)
- Схема редукции с обратным циклом (s >>= 1), в которой каждый поток с tid < s выполняет tile[tid] += tile[tid+s], поэтому активные потоки непрерывны — без дивергенции, без конфликтов.
- конфликт банков (bank conflict)
- Когда потоки одного warp обращаются к одному и тому же банку разделяемой памяти, доступы сериализуются вместо параллельного выполнения — что снижает производительность.
- активные потоки (active threads)
- Потоки, выполняющие работу на данном шаге редукции. При sequential addressing они непрерывны 0..s-1; при interleaved они разбросаны.
