Models for synchronized parallel computation are described, in which processors are interconnected by networks. These models are used to solve the problem of finding the maximum value, the minimum value, or both values in parallel. The proposed algorithm is based on the binary tree routing scheme. The time complexities are investigated by taking account of the communication overhead. The optimal number of processors for a fixed number of data is analytically obtained. This number depends significantly on the types of interconnection networks. Results are presented for linear, mesh, three-dimensional, and cube-connected arrays. Execution times are investigated and are measured using a cluster multiprocessor system.>

We can perform a N-point FFT with time performance T=Ο(log N) and area-time performance AT 2 =Ο(N log 4 N), by using the 3-dimensional VLSI system which is optically interconnected. This performance exceeds the theoretical lower bound of the area-time performance (N 2 log 2 N) of the conventional VLSI.

The Top-Of-Stack(TOS) register is a high-speed storage which hold the top portion of the frequently used stack entries.We propose a Cut-Back-K algorithm, a sophisticated algorithm for TOS register management, to speed up the stack operation.The performance of this algorithm is analyzed with random-walk model.The effective stack access time with this algorithm can be as fast as the inherent access time of the TOS register in appropriate configurations.The inherent access time of TOSregister formed by on-chip shift register is proportional to O(1)~O(log N) for N cells.On the other hand, N elements arrav of dual-ports register takes O(N 27k) minimum access delay (k:some constant) .