需要帮助使用 openmp 并行化 C++ 代码

Question

我已经在一个文本文件中逐行生成了 16 个 0 和 16 个 1 的所有 32 位排列，values.txt。例-

00000000000000001111111111111111
00000000000000010111111111111111
00000000000000011011111111111111
00000000000000011101111111111111

等等....

让我们假设文本文件的每一行都是一个布尔函数。我需要检查这个函数在域中的可逆性。

为此，我从文本文件中取出第一行并将其存储到维度为 32x1 的列矩阵中，矩阵 a[][]。

在嵌套的 for 循环中，我基本上以 3x3 矩阵的形式生成域值，我需要为此检查函数的可逆性。我创建了一个维度为 3x3 的矩阵 g[][]，它将存储所有编号的二进制表示。从 1 到 2^9。例如- 对于 0 矩阵 g 看起来像-

0 0 0
0 0 0
0 0 0

对于 1，矩阵 g 将是-

0 0 0 
0 0 0
0 0 1

对于 2 矩阵 g 将是

0 0 0
0 0 0
0 1 0

依此类推直到 2^9。

对于上面从 0 到 2^9 生成的每个矩阵，我正在根据我的函数计算一个维度为 3x3 的新矩阵 u[][]。这是通过读取矩阵的每个元素的 5 个相邻值来完成的。

例如-考虑g矩阵为

0 0 0
0 1 1
1 0 0

我选取第一个元素，即 g[0][0]，使用五个相邻值（顶部值、左侧值、元素本身、右侧值、下方值）为其计算一个新值，即 g [2][0]、g[0][2]、g[0][0]、g[0][1]、g[1][0]。这5个没有。组合起来代表一个二进制数。我计算它的十进制当量，十进制值对应于行号。矩阵 a[][] 的矩阵，我必须用它来更新 u[0][0] 的值。我将对 g 的每个元素重复上述过程，最终得到一个 3x3 的 u 矩阵。

这个完整的过程是针对一个矩阵的，它的矩阵对应0。像这样，对于从 0 到 2^9 的每个 g[][] 矩阵，我将创建 2^9 矩阵。

在任何时候，如果对于两个矩阵 g[][]，矩阵 u[][] 恰好相同，我将中止该函数，读取文本文件的第二行并再次开始上述过程，即，我对导致重复矩阵的函数不感兴趣。如果所有 2^9 矩阵恰好不同，我将相应函数的值（文本文件中的行）写入另一个文本文件。

因此，总而言之，我需要为整体计算创建总共 6 亿个* 2^9 矩阵。

问题是对于文本文件中的特定函数，2^9 矩阵是单独计算的。如果我能以某种方式将它们并行化，我会大大减少计算时间...

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#include <boost/lexical_cast.hpp>
#include <cctype>
#include <boost/assign/list_of.hpp>
#include <set>
#include <stdint.h>
#include <omp.h>
#define convertToString(x) #x
using namespace boost::assign;

int main()
{
    ifstream infile;
    infile.open("values.txt");
    ofstream outfile;
    outfile.open("haha.txt");
    short a[32][1];
    while(!infile.eof())
    {
        string STRING;
        getline(infile,STRING);
        set<string> SET;
        int count=0;


        for(int i=0;i<32;i++)
        {
                a[i][0]=STRING.at(i)-'0';
        }


        int g[9];
        int u[9];
        char buffer[10];
        buffer[9] = 0;
        uint16_t f = 0;

        int max = (int)pow(2,3);


        for(int r=0;r<max && count!=1;r++)
        {
           for(int s=0;s<max && count!=1;s++)
           {
              for(int t=0;t<max && count!=1;t++)
              {
                for(int i = 0; i < 9; ++i)
                {
                   g[i] = (f & (1 << (8 - i))) != 0;
                }
                ++f;

                u[0]=a[(g[6]*2*2*2*2)+(g[2]*2*2*2)+(g[0]*2*2)+(g[1]*2)+(g[3]*1)][0];
                u[1]=a[(g[7]*2*2*2*2)+(g[0]*2*2*2)+(g[1]*2*2)+(g[2]*2)+(g[4]*1)][0];
                u[2]=a[(g[8]*2*2*2*2)+(g[1]*2*2*2)+(g[2]*2*2)+(g[0]*2)+(g[5]*1)][0];
                u[3]=a[(g[0]*2*2*2*2)+(g[5]*2*2*2)+(g[3]*2*2)+(g[4]*2)+(g[6]*1)][0];
                u[4]=a[(g[1]*2*2*2*2)+(g[3]*2*2*2)+(g[4]*2*2)+(g[5]*2)+(g[7]*1)][0];
                u[5]=a[(g[2]*2*2*2*2)+(g[4]*2*2*2)+(g[5]*2*2)+(g[3]*2)+(g[8]*1)][0];
                u[6]=a[(g[3]*2*2*2*2)+(g[8]*2*2*2)+(g[6]*2*2)+(g[7]*2)+(g[0]*1)][0];
                u[7]=a[(g[4]*2*2*2*2)+(g[6]*2*2*2)+(g[7]*2*2)+(g[8]*2)+(g[1]*1)][0];
                u[8]=a[(g[5]*2*2*2*2)+(g[7]*2*2*2)+(g[8]*2*2)+(g[6]*2)+(g[2]*1)][0];


                for(int i = 0; i < 9; ++i)
                {
                   buffer[i] = '0' + u[i];
                }
                if(!SET.insert(::std::string(buffer)).second)
                {
                   count = 1;
                }
             }
          }
        }

        if(count==0)
        {
            outfile<<STRING<<"\n";
            cout<<STRING<<"\n";
        }


    }
        infile.close();
        outfile.close();
        return 0;
    }

Answer 1

当第二个维度仅为 1 时，无需使用二维数组。只需定义 a[32] 并在访问数组的任何位置省略第二个索引运算符 ([0])（可能只会提高可读性，我希望编译器无论如何都会对此进行优化 - 但这样你就安全了）。

你的convert函数是无效的，每次都在一个字符串前面添加将创建一个新的字符串对象。在这样的缓冲区中执行一次：

char buffer[10];
buffer[9] = 0;
for(int i = 0; i < 9; ++i)
{
    buffer[i] = '0' + ((dec & (1 << (8 - i))) != 0);
}
return ::std::string(buffer);

为什么只输出9位而不输出16位？

循环中的 u 数组也一样...

高一级：

string binary=in.convert(f++);

for(int i=0;i<9;i++)
    g[i]=binary.at(i)-'0';

您先转换了一个字符串，然后再将其转换回数字？为什么不将数组传递给转换函数并直接分配值（0 和 1，而不是“0”和“1”）？

您只在一个地方使用转换函数 - 也许您想将其内联。至少，让它成为静态的，因为它不依赖于任何 class 成员（如果没有其他成员函数保留，宁愿使用命名空间而不是 class）。

编辑： 我允许简单地内联所有内容（省略 pragma）：

int g[9];
int u[9];
char buffer[10];
buffer[9] = 0;
uint16_t f = 0;

int max = (int)pow(2,3);
for(int r=0;r<max;r++
{
    for(int s=0;s<max;s++)
    {
        for(int t=0;t<max;t++)
        {
            for(int i = 0; i < 9; ++i)
            {
                g[i] = (f & (1 << (8 - i))) != 0;
            }
            ++f;
            /* calculate the u array here */
            for(int i = 0; i < 9; ++i)
            {
                buffer[i] = '0' + (u[i] != 0);
            }
            if(!SET.insert(::std::string(buffer)).second)
            {
                count = 1;
            }
        }
    }
}

预先计算了功率，不确定编译器是否会优化掉它...

如果对 u 和 g 数组使用其大小与 CPU 寄存器大小匹配的整数类型，您可能会获得一些额外的性能提升...

您没有检查您的数组 a 可以获得哪些值。可能，任何人都可能是。如果您保证这些值始终只有 0 或 1，您甚至可以将代码缩短得最少：

buffer[i] = '0' + u[i];

尽早结束循环：

#pragma omp parallel
{
    for(int r=0;r<(int)pow(2,3);r++)
    {
        for(int s=0;s<(int)pow(2,3);s++)
        {
            #pragma omp parallel for shared(SET,count,f)
            for(int t=0;t<(int)pow(2,3);t++)
            {
                /* ... */
                    count = 1;
                    goto EndOfLoop;
                /* ... */
            }
        }
    }
    :EndOfLoop;
}

"It is illegal to branch (goto) into or out of a parallel region"，但不在里面，正如我读到的那样......变体是

for(int r=0; count == 0 && r<(int)pow(2,3);r++)

对于所有三个循环，但是这些额外的 if 的性价比...

需要帮助使用 openmp 并行化 C++ 代码

Need help parallelizing the C++ code using openmp

c++

parallel-processing

nested

openmp