Использование OpenMP для распараллеливания вычислений

    Есть задача — восстановить пароль по его MD5 хэшу. Пароль простой, состоит из 7 цифр и начинается с 8-ки. Оговорюсь сразу — пароль мой, я его банально забыл, и это не инструкция о том, как брутфорсить чужие пароли.

    Программа должна работать в несколько потоков для максимально быстрого достижения результата. Хотя бы потому, что запускать я ее буду на компьютере с двухъядерным процессором. Один поток не сможет максимально использовать оба ядра.

    Рассмотрим два способа: создание нескольких рабочих потоков и использование OpenMP


    Способ первый — создание нескольких потоков.



    Для простоты будем решать задачу в лоб, без синхронизации потоков при выводе результатов. Иначе придется позаботиться о deadlock-ах, вернее об их отсутствии.
    // Объявляем переменные
    const int g_nNumberOfThreads = 4;

    const int g_nFrom = 8000000;
    const int g_nTo  = 8999999;
    const string g_strCompareWith = "4ac7b1796b90478f2991bb9a7b05d2bf";

    time_t g_timeElapsed;

    // Объявляем структуру, через которую будем передавать в поток исходные данные
    struct THREAD_PARAMS
    {
      int nFrom;
      int nTo;
    };

    // Прототип функции вычисляющей хэш MD5
    BOOL GetMD5Hash(string strIn, string &strHash)

    // Тело потока
    DWORD WINAPI _WorkerThread(LPVOID pParams)
    {
      // Сохраняем входные данные
      THREAD_PARAMS *pThreadParams = (THREAD_PARAMS*)pParams;

      int nFrom = pThreadParams->nFrom;
      int nTo  = pThreadParams->nTo;

      delete pParams;

      string strHash;

      for(int i = nFrom; i < nTo; ++i)
      {
        stringstream stream;
        stream << i;

        // Вычисляем очередной хэш
        GetMD5Hash(stream.str(), strHash);

        // Сравниваем с эталоном
        if(strHash == g_strCompareWith)
        {
          // Пароль найден
          cout << "Password is: " << stream.str() << endl;
          cout << "Elapsed time: " << time(NULL) - g_timeElapsed << " sec." << endl;
          exit(0);
        }

        // Отчитываемся о своей работе каждые 10000 итераций
        if((i % 10000) == 0)
        {
          cout << "Current password: " << i << " Elapsed time: " << time(NULL) - g_timeElapsed << " sec." << endl;
        }
      }

      return 0;
    }

    // Запуск потоков
    void MultiThreadWay()
    {
      int nDataLength = (int)(g_nTo - g_nFrom) / g_nNumberOfThreads;
      HANDLE *hThreads = new HANDLE[g_nNumberOfThreads];

      for(int i = 0; i < g_nNumberOfThreads; ++i)
      {
        THREAD_PARAMS *pParams = new THREAD_PARAMS();

        pParams->nFrom  = g_nFrom + (i * nDataLength);
        pParams->nTo  = pParams->nFrom + nDataLength;

        hThreads[i] = CreateThread(NULL, 0, _WorkerThread, pParams, 0, NULL);
        
        Sleep(100);
      }

      WaitForMultipleObjects(g_nNumberOfThreads, hThreads, TRUE, INFINITE);

      delete [] hThreads;
    }

    // Главная функция
    int _tmain(int argc, _TCHAR* argv[])
    {
      g_timeElapsed = time(NULL);

      MultiThreadWay();

      return 0;
    }


    * This source code was highlighted with Source Code Highlighter.


    Способ второй — использование OpenMP



    Необходимо включить заголовочный файл

    #include <omp.h>

    И добавить опцию компилятора /openmp. В Visual Studio это делается через свойства проекта



    // Объявляем переменные
    const int g_nNumberOfThreads = 4;

    const int g_nFrom = 8000000;
    const int g_nTo  = 8999999;
    const string g_strCompareWith = "4ac7b1796b90478f2991bb9a7b05d2bf";

    time_t g_timeElapsed;

    // Прототип функции вычисляющей хэш MD5
    BOOL GetMD5Hash(string strIn, string &strHash)

    int _tmain(int argc, _TCHAR* argv[])
    {
      g_timeElapsed = time(NULL);

      // Устанавливаем желаемое количество потоков
      omp_set_num_threads(g_nNumberOfThreads);

      // Одна прагма, добавленная перед циклом сделает за нас всю работу.
      // Цикл будет выполняться в g_nNumberOfThreads потоков.
      // Параметры цикла будут автоматически распределены между потоками.
      #pragma omp parallel for
      for(int i = g_nFrom; i < g_nTo; ++i)
      {
        // Эти переменные должны быть индивидуальными
        // для каждого потока
        string strHash;
        stringstream stream;

        stream << i;

        // Вычисляем очередной хэш
        GetMD5Hash(stream.str(), strHash);
        
        // Сравниваем с эталоном
        if(strHash == g_strCompareWith)
        {
          cout << "Password is: " << stream.str() << endl;
          cout << "Elapsed time: " << time(NULL) - g_timeElapsed << " sec." << endl;
          exit(0);
        }

        // Отчитываемся о своей работе каждые 10000 итераций
        if((i % 10000) == 0)
        {
          // В этот раз используем критическую секцию.
          // Почему бы нет, нам не нужно за нее "платить"
          #pragma omp critical 
          {
            cout << "Current password: " << i << " Elapsed time: " << time(NULL) - g_timeElapsed << " sec." << endl;
          }
        }
      }

      return 0;
    }


    * This source code was highlighted with Source Code Highlighter.


    С использованием OpenMP код получился гораздо короче. При этом вычисление пароля вторым методом, на моем компьютере, выполнялось значительно быстрее. Не смотря на то, что оба метода «грузили» оба ядра почти полностью.

    Если Вас заинтересовал OpenMP Вы можете начать изучение со статей, размещенные на сайте компании Intel

    Начало работы с OpenMP
    Эффективное распределение нагрузки между потоками с помощью OpenMP
    Advanced OpenMP Programming

    И не забудьте посетить сайт OpenMP. Там Вы сможете найти список компиляторов, поддерживающих OpenMP и спецификации OpenMP
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

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

          Если же считать хочется онлайном, то сейчас уже есть готовый код брутфорса md5 хэша на базе NVidia CUDA, который работает ощутимо быстрее любого SMP :)
          • +4
            ваш пароль 8843765, посчитал за доли секунды на видеокарте :)
            • +1
              рассказали бы как, очень интересно )
            • 0
              За подсказку с NVidia CUDA спасибо, интересная тема.
          • 0
            Можно за несколько минут создать 2 текста с одним md5 хэшем, но подобрать коллизию к заданному тексту или хэшу так просто уже нельзя.
            • НЛО прилетело и опубликовало эту надпись здесь
            • +1
              может быть виндошная реализация omp умней чем линуксовя, но вам явно не хватает объявления private(strHash, stream) в прагме, без этого могут встречаться ситуации, когда пароль никогда не будет найден
              «платить» за критическую секцию все равно придется
              • 0
                Запускал под виндой, проблем не было. Не исключаю, что я что-то упустил, но я не вижу проблемы. Объявление переменных strHash и stream происходит внутри тела цикла, т.е. они, если я правильно понимаю, для каждого потока будут своими. Вот если бы я вынес их объявление за тело цикла, тогда бы пришлось использовать private(strHash, stream). По моему как-то так.
                • +3
                  может быть виндошная реализация 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); 
                      } 

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

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

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

                      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 и т.д. Насчет на разных серверах не скажу, не сталкивался, хотя тоже интересно.
                    • +1
                      можно. с помощью mpi
                      • 0
                        Cluster OpenMP (ru preview, eng download), но лучше и вправду MPI, для большего контроля.
                      • +4
                        зачем делать многопоточную программу, когда можно параллельно запустить 2 однопоточные?
                        при этом только нужно разделить входные данные, чтобы дважды их не обрабатывать
                        • 0
                          Это просто «синтетический» пример, необходимость многопоточных вычислений может возникнуть, например, в 3D редакторе, при рендеринге изображений.
                          • 0
                            да, вы предлагаете тогда запускать запускать 100 программ когда нужно 100 трэдов? и сто лишних дескрипторов процессов повиснут где то в памяти ядра… не стоит забывать, что context-switch между трэдами одного процесса и между процессами происходит в десятки раз быстрей
                            • 0
                              нафиг переключаться? делим задание на 100 отдельных частей и каждому процессу назначаем отдельное задание, какие еще переключения?
                              • 0
                                и как предлагается ядру выполнять сто процессов без переключения контекста между ними? (100 процессорную/ядерную систему в расчет не берем)
                                • 0
                                  пожалуйста, почитайте как работают многозадачные ос.

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

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

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

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

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

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

                                        Минута гугления дала ключевые слова «libgomp» и «gcc -lgomp». Проверил пример с википедии — работает.
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                        • 0
                                          Про какую ОС идет речь? В известных мне два потока одного процесса прекрасно выполнялись на разных ядрах. Более того OpenMP как раз потоки и создает.
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                          • 0
                                            ага, конечно.
                                            а все и пишут многопоточные приложения, что бы они на одном ядре работали.
                                          • –1
                                            недавно встретил задачку(не помню уже где): есть 2^128 md5 хешей, требуется найти число прообразов
                                            • –1
                                              Под Касперски косишь?
                                              • +3
                                                Прообразов бесконечно много.

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

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

                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.