如何在Brute-Force攻击中最好地“并行化”一组四个嵌套for（）循环？

Question

我有以下功课： 我需要使用以下掩码强制使用4-char密码

%%@@

（其中@ - 是一个数字字符，% - 是一个字母字符）

在几个使用OpenMP的线程中。

这是一段代码，但我不确定它是否正在做正确的事情：

int i, j, m, n;

const char alph[26] = "abcdefghijklmnopqrstuvwxyz";
const char num[10] = "0123456789";

#pragma omp parallel for private(pass) schedule(dynamic) collapse(4)
for (i = 0; i < 26; i++)
    for (j = 0; j < 26; j++)
        for (m = 0; m < 10; m++)
            for (n = 0; n < 10; n++) {
                pass[0] = alph[i];
                pass[1] = alph[j];
                pass[2] = num[m];
                pass[3] = num[n];

                /* Working with pass here */

            }

所以我的问题是： 如何正确指定“并行”指令，以便分割几个核心之间的密码范围？

非常感谢帮助。

Answer 1

除了使用alph而不是num之外，你的代码非常正确。如果你能够在循环中定义pass变量，那将为你节省很多麻烦。

一个完整的MWE可能看起来像：

//Compile with, e.g.: gcc -O3 temp.c -std=c99 -fopenmp
#include <stdio.h>
#include <unistd.h>
#include <string.h>

int PassCheck(char *pass){
  usleep(50); //Sleep for 100 microseconds to simulate work
  return strncmp(pass, "qr34", 4)==0;
}

int main(){
  const char alph[27] = "abcdefghijklmnopqrstuvwxyz";
  const char num[11]  = "0123456789";
  char goodpass[5] = "----"; //Provide a default password to indicate an error state

  int i, j, m, n;

  #pragma omp parallel for collapse(4)
  for (i = 0; i < 26; i++)
  for (j = 0; j < 26; j++)
  for (m = 0; m < 10; m++)
  for (n = 0; n < 10; n++){
    char pass[4];
    pass[0] = alph[i];
    pass[1] = alph[j];
    pass[2] = num[m];
    pass[3] = num[n];
    if(PassCheck(pass)){
      //It is good practice to use `critical` here in case two
      //passwords are somehow both valid. This won't arise in
      //your code, but is worth thinking about.
      #pragma omp critical
      {
        memcpy(goodpass, pass, 4);
        goodpass[4] = '\0';
        //#pragma omp cancel for //Escape for loops!
      }
    }
  }

  printf("Password was '%s'.\n",goodpass);

  return 0;
}

动态调度

在这里使用dynamic时间表可能毫无意义。您的期望应该是每个密码平均需要大约相同的检查时间。因此，循环的每次迭代将花费大约相同的时间量。因此，不需要使用动态调度，因为您的循环将保持均匀分布。

视觉噪音

请注意，循环嵌套是堆叠的，而不是缩进的。您经常会在代码中看到这种情况，其中有许多嵌套循环，因为它往往会降低视觉噪音。

早破

#pragma omp cancel for从OpenMP 4.0开始提供;但是，在这种情况下，我收到了警告，所以我已经评论过了。如果你能够让它运行起来，那么你的运行时间会缩短一半，因为一旦找到正确的密码就会浪费所有的努力，而且密码平均位于搜索空间的中间位置。

生成猜测密码的位置

评论员之一建议移动，例如pass[0]使它不在最里面的循环中。这是一个坏主意，因为这样做会阻止你使用collapse(4)。因此，您可以并行化外部循环，但是存在其迭代计数不能均匀地除以线程数的风险，从而导致较大的负载不平衡。或者，您可以并行化内部循环，这会在每次循环结束时向您展示相同的问题以及高同步成本。

为什么usleep？

usleep函数导致代码运行缓慢。这是故意的;它提供了关于并行性影响的反馈，因为工作量很小。

如果我删除了usleep，那么代码在单个内核上以0.003秒完成，在4个内核上完成0.004秒。你无法分辨并行性是否正常。离开usleep在单个核心上提供8.950s，在4个核心上提供2.257s，这恰好证明了并行性的有效性。

当然，一旦确定并行性能正常工作，就会删除此行。

此外，任何实际的暴力密码破解者都可能在PassCheck函数内计算昂贵的散列函数。包括usleep()在这里允许我们模拟该功能并尝试高级设计而无需首先使用该功能。