Помехоустойчивое кодирование

Вообще-то интересно время именно на квадратной матрице со 100% избыточностью. А что такого странного в 100% избыточности? Иногда нужна избыточность и в 400%.

Вот это и странно, даже удивительно. У Вас какая-то нестандартная терминология из-за которой практически невозможно понять, что на самом деле происходит. Какой размер матрицы в этой задаче? Глядя на параметры я предполагаю, что это матрица 9888 x 128. Но тогда время кодирования не может быть 4 секнуды для "квадратичной" матричной реализации RS.

Вот смотрите сами. У нас есть 128 контрольных блоков и 9888 исходных. У нас просто в силу теоретических ограничений КАЖДЫЙ входной блок должен поучаствовать В КАЖДОМ контрольном блоке. Кодер у Вас на умножении матрицы на вектор. Никуда не деться от того, чтобы выполнить КАК МИНИМУМ 128 x 9888 операций над блоками. Объем памяти которую нужно считать и записать обратно в каждой операции - это 2 * 8192 байтов на чтение (исходное данное + одна из контрольных сумм) и 8192 байтов на запись (новое значение контрольной суммы). Итого, в матричном кодере нам нужно прокачать через память КАК МИНИМУМ 9888 * 128 * (8192 * 3) = 31,104,958,464 = ~31 GB. Делим это на 4, получаем ~7.24 GB/s. Вы что, делаете там ОДИН xor на блок (а где же операции над GF(2^32)), а в машине стоит самая мощная DDR3-память?

 

Дык в чём и цимес: можно долго суммировать пары 64-битных, а потом один раз взять остаток - и вуаля.

 

Блин, после того как снял ограничение на число блоков (поскольку у RS32 оно может доходить до миллиардов),
посыпались локальные перегрузки объема памяти за 2G допустимых для приложения. сидел два дня правил.

Странно, как Вы при делении 80 метров на 128 хотите получить 8 кило на блок? Мой прог интерливом не занимается

Терминология самая простая и стандартная. Я не употребляю CodeWord, MSD и прочие малопонятные термины. И говоря о матрице, я конечно не дополняю ее еще Identity Matrix и прочей бесполезной для практики туфтой.

Так и есть, каждый входной элемент целуется разок с каждым матричным.
А когда будет FFT, тогда они еще и размножаться будут как кролики.

 

Ответьте прямо - если заданы параметры -wrr128-128 то какого размера будет матрица? 128 x 128? Как тогда получается, что скорость работы на матрице 128 x 128 (-wrr128-128) и на матрице 32 x 32 (-wrr32-32) почти одинаковая, в то время как матрица имеет в 16 (!) раз большую площадь.

 

Какие-какие операции? Матричные кодеры не содержат вызовов функций и даже инлайн-функций, поля остаются только у программера в голове, а кодер работает исключительно с набором самых базовых инструкций проца.

Не стоит сравнивать RS32 с Вашими вылизанными до блеска микроскопическими полями GF(16) и т.п. На такую мелочевку накладные расходы по вызову будут больше чем собственно кодирование. Начинайте с 3000х3000 или 10000х3000.

Да, именно 128 на 128 и будет.

 

А как насчёт поделиться описаловом, именно чтобы сравнить? :?

 

Это понятно, но он же не может делать ровно по одной инструкции на одно машинное слово/одно слово SSE/MMX. Из-за того, что по сути он должен видоизменить данные, а не просто наложить XOR-ом исходные данные на контрольную сумму в неименном виде того и другого.

Могу Вас обрадовать - Ваш кодер прекрасно работает на пределе скорости памяти именно с крупными матрицами, где-то за пределами 128 x 128, но жестко проигрывает (в разы) на мелких матрицах типа 32 x 32 даже неоптимизированному коду, не использующему вообще SSE/MMX. Это меня и удивляет - что за алгоритм такой нелинейный.

И естественно возникает вопрос - почему именно нелинейно изменяется время работы? Почему матрицы маленькие и большие обсчитываются с разницей во времени где-то в 1.2 раза, в то время как их площади отличаются в 16 раз.

 

Ну вот, новый тест, с большими матрицами по Вашему же совету. 1000 x 1000 -> 50 секунд, 10000 x 10000 -> 405 секунд, при этом скорость обработки находится за пределами возможностей памяти данной машинки, которой уже много-много лет. Возьмем наши 80 MB, поделим на 10000 -> блок размером примерно 8K, Ваша программа даже выводит цифру 10240 (взяла блок побольше). 10000 x 10000 x 10240 x 3 / 405 секунд -> ~7 GB/s. У меня память так быстро не работает. Откуда я беру коэффициент 3? Как минимум нужно считать каждое слово исходного блока и каждое слово выходного блока и сделать между ними xor и отписать назад. Не так? (Я знаю как минимум 2 метода, как сделать иначе, один из них пресловутое FFT. Но это будет не квадратичный, а совсем другой кодер.)

 

ginger_tigra
Хорошее описание матричного RS можно найти в документации к проекту Recovery Star by Артем Дробанов

 

sysprg
Попробуйте еще с ключом -tm4. Там матрица тоже плотная. Какой скорость прокача получается?

 

Но в RS матрица не просто плотная - там нулей максимум одна строка. Откуда тогда берется такая скорость? Если это матричный метод. Объясните.

 

И почему при переходе с матрицы 1000 x 1000 к матрице 10000 x 10000 время обработки растет в 8 раз, не в 100 раз. Если это квадратичный метод. И если результат потом можно восстановить.

 

Какая именно скорость, времена можно? Что касается complexity обработки фиксированного объема оно на единицу меньше, уже обсуждали

 

Матрица 10000x10000 обсчитывается за 405 секунд, матрица 1000x1000 обсчитывается за ~50 секунд, при этом разница в номинальной площади матриц огромна - в 100 раз. Время же меняется всего в 8 раз. Объемы данных все те же = 80 MB (ровно). Я заинтересовался Вашей программой - на самом деле! Сколько нулей у Вас в этих матрицах, какое количество? Удивительно, что на матрицах меньше 128 x 128 время работы CRC32 (несмотря на SSE2 оптимизации) среднее в сравнении с другими программам и сильно уступает лучшим образцам заточенным под мелкие матрицы (типа моей программы). Но на больших матрицах Вы резко ускоряетесь. Неужели там так много нулей в матрице? При режиме -tm3. Я не могу напрямую сравнить со своей программой, заточенной на GF(2^8) на больших матрицах, но я сравнил с другими программами, которые не оптимизированы на определенное поле и работают на очень больших матрицах - и Вы их действительно сильно опережаете. Поэтому интересно понять - это за счет нулей или у Вас просто код настолько лучше прописан?

 

А я понял, что торможу, удивляясь нелинейному росту времени работы! Объем данных-то в этом тесте фиксированный... В результате хотя растет нагрузка на кодер из-за роста размера матрицы, но падает объем данных!

Сказывается долгое тестирование кодеров в чистом виде, как абстрактных библиотек без привязки к файлам и тому подобному - при таком сравнении размер блока забит константой, скажем 8192. В результате когда мы меняем размер матрицы * 10 по каждой стороне - время действительно растет в 100 раз. Потому, что увеличивается и СУММАРНЫЙ объем данных в тесте. В случае же тестирования Вашей программы объем данных, взятых из файла, фиксированный - и в результате затраты из-за матрицы растут, но длина блока падает и КОМПЕНСИРУЕТ частично накладные расходы связанные с матрицей...

 

Матрицы методов RS32 и TBPC (ключи –tm3 и –tm4) нолей не содержат, пропусков не делают, и уж тем более не разбавляют матрицу нулями по мере ее роста. Все элементы этих матриц чинно обрабатываются друг за другом без прыжков.

У меня для RS32 80М файлов получились такие времена для своей машины:

1000x1000 - 36 сек
10000x10000 - 290 сек

Казалось бы можно было на этом успокоиться, однако ж моя программа в ряду PAR2-подобных впервые вводит методы основанные на избыточных томах. Для –tm4 времена такие:

1000x1000 - 7 сек
10000x10000 - 80 сек

Повторяю, что прыжков матрица –tm4 не содержит, поскольку является плотной.
Возникает законный вопрос – а может ли метод вернуть обратно информацию и вылечить то, что закодил? В таком виде как было закодировано – не может, ибо зачем тогда держать два одинаковых метода, если один в пять раз быстрее? Для –tm4 кодировать нужно так:

-wrr10000-10015 -tm4

То есть давать ему 15 блоков свыше необходимых.
Закодили.
Теперь стираем исходные файлы совсем и попробуем их вернуть.
-rrr
Вернули. Правда, метод потребовал кубического обращения матрицы, а это не слишком быстро.

 

Быстродействие для больших матриц просто отличное! Для маленьких - при включенном SSE2 среднее (чуть медленее классических программ), при выключенном - уже оставание раз в 10. Но на больших матрицах - все наоборот. Поэтому и интересно - в чем тут хитрость? Сколько операций XOR Вы делаете на каждое элементерное умножение в GF? Сколько происходит операций для одной ячейки той матрицы, которая 1000 x 1000? И какой у Вас размер элементарной единицы обработки? То, что программа ускоряется за счет SSE наводит на мысль что обработка идет маленькими/средними словами, например по 128 битов, а не целыми блоками сразу.

 

Имеются статьи, где главной задачей является снижение нагрузки на сеть, а получатели потом могут возиться с расшифровкой сколько душе угодно, как тут и получилось с ключом -tm4

 

Результаты для матриц, где нужны дополнительные контрольные суммы меня лично не удивляют. Особенно для неплотных матриц. Мне просто интересно - за счет чего у Вас происходит сильное ускорение в сравнении со всеми обычными доступными в исходниках кодерами для очень больших матриц? Если матрица у Вас плотная и как Вы писали - просто матрица Коши, то в чем причина такого высокого быстродействия - в оптимизации кода программной или в использовании каких-то нестандартных решений на уровне самой математики? Обычные программы доступные в исходных кодах не содержат оптимизации под SSE, но Вы их обгоняете и даже с выключенным SSE. Может быть Вы лучше используете interleave памяти, может кэш - это одно возможное объяснение. Второе - у Вас не совсем обычный матричный кодер. Я не спрашиваю какой там алгоритм, меня интересует причина ускорения в общих чертах - это классная реализация одной операции умножения в GF(2^32) или это выход за рамки независимой и индивидуальной обработки каждой из 1000 x 1000 таких операций. То, что там нет FFT – Вы уже написали. Но может у Вас там есть что-то другое? Или вся соль в превосходной реализации обработки в рамках классического алгоритма, которому в итоге нужно 1000 x 1000 раз сделать операцию умножения GF(2^32) - но Вы лучше всех остальных программ раскладываете ее в элементарные XOR (или в что-то еще). Если источник быстродействия именно превосходная реализация одного такого умножения (по сути) - то сколько XOR в итоге получается у Вас на одну такую операцию и при какой порции данных?

 

Косвенно понял из этой темы, что на каком-то другом форуме Вы доказываете преимущества неплотных матриц для ситуации, когда очень много блоков. Для меня это очевидно - для этого и были придуманы современные варианты LDPC и прочие родственные методы. По большому счету в подавляющем большинстве приложений, где нужны огромные матрицы, не нужно даже делать никакое FFT или иной субквадратичный способ кодирования RS. Так как на фоне сотен тысяч или миллионов блоков наличие избыточных 30-100 или даже 1000 блоков никого не волнует, а быстродействие на рассеянных матрицах будет еще выше. LDPC и родственные методы даже вошли уже в некоторые стандарты или предложения по стандартам в связи именно по этой причине - они дают огромное быстродействие ценой слегка неоптимального кодирования. Но быстродействие таково, что MDS-кодам его не достичь (пока что?) никаким образом.