Bulat_Ziganshin
Silver Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Цитата: Оно сможет эффективно искать в 1гб словаре? А на карте какого уровня? И будет ли какой-нибудь толк от использования встройки?
|
у меня на 4-ядернике i7-4770 скорость RAR - порядка 50 МБ/с, что - не так уж случайно - совпадает с поточной скоростью случайных обращений к памяти
BSC с GPU-акселерацией кодирует со скоростью 140 МБ/с. На GPU при этом ложится сортировка, на CPU - только кодирование. если кодирование упростить (к примеру, до алгоритма, эквивалентного bzip2), то можно добить скорость до 1 ГБ/с, потеряв ~5% сжатия. Даже без GPU такой упрощённый алгоритм сможет сжимать со скоростью 300-500 МБ/с. Но понятно - у BWT/ST алгоритмов медленная распаковка и наилучшее сжатие только для текстов. Хотя если сравнить с другими алгоритмами, работающими на таких скоростях, то вероятно bzip2 обойдёт их и на бинарниках. Это достаточно простой, заведомо реализуемый проект. Я провёл необходимые для его реализации исследования в https://github.com/Bulat-Ziganshin/Compression-Research
По LZ-сжатию у меня есть только намётки различных подходов к поиску и оптимальному парсингу, оценки в районе 300-1000 МБ/с для 1080ti исходят из того, что мы сможем сделать поиск с одним обращением в память на один входной байт (позицию во входном буфере) и при этом не упереться в скорость вычислений
Вообще, отличия GPU от CPU:
1) на порядок больше memory throughput, в частности больше миллиарда случайных обращений в секунду
2) на порядок больше число ядер, например gf1080 - 2560/32=80 ядер, vega64 - 4096/16=256 ядер
3) строго in-order выполнение, большие чем у CPU задержки выполнения команд и обращений к памяти, особенно обращения к L1 кешу и shared memory - десятки циклов. чтобы покрыть их, у нвидии каждое ядро должно выполнять ~10 потоков, а у амд 3-4. т.е. в целом вынь да положь ~1000 потоков выполнения
4) это исключительно SIMD-процессоры с шириной simd-команд у intel 8-32, nvidia - 32, amd - 64. если твой алгоритм не simd-ифицируем, то ты теряешь большую часть вычислительных ресурсов. Впрочем, во-первых, в GPU simd очень гибкий, во-вторых даже на скалярных вычислениях GPU сопоставимы по мощи с CPU (но уже не превосходят их на порядок как в SIMD)
5) размеры кеш-памяти сопоставимы с CPU-шными, таким образом на каждый поток выполнения приходится раз в 100 меньше кеша. это собственно единственная причина, почему большинство даже хорошо распараллеливаемых CPU-алгоритмов плохо ложатся на GPU. Алгоритмы для GPU не должны полагаться на то, что данные лягут в кеш и 90% обращений к памяти до неё не дойдут. С другой стороны, память тут куда быстрее
В целом, GPU алгоритмы должны переносить тяжесть с хеширования как универсального способа решения всех проблем на сортировку в том же качестве 
Например, твой m/t алгоритм поиска уже рассортировывает позиции на несколько потоков. Представь сортировку по номеру хеш-бакета (а radix сортировка на GPU очень быстрая, миллиарды записей в секунду), после чего ты небольшие сегменты, соответствующие каждой хеш-корзине, можешь обрабатывать совершенно независимо от других корзин. Т.е. запустить ту самую тысячу потоков на GPU. При этом каждый поток будет держать в кеше по 32 байта из последних 32 позиций в своей хеш-корзине, т.е. 1024 байта на поток, 1 МБ достаточно для тыщи потоков
Т.е. в целом алгоритм поиска может выглядеть так - берём 8 МБ входных данных, сортируем их по корзинам, собираем матчи, сортируем их по позициям и отдаём это оптимальному lz-парсеру
Это лишь один из возможных подходов, которые я придумал, но понятно что тут куча ньюансов. В целом, GPU-алгоритмы - это отдельная область, нуждающаяся в большом объёме исследований. Когда кто-то их проведёт, расставит вешки, тогда уже другим будет легче
С другой стороны, внедрение GPU-алгоритмов не происходит потому, что все думают только об идеальных результатах, когда раз - и весь твой кодек на GPU заработал, только в 10 раз быстрее, причём на встройке и с гигабайтным словарём. А надо начинать с малого - скажем, в zstd -1 половина времени уходит на хафмена. В BSC на gpu перенесли алгоритм сортировки. У меня в новом srep память GPU будет использоваться вместо свопинга на HDD. И т.д.
Отдельный вопрос - встройки. У интеловских встроек мощность что в SIMD, что в скалярном режиме сопоставима с CPU, не говоря уже об одинаковой памяти. Т.е. тут о превосходстве на порядок можно забыть. Но с другой стороны - это всё же вторая пара рук, причём совершенно бесплатно и на любом компьютере. Разве плохо переложить на них того же хафмена и получить от 10% ускорения в обычных режимах до 2-кратного в -m1?
Более того - поскольку simd в gpu более развит, чем в cpu, есть шанс, что алгоритмы, которые не удаётся впихнуть в прокрустово ложе SSE/AVX, будут эффективно работать на GPU включая встройки. Тот же оптимальный парсинг в них вполне реализуем (впрочем, он даже на AVX2 может худо-бедно лечь), упираясь лишь во всё те же проблемы соотношения объёма кеш-памяти и уровня simd-параллелизма.
Так что от мифа, что GPU принципиально не подходят для наших алгоритмов, я перешёл к вере в то, что их реализация возможна, но потребует огромного объёма работы с освоением совершенно новых для нас подходов к оптимизации. Вот только востребовано ли это?
|
Общедоступные версии 1.3х появились, если склероз не подводит, примерно в ноябре. 
