Home Author Index Search Volume 1 May 2009 ISSN 1797-9617

International Journal of

Recent Trends in Engineering

Home > Vol. 1, No. 1

 

International Journal of Recent Trends in Engineering (IJRTE)

ISSN 1797-9617

Volume 1, Number 1, May 2009

Issue on Computer Science

Page(s): 560-562

Parallel Algorithm for Prefix Computation on OTIS k-Ary 3-Cube Parallel Computers

Keny T. Lucas

Full text: PDF

Abstract

The OTIS (Optical Transpose Interconnection System) has been a popular interconnection model for developing parallel processing systems. 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 of their respective solutions. In this paper we have proposed parallel algorithm for prefix computation on SIMD model of OTIS k-ary 3-cube. The prefix computation for N(=k6) data elements requires O(k) electronic moves and O(1) OTIS move on k6 processors.

Index Terms

interconnection network, OTIS, parallel algorithm, prefix computation, time complexity

Published by Academy Publisher in cooperation with the ACEEE

@ Copyright 2009 ACADEMY PUBLISHER All rights reserved