Pull to refresh

Comments 50

Вы это чего? зачем в 21 вере MD5 хэш брутфорсить? нормально подбирается коллизия в течении десятков минут с помощью md5coll. Или это была чисто теоретическая задачка?
Чисто теоретическая. Показать на примере два подхода к распаралелливанию задачи.
Чисто практически, существуют уже просчитанные базы обратной конверсии хэшей, в т.ч. MD5. Называются такие таблицы — rainbow tables.

Если же считать хочется онлайном, то сейчас уже есть готовый код брутфорса md5 хэша на базе NVidia CUDA, который работает ощутимо быстрее любого SMP :)
ваш пароль 8843765, посчитал за доли секунды на видеокарте :)
рассказали бы как, очень интересно )
За подсказку с NVidia CUDA спасибо, интересная тема.
Можно за несколько минут создать 2 текста с одним md5 хэшем, но подобрать коллизию к заданному тексту или хэшу так просто уже нельзя.
UFO just landed and posted this here
может быть виндошная реализация omp умней чем линуксовя, но вам явно не хватает объявления private(strHash, stream) в прагме, без этого могут встречаться ситуации, когда пароль никогда не будет найден
«платить» за критическую секцию все равно придется
Запускал под виндой, проблем не было. Не исключаю, что я что-то упустил, но я не вижу проблемы. Объявление переменных strHash и stream происходит внутри тела цикла, т.е. они, если я правильно понимаю, для каждого потока будут своими. Вот если бы я вынес их объявление за тело цикла, тогда бы пришлось использовать private(strHash, stream). По моему как-то так.
может быть виндошная реализация omp умней чем линуксовя, но вам явно не хватает объявления private(strHash, stream) в прагме

В статьях по ссылкам выше:
По умолчанию общими являются все переменные, за исключением переменной цикла, которая является индивидуальной. Память можно объявить как индивидуальную следующими двумя способами.

* Объявите переменную внутри цикла (внутри директивы OpenMP) без ключевого слова static.
* Укажите индивидуальное выражение в директиве OpenMP.

И там же пример с комментариями:
// This works. The variable temp is now private 
    #pragma omp parallel for 
    for (i=0; i < 100; i++) 
    { 
       int temp; // variables declared within a  parallel construct are, by definition, private 
       temp = array[i]; 
       array[i] = do_something(temp); 
    } 

Так что вроде все верно и логично, если переменная объявлена внутри цикла, она по умолчанию приватная, если снаружи, общая.
тогда конечно все верно.
Я с первого прохода по коду (глазами) не углядел, где там маппится, а где редъюсится. Я правильно понял, что решает в данном случае всего лишь прагма на цикл?

Ещё было бы интересно узнать, возможно ли как-нибудь так же просто, параллелится за пределы одного сервера.
Да, добавляем прагму на цикл и получаем параллельное выполнение.Происходить это будет следующим образом (на примере первой итерации):

Извиняюсь, почему-то вставка текста привела к отправке коммента.

Current password: 8250000 Elapsed time: 0 sec.
Current password: 8500000 Elapsed time: 0 sec.
Current password: 8000000 Elapsed time: 0 sec.
Current password: 8750000 Elapsed time: 0 sec.

Т.е. первый цикл начал работу с 8000000, второй 8250000 и т.д. Насчет на разных серверах не скажу, не сталкивался, хотя тоже интересно.
можно. с помощью mpi
зачем делать многопоточную программу, когда можно параллельно запустить 2 однопоточные?
при этом только нужно разделить входные данные, чтобы дважды их не обрабатывать
Это просто «синтетический» пример, необходимость многопоточных вычислений может возникнуть, например, в 3D редакторе, при рендеринге изображений.
да, вы предлагаете тогда запускать запускать 100 программ когда нужно 100 трэдов? и сто лишних дескрипторов процессов повиснут где то в памяти ядра… не стоит забывать, что context-switch между трэдами одного процесса и между процессами происходит в десятки раз быстрей
нафиг переключаться? делим задание на 100 отдельных частей и каждому процессу назначаем отдельное задание, какие еще переключения?
и как предлагается ядру выполнять сто процессов без переключения контекста между ними? (100 процессорную/ядерную систему в расчет не берем)
пожалуйста, почитайте как работают многозадачные ос.

потоки и процессы — все нужно переключать, процессор-то один.
а вот цена переключения разная.
каких только извращений не придумает человек, лишь бы не использовать языков с нативной многопоточностью
эрланг, например )
да хоть тотже лисп, не будь он к ночи помянут
К сожалению, для некоторых задач, таких как брутфорс, Erlang проигрывает чистому C в 20-60 раз. Мне однажды было проще написать на С однопоточную прогу и запустить 8 процессов на моей 8-ядерной рабочей телеге, чем ждать, когда закончит работать Erlang. Да, можно было бы на других компах запустить процессы, но согласитесь, это получается, что ~50 компов нужно, чтобы уравновесить.

P.S. Я использовал Erlang HiPE, обычный по понятным причинам даже не рассматривал.
а как насчет Java?

В арифметике Java даже превосходит С++. И не слушайте вы этих школьников «жаба тормозит!!!!1111111111111111111111»
С Java никогда дела не имел и предубеждений против неё нет. Может, она и лучше была бы. Ведь очень неплохая библиотека JTS(JTS Topology Suite) написана именно на ней, а мы в своей работе используем её порт на C++ — GEOS.

Но сейчас у нас уже в обработке данных C/C++, Python и всяческие скрипты на shell/bash/perl. Уже планируется использовать Erlang. Ещё одного языка нам с коллективом 8 человек не потянуть.
что-то я количественных оценок быстродействия не встретил. А так — rainbow tables в руки и вперёд.
а можно использовать OpenMP без Visual Studio
я сторонник Unix технологий

>При этом вычисление пароля вторым методом, на моем компьютере, выполнялось значительно быстрее.
желательно такие заявления подтверждать цифрами. что стоит запустить таймер перед вычислениями и остановить после.
И еще посторить 10-100 итераций для усреднения…

Зато наглядно.
>а можно использовать OpenMP без Visual Studio
>я сторонник Unix технологий

Минута гугления дала ключевые слова «libgomp» и «gcc -lgomp». Проверил пример с википедии — работает.
UFO just landed and posted this here
Про какую ОС идет речь? В известных мне два потока одного процесса прекрасно выполнялись на разных ядрах. Более того OpenMP как раз потоки и создает.
UFO just landed and posted this here
ага, конечно.
а все и пишут многопоточные приложения, что бы они на одном ядре работали.
недавно встретил задачку(не помню уже где): есть 2^128 md5 хешей, требуется найти число прообразов
Прообразов бесконечно много.

Ваш К.О.
Хотелось бы все таки разницу в цифрах увидеть.
Разница очень значительная, я ее побоялся показывать (первый способ более 70-ти секунд, второй — 3) ищу ошибку в программе. Как буду уверен, что я нигде не ошибся — покажу :)
Извините, но статья практически ни о чем. Да, есть explicit thread creation, есть OpenMP, а еще есть Threading Building Blocks, Parallel Pattern Library, GPGPU, SIMD-оптимизация. Если уж показывать разные варианты, то не в стиле A vs. B, особенно если учесть что задачка весьма специфичная, а не обобщенная (как например умножение матриц).
Было желание показать простоту создания многопоточного приложения при использовании OpenMP, а не способ оптимизировать задачу от и до.
UFO just landed and posted this here
Согласен, код можно заставить быстрее и без многопоточности. Но если уж нам достался 2-х, 4-х и т.д. процессор почему бы не использовать его на всю катушку.
В распараллеленном коде операции с динамической памятью становятся особенно узким местом, если не применять специальных техник, типа отдельных пулов памяти на каждый поток.
Кроме счета на видюхе есть технология MassCore — отнимает у винды несколько ядер в пользование проги, на них больше нету context-switch и считать намного веселее, особенно если написать чтобы в кеше все уместилось.
Предлагаю внести stringstream stream внутрь тела цикла в функции _WorkerThread.
Потому что оператор << добавляет данные в поток.
Так что в конце там оказывается очень динная строчка.

Кроме того, delete [] хорош к месту, в функции _WorkerThread должен быть простой delete.
Большое Вам спасибо за внимательность! Я этот кусок кода упустил из виду, и уже второй день бьюсь головой об стол, пытаясь понять — почему первый метод дико тормозит и работает безобразно долго.
а еще openmp кроссплатформенный метод.
Sign up to leave a comment.

Articles