Расчлененка

[Igors]

Добрый день

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

Код

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

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

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

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

Спасибо

[Akon]

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

[Igors]

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

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

[Fat-Zer]

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

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

[Bepec]

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

[Igors]

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

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

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

[Fat-Zer]

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

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

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

[Igors]

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

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

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

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

[DmitryM]

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

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