A COST AND SPEED MODEL FOR K-ARY N-CUBE WORMHOLE ROUTERS

The evaluation of advanced routing features must be based on both of c osts and benefits. To date, adaptive routers have generally been evalu ated on the basis of the achieved network throughput (channel utilizat ion),ignoring the effects of implementation complexity. In this paper, we describe a parameterized cost model for router performance, charac terized by two numbers: router delay and flow control time. Grounding the cost model in a 0.8 micron gate array technology, we use it to com pare a number of proposed routing algorithms. From these design studie s, several insights into the implementation complexity of adaptive rou ters are clear. First, header update and selection is expensive in ada ptive routers, suggesting that absolute addressing should be reconside red. Second, virtual channels are expensive in terms of latency and cy cle time, so decisions to include them to support adaptivity or even v irtual lanes should not be taken lightly. Third, requirements of large r crossbars and more complex arbitration cause some increase in the co mplexity of adaptive routers, but the rate of increase is small. Last, the complexity of adaptive routers significantly increases their setu p delay and flow control cycle times, implying that claims of performa nce advantages in channel utilization and low load latency must be car efully balanced against losses in achievable implementation speed.