병렬 상호 연결망을 위한 초집중기의 구성 = An Explicit Superconcentrator Construction for Parallel Interconnection Network

다국어 초록 (Multilingual Abstract)

Linear size expanders have been studied in many fields for the practical use, which make it possible to connect large numbers of device chips in both parallel communication systems and parallel computers. One major limitation on the efficiency of parallel computer designs has been the highly cost of parallel communication between processors and memories. Linear order concentrators can be used to construct theoretically optimal interconnection network schemes. Exiting explicitly defined constructions are based on expanders, which have large constant factors, thereby rendering them impractical for reasonable sized networks. For these objectives, we use the more detailed matching points in permutation functions, to find out the bigger expansion constant from an equation, Rx>=1 d(1-X/n)X. This paper presents an improvement of expansion constant on construction concentrators using expanders, which realizes the reduction of the size in a superconcentrator by a constant factor. As a result, this paper shows an explicit construction of (n,5,1-(root3)/2) expander. Thus, superconcentrators with 209n edges can be obtained by applying to the expanders of Gabber and Galil's construction.