Robust/src/Benchmarks/Prefetch/2DFFT/dsm/fft2d.java

   1 public class fft2d extends Thread {
   2   //Title:        2-d mixed radix FFT.
   3   //Version:
   4   //Copyright:    Copyright (c) 1998
   5   //Author:       Dongyan Wang
   6   //Company:      University of Wisconsin-Milwaukee.
   7   //Description:
   8   //              . Use fft1d to perform fft2d.
   9   //
  10   // Code borrowed from :Java Digital Signal Processing book by Lyon and Rao
  11
  12   public fft1d fft1, fft2;
  13   public Matrix data;
  14   public int x0, x1, y0, y1;
  15
  16   // Constructor: 2-d FFT of Complex data.
  17   public fft2d(Matrix data, fft1d fft1, fft1d fft2, int x0, int x1, int y0, int y1) {
  18     this.data = data;
  19     this.x0 = x0;
  20     this.x1 = x1;
  21     this.y0 = y0;
  22     this.y1 = y1;
  23     this.fft1 = fft1;
  24     this.fft2 = fft2;
  25   }
  26
  27   public void run() {
  28     Barrier barr;
  29     barr = new Barrier("128.195.175.84");
  30     double tempdataRe[][];
  31     double tempdataIm[][];
  32     int rowlength, columnlength;
  33     double temRe[];// intermediate results
  34     double temIm[];
  35
  36
  37     atomic {
  38       rowlength = data.M;  //height
  39       columnlength = data.N; //width
  40       tempdataRe = data.dataRe;
  41       tempdataIm = data.dataIm;
  42
  43       // Calculate FFT for each row of the data.
  44       // for (int i = 0; i < height; i++)
  45       // fft1.fft(dataRe[i], dataIm[i]);
  46       for (int i = x0; i < x1; i++) {
  47         int N = fft1.N;
  48         if(columnlength != N) {
  49           System.printString("Error: the length of real part & imaginary part " + "of the input to 1-d FFT are different");
  50           return;
  51         } else {
  52           //Permute() operation on fft1
  53           //input of FFT
  54           double inputRe[] = tempdataRe[i]; //local array
  55           double inputIm[] = tempdataIm[i];
  56           //output of FFT
  57           double outputRe[] = fft1.outputRe; //local array
  58           double outputIm[] = fft1.outputIm;
  59           temRe = fft1.temRe;   // intermediate results
  60           temIm = fft1.temIm;
  61           int count[] = new int[fft1.MaxFactorsNumber];
  62           int j;
  63           int k = 0;
  64           for(int a = 0; a < N-1; a++) {
  65             outputRe[a] = inputRe[k];
  66             outputIm[a] = inputIm[k];
  67             j = 0;
  68             k = k + fft1.remain[j];
  69             count[0] = count[0] + 1;
  70             while (count[j] >= fft1.factors[j]) {
  71               count[j] = 0;
  72               int tmp;
  73               if(j == 0)
  74                 tmp = N;
  75               else
  76                 tmp = fft1.remain[j - 1];
  77               k = k - tmp + fft1.remain[j + 1];
  78               j++;
  79               count[j] = count[j] + 1;
  80             }
  81           }
  82           outputRe[N - 1] = inputRe[N - 1];
  83           outputIm[N - 1] = inputIm[N - 1];
  84
  85           //Twiddle oeration on fft1
  86           for (int factorIndex = 0; factorIndex < fft1.NumofFactors; factorIndex++) {
  87             twiddle(factorIndex, fft1, temRe, temIm, outputRe, outputIm);
  88           }
  89           //System.printString("ready to copy");
  90           // Copy the output[] data to input[], so the output can be
  91           // returned in the input array.
  92           for (int b = 0; b < N; b++) {
  93             inputRe[b] = outputRe[b];
  94             inputIm[b] = outputIm[b];
  95           }
  96         }
  97       }
  98     }
  99     //Start Barrier
 100     Barrier.enterBarrier(barr);
 101
 102     // Tranpose data.
 103     double mytemRe[][], mytemIm[][];
 104     atomic {
 105       tempdataRe = data.dataRe;
 106       tempdataIm = data.dataIm;
 107       for(int i = x0; i<x1; i++) {
 108         double tRe[] = tempdataRe[i];
 109         double tIm[] = tempdataIm[i];
 110         for(int j = 0; j<columnlength; j++) { //TODO Check this
 111           mytemRe[j][i] = tRe[j];
 112           mytemIm[j][i] = tIm[j];
 113         }
 114       }
 115     }
 116
 117     //Start Barrier
 118     Barrier.enterBarrier(barr);
 119    // double temRe[][] = transpose(data.dataRe);
 120     //double temIm[][] = transpose(data.dataIm);
 121
 122     // Calculate FFT for each column of the data.
 123     atomic {
 124       for (int j = y0; j < y1; j++) {
 125         //fft2.fft(temRe[j], temIm[j]);
 126         int N = fft2.N;
 127         if(rowlength != N) {
 128           System.printString("Error: the length of real part & imaginary part " + "of the input to 1-d FFT are different");
 129           return;
 130         } else {
 131           //Permute() operation on fft2
 132           //input of FFT
 133           double inputRe[] = mytemRe[j]; //local array
 134           double inputIm[] = mytemIm[j];
 135           //output of FFT
 136           double outputRe[] = fft2.outputRe; //local array
 137           double outputIm[] = fft2.outputIm;
 138           temRe = fft2.temRe;   // intermediate results
 139           temIm = fft2.temIm;
 140           int count[] = new int[fft2.MaxFactorsNumber];
 141           int r;
 142           int k = 0;
 143           for(int a = 0; a < N-1; a++) {
 144             outputRe[a] = inputRe[k];
 145             outputIm[a] = inputIm[k];
 146             r = 0;
 147             k = k + fft2.remain[r];
 148             count[0] = count[0] + 1;
 149             while (count[r] >= fft2.factors[r]) {
 150               count[r] = 0;
 151               int tmp;
 152               if(r == 0)
 153                 tmp = N;
 154               else
 155                 tmp = fft2.remain[r - 1];
 156               k = k - tmp + fft2.remain[r + 1];
 157               r++;
 158               count[r] = count[r] + 1;
 159             }
 160           }
 161           outputRe[N - 1] = inputRe[N - 1];
 162           outputIm[N - 1] = inputIm[N - 1];
 163
 164           //Twiddle oeration on fft2
 165           for (int factorIndex = 0; factorIndex < fft2.NumofFactors; factorIndex++) {
 166             twiddle(factorIndex, fft2, temRe, temIm, outputRe, outputIm);
 167           }
 168           //System.printString("ready to copy");
 169           // Copy the output[] data to input[], so the output can be
 170           // returned in the input array.
 171           for (int b = 0; b < N; b++) {
 172             inputRe[b] = outputRe[b];
 173             inputIm[b] = outputIm[b];
 174           }
 175         }
 176       }//end of fft2 for
 177     }
 178
 179     //Start Barrier
 180     Barrier.enterBarrier(barr);
 181
 182     // Tranpose data.
 183     // Copy the result to input[], so the output can be
 184     // returned in the input array.
 185
 186     for (int i = x0; i < x1; i++) {
 187       for (int j = y0; j < y1; j++) {
 188         tempdataRe[i][j] =  mytemRe[j][i];
 189         tempdataIm[i][j] = mytemIm[j][i];
 190         //inputRe[i * width + j] = temRe[j][i];
 191         //inputIm[i * width + j] = temIm[j][i];
 192       }
 193     }
 194   }//end of run
 195
 196   //("ready to twiddle");
 197   private void twiddle(int factorIndex, fft1d myfft, double[] temRe, double[] temIm,
 198       double[] outputRe, double[] outputIm) {
 199     // Get factor data.
 200     int sofarRadix = myfft.sofar[factorIndex];
 201     int radix = myfft.factors[factorIndex];
 202     int remainRadix = myfft.remain[factorIndex];
 203
 204     double tem;   // Temporary variable to do data exchange.
 205
 206     double W = 2 * (double) Math.setPI() / (sofarRadix * radix);
 207     double cosW = (double) Math.cos(W);
 208     double sinW = -(double) Math.sin(W);
 209
 210     double twiddleRe[] = new double[radix];
 211     double twiddleIm[] = new double[radix];
 212     double twRe = 1.0f, twIm = 0f;
 213
 214     //Initialize twiddle addBk.address variables.
 215     int dataOffset = 0, groupOffset = 0, address = 0;
 216
 217     for (int dataNo = 0; dataNo < sofarRadix; dataNo++) {
 218       //System.printString("datano="+dataNo);
 219       if (sofarRadix > 1) {
 220         twiddleRe[0] = 1.0f;
 221         twiddleIm[0] = 0.0f;
 222         twiddleRe[1] = twRe;
 223         twiddleIm[1] = twIm;
 224         for (int i = 2; i < radix; i++) {
 225           twiddleRe[i] = twRe * twiddleRe[i - 1] - twIm * twiddleIm[i - 1];
 226           twiddleIm[i] = twIm * twiddleRe[i - 1] + twRe * twiddleIm[i - 1];
 227         }
 228         tem = cosW * twRe - sinW * twIm;
 229         twIm = sinW * twRe + cosW * twIm;
 230         twRe = tem;
 231       }
 232       for (int groupNo = 0; groupNo < remainRadix; groupNo++) {
 233         //System.printString("groupNo="+groupNo);
 234         if ((sofarRadix > 1) && (dataNo > 0)) {
 235           temRe[0] = outputRe[address];
 236           temIm[0] = outputIm[address];
 237           int blockIndex = 1;
 238           do {
 239             address = address + sofarRadix;
 240             temRe[blockIndex] = twiddleRe[blockIndex] * outputRe[address] -
 241               twiddleIm[blockIndex] * outputIm[address];
 242             temIm[blockIndex] = twiddleRe[blockIndex] * outputIm[address] +
 243               twiddleIm[blockIndex] * outputRe[address];
 244             blockIndex++;
 245           } while (blockIndex < radix);
 246         } else
 247           for (int i = 0; i < radix; i++) {
 248             //System.printString("temRe.length="+temRe.length);
 249             //System.printString("i = "+i);
 250             temRe[i] = outputRe[address];
 251             temIm[i] = outputIm[address];
 252             address += sofarRadix;
 253           }
 254         //System.printString("radix="+radix);
 255         if(radix == 2) {
 256           tem = temRe[0] + temRe[1];
 257           temRe[1] = temRe[0] - temRe[1];
 258           temRe[0] = tem;
 259           tem = temIm[0] + temIm[1];
 260           temIm[1] = temIm[0] - temIm[1];
 261           temIm[0] = tem;
 262         } else if( radix == 3) {
 263           double t1Re = temRe[1] + temRe[2];
 264           double t1Im = temIm[1] + temIm[2];
 265           temRe[0] = temRe[0] + t1Re;
 266           temIm[0] = temIm[0] + t1Im;
 267
 268           double m1Re = myfft.cos2to3PI * t1Re;
 269           double m1Im = myfft.cos2to3PI * t1Im;
 270           double m2Re = myfft.sin2to3PI * (temIm[1] - temIm[2]);
 271           double m2Im = myfft.sin2to3PI * (temRe[2] - temRe[1]);
 272           double s1Re = temRe[0] + m1Re;
 273           double s1Im = temIm[0] + m1Im;
 274
 275           temRe[1] = s1Re + m2Re;
 276           temIm[1] = s1Im + m2Im;
 277           temRe[2] = s1Re - m2Re;
 278           temIm[2] = s1Im - m2Im;
 279         } else if(radix == 4) {
 280           fft4(temRe, temIm);
 281         } else if(radix == 5) {
 282           fft5(myfft, temRe, temIm);
 283         } else if(radix == 8) {
 284           fft8(myfft, temRe, temIm);
 285         } else if(radix == 10) {
 286           fft10(myfft, temRe, temIm);
 287         } else {
 288           fftPrime(radix, temRe, temIm);
 289         }
 290         address = groupOffset;
 291         for (int i = 0; i < radix; i++) {
 292           outputRe[address] = temRe[i];
 293           outputIm[address] = temIm[i];
 294           address += sofarRadix;
 295         }
 296         groupOffset += sofarRadix * radix;
 297         address = groupOffset;
 298       }
 299       groupOffset = ++dataOffset;
 300       address = groupOffset;
 301     }
 302   } //twiddle operation
 303
 304   // The two arguments dataRe[], dataIm[] are mainly for using in fft8();
 305   private void fft4(double dataRe[], double dataIm[]) {
 306     double t1Re,t1Im, t2Re,t2Im;
 307     double m2Re,m2Im, m3Re,m3Im;
 308
 309     t1Re = dataRe[0] + dataRe[2];
 310     t1Im = dataIm[0] + dataIm[2];
 311     t2Re = dataRe[1] + dataRe[3];
 312     t2Im = dataIm[1] + dataIm[3];
 313
 314     m2Re = dataRe[0] - dataRe[2];
 315     m2Im = dataIm[0] - dataIm[2];
 316     m3Re = dataIm[1] - dataIm[3];
 317     m3Im = dataRe[3] - dataRe[1];
 318
 319     dataRe[0] = t1Re + t2Re;
 320     dataIm[0] = t1Im + t2Im;
 321     dataRe[2] = t1Re - t2Re;
 322     dataIm[2] = t1Im - t2Im;
 323     dataRe[1] = m2Re + m3Re;
 324     dataIm[1] = m2Im + m3Im;
 325     dataRe[3] = m2Re - m3Re;
 326     dataIm[3] = m2Im - m3Im;
 327   }   // End of function fft4().
 328
 329   // The two arguments dataRe[], dataIm[] are mainly for using in fft10();
 330   private void fft5(fft1d myfft, double dataRe[], double dataIm[]) {
 331     double t1Re,t1Im, t2Re,t2Im, t3Re,t3Im, t4Re,t4Im, t5Re,t5Im;
 332     double m1Re,m1Im, m2Re,m2Im, m3Re,m3Im, m4Re,m4Im, m5Re,m5Im;
 333     double s1Re,s1Im, s2Re,s2Im, s3Re,s3Im, s4Re,s4Im, s5Re,s5Im;
 334
 335     t1Re = dataRe[1] + dataRe[4];
 336     t1Im = dataIm[1] + dataIm[4];
 337     t2Re = dataRe[2] + dataRe[3];
 338     t2Im = dataIm[2] + dataIm[3];
 339     t3Re = dataRe[1] - dataRe[4];
 340     t3Im = dataIm[1] - dataIm[4];
 341     t4Re = dataRe[3] - dataRe[2];
 342     t4Im = dataIm[3] - dataIm[2];
 343     t5Re = t1Re + t2Re;
 344     t5Im = t1Im + t2Im;
 345
 346     dataRe[0] = dataRe[0] + t5Re;
 347     dataIm[0] = dataIm[0] + t5Im;
 348
 349     m1Re = myfft.c51 * t5Re;
 350     m1Im = myfft.c51 * t5Im;
 351     m2Re = myfft.c52 * (t1Re - t2Re);
 352     m2Im = myfft.c52 * (t1Im - t2Im);
 353     m3Re = -(myfft.c53) * (t3Im + t4Im);
 354     m3Im = myfft.c53 * (t3Re + t4Re);
 355     m4Re = -(myfft.c54) * t4Im;
 356     m4Im = myfft.c54 * t4Re;
 357     m5Re = -(myfft.c55) * t3Im;
 358     m5Im = myfft.c55 * t3Re;
 359
 360     s3Re = m3Re - m4Re;
 361     s3Im = m3Im - m4Im;
 362     s5Re = m3Re + m5Re;
 363     s5Im = m3Im + m5Im;
 364     s1Re = dataRe[0] + m1Re;
 365     s1Im = dataIm[0] + m1Im;
 366     s2Re = s1Re + m2Re;
 367     s2Im = s1Im + m2Im;
 368     s4Re = s1Re - m2Re;
 369     s4Im = s1Im - m2Im;
 370
 371     dataRe[1] = s2Re + s3Re;
 372     dataIm[1] = s2Im + s3Im;
 373     dataRe[2] = s4Re + s5Re;
 374     dataIm[2] = s4Im + s5Im;
 375     dataRe[3] = s4Re - s5Re;
 376     dataIm[3] = s4Im - s5Im;
 377     dataRe[4] = s2Re - s3Re;
 378     dataIm[4] = s2Im - s3Im;
 379   }   // End of function fft5().
 380
 381   private void fft8(fft1d myfft, double[] temRe, double[] temIm) {
 382     double data1Re[] = new double[4];
 383     double data1Im[] = new double[4];
 384     double data2Re[] = new double[4];
 385     double data2Im[] = new double[4];
 386     double tem;
 387
 388     // To improve the speed, use direct assaignment instead for loop here.
 389     data1Re[0] = temRe[0];
 390     data2Re[0] = temRe[1];
 391     data1Re[1] = temRe[2];
 392     data2Re[1] = temRe[3];
 393     data1Re[2] = temRe[4];
 394     data2Re[2] = temRe[5];
 395     data1Re[3] = temRe[6];
 396     data2Re[3] = temRe[7];
 397
 398     data1Im[0] = temIm[0];
 399     data2Im[0] = temIm[1];
 400     data1Im[1] = temIm[2];
 401     data2Im[1] = temIm[3];
 402     data1Im[2] = temIm[4];
 403     data2Im[2] = temIm[5];
 404     data1Im[3] = temIm[6];
 405     data2Im[3] = temIm[7];
 406
 407     fft4(data1Re, data1Im);
 408     fft4(data2Re, data2Im);
 409
 410     tem = myfft.OnetoSqrt2 * (data2Re[1] + data2Im[1]);
 411     data2Im[1] = myfft.OnetoSqrt2 * (data2Im[1] - data2Re[1]);
 412     data2Re[1] = tem;
 413     tem = data2Im[2];
 414     data2Im[2] = -data2Re[2];
 415     data2Re[2] = tem;
 416     tem = myfft.OnetoSqrt2 * (data2Im[3] - data2Re[3]);
 417     data2Im[3] = -(myfft.OnetoSqrt2) * (data2Re[3] + data2Im[3]);
 418     data2Re[3] = tem;
 419
 420     temRe[0] = data1Re[0] + data2Re[0];
 421     temRe[4] = data1Re[0] - data2Re[0];
 422     temRe[1] = data1Re[1] + data2Re[1];
 423     temRe[5] = data1Re[1] - data2Re[1];
 424     temRe[2] = data1Re[2] + data2Re[2];
 425     temRe[6] = data1Re[2] - data2Re[2];
 426     temRe[3] = data1Re[3] + data2Re[3];
 427     temRe[7] = data1Re[3] - data2Re[3];
 428
 429     temIm[0] = data1Im[0] + data2Im[0];
 430     temIm[4] = data1Im[0] - data2Im[0];
 431     temIm[1] = data1Im[1] + data2Im[1];
 432     temIm[5] = data1Im[1] - data2Im[1];
 433     temIm[2] = data1Im[2] + data2Im[2];
 434     temIm[6] = data1Im[2] - data2Im[2];
 435     temIm[3] = data1Im[3] + data2Im[3];
 436     temIm[7] = data1Im[3] - data2Im[3];
 437   }   // End of function fft8().
 438
 439   private void fft10(fft1d myfft, double[] temRe, double[] temIm) {
 440     double data1Re[] = new double[5];
 441     double data1Im[] = new double[5];
 442     double data2Re[] = new double[5];
 443     double data2Im[] = new double[5];
 444
 445     // To improve the speed, use direct assaignment instead for loop here.
 446     data1Re[0] = temRe[0];
 447     data2Re[0] = temRe[5];
 448     data1Re[1] = temRe[2];
 449     data2Re[1] = temRe[7];
 450     data1Re[2] = temRe[4];
 451     data2Re[2] = temRe[9];
 452     data1Re[3] = temRe[6];
 453     data2Re[3] = temRe[1];
 454     data1Re[4] = temRe[8];
 455     data2Re[4] = temRe[3];
 456
 457     data1Im[0] = temIm[0];
 458     data2Im[0] = temIm[5];
 459     data1Im[1] = temIm[2];
 460     data2Im[1] = temIm[7];
 461     data1Im[2] = temIm[4];
 462     data2Im[2] = temIm[9];
 463     data1Im[3] = temIm[6];
 464     data2Im[3] = temIm[1];
 465     data1Im[4] = temIm[8];
 466     data2Im[4] = temIm[3];
 467
 468     fft5(myfft, data1Re, data1Im);
 469     fft5(myfft, data2Re, data2Im);
 470
 471     temRe[0] = data1Re[0] + data2Re[0];
 472     temRe[5] = data1Re[0] - data2Re[0];
 473     temRe[6] = data1Re[1] + data2Re[1];
 474     temRe[1] = data1Re[1] - data2Re[1];
 475     temRe[2] = data1Re[2] + data2Re[2];
 476     temRe[7] = data1Re[2] - data2Re[2];
 477     temRe[8] = data1Re[3] + data2Re[3];
 478     temRe[3] = data1Re[3] - data2Re[3];
 479     temRe[4] = data1Re[4] + data2Re[4];
 480     temRe[9] = data1Re[4] - data2Re[4];
 481
 482     temIm[0] = data1Im[0] + data2Im[0];
 483     temIm[5] = data1Im[0] - data2Im[0];
 484     temIm[6] = data1Im[1] + data2Im[1];
 485     temIm[1] = data1Im[1] - data2Im[1];
 486     temIm[2] = data1Im[2] + data2Im[2];
 487     temIm[7] = data1Im[2] - data2Im[2];
 488     temIm[8] = data1Im[3] + data2Im[3];
 489     temIm[3] = data1Im[3] - data2Im[3];
 490     temIm[4] = data1Im[4] + data2Im[4];
 491     temIm[9] = data1Im[4] - data2Im[4];
 492   }   // End of function fft10().
 493
 494   private void fftPrime(int radix, double[] temRe, double[] temIm) {
 495     // Initial WRe, WIm.
 496     double W = 2 * (double) Math.setPI() / radix;
 497     double cosW = (double) Math.cos(W);
 498     double sinW = -(double) Math.sin(W);
 499     double WRe[] = new double[radix];
 500     double WIm[] = new double[radix];
 501
 502     WRe[0] = 1;
 503     WIm[0] = 0;
 504     WRe[1] = cosW;
 505     WIm[1] = sinW;
 506
 507     for (int i = 2; i < radix; i++) {
 508       WRe[i] = cosW * WRe[i - 1] - sinW * WIm[i - 1];
 509       WIm[i] = sinW * WRe[i - 1] + cosW * WIm[i - 1];
 510     }
 511
 512     // FFT of prime length data, using DFT, can be improved in the future.
 513     double rere, reim, imre, imim;
 514     int j, k;
 515     int max = (radix + 1) / 2;
 516
 517     double tem1Re[] = new double[max];
 518     double tem1Im[] = new double[max];
 519     double tem2Re[] = new double[max];
 520     double tem2Im[] = new double[max];
 521
 522     for (j = 1; j < max; j++) {
 523       tem1Re[j] = temRe[j] + temRe[radix - j];
 524       tem1Im[j] = temIm[j] - temIm[radix - j];
 525       tem2Re[j] = temRe[j] - temRe[radix - j];
 526       tem2Im[j] = temIm[j] + temIm[radix - j];
 527     }
 528
 529     for (j = 1; j < max; j++) {
 530       temRe[j] = temRe[0];
 531       temIm[j] = temIm[0];
 532       temRe[radix - j] = temRe[0];
 533       temIm[radix - j] = temIm[0];
 534       k = j;
 535       for (int i = 1; i < max; i++) {
 536         rere = WRe[k] * tem1Re[i];
 537         imim = WIm[k] * tem1Im[i];
 538         reim = WRe[k] * tem2Im[i];
 539         imre = WIm[k] * tem2Re[i];
 540
 541         temRe[radix - j] += rere + imim;
 542         temIm[radix - j] += reim - imre;
 543         temRe[j] += rere - imim;
 544         temIm[j] += reim + imre;
 545
 546         k = k + j;
 547         if (k >= radix)
 548           k = k - radix;
 549       }
 550     }
 551     for (j = 1; j < max; j++) {
 552       temRe[0] = temRe[0] + tem1Re[j];
 553       temIm[0] = temIm[0] + tem2Im[j];
 554     }
 555   }   // End of function fftPrime().
 556
 557   public static void main(String[] args) {
 558     int NUM_THREADS = 1;
 559     int SIZE = 800;
 560     int inputWidth = 10;
 561     if(args.length>0) {
 562       NUM_THREADS=Integer.parseInt(args[0]);
 563       if(args.length > 1)
 564         SIZE = Integer.parseInt(args[1]);
 565     }
 566
 567     // Initialize Matrix
 568     // Matrix inputRe, inputIm;
 569
 570     double[] inputRe;
 571     double[] inputIm;
 572     atomic {
 573       inputRe = global new double[SIZE];
 574       inputIm = global new double[SIZE];
 575
 576       for(int i = 0; i<SIZE; i++){
 577         inputRe[i] = i;
 578         inputIm[i] = i;
 579       }
 580     }
 581
 582     int[] mid = new int[8];
 583     mid[0] = (128<<24)|(195<<16)|(175<<8)|84; //dw-10
 584     mid[1] = (128<<24)|(195<<16)|(175<<8)|85; //dw-11
 585     mid[2] = (128<<24)|(195<<16)|(175<<8)|86; //dw-12
 586     mid[3] = (128<<24)|(195<<16)|(175<<8)|87; //dw-13
 587     mid[4] = (128<<24)|(195<<16)|(175<<8)|88; //dw-14
 588     mid[5] = (128<<24)|(195<<16)|(175<<8)|89; //dw-15
 589     mid[6] = (128<<24)|(195<<16)|(175<<8)|90; //dw-16
 590     mid[7] = (128<<24)|(195<<16)|(175<<8)|91; //dw-17
 591
 592     // Start Barrier Server
 593     BarrierServer mybarr;
 594     atomic {
 595        mybarr = global new BarrierServer(NUM_THREADS);
 596     }
 597     mybarr.start(mid[0]);
 598
 599
 600     // Width and height of 2-d matrix inputRe or inputIm.
 601     int width, height;
 602     width = inputWidth;
 603     int Relength, Imlength;
 604     atomic {
 605       height = inputRe.length / width;
 606       Relength = inputRe.length;
 607       Imlength = inputIm.length;
 608     }
 609
 610     Matrix data;
 611     fft1d fft1, fft2;
 612     // First make sure inputRe & inputIm are of the same length in terms of columns
 613     if (Relength != Imlength) {
 614       System.printString("Error: the length of real part & imaginary part " +
 615           "of the input to 2-d FFT are different");
 616       return;
 617     } else {
 618       atomic {
 619         fft1 = global new fft1d(width);
 620         fft2 = global new fft1d(height);
 621         // Set up data for FFT transform
 622         data = global new Matrix(height, width);
 623         data.setValues(inputRe, inputIm);
 624       }
 625
 626       // Create threads to do FFT
 627       fft2d[] myfft2d;
 628       atomic {
 629         myfft2d = global new fft2d[NUM_THREADS];
 630         int increment = SIZE/NUM_THREADS;
 631         int base = 0;
 632         for(int i =0 ; i<NUM_THREADS; i++) {
 633           if((i+1)==NUM_THREADS)
 634             myfft2d[i] = global new fft2d(data, fft1, fft2, base, SIZE, 0, SIZE);
 635           else
 636             myfft2d[i] = global new fft2d(data, fft1, fft2, base, base+increment, 0, SIZE);
 637           base+=increment;
 638         }
 639       }
 640
 641       boolean waitfordone=true;
 642       while(waitfordone) {
 643         atomic {
 644           if (mybarr.done)
 645             waitfordone=false;
 646         }
 647       }
 648
 649       fft2d tmp;
 650       //Start a thread to compute each c[l,n]
 651       for(int i = 0; i<NUM_THREADS; i++) {
 652         atomic {
 653           tmp = myfft2d[i];
 654         }
 655         tmp.start(mid[i]);
 656       }
 657
 658       //Wait for thread to finish
 659       for(int i = 0; i<NUM_THREADS; i++) {
 660         atomic {
 661           tmp = myfft2d[i];
 662         }
 663         tmp.join();
 664       }
 665     }
 666
 667     // Display results
 668     // Tranpose data.
 669     // Copy the result to input[], so the output can be
 670     // returned in the input array.
 671     atomic {
 672       for (int i = 0; i < height; i++) {
 673         for (int j = 0; j < width; j++) {
 674           //inputRe[i * width + j] = temRe[j][i];
 675           System.printInt((int)inputRe[i * width + j]);
 676           //inputIm[i * width + j] = temIm[j][i];
 677           System.printInt((int)inputIm[i * width + j]);
 678         }
 679       }
 680     }
 681   }
 682 }