iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 9
1
自我挑戰組

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

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

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

老掉牙的 N 皇后問題

題目是這樣的,在一個 https://chart.googleapis.com/chart?cht=tx&chl=N%5Ctimes%20N 的棋盤上放 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;
}

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

參考資料

Multithreading in Cpp

現在大部份的編譯器都支援 OpenMP 了~比方說如果你用的是 GNU C++,那在編譯時加入 -fopenmp 參數就可以啟用 OpenMP 囉,相當方便。OpenMP 相關資源參考,還有逐步教學:

Multithreading in Python

GIL 的概念、以及哪些 package 可以幫助你繞過 GIL 實現方便的平行計算:

Multithreading in Javascript/ NodeJS


上一篇
Day 8: 平行計算模型(一)Parallel Computation Model, Part 1 -- 加總問題
下一篇
Day 10: 平行計算模型(三) Parallel Computation Model, Part 3 -- 前綴極小值問題
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言