cpupar.cpp
// Take one step of "top-down" BFS. Modified from assignment 3.
Take one step of "top-down" BFS. Modified from assignment 3.
Take one step of " top - down " BFS . Modified from assignment 3 .
bool topDownStep(Graph *g, vertexSet *frontier, vertexSet *threadFrontiers,
                 int *flowMatrix, int *parents, int *pathCapacities, int t) {
    int maxThreads = omp_get_max_threads();
    bool foundT = false;
    #pragma omp parallel for schedule(static)
    for (int i=0; i < frontier->count; i++) {
        if (foundT) {
            i = frontier->count;
            continue;
        }
        int threadNum = omp_get_thread_num();
        int u = frontier->vertices[i];
        for (int v = 0; ((v < g->n) && (!foundT)); v++) {
            if (u == v) continue;
            int residual = g->capacities[IDX(u, v, g->n)] - flowMatrix[IDX(u, v, g->n)];
            if ((residual > 0) && (parents[v] == NOT_VISITED_MARKER) &&
                __sync_bool_compare_and_swap((&parents[v]), NOT_VISITED_MARKER, u)) {
                pathCapacities[v] = std::min(pathCapacities[u], residual);
                if (v != t) {
                    vertexSet *curFrontier = &threadFrontiers[threadNum];
                    int index = curFrontier->count++;
                    curFrontier->vertices[index] = v;
                } else {
                    foundT = true;
                }                
            }
        }
    }
    vertexSetClear(frontier);
    if (foundT) {
        return true;
    }
    #pragma omp parallel for schedule(static)
    for (int i=0; i < maxThreads; i++) {
        vertexSet *curFrontier = &threadFrontiers[i];
        int count = curFrontier->count;
        if (count > 0) {
            int index = __sync_fetch_and_add(&(frontier->count), count);
            for (int j = index; j < count + index; j++) {
                frontier->vertices[j] = curFrontier->vertices[j - index];
            }
        }
        vertexSetClear(curFrontier);
    }
    return false;
}
bool topDownStep ( Graph * g , vertexSet * frontier , vertexSet * threadFrontiers , int * flowMatrix , int * parents , int * pathCapacities , int t ) { int maxThreads = omp_get_max_threads ( ) ; bool foundT = false ; #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < frontier -> count ; i ++ ) { if ( foundT ) { i = frontier -> count ; continue ; } int threadNum = omp_get_thread_num ( ) ; int u = frontier -> vertices [ i ] ; for ( int v = 0 ; ( ( v < g -> n ) && ( ! foundT ) ) ; v ++ ) { if ( u == v ) continue ; int residual = g -> capacities [ IDX ( u , v , g -> n ) ] - flowMatrix [ IDX ( u , v , g -> n ) ] ; if ( ( residual > 0 ) && ( parents [ v ] == NOT_VISITED_MARKER ) && __sync_bool_compare_and_swap ( ( & parents [ v ] ) , NOT_VISITED_MARKER , u ) ) { pathCapacities [ v ] = std :: min ( pathCapacities [ u ] , residual ) ; if ( v != t ) { vertexSet * curFrontier = & threadFrontiers [ threadNum ] ; int index = curFrontier -> count ++ ; curFrontier -> vertices [ index ] = v ; } else { foundT = true ; } } } } vertexSetClear ( frontier ) ; if ( foundT ) { return true ; } #pragma  omp parallel for schedule(static) for ( int i = 0 ; i < maxThreads ; i ++ ) { vertexSet * curFrontier = & threadFrontiers [ i ] ; int count = curFrontier -> count ; if ( count > 0 ) { int index = __sync_fetch_and_add ( & ( frontier -> count ) , count ) ; for ( int j = index ; j < count + index ; j ++ ) { frontier -> vertices [ j ] = curFrontier -> vertices [ j - index ] ; } } vertexSetClear ( curFrontier ) ; } return false ; }
Take one step of "top-down" BFS.
Take one step of " top - down " BFS .
// hack to get early loop termination // attempt to add all neighbors to the thread's new frontier // copy individual new frontiers back to main, single frontier