tree reduction

tree-red.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <thread>
#include <mutex>
#include <cstring>

constexpr bool isPowerOf2(int n) { return (!(n & (n - 1))); }

constexpr unsigned nextPowerOf2(int n) {
  return (n <= 1) ? 1 : (isPowerOf2(n) ? n : (2 * nextPowerOf2((n + 1) / 2)));
}
using namespace std;
const int N = 1500;
const int MAX_THREADS = 64;


float treered(float *a, int n) {
    float *A = new float[n];
    memcpy(A, a, sizeof(*a) * n);

    float sum = 0;
    for (int s = 2; s <= n; s <<= 1) {   
        int ws = min(n/s, MAX_THREADS);
        int ub = min(ws*s, n);
        int lb = 0;  
        //cerr << "ws:" << ws << "\n";  
        while (lb < ub) {
            //cerr << " " << lb << " to " << ub << " step " << s << " : ";

            for (int i = lb; i < ub; i+=s) {
                //cerr << i << ",";
                int id = i + s/2;
                A[i] += A[id];
            }
            //cerr << "\n";           
            lb = ub;
            
            ub += ws*s;
            ub = min(ub, n);        
        }
     
        //[&](){for (int x=0; x<n; ++x) cout << A[x] << "."; cout << "\n";}();
    }

    if (!isPowerOf2(n)) 
        A[0] += A[nextPowerOf2(n)/2];
    return A[0];
}

int main() {
    float A[N];
    for (int i = 0; i < N; i++)

            A[i] = 1;   

    auto res = treered(A, N);
    cout << "res:" << res << "\n";

}