LINUX.ORG.RU

параллельная дефрагментация массива?

 ,


0

1

Пусть есть массив с данными data[n], часть данных помечена как пустые в отсортированном массиве ihole[m], m<n. Например data=[x0,x1,x2,x3], holes[1,3] — т.е. на месте x1 и x3 хранится мусор.

Необходимо дефрагментировать массив data, что бы на место мусора перемещались полезные данные из конца массива, а n-=m. Последовательный алгоритм тривиален:

for i in range(m):
	src = n-i-1
	dst = ihole[m-i-1]
	if src>dst: data[dst] = data[src]
Как проделать это параллельно? Собственно, хочу сделать аналогично функции «gpuppord2l» из https://github.com/UCLA-Plasma-Simulation-Group/PIC-skeleton-codes/blob/962a7..., но в силу своеобразного стиля написания этого кода никак не могу понять как оно работает...

★★★★★

Ответ на: комментарий от NeXTSTEP

откусить с конца data k кусков размером m/k (не считая дыр)

(не считая дыр)

предполагается, что это будет быстрее, чем сразу в один поток выполнить исходную задачу?

MyTrooName ★★★★★ ()

А ты PIC код

переписываешь? Интересное занятие. Это питон у тебя в примере, или куда так и выглядит? И есть ли смысл впринципеот параллелизации конкрено отбрасывания частиц? Мне кажется, они потихоньку уходят-приходят в объем, и выигрыша от параллельности не будет.

sshestov ()

Кажись вот этот кусок

Кажись вот этот кусок, который тебе нужнен. По-моему всё как так и происходит, как ты написал

/* move particles from end into remaining holes */
if (j < (ii+blockDim.x*nn)) {
               if (ii < nths)
                  j1 = sj[threadIdx.x];
               for (i = 0; i < idimp; i++) {
                  ppart[j2+nppmx*(i+idimp*k)]
                  = ppart[j1+nppmx*(i+idimp*k)];
               }
            }

sshestov ()
Ответ на: А ты PIC код от sshestov

переписываешь? Интересное занятие.

Свои поделки переношу с openmp на cuda, то что по ссылке использую как образец, т.к. модификации оно не поддаётся. Но алгоритм там очень быстрый, даже на ноутбуке около 0.6нс на частицу получается, т.е. более чем 10и кратный прирост по сравнению с cpu-тредами.

потихоньку уходят-приходят

Не, там домены маленькие, поэтому обмен между ними весьма активно идёт.

thunar ★★★★★ ()
Последнее исправление: thunar (всего исправлений: 1)
Ответ на: Кажись вот этот кусок от sshestov

Да, нашёл это место, скопировал оттуда, вроде работает. Там только до него какая-то хитрая арифметика с индексами в shared-памяти, которую не понял.

thunar ★★★★★ ()
Последнее исправление: thunar (всего исправлений: 1)