Должен ли я использовать потоки и рекурсию вместе?

Question

Я некоторое время возился с деревьями BSP, а также играю с потоками.При добавлении треугольника в BSP-дерево появляется возможность создать новый поток для целей параллельной обработки данных.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

Две вышеописанные операции вставки могут выполняться двумя потоками, и, поскольку они не изменяют одни и те же данные, можно использовать дешевую синхронизацию.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

Этот новый метод пытается создать поток для параллельного выполнения операции, но он не должен давать сбой, если поток не может быть создан (он просто вернется к исходному алгоритму).

Это правильная практика программирования или я неправильно использую потоки?Литературы по этой методике мне найти не удалось.Мне нравится, что он имеет тенденцию использовать мой процессор на полную мощность (2 ядра) и теоретически масштабируется до любого количества доступных процессоров.Мне не нравится, что это может быть ужасно расточительно для процессора и памяти.

Answer 1

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

Однако для задач, требующих интенсивной обработки, большее количество потоков, чем процессоров, фактически создает накладные расходы.Кажется, что ваши потоки выполняют всю «работу процессора», поэтому я бы придерживался одного потока на ядро ​​- хотя проверьте, чтобы найти оптимальное количество.

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

Answer 2

Лучше всего было бы создать пул потоков, а затем использовать его «прозрачно» для добавления узлов.

Например, создайте 2 потока при запуске программы, заставьте их ждать семафор или событие. Когда у вас есть узлы для добавления, вы помещаете данные в очередь, а затем запускаете семафор. Это пробуждает один из потоков, который выталкивает данные из очереди и выполняет обработку. (убедитесь, что доступ к очереди безопасен для потоков - лучше всего полностью синхронизировать с критическим разделом).

Общая производительность вашего приложения ниже, поскольку у вас больше накладных расходов при копировании данных в очередь и запуске дополнительных потоков, но если вы раньше работали на одном ядре, то теперь вы будете работать на 2. Это лучше всего работает если многопоточная обработка стоит дорого.

Answer 3

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