An MIMD Algorithm for Finding Maximum and Minimum on OMTSE Architecture

Abstract

Optical Multi-Trees with Shuffle Exchange (OMTSE), recently proposed, is an efficient model of optoelectronic parallel computer. The OMTSE interconnection system consists of n2 factor networks called TSE networks, which are organized in the form of an n × n matrix. Each factor network has n number of leaf nodes. The network has a total of 3 n3/2 nodes. The diameter and bisection width of the network is 6log n-1 and n3/4 respectively. In this paper we present a synchronous MIMD algorithm to find the maximum and minimum of n (n-1)2 data elements on OMTSE with (4log n + 4) electronic moves and 3 optical moves.