История изменений
Исправление slovazap, (текущая версия) :
А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный
for (i=0; i<vec.len()-1; i++) {
swap(vec[i], vec[rand(i, vec.len())]);
}
прям не подходит? Я не представляю как он может быть заметен на фоне любых других осмысленных вычислений по этим данным. Если только он не вызывается каждую итерацию какого-нибудь tight loop, тогда возможно стоит смотреть на какое-нибудь частичное-постепенное перемешивание.
А так не знаю, если идеальное качество не нужно, можно попробовать отдельными потоками перемешивать непересекающиеся выборки из массива, т.е. в случае двух потоков, например, один мешает только чётные элементы (с чётными), другой только нечётные. Конкретно это будет очень плохо дружить с кэшом и всё замедлит, но можно попробовать работать с бОльшими блоками (т.е. первый поток работает на элементах 0÷127, 256÷383, … второй - 128÷255, 384÷511, …). Нужно будет немного битовой магии чтобы вычислить индексы.
правильно называется на английском языке
parallel shuffle?
Исправление slovazap, :
А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный
for (i=0; i<vec.len()-1; i++) {
swap(vec[i], vec[rand(i, vec.len())]);
}
прям не подходит? Я не представляю как он может быть заметен на фоне любых других осмысленных вычислений по этим данным. Если только он не вызывается каждую итерации какого-нибудь tight loop, тогда возможно стоит смотреть на частичное-постепенное перемешивание.
А так не знаю, если идеальное качество не нужно, можно попробовать отдельными потоками перемешивать непересекающиеся выборки из массива, т.е. в случае двух потоков, например, один мешает только чётные элементы (с чётными), другой только нечётные. Конкретно это будет очень плохо дружить с кэшом и всё замедлит, но можно попробовать работать с бОльшими блоками (т.е. первый поток работает на элементах 0÷127, 256÷383, … второй - 128÷255, 384÷511, …). Нужно будет немного битовой магии чтобы вычислить индексы.
правильно называется на английском языке
parallel shuffle?
Исходная версия slovazap, :
А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный
for (i=0; i<vec.len()-1; i++) {
swap(vec[i], vec[rand(i, vec.len())]);
}
прям не подходит?
Ну не знаю, если идеальное качество не нужно, можно попробовать отдельными потоками перемешивать непересекающиеся выборки из массива, т.е. в случае двух потоков, например, один мешает только чётные элементы (с чётными), другой только нечётные. Конкретно это будет очень плохо жить с кэшом и эффективнее будет работать с бОльшими блоками (т.е. первый поток работает на элементах 0÷127, 256÷383, … второй - 128÷255, 384÷511, …).
правильно называется на английском языке
parallel shuffle?