Speaker: Rajgopal Kannan

Title: The KR-Benes Network: The (almost) Ultimately (control) Optimal Rearrangeable Permutation Network

Date and Time: Friday, September 19th., 2:30 PM
Place: 245 Coates

Abstract:

We have recently derived a major new result on optimally rearrangeable permutation networks. The Benes networks is one of the best known rearrangeable networks and has been unchanged over the last 30 years. We show in the following paper that it is possible to derive a control optimal rearrangeable network whose worst case control complexity is bounded by the Benes. The control and hardware complexity of this new network (called KR-Benes) is one stage more than provably optimal ( and substantially better than the Benes in most cases). We also present a strong conjecture that the KR-Benes is indeed optimal.