Improved Parallel Prefix Algorithm on OTIS-Mesh of Trees

Abstract—A parallel algorithm for prefix computation reported recently on interconnection network called OTIS-Mesh Of Trees[4]. Using n4 processors, algorithm shown to run in 13log n + O(1) electronic moves and 2 optical moves for n4 data points. In this paper we present new and improved parallel algorithm for prefix on OTIS-Mesh of Trees. The algorithm requires 10log n + O(1) electronic steps + 1 optical step for prefix computation on the same number of processors and data points as considered in [4]. Index Terms—Prefix computation, parallel algorithm, time complexity