// ************************************************************************** //
//                                                                            //
//    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.                                                                 //
// In contrast to ListRanking1, the version below does not make use of pointer//
// jumping. Instead, the indices are computed directly.                       //
// ************************************************************************** //

macro N = 8;

module ListRanking2([N]nat ?x,[N]nat y,event !rdy) {

    for(i=0..N-1)
        y[i] = x[i];
    for(i=0..log(N)-1) {
        for(j=exp(2,i)..N-1) {
            next(y[j]) = y[j] + y[j-exp(2,i)];
        }
        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]);
}