История изменений

А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный

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?

А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный

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?

А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный

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?