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

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 может быть запрограммирован многопоточным довольно легко и получить большой прирост производительности в многоядерных системах и некоторые небольшие потери производительности в не многопоточных. Просто помните, что теперь вы добавляете накладные расходы дважды - один раз для сохранения стека в рекурсии и один раз в потоке, поэтому, если вы выполняете большое количество рекурсий, это может привести к перегрузке системы быстрее, чем не многопоточный подход.