多队列架构中控制其相依顺序的方法与装置

摘要

本装置包含周期号码产生器、障碍位/障碍号码产生器、周期号码及障碍号码比较器。每个推入队列项目都有一个周期号码,如推入第一队列的项目和第二队列的项目有相依关系,则障碍位/障碍号码产生器设定第一队列推入项目的障碍位并产生障碍号码,当该项目要被推出执行时,上述比较器会比较该项目的号码及第二队列中每一个项目的周期号码,该项目会在第二队列中所有与该项目有相依关系的项目都被推出执行完毕后推出。

说明书

本发明涉及一种先进先出队列(FIFO queue)的设计。特别是，涉及多队列架构中之相依顺序控制。

在高度整合的系统中，存储器可被多个装置存取，并以多路的模式运作。因此，提升存储器数据存取频宽(bandwidth)，是增进系统效能并使系统符合延迟需求的重要方法。在存储器控制器设计中，已有一些装置被用来最佳化动态随机存取存储器(DRAM)的总线使用率。当存储器控制器接到存储器存取要求时，正确的存储器指令会根据目前同步动态随机存取存储器(SDRAM)的内部状态来产生。

存储器指令可分为预充电(pre-charge)/主动态(active)指令及读/写指令，并且这两种分类的指令会被分别置于相对应的预充电/主动态和读/写的队列中。通常读/写指令与数据传输有关，预充电/主动态指令则是读/写指令的预备动作。当队列中欲被取出的指令的执行条件都满足时，该指令会立刻被送上DRAM总线以便执行。

由于预充电/主动态指令与数据传输无关，所以当数据总线忙碌但指令总线有空时仍可被执行；也就是说预充电/主动态指令与读/写指令在执行的时序上可以重迭。因此预充电/主动态指令队列与读/写指令队列可同时被用以管线(pipeline)处理的方式来执行存储器指令，使总线达到最大的利用效能。然而，由于指令来自于两个不同的队列，因此有可能发生执行时序的差错，如果预充电/主动态指令过早被执行，则其后的读/写指令将无法得到正确的结果。

举例来说，某次存储器存取要求包含三个周期：周期一是可写到存储器A层(hit write on bank A)，周期二是可读存储器A层(hit readon bank A)，周期三是无法写到存储器A层(miss write on bank A)。当该要求产生时，读/写指令队列(简称前景队列FQ)及预充电/主动态指令队列(简称背景队列BQ)的状态如图3所示。其中周期三会译码成三个存储器指令：预充电(PRE)存储器A层，主动态(ACT)存储器A层及写入(WTT)存储器A层，并且预充电存储器A层及主动态存储器A层会被置于背景队列的第一层(level 1)，写入存储器A层会被置于前景队列的第三层(level 3)，在这种情形下，背景队列第一层的指令必须等到前景队列第二层的指令执行完才能被执行，否则，周期二的读取指令可能会因为背景队列第一层的指令而读到错误的存储器分页。

由以上的例子，如果两个队列间的相依顺序没有考虑在队列的设计中，预充电存储器A层及主动态存储器A层极有可能在前景队列的第一层指令执行完毕后就立刻被执行，这是因为前景队列第一层指令执行完后的状态符合预充电及主动态的执行条件。因此，在执行背景队列中的指令前，有必要作和前景队列间的相依顺序检查。

前面一直提到的队列，一般都是用先进先出(FIFO)的运作模式，如图1所示。也有同时使用两个队列的双队列的架构(2-way FIFO queue)，两个队列是同步但独立的运作，如图2所示。双队列架构较单个队列要有效率，但双队列间较难维持队列中项目的顺序。

本发明克服上述效能最佳化及多队列间相依顺序控制上的困难。其主要目的之一是，在双队列架构下，提供一种障碍控制方法在最大平行度(parallelism)下来控制队列间的相依顺序，使其效能达到最佳。本发明之障碍控制方法包含一个周期号码产生器、一个障碍位(barrierbit)/障碍号码产生器(barrier ID generator)及一个周期号码和障碍号码比较器。

周期号码产生器产生序号并给每个指令周期编号，障碍位/障碍号码产生器决定每一个置于第一队列的相依项目的障碍位及障碍号码，如果该项目和第二队列中的项目有相依的关系，则障碍位会设为1，同时障碍号码会依据相依顺序来产生。周期号码和障碍号码比较器会比较第一队列中即将被取出的项目的障碍号码，及第二队列中即将被取出的项目的周期号码，来决定第一队列中即将被取出的项目是否应该暂缓取出。

本发明之另一目的是，是提供一个障碍位/障碍号码的产生方法，使进来第一队列的项目根据其与第二队列中项目的相依顺序，得到一个障碍位及障碍号码，并且，如果两者间没有相依关系，则障碍位会设为0，障碍号码则不予理会；否则，障碍位将被设为1，障碍号码会被决定于两者相依的方式。

在本发明中，每个队列都有一个推入指针(PUSH pointer)，使得第二队列中有一个项目最靠近推入指针，并且该项目与最近进来第一队列的项目有相依关系。因此，本发明提出一个根据推入指针及两队列间的相依顺序来产生障碍号码的方法，且该方法可以组合逻辑电路来制作。

本发明之另一目的是，提供一个上到下决策树(top-down decisiontree)的周期号码和障碍号码比较器，该上到下决策树会由周期号码和障碍号码的高位比到低位。同时，为使两者比较的结果正确，本发明中的周期号码会较表示多队列最大容量的位数多一个位。根据周期号码和障碍号码的顺序，决策树会包含多个子叶节点(leaf node)及非子叶节点(non-leaf node)，非子叶节点代表比较的状态，子叶节点代表比较的结果。如果周期号码大于障碍号码，则子叶节点会显示真值，否则为假。因此，根据决策树的结果，周期号码和障碍号码比较器可决定第一队列中即将被取出的项目是否应该暂缓取出。

图1系典型先进先出之队列架构。

图2系双队列架构。

图3系关于存储器控制器中前景队列及背景队列运作的一个例子。

图4系本发明之障碍控制方法的架构。

图5系本发明之关于队列A推入(PUSH)/取出(POP)运作的流程图。

图6系本发明之障碍位及障碍号码的产生方法。

图7系比较周期号码及障碍号码的决策树。

图8系说明为何周期号码须较表示多队列最大容量的位数多一个位。

图9系周期号码及障碍号码的比较。

兹结合附图、实施例之详细说明及专利要求保护范围，将上述及本发明之其它目的与优点详述于后。

参照图4，本发明的障碍控制方法架构中包含一个周期号码产生器401、一个障碍位/障碍号码产生器402及一个周期号码和障碍号码比较器403，来控制队列A及队列B项目间的相依顺序。一个推入控制器411和一个取出控制器412用来控制队列A的运作；同样的，推入控制器421及取出控制器422用来控制队列B的运作。

假设队列A中的项目取出须依据该项目及队列B中项目的顺序，并且，队列B中的项目取出与队列A无关。于是，队列B的推入取出可同步进行且没有任何限制；队列A的推入取出也可同步进行，但队列A的取出可能会因和队列B间顺序的控制而被暂缓取出。

周期号码产生器401会产生顺序的周期号码给每一个推入队列A和队列B的项目。对一个即将被推入队列A的项目A，障碍位/障碍号码产生器402会检查项目A和队列B的每一个项目的相依关系，并产生项目A的障碍位及障碍号码。队列A的推入控制器411会将项目A、401所产生的周期号码及402产生的障碍位/障碍号码一并存入项目A中。

当项目A即将被取出时，队列A的取出控制器会检查项目A的障碍位，及项目A的障碍号码和队列B中即将被取出项目的周期号码的比较结果。如果周期号码大于障碍号码，则比较的结果为真，否则为假。

根据上述「周期号码大于障碍号码」，表示周期号码的产生较慢，即使实际上产生的号码不见得较大，这是因为周期号码会由零重新循环，这现象将讨论于后。项目A在其障碍位为1，且比较器403的结果为假时会被暂缓取出，这表示队列B中尚有一些项目须先被取出执行。图5系队列A推入及取出控制器的运作流程图。

上述的说明虽然假设队列B中的项目取出与队列A无关，但相同的障碍控制方法也可应用在相反的状况：队列B中的项目取出与队列A的项目有相依顺序。

为了控制队列A和队列B项目间的顺序，每个推入项目都需要一个周期号码，并与该项目及其它相关信息一并被推入队列中。周期号码被顺序的产生，也就是当一个周期号码产生后即自动加一，但若两个项目同时推入两个队列中，则这两个项目会得到相同的周期号码。在本发明的实施例中，周期号码产生器401可以是一个计数器，且该计数器的累计动作是由队列A及队列B推入动作的OR逻辑运算结果来控制。

当周期号码溢位时，周期号码会由零重新循环，因此周期号码计数器的位数须被谨慎选取。为确保队列中每个项目都有唯一的周期号码，周期号码的数量不可少于队列全部的容量。举例来说，如果队列全部的容量是8(即每个队列的容量为4)，则周期号码计数器必须至少有三个位。同时，由于周期号码会和障碍号码比较，因此障碍号码计数的范围须和周期号码一致。但为避免在比较时的模糊，周期号码须多一个位，以本例来说，即是四个位元。

如图8所示，三位元的周期号码计数器产生依序产生八个周期号码000到111，如图8左边的数列A，计数器到111后会重新由000循环一次，如图8左边的数列B。在这种情形下，当障碍编号是在数列B的000，周期编号是111，则周期号码和障碍号码比较器会无法决定周期编号和障碍编号的先后顺序：周期编号111可能是发生在数列B的000之前数列A的111，也可能同样是在数列B中但在000后面的111。为了解决这个问题，周期号码需要多一个位，如图8右边是四位元周期号码计数器产生的数列A1、数列B1、数列C1，新增加的位不一起计数，但在计数器重新循环时，该位会在0、1切换以标示不同的循环，如此一来，前述的问题便不再发生。

队列A中每个项目都需要障碍位及障碍号码来记录和队列B的相依关系。当障碍位是0，表示两者间没相依关系可以被同时取出执行；如果障碍位是1，则该项目须暂缓取出，直到被障碍号码标示的队列B中的相依项目被取出执行。

在一个项目被推入队列A前(为方便说明我们称此项目为A)，障碍位/障碍号码产生器402会检查队列B中所有有效的项目是否有须要在项目A之前被取出的相依关系。如果队列B中不存在这样的项目，则障碍位会设为0，障碍号码则不予理会；相反的，队列B中存在这样的项目(项目B)，则障碍位会设为1，障碍号码产生器会找出项目B的周期号码(如果存在多个项目B，则以其中最后被推入的项目和项目A有相依关系)，并将障碍号码设为项目B的周期号码。

图6系本发明之障碍位及障碍号码的产生方法。队列A及队列B是环状队列，因此队列的控制须有推入指针PUSHPTR及取出指针POPPTR指向队列的推入位置及取出位置，并且推入指针所指的项目为无效项目。如图6所示，队列B有有效项目w、y、z，在项目A被推入队列A前，项目A和项目w、y、z的相依关系会先被检查，并将结果用h_w、h_y、h_z表示。如果项目A和项目w有相依关系，则h_w会被设为1，否则设为0。如果h_w、h_y、h_z的值都是0，则障碍位会设为0，障碍号码则不予理会；否则，则障碍位会设为1，并根据以下说明的方法，找出最后被推入的相依项目。

在环状队列中，最后的有效项目就是其位置最靠近推入指针的项目，因此找最后有效且相依的项目的方法须根据推入指针的位置来推算，如图6下方表格的栏所示。在图6表格的第二列为选择项目w为最后有效且相依项目的所有可能条件，并以项目w的周期号码作为项目A的障碍号码(Select_w_cycle_ID)。在第二列第二栏，由于推入指针指到项目w(PUSHPTR＝w)，因此项目w无效也不会被选到；在第三栏中推入指针指到项目x(PUSHPTR＝x)，选择项目w的条件是h_w的值为1(h_w)；在第四栏中推入指针指到项目y(PUSHPTR＝y)，项目w不再是靠推入指针最近的项目(项目x最靠近推入指针)，选择项目w的条件是h_w的值为1且h_x的值为0(h_w^*！h_x)；最后一栏推入指针指到项目z(PUSHPTR＝z)，项目y最靠近推入指针，因此选择项目w的条件是h_w的值为1且h_x及h_y的值均为0(h_w^*！h_x^*！h_y)；同样的推论适用于图6表格的其它列。当项目A的障碍位及障碍号码决定后，会和项目A一并推入队列A中。为节省运算时间，障碍位/障碍号码产生器402一般都由一个组合逻辑电路来制作。

障碍位和障碍号码及周期号码比较的结果，足以决定是否暂缓队列的取出动作。如果障碍位是0，表示项目A与队列B中的项目没有相依关系，因此项目A可立即被取出执行；相反的，如果障碍位是1，并且障碍号码及周期号码比较的结果是真，表示队列B即将取出项目的周期号码大于(或晚于)项目A的障碍号码，也就是队列B中所有与项目A相依的项目都已被取出执行完毕，这时可立刻取出并执行项目A；否则项目A会一直被暂缓取出，直到障碍号码及周期号码比较的结果为真。

障碍号码及周期号码比较的算法是以决策树来执行，如图7所示，决策树的非子叶节点是比较的条件，子叶节点是各比较的结果。在这样的决策树中，如果周期号码大于(或晚于)障碍号码，则最后的结果是真，否则为假。

通常比较是由高位到低位逐位的相比，所以，决策树是以上到下的方式由根节点比到子叶节点。根节点的条件可产生两个分枝，如图7，根节点左子树表示障碍号码及周期号码最高位(即第三个位)相等，右子树表示障碍号码及周期号码最高位不相等。

如果两者最高位相等，也就是在根节点的左子树，表示两者的号码都在如图9的序列一、或都在序列二、或都在序列三。因此，如果周期号码第二个位是1并且障碍号码第二个位是0，则周期号码是落在图9某一个序列的后四个数字(后三位：111，110，101，100)；障碍号码是落在图9某一个序列的前四个数字(后三位：000，001，010，011)。以这样的方式便能决定周期号码和障碍号码的先后顺序；如果两者的第二位相等，则决策树必须以相同的方法往后面的位继续比较，直到可以决定两者的先后顺序为止。

如果两者最高位不相等，也就是在根节点的右子树，则两者的号码必分别落在位三不同的两个序列中。如果周期号码第二位是0并且障碍号码第二个位是1，则周期号码是落在图9序列a或序列b的后四个数字(后三位：000，001，010，011)；障碍号码是落在图9序列a或序列b的前四个数字(后三位：100，101，110，111)。由这样的结果便能决定周期号码在障碍号码的顺序之后；如果两者的第二位元相等，则决策树必须以相同的方法往后面的位继续比较，直到可以决定两者的先后顺序为止。

本发明的障碍控制方法可被用在存储器控制器中，或其它应用中，例如，外围控制接口(FCI)和处理单元接口间的管道是一个双队列架构，其中一个队列处理写入的周期，另一个队列处理读取的周期，双队列间相依顺序的控制便可用本发明的障碍控制方法。

前述障碍控制方法是架构在双队列架构，然而，本发明的方法具有扩充性，也就是可以很容易的移植到多队列架构上。本发明的障碍控制方法提供一个控制及维护多队列间相依顺序的实用方法。

以上所述仅为本发明之较佳实施例而已，当不能以此限定本发明实

以上所述仅为本发明之较佳实施例而已，当不能以此限定本发明实施之范围。大凡依本发明申请专利范围所做之等效变化与修饰，皆应属本发明专利涵盖之范围内。