一种调度器的分级轮询方法
专利名称：一种调度器的分级轮询方法
技术领域：
本发明涉及通信领域中轮询调度器，尤其涉及的是轮询调度器的一种分级实现方法。
背景技术：
现有技术中的轮询是调度算法中最为普通的一种，如何实现对多申请(Request，以下简写为Req)快速轮询，从而调度出一个输出，是轮询算法的关键。
假设在硬件实现中每个时钟最多能轮询16个Req，对于1K个Req，如采用串行轮询调度器最多需要64个时钟才能选出1个。串行轮询调度器逻辑简单，耗费硬件资源少，但其缺点也是显而易见的，就是耗费时间过长。
为了克服串行轮询调度器所需时间过长的缺点，系统可采用多个轮询调度器进行并行轮询，如采用64个轮询调度器，每个轮询调度器模块轮询16个Req，则在1个周期内，可得到64个候选Req，然后再通过1个高层轮询调度器得到1个输出结果，如此耗费时间大大缩短，但并行轮询调度器硬件资源多。
实现轮询的方法很多，串行轮询调度器与并行轮询调度器是两个极端的情况，它们的优劣势非常明显，因此，现有技术都存有缺陷，而有待于改进和发展。
发明内容
本发明的目的在于提供一种调度器的分级轮询方法，是一种新的分级轮询调度器，综合串行轮询调度器与并行轮询调度器的优点，所耗资源不多，耗费时间也不长。
本发明的技术方案如下一种调度器的分级轮询方法，其采用分级轮询调度器，当有N个请求，每个周期最多轮询M个请求，该方法包括以下步骤步骤1将这N个请求以M个申请为一组，共N/M组，每组共用1个信号组成上一级申请信号；步骤2在上一级申请信号中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号组成高一级申请；步骤3在高一级申请信号中，对这(N/M)/M个申请信号再通过上述分级方式组织，每组共用1个信号组成更高一级申请；步骤4按照步骤1和步骤2方法继续，直至能够在1个周期内调度本级的申请信号；其中，N和M为表示请求和分组数目的自然数。
所述的方法，其中，所述分级轮询方法从最高一级的调度器开始轮询，根据上次轮询的现场值，选择信号为真的一组，依次采用下一级的调度器向下一分级进行轮询。
本发明所提供的一种调度器的分级轮询方法，由于采用由上至下的方式分级轮询，轮询时间固定，效率高，所耗硬件资源也不多，所需时间不长，所需资源也不多，因此适用于申请数多，调度时延要求高的场合。
图1是本发明方法一具体实施例的三级调度流程图；图2是本发明方法的4K条申请信号调度系统硬件实现图。
具体实施例方式
以下将对本发明的具体实施方式
加以详细说明
本发明所述的调度器的分级轮询方法采用了分级轮询调度器，分级轮询调度器的思想在于将轮询范围逐渐求精，当有N个Req，每个周期最多轮询M个Req，用以下方式进行申请信号组织1)将这N个Req以M个申请为一组，共N/M组，每组共用1个信号组成上一级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有N/M个申请信号；2)在上一级申请信号中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号组成高一级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有(N/M)/M个申请信号；3)假设申请信号通过第1、2步的方式组织后，到本级后，调度器已经能够在1个时钟内，对(N/M)/M个申请信号进行轮询；假设通过以上方式，最终有3级申请信号，则对于N个Req，分级轮询调度器通过以下方式进行调度1.第一级轮询该级申请信号共(N/M)/M个。分级轮询调度器首先轮询输入的M个信号，并根据上次轮询的现场值，发现其中1个信号为真，这表示该申请信号所代表的下面M个申请有大于等于1个为真。
2.第二级轮询该级申请信号共N/M个。分级轮询调度器再轮询下面的M个Req，并根据上次轮询的现场值，发现其中1个信号为真，这表示该申请信号所代表的下面M个申请有大于等于1个为真；3.第三级轮询该级申请信号共N个。分级轮询调度器在轮询下面的M个申请，并根据上次轮询的现场值，最终发现其中1个Req为真，该信号为真实的申请信号。
以上的三级调度流程如图1所示以下为本发明的另一具体实施例的说明如有4K个Req，设每个周期最多能轮询16个Req，如果时钟频率较低，则每个周期可轮询更多的Req，如32个或64个Req，这样使申请信号级别减少，使调度器的轮询效率得到提高。
用以下方式进行申请信号组织1)将这4K个Req以16个申请为一组，共256组，每组共用一个信号组成高一级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有256个申请信号；2)在高一级申请信号中，将这256申请信号又以16个为一组，共16组，每组共用一个信号组成最高级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有16个申请信号；3)对最高级的16个申请信号进行轮询调度。
根据各级的申请信号，对于4K个Req，分级轮询调度器通过以下方式进行调度1)第一级轮询该级申请信号共16个。分级轮询调度器首先轮询输入的16个申请信号，并根据上次轮询的现场值，发现其中一个信号为真，这表示该申请信号所代表的下面16个申请有超过一个为真。
2)第二级轮询该级申请信号共256个。分级轮询调度器再轮询下面的16个申请，并根据上次轮询的现场值，发现其中一个信号为真，这表示该申请信号所代表的下面16个申请有超过一个为真；3)第三级轮询该级申请信号共4K个。分级轮询调度器在轮询下面的16个申请，并根据上次轮询的现场值，发现其中一个信号为真，该信号为真实的申请信号。
有4K个申请信号，初始情况为所有申请都为假，以低电平表示，这时有第287个申请信号为真(高电平表示)，其余申请信号为假。这时有以下表的三级申请信号表示。
表1 三级申请信号表 在表1中，没有括号的数据表示申请信号，有括号的数据表示当前的调度现场值。
第三级申请信号中，第18个数据为0x0002表示第287个申请信号为真，下次开始调度的现场值为0xF表示下次第三级调度开始的位置，当下次调度超过0xF时，现场值又从0x0开始。
第二级申请信号中，第2个数据为0x4000表示第18个申请信号为真，下次开始调度的现场值为0x2表示下次第二级调度开始的位置，当下次调度超过0xF时，现场值又从0x0开始。
第一级申请信号中，数据为0x4000表示第2个申请信号为真，下次开始调度的现场值为0x2表示下次第一级调度开始的位置，当下次调度超过0xF时，现场值又从0x0开始。
分级轮询调度器的工作步骤如下1)分级轮询调度器首先调度第一级申请信号，发现数据为0x4000，表示需要进一步轮询第二级申请信号中的第17到第32个数据，即第三级申请信号(实际申请信号)的第256个到第511个申请，此时将第一级调度现场值设为0x2，表示下次对该块数据的轮询从第3个申请信号开始。
2)分级轮询调度器进一步轮询第二级申请信号的第17到第32个数据，发现数据为0x4000，表示需要进一步轮询第三级申请信号(实际申请信号)的第272个到第288个数据，可以看出，这比第1步骤中将第三级申请信号(实际申请信号)的第256个到第511个申请的定位更加准确了。此时将第二级调度现场值设为0x2，表示对该数据下次轮询从第3个申请信号开始。
3)分级轮询调度器进一步轮询第三级申请信号的第272到第288个数据，发现数据为0x0002，表示第287个申请信号有效，此时将第三级调度现场值设为0xF，表示对该数据下次轮询从第16个申请信号开始。
如图2为4K条申请信号调度系统硬件实现图。图2中，“刷新申请信号模块”负责对第三级RAM(存储4K个第三级申请信号)、第二级RAM(存储256个第二级申请信号)、第一级REG(存储16个第一级申请信号)进行刷新。其中，第三级RAM和第二级RAM由双口RAM构成，第一级REG由寄存器构成。
相对应的，图2中的“三级调度模块”读取各级RAM和REG中的信号，通过分级轮询方式，实现对4K个申请信号的实时调度。
分级轮询调度器通过以上逐步求精的方法，在3个时钟周期(不包括从RAM中读取申请信号所需周期)就在4K个申请中得到了调度输出，所耗资源较并行轮询方法大大减少，以上的分级轮询调度器采用由上至下的方式，轮询时间固定，效率高，所耗硬件资源也不多。同理，该调度器可在4个时钟内对64K个申请进行调度，以此类推。
应当理解的是，本发明方法的上述实施例描述比较具体，并不能因此而理解为对本发明方法的专利保护范围的限制，其专利保护范围应以所附权利要求为准。
权利要求
1.一种调度器的分级轮询方法，其采用分级轮询调度器，当有N个请求，每个周期最多轮询M个请求，该方法包括以下步骤步骤1将这N个请求以M个申请为一组，共N/M组，每组共用1个信号组成上一级申请信号；步骤2在上一级申请信号中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号组成高一级申请；步骤3在高一级申请信号中，对这(N/M)/M个申请信号再通过上述分级方式组织，每组共用1个信号组成更高一级申请；步骤4按照步骤1和步骤2方法继续，直至能够在1个周期内调度本级的申请信号；其中，N和M为表示请求和分组数目的自然数。
2.根据权利要求1所述的方法，其特征在于，所述分级轮询方法从最高一级的调度器开始轮询，根据上次轮询的现场值，选择信号为真的一组，依次采用下一级的调度器向下一分级进行轮询。
全文摘要
本发明的一种调度器的分级轮询方法，其采用分级轮询调度器，当有N个请求，每个周期最多轮询M个请求，用以下方式进行申请信号组织将这N个请求以M个申请为一组，共N/M组，每组共用1个信号向高一级调度器申请；在高一级的调度器中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号向更高一级调度器申请；在更高一级调度器中，对这(N/M)/M个申请信号再通过上述分级方式组织，直至能够在1个周期内调度本级的申请信号。本发明方法由于采用由上至下的方式分级轮询，轮询时间固定，效率高，所耗硬件资源也不多，所需时间不长，所需资源也不多，因此适用于申请数多，调度时延要求高的场合。
文档编号H04L12/403GK1767489SQ20041005193
公开日2006年5月3日 申请日期2004年10月26日 优先权日2004年10月26日
发明者童进 申请人:中兴通讯股份有限公司
技术领域：
本发明涉及通信领域中轮询调度器，尤其涉及的是轮询调度器的一种分级实现方法。
背景技术：
现有技术中的轮询是调度算法中最为普通的一种，如何实现对多申请(Request，以下简写为Req)快速轮询，从而调度出一个输出，是轮询算法的关键。
假设在硬件实现中每个时钟最多能轮询16个Req，对于1K个Req，如采用串行轮询调度器最多需要64个时钟才能选出1个。串行轮询调度器逻辑简单，耗费硬件资源少，但其缺点也是显而易见的，就是耗费时间过长。
为了克服串行轮询调度器所需时间过长的缺点，系统可采用多个轮询调度器进行并行轮询，如采用64个轮询调度器，每个轮询调度器模块轮询16个Req，则在1个周期内，可得到64个候选Req，然后再通过1个高层轮询调度器得到1个输出结果，如此耗费时间大大缩短，但并行轮询调度器硬件资源多。
实现轮询的方法很多，串行轮询调度器与并行轮询调度器是两个极端的情况，它们的优劣势非常明显，因此，现有技术都存有缺陷，而有待于改进和发展。
发明内容
本发明的目的在于提供一种调度器的分级轮询方法，是一种新的分级轮询调度器，综合串行轮询调度器与并行轮询调度器的优点，所耗资源不多，耗费时间也不长。
本发明的技术方案如下一种调度器的分级轮询方法，其采用分级轮询调度器，当有N个请求，每个周期最多轮询M个请求，该方法包括以下步骤步骤1将这N个请求以M个申请为一组，共N/M组，每组共用1个信号组成上一级申请信号；步骤2在上一级申请信号中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号组成高一级申请；步骤3在高一级申请信号中，对这(N/M)/M个申请信号再通过上述分级方式组织，每组共用1个信号组成更高一级申请；步骤4按照步骤1和步骤2方法继续，直至能够在1个周期内调度本级的申请信号；其中，N和M为表示请求和分组数目的自然数。
所述的方法，其中，所述分级轮询方法从最高一级的调度器开始轮询，根据上次轮询的现场值，选择信号为真的一组，依次采用下一级的调度器向下一分级进行轮询。
本发明所提供的一种调度器的分级轮询方法，由于采用由上至下的方式分级轮询，轮询时间固定，效率高，所耗硬件资源也不多，所需时间不长，所需资源也不多，因此适用于申请数多，调度时延要求高的场合。
图1是本发明方法一具体实施例的三级调度流程图；图2是本发明方法的4K条申请信号调度系统硬件实现图。
具体实施例方式
以下将对本发明的具体实施方式
加以详细说明
本发明所述的调度器的分级轮询方法采用了分级轮询调度器，分级轮询调度器的思想在于将轮询范围逐渐求精，当有N个Req，每个周期最多轮询M个Req，用以下方式进行申请信号组织1)将这N个Req以M个申请为一组，共N/M组，每组共用1个信号组成上一级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有N/M个申请信号；2)在上一级申请信号中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号组成高一级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有(N/M)/M个申请信号；3)假设申请信号通过第1、2步的方式组织后，到本级后，调度器已经能够在1个时钟内，对(N/M)/M个申请信号进行轮询；假设通过以上方式，最终有3级申请信号，则对于N个Req，分级轮询调度器通过以下方式进行调度1.第一级轮询该级申请信号共(N/M)/M个。分级轮询调度器首先轮询输入的M个信号，并根据上次轮询的现场值，发现其中1个信号为真，这表示该申请信号所代表的下面M个申请有大于等于1个为真。
2.第二级轮询该级申请信号共N/M个。分级轮询调度器再轮询下面的M个Req，并根据上次轮询的现场值，发现其中1个信号为真，这表示该申请信号所代表的下面M个申请有大于等于1个为真；3.第三级轮询该级申请信号共N个。分级轮询调度器在轮询下面的M个申请，并根据上次轮询的现场值，最终发现其中1个Req为真，该信号为真实的申请信号。
以上的三级调度流程如图1所示以下为本发明的另一具体实施例的说明如有4K个Req，设每个周期最多能轮询16个Req，如果时钟频率较低，则每个周期可轮询更多的Req，如32个或64个Req，这样使申请信号级别减少，使调度器的轮询效率得到提高。
用以下方式进行申请信号组织1)将这4K个Req以16个申请为一组，共256组，每组共用一个信号组成高一级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有256个申请信号；2)在高一级申请信号中，将这256申请信号又以16个为一组，共16组，每组共用一个信号组成最高级申请信号，该信号为一组中申请信号的或运算(申请信号为高电平有效时)，共有16个申请信号；3)对最高级的16个申请信号进行轮询调度。
根据各级的申请信号，对于4K个Req，分级轮询调度器通过以下方式进行调度1)第一级轮询该级申请信号共16个。分级轮询调度器首先轮询输入的16个申请信号，并根据上次轮询的现场值，发现其中一个信号为真，这表示该申请信号所代表的下面16个申请有超过一个为真。
2)第二级轮询该级申请信号共256个。分级轮询调度器再轮询下面的16个申请，并根据上次轮询的现场值，发现其中一个信号为真，这表示该申请信号所代表的下面16个申请有超过一个为真；3)第三级轮询该级申请信号共4K个。分级轮询调度器在轮询下面的16个申请，并根据上次轮询的现场值，发现其中一个信号为真，该信号为真实的申请信号。
有4K个申请信号，初始情况为所有申请都为假，以低电平表示，这时有第287个申请信号为真(高电平表示)，其余申请信号为假。这时有以下表的三级申请信号表示。
表1 三级申请信号表 在表1中，没有括号的数据表示申请信号，有括号的数据表示当前的调度现场值。
第三级申请信号中，第18个数据为0x0002表示第287个申请信号为真，下次开始调度的现场值为0xF表示下次第三级调度开始的位置，当下次调度超过0xF时，现场值又从0x0开始。
第二级申请信号中，第2个数据为0x4000表示第18个申请信号为真，下次开始调度的现场值为0x2表示下次第二级调度开始的位置，当下次调度超过0xF时，现场值又从0x0开始。
第一级申请信号中，数据为0x4000表示第2个申请信号为真，下次开始调度的现场值为0x2表示下次第一级调度开始的位置，当下次调度超过0xF时，现场值又从0x0开始。
分级轮询调度器的工作步骤如下1)分级轮询调度器首先调度第一级申请信号，发现数据为0x4000，表示需要进一步轮询第二级申请信号中的第17到第32个数据，即第三级申请信号(实际申请信号)的第256个到第511个申请，此时将第一级调度现场值设为0x2，表示下次对该块数据的轮询从第3个申请信号开始。
2)分级轮询调度器进一步轮询第二级申请信号的第17到第32个数据，发现数据为0x4000，表示需要进一步轮询第三级申请信号(实际申请信号)的第272个到第288个数据，可以看出，这比第1步骤中将第三级申请信号(实际申请信号)的第256个到第511个申请的定位更加准确了。此时将第二级调度现场值设为0x2，表示对该数据下次轮询从第3个申请信号开始。
3)分级轮询调度器进一步轮询第三级申请信号的第272到第288个数据，发现数据为0x0002，表示第287个申请信号有效，此时将第三级调度现场值设为0xF，表示对该数据下次轮询从第16个申请信号开始。
如图2为4K条申请信号调度系统硬件实现图。图2中，“刷新申请信号模块”负责对第三级RAM(存储4K个第三级申请信号)、第二级RAM(存储256个第二级申请信号)、第一级REG(存储16个第一级申请信号)进行刷新。其中，第三级RAM和第二级RAM由双口RAM构成，第一级REG由寄存器构成。
相对应的，图2中的“三级调度模块”读取各级RAM和REG中的信号，通过分级轮询方式，实现对4K个申请信号的实时调度。
分级轮询调度器通过以上逐步求精的方法，在3个时钟周期(不包括从RAM中读取申请信号所需周期)就在4K个申请中得到了调度输出，所耗资源较并行轮询方法大大减少，以上的分级轮询调度器采用由上至下的方式，轮询时间固定，效率高，所耗硬件资源也不多。同理，该调度器可在4个时钟内对64K个申请进行调度，以此类推。
应当理解的是，本发明方法的上述实施例描述比较具体，并不能因此而理解为对本发明方法的专利保护范围的限制，其专利保护范围应以所附权利要求为准。
权利要求
1.一种调度器的分级轮询方法，其采用分级轮询调度器，当有N个请求，每个周期最多轮询M个请求，该方法包括以下步骤步骤1将这N个请求以M个申请为一组，共N/M组，每组共用1个信号组成上一级申请信号；步骤2在上一级申请信号中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号组成高一级申请；步骤3在高一级申请信号中，对这(N/M)/M个申请信号再通过上述分级方式组织，每组共用1个信号组成更高一级申请；步骤4按照步骤1和步骤2方法继续，直至能够在1个周期内调度本级的申请信号；其中，N和M为表示请求和分组数目的自然数。
2.根据权利要求1所述的方法，其特征在于，所述分级轮询方法从最高一级的调度器开始轮询，根据上次轮询的现场值，选择信号为真的一组，依次采用下一级的调度器向下一分级进行轮询。
全文摘要
本发明的一种调度器的分级轮询方法，其采用分级轮询调度器，当有N个请求，每个周期最多轮询M个请求，用以下方式进行申请信号组织将这N个请求以M个申请为一组，共N/M组，每组共用1个信号向高一级调度器申请；在高一级的调度器中，将这N/M申请信号又以M个信号为一组，共(N/M)/M组，每组共用1个信号向更高一级调度器申请；在更高一级调度器中，对这(N/M)/M个申请信号再通过上述分级方式组织，直至能够在1个周期内调度本级的申请信号。本发明方法由于采用由上至下的方式分级轮询，轮询时间固定，效率高，所耗硬件资源也不多，所需时间不长，所需资源也不多，因此适用于申请数多，调度时延要求高的场合。
文档编号H04L12/403GK1767489SQ20041005193
公开日2006年5月3日 申请日期2004年10月26日 优先权日2004年10月26日
发明者童进 申请人:中兴通讯股份有限公司
最新回复(0)