Rearrangeability of multistage interconnection networks and improved bounds on explicit superconcentrator constructions /
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | Thesis Book |
| Language: | English |
| Published: |
1994.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy http://proxy.library.tamu.edu/login?url=http://proquest.umi.com/pqdweb?did=740896411&sid=1&Fmt=2&clientId=2945&RQT=309&VName=PQD |
| Abstract: | A model, banyan-banyan-1 multistage networks, is presented to describe the rearrangeability for every arbitrary permutation by providing a bit decomposition and composition algorithm. The proposed algorithm is not an iterative switching elements setting algorithm such as the looping algorithm. Although this algorithm has the same complexity as the looping algorithm of the Benes network, the calculations of inverse mappings are not required to be rearrangeable. Consequently, it seems to be simpler and easier to understand the rearrangeability of the networks. By applying these patterns to a multistage reverse shuffle/exchange network, we propose another routing permutation scheme on this network. Currently, the best upper bound for the rearrangeability of a shuffle/exchange network in nonsymmetric networks is 3 log N - 3 stages. We describe the rearrangeability of reverse shuffle/exchange multistage interconnection network on every arbitrary permutation with N <16. This rearrangeability can be established by setting two more stages in the middle stage of the network to allow the reduced network to be topologically equivalent to a class of rearrangeable networks. The better results enable us to establish an upper bound, 2 log TV+ 1 stages for rearrangeable reverse shuffle/exchange networks with N < 16, and leads to the possibility of this bound when N >16. For the new interconnection structures which realize optimal hardware complexity and which might be easier to route than the existing configurations, linear size expanders have been studied in many fields for practical use. This makes it possible to connect large numbers of device chips in parallel communication systems. Linear order concentrators can be used to construct theoretically optimal interconnection network schemes. Actually, the defined explicit constructions are based on expanders, which have large constant factors, thus rendering them impractical for reasonable sized networks. Therefore, this presents the need for an improvement of the expansion constant and the concentrator construction using expanders, which realizes the reduction of the size in a superconcentrator by the constant factor. As a result, we show an explicit construction with an (n, 5 ,1 -V 3 /2 ) expander. The superconcentrators with density, 196n, can be obtained. |
|---|---|
| Item Description: | Vita. "Major subject: Electrical Engineering." |
| Physical Description: | xi, 101 leaves : illustrations ; 28 cm |
| Bibliography: | Includes bibliographical references. |