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

Low Complexity and High Efficient Algorithm in CICQ

作　　者：周功业[1] 李成俊[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《小型微型计算机系统》2007年第6期1144-1148,共5页Journal of Chinese Computer Systems

基　　金：国家"九七三"项目(2004CB318200)资助.

摘　　要：随着芯片集成度快速提高,带有交叉缓存(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近似的输出延迟.并且非常易于硬件实现.最后讨论硬件实现办法.With continued increase in density of chip,switch with crosspoint buffer have been widly researched （cicq ：Combined Input and Crossbar Queued switch）. Based on analysis of the nature of cicq modle,propose a new conception-instant speedup and effective speedup,then point out that instant speedup is a resource in cicq modle. Also analyse the affection of input queue and ouput queue on performance of system. Based on this anlysis,propose an input arbitration algorithm-TCBF （Thresh-hold Crosspoint Buffer First）,get simulation result,and made a improvement for nonuniform patten. Simulation result shows that this algorithm with O（1） complexity can have 100% thoughput,have similar performance with OQ-N,and it＇s also very easy to implement.

关 键 词：CICQ 加速比 瞬时加速比 有效加速比 虚拟输出队列 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]