Day 9: 平行計算模型（二） Parallel Computation Model, Part 2 -- 搜索問題

2019 iT 邦幫忙鐵人賽

DAY 9

自我挑戰組

當傳統演算法遇到新的計算模型系列第 9 篇

2019鐵人賽

卡卡恩

2018-10-24 12:46:12

2814 瀏覽

分享至

一些經典的搜索問題—比方說數獨、比方說N皇后問題等，當我們被允許使用不只一個執行緒找答案的時候，通常可以有不錯的加速效果。而理由不外乎就是因為這些搜索演算法的工作深度很低（相較於指數級別的總工作量，多項式級別的工作深度相對低很多）。在這樣的情況下，每一種搜尋過程都可以被一個獨立的執行緒處理掉，也不需要共享太多的記憶體造成相依性。

老掉牙的 N 皇后問題

題目是這樣的，在一個 $N\times N$ 的棋盤上放 N 個皇后，皇后牙齒不好，所以老掉牙。請問她們不互相攻擊的情形有幾種？

讓我們來考慮一個超天真 C++ 版本：

#include <bits/stdc++.h>
#include "omp.h"
using namespace std;

// 這個範例使用的棋盤大小為 12 x 12。
int N = 12;

// 判斷 (r, c) 能不能放新的皇后。
bool can_put(vector<int> &position, int r, int c) {
  for (int i = 0; i < r; i++) {
    if (position[i] == c) return false;
    if (position[i]-c == i-r) return false;
    if (position[i]-c == r-i) return false;
  }
  return true;
}

// 計算給定目前的盤面 position[0..row_id-1]，總共有幾組解。
int count_nqueen(vector<int> &position, int row_id) {
  if (row_id == N) return 1;
  int num_solutions = 0;

  // 枚舉第 row_id 列的每一個位置，放一隻皇后試試看。
  for (int i = 0; i < N; i++) {
    vector<int> p2 = position;
    if (can_put(p2, row_id, i)) {
      p2[row_id] = i;
      num_solutions += count_nqueen(p2, row_id+1);
    }
  }
  return num_solutions;
}

int main(void) {
  vector<int> position(N);
  int count = count_nqueen(position, 0);
  printf("%d\n", count);
  return 0;
}

執行時間(1 thread)：

real	0m1.734s
user	0m1.730s
sys	0m0.000s

我們可以很無腦地用 OpenMP 對 for 迴圈進行平行化：
在 count_nqueen() 裡面的 for loop 上面加入

#pragma omp parallel for reduction(+:num_solutions)

執行時間(8 threads)：

real	0m0.603s
user	0m3.180s
sys	0m0.368s

如果我們只讓第一層遞迴展開，則可以預期會快一些：

real	0m0.499s
user	0m3.079s
sys	0m0.009s

以下是改過的內容（把 main 函式修改）

int main(void) {
  int count = 0;
#pragma omp parallel for reduction(+:count)
  for (int i = 0; i < N; i++) {
    vector<int> position(N);
    position[0] = i;
    count += count_nqueen(position, 1);
  }
  printf("%d\n", count);
  return 0;
}

明天我們來看看一些乍看之下需要循序計算的演算法，試圖找出他們可平行計算之處吧！