存取仲裁装置和可仲裁条件验证装置转让专利
申请号 : CN200680003680.6
文献号 : CN100593777C
文献日 : 2010-03-10
发明人 : 渡部彰启 , 森重孝行 , 相原祐一郎
申请人 : 松下电器产业株式会社
摘要 :
存取优先级越高值越小的优先级控制值，在进行存取请求时，随着时间的经过而逐个请求者地进行减少。当存取结束时，增加优先级下降值(PERIOD)。并且，当没有存取请求时，优先级控制值下降到基准优先值(TMIN)之后，被维持在基准优先值。在进行请求的请求者中，对上述优先级控制值最小的请求者，许可进行存取。因此，能够以简洁的硬件结构高速地进行适当的仲裁。
权利要求 :
1.一种存取仲裁装置，用于仲裁多个请求者对存取对象的存取 请求，其特征在于，包括：
优先级保持机构，用于保持对于各请求者的存取许可的优先级；
优先级控制机构，用于控制上述优先级保持机构所保持的优先 级；以及存取许可机构，用于对上述优先级保持机构所保持的优先级最高 的请求者给予存取许可，其中，上述优先级控制机构的构成为：当有来自请求者的存取请求时、 和没有存取请求且优先级低于预定的基准优先级时，按照经过的时间 来使优先级上升预定的上升程度；而当存取已被许可时，使优先级降 低预定的降低程度。
2.根据权利要求1所述的存取仲裁装置，其特征在于：上述优先级的上升程度和降低程度按每个请求者而被设定。
3.根据权利要求1所述的存取仲裁装置，其特征在于：在请求者所请求的存取完成时进行上述优先级的降低。
4.根据权利要求1所述的存取仲裁装置，其特征在于：上述存取许可机构对由上述优先级的降低而导致优先级低于预 定的停止许可优先级的请求者不给予存取许可。
5.根据权利要求1所述的存取仲裁装置，其特征在于：上述优先级控制机构还在所有请求者的优先级都低于上述基准 优先级的情况下，将至少一部分的预定请求者的优先级设定为基准优 先级。
6.根据权利要求1所述的存取仲裁装置，其特征在于：上述优先级控制机构还在没有来自所有的请求者的存取请求的 情况下，将至少一部分的预定请求者的优先级设定为上述基准优先 级。
7.根据权利要求1所述的存取仲裁装置，其特征在于：上述优先级控制机构还在只有来自1个请求者的存取请求的情况 下，将没有存取请求的其他请求者中的至少一部分的预定请求者的优 先级设定为上述基准优先级。
8.根据权利要求1所述的存取仲裁装置，其特征在于：上述优先级控制机构还在直到上述优先级达到预定的极限优先 级为止未对任何请求者给予存取许可的情况下，输出出错信号。
说明书 :
技术领域
本发明涉及用于存储接口(memory interface)、任务(task)控 制等的存取仲裁装置(arbiter：判优器)。
背景技术
在系统LSI(Large Scale Integrated circuit：大规模集成电路)正 在被广泛使用的今天，经常会在1个芯片内集成具有以前多个芯片的 功能的多个功能模块。在这种情况下，为了谋求降低成本(cost down) 往往会合并外部存储器。即如以前那样当使用多个芯片的LSI时，多 数情况下也设置有多个存储器，该多个存储器分别被各LSI占用，但 在系统LSI中，绝大多数情况是多个功能模块共用1个存储器。因此， 为了仲裁来自多个功能模块的相互竞争的存取，而使用存取仲裁装 置。
存取仲裁装置的性能，如数字AV(audio visual)家电中的AV 处理模块那样，在要求实时(real time)性高的处理的情况下尤为重 要。对于这种要求高实时性的处理，例如已知使用能保证最低要求的 存取时间(worst access time)(从具有存取请求开始到存取被实施为 止的最长时间)的循环(round robin)方式的硬件机制(hardwarc mechanism)(例如，参照专利文献1)。
此外，还已知不是专门涉及总线仲裁，而是在多任务 (multitasking)处理中为了调度(scheduling)多个程序的执行，而 使用了被称作EDF(Earliest Deadline First)的方法等。具体而言，进 行如下处理，即生成等待执行队列，在生成新的任务时等情况下，利 用至最后期限(dead line)为止的时间长度来进行排序(sort)(例如， 参照专利文献2)。
另一方面，例如在近年来的数字AV(audio visual)家电中，考 虑采用如下一种结构，即在系统LSI的内部设置有进行实时性高的 AV处理的AV处理模块和进行GUI(graphical user interface：图形用 户界面)等与计算机同样复杂的控制的通用微机(micro computer) 等，且各个功能模块共用相同的存储器。这样，在要求实时性的系统 和如微机那样虽然不要求那么高实时性但却要求高性能 (performance)(平均性能)的系统中，尤其需要高效的仲裁已合并 的存储器的存取，使得兼具实时性和性能。
专利文献1：日本特表2001-516100号公报
专利文献2：日本特开平5-274162号公报
存取仲裁装置的性能，如数字AV(audio visual)家电中的AV 处理模块那样，在要求实时(real time)性高的处理的情况下尤为重 要。对于这种要求高实时性的处理，例如已知使用能保证最低要求的 存取时间(worst access time)(从具有存取请求开始到存取被实施为 止的最长时间)的循环(round robin)方式的硬件机制(hardwarc mechanism)(例如，参照专利文献1)。
此外，还已知不是专门涉及总线仲裁，而是在多任务 (multitasking)处理中为了调度(scheduling)多个程序的执行，而 使用了被称作EDF(Earliest Deadline First)的方法等。具体而言，进 行如下处理，即生成等待执行队列，在生成新的任务时等情况下，利 用至最后期限(dead line)为止的时间长度来进行排序(sort)(例如， 参照专利文献2)。
另一方面，例如在近年来的数字AV(audio visual)家电中，考 虑采用如下一种结构，即在系统LSI的内部设置有进行实时性高的 AV处理的AV处理模块和进行GUI(graphical user interface：图形用 户界面)等与计算机同样复杂的控制的通用微机(micro computer) 等，且各个功能模块共用相同的存储器。这样，在要求实时性的系统 和如微机那样虽然不要求那么高实时性但却要求高性能 (performance)(平均性能)的系统中，尤其需要高效的仲裁已合并 的存储器的存取，使得兼具实时性和性能。
专利文献1：日本特表2001-516100号公报
专利文献2：日本特开平5-274162号公报
发明内容
上述那样的循环方式，虽然能保证实时性，但因此会在仲裁对象 的处理中需要过高的处理能力。即与请求存取的处理的优先级无关地 以一定的顺序许可存取，因此，需要可以在进行了优先级低的处理后 进行优先级高的处理这样的处理能力。
另一方面，虽然已知EDF方法能进行最佳的调度，但却难以以 硬件逐次生成任务时或执行完成时地频繁进行重新排列等待队列的 项目的处理等。因此，难以适用于需要总线仲裁等这样的高速响应的 情况。
而且，EDF方法虽然能够容易地适用于最后期限被明确地决定的 实时系统的处理，但非实时系统的处理则没有明确的最后期限(虽然 需要平均的处理能力，但却没有各处理在何时之前必须完成这样的制 约)，因此，其应用未必容易。尤其是当实时系统的处理和非实时系 统的处理混合在一起时，难以将已被合并的存储器的存取高效地仲裁 为兼具实时性和性能的方式。
本发明鉴于上述问题点，以提供一种存取仲裁装置为目的，该存 取仲裁装置能以简洁的硬件结构高速进行适当的仲裁，并且，即使是 在实时系统的处理和非实时系统的处理混合在一起的情况下，也能共 同地进行这些处理，容易地进行兼具实时性和性能的高效的仲裁。
为了解决上述课题，本发明实施方式的第一存取仲裁装置，用于 仲裁由多个请求者对存取对象的存取请求，其特征在于，
包括
优先级保持机构，用于保持对于各请求者的存取许可的优先级；
优先级控制机构，用于控制上述优先级保持机构所保持的优先 级；以及
存取许可机构，用于对上述优先级保持机构所保持的优先级最高 的请求者给予存取许可，其中，上述优先级控制机构的构成为：当有 来自请求者的存取请求时、和没有存取请求且优先级低于预定的基准 优先级时，按照经过的时间来使优先级上升预定的上升程度；而当存 取已被许可时，使优先级降低预定的降低程度。
本发明实施方式的第二存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级的上升程度和降低程度按每个请求者而被设 定。
本发明实施方式的第三存取仲裁装置的特征在于，在第一存取仲 裁装置中，在请求者所请求的存取完成时进行上述优先级的降低。
据此，能够不需要等待队列的排序处理等地利用加减法等程度的 处理进行仲裁，使得在最佳的响应时间进行存取。而且，对于所谓的 非实时系统的处理等，也能够通过设定基准优先级等的值，而容易地 与实时系统的处理等一并进行仲裁。
本发明实施方式的第四存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述存取许可机构对由上述优先级的降低而导致优先级低 于预定的停止许可优先级的请求者不给予存取许可。
由此，能够防止在连续进行了存取请求时，对应于优先级的值变 得过大或变得过小。
本发明实施方式的第五存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在所有请求者的优先级都低于上述 基准优先级的情况下，将至少一部分的预定的请求者的优先级设定为 基准优先级。
本发明实施方式的第六存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在没有来自所有的请求者的存取请 求的情况下，将至少一部分的预定的请求者的优先级设定为上述基准 优先级。
本发明实施方式的第七存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在只有来自1个请求者的存取请求 的情况下，将没有存取请求的其他请求者中的至少一部分的预定请求 者的优先级设定为上述基准优先级。
据此，即使当由连续的存取请求而使得优先级降低时，在没有其 他的存取请求等情况下，能使优先级得以恢复而变得易于被许可存 取。
本发明实施方式的第八存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在直到上述优先级达到预定的极限 优先级为止未对任何请求者给予存取许可的情况下，输出出错信号。
由此，能够容易地确认仲裁是否被适当地进行等。
根据本发明，能够以简单的电路，对多个处理或装置(请求者) 共用存储器的情况下的总线仲裁等，实现例如兼具实时性和性能的高 效率的仲裁。
另一方面，虽然已知EDF方法能进行最佳的调度，但却难以以 硬件逐次生成任务时或执行完成时地频繁进行重新排列等待队列的 项目的处理等。因此，难以适用于需要总线仲裁等这样的高速响应的 情况。
而且，EDF方法虽然能够容易地适用于最后期限被明确地决定的 实时系统的处理，但非实时系统的处理则没有明确的最后期限(虽然 需要平均的处理能力，但却没有各处理在何时之前必须完成这样的制 约)，因此，其应用未必容易。尤其是当实时系统的处理和非实时系 统的处理混合在一起时，难以将已被合并的存储器的存取高效地仲裁 为兼具实时性和性能的方式。
本发明鉴于上述问题点，以提供一种存取仲裁装置为目的，该存 取仲裁装置能以简洁的硬件结构高速进行适当的仲裁，并且，即使是 在实时系统的处理和非实时系统的处理混合在一起的情况下，也能共 同地进行这些处理，容易地进行兼具实时性和性能的高效的仲裁。
为了解决上述课题，本发明实施方式的第一存取仲裁装置，用于 仲裁由多个请求者对存取对象的存取请求，其特征在于，
包括
优先级保持机构，用于保持对于各请求者的存取许可的优先级；
优先级控制机构，用于控制上述优先级保持机构所保持的优先 级；以及
存取许可机构，用于对上述优先级保持机构所保持的优先级最高 的请求者给予存取许可，其中，上述优先级控制机构的构成为：当有 来自请求者的存取请求时、和没有存取请求且优先级低于预定的基准 优先级时，按照经过的时间来使优先级上升预定的上升程度；而当存 取已被许可时，使优先级降低预定的降低程度。
本发明实施方式的第二存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级的上升程度和降低程度按每个请求者而被设 定。
本发明实施方式的第三存取仲裁装置的特征在于，在第一存取仲 裁装置中，在请求者所请求的存取完成时进行上述优先级的降低。
据此，能够不需要等待队列的排序处理等地利用加减法等程度的 处理进行仲裁，使得在最佳的响应时间进行存取。而且，对于所谓的 非实时系统的处理等，也能够通过设定基准优先级等的值，而容易地 与实时系统的处理等一并进行仲裁。
本发明实施方式的第四存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述存取许可机构对由上述优先级的降低而导致优先级低 于预定的停止许可优先级的请求者不给予存取许可。
由此，能够防止在连续进行了存取请求时，对应于优先级的值变 得过大或变得过小。
本发明实施方式的第五存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在所有请求者的优先级都低于上述 基准优先级的情况下，将至少一部分的预定的请求者的优先级设定为 基准优先级。
本发明实施方式的第六存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在没有来自所有的请求者的存取请 求的情况下，将至少一部分的预定的请求者的优先级设定为上述基准 优先级。
本发明实施方式的第七存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在只有来自1个请求者的存取请求 的情况下，将没有存取请求的其他请求者中的至少一部分的预定请求 者的优先级设定为上述基准优先级。
据此，即使当由连续的存取请求而使得优先级降低时，在没有其 他的存取请求等情况下，能使优先级得以恢复而变得易于被许可存 取。
本发明实施方式的第八存取仲裁装置的特征在于，在第一存取仲 裁装置中，上述优先级控制机构还在直到上述优先级达到预定的极限 优先级为止未对任何请求者给予存取许可的情况下，输出出错信号。
由此，能够容易地确认仲裁是否被适当地进行等。
根据本发明，能够以简单的电路，对多个处理或装置(请求者) 共用存储器的情况下的总线仲裁等，实现例如兼具实时性和性能的高 效率的仲裁。
附图说明
图1是表示存取仲裁装置结构的框图。
图2是表示仲裁动作与优先级控制值等的变化之间关系的例子的 说明图。
图3是表示1个可仲裁条件的导出过程的说明图。
图4是表示其他可仲裁条件的导出过程的说明图。
图5是表示可仲裁条件验证装置的动作的流程图。
标号说明
100 存取仲裁装置
101 优先级控制值寄存器
102 优先级控制值控制部
103 选择部
104 存取控制部
201·202 请求者
203 存储器
图2是表示仲裁动作与优先级控制值等的变化之间关系的例子的 说明图。
图3是表示1个可仲裁条件的导出过程的说明图。
图4是表示其他可仲裁条件的导出过程的说明图。
图5是表示可仲裁条件验证装置的动作的流程图。
标号说明
100 存取仲裁装置
101 优先级控制值寄存器
102 优先级控制值控制部
103 选择部
104 存取控制部
201·202 请求者
203 存储器
具体实施方式
作为本发明的实施方式，如图1所示，对存取仲裁装置100的例 子进行说明，该存取仲裁装置100用于仲裁由2个请求者201·202请 求的对存储器203的存取。
该存取仲裁装置100，根据从由请求者201·202给予的基准优先 值(TMIN)、优先级降低值(PERIOD)、以及停止许可优先值(TMAX) 来，进行仲裁(上述各值和后述的优先级控制值是与优先级相关的值， 但为了便于说明，其单位作为时钟周期(clock circle)数或者与此对 应的时间的次元来进行说明。)。
当以预定以上的请求周期进行请求时，上述基准优先值(TMIN)， 表示从进行请求开始，应在该值的响应时间(时钟周期数)以内完成 存取。上述预定以上的请求周期，是满足(请求周期-优先级降低值 (PERIOD))的累计值≥0这样的周期(上述累计值在每次累计值＞0 时被复位为0。)。此处，上述响应时间，能通过上述基准优先值(TMIN) 以及优先级降低值(PERIOD)、和各请求者201·202的存取所需的 时间(Taccess)，如后文详述的那样满足预定的条件来保证。
另外，停止许可优先值(TMAX)，表示在优先级控制值超过该 值的期间，可以与其他请求者的优先级控制值之间的大小关系无关 地，不许可进行存取(优先级控制值增大而超过停止许可优先值 (TMAX)，例如是在连续进行使用比优先级降低值(PERIOD)短 的周期的请求的情况下发生的，即使在优先级控制值超过停止许可优 先值(TMAX)的期间不许可存取，也能保证平均的响应时间。)。
另外，通常，非实时系统的处理或处理装置，未必要求绝对的响 应性，但通过与实时系统同样地设定上述各参数，能够不作特别区分 地进行仲裁动作本身。由此，例如能够提供实时系统的存取的剩余带 宽，作为对非实时系统的存取的最低保证(即使在这种情况下，也能 如后述那样地，在处理有富余时，充分发挥在此之上的性能。)。
存取仲裁装置100
存取仲裁装置100，具体而言，包括：优先级控制值寄存器 101·101，用于保持对于各请求者201·202的优先级控制值；优先级控 制值控制部102·102，用于控制上述优先级控制值；选择部103，根据 优先级控制值寄存器101·101所保持的优先级控制值，选择许可存取 的请求者201·202；以及存取控制部104，根据选择结果进行存取控制。
上述优先级控制值寄存器101所保持的优先级控制值，例如表示 到由各请求者201·202请求的存取应该完成时为止的时间(时钟周期 数)。因此，在这种情况下，值越小优先级越高。上述优先级控制值 寄存器101，具体而言，例如使用计数器(counter)来构成。
优先级控制值控制部102，根据从请求者201·202给予的预定的 基准优先值(TMIN)、和优先级降低值(PERIOD)，如图2和以下 所述那样，控制上述优先级控制值寄存器101所保持的优先级控制值。
(a)逐个时钟周期地，使优先级控制值减少1。
(b)但是，当没有来自请求者201·202的请求时(请求信号未被 确认有效(assert)时)，不使优先级控制值变得比基准优先值(TMIN) 小。
(c)当由请求者201·202请求的对存储器203的存取完成时，使 优先级控制值增加优先级降低值(PERIOD)。上述存取的完成，具 体而言，例如利用在存取完成时请求信号被确认无效(negate)来进 行检测。
进而，优先级控制值控制部102，在优先级控制值为基准优先值 (TMIN)以上(优先级低)时，输出被确认无效的占用(busy)信 号，并且当该占用信号无论对哪个请求者201·202都被确认无效时， 如后述那样，根据来自存取控制部104的初始化信号被确认有效，而 将优先级控制值设定为基准优先值(TMIN)。
此外，当优先级控制值变为负时(在减1前为0时)，输出被确 认无效的出错信号。该出错信号，例如在存取仲裁装置的调试(debug) 时，能够用于确认仲裁未失败等，但也可以不一定要输出这种出错信 号。
而且，选择部103选择请求信号被确认有效的请求者201·202中 的、优先级控制值寄存器101所保持的优先级控制值小的一者，输出 选择结果信号。但是，当优先级控制值超过从请求者201·202输出的 停止许可优先值(TMAX)时，不进行选择。
存取控制部104，根据上述选择结果信号，向请求者201·202输 出存取许可信号。而且，如上述那样，当从所有的优先级控制值控制 部102输出的占用信号都被确认无效时(无论对哪个请求者201·202， 优先级控制值都为基准优先值(TMIN)以上时)，将向至少对应于 请求者201·202中的一者的优先级控制值控制部102输出的初始化信 号确认有效，使优先级控制值设定为基准优先值(TMIN)。
上述基准优先值(TMIN)等的值，不限于从请求者201·202提供， 既可以从其他的管理装置等提供，也可以预先由存取仲裁装置设定。 另外，使其被保持在寄存器等中，而能够不变更电路地变更参数，则 可以提高应对于方法变更的灵活性和通用性等。
而且，请求者的数量不限于2个，尤其是即便在请求者的数量较 多的情况下，各请求者也同样地进行使用，不会造成电路规模和复杂 程度的大幅度增加，因此，也可以容易地构成能仲裁多个请求者的装 置。
此外，优先级降低值(PERIOD)的加法定时(timing)等，不限 于上述那样的情况，也可以使用能够取得实质上相同的动作的各种变 形例。具体而言，例如，在如上述那样当存取完成时加上优先级降低 值(PERIOD)的情况下，易于以与请求周期等的关系来把握值的意 义，但也可以在进行了存取许可的时刻，加上考虑了存取中的优先级 控制值的减少的值。
如上述那样地构成的存取仲裁装置100，当如在后文中详述的那 样满足预定的条件时，由请求者201·202请求的存取必须在优先级控 制值变为0之前完成。即优先级控制值，在进行了请求时，表示到存 取应该完成时(最后期限)为止的时间。另外，上述优先级控制值最 小(最后期限最近)的请求者201·202被选择，因此，该存取仲裁装 置100进行基于EDF(Earliest Deadline First)算法(algorithm)的仲 裁。
以下，根据图2说明具体的动作例。
(A)在仲裁开始之际等，当在优先级控制值为基准优先值 (TMIN)的状态下，请求信号被确认有效时，优先级控制值随着时 间的经过而减少(优先级逐渐上升。)。
(B)当不久后优先级控制值小于进行请求的其他请求者的优先 级控制值时，许可进行存取。当存取时间(Taccess)的存取完成而请 求信号被确认无效时，优先级控制值上升为加上了优先级降低值 (PERIOD)的值。
(C)已上升的优先级控制值，至少到降低为基准优先值(TMIN) 为止，与有无下一请求无关地逐渐减少。
(D)当有下一请求时，在优先级控制值降低至基准优先值 (TMIN)后，仍然继续降低。不久后与上述(B)同样地，被许可进 行存取，在优先级控制值变为0之前完成存取。于是，优先级控制值， 进而上升为加上了优先级降低值(PERIOD)的值。
(E)优先级控制值与(C)同样逐渐减少，但当在优先级控制值 降低至基准优先值(TMIN)的时刻没有下一请求时，在出现下一请 求前，优先级控制值被保持为基准优先值(TMIN)。
(F)当出现下一请求时，优先级控制值开始降低。并且，被许 可进行存取，在存取完成时，上升为加上了优先级降低值(PERIOD) 的值。
(G)依然是优先级控制值逐渐减少。此处，即使优先级控制值 比基准优先值(TMIN)大，但如果比其他请求者的优先级控制值小， 则被许可进行存取。但是，当优先级控制值大于停止许可优先值 (TMAX)时，存取许可被抑制。因此，即使在短时间内重复进行请 求，优先级控制值也不会变得比(停止许可优先值(TMAX)+优先 级降低值(PERIOD))大，因此，能够避免优先级控制值寄存器101 的溢出(overflow)。而且，即使如上述那样地存取许可被抑制，也 能如前述那样保证平均的响应时间。
另外，当上述停止许可优先值(TMAX)被设定为比较小的值时， 即使频繁地进行了请求，一定周期以下的请求也会被禁止而谋求存取 的平均化，因此，能够容易地实现例如适当地进行存储器的刷新 (refresh)动作等。另一方面，当停止许可优先值(TMAX)被设定 为较大的值时，便能够许可连续的存取。因此，例如对于非实时系统 的请求者等，通过将停止许可优先值(TMAX)设定得比较大，能够 将性能设定得比较高。
另外，即使没有一定要进行如上述那样的存取许可的抑制，若优 先级控制值寄存器101的容量足够大，则也能够适当地进行仲裁动作 本身。
(H)另一方面，即使在优先级控制值比停止许可优先值(TMAX) 大的情况下，若所有请求者201·202的优先级控制值分别大于等于基 准优先值(TMIN)(占用信号为确认无效状态)，则所有请求者或 者一部分请求者的优先级控制值，例如被设定为基准优先值(TMIN)， 然后进行了请求之后、或者在已经进行着请求时，立刻从上述基准优 先值(TMIN)开始降低。
此处，如上述那样，当所有请求者201·202的优先级控制值分别 为基准优先值(TMIN)以上时，即使各优先级控制值被设定为基准 优先值(TMIN)，也不会破坏适当的存取。这可以从以下的观点得 到明确。即当满足预定的条件时，就能保证在基准优先值(TMIN) 以内的期间完成各请求者的存取。因此，无论哪个请求者，即使将优 先级控制值从比基准优先值(TMIN)大的值降低至基准优先值 (TMIN)，该请求者的存取也能得到保证。而且，上述保证与其他 请求者的优先级控制值是如何设定的无关，因此，即使将上述其他请 求者的优先级控制值分别降低至基准优先值(TMIN)也不受妨碍。 因此，在所有请求者的优先级控制值都比基准优先值(TMIN)大的 情况下，无论哪个请求者的优先级控制值都能变更为基准优先值 (TMIN)。
而且，如上述那样，通过在判断为仲裁未失败时变更优先级控制 值，使得即使是超过了停止许可优先值(TMAX)的请求者，也能够 尽可能地被许可进行存取。因此，可以是对于所有请求者变更为基准 优先值(TMIN)，但例如，通过对非实时系统的请求者进行如上述 那样的变更，既能够容易地确保实时系统的请求者所需的存取(保证 最长延迟时间而保证实时性)，又能够容易地提高非实时系统的请求 者所需的处理的性能等。
另外，也可以代替如上述那样的判断所有请求者201·202的占用 信号是否为被确认无效的状态，而判断是否无论从哪个请求者 201·202都没有进行请求。即当没有进行请求时，优先级控制值不会 小于基准优先值(TMIN)，因此，所获得的判定结果是相同的。进 而，当进行请求的请求者仅为1个时也是该请求者立刻被许可进行存 取，因此，在这种情况下，可以其他所有的请求者、或者一部分请求 者变更优先级控制值。而且，所变更的值不限于基准优先值(TMIN)， 以此为限度是使优先级变高的变更即可。
在进行如上述那样的仲裁的情况下的请求后，到存取完成为止的 响应时间最大值如下式，
max{(n-1)×PERIOD-T(n)，0}+TMIN
其中，将第n个请求时刻设为T(n)(max {，}代表{，}内大的 一者的值。)。之所以如此，是因为优先级控制值，逐次对于到第n -1个为止的各请求的存取完成地增加1次优先级降低值(PERIOD)， 减少至时刻T(n)为止的经过时间，但是，在没有请求的状态下则 不会从基准优先值(TMIN)减少。
可仲裁条件
接着，说明如下条件(可仲裁条件)及其验证。即该条件用于保 证当各请求者的请求周期分别为预定以上时，无论对于哪个请求者， 在从进行请求开始的预定的响应时间以内，即在优先级控制值变为0 之前，必须存取被进行(完成)。
上述可仲裁条件，首先，考虑在某个时刻t＝Terror仲裁失败的情 况，即考虑在时刻t＝Terror，某个请求者的最后的存取尚未完成，优 先级控制值就变为0的情况，只需求出在此之前的存取全部被许可并 完成的条件，进而，求出对于任意的t＝Terror满足该条件的条件即可。
存取失败的情况，可以划分成以下这2种失败类型。此处，如前 述那样，在存取完成时加上优先级降低值(PERIOD)。另外，在以 下的说明中，概括各请求者以及与各请求者相关的值而附加标记(j) 等进行表示。
(1)第1失败类型
对于各请求者(j)，当至最后存取完成为止的优先级控制值P (j)小于等于Terror-t时
各请求者(j)在时刻t的优先级控制值P(j)，如图3所示，将 基准优先值(TMIN(j))作为初始值，逐次存取完成地增加一次优 先级降低值(PERIOD(j))，随着时间的经过而减少t。于是，在 到时刻t＝Terror之前，将逐个请求者的存取已完成的次数设为n0(j)， 将优先级控制值P(j)被保持在TMIN(j)的时间的合计设为Twait (j)时，到第n0(j)次存取完成为止的p(j)以下式进行计算(因 为可以不考虑在最后的存取完成后加上的PERIOD(j))。
P(j)＝TMIN(j)+{n0(j)-1}×PERIOD(j)-t+Twait(j)
而且，在为第1失败类型的情况下，对于所有的请求者(j)，始 终是满足下式。
P(j)≤Terror-t
因此，
TMIN(j)+{n0(j)-1}×PERIOD(j)-t+Twait(j)
≤Terror-t。
因此，上述存取完成次数n0(j)为，
n0(j)
≤{Terror-TMIN(j)-Twait(j)}/PERIOD(j)+1
≤{Terror-TMIN(j)}/PERIOD(j)+1。
(∵Twait(j)≥0)。
即对于各请求者(j)，在t＝Terror之前完成的存取次数小于等于 {Terror-TMIN(j)}/PERIOD(j)+1。
另一方面，将各请求者(j)的存取所需的时间设为Taccess(j)， 对于最初的请求者的请求，将被许可存取后至开始存取为止的时间设 为delay，则所有请求者的存取时间的总计(Tall)为，
Tall
＝delay+∑n0(j)×Taccess(j)
≤delay+∑〔{Terror-TMIN(j)}/PERIOD(j)+1〕×Taccess(j)。
因为当该值小于等于Terror时，时刻t＝Terror之前的所有存取已 确实完成(未失败)，
delay+∑〔{Terror-TMIN(j)}/PERIOD(j)+1〕×Taccess(j)
≤Terror(上述除法进行舍去。)...(式1)
因此，当对于任意的Terror上述(式1)成立时，在各请求者的 请求周期分别为预定以上的情况下，无论对于任何请求，在优先级控 制值变为0之前，即在进行请求后的预定的响应时间以内，能够保证 存取被许可并完成。
(2)第2失败类型
当时刻t＝Terror之前存取完成的请求者(j)中，存在优先级控制 值P(j)大于Terror-t的情况时
在这种情况下，仅考虑优先级控制值P(j)变得比Terror-t大 的最后的请求被许可之后的动作即可。更具体而言，例如，如图4所 示，考虑如下情况即可，即在请求者(k)的请求被许可而完成了存 取后，到t＝Terror之前，至最后存取完成为止的各个优先级控制值P (j)小于等于Terror-t的情况(此处，在图4中，为了便于说明， 将对请求者(k)进行存取许可后的1个时钟周期后的定时取为t＝0， 之后在经过(delay-1)后进行Taccess(k)期间的存取。)。
之所以说只需考虑上述这种情况即可，是基于如下的理由。
对于在t＝-1之前进行请求的其他请求者(j)，当其优先级控制 值P(j)比优先级控制值P(k)小时，在其存取完成后请求者(k) 的存取被许可(成为图4的状态)，因此不需要加以考虑。另一方面， 当优先级控制值P(j)比优先级控制值P(k)大时，其请求者(j) 被许可存取是在t＝Terror以后，因此，仍然不需要加以考虑。请求者 (k)在该图的存取之后再次进行存取的情况也是同样的(基于上述 理由，可以认为在t＝0的时刻，没有来自请求者(k)以外的请求者 (j)的请求。)。
进而，在请求者(k)的存取之后，也不需要考虑优先级控制值P 变得比Terror-t大的其他请求者。当存在这种请求者时，关于该请 求者，会成为图4的状态，因此，结果是只需以请求者(k)为代表 进行考虑即可。
在第2失败类型的情况下，可以认为如上述那样，在t＝0的时刻， 没有来自请求者(k)以外的请求者(j)的请求，因此，这些优先级 控制值P(j)分别成为TMIN(j)以上(设为TMIN(j)+α)。于 是，在时刻t＝0～Terror之前，将逐个请求者的存取已完成的次数设 为n1(j)时，至t＝0之后、第n1(j)次存取完成为止的P(j)，与 (1)的情况相同地进行考虑，则
P(j)
＝{TMIN(j)+α}+{n1(j)-1}×PERIOD(j)-t+Twait(j)，
在第2失败类型的情况下，对于所有的请求者(j)，始终为
P(j)≤Terror-t，
因此，
{TMIN(j)+α}+{n1(j)-1}×PERIOD(j)-t+Twait(j)
≤Terror-t。
因此，上述存取完成次数n1(j)，为
n1(j)≤{Terror-TMIN(j)}/PERIOD(j)+1。
(∵α≥0，Twait(j)≥0)
另一方面，仍然与(1)的情况同样地，所有请求者的存取时间 的总计(Tall)为，
Tall
＝{delay-1+Taccess(k)}+∑n1(j)×Taccess(j)
≤{delay-1+Taccess(k)}+∑〔{Terror-TMIN(j)}/PERIOD(j)+1〕
×Taccess(j)。
当该值小于等于Terror时，则时刻t＝Terror之前的所有存取已确 实完成(未失败)，因此，
{delay-1+Taccess(k)}+∑〔{Terror-TMIN(j)}/PERIOD(j)
+1〕×Taccess(j)
≤Terror(上述除法进行舍去。而且，∑内的j不包括j＝k的情况。)
...(式2)
因此，当对于任意的Terror上述(式2)成立时，若各请求者的 请求周期分别为预定以上，则无论对于哪个请求者，在优先级控制值 变为0之前，即在进行请求之后的预定的响应时间以内，能够保证进 行存取。
因此，当同时满足上述(式1、2)时，能保证在所有情况下，优 先级控制值都不变成0地进行仲裁。
此处，上述(式1、2)，如以上那样，是以本实施方式的存取仲 裁装置100的动作为前提而进行导出的，但当由这些而保证可进行仲 裁时，也可以构成使用了EDF方法的其他存取仲裁装置。即当用某 种方法示出能进行仲裁时，则用EDF方法的存取仲裁装置也必能进 行仲裁，因此，上述那样的验证，能够广泛应用于各种存取仲裁装置 的仲裁可能性的验证。
另外，在上述(式1、2)中示出了使用“≤”进行表述的例子， 但实质上，根据时钟定时(clock timing)的考虑方法等也可以将使用 了“＜”的式子作为条件等。
可仲裁条件验证装置
接着，对利用上述(式1、2)的设计装置(可仲裁条件验证装置) 进行说明。该设计装置，并无特殊限定，例如，可以是在计算机中安 装发挥图5所示的各种功能的软件而构成的。
(S101)首先，例如决定对作为存取对象的共用存储器进行存 取的功能模块。
(S102)决定各功能模块的对存储器存取(memory access)的 要求参数即基准优先值(TMIN)和优先级降低值(PERIOD)、以及 各功能块的存取所需的时间(Taccess)。其对应于所需的响应时间(延 迟时间)、请求周期(请求带宽)、数据传输能力和输入输出速度等。
另外，上述(S102、S102)的决定也可以在外部进行，从输入部 仅输入上述参数。
(S103)使用上述(式1、2)来检查(check)存取仲裁装置整 体上是否成立即对于预定数的各种Terror值检查其是否成立。
(S104)判断仲裁是否失败，如果仲裁失败，返回(S101)，进 行对共用存储器进行存取的功能模块的取舍选择、仲裁要求参数的变 更，重复进行评价。
(S105)另一方面，当在上述(S104)的判断中判断为可进行仲 裁时，进行满足上述参数的各功能模块、共用存储器以及存储器总线 等的详细电路设计。据此就能不用苛刻的技术要求(over spec)而容 易构成最佳系统。另外，也可以对应于设计制造的阶段，利用模拟和 实机调试(debug)来确认是否优先级控制值为0而从优先级控制值 控制部102输出出错信号。
产业上的可利用性
本发明的存取仲裁装置具有能够以简单的电路对多个处理或者 装置(请求者)共用存储器时的总线仲裁等实现例如兼具实时性和性 能的高效率仲裁这样的效果，且其作为被用于存储接口和任务控制等 的存取仲裁装置(arbiter)等是有用的。
该存取仲裁装置100，根据从由请求者201·202给予的基准优先 值(TMIN)、优先级降低值(PERIOD)、以及停止许可优先值(TMAX) 来，进行仲裁(上述各值和后述的优先级控制值是与优先级相关的值， 但为了便于说明，其单位作为时钟周期(clock circle)数或者与此对 应的时间的次元来进行说明。)。
当以预定以上的请求周期进行请求时，上述基准优先值(TMIN)， 表示从进行请求开始，应在该值的响应时间(时钟周期数)以内完成 存取。上述预定以上的请求周期，是满足(请求周期-优先级降低值 (PERIOD))的累计值≥0这样的周期(上述累计值在每次累计值＞0 时被复位为0。)。此处，上述响应时间，能通过上述基准优先值(TMIN) 以及优先级降低值(PERIOD)、和各请求者201·202的存取所需的 时间(Taccess)，如后文详述的那样满足预定的条件来保证。
另外，停止许可优先值(TMAX)，表示在优先级控制值超过该 值的期间，可以与其他请求者的优先级控制值之间的大小关系无关 地，不许可进行存取(优先级控制值增大而超过停止许可优先值 (TMAX)，例如是在连续进行使用比优先级降低值(PERIOD)短 的周期的请求的情况下发生的，即使在优先级控制值超过停止许可优 先值(TMAX)的期间不许可存取，也能保证平均的响应时间。)。
另外，通常，非实时系统的处理或处理装置，未必要求绝对的响 应性，但通过与实时系统同样地设定上述各参数，能够不作特别区分 地进行仲裁动作本身。由此，例如能够提供实时系统的存取的剩余带 宽，作为对非实时系统的存取的最低保证(即使在这种情况下，也能 如后述那样地，在处理有富余时，充分发挥在此之上的性能。)。
存取仲裁装置100
存取仲裁装置100，具体而言，包括：优先级控制值寄存器 101·101，用于保持对于各请求者201·202的优先级控制值；优先级控 制值控制部102·102，用于控制上述优先级控制值；选择部103，根据 优先级控制值寄存器101·101所保持的优先级控制值，选择许可存取 的请求者201·202；以及存取控制部104，根据选择结果进行存取控制。
上述优先级控制值寄存器101所保持的优先级控制值，例如表示 到由各请求者201·202请求的存取应该完成时为止的时间(时钟周期 数)。因此，在这种情况下，值越小优先级越高。上述优先级控制值 寄存器101，具体而言，例如使用计数器(counter)来构成。
优先级控制值控制部102，根据从请求者201·202给予的预定的 基准优先值(TMIN)、和优先级降低值(PERIOD)，如图2和以下 所述那样，控制上述优先级控制值寄存器101所保持的优先级控制值。
(a)逐个时钟周期地，使优先级控制值减少1。
(b)但是，当没有来自请求者201·202的请求时(请求信号未被 确认有效(assert)时)，不使优先级控制值变得比基准优先值(TMIN) 小。
(c)当由请求者201·202请求的对存储器203的存取完成时，使 优先级控制值增加优先级降低值(PERIOD)。上述存取的完成，具 体而言，例如利用在存取完成时请求信号被确认无效(negate)来进 行检测。
进而，优先级控制值控制部102，在优先级控制值为基准优先值 (TMIN)以上(优先级低)时，输出被确认无效的占用(busy)信 号，并且当该占用信号无论对哪个请求者201·202都被确认无效时， 如后述那样，根据来自存取控制部104的初始化信号被确认有效，而 将优先级控制值设定为基准优先值(TMIN)。
此外，当优先级控制值变为负时(在减1前为0时)，输出被确 认无效的出错信号。该出错信号，例如在存取仲裁装置的调试(debug) 时，能够用于确认仲裁未失败等，但也可以不一定要输出这种出错信 号。
而且，选择部103选择请求信号被确认有效的请求者201·202中 的、优先级控制值寄存器101所保持的优先级控制值小的一者，输出 选择结果信号。但是，当优先级控制值超过从请求者201·202输出的 停止许可优先值(TMAX)时，不进行选择。
存取控制部104，根据上述选择结果信号，向请求者201·202输 出存取许可信号。而且，如上述那样，当从所有的优先级控制值控制 部102输出的占用信号都被确认无效时(无论对哪个请求者201·202， 优先级控制值都为基准优先值(TMIN)以上时)，将向至少对应于 请求者201·202中的一者的优先级控制值控制部102输出的初始化信 号确认有效，使优先级控制值设定为基准优先值(TMIN)。
上述基准优先值(TMIN)等的值，不限于从请求者201·202提供， 既可以从其他的管理装置等提供，也可以预先由存取仲裁装置设定。 另外，使其被保持在寄存器等中，而能够不变更电路地变更参数，则 可以提高应对于方法变更的灵活性和通用性等。
而且，请求者的数量不限于2个，尤其是即便在请求者的数量较 多的情况下，各请求者也同样地进行使用，不会造成电路规模和复杂 程度的大幅度增加，因此，也可以容易地构成能仲裁多个请求者的装 置。
此外，优先级降低值(PERIOD)的加法定时(timing)等，不限 于上述那样的情况，也可以使用能够取得实质上相同的动作的各种变 形例。具体而言，例如，在如上述那样当存取完成时加上优先级降低 值(PERIOD)的情况下，易于以与请求周期等的关系来把握值的意 义，但也可以在进行了存取许可的时刻，加上考虑了存取中的优先级 控制值的减少的值。
如上述那样地构成的存取仲裁装置100，当如在后文中详述的那 样满足预定的条件时，由请求者201·202请求的存取必须在优先级控 制值变为0之前完成。即优先级控制值，在进行了请求时，表示到存 取应该完成时(最后期限)为止的时间。另外，上述优先级控制值最 小(最后期限最近)的请求者201·202被选择，因此，该存取仲裁装 置100进行基于EDF(Earliest Deadline First)算法(algorithm)的仲 裁。
以下，根据图2说明具体的动作例。
(A)在仲裁开始之际等，当在优先级控制值为基准优先值 (TMIN)的状态下，请求信号被确认有效时，优先级控制值随着时 间的经过而减少(优先级逐渐上升。)。
(B)当不久后优先级控制值小于进行请求的其他请求者的优先 级控制值时，许可进行存取。当存取时间(Taccess)的存取完成而请 求信号被确认无效时，优先级控制值上升为加上了优先级降低值 (PERIOD)的值。
(C)已上升的优先级控制值，至少到降低为基准优先值(TMIN) 为止，与有无下一请求无关地逐渐减少。
(D)当有下一请求时，在优先级控制值降低至基准优先值 (TMIN)后，仍然继续降低。不久后与上述(B)同样地，被许可进 行存取，在优先级控制值变为0之前完成存取。于是，优先级控制值， 进而上升为加上了优先级降低值(PERIOD)的值。
(E)优先级控制值与(C)同样逐渐减少，但当在优先级控制值 降低至基准优先值(TMIN)的时刻没有下一请求时，在出现下一请 求前，优先级控制值被保持为基准优先值(TMIN)。
(F)当出现下一请求时，优先级控制值开始降低。并且，被许 可进行存取，在存取完成时，上升为加上了优先级降低值(PERIOD) 的值。
(G)依然是优先级控制值逐渐减少。此处，即使优先级控制值 比基准优先值(TMIN)大，但如果比其他请求者的优先级控制值小， 则被许可进行存取。但是，当优先级控制值大于停止许可优先值 (TMAX)时，存取许可被抑制。因此，即使在短时间内重复进行请 求，优先级控制值也不会变得比(停止许可优先值(TMAX)+优先 级降低值(PERIOD))大，因此，能够避免优先级控制值寄存器101 的溢出(overflow)。而且，即使如上述那样地存取许可被抑制，也 能如前述那样保证平均的响应时间。
另外，当上述停止许可优先值(TMAX)被设定为比较小的值时， 即使频繁地进行了请求，一定周期以下的请求也会被禁止而谋求存取 的平均化，因此，能够容易地实现例如适当地进行存储器的刷新 (refresh)动作等。另一方面，当停止许可优先值(TMAX)被设定 为较大的值时，便能够许可连续的存取。因此，例如对于非实时系统 的请求者等，通过将停止许可优先值(TMAX)设定得比较大，能够 将性能设定得比较高。
另外，即使没有一定要进行如上述那样的存取许可的抑制，若优 先级控制值寄存器101的容量足够大，则也能够适当地进行仲裁动作 本身。
(H)另一方面，即使在优先级控制值比停止许可优先值(TMAX) 大的情况下，若所有请求者201·202的优先级控制值分别大于等于基 准优先值(TMIN)(占用信号为确认无效状态)，则所有请求者或 者一部分请求者的优先级控制值，例如被设定为基准优先值(TMIN)， 然后进行了请求之后、或者在已经进行着请求时，立刻从上述基准优 先值(TMIN)开始降低。
此处，如上述那样，当所有请求者201·202的优先级控制值分别 为基准优先值(TMIN)以上时，即使各优先级控制值被设定为基准 优先值(TMIN)，也不会破坏适当的存取。这可以从以下的观点得 到明确。即当满足预定的条件时，就能保证在基准优先值(TMIN) 以内的期间完成各请求者的存取。因此，无论哪个请求者，即使将优 先级控制值从比基准优先值(TMIN)大的值降低至基准优先值 (TMIN)，该请求者的存取也能得到保证。而且，上述保证与其他 请求者的优先级控制值是如何设定的无关，因此，即使将上述其他请 求者的优先级控制值分别降低至基准优先值(TMIN)也不受妨碍。 因此，在所有请求者的优先级控制值都比基准优先值(TMIN)大的 情况下，无论哪个请求者的优先级控制值都能变更为基准优先值 (TMIN)。
而且，如上述那样，通过在判断为仲裁未失败时变更优先级控制 值，使得即使是超过了停止许可优先值(TMAX)的请求者，也能够 尽可能地被许可进行存取。因此，可以是对于所有请求者变更为基准 优先值(TMIN)，但例如，通过对非实时系统的请求者进行如上述 那样的变更，既能够容易地确保实时系统的请求者所需的存取(保证 最长延迟时间而保证实时性)，又能够容易地提高非实时系统的请求 者所需的处理的性能等。
另外，也可以代替如上述那样的判断所有请求者201·202的占用 信号是否为被确认无效的状态，而判断是否无论从哪个请求者 201·202都没有进行请求。即当没有进行请求时，优先级控制值不会 小于基准优先值(TMIN)，因此，所获得的判定结果是相同的。进 而，当进行请求的请求者仅为1个时也是该请求者立刻被许可进行存 取，因此，在这种情况下，可以其他所有的请求者、或者一部分请求 者变更优先级控制值。而且，所变更的值不限于基准优先值(TMIN)， 以此为限度是使优先级变高的变更即可。
在进行如上述那样的仲裁的情况下的请求后，到存取完成为止的 响应时间最大值如下式，
max{(n-1)×PERIOD-T(n)，0}+TMIN
其中，将第n个请求时刻设为T(n)(max {，}代表{，}内大的 一者的值。)。之所以如此，是因为优先级控制值，逐次对于到第n -1个为止的各请求的存取完成地增加1次优先级降低值(PERIOD)， 减少至时刻T(n)为止的经过时间，但是，在没有请求的状态下则 不会从基准优先值(TMIN)减少。
可仲裁条件
接着，说明如下条件(可仲裁条件)及其验证。即该条件用于保 证当各请求者的请求周期分别为预定以上时，无论对于哪个请求者， 在从进行请求开始的预定的响应时间以内，即在优先级控制值变为0 之前，必须存取被进行(完成)。
上述可仲裁条件，首先，考虑在某个时刻t＝Terror仲裁失败的情 况，即考虑在时刻t＝Terror，某个请求者的最后的存取尚未完成，优 先级控制值就变为0的情况，只需求出在此之前的存取全部被许可并 完成的条件，进而，求出对于任意的t＝Terror满足该条件的条件即可。
存取失败的情况，可以划分成以下这2种失败类型。此处，如前 述那样，在存取完成时加上优先级降低值(PERIOD)。另外，在以 下的说明中，概括各请求者以及与各请求者相关的值而附加标记(j) 等进行表示。
(1)第1失败类型
对于各请求者(j)，当至最后存取完成为止的优先级控制值P (j)小于等于Terror-t时
各请求者(j)在时刻t的优先级控制值P(j)，如图3所示，将 基准优先值(TMIN(j))作为初始值，逐次存取完成地增加一次优 先级降低值(PERIOD(j))，随着时间的经过而减少t。于是，在 到时刻t＝Terror之前，将逐个请求者的存取已完成的次数设为n0(j)， 将优先级控制值P(j)被保持在TMIN(j)的时间的合计设为Twait (j)时，到第n0(j)次存取完成为止的p(j)以下式进行计算(因 为可以不考虑在最后的存取完成后加上的PERIOD(j))。
P(j)＝TMIN(j)+{n0(j)-1}×PERIOD(j)-t+Twait(j)
而且，在为第1失败类型的情况下，对于所有的请求者(j)，始 终是满足下式。
P(j)≤Terror-t
因此，
TMIN(j)+{n0(j)-1}×PERIOD(j)-t+Twait(j)
≤Terror-t。
因此，上述存取完成次数n0(j)为，
n0(j)
≤{Terror-TMIN(j)-Twait(j)}/PERIOD(j)+1
≤{Terror-TMIN(j)}/PERIOD(j)+1。
(∵Twait(j)≥0)。
即对于各请求者(j)，在t＝Terror之前完成的存取次数小于等于 {Terror-TMIN(j)}/PERIOD(j)+1。
另一方面，将各请求者(j)的存取所需的时间设为Taccess(j)， 对于最初的请求者的请求，将被许可存取后至开始存取为止的时间设 为delay，则所有请求者的存取时间的总计(Tall)为，
Tall
＝delay+∑n0(j)×Taccess(j)
≤delay+∑〔{Terror-TMIN(j)}/PERIOD(j)+1〕×Taccess(j)。
因为当该值小于等于Terror时，时刻t＝Terror之前的所有存取已 确实完成(未失败)，
delay+∑〔{Terror-TMIN(j)}/PERIOD(j)+1〕×Taccess(j)
≤Terror(上述除法进行舍去。)...(式1)
因此，当对于任意的Terror上述(式1)成立时，在各请求者的 请求周期分别为预定以上的情况下，无论对于任何请求，在优先级控 制值变为0之前，即在进行请求后的预定的响应时间以内，能够保证 存取被许可并完成。
(2)第2失败类型
当时刻t＝Terror之前存取完成的请求者(j)中，存在优先级控制 值P(j)大于Terror-t的情况时
在这种情况下，仅考虑优先级控制值P(j)变得比Terror-t大 的最后的请求被许可之后的动作即可。更具体而言，例如，如图4所 示，考虑如下情况即可，即在请求者(k)的请求被许可而完成了存 取后，到t＝Terror之前，至最后存取完成为止的各个优先级控制值P (j)小于等于Terror-t的情况(此处，在图4中，为了便于说明， 将对请求者(k)进行存取许可后的1个时钟周期后的定时取为t＝0， 之后在经过(delay-1)后进行Taccess(k)期间的存取。)。
之所以说只需考虑上述这种情况即可，是基于如下的理由。
对于在t＝-1之前进行请求的其他请求者(j)，当其优先级控制 值P(j)比优先级控制值P(k)小时，在其存取完成后请求者(k) 的存取被许可(成为图4的状态)，因此不需要加以考虑。另一方面， 当优先级控制值P(j)比优先级控制值P(k)大时，其请求者(j) 被许可存取是在t＝Terror以后，因此，仍然不需要加以考虑。请求者 (k)在该图的存取之后再次进行存取的情况也是同样的(基于上述 理由，可以认为在t＝0的时刻，没有来自请求者(k)以外的请求者 (j)的请求。)。
进而，在请求者(k)的存取之后，也不需要考虑优先级控制值P 变得比Terror-t大的其他请求者。当存在这种请求者时，关于该请 求者，会成为图4的状态，因此，结果是只需以请求者(k)为代表 进行考虑即可。
在第2失败类型的情况下，可以认为如上述那样，在t＝0的时刻， 没有来自请求者(k)以外的请求者(j)的请求，因此，这些优先级 控制值P(j)分别成为TMIN(j)以上(设为TMIN(j)+α)。于 是，在时刻t＝0～Terror之前，将逐个请求者的存取已完成的次数设 为n1(j)时，至t＝0之后、第n1(j)次存取完成为止的P(j)，与 (1)的情况相同地进行考虑，则
P(j)
＝{TMIN(j)+α}+{n1(j)-1}×PERIOD(j)-t+Twait(j)，
在第2失败类型的情况下，对于所有的请求者(j)，始终为
P(j)≤Terror-t，
因此，
{TMIN(j)+α}+{n1(j)-1}×PERIOD(j)-t+Twait(j)
≤Terror-t。
因此，上述存取完成次数n1(j)，为
n1(j)≤{Terror-TMIN(j)}/PERIOD(j)+1。
(∵α≥0，Twait(j)≥0)
另一方面，仍然与(1)的情况同样地，所有请求者的存取时间 的总计(Tall)为，
Tall
＝{delay-1+Taccess(k)}+∑n1(j)×Taccess(j)
≤{delay-1+Taccess(k)}+∑〔{Terror-TMIN(j)}/PERIOD(j)+1〕
×Taccess(j)。
当该值小于等于Terror时，则时刻t＝Terror之前的所有存取已确 实完成(未失败)，因此，
{delay-1+Taccess(k)}+∑〔{Terror-TMIN(j)}/PERIOD(j)
+1〕×Taccess(j)
≤Terror(上述除法进行舍去。而且，∑内的j不包括j＝k的情况。)
...(式2)
因此，当对于任意的Terror上述(式2)成立时，若各请求者的 请求周期分别为预定以上，则无论对于哪个请求者，在优先级控制值 变为0之前，即在进行请求之后的预定的响应时间以内，能够保证进 行存取。
因此，当同时满足上述(式1、2)时，能保证在所有情况下，优 先级控制值都不变成0地进行仲裁。
此处，上述(式1、2)，如以上那样，是以本实施方式的存取仲 裁装置100的动作为前提而进行导出的，但当由这些而保证可进行仲 裁时，也可以构成使用了EDF方法的其他存取仲裁装置。即当用某 种方法示出能进行仲裁时，则用EDF方法的存取仲裁装置也必能进 行仲裁，因此，上述那样的验证，能够广泛应用于各种存取仲裁装置 的仲裁可能性的验证。
另外，在上述(式1、2)中示出了使用“≤”进行表述的例子， 但实质上，根据时钟定时(clock timing)的考虑方法等也可以将使用 了“＜”的式子作为条件等。
可仲裁条件验证装置
接着，对利用上述(式1、2)的设计装置(可仲裁条件验证装置) 进行说明。该设计装置，并无特殊限定，例如，可以是在计算机中安 装发挥图5所示的各种功能的软件而构成的。
(S101)首先，例如决定对作为存取对象的共用存储器进行存 取的功能模块。
(S102)决定各功能模块的对存储器存取(memory access)的 要求参数即基准优先值(TMIN)和优先级降低值(PERIOD)、以及 各功能块的存取所需的时间(Taccess)。其对应于所需的响应时间(延 迟时间)、请求周期(请求带宽)、数据传输能力和输入输出速度等。
另外，上述(S102、S102)的决定也可以在外部进行，从输入部 仅输入上述参数。
(S103)使用上述(式1、2)来检查(check)存取仲裁装置整 体上是否成立即对于预定数的各种Terror值检查其是否成立。
(S104)判断仲裁是否失败，如果仲裁失败，返回(S101)，进 行对共用存储器进行存取的功能模块的取舍选择、仲裁要求参数的变 更，重复进行评价。
(S105)另一方面，当在上述(S104)的判断中判断为可进行仲 裁时，进行满足上述参数的各功能模块、共用存储器以及存储器总线 等的详细电路设计。据此就能不用苛刻的技术要求(over spec)而容 易构成最佳系统。另外，也可以对应于设计制造的阶段，利用模拟和 实机调试(debug)来确认是否优先级控制值为0而从优先级控制值 控制部102输出出错信号。
产业上的可利用性
本发明的存取仲裁装置具有能够以简单的电路对多个处理或者 装置(请求者)共用存储器时的总线仲裁等实现例如兼具实时性和性 能的高效率仲裁这样的效果，且其作为被用于存储接口和任务控制等 的存取仲裁装置(arbiter)等是有用的。