Improved bounds on linear size expander

Author

Park, B.

Author_Institution

Dept. of Electr. Eng., Texas A&M Univ., College Station, TX, USA

fYear

1994

fDate

2-6 May 1994

Firstpage

96

Lastpage

101

Abstract

Linear size expanders have been studied in many fields for their practical use, which is the possibility to connect large numbers of device chips in parallel communication systems. One of the critical points in parallel computer designs has been very high cost of communication between processors and memories. Currently, linear size expanders can be used to construct theoretically optimal interconnection networks with reducing large constant factors. This paper presents an improvement on constructing concentrators using an (n, k, 2rs)/(r²-s²) expander, which realizes the reduction of the size in a superconcentrator by a constant factor

Keywords

multiprocessor interconnection networks; parallel architectures; linear size expander; optimal interconnection networks; parallel communication systems; parallel computer designs; superconcentrator; Computer architecture; Concurrent computing; Costs; Graph theory; Memory architecture; Microprocessors; Multiprocessor interconnection networks; Network topology; Protocols; Routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on

Conference_Location

Ischia

Print_ISBN

0-8186-6322-7

Type

conf

DOI

10.1109/MPCS.1994.367088

Filename

367088