c - 我怎样才能在暴力攻击中最好地使用 "parallelise"一组四个嵌套的 for() 循环？

Question

我有以下家庭作业:
我需要使用以下掩码暴力破解 4 个字符的密码

%%@@

(其中 @ - 是数字字符，% - 是字母字符)

在多个线程中使用 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 */

            }

所以我的问题是:
如何正确指定“parallel for”指令，以便在多个内核之间拆分密码短语范围？

非常感谢您的帮助。

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;
}

动态调度

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

视觉噪音

请注意，循环嵌套是堆叠的，而不是缩进的。您会经常在有许多嵌套循环的代码中看到这一点，因为它往往会减少视觉噪音。

早点休息

#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() 使我们能够模拟该功能并使用高级设计进行实验，而无需先使用该功能。