// ************************************************************************** // // // // 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 // // // // ************************************************************************** // [128]nat x; thread ParallelPrefixTree_128 { // up-level 0 x[1] = x[0] + x[1]; x[3] = x[2] + x[3]; x[5] = x[4] + x[5]; x[7] = x[6] + x[7]; x[9] = x[8] + x[9]; x[11] = x[10] + x[11]; x[13] = x[12] + x[13]; x[15] = x[14] + x[15]; x[17] = x[16] + x[17]; x[19] = x[18] + x[19]; x[21] = x[20] + x[21]; x[23] = x[22] + x[23]; x[25] = x[24] + x[25]; x[27] = x[26] + x[27]; x[29] = x[28] + x[29]; x[31] = x[30] + x[31]; x[33] = x[32] + x[33]; x[35] = x[34] + x[35]; x[37] = x[36] + x[37]; x[39] = x[38] + x[39]; x[41] = x[40] + x[41]; x[43] = x[42] + x[43]; x[45] = x[44] + x[45]; x[47] = x[46] + x[47]; x[49] = x[48] + x[49]; x[51] = x[50] + x[51]; x[53] = x[52] + x[53]; x[55] = x[54] + x[55]; x[57] = x[56] + x[57]; x[59] = x[58] + x[59]; x[61] = x[60] + x[61]; x[63] = x[62] + x[63]; x[65] = x[64] + x[65]; x[67] = x[66] + x[67]; x[69] = x[68] + x[69]; x[71] = x[70] + x[71]; x[73] = x[72] + x[73]; x[75] = x[74] + x[75]; x[77] = x[76] + x[77]; x[79] = x[78] + x[79]; x[81] = x[80] + x[81]; x[83] = x[82] + x[83]; x[85] = x[84] + x[85]; x[87] = x[86] + x[87]; x[89] = x[88] + x[89]; x[91] = x[90] + x[91]; x[93] = x[92] + x[93]; x[95] = x[94] + x[95]; x[97] = x[96] + x[97]; x[99] = x[98] + x[99]; x[101] = x[100] + x[101]; x[103] = x[102] + x[103]; x[105] = x[104] + x[105]; x[107] = x[106] + x[107]; x[109] = x[108] + x[109]; x[111] = x[110] + x[111]; x[113] = x[112] + x[113]; x[115] = x[114] + x[115]; x[117] = x[116] + x[117]; x[119] = x[118] + x[119]; x[121] = x[120] + x[121]; x[123] = x[122] + x[123]; x[125] = x[124] + x[125]; x[127] = x[126] + x[127]; // up-level 1 x[3] = x[1] + x[3]; x[7] = x[5] + x[7]; x[11] = x[9] + x[11]; x[15] = x[13] + x[15]; x[19] = x[17] + x[19]; x[23] = x[21] + x[23]; x[27] = x[25] + x[27]; x[31] = x[29] + x[31]; x[35] = x[33] + x[35]; x[39] = x[37] + x[39]; x[43] = x[41] + x[43]; x[47] = x[45] + x[47]; x[51] = x[49] + x[51]; x[55] = x[53] + x[55]; x[59] = x[57] + x[59]; x[63] = x[61] + x[63]; x[67] = x[65] + x[67]; x[71] = x[69] + x[71]; x[75] = x[73] + x[75]; x[79] = x[77] + x[79]; x[83] = x[81] + x[83]; x[87] = x[85] + x[87]; x[91] = x[89] + x[91]; x[95] = x[93] + x[95]; x[99] = x[97] + x[99]; x[103] = x[101] + x[103]; x[107] = x[105] + x[107]; x[111] = x[109] + x[111]; x[115] = x[113] + x[115]; x[119] = x[117] + x[119]; x[123] = x[121] + x[123]; x[127] = x[125] + x[127]; // up-level 2 x[7] = x[3] + x[7]; x[15] = x[11] + x[15]; x[23] = x[19] + x[23]; x[31] = x[27] + x[31]; x[39] = x[35] + x[39]; x[47] = x[43] + x[47]; x[55] = x[51] + x[55]; x[63] = x[59] + x[63]; x[71] = x[67] + x[71]; x[79] = x[75] + x[79]; x[87] = x[83] + x[87]; x[95] = x[91] + x[95]; x[103] = x[99] + x[103]; x[111] = x[107] + x[111]; x[119] = x[115] + x[119]; x[127] = x[123] + x[127]; // up-level 3 x[15] = x[7] + x[15]; x[31] = x[23] + x[31]; x[47] = x[39] + x[47]; x[63] = x[55] + x[63]; x[79] = x[71] + x[79]; x[95] = x[87] + x[95]; x[111] = x[103] + x[111]; x[127] = x[119] + x[127]; // up-level 4 x[31] = x[15] + x[31]; x[63] = x[47] + x[63]; x[95] = x[79] + x[95]; x[127] = x[111] + x[127]; // up-level 5 x[63] = x[31] + x[63]; x[127] = x[95] + x[127]; // up-level 6 x[127] = x[63] + x[127]; // up-level 7 // down-level 8 // down-level 9 x[95] = x[63] + x[95]; // down-level 10 x[47] = x[31] + x[47]; x[79] = x[63] + x[79]; x[111] = x[95] + x[111]; // down-level 11 x[23] = x[15] + x[23]; x[39] = x[31] + x[39]; x[55] = x[47] + x[55]; x[71] = x[63] + x[71]; x[87] = x[79] + x[87]; x[103] = x[95] + x[103]; x[119] = x[111] + x[119]; // down-level 12 x[11] = x[7] + x[11]; x[19] = x[15] + x[19]; x[27] = x[23] + x[27]; x[35] = x[31] + x[35]; x[43] = x[39] + x[43]; x[51] = x[47] + x[51]; x[59] = x[55] + x[59]; x[67] = x[63] + x[67]; x[75] = x[71] + x[75]; x[83] = x[79] + x[83]; x[91] = x[87] + x[91]; x[99] = x[95] + x[99]; x[107] = x[103] + x[107]; x[115] = x[111] + x[115]; x[123] = x[119] + x[123]; // down-level 13 x[5] = x[3] + x[5]; x[9] = x[7] + x[9]; x[13] = x[11] + x[13]; x[17] = x[15] + x[17]; x[21] = x[19] + x[21]; x[25] = x[23] + x[25]; x[29] = x[27] + x[29]; x[33] = x[31] + x[33]; x[37] = x[35] + x[37]; x[41] = x[39] + x[41]; x[45] = x[43] + x[45]; x[49] = x[47] + x[49]; x[53] = x[51] + x[53]; x[57] = x[55] + x[57]; x[61] = x[59] + x[61]; x[65] = x[63] + x[65]; x[69] = x[67] + x[69]; x[73] = x[71] + x[73]; x[77] = x[75] + x[77]; x[81] = x[79] + x[81]; x[85] = x[83] + x[85]; x[89] = x[87] + x[89]; x[93] = x[91] + x[93]; x[97] = x[95] + x[97]; x[101] = x[99] + x[101]; x[105] = x[103] + x[105]; x[109] = x[107] + x[109]; x[113] = x[111] + x[113]; x[117] = x[115] + x[117]; x[121] = x[119] + x[121]; x[125] = x[123] + x[125]; // down-level 14 x[2] = x[1] + x[2]; x[4] = x[3] + x[4]; x[6] = x[5] + x[6]; x[8] = x[7] + x[8]; x[10] = x[9] + x[10]; x[12] = x[11] + x[12]; x[14] = x[13] + x[14]; x[16] = x[15] + x[16]; x[18] = x[17] + x[18]; x[20] = x[19] + x[20]; x[22] = x[21] + x[22]; x[24] = x[23] + x[24]; x[26] = x[25] + x[26]; x[28] = x[27] + x[28]; x[30] = x[29] + x[30]; x[32] = x[31] + x[32]; x[34] = x[33] + x[34]; x[36] = x[35] + x[36]; x[38] = x[37] + x[38]; x[40] = x[39] + x[40]; x[42] = x[41] + x[42]; x[44] = x[43] + x[44]; x[46] = x[45] + x[46]; x[48] = x[47] + x[48]; x[50] = x[49] + x[50]; x[52] = x[51] + x[52]; x[54] = x[53] + x[54]; x[56] = x[55] + x[56]; x[58] = x[57] + x[58]; x[60] = x[59] + x[60]; x[62] = x[61] + x[62]; x[64] = x[63] + x[64]; x[66] = x[65] + x[66]; x[68] = x[67] + x[68]; x[70] = x[69] + x[70]; x[72] = x[71] + x[72]; x[74] = x[73] + x[74]; x[76] = x[75] + x[76]; x[78] = x[77] + x[78]; x[80] = x[79] + x[80]; x[82] = x[81] + x[82]; x[84] = x[83] + x[84]; x[86] = x[85] + x[86]; x[88] = x[87] + x[88]; x[90] = x[89] + x[90]; x[92] = x[91] + x[92]; x[94] = x[93] + x[94]; x[96] = x[95] + x[96]; x[98] = x[97] + x[98]; x[100] = x[99] + x[100]; x[102] = x[101] + x[102]; x[104] = x[103] + x[104]; x[106] = x[105] + x[106]; x[108] = x[107] + x[108]; x[110] = x[109] + x[110]; x[112] = x[111] + x[112]; x[114] = x[113] + x[114]; x[116] = x[115] + x[116]; x[118] = x[117] + x[118]; x[120] = x[119] + x[120]; x[122] = x[121] + x[122]; x[124] = x[123] + x[124]; x[126] = x[125] + x[126]; }