通過MPI並行化遞歸函數？

我們可以使用MPI並行化遞歸函數嗎？我想並行化快速排序功能，但不知道它是否在MPI中起作用，因爲它是遞歸的。我也想知道我應該在哪裏做平行區域。通過MPI並行化遞歸函數？

// quickSort.c 
#include <stdio.h> 

void quickSort(int[], int, int); 
int partition(int[], int, int); 


void main() 
{ 
    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9}; 

    int i; 
    printf("\n\nUnsorted array is: "); 
    for(i = 0; i < 9; ++i) 
     printf(" %d ", a[i]); 

    quickSort(a, 0, 8); 

    printf("\n\nSorted array is: "); 
    for(i = 0; i < 9; ++i) 
     printf(" %d ", a[i]); 

} 



void quickSort(int a[], int l, int r) 
{ 
    int j; 

    if(l < r) 
    { 
    // divide and conquer 
     j = partition(a, l, r); 
     quickSort(a, l, j-1); 
     quickSort(a, j+1, r); 
    } 

} 



int partition(int a[], int l, int r) { 
    int pivot, i, j, t; 
    pivot = a[l]; 
    i = l; j = r+1; 

    while(1) 
    { 
    do ++i; while(a[i] <= pivot && i <= r); 
    do --j; while(a[j] > pivot); 
    if(i >= j) break; 
    t = a[i]; a[i] = a[j]; a[j] = t; 
    } 
    t = a[l]; a[l] = a[j]; a[j] = t; 
    return j; 
}

如果還有另一個簡單的快速排序代碼，我也會很感激。

來源

2013-12-07 user2891902

嗯，在技術上你可以，但我恐怕這隻會在SMP中有效。而陣列是否適合單節點？如果不是，那麼即使是第一次快速排序也無法執行。

如果您確實需要使用MPI對並行系統上的數組進行排序，您可能需要考慮使用合併排序（當然，在開始合併塊之前，您仍然可以對每個節點上的單個塊使用快速排序）。

如果你還是想用快速排序，但你感到困惑與遞歸版本，這裏就是非遞歸算法的草圖，其希望可以並行更容易一點，但它本質上是相同的：

std::stack<std::pair<int, int> > unsorted; 
unsorted.push(std::make_pair(0, size-1)); 
while (!unsorted.empty()) { 
    std::pair<int, int> u = unsorted.top(); 
    unsorted.pop(); 
    m = partition(A, u.first, u.second); 

    // here you can send one of intervals to another node instead of 
    // pushing it into the stack, so it would be processed in parallel. 
    if (m+1 < u.second) unsorted.push(std::make_pair(m+1, u.second)); 
    if (u.first < m-1) unsorted.push(std::make_pair(u.first, m-1)); 
}

來源

2013-12-07 22:26:48 Inspired

理論上可以使用MPI並行化「任何事物」，但請記住MPI本身並未進行任何並行化。它只是提供進程之間的通信層。只要你所有的發送和接收（或集體呼叫）匹配，這是一個正確的方案，大部分。這就是說，根據您的算法，使用MPI可能不是最有效的方法。如果你要分揀大量和大量的數據（超過一個節點的內存容量），那麼使用MPI可能是高效的（你可能想看一下RMA章節）或者一些其他更高級別的庫可能使這種類型的應用程序變得更簡單（UPC，聯合陣列Fortran，SHMEM等）。

來源

2013-12-09 19:25:21

通過MPI並行化遞歸函數？

回答

相關問題