benchmark/fourier/parallel/pi/xeonphi/openmp/fourier-parallel-pi-xeonphi-openmp.c
int run(tr_t t_shared){
  uint32_t size, iter, offset, bit;         // butterfly size, offset and iter,
  uint32_t which_butterfly, which_half;     // which butterfly, and which half,
  tmr_t    tm_funnel, tm_tube;              // tmr_t objects (for timing)
  tr_t     t;                               // per-thread copy of shared tr_t.

  
  // Initialize the data (or ret -1 err, cleaning up any malloc'd data first)
  if(initialize_data(&t_shared)){
    cleanup_data(&t_shared);
    goto err;
  }

  // Spawn P threads
  omp_set_num_threads(t_shared.P);
  #pragma omp parallel private(size, iter, offset, bit, \
                               which_butterfly, which_half, \
                               tm_funnel, tm_tube, t)
  {
    
    // Populate the local tr_t object, and determine which Pi is this.
    t    = t_shared;
    t.Pi = omp_get_thread_num();

    // We need:
    // - N entries for the input scratchpad, and
    if((t.tmp_in = (data_t*)malloc(sizeof(data_t)*t.N)) == NULL){
      perror_out("malloc error");
    }
    // - N entries for the output scratchpad.
    if((t.tmp_out = (data_t*)malloc(sizeof(data_t)*t.N)) == NULL){
      perror_out("malloc error");
    }

    // Copy the full input to the input scratchpad.
    copy_to(t.tmp_in, t.in, t.N);



    // (1) Tree stage: 
    // ---------------

    // Start the timer for the funnel stage
    timer_start(&tm_funnel);

    // For the first log P iters
    // (i.e. butterfly sizes N,     N/2,       ..., 2(N/P),
    //       iteration stage log P, log P - 1, ..., 1),
    for(size = t.N, iter = ilog2(t.P); size > t.N/t.P; size /= 2, iter--){

      // Determine _which_ butterfly to compute, depending on (Pi >> iter)
      which_butterfly = (t.Pi >> iter);

      // Determine _which_ segment_ of size 'size' to compute the butterfly on
      offset = which_butterfly * size;

      // Determine _which half_, depending on the parity of the 1st, 2nd, ...
      // most significant bit of Pi.
      which_half = ((t.Pi >> (iter - 1)) % 2 == 0);

      // And compute the butterfly accordingly
      if(which_half){
        butterfly_left(
          t.tmp_out + offset,  // output to the _1st_ half of the scratchpad
          t.tmp_in  + offset,  // and reading from the input scratchpad.
          size, t.N);
      }
      else{
        butterfly_right(
          t.tmp_out + offset,  // output to the _2nd_ half of the scratchpad
          t.tmp_in  + offset,  // and reading from the input scratchpad.
          size, t.N);      
      }

      // And swap scratchpads, so that the new results become the input for
      // the next iteration.
      swap_scratchpads(&t);
    }

    // Stop the timer for the tree stage
    timer_stop(&tm_funnel);


    // (2) Cylinder stage
    // ------------------

    // Start the timer for the tube stage
    timer_start(&tm_tube);

    // For the last log N/P iters
    // (i.e. butterfly sizes N/P, (N/P)/2, ..., 2), 
    // we work only on the portion of the output assigned to this processor
    for(size = t.N/t.P; size > 1; size /= 2){

      // Compute 1, 2, ..., (N/P)/2 butterflies of size N/P, (N/P)/2, ..., 2 
      // over _consecutive_ intervals across the assigned segment (of size N/P)
      // (which recall starts from (t.N/t.P)).
      for(offset=(t.N/t.P)*t.Pi; offset<(t.N/t.P)*t.Pi+t.N/t.P; offset+=size){
        butterfly(
          t.tmp_out + offset,       // output to the _assigned_ segment,
          t.tmp_in  + offset,       // and reading from the _assigned_ segment.
          size, t.N);
      }

      // And swap scratchpads, so that the new results become the input for
      // the next iteration.
      swap_scratchpads(&t);
    }

    // Stop the timer for the tube stage
    timer_stop(&tm_tube);


    // If not in test mode, show elapsed times (total, funnel and tube stages)
    if(!t.test_mode && t.Pi == 0){
      if(!t.no_header){ 
        print_out("n\tp\ttime (total)\t"
                  "time (stage 1)\ttime (stage 2)\n"); };
      print_out("%u\t%u\t%lf\t%lf\t%lf\n", 
                t.N, t.P, tm_funnel.elapsed + tm_tube.elapsed, 
                tm_funnel.elapsed, tm_tube.elapsed);
    }
    // Otherwise, copy the result from the _assigned_ segment of the input
    // scratchpad (which will contain the new results at this point) to the 
    // output, in bit-reversed order.
    else{
      for(bit = (t.N/t.P)*t.Pi; bit < (t.N/t.P)*t.Pi+t.N/t.P; bit++)
        t.out[bit_reverse(bit, ilog2(t.N))] = t.tmp_in[bit];
    }
    

    // Free the data
    if(t.tmp_in  != NULL){ free(t.tmp_in);   t.tmp_in  = NULL; }
    if(t.tmp_out != NULL){ free(t.tmp_out);  t.tmp_out = NULL; }

  }

  // If in test mode, print out the result, and verify that it is correct.
  if(t_shared.test_mode){
    print_output(&t_shared);
    verify_results(&t_shared);
  }

  // Cleanup the data, and return
  cleanup_data(&t_shared);
  return 0;

err:
  stderr_out("Could not run the transform\n");
  return -1;
}
// This function runs the given transform on P separate processors. Returns 0
// if success or -1 if err.
//
//   t:                      copy of tr_t object to use
//
//   returns:                0 if success, or -1 if error.
// 
This function runs the given transform on P separate processors. Returns 0
if success or -1 if err.

copy of tr_t object to use

0 if success, or -1 if error.
This function runs the given transform on P separate processors . Returns 0 if success or - 1 if err . copy of tr_t object to use 0 if success or - 1 if error .
int run(tr_t t_shared){
  uint32_t size, iter, offset, bit;         
  uint32_t which_butterfly, which_half;     
  tmr_t    tm_funnel, tm_tube;              
  tr_t     t;                               
  if(initialize_data(&t_shared)){
    cleanup_data(&t_shared);
    goto err;
  }
  omp_set_num_threads(t_shared.P);
  #pragma omp parallel private(size, iter, offset, bit, \
                               which_butterfly, which_half, \
                               tm_funnel, tm_tube, t)
  {
    t    = t_shared;
    t.Pi = omp_get_thread_num();
    if((t.tmp_in = (data_t*)malloc(sizeof(data_t)*t.N)) == NULL){
      perror_out("malloc error");
    }
    if((t.tmp_out = (data_t*)malloc(sizeof(data_t)*t.N)) == NULL){
      perror_out("malloc error");
    }
    copy_to(t.tmp_in, t.in, t.N);
    timer_start(&tm_funnel);
    for(size = t.N, iter = ilog2(t.P); size > t.N/t.P; size /= 2, iter--){
      which_butterfly = (t.Pi >> iter);
      offset = which_butterfly * size;
      which_half = ((t.Pi >> (iter - 1)) % 2 == 0);
      if(which_half){
        butterfly_left(
          t.tmp_out + offset,  
          t.tmp_in  + offset,  
          size, t.N);
      }
      else{
        butterfly_right(
          t.tmp_out + offset,  
          t.tmp_in  + offset,  
          size, t.N);      
      }
      swap_scratchpads(&t);
    }
    timer_stop(&tm_funnel);
    ---
    timer_start(&tm_tube);
    for(size = t.N/t.P; size > 1; size /= 2){
      for(offset=(t.N/t.P)*t.Pi; offset<(t.N/t.P)*t.Pi+t.N/t.P; offset+=size){
        butterfly(
          t.tmp_out + offset,       
          t.tmp_in  + offset,       
          size, t.N);
      }
      swap_scratchpads(&t);
    }
    timer_stop(&tm_tube);
    if(!t.test_mode && t.Pi == 0){
      if(!t.no_header){ 
        print_out("n\tp\ttime (total)\t"
                  "time (stage 1)\ttime (stage 2)\n"); };
      print_out("%u\t%u\t%lf\t%lf\t%lf\n", 
                t.N, t.P, tm_funnel.elapsed + tm_tube.elapsed, 
                tm_funnel.elapsed, tm_tube.elapsed);
    }
    else{
      for(bit = (t.N/t.P)*t.Pi; bit < (t.N/t.P)*t.Pi+t.N/t.P; bit++)
        t.out[bit_reverse(bit, ilog2(t.N))] = t.tmp_in[bit];
    }
    if(t.tmp_in  != NULL){ free(t.tmp_in);   t.tmp_in  = NULL; }
    if(t.tmp_out != NULL){ free(t.tmp_out);  t.tmp_out = NULL; }
  }
  if(t_shared.test_mode){
    print_output(&t_shared);
    verify_results(&t_shared);
  }
  cleanup_data(&t_shared);
  return 0;
err:
  stderr_out("Could not run the transform\n");
  return -1;
}
int run ( tr_t t_shared ) { uint32_t size , iter , offset , bit ; uint32_t which_butterfly , which_half ; tmr_t tm_funnel , tm_tube ; tr_t t ; if ( initialize_data ( & t_shared ) ) { cleanup_data ( & t_shared ) ; goto err ; } omp_set_num_threads ( t_shared . P ) ; #pragma  omp parallel private(size, iter, offset, bit, \
                               which_butterfly, which_half, \
                               tm_funnel, tm_tube, t) { t = t_shared ; t . Pi = omp_get_thread_num ( ) ; if ( ( t . tmp_in = ( data_t * ) malloc ( sizeof ( data_t ) * t . N ) ) == NULL ) { perror_out ( " " ) ; } if ( ( t . tmp_out = ( data_t * ) malloc ( sizeof ( data_t ) * t . N ) ) == NULL ) { perror_out ( " " ) ; } copy_to ( t . tmp_in , t . in , t . N ) ; timer_start ( & tm_funnel ) ; for ( size = t . N , iter = ilog2 ( t . P ) ; size > t . N / t . P ; size /= 2 , iter -- ) { which_butterfly = ( t . Pi >> iter ) ; offset = which_butterfly * size ; which_half = ( ( t . Pi >> ( iter - 1 ) ) % 2 == 0 ) ; if ( which_half ) { butterfly_left ( t . tmp_out + offset , t . tmp_in + offset , size , t . N ) ; } else { butterfly_right ( t . tmp_out + offset , t . tmp_in + offset , size , t . N ) ; } swap_scratchpads ( & t ) ; } timer_stop ( & tm_funnel ) ; timer_start ( & tm_tube ) ; for ( size = t . N / t . P ; size > 1 ; size /= 2 ) { for ( offset = ( t . N / t . P ) * t . Pi ; offset < ( t . N / t . P ) * t . Pi + t . N / t . P ; offset += size ) { butterfly ( t . tmp_out + offset , t . tmp_in + offset , size , t . N ) ; } swap_scratchpads ( & t ) ; } timer_stop ( & tm_tube ) ; if ( ! t . test_mode && t . Pi == 0 ) { if ( ! t . no_header ) { print_out ( " \t \t \t " " \t \n " ) ; } ; print_out ( " \t \t \t \t \n " , t . N , t . P , tm_funnel . elapsed + tm_tube . elapsed , tm_funnel . elapsed , tm_tube . elapsed ) ; } else { for ( bit = ( t . N / t . P ) * t . Pi ; bit < ( t . N / t . P ) * t . Pi + t . N / t . P ; bit ++ ) t . out [ bit_reverse ( bit , ilog2 ( t . N ) ) ] = t . tmp_in [ bit ] ; } if ( t . tmp_in != NULL ) { free ( t . tmp_in ) ; t . tmp_in = NULL ; } if ( t . tmp_out != NULL ) { free ( t . tmp_out ) ; t . tmp_out = NULL ; } } if ( t_shared . test_mode ) { print_output ( & t_shared ) ; verify_results ( & t_shared ) ; } cleanup_data ( & t_shared ) ; return 0 ; err : stderr_out ( " \n " ) ; return -1 ; }
This function runs the given transform on P separate processors.
This function runs the given transform on P separate processors .
// butterfly size, offset and iter, // which butterfly, and which half, // tmr_t objects (for timing) // per-thread copy of shared tr_t. // Initialize the data (or ret -1 err, cleaning up any malloc'd data first) // Spawn P threads // Populate the local tr_t object, and determine which Pi is this. // We need: // - N entries for the input scratchpad, and // - N entries for the output scratchpad. // Copy the full input to the input scratchpad. // (1) Tree stage:  // --------------- // Start the timer for the funnel stage // For the first log P iters // (i.e. butterfly sizes N,     N/2,       ..., 2(N/P), //       iteration stage log P, log P - 1, ..., 1), // Determine _which_ butterfly to compute, depending on (Pi >> iter) // Determine _which_ segment_ of size 'size' to compute the butterfly on // Determine _which half_, depending on the parity of the 1st, 2nd, ... // most significant bit of Pi. // And compute the butterfly accordingly // output to the _1st_ half of the scratchpad // and reading from the input scratchpad. // output to the _2nd_ half of the scratchpad // and reading from the input scratchpad. // And swap scratchpads, so that the new results become the input for // the next iteration. // Stop the timer for the tree stage // (2) Cylinder stage // ------------------ // Start the timer for the tube stage // For the last log N/P iters // (i.e. butterfly sizes N/P, (N/P)/2, ..., 2),  // we work only on the portion of the output assigned to this processor // Compute 1, 2, ..., (N/P)/2 butterflies of size N/P, (N/P)/2, ..., 2  // over _consecutive_ intervals across the assigned segment (of size N/P) // (which recall starts from (t.N/t.P)). // output to the _assigned_ segment, // and reading from the _assigned_ segment. // And swap scratchpads, so that the new results become the input for // the next iteration. // Stop the timer for the tube stage // If not in test mode, show elapsed times (total, funnel and tube stages) // Otherwise, copy the result from the _assigned_ segment of the input // scratchpad (which will contain the new results at this point) to the  // output, in bit-reversed order. // Free the data // If in test mode, print out the result, and verify that it is correct. // Cleanup the data, and return