(TCBF):CICQ中一种复杂度低的高效算法

摘要

随着芯片集成度快速提高,带有交叉缓存(crosspoint buffer)的cicq(Combined Input and Crossbar Queued switch)交换机引起了人们的广泛关注和研究兴趣.分析了cicq模型的性质后,提出了在cicq中瞬时加速比和有效加速比的概念,指出瞬时加速比也是一种资源.分析了输入队列和输出队列对cicq系统性能的影响,在此基础上提出了基于cicq的输入仲裁算法-TCBF(Thresh-hold Crosspoint Buffer First),并进行了仿真实验,针对非均匀业务模式(nonuniform)的情况作了改进.实验证明,这种时间复杂度为O(1)的算法有100%的吞吐率,有和OQ-N近似的输出延迟.并且非常易于硬件实现.最后讨论硬件实现办法.