LINUX.ORG.RU

асинхронная дефрагментация массива

 , , , ,


1

2

Например, имеются массивы data[N], hole[M], N≥M. В data хранятся данные, а в hole — в порядке возрастания, индексы, отмечающие пустые точки. Нужно дефрагментировать этот массив, т.е. обменять элементы так что бы данные лежали непрерывно. При этом, порядок в котором они они пишутся не важен. Что-то вроде:

8 holes:
	3 5 6 16 22 23 25 26
in:
	00 01 02 -- 04 -- -- 07 08 09 10 11 12 13 14 15 -- 17 18 19 20 21 -- -- 24 -- -- 27 28 29
out:
	00 01 02 29 04 28 27 07 08 09 10 11 12 13 14 15 24 17 18 19 20 21 -- -- -- -- -- -- -- --
Как называется этот алгоритм и как реализовать его параллельный вариант для произвольного количества тредов?

В наивной последовательной реализации (набросал на python)

id_hole = len(hole)-1
id_tail = len(data)-1
for j in range(0,len(hole)):
	dst = hole[j]
	while(id_hole>=j):
		if hole[id_hole] >= id_tail:
			#skip
			id_tail = id_tail-1 #atomic
			id_hole = id_hole-1 #atomic
		else:
			#move
			data[dst],data[id_tail] = data[id_tail],data[dst]
			id_tail = id_tail-1 #atomic
			break
получается две шаренные переменные, т.е. если параллелить цикл по j, то на каждый шаг будет не менее двух атомарных операций, что нехорошо. Как тут можно переделать?

Предполагается, что с этим будет работать код на CUDA, в пределах одного блока тредов.

★★★★★

если два треда, то один занимается нечетными элементами ВЫХОДНОГО массива, другой четными. разве сложно рассчитать отображение исходных элементов в конечные?

alysnix ()
Ответ на: комментарий от alysnix

вот в приведенном примере, если два треда.

один будет заполнять дырки 3,5,23,25. другой - 6,16,22,26…

вообще тут неважно как распределять. просто надо раздать дырки разным тредам неким способом. важно чтобы они понимали, какой элемент туда надо переместить

alysnix ()
Ответ на: комментарий от DllMain

Быстрая сортировка(или любая другая дихотомическая)…

а где тут отношение порядка? по какому приципу сортировать? тут четкой алгоритм последний непустой элемент попадает в первую дырку. делаем это. продвигаем индекс дырок вперед, длину массива уменьшаем на 1. повторяем в цикле пока дырки не кончатся.(ну или длина массива меньше индекса дырки - это если дырок больше чем элементов :) ) и параллелим этот алгоритм.

alysnix ()
Ответ на: комментарий от alysnix

последний непустой элемент попадает в первую дырку

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

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

Упражнение хорошее, но с чего ты взял что имеет смысл параллелить такую ерунду как копирование элементов, а также что всё не замедлится из-за атомарных операций и синхронизации кэшей?

Но вообще тут атомарные операции конечно же не нужны, потому что с каждым элементом работает не более одного потока. И обмен не нужен - можно копировать, потом заполнить конец массива тем что у тебя обозначает отсутствие элемента или просто обрезать.

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

А такую задачу вообще нужно параллелить? От этого будет какой-нибудь осязаемый выигрыш?

Мне кажется, задача сводится к следующей: есть массив holes размера M, в нем сидят номера индексов. Нужно добиться такого (поменяв местами какие-то элементы в data и значения в holes), чтобы в holes содержалось: [N-M+1, N-M+2, N-M+3, … ,N]. Итого, элемент data[holes[0]] меняем с data[N-M+1], data[holes[1]] - с data[N-M+2] и т.д.

Каждый независимый тред должен работать со своим диапазоном индексов из holes.

sshestov ()
Ответ на: комментарий от sshestov

holes можно не трогать, его конечное состояние тривиально.

каждому треду нужен не только свой диапазон из holes но и свой диапазон из data, иначе будет гонка

Да, вот насчет того что эту штуку нужно параллелить я тоже сомневаюсь. На первый взгляд и в один поток все будет норм.

AntonI ()
Ответ на: комментарий от AntonI

каждому треду нужен не только свой диапазон из holes но и свой диапазон из data, иначе будет гонка

там однозначное соответствие между исходным положением элемента и конечным. их даже можно аналитически посчитать и создать массив кто-куда. но это не надо. если одному треду дать четные дырки(дырки с четным индексом в массиве дырок), а второму с нечетным индексом, то в силу однозначности никаких коллизий не будет. просто один будет перемещать каждый 2*n из тех, что будут перемещены, а второй - каждый 2n+1. то есть если однотредовый вариант перемещал каждого кандидата, то в двухтредовом перемещаться будут кандидаты через один каждым тредом.

alysnix ()
Ответ на: комментарий от sshestov

Вот первый тред берет какой то элемент holes (пусть там лежит 10) и перемещает в ячейку 10 последний элемент data. Какой элемент data должен перемещать второй тред в ячейку заданную другим элементом holes? Актуален ли этот элемент data, не находится ли он уже в holes?

AntonI ()
Ответ на: комментарий от AntonI

для четного треда - последний это последний. а для нечетного - последний это предпоследний.

то есть один тред работает ровно как одиночный, но пропускает каждый второй элемент. а другой соотвественно тоже как одиночный. но берет этот каждый второй элемент.

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

alysnix ()
Последнее исправление: alysnix (всего исправлений: 2)
Ответ на: комментарий от alysnix

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

alysnix ()
Ответ на: комментарий от Siborgium

Зря вы так, общепринятая терминология, между прочим.

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

AntonI ()
Ответ на: комментарий от alysnix

Ваш алгоритм - Вам и доказывать его работоспособность. Набросайте пример кода, поговорим.

Пока что я не вижу многопоточных реализаций без хотя бы одной атомик переменной указывающей на конец даты, и то не факт что ее хватит.

AntonI ()
Ответ на: комментарий от AntonI

берутся два индекса.

h0(индекс первой дырки) = 0, h1(индекс последней)=длина массива дырок-1; и индекс последнего элемента массива данных = i.

проверяется валидность i. i валиден если он указывает не на последнюю дырку(она с индексом h1). если указывает на последнюю - делаем –h1; –i. то есть данная дырка не может быть ничем заполнена(поскольку дырку можно заполнить только справа, а справа элементов нет), делаем это в цикле, пока последняя дырка не окажется слева от текущего i. тут мы нашли самый правый непустой элемент переставляемго массива. если h0 <= h1, то есть массив дырок не сошелся в ноль, мы переставляем этот элемент данных с индексом i на позицию holes[h0] и инкрементруем h0.

то есть data[holes[h0++]]=data[i–];

поскольку тут декрементировали i, проверяем holes[h1]<i. если тру - элемент можно переставить и он не дырка. если дырка - смотрите алгоритм выше. как только h0>h1 - дырки кончились, выходим.

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

разумеется дырки изначально отсортированы массиве дырок

alysnix ()
Последнее исправление: alysnix (всего исправлений: 2)
Ответ на: комментарий от alysnix
где то так короче. основная идея.

void move(){
	int holes[]={2,3,4};
	int data[]={100,100,100,100,100,100,100};
		
	const int holesLen = 3;
	const int dataLen = 7;
	
	
	int h0 = 0, h1 = holesLen-1;
	int i = dataLen-1;
		
	while (h0<=h1){
		if (i <= holes[h1]) {
			if(i==holes[h1]) --i;
                        --h1;
 			continue;
		}
		//he we can move the righmost element
		data[holes[h0++] = data[i--]];
	}
}
alysnix ()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от AntonI

Это все прекрасно, но где тут многопоточность? Это вроде однопоточная версия?;-)

если тупо в лоб - оба потока исполняют ровно эту же функцию, только пропускают не свою дырку, вместо этого :

  data[holes[h0++] = data[i--]];

делая это:

  ++h0; --i;

это если тупо. но можно явно и оптимизировать.

alysnix ()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от alysnix

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

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

И насколько я знаю задачи @thunar (моделирование плазмы методом PIC) эта дефрагментация отнюдь не является узким местом, там есть более другие места которые действительно стоит пооптимизировать.

AntonI ()
Последнее исправление: AntonI (всего исправлений: 1)
Ответ на: комментарий от AntonI

она не является ОБЩЕЙ. индекс самого правого у каждого треда свой. и h0,h1 свой. написал же. РОВНО ТА ЖЕ ФУНКЦИЯ, со своими локальными переменными.завершение работы - окончание всех тредов.

alysnix ()
Ответ на: комментарий от alysnix

Это было бы правдой, если каждый тред работал бы со своим массивом данных и своим списком дырок. Но это не так.

проверяется валидность i. i валиден если он указывает не на последнюю дырку(она с индексом h1)

два треда - две последних дырки.

AntonI ()
Ответ на: комментарий от AntonI

два треда - две последних дырки.

массив дырок не меняется. любому из тредов все равно, как работает другой тред. это не его дело. у них разные дырки. один заполняет свои, другой свои. индексы тоже свои. «последняя дырка» - тоже своя, это его личный контекст.

alysnix ()
Ответ на: комментарий от sshestov

Ну @alysnix настаивает что можно параллелизовать без атомиков, я спинным мосгом ощущаю что нет, но контрпример придумывать лень - так работаю сейчас нонстопом который день, голова квадратная;-(

AntonI ()
Ответ на: комментарий от AntonI

Ну @alysnix настаивает что можно параллелизовать без атомиков,

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

а когда тредов два - у каждого треда свой экземпляр итератора, и они его вызывают, просто пропуская не свой элемент. и переставляя свой. один переставляет 0,2,4,6… элементы от итератора, а другой - 1,3,5…

то есть треды вообще никак не пересекаются ни в какой точке. итератор в любом контексте будет выдавать нужную последовательность. другое дело, что оба треда тут вызывают свой итератор, вычисляя след. элемент, и делают одну и ту же работу, то есть тратят время. и прирост производительности тут будет не 100 процентов, а процентов 50. но! итератор явно можно сделать более быстрым, чтобы итеририровать через 2 элемента, поскольку тредам, если их два - надо итерировать через два. тогда прирост будет уже процентов 80-90, навскидку.

alysnix ()
Ответ на: комментарий от AntonI

я спинным мосгом ощущаю что нет

А мне кажется, что всё таки можно. Просто @alysnix делит задачу на подзадачи как-то странно.

Находим позицию у которой количество дырок слева равно количеству элементов с данными справа. Бинарным поиском по массиву дырок должно находится. Назовём её P, а это количество N.

Дальше можно делать T потоков, каждый из которых будет обрабатывать n=N/T дырок (кроме последнего). Каждый поток с номером t берёт свою часть дырок [t*n; (t+1)*n] и элементов справа от P [P + t*n; P + (t+1)*n]. Первый элемент для каждого потока это P + количество дырок между P и P + t*n (т.е. опять бинарный поиск для поиска нижней границы в массиве дырок). При переходе к следующему элементу надо пропускать дырки смотря на индекс следующей дырки (мол while(idx == holes[nextHole]) { ++idx; ++nextHole; }).

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

xaizek ★★★★★ ()
Ответ на: комментарий от alysnix

есть еще более быстрый однопоточный алгоритм, чем мой. его паралелить проще. является модификацией моего.

вместо постоянных проверок для для каждого индекса последнего элемента - не попадает ли он в последнюю дырку, сначала просто вычисляется хвостовой бездырочный отрезок, а его длина равна lastDataPos - holes[lastHole]. вот пока такая длина не будет больше или равной единице - последние дырки выбрасываются - то есть декрементируется индекс последней дырки. как только такой отрезок появился его можно паралельно делать самым наивным образом, поскольку он непрерывный. просто писать подряд все элементы в первую дырку, инкрементируя индекс первой дырки. как только перекинули его, опять ищем непрерывный отрезок, и все повторяется. отрезки ищутся с хвоста данных. экономим на проверке - попадаем ли в дырку, для каждого элемента такого отрезка. поскольку мы заранее тривиально вычислили его начало, а конец - знаем.

alysnix ()