(untitled) (International Journal of Engineering and Computer Science, 2014)
The OTIS (Optical Transpose Interconnection System) has become one of the popular models for developing parallel algorithms solving various computation and communication intensive problems. Various real life problems including job scheduling, knapsack, loop optimization, evaluation of polynomials, solutions of linear equations, and polynomial interpolation depend on the time complexity of prefix computation for the efficiency for their respective solutions. In this paper, we have proposed an algorithm for parallel prefix computation on OTIS-Hyper Hexa-cell. In this architecture, the time complexity of the algorithm for n2 data elements is O(n) electronic moves and O(n) OTIS moves.