Conventional reconfigurable components have substantially more interconnect configuration bits than they strictly need. Using counting arguments we can establish loose bounds on the number of programmable bits actually required to describe an interconnect. We apply these bounds in crude form to some existing devices, demonstrating the large redundancy in their programmable bit streams. In this process we review and demonstrate basic counting techniques for identifying the information required to specify an interconnect. We examine several common interconnect building blocks and look at how efficiently they use the information present in their programming bits. We also discuss the impact of this redundancy on important device aspects such as area, routing, and reconfiguration time.
N.B. There is at least one claim in this paper which I no longer believe is accurate---or rather can be quite misleading. Table 1, suggests crosspoints and switches should grow as O(n2). But, we know a Benes network can connect any permutation with O(n log n) switches. See my SLIP'01 paper on Rent's Rule based switching requirements for a more sophisticated treatment of switching requirements.
Paper
Extended Version of Paper:
Slides: