параллельный стрлен?

Question

Мне интересно, будет ли смысл пытаться закодировать функцию strlen, чтобы найти последовательность \0 параллельно.Если да, что должна учитывать такая функция?Спасибо.

Answer 1

strlen() является последовательным по духу - один шаг после нулевого терминатора является неопределенным поведением, и нулевой терминатор может быть где угодно - первый символ или миллионный символ, поэтому вы должны сканировать последовательно.

Answer 2

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

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

Answer 3

Это было бы возможно на некоторых параллельных архитектурах, но только если бы можно было гарантировать безопасный доступ к значительному объему памяти вне строки; это было бы практичным, если бы ожидали, что строки были бы достаточно длинными, а связь и синхронизация потоков были бы дешевыми. Например, если у одного было шестнадцать процессоров, и один знал, что можно безопасно получить доступ к 256 КБ за пределы конца строки, можно было бы начать с отправки шестнадцати процессоров для обработки шестнадцати блоков по 4 КБ. Каждый раз, когда процессор заканчивал работу и не находил ноль, он мог либо начать обрабатывать либо следующий 4-килобайтный блок (если он находился в пределах 256 КБ самого младшего блока, который все еще находился в процессе), либо ждать завершения работы самого низкого процессора. На практике, если строки не были действительно огромными, задержки синхронизации и избыточная работа могли бы спровоцировать любые выгоды от параллелизма, но если бы нужно было найти длину строки в несколько мегабайт, задачу можно было бы выполнить параллельно.

Answer 4

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

Answer 5

Вы можете использовать это для строк FIXED-WIDTH, но не намного больше.

Answer 6

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

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

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

Скажем, у нас есть разделение строкв 8 кусков (0-7).Если мы нашли NUL-значения в чанке 3, мы не можем знать, возможно, есть ли другие NUL-значения в чанках 0-2, поэтому нам нужно ждать любого из этих потоков, и мы можем немедленно остановить все другие потоки.Если в потоке 1 будет найдено значение NUL, нам нужно только дождаться завершения потока 0, чтобы мы могли получить окончательный ответ.