// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// The parallel prefix problem (also known a list ranking see [KaRa88]) is    //
// defined as follows: For an array x[0..N-1], we have to compute the values  //
// y[i] = sum(j=0..i) x[j] for all i=0..N-1. The module below computes these  //
// values in log(N) time using O(N) processors which is an optimal PRAM       //
// algorithm.                                                                 //
// Clearly, the problem can be generalized to computed not the sum, but for   //
// any associative function f the values y[i] = f(x[0],f(x[1],...x[i]).       //
// The algorithm is based on pointer jumping, a frequently used technique     //
// where each predecessor pointer is replaced by the successor's successor    //
// pointer.                                                                   //
// ************************************************************************** //

macro N = 8;

module ListRanking1([N]nat ?x,[N]nat y,event !rdy) {
    [N]nat{N+1} suc;

    for(i=0..N-1) {
        y[i] = x[i];
        suc[i] = i+1;
    }
    for(i=0..log(N)-1) {
        for(j=0..N-1) {
            if(suc[j]<N) {
                next(y[suc[j]]) = y[j] + y[suc[j]];
                next(suc[j]) = suc[suc[j]];
            }
        }
        pause;
    }
    emit(rdy);
}
drivenby {
    for(i=0..N-1) {
        x[i] = i+1;
    }
    await(rdy);
    for(i=0..N-1)
        assert(y[i] == sum(j=0..i) x[j]);
}