CUDA Academy · Урок

Идея дерева свёртки

На каждом шаге уменьшайте число активных потоков вдвое.

Урок 1 из 413 шагов

«Идея дерева свёртки» — бесплатный урок CUDA Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения CUDA Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс CUDA Academy содержит 4 уроков всего.

Что означает свёртка

Свёртка преобразует целый массив в одно значение — например, складывает все элементы в один общий итог. Это один из самых распространённых шаблонов вычислений на GPU. 🌳

Последовательный способ работает медленно

На CPU элементы складываются один за другим. Это последовательные шаги O(n), поэтому для миллиона чисел потребуется миллион зависимых сложений подряд.

Сложение ассоциативно

Секрет в том, что сложение ассоциативно: (a+b)+c равно a+(b+c). Поэтому пары можно складывать в любом порядке группировки.

Складывайте пары параллельно

Поскольку группировка не имеет значения, можно одновременно складывать множество независимых пар. Каждый поток обрабатывает одну пару — всё за один параллельный шаг.

Уменьшение вдвое на каждом шаге

После одного прохода половина элементов исчезает. Повторяйте этот процесс, и количество активных элементов продолжит уменьшаться вдвое: 8, 4, 2, 1.

Логарифмическая глубина

Уменьшение вдвое означает, что вычисление завершается за log2(n) шагов вместо n. Миллион элементов сворачивается примерно за 20 шагов, а не за миллион.

Представьте дерево

Если изобразить объединение пар, получится двоичное дерево. Листья — это входные данные, на каждом уровне число узлов уменьшается вдвое, а корень содержит итоговую сумму.

Шаг увеличивается вдвое на каждом проходе

Один из способов реализации таков: на каждом шаге поток складывает своё значение с соседом на расстоянии шага, а это расстояние удваивается при каждом проходе по данным.

for (int s = 1; s < blockDim.x; s *= 2) {
  if (tid % (2 * s) == 0)
    data[tid] += data[tid + s];
  __syncthreads();
}

Синхронизация между шагами

Каждый уровень зависит от завершения предыдущего, поэтому потоки должны ждать у барьера, прежде чем читать результат своего партнёра.

Объём работы и критический путь

Общее число сложений остаётся примерно равным n — это объём работы. Но самая длинная цепочка зависимостей, то есть критический путь, сокращается до log2(n). Та же работа выполняется с гораздо меньшим ожиданием.

Не только сложение

То же дерево подходит для любой ассоциативной операции: поиска максимума, минимума, произведения или логического AND. Замените оператор — структура останется прежней.

Быстрая проверка

Подумайте, сколько параллельных шагов требуется для свёртки с помощью дерева.

Ответь в интерактивном уроке

Итоги

Вы изучили дерево свёртки: складывать пары параллельно, уменьшать их число вдвое на каждом шаге и завершать вычисление за log2(n). Этот подход работает для любой ассоциативной операции. Далее — эффективная загрузка варпов! 🎉

Можно начать бесплатно

Изучай C++ с ИИ-репетитором — бесплатно

Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.

Курсы: 30
Уроки: 120

Начать учиться бесплатно Посмотреть полный курс

Часто задаваемые вопросы

Урок «Идея дерева свёртки» бесплатный?

Да — полный текст урока «Идея дерева свёртки» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс CUDA Academy, подпишись на CoddyKit PRO. Курс CUDA Academy содержит 4 уроков всего.

Чему я научусь в уроке «Идея дерева свёртки»?

На каждом шаге уменьшайте число активных потоков вдвое. Ты практикуешь CUDA Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать CUDA Academy?

Предыдущий опыт не требуется. CUDA Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.

Сколько времени занимает урок «Идея дерева свёртки»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке CUDA Academy?

Да. Каждый урок CUDA Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к CUDA Academy