Russian Qt Forum

Добрый день

Есть массив/контейнер 500k таких точек

C++ (Qt)
struct CPoint {
 QVector3D mPosition;  // позиция точки в пр-ве
 double mRadius;         // радиус
 // др данные (здесь нас не интересуют) 
};
 

Расчет длится неск минут, поэтому нужно задействовать все ядра. Но просто так дать каждой нитке часть точек не выходит, т.к. точки влияют одна на другую. Это ограничение можно сформулировать так:

- нельзя одновременно считать 2 точки (в разных нитках) если одна находится в радиусе другой

Как же расчленить данные (возможно повторно просчитывая некоторые точки)?

Спасибо

Т.е никак не возникает суперпозиции (результат воздействия на точку нескольких внешних точек есть сумма воздействия этих точек)?

Грубо говоря строится граф: точка связывается с соседней, образуется "ребро" которое запоминается в обеих точках. Разные нитки не не  должны одновременно добавлять ребра в одни и те же точки.

А если на каждую точку поставить мьютекс? или жирно слишком будет?

Насколько я знаю - черезчур жирно.

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

Распиливание/расчленение возможно. Напр взяли кусок слева, др справа, так что они не пересекутся, тогда можно дать каждой нитке по куску.

я слабо себе алгоритм представляю...

а если не на CPU распараллеливать, а вынести всё в openCL? не получится?

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

Задача не выглядит такой уж страшной и требующей привлечения таких масштабных тулзов  :)

Если ничего не знать о природе точек, то это превращается в УГ.
На первый взгляд, нужно разбить данные на не пересекающиеся куски, а потом обработать, и на ум приходит MapReduce и Qt Concurrent.
А вот задача о независимом множестве относиться к NP-полным задачам, что и угнетает.