Openacc优化Floyd算法

常规的Floyd算法目的在于找最短路，所以状态转移方程：dis[i,j]:=min{dis[i,k]+dis[k,j],dis[i,j]}，距离矩阵初始化为正无穷；本实验目的在于找最长路，所以状态转移方程：dis[i,j]:=max{dis[i,k]+dis[k,j],dis[i,j]}，距离矩阵初始化为负无穷。

众所周知Floyd算法的k是不能并行的，所以重点在于如何并行内层的两重循环。

floyd.cpp

#define INF 1e7
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

inline int index(const int i, const int j) {
  return i * SIZE + j;
}

// add your codes begin
#define P 4
// add your codes end

int main() {
  const int size2 = SIZE * SIZE;
  float* data = new float[size2];
  for (int i = 0; i < size2; i++) data[i] = -INF;

  srand(SIZE);
  for (int i = 0; i < SIZE*20; i++) {
    int prev = rand() % SIZE;
    int next = rand() % SIZE;
    if ((prev == next) || (data[index(prev, next)] > -INF)) {
      i--;
      continue;
    }
    data[index(prev, next)] = log((rand() % 99 + 1.0) / 100);
  }

  double t = omp_get_wtime();
  // add your codes begin
  omp_set_num_threads(P);
  #pragma omp parallel
  {
    int my_gpu=omp_get_thread_num();
    acc_set_device_num(my_gpu,acc_device_nvidia);
    #pragma acc data copy(data[0:size2])
    for(int k=my_gpu;k 

run.sh（4卡）

source device.sh 4
make clean
# timeout 1m time make serial
# timeout 1m time make multicore
# timeout 1m time make managed
# timeout 1m time make optimize
timeout 1m time make multidevice

这样省去了很多时间，只编译多卡

有问题欢迎在评论区讨论