Здравствуйте, VGn, Вы писали:
WH>>>>Лучше так: Много ли есть задач для которых нет эффективных параллельных алгоритмов? CC>>>"Ты не поверишь!" (С) WH>>Огласите весь список пожалуйста.
VGn>И отфильтруйте по тем задачам, которые могут подвесить по производительности ядро процессора ну допустим i7-950 допустим на пару секунд.
RSA с большим ключом, SHA-1 большого сообщения.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
T>И там на каждом ядре будет по копии всего синтаксического дерева всего проекта, ты не подумал об этом?
Зачем для всего дерева? Только AST тех хэдеров, которые импортируются в файл. Понятно, что сначала нужно будет построить дерево зависимостей файлов, и по нему уже распределять работу.
И всё будет вполне прилично параллелиться, даже без необходимости менять сам компилятор.
Здравствуйте, WinterMute, Вы писали:
WM>Первое что приходит на ум: поиск в отсортированнном массиве. Не такая уж редкая задача.
1)"поиск в отсортированном массиве" это как правило часть конкретного решения конкретной задачи.
2)Параллелить операцию со сложностью O(Log(N)) мягко говоря мало смысла в любом случае.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, thesz, Вы писали:
T>RSA с большим ключом,
Принято.
Но асимметричные шифры для больших сообщений как правило не используют.
А если брать симметричные то мы имеем например http://en.wikipedia.org/wiki/Salsa20
T>SHA-1 большого сообщения.
Опять таки если не зацикливаться на конкретном алгоритме то см md6.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, thesz, Вы писали:
T>Значительное время в компиляции C++ занимает разбор, который — в случае gcc, — параллелизуется плохо. T>И там на каждом ядре будет по копии всего синтаксического дерева всего проекта, ты не подумал об этом?
Есть такая хрень IncrediBuild называется... она явно показывает что компиляцию можно распараллелить не только по ядрам но и по куче машин.
Да и вижулстудия когда видит несколько ядер начинает несколько исходников параллельно компилировать.
В том же немерле хоть и пока не сделано но вполне реально запускать типизацию всех функций пареллено.
Короче твое утверждение про то что компиляторы не пареллеляться мягко говоря не соответствует действительности.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Andrei F., Вы писали:
AF>Здравствуйте, thesz, Вы писали:
T>>И там на каждом ядре будет по копии всего синтаксического дерева всего проекта, ты не подумал об этом?
AF>Зачем для всего дерева? Только AST тех хэдеров, которые импортируются в файл.
Весьма объёмная часть от проекта. Отличающаяся по объёму от всего проекта в константу раз, а, значит, имеющая ту же сложность O(размер_проекта).
Иными словами — дерево всего проекта.
AF>Понятно, что сначала нужно будет построить дерево зависимостей файлов, и по нему уже распределять работу. AF>И всё будет вполне прилично параллелиться, даже без необходимости менять сам компилятор.
Вот "без необходимости" это я бы порекомендовал проверить.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, thesz, Вы писали:
T>>RSA с большим ключом, WH>Принято. WH>Но асимметричные шифры для больших сообщений как правило не используют.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, thesz, Вы писали:
T>>Значительное время в компиляции C++ занимает разбор, который — в случае gcc, — параллелизуется плохо. T>>И там на каждом ядре будет по копии всего синтаксического дерева всего проекта, ты не подумал об этом? WH>Есть такая хрень IncrediBuild называется... она явно показывает что компиляцию можно распараллелить не только по ядрам но и по куче машин. WH>Да и вижулстудия когда видит несколько ядер начинает несколько исходников параллельно компилировать. WH>В том же немерле хоть и пока не сделано но вполне реально запускать типизацию всех функций пареллено. WH>Короче твое утверждение про то что компиляторы не пареллеляться мягко говоря не соответствует действительности.
Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.
Лично моё мнение таково: для распараллеливания придётся переползти с LALR на CYK (он работает над всем файлом сразу), а это означает серъёзную переработку разбора и его окружения.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
WH>>А если брать симметричные то мы имеем например http://en.wikipedia.org/wiki/Salsa20 T>В своё время это был DES(Block[i] XOR i).
Вот так больше похоже Block[i] XOR DES(i)
Но DES давно разломали.
А не сильно покоцанную сальсу даже не поцарапали.
T>Ага, понятно. Я подожду, пока это будет проверено.
Даже если поломают md6 то все равно не тех же принципах сделают легко распараллеливаемую хешфункцию.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, thesz, Вы писали:
T>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.
1)Где ты видел проект из одного файла? Еще раз читай про IncrediBuild и то как он работает. Сборку реальных проектов ускоряет капитально. Сам видел.
2)С++ имеет абсолютно дебильную структуру которую невозможно эффективно парсить. К счастью не все языки столь дурацки сделаны.
3)20%? На парсинг? Не верю! А если появляются шаблоны то там разбор текста ты и в микроскоп не увидишь.
4)Когда дело доходит до оптимизации и кодогенерации там можно параллелить и параллелить.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, thesz, Вы писали:
WH>>>А если брать симметричные то мы имеем например http://en.wikipedia.org/wiki/Salsa20 T>>В своё время это был DES(Block[i] XOR i). WH>Вот так больше похоже Block[i] XOR DES(i)
Легко показать, почему так нельзя.
Мы знаем что известный нам block[i] стал block[j] в другом сообщении. Значит, мы сможем вычислить block[j] в первом. В случае DES(block[i] XOR i) будет сложнее так сделать. А если мы ещё и добавим случайное число DES(block[i] XOR i XOR nonce), то так поступить будет невозможно в принципе.
WH>Но DES давно разломали.
Возьми любой другой современный блочный шифр. DES был в качестве примера.
WH>А не сильно покоцанную сальсу даже не поцарапали.
Она молодая.
T>>Ага, понятно. Я подожду, пока это будет проверено. WH>Даже если поломают md6 то все равно не тех же принципах сделают легко распараллеливаемую хешфункцию.
Это невыгодно, поскольку ускоряет перебор.
Я вполне серьёзен.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, thesz, Вы писали:
T>>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли. WH>1)Где ты видел проект из одного файла?
После препроцессора он становится одним файлом.
WH>Еще раз читай про IncrediBuild и то как он работает. Сборку реальных проектов ускоряет капитально. Сам видел.
Да и make -n тоже, вроде, как.
WH>2)С++ имеет абсолютно дебильную структуру которую невозможно эффективно парсить. К счастью не все языки столь дурацки сделаны.
А мы их отметём, как неорганиозванные.
WH>3)20%? На парсинг? Не верю! А если появляются шаблоны то там разбор текста ты и в микроскоп не увидишь. WH>4)Когда дело доходит до оптимизации и кодогенерации там можно параллелить и параллелить.
Мои коллеги-компиляторщики, писавшие автоматически распараллеливающий компилятор на основе gcc, не делали попыток автоматически распараллелить свой компилятор. За безнадёжностью.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, thesz, Вы писали:
WH>>Вот так больше похоже Block[i] XOR DES(i) T>Легко показать, почему так нельзя.
Cальса работает так: Block[i] xor Salsa(key, nonce, i)
Как следствие этим шифром можно зашифровать любое количество бит не парясь с паддингом и все классы атак которые основаны на всяких хитрых манипуляциях с сообщением также отваливаются.
WH>>А не сильно покоцанную сальсу даже не поцарапали. T>Она молодая.
Это не отменяет того что по ней капитально прошлись всеми известными криптоанализами.
Если бы DES придумали сегодня то его бы разломали на раз.
T>Это невыгодно, поскольку ускоряет перебор. T>Я вполне серьёзен.
Есть ссылки?
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, thesz, Вы писали:
T>После препроцессора он становится одним файлом.
Я начинаю сомневаться в том что ты знаешь как компилируется С++.
В один файл сливаются все заголовки прямо или косвенно подключенные к cpp файлу.
Но разные cpp файлы в один не сливаются.
T>Да и make -n тоже, вроде, как.
Во-во. По тому я и говорю что компиляция реальных проектов весьма неплохо параллелится даже с учетом современных тупых компиляторов.
T>А мы их отметём, как неорганиозванные.
А если не отметать?
T>Мои коллеги-компиляторщики, писавшие автоматически распараллеливающий компилятор на основе gcc, не делали попыток автоматически распараллелить свой компилятор. За безнадёжностью.
За безнадежностью распараллеливания gcc?
Я бы тоже не решился параллелить страшный сишный код.
А вот код написанный на функциональном языке причем без грязи можно распареллелить очень не плохо. Хотябы на уровне замены в нескольких местах map на parallelMap.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, thesz, Вы писали:
T>>>Ага, понятно. Я подожду, пока это будет проверено. WH>>Даже если поломают md6 то все равно не тех же принципах сделают легко распараллеливаемую хешфункцию. T>Это невыгодно, поскольку ускоряет перебор. ;) T>Я вполне серьёзен.
Перебор чего и как? Вычисление хэша короткого ввода (как пароль), для которого нужен перебор, это не ускорит. А задача "вычислить соответствующий данному хэшу документ, соответствующий всем нормам соответствующей грамматики" и так параллелится за счёт множества проб.
Здравствуйте, thesz, Вы писали:
T>Весьма объёмная часть от проекта. Отличающаяся по объёму от всего проекта в константу раз, а, значит, имеющая ту же сложность O(размер_проекта). T>Иными словами — дерево всего проекта.
Здравствуйте, thesz, Вы писали:
T>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли.
Параллелить можно по-разному.
Можно каждый цикл параллелить, а можно логический блок.
Можно пытаться ускорить разбор одного файла, как ты предлагаешь. А можно обработать одновременно несколько файлов, как сделано производителями компиляторов (микрософт и интел)
Здравствуйте, thesz, Вы писали:
T>>>Распараллель разбор C++ исходника, тогда поговорим. Разбор занимает много времени, что-то порядка 20%, что ли. WH>>1)Где ты видел проект из одного файла? T>После препроцессора он становится одним файлом. Нет!
Если у тебя есть 1.cpp и 2.сpp то после препроцессора у тебя все равно 2 файла. И тот самый разбор исходника будет происходить уже после препроцессора.
WH>>Еще раз читай про IncrediBuild и то как он работает. Сборку реальных проектов ускоряет капитально. Сам видел. T>Да и make -n тоже, вроде, как.
Он тоже умеет раскидывать компиляцию по разным компам и ядрам проца?
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, thesz, Вы писали:
T>>Это невыгодно, поскольку ускоряет перебор.
N>Перебор чего и как? Вычисление хэша короткого ввода (как пароль), для которого нужен перебор, это не ускорит. А задача "вычислить соответствующий данному хэшу документ, соответствующий всем нормам соответствующей грамматики" и так параллелится за счёт множества проб.
Да, не подумал.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, thesz, Вы писали:
WH>>>Вот так больше похоже Block[i] XOR DES(i) T>>Легко показать, почему так нельзя. WH>Cальса работает так: Block[i] xor Salsa(key, nonce, i) WH>Как следствие этим шифром можно зашифровать любое количество бит не парясь с паддингом и все классы атак которые основаны на всяких хитрых манипуляциях с сообщением также отваливаются.
Сальса — потоковый шифр. nonce ему помогает, но спасает не полностью.
WH>>>А не сильно покоцанную сальсу даже не поцарапали. T>>Она молодая. WH>Это не отменяет того что по ней капитально прошлись всеми известными криптоанализами. WH>Если бы DES придумали сегодня то его бы разломали на раз.
Современные варианты криптоанализа (конкретно, дифференциальный криптоанализ) снижают стоимость перебора DES с 2**56 до 2**49.5. Это при условии, что ты можешь зашифровать порядка 2**20 выбранных тобой блоков (chosen plaintext). При использовании известных тебе блоков (known plaintext) количество необходимых данных растёт порядка на полтора или два, сейчас уже и не помню.
DES очень, очень хороший шифр.
T>>Это невыгодно, поскольку ускоряет перебор. T>>Я вполне серьёзен. WH>Есть ссылки?
Тут неподалёку netch80 указал, что я неправ.
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Только AST тех хэдеров, которые импортируются в файл. Понятно, что сначала нужно будет построить дерево зависимостей файлов, и по нему уже распределять работу.
