With the recent advancements in LSI technology, Parallel processors, referred to as simple instruction stream multiple data(SIMD) stream machines, can now be made much cheaper and faster.
The use of microprocessors and LSI memory modules for the construction of parallel processors becomes very attractive.
In the parallel processors all processing elements execute the same instruction at the same time. Particularly, an instruction may process a set of data in different processors.
Parallel processors may be classified by the existence of interconnection network, which is of major importance to the system designers who must implement the system.
In this thesis, a shuffle-exchange network among processing element interconnection networks and its control scheme are described.
We indicate by a series of examples that the shuffle-exchange network is an important interconnection network for a parallel processor. The examples include the fast Fourier transform, polinomial evaluation, and sorting.
Among these algorithms, we are particularly, interested in sorting algorithms. The problem of sorting sequence of N elements on the proposed system with k processing elements is considered.
K is an optimal number of processing elements when sorting 2k elements using the shuffle-exchange network.
For larger N, the performance of the parallel sorting is improved significantly as the number of processing elements becomes larger.
The polinomial evaluation and the proposed sorting algorithm is actually implemented on the proposed system with the shuffle-exchange network.
The proposed system includes two microprocessors as the processing elements and is designed to be adaptive in these algorithms.
본 논문은 parallel processor 에 이용되는 여러 interconnection network 중 shuffle-exchange network의 긴요성을 sorting, FFT 와 polynomial evaluation 등의 예를 들어 설명했다.
특히, K 개의 processor 를 지닌 parallel computer에서 n개의 element를 sorting하는 문제가 고려됐다. 이 sorting의 성능을 좋게하기 위해 shuffle-exchange network으로 구성된 processing element array 외에 comparator module을 사용한 system에서 algorithm 이 작성됐으며, 이 system의 control scheme은 FFT나 polynomial evaluation 의 처리도 가능 하도록 설계했다.
parallel sorting의 성능은 SISD algorithm 에 비해 processor 의 수가 증가할수록 더욱 향상됨을 알수 있었다.
