В проекте, над которым я сейчас работаю, мне часто нужно найти самый низкий возможный индекс в отсортированном массиве, в который можно вставить элемент (например, std::lower_bound в C++). Мне кажется довольно привлекательным использовать SSE для ускорения моего алгоритма, поскольку я работаю с массивами uint32, размер которых обычно равен размеру строки кэша процессора. Я никогда раньше не использовал SSE-инструкции, поэтому не могу понять, как будет выглядеть SSE-реализация этой функции. Пожалуйста, дайте подсказки, чтобы помочь мне написать это оптимально с помощью SSE.
Использование SSE для ускорения функции lower_bound
comment
Найдите время, чтобы провести небольшое исследование. Затем подумайте об этом и, возможно, попробуйте несколько вещей, чтобы почувствовать, как это работает. Затем задайте более прямой вопрос — здесь нет вопроса.
- person schedule 22.01.2011
comment
Я нашел pcmpled, который сравнивает 4 32-битных упакованных целых числа с 32-битным операндом, но мне не удалось найти, как получить результат этой инструкции. Может быть, вы могли бы указать хороший справочник о том, как использовать эту инструкцию (или соответствующую встроенную), если она у вас есть?
- person fokenrute schedule 23.01.2011
comment
Похоже, я был неправ; pcmpled сравнивает два вектора 4 из 32-битных целых чисел и заполняет vec4 0 и 1 в зависимости от результата сравнения. Ничего полезного для меня. Похоже, Билли ОНил прав, SSE мне не пригодится.
- person fokenrute schedule 23.01.2011
Ответы (1)
Ничего похожего на std::lower_bound нельзя масштабировать с помощью SSE. Причина, по которой SSE ускоряет работу, заключается в том, что она позволяет выполнять несколько вычислений одновременно. Например, одна инструкция SSE может привести к одновременному выполнению 4 операций умножения. Однако способ работы std::lower_bound нельзя распараллелить, поскольку каждый шаг алгоритма требует сравнения результатов предыдущих шагов. Кроме того, это уже O(lg n), и в результате вряд ли это будет узким местом.
Более того, прежде чем переходить к встроенному ассемблеру, вы должны знать, что всякий раз, когда вы используете встроенный ассемблер, вы отменяете большинство оптимизаций компилятора, которые могут возникнуть в этом разделе вашей программы, и часто в результате ваша программа будет работать медленнее - компиляторы обычно пишут лучший ассемблер. чем мы, люди.
Если вы хотите использовать SSE, вам лучше использовать intrinsics — специальные «функции» или ключевые слова, предоставляемые компилятором, которые вызывают инструкцию SSE, но в остальном позволяют выполнять оптимизацию. Такие встроенные функции доступны в Microsoft Visual C++, а также в Коллекция компиляторов GNU . (И, вероятно, почти любой компилятор. Обратитесь к документации вашего компилятора)
Вместо того, чтобы пытаться ускорить std::lower_bound с помощью SSE, вы должны попытаться вообще не вызывать его. Например, если вы постоянно вставляете элементы в вектор с помощью lower_bound, вы должны знать, что фактически создали сортировка вставками, и при этом плохая сортировка вставками, которая потребует квадратичного времени. Вероятно, вам было бы лучше просто поместить новые элементы в конец вектора, а затем отсортировать вектор, когда вам нужно отсортировать его, что сводит вещи к сортировке O (n lg n). Если ваши шаблоны доступа к данным таковы, что вы будете прибегать к ним слишком часто, вам следует вместо этого использовать что-то вроде std::set, что обеспечивает O (lg n) операций для вставок, а не O (n + lg n) вставок, которые вы в настоящее время используете. получение с векторами.
И, конечно же, не забывайте бенчмаркировать :)
person
Billy ONeal
schedule
22.01.2011
