>Я не знаю конечно как это реализовано в самом раре, но как
>такая мысль: Не катит, там ключ шифрования строится из результата 262 144 циклов SHA (насколько я понял их механику).Это было надо чтобы подгадить брутфорсерам.За счет такого подхода тысячи PPS упали до 1...несколько PPS на мощном проце :).При легитимном юзеже для юзера почти незаметно: на обычном более-менее мощном general purpose проце мощности пня 3 или выше это - лишь маленькая пауза до начала работы с архивом.Полсекунды (плюс-минус лапоть) юзер подождет до начала распаковки\упаковки.Но оно так на МОЩНОМ ядре.А на ДОХЛОМ юзер будет ждать пропорционально дольше пока оно отпедалит 262 144 цикла.И эти циклы не параллелятся потому что для начала очередного надо знать результат предыдущего.Итого вот так в лоб - все определяется скоростью выполнения на даденом ядре одного цикла SHA.Может быть можно разнести на несколько ядер сами циклы, но это довольно сомнительно, да и нет там ничего на 1000 процов.И вот подобных алгоритмов - есть.В сжатии, шифровании и прочем результат часто зависит от предыдущего, что здорово мешает распараллелить все это дело (ждать предыдущий результат - придется и толку с распараллеливания будет ноль).
Или вот например еще: как вы представляете себе распараллеливание ARCFOUR (как достаточно простой для понимания алгоритм) шифрующего непрерывным потоком?Я вот так сходу вижу только очень извращенские методы не дающие к тому же выигрыша в скорости в лоб, только n-разовое повышение *пикового* throughput'а по числу ядер весьма дорогой ценой (заранее обмолотить ядрами поток до нужной позиции и ждать там своего часа после чего втопить обсчет своего сегмента) при *средней* скорости потока - как на одном процессоре (каждое ядро будет доходить до определенной позиции потока со скоростью 1-процессорной системы и в случае непрерывного потока на пределе возможностей CPU все это даст ровно нулевой выигрыш vs 1 ядро - оно за то же время и так домолотит поток до той же позиции:P)
>первый вариант: файл разбивается на блоки, и т.о. получить хорошее ускорение?
Пауза до начала шифрования\дешифрования на прогон 262 144 циклов SHA чтобы просто получить из пароля ключ никуда не денется.И юзеру придется ждать пока эти циклы прогонятся.Чем дохлее ядро - тем дольше.А поскольку не параллелится вот так сходу - ждать придется именно столько и никак иначе.Итого на расшифровку 5кБ архива уйдет 100 секунд на SHA циклы + крохи на все остальное.На проце с мощным ядром 0.5 секунды + какая-то мелочь.Как вы думаете, что выберут юзеры?Правильно - они не будут переться от проца с множеством дохлых ядер в таких ситуациях.И поверьте, это встречается много где :)
>Другой вариант: Много файлов и каждый обрабатывается в своем ядре.
А паузу в допустим 100 секунд это не уберет :P
>третий вариант: поставить ядра друг за другом цепочкой.
А что это даст?Если такой алгоритм распихать на много ядер - закончится тем что одно молотит а остальные ждут результатов с того которое молотит.Потом следующее молотит а остальные ждут с него результат.И т.п. - скорость будет как на одном ядре.
Кстати вы верно заметили что разбивка на блоки... но как вы понимаете, в эпоху однопроцессорных систем МАЛО КТО ГРЕЛ МОЗГ ЭТИМ ВОПРОСОМ.Поэтому полно форматов данных, протоколов, алгоритмов и стандартов которые сделаны не так и потому - нифига не параллелятся.
>Я не готов с полной увереностью сказать про шифрование, но
>1. если используется блочное шифрование, но там изначально все разбито на блоки.
Да, в одной из его инкарнация можно выиграть.Только это самый поганый вид шифрования.Если вы шифруете все блоки одним ключом, очевидно что 2 одинаковых блока на входе == 2 одинаковых на выходе.Что позволяет хацкерам узнавать много нового о том что вы там пихаете.Никогда не видели как имеючи 2 картинки зашифрованных AESом чуваки восстанавливали контуры изображения путем нехитрых математических действий над двумя шифрованными вариантами? :).А в случае если key scheduling как-то завязан на предысторию, параллелимости настает каюк - из-за предыстории как раз :)
>И каждый блок вполне себе может шифроваться на своем ядре.
Вот только результат этой вот независимости - полное дерьмо как то утечка информации о структуре данных в шифрованном потоке.Одинаковые блоки на вход дают одинаковый результат на выход.И если вы послали 5 Кбайт нулей, атакующий легко может стать в курсе что вы послали именно 5Кбайт нулей.По пачке одинаковых пакетов.А уж если он свой plaintext может впарить - вообще труба, т.к. можно заранее пропихать сюжетно интересные пакеты и посмотреть как они в шифрованном виде выглядят.После чего иметь неплохое представление о том что в шифрованном потоке летает.Не полное но - достаточно неслабое.
>2. Если используется поточное шифрование, то для получения лавинного эффекта можно
>распределить вычисления между ядрами, выстроив их последовательно, а именно
>ядро №001-024 - выработка ключевой последовательности
Ну вон тот же arcfour - прост как топор.Слабо себе представляю как несколько тривиальных действий распихнуть на несколько процов.Там оверхед синхронизации будет больше чем просто смолотить всю операцию на 1 ядре (а что вы собрались параллелить в перестановке 2 байтов в массиве? :D).
>ядро №025-128 - само шифрование.
У того же arcfour например шифрование сводится аж к целому XOR псевдорандомной последовательности с последовательностью данных.И что вы там параллелить собрались?Это быстрее генерации псевдорандомной последовательности а ее генерацию вы хрен с два запараллелите - а там особо нечего параллелить - все просто как топор, 2 числа в массиве переставить :).Итого - вот так влоб от 103 процессоров будет нулевой выигрыш.С ксоркой справится и один а генереж псевдорандома вы имхо не запараллелите :).
В алгоритмах типа AES и подобных вас ожидает подстава в том что результат следующего раунда зависит от прошлого.Тоже фиг с два вот так в лоб запараллелишь - 1 ядро будет молотить раунд а остальные пардон будут ждать когда оно смолотит.Ничегонеделая :P.И как вы представляете в результате припахивание к этой операции 20 процессоров?Побить на независимые блоки?См.выше :P.А если они зависимые - параллельносьти не получится.Из-за зависимости как раз - придется ждать пока кто-то домолотит до нужного места чтобы узнать результат и начать обмолот с этого места.И поскольку само "ядро" алгоритма параллелится туго - ждать придется скорее всего столько же сколько при выполнении этого алгоритма на 1 ядре.За счет хилости отдельно взятого ядра есть шанс слить классическим 1...несколько ядерникам.С другой стороны - если расшифровку вынести на одно ядро, шифровку на другое, туда сбагрить компрессию, туда декомпрессию, вон тот гребет прерывание 1, а вон тот - прерывание 2, вон тот - занимается I\O с вон той периферией, ... - такая мелочь по сумме выполняемых задач может 1-ядерник и обойти.Если повезет.А если не повезет - сольет с треском.Ну вот потому такое и не делают.Как максимум - IBM с его Cell, который штука ядреная но - для специфичных задач.Да, ему фигня вопрос H.264 в реалтайме с HD качеством давить с его кучкой SPU.И там где раньше над этим пахала большая пачка прожорливых ксеонов может стоять один Cell, если софт оптимизнуть.Но пачка ксеонов намного быстрее выполняла general purpose задачи в ОС чем этот Cell :P.А на мобильных устройствах и т.п. задачи все-таки ближе к general purpose чем специальным.Ну вот кило ядер и оказалось мало кому надо.Может когда и запихнут как сопроцессор-акселератор, типа как произвольные вычисления на GPU на десктопах но - не более того.Именно основным процессором ему не бывать, по крайней мере - не сейчас.Вот видимо айбиэмщики поперлись от крутости а прикрутить реально никуда не осилили.Т.к. для декода H.264, кодирования с камер в жпег и т.п. у чипмэйкеров уже давно есть свои железки-акселераторы, кому надо крутую графику - есть видеочипы или встроенное ускорение. А больше "мобильщикам" ничего и не надо особо.Они думаю просто не хотят платить денег айбиэм за неочевидные выигрыши :) (выигрыш от кила ядер очевиден только узкой прослойке хакерофф на которых никто не ориентируется ессно :D)
>Во всем написанном мною для меня как программиста не сталкивавшимся толком с
>многоядерностью только одна проблема: как организовать взаимодействия между потоками.
Самое плохое - что попытка разнести простые и быстрые операции (в шифровании, хэшировании и т.п.) как раз уткнется в то что синхронизация затормозит все больше чем получится выигрыш :).Процы обычно быстры в выполнении команд а вот с внешним миром взаимодействие медленнее (айбиэмщики по этой причине воткнули для SPU довольно приличную локальную память чтобы SPU могли достаточно долго и независимо молотить без вмешательства "дирижера", но на килограмме ядер большую память каждому ядру не выделишь...).Кстати из подобных по структуре чипов - есть конторка Parallax которая делает довольно извращенные микропроцессоры с подобной структурой так что айбиэм скупивший кило ядер - не единственные кого приперло поизвращаться с экстремальными подходами.Конечно ядер не 1000 но для мелкого чипа embedded класса многоядерность как у параллакса весьма неслабая :)
>Что в прочем не является сверх проблемой, для алгоритмического решения.
В теории - да :) а на практике когда процы быстро только инструкции молотят а I\O с внешним миром заметно медленнее - выигрыш от разнесения простых операций может не получиться а достаточно большие блоки вычислений могут параллелиться не всегда.Ну вон распараллельте тот же ARCFOUR?Я сломав мозг придумал только как получить пиковую производительность в N раз.При СРЕДНЕЙ - как у одного ядра практически :D.Не больно супер-дупер, да?С другой стороны - это плохо для VPN сервера и т.п. - где одно толстое соединение которое потребно шифровать как можно быстрее.А если это торрент клиент где соединений 100 а каждое из них не очень крутое, каждое можно независимо распихать (де)шифроваться на свой процессор без каких-либо проблем :).Но это - потому что повезло и есть чему параллелиться.Есть много случаев где "не повезло", что и сдерживает появление многоядерников и многопроцессорников на десктопах и в мобильном сегменте.Реально большие количества ядер востребованы пока разве что на серверах т.к. там есть чему параллелиться.Ну собссно серваки с 4 проца по 4 ядра в серверах не редкость.Это конечно не кило ядер но уже кое-что :).На серверах все-таки нужны не ядра-задохлики как в килограмме ядер а полновесные ядра.И их пока удается впихивать все-таки не тысячами :)
