Как применить openMP к функции C ++ для проверки всех строк решения головоломки судоку?

Question

Как применить openMP к функции C ++ для проверки всех строк решения головоломки судоку?

Я разрабатываю программу, которая будет тестировать, чтобы увидеть, дается ли программе верное решение головоломки судоку или нет. Сначала я разработал его на C ++, но теперь я хочу попробовать сделать его параллельным. Программа прекрасно компилируется без ошибок.

Сначала я должен был найти способ справиться с использованием оператора return внутри структурированного блока. Я просто решил создать массив bool, которые инициализируются как true. Однако вывод этой функции ложен, и я точно знаю, что решение, которое я представляю, верно. Я новичок в openMP, и мне было интересно, если кто-нибудь может мне помочь?

У меня есть ощущение, что проблема с моей переменной возвращаться к 0 и, возможно, также с моей другой переменной nextSudokuNum возвращаться к 1.

bool test_rows(int sudoku[9][9])
{
int i, j, a;
int nextSudokuNum = 1;
bool rowReturn[9];

#pragma omp parallel for private(i)
for(i = 0; i < 9; i++)
{
rowReturn[i] = true;
}

#pragma omp parallel for private(i,j) \
reduction(+: a, nextSudokuNum)
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
{
a = 0;
while(sudoku[i][a] != nextSudokuNum) {
a++;
if(a > 9) {
rowReturn[i] = false;
}
}

nextSudokuNum++;
}
nextSudokuNum = 1;
}

for(i = 0; i < 9; i++)
{
if(rowReturn[i] == false) {
cout << "Invalid Sudoku Solution(Next Valid Sudoku Number Not Found)" << endl;
cout << "Check row " << (i+1) << endl;
return false;
}
}

cout << "Valid sudoku rows(Returning true)" << endl;
return true;
}

3

c++openmp parallels sudoku

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Отказ от ответственности:

Во-первых, не распараллеливайте очень маленькие циклы или циклы, которые выполняются практически мгновенно. Затраты на создание потоков будут доминировать над преимуществами, которые вы получите, выполняя внутренние операторы цикла параллельно. Поэтому, если каждая итерация, которую вы распараллеливаете, не выполнит тысячи миллионов FLOP, последовательная версия кода будет работать быстрее, чем параллельная версия кода.

Следовательно, лучший план распараллеливания ваших (вероятных) задач — распараллеливание на более высоком уровне. То есть, по-видимому, вы звоните test_rows(sudoku), test_columns(sudoku), а также test_box(sudoku) из одной функции где-то еще. Что вы можете сделать, это вызвать эти три последовательные функции параллельно, используя OpenMP sections где вызов каждой из этих трех функций является отдельным OpenMP section, Это только выиграет от использования трех ядер вашего процессора, но, по-видимому, вы все равно делаете это на своем ноутбуке, так что у вас, вероятно, только 2 или 4.

Теперь к вашим актуальным проблемам:

Вы не распараллеливаете jно только более i, Таким образом, вы можете видеть, что ваша переменная nextSudokuNum не уменьшается; для каждого i итерация, nextSudokuNum является автономным. Таким образом, он должен быть инициализирован внутри цикла и сделан private в #pragma omp parallel пункт.

Кроме того, вы не выполняете сокращение в течение a или. Для каждой итерации i, a устанавливается, сравнивается и увеличивается внутри. Опять же, это должна быть закрытая переменная.

Поэтому ваш новый код должен выглядеть так:

   #pragma omp parallel for private(i,j,a,nextSudokuNum)
for(i = 0; i < 9; i++)
{
// all private variables must be set internal to parallel region before being used
nextSudokuNum = 1;

for(j = 0; j < 9; j++)
{
a = 0;
while(sudoku[i][a] != nextSudokuNum) {
a++;
if(a > 9) {
rowReturn[i] = false;
}
}

nextSudokuNum++;
}
}

0