一种适用于反馈制两级交换结构的调度算法

摘要

本发明公开了一种适用于反馈制两级交换结构的调度算法，适用于FTSA结构中任意输入端口i依据算法自身规则选择满足条件VOQ2(j，r)为空的非空VOQ1(i，r)的队首信元，并将其转发至下一时槽与输入端口i相连的中间端口j。采用r＝i-2，i-3，…，0，N-1，N-2，…，i，i-1的顺序搜索第一个满足VOQ2(j，r)为空的非空VOQ1(i，r)并将其队首信元转发；包括建立映射、信息过滤和优先级位图算法调度等步骤，最后将调度结果反映射为子队列号。本发明使FTSA结构算法复杂度从O(N)降低为O(1)，提高了FTSA的高速交换能力和可扩展性。

主权项

一种适用于反馈制两级交换结构的调度算法，适用于反馈制两级交换结构，即FTSA结构中任意输入端口i依据算法自身规则选择满足条件VOQ2(j,r)为空的非空VOQ1(i,r)的队首信元，并将其转发至下一时槽与输入端口i相连的中间端口j；采用r=i‑2,i‑3,…,0,N‑1,N‑2,…,i,i‑1的顺序搜索第一个满足VOQ2(j,r)为空的非空VOQ1(i,r)并将其队首信元转发；包括以下步骤：1）首先将任意输入端口的N个子队列的缓存状态信息映射为优先级状态数据,建立如下映射：A：任意子队列VOQ1(i,r)映射为优先级为i‑r‑2的任务；B：VOQ1(i,r)由空状态转为非空状态映射为优先级为i‑r‑2的任务就绪；C：VOQ1(i,r)由非空转为空状态映射为优先级为i‑r‑2的任务执行完毕;2）在每个时槽之初利用反馈得到的中间缓存状态信息V过滤优先级就绪表OSRdyTbl而生成临时优先级就绪表TmpRdyTbl，随后根据TmpRdyTbl生成临时优先级就绪组TmpRdyGrp；3）依据2）生成的临时优先级就绪组TmpRdyGrp和临时优先级就绪表TmpRdyTbl，采用优先级位图算法进行调度，并将调度结果——最高优先级号反映射为子队列号。