CN101213533A - 存储器控制器、控制存储器存取的方法以及包括存储器控制器的系统 - Google Patents

Abstract

在用于控制对于共享存储器的多个请求者的存取的方法中，针对连续的时间窗口重复的以下步骤：从不同的请求者接收存取请求(S1)；确定通过请求者请求的存取类型；将所请求的存取类型与针对根据后端调度的各个时间窗口授权存取类型进行比较；产生输入请求的第一选择，所述输入请求具有针对相关的时间窗口的指定存取类型；从第一选择中动态地选择请求之一。

Description

存储器控制器、控制存储器存取的方法以及包括存储器控制器的系统

技术领域

本发明涉及一种存储器控制器。

本发明还涉及一种用于仲裁存储器存取的方法。

本发明还涉及一种包括存储器控制器的系统。

背景技术

当前的数据处理系统可以具有大量的客户端，在下文中称为请求者，具有不同的并且可能冲突的需求。更具体地，在下文中将请求者定义为要求存取存储器的逻辑实体。随机存取存储器RAM是计算机系统中的功能部件。将其用作用于诸如处理器之类的系统中的处理单元的媒质存储器。存在目标在于带宽、功耗和制造成本的需求的多种类型RAM。最常用的两种类型的RAM是SRAM和DRAM。静态RAM(SRAM)在1970年引入，并且提供高带宽和低存取时间。SRAM通常用于存储器等级中的较高等级中的高速缓冲存储器以提升性能。因为针对存储器阵列中的每个比特需要6个晶体管，SRAM的缺点是成本。DRAM比SRAM便宜很多，因为其每比特只需要一个晶体管和一个电容器，但是具有较低的速度。在过去的十多年来，已经显著地改进了DRAM设计。已经向先前异步的DRAM接口添加时钟信号以减小在脉冲串传送期间存储器控制器的同步开销。这种存储器称为同步DRAM或简称为SDRAM。双数据率(DDR)SDRAM特征在于显著更高的带宽，因为其在时钟的上升沿和下降沿两者上均传送数据，有效地使带宽加倍。这些DDR存储器的第二代(称为DDR2)在设计上非常类似，但是缩放为更高时钟频率和峰值带宽。

请求者可以通过以下一个或更多参数来详细说明：存取方向d(读取/写入)、最小请求的数据带宽(w)、最大请求字的大小(σ字)、最大等待时间(1)和优先级(c)。

就此而论，可以认为CPU是请求对于存储器的读取存取的第一请求者和请求对于存储器的写入存取的第二请求者。可以认为动态存储器是请求者本身，因为其要求其内容的刷新时间。其他存储器可以同样地请求用于他们内容的周期性纠错的时间。一些请求者可能具有实时要求而另一些不具有实时要求。可以区分不同种类的通信量，相对于带宽、等待时间和抖动具有不同的要求。诸如来自CPU或DSP的高速缓冲存储器失败的存储器请求之类的非实时通信量是无规律的，因为这些请求可能实质上出现在任意时间，并且曾经用于包括完整的高速缓冲存储器线的传输。在等待高速缓冲存储器线从存储器返回的同时，处理器将停止，因此需要最低可能的等待时间(latency)以防止浪费处理功率。这种通信量要求良好的平均吞吐量和较低的平均等待时间，但是只要其不频繁出现，对于最差情况就几乎没有限制。

存在两种类型的实时应用：软的和硬的。软实时应用不具有绝对的服务合同(contract)。其遵循偶尔可以违反保证，因此本质上是统计的。嵌入式系统更关注硬实时请求，因为他们多为特定应用，并且被裁剪为总是满足其规范。

考虑进行音频/视频解码的机顶盒。请求和响应是可预测的，并且周期性地重复。这种类型的通信量要求得到保证的最小带宽，以获得其目的地的数据。在这种类型的系统中低等待时间是有利的，但是更重要的是等待时间是恒定的。因为在接收机中要求缓冲器以防止引起断断续续的回放的下溢(underflow)，等待时间的变化(通常称为抖动)引起问题。为此原因，这种类型的系统要求低限制的抖动。

将控制系统用于监测和控制潜在的临界系统。考虑核电站中的控制系统。在太迟之前将传感器输入递送至调整器，以便防止潜在的危险情况。该通信量要求得到保证的最小带宽和小的最差情况等待时间，但是容忍抖动。

上述CPU、机顶盒和控制系统示出了请求的范围，并且可以将良好的存储器方案设计用于这些系统的任意一个。当全部这些通信量类型不得不通过相同的系统解决似时困难增大，特别是在复杂的当代嵌入式系统是全部通信量类型的情况下是同时存在的。这种系统请求灵活的存储器解决方案以解决所述多样性。可以将带宽指定为毛带宽或净带宽，这进一步地使请求变复杂。毛带宽是不考虑存储器效率的峰值带宽量。毛带宽保证转换为保证请求者许多存储器时钟周期，这正是大多数存储器控制器所做的。如果所述通信量不是性能良好的，或者如果存储器控制器无效，则净带宽只是毛带宽的一部分。净带宽是应用在它们的规范中所请求的，并且与实际数据率相对应。提供净带宽保证的困难在于所述通信量如何存取存储器的细节需要是众所周知的。

可以辨别两种类型的存储器控制器：静态的和动态的。这些类型的控制器具有不同的性质。静态存储器控制器遵循硬件方案以向请求者分配存储器带宽。静态存储器控制器的主要优点是可预测性；它们提供保证的最小带宽、最大等待时间和抖动限制，这在实时系统中是非常重要的。因为是可预先计算的，该方案如何存取存储器是众所周知的。这使得静态存储器控制器可以提供净带宽保证。

然而，因为如果向系统添加额外的请求者，所述方案不得不重新计算，静态存储器控制器不会非常好地缩放。计算方案的难度也随着请求者个数的增加而增长。静态存储器控制器适用于具有可预测请求者的系统，但是不能向间歇的请求者提供低等待时间。由于缺乏灵活性，动态工作量不会很好地处理，并且导致显著的浪费。

动态存储器控制器在运行时间作出决定，并且可以使它们的行为与通信量的性质相适应。这使得它们非常灵活，并且甚至对于动态工作量也允许它们实现低平均等待时间和高平均吞吐量。将所提供的请求进行缓冲，并且一个或更多仲裁决定向哪一个服务。仲裁可以是简单的具有静态优先级，或者可以包括利用多个通信量级别的复杂基于信用的方案。尽管这些仲裁器可以使得存储器效率付出某种代价。复杂的仲裁器较慢，要求很多芯片面积并且难以预测。动态存储器控制器的不可预测性使得非常难以提供硬实时保证，并且计算有用的最差情况等待时间限制。存储器如何存取极大程度的依赖于所提供的通信量。然而，适用于存储器存取的时钟周期的实际可用个数依赖于各种因素，例如存储方向从读取变为写入的频率、对于DRAM激活新行的次数。因此，这些控制器不能通过构建来提供对净带宽的保证。用于得到这种保证的方式是试图模拟最差情况通信量并且整体分配毛周期以得到安全裕度(margin)。如果最差情况是已知的则整体分配的量可能是严格的，而如果对于硬实时系统所得到的保证是足够的，则可以对其进行商议。

发明内容

本发明的目的是提出一种存储器控制器和方法，用于调度存储器存取，可以确保对于带宽的最小限制和对于等待时间的上限，同时也是足够灵活的。

该目的是通过如权利要求1所述的本发明的方法实现的。

该目的是通过如权利要求2所述的本发明的存储器控制器实现的。

在根据本发明的存储器控制器和方法中，与静态存储器控制器设计类似的预定后端调度定义了如何存取存储器。当存取模式是固定的时，同样可用于请求者的净带宽的总量是固定的。通过提供净带宽的硬实时保证的分配方案将该调度中的净带宽分配给请求者作为信用。然而与静态存取控制器中的过程相反，通过增加了设计灵活度但是提供了理论最差情况持续限制的动态前端调度器来提供存储器存取。依赖于对于公平、抖动限制和缓冲进行的折衷，可以从诸如循环复用之类的各种前端调度器中进行选择，提供前端调度方案的仲裁政策遵照固定的后端调度。

在后端调度的计算中，考虑存储器请求者在带宽方面的预定或长期需求。然后，积累针对每一个存储体的读取和写入方面的总需求和其他需求，例如在存储器是DRAM情况下的刷新需求，或者在例如闪速存储器的情况下的定期的纠错需求。在这一阶段，不考虑请求的来源，只有针对调度而选定的时间窗口内的存储器存取的每一个种类的总带宽是相关的。在已经积累了针对每一个存取种类的带宽需求时，优选地，确定带宽需求的总数是否小于净可用带宽。如果不是这种情况，不能找到正确的调度，并且不得不考虑另一个硬件结构，或者不得不接受不能满足全部需求。

所述方法的第一阶段可以静态地执行。即，可以将后端调度与系统的设计一起定义，并且例如可以将后端调度存储在ROM中。后端调度可以基于存储器请求者的预定性质和需求，例如针对等待时间和带宽所需要的限制，以及在读取和写入请求方面的请求者行为等。将针对每一个存储体的读取和写入方面的总请求进行积累，并且确定这些存取按照哪种顺序进行更有效，在该阶段忽略请求的来源。

可选地，所述存储器控制器可以易于允许用户定义后端调度。

可选地，可以动态地执行根据本发明的方法的第一阶段。例如，所述调度器可以按照规则的时间间隔更新所述后端调度以使其适应于所观察到的请求者行为。

优选地，所述调度是周期性地重复的基本存取模式。可以相对容易地计算这种调度。

附图说明

参考附图详细描述这些和其他方面。其中：

图1示意性地示出了包括通过互连装置与存储器子系统相连的各种请求者的系统；

图2详细地示出了存储器子系统，具有本发明可应用的存储器控制器；

图3示出了存储器布局；

图4示出了简化的DDR状态图；

图5示出了存储器映射的第一示例；

图6示出了存储器映射的第二示例；

图7示出了存储器映射的第三示例；

图8示意性地示出了在后端调度中所应用的读取、写入和刷新组；

图9示意性地示出了基本读取组；

图10示意性地示出了基本写入组；

图11示意性地示出了基本刷新组；

图12示意性地示出了在读取和写入组之间切换时招致的成本；

图13示出了其中按照任意顺序调度存储器脉冲串的调度示例；

图14示出了其中请求者具有滑动分配窗口的调度示例；

图15示出了具有不同读取/写入混合的四个服务时间段的调度；

图16示出了其中在后端调度的一个循环期间执行服务时间段的整数次数的调度；

图17示出了在后端调度的整数次循环中执行服务时间段的调度；

图18示出了针对交错的存储器映射的调度；

图19示出了用于计算后端调度的方法；

图20示出了在用于读取和写入的后端调度中的最差情况位置；

图21示意性地示出了根据本发明的前端调度器；

图22示意性地示出了其中服务各种类型的请求者的顺序。

图23示出了提供给存储器知晓(memory-aware)系统中的请求者的累积带宽；

图24示出了表示本发明第一模拟实施例中的请求者体验的等待时间的关键图；

图25示出了针对另外实施例中的请求者体验的等待时间的关键图；

图26示出了针对另外实施例中的请求者体验的等待时间的关键图。

具体实施方式

这里所述的更详细的实施例进一步阐明本发明具体涉及同步DRAM。然而，本领域的普通技术人员将应该理解，本发明在使用存储器的其他系统中也是有用的，其中所述存储器的效率依赖于对存储器的存取模式。

所考虑的系统由一个或更多请求者1A、1B、1C组成。请求者1A、1B、1C通过诸如直接线(direct wire)、总线或片上网络之类的互连装置2与存储器子系统3相连。这如图1所示。

存储器子系统3包括存储器控制器30和存储器50，如图2所示。存储器控制器30包括如图所示的多个信道缓冲器。每一个请求者1A、...、1C经由输入31A、31B、31C与请求缓冲器32A、32B、32C相连，并且经由输出40A、40B、40C与响应缓冲器39A、39B、39C相连。这些缓冲器提供了时域交叉，使得存储器控制器可以按照与互连装置不同的频率操作。本领域普通技术人员应该理解的是，存储器控制器不需要物理上分离的输入以及物理上分离的输出，例如请求者1A、1B、1C可以共享总线。同样地可以共享缓冲器，具有用于与各种请求者有关的请求或响应的分离的地址范围。请求者通过连接与存储器50通信。连接是双向消息流，具有将请求者与存储器控制器中相应的缓冲器相连的请求和响应信道。在使用情况规范中详细规定了请求者的通信量特征和期望的服务质量水平。倘若存在可用的足够资源，则存储器控制器的准入控制接受请求者的服务合同。然后，只要请求者根据所述规范行动，就会保证履行所述请求。双向数据路径37至存储器50的第一部分经由选择单元33与输入缓冲器32A、…、32C相连。仲裁器35控制所述选择单元。存储器50的输出经由双向数据路径37的第二部分与取消选择单元38相连。取消选择单元38受到仲裁器35的控制，以选择性地向输出缓冲器之一提供经由双向数据路径的第二半部分接收到的数据。

接下来假设允许请求者读取或写入，但非两者。如同在[8]中所看到的，该分离是不常见的。请求者通过发送请求与存储器通信。将请求在请求信道上发送，并且将其存储在指定的请求缓冲器中直到其受到存储器控制器的服务为止。在读取请求的情况下，将响应数据存储在响应缓冲器中直到其在响应信道上返回为止。请求缓冲器可以包含针对命令数据(读取或写入请求)、存储器地址和请求长度的字段，在写入命令的情况下包含写入数据。存储器控制器按照先到先服务(FCFS)的顺序对请求缓冲器中的请求进行服务，因此提供了每个连接中的连续的连贯性，假设这是互连装置所支持的。没有在不同的连接之间提供同步或依赖性跟踪，并且必需另外地提供。

考虑信道缓冲器模型的这种体系结构，可以看出，可以将存储器子系统中的请求的等待时间定义为四个分量的总和：请求队列等待时间、服务等待时间、存储器等待时间和响应队列等待时间。为了本申请的目的，仅考虑服务等待时间，因为这个特征反映出存储器控制器如何对存储器进行调度。然而，服务等待时间与互连装置和具体存储器件的定时无关。更具体地，从请求处于请求队列的头部的时刻直到最后的字离开队列为止来测量所述服务等待时间。

现代DRAM具有三维布局，所述三维是存储体(bank)、行和列。存储体在某个方面与矩阵类似，其在行和列中存储多个字大小的元素。所述存储器布局在图3中描述。

在DRAM存取时，将地址解码为存储体、行和列地址。

存储体具有两个状态：空闲和激活。在图4中示出了简化的DDR状态图。通过激活命令存储体从空闲状态激活，所述激活命令将所请求的行加载到读取放大器，也称为行缓冲器。每一个存储体都具有行缓冲器，用于对最近使用的行进行高速缓存。一旦激活了存储体，可以向行缓冲器中的列发出诸如读取和写入命令之类的列存取。发出预充电命令以使存储体返回空闲状态。这将缓冲器中的行存储回存储器阵列中。行也称为页，所述页取决于其是否存在于行缓冲器中而打开或闭合。将对于闭合页的存储器存取称为页错误。

在4或8个字的脉冲串中进行读取和写入。将打开的页划分为具有脉冲串尺寸的唯一可寻址的边界段，所述脉冲串尺寸在初始化时在存储器中进行编程。这限制了脉冲串的可能的起始地址的集合。

许多系统经历了存储器存取中的空间局域性(locality)，这意味着后继存储器存取的目标存储器地址通常彼此临近。因为DDR2存储器件中的典型行尺寸是1KB，因此常见的是，若干读取和写入命令将目标定为已激活的行。

作为上述泄漏的结果，为了不丢失(loose)数据，不得不定期地刷新DRAM中的全部行。这是通过发出刷新命令实现的。每一个刷新命令实现了刷新存储器行。对于较大的器件，刷新命令需要更多时间，引起比较小器件更多时间的刷新。

在发出刷新命令之前，不得不将全部存储体预充电。在表1中总结了所讨论的SDRAM命令。

表1：一些SDRAM命令

SDRAM命令	描述
		无操作(NOP)	忽略全部输入
激活(ACT)	打开特定存储体中的激活行
		读取(RD)	向激活的行初始化读取脉冲串
写入(WR)	向激活的行初始化写入脉冲串
		预充电(PRE)	关闭特定存储体中的激活行
刷新(REF)	开始刷新操作

作为示例，考虑在DDR2参考文献[9]中描述的256Mb1(32M×8)DDR2-400 SDRAM芯片。所考虑的SDRAM芯片具有总共4个存储体，每个存储体具有8192行以及每行1024列。这意味着存储体编号的物理地址需要两个比特，对于行编号是13，对于列是10。页尺寸是1KB。

这些芯片具有8比特的字宽，但是通常将若干芯片进行组合以创建具有更大字宽的存储器。将如何将芯片组合在存储器模块上称为存储器配置。例如，当将这些芯片中的四个平行放置，所述存储器模块具有256Mb*4＝128MB的容量以及32比特的字宽。该特定存储器以200MHz的时钟频率运行，对于该特定结构导致200*2*32/8＝1600MB/s的峰值带宽。

在一个时钟周期期间总是发出命令，但是所述存储器具有非常紧密的定时限制，所述限制定义了不同命令之间的所需要的延迟。在规范中找到所述定时。将最重要的在表2中总结。

表2：针对DDR2-400 256Mb的一些定时参数

参数	时间(ns)	描述
			tCK	5	时钟周期时间
tRAS	45	激活以预充电命令延迟
			tRC	60	激活以激活命令延迟(相同存储体)
tRCD	15	激活以读取或写入延迟
			tRFC	75	刷新以激活命令延迟
tRP	15	预充电以激活命令延迟
			tRRD	7.5	激活以激活命令延迟(不同存储体)
tREFI	7800	平均的刷新以刷新命令延迟
			tWR	15	写入恢复时间

多存储体(multi-bank)结构的主要优势是对于不同存储体的命令可以按照流水线的方式而组织。在将数据传送至存储体或从存储体传送数据时，可以用针对随后请求的另一行来预充电和激活其他存储体。表示为存储体准备的该过程可以节省相当多的时间，并且有时完全隐藏了预充电和激活延迟。

当今天的嵌入式系统考虑存储器效率时，其具有较高的要求。这是正常的，因为低效的存储器使用意味着不得不使用更快的存储器，这更加昂贵并且消耗更多的功率。这里将存储器效率e定义为传送数据期间的时钟周期数S0和时钟周期总数S的比率，因此：

e＝S0/S    (1)

各种因素对于引起不会在每一个周期期间传输数据有贡献。将这些因素称为低效率的来源。最重要的因素是刷新效率、数据效率、存储体冲突效率、读取/写入效率和命令冲突效率。这些因素的相对贡献依赖于所使用的存储器的类型。对于动态存储器，定期刷新是低效率的来源。因为在发出刷新命令之前不得不对全部存储体进行预充电，刷新所需的时间依赖于存储器的状态。该规范声称必须每t_REFI平均进行一次。对于全部DDR2器件是7800ns。平均刷新间隔允许推迟但不是省略刷新命令。

可以将刷新推迟直到当必须发出8个刷新命令时的最大值9*t_REF1为止。当调度DRAM命令时推迟刷新命令是有用的，并且有助于摊销预充电全部存储体的成本。因为从存储器器件的规范中得到平均刷新间隔、时钟周期时间和刷新时间，刷新效率相对易于量化。另外，刷新效率是通信量无关的。对DDR2-400上的全部存储体进行预充电所需的最差情况时间是10个周期。这在作出刷新的决定之前的一个周期激活存储体的事件中发生。将存储器器件的刷新效率e_refresh如公式2所示地计算，其中n是连续的刷新命令的个数，t_pall是对全部存储体进行预充电所需的时间。必须将所述定时转换为时钟周期以便获得准确的等式。

$e_{\mathrm{refresh}}=1-\frac{1}{t_{\mathrm{REFI}}\·n}\·(t_{\mathrm{RFC}}\·n+t_{p\_\mathrm{all}}),n\∈[1..8]---\left(2\right)$

对于上述DDR2-400，刷新效率几乎是可忽略的，对于单独的刷新命令为大约98.7％。刷新效率随着更大和更快的器件变得更加显著。对于4GbDDR2-800器件，刷新效率下降到91.3％。然而，对于减小刷新的影响没什么可作的，除了试图当存储器空闲时对其进行调度。

因为将存储器划分为具有已编程脉冲串大小的段，所以脉冲串不能开始于任意字。因此，当请求针对未对齐(unaligned)数据的存储器存取时，必须将包括所述未对齐数据的段整体地写入或读取。这减小了发送的期望数据的总量。效率损失随着越小的请求和越大的脉冲串尺寸而增加。该问题通常不会通过存储器控制器解决，因为最小脉冲串尺寸与存储器器件相关并且数据对齐是软件的问题。

当脉冲串所定位的列不处于打开的页中时，不得不对存储体预充电并且激活以打开所请求的页。如表2所示，如果连续的读取或写入命令试图存取相同存储体中的不同页，则在面对存储体的连续的激活命令之间存在最小延迟，导致潜在的严厉惩罚(penalty)。其影响取决于通信量、目标存储器的定时以及所使用的存储器映射。

该问题可以通过重新安排脉冲串或请求来解决。智能通用存储器控制器配备有预测(look-ahead)或重新安排缓冲器，提供与不远的将来进行服务的脉冲串有关的信息。通过在缓冲器中查找，所述控制器可以检测并且可能通过请求的重新安排防止存储体冲突[2、8、10、15、17]。该机制工作地足够好以完全地隐藏了所引入的额外等待时间，假定存在面向缓冲器中不同存储体的脉冲串。该解决方案非常有效，但是增加了请求的等待时间。重新安排没什么困难。如果重新排列请求中的脉冲串，必须重新组装所述脉冲串，这要求额外的缓冲。如果在请求之间进行重新安排，则会出现写入后读取、读取后写入、和读取后写入的风险，除非紧密地监测依赖性。这要求额外的逻辑。

SDRAM受到当切换方向时的成本问题，即从写入到读取或从读取到写入。当将双向数据总线反转时，不得不发出NOP命令，导致丧失的周期。当从写入到读取或从读取到写入而切换方向时，丢失周期的个数不同。可以优先读取后读取以及写入后写入来改进读取/写入效率[2、8]，然而这导致更高的等待时间。

即使DDR器件在时钟的上升沿和下降沿两者处传送数据，每一个时钟周期也只能发出一次命令。结果，当传送连续的读取或写入脉冲串时，命令总线上可能没有足够的空间以发出所需的激活和预充电命令。这导致当由于页故障而不得不推迟读取或写入脉冲串时出现丧失的周期。对于8个字的脉冲串尺寸，必须每四个时钟周期发出新的读取或写入命令，使得命令总线在75％的时间对于其他命令是空闲的。对于四个字的脉冲串尺寸，在每二个周期发出读取和写入命令。第一代DDR模块支持大小为2的脉冲串。因为不会发出其他命令，不可能长期地维持连续的脉冲串。可以利用自动预充电来发出读取和写入命令，导致在完成传送之后的最早可能时刻对存储体预充电。这节省了命令总线上的空间，并且当下一个脉冲串以闭合的页为目标时是有用的。估计该命令冲突效率在95％～100％的范围中，使得几乎没有效率低的明显来源。

存储器控制器是系统和存储器之间的接口。普通的存储器控制器由四个功能块组成：存储器映射模块、仲裁器、命令发生器和数据路径。

存储器映射模块执行从请求者所使用的逻辑地址空间到存储器所使用的物理地址空间(存储体、行、列)的转换。

针对使用5比特地址的存储器映射示出了三个示例。在图5中观察到的第一存储器映射将连续的地址映射到相同的存储体。通过将两个最高有效位解码为存储体编号，该映射确保了在切换存储体之前在列和行上进行反复(iteration)。因为确保了预定义地址间隔中的全部通信量命中(hit)相同的存储体，当进行分割以将IP的行为彼此隔离时连续的存储器映射是有用的。该映射的缺点是大量请求可能命中页的末端，导致页故障。

图6中的存储器映射把全部四个存储体上由两个存储体所组成的对中的连续地址进行交错(interleave)。因为大量请求在全部存储体上交错，一同消除了页故障的风险，所以交错的存储器映射具有优点。该映射的底侧是，需要最小脉冲串长度以隐藏激活和预充电的等待时间。当假设脉冲串尺寸为2对于存储体的预充电和激活(如果在连续的存取之间需要)来说足够的条件下对存储体进行交错时，该特定映射是有用的。可以针对不同区域使用多个存储器映射。例如，图7中的存储器映射具有两个区域。第一个覆盖了头两个存储体，而第二个覆盖了两个余下的存储体。第一区域将地址顺序地首先映射至存储体1，然后映射至存储体2(如图5所示)。第二区域改变存储器映射以提供对于存储体2和3的交错存取。这些存储器映射不会重叠，但是仍然设法使用整个物理存储器。

再次参考图2，仲裁器35或调度器决定什么请求(或者脉冲串，依赖于粒度(granularity)水平)接下来将存取存储器50。该选择可以依赖于请求的使用期限、针对所述请求者已经服务的通信量、以及各种其他因素。

在仲裁器35已经选择了用于服务的请求之后，需要产生实际的存储器命令。将命令发生器36设计用于以诸如SDRAM之类的特定存储器体系结构为目标，并且利用针对诸如DDR2-400之类的特定存储器器件的定时来编程。该模块性有助于使存储器控制器适用于其他存储器。命令发生器36需要保持存储器状态的跟踪，以确保不会违反定时。将双向数据路径37配置用于与存储器50的实际数据传送。数据路径37与调度器35相关，由于反转该数据路径37方向的事实，即从读取到写入的切换，导致丧失的周期。

可以在存储器控制器30内辨别两个逻辑块，即前端和后端。认为存储器映射模块34和仲裁器35是前端的一部分，而命令发生器36是后端的一部分(参见图2)。在根据本发明的存储器控制器中，通过动态前端调度器35对存储器存取进行仲裁，所述动态前端调度器35按照预定的后端调度来分配存储器50。

预定的后端调度使得存储器存取是可预测的，并且提供了有效的毛带宽到净带宽的转换。调度包括如图8所示的读取、写入和刷新组。读取和写入组包含针对存储器中的每一个组的最大脉冲串尺寸的存储器存取。将这些存取交错到组上，以便实现有效的流水线传输以及因此高的存储器效率。因为后端调度确定了关于存储器的存取模式，所以存储器效率是已知的，因此请求者可用于存取的净存储器周期数是已知的。可以将这些可用的存储器周期分配给请求者，并随后动态地调度，然而无需改变预定的存取模式。

存储器需要不时地刷新，因此必须在多个基本组之后调度刷新组。

因为已经消除或限制了一些前述的低效率的来源，后端调度产生了良好的存储器效率。例如，因为读取和写入组在组上交错，通过构造可以不发生组冲突，于是提供了针对组准备的足够时间。通过在后端调度中对读取和写入脉冲串一起分组来解决读取/写入效率。这限制了切换的次数。

必须针对由最小净带宽要求和最大等待时间组成的给定通信量规范来计算合适的后端调度。这要求确定在后端调度中的读取、写入和刷新组的个数和布局。所产生的所述组的顺序必须提供针对请求者指定的组以及读取和写入方向中的足够净带宽。对于请求者的带宽分配考虑了对于净带宽和最差情况等待时间的硬实时保证。最后，将后端调度中的脉冲串向系统中的请求者调度，考虑它们的分配和服务质量要求。这是动态地完成的，以增加灵活性。动态前端调度器可以按照几种方式实现，但是必须足够完善以传递保证，同时仍然足够简单以进行解析分析。

现在将更详细地描述后端调度的计算。

后端调度包括从存储器控制器的后端向存储器发送的命令的已产生序列。固定后端调度使得存储器存取是可预测的，于是允许确定性毛带宽到净带宽的转换。后端调度应该遵照针对读取和写入带宽以及请求者的最大允许等待时间的一组要求。后端调度可以针对不同的目的进行优化，例如存储器效率或低等待时间。后端调度由低级别块组成，包括读取组、写入组和刷新组。每一个组由多个存储器命令组成，并且可以取决于目标存储器而不同。

现在更详细地作出DDR2 SDRAM[9]的特定后端调度的计算。然而，基本原理相等地应用于其他SDRAM版本，例如SDR SDRAM和DDR SDRAM。在图9、10和11中示出了这些组。所述组由与表1类似的多个连续SDRAM命令组成。使得它们对于潜在目标为不同页的连续的读取和写入100％有效的唯一方式是在全部四个组上顺序地交错存储器存取，并且使用八个元素的脉冲串尺寸。较大的脉冲串尺寸提供对于相同组的连续存取之间的足够时间，以对另一行预充电和激活。缺点与数据效率有关。没有在八个字的边界上对齐的数据以及比选定脉冲串尺寸要小的请求导致显著的浪费。利用自动预充电发出全部读取和写入命令，以确保在最早可能的时刻对存储体预充电。这避免了命令总线上的竞争，并且使得所述组易于调度。

基本的读取组如图9所示。读取组由16个周期组成，并且在所有这些周期期间传送数据，使得组100％有效。

图10示出了基本的写入组。所述组横跨16个周期，并且在所有这些周期期间传送数据，恰好类似于基本读取组。

在发出刷新命令之前必须对全部存储体预充电。假设图11中所示的刷新组跟随着读取组，以更有效地以流水线的方式对存储体进行预充电。一旦已经发出了刷新命令，在所谓的刷新至激活延迟(tRFC)期间存在许多NOP命令，在发出新的基本组之前必须经过所述延迟。该特定的刷新组对于256MB DDR2-400期间是有效的；更大和更快的器件需要更多的周期来刷新。

后端调度由这些块的序列组成。如前解释的，成本涉及从读取到写入的切换方向中，反之亦然。这暗示着必须在读取和写入组之间(在这种情况下是2个)以及写入和读取组之间(在这种情况下是4个)添加NOP指令。这如图12所示。

DRAM中的每一行需要定期刷新以便不会丢失数据。这必须被考虑以使得存储器存取是可预测的，并且为此原因在调度的末端产生刷新组。刷新组必须通过对全部组预充电并且然后在一至八个连续的刷新命令之间发出而开始。如果刷新组在预定义的读取或写入组之后，可以使用所述组的预充电命令以使刷新组更短。在这里所述的实施例中，刷新组在读取组之后。按照这种方式，读取组将刷新组缩短了两个周期。延迟刷新的益处在于，在预充电全部存储体中所涉及的花销在大组上摊销。然而，延迟刷新并非没有缺点，因为这使得刷新组更长，影响了最差情况等待时间。取决于连续刷新的个数n，刷新组所需周期的个数t_ref在等式3中计算。

t_ref(n)＝8+15*n；n∈[1...8]    (3)

知道了刷新组长度t_ref(n)h和平均刷新间隔T_REFI，则确定了针对两个刷新之间的读取和写入组的最大可用周期数，如等式4所示。这有效地确定了后端调度的长度。

t_avail＝n.t_REFI-t_ref(n)  n∈[1...8]    (4)

后端调度由读取、写入和刷新组组成。现在将确定需要多少个读取和写入组以及这些组在后端调度中应该如何放置。这是在[8]中出现的普遍化，其中在切换方向之前只允许单独组的等价物。该方法对于较早的存储器工作良好，但是切换方向增加的成本使得该普遍化是必要的。读取和写入组的个数与系统中请求者的读取和写入请求有关。在现有的方法中，将其选择为对针对读取和写入所请求的总带宽进行求和，并且随后让在调度中的读取和写入之间所请求的比例通过这些个数确定的分数a来确定。该分数是通过等式5计算的，其中w_r(d)是返回请求者r在方向d上请求的带宽的请求函数。

(5)

确定多个连续的读取和写入组c_read和c_write以表示该比率并且组成基本组。c_read和c_write的所选值定义了所提供的读取/写入比率β。

$\mathrm{\β}=\frac{c_{\mathrm{read}}}{c_{\mathrm{write}}}---\left(6\right)$

基本组通过写入组后紧接着读取组并且添加有切换所需的NOP指令来定义。优选地，重复基本组直到在刷新前不再适合为止。重复的基本组的最大可允许个数k在等式7中计算，其中t_switch是从读取到写入以及再次回到读取的切换方向所需的NOP的个数。对于DDR2-400，t_switch＝t_rtw+t_wtr＝6个周期。t_group是读取或写入组所需的时间，对于DDR2-400都是16个周期。

$k=\left|\frac{t_{\mathrm{avail}}}{(c_{\mathrm{read}}+c_{\mathrm{write}})\·t_{\mathrm{group}}+t_{\mathrm{switch}}}\right|---\left(7\right)$

通常为了效率的原因，需要将具有相同方向的组顺序地放置。这消除了发出使所述组共同适合所需的额外NOP指令。然而在静态调度中，这种试探法(heuristic)只在特定程度上是有效的，因为由于等式7的非线性，较大的基本组可能不会相对于刷新很好地重复。这意味着可能将大组依次放置多次，但是在平均刷新间隔的末端之前，大量周期是未使用的，因为没有足够的附加时间可用于附加的基本组。尽管基本组同样是非常有效率的，这引起了过早地调度了刷新组，导致低效的调度。这特别是在如果下取整函数(floor function)的括号之间的比率刚好略微小于最接近的整数值的情况。该效应的影响随着更大的c_read和c_write而变大。

将全部组沿相同方向依次放置的问题在于，针对请求的最差情况等待时间显著地增加，因为在考虑特定请求的调度之前，可能存在沿干扰方向行进的大量脉冲串。请求者的最大等待时间限制了不会违反保证情况下可以依次放置的读取和写入组的个数。针对请求的最差情况等待时间取决于连续的读取和写入组两者的个数。这将在说明书的另外部分中更加详细地描述。

还应该考虑的是所述分数在没有非常大的分子或分母的情况下有时不能精确地表示。因为等待时间限制了特定方向上连续组的个数，显而易见的是对于某些读取/写入比率，存储器效率不得不为了较低的等待时间而折衷。

解决方案的总效率取决于两个分量。第一分量是由于有规律的无效率来源，如前所述，例如读取/写入切换和刷新，导致丧失的周期。第二分量涉及所提供的读取/写入混合β与所请求的a相对应的紧密度如何。在某些方面，第一分量在全部存储器控制方案中是重要的，但是第二分量对于这种方法是固有的。将在给出后端调度的正式定义之后更加详细地考虑第二分量。

对于目标存储器，后端调度θ通过三元组(n，c_read，c_write)来定义，其中n是在刷新组中连续的刷新命令的个数，c_read和c_write分别是基本组中的连续的读取和写入组的个数。

将后端调度θ的调度效率e_θ定义为通过调度提供的净带宽量S′_θ和可用毛带宽S之间的分数。

$e_{\mathrm{\θ}}=\frac{{S^{\′}}_{\mathrm{\θ}}}{S}---\left(8\right)$

在读取和写入组的所有周期中传送数据。只有在刷新周期期间以及当切换方向时不能传送数据。目标为特定存储器的后端调度的效率在等式9中表示。将所述等式写为两种形式，一种集中于时钟周期与数据传送的分数，另一种集中于周期与无传送的分数。

$e_{\mathrm{\θ}}=\frac{(c_{\mathrm{read}}+c_{\mathrm{write}})\·k\·t_{\mathrm{group}}}{((c_{\mathrm{read}}+c_{\mathrm{wreite}})\·t_{\mathrm{group}}+t_{\mathrm{switch}})\·k+t_{\mathrm{ref}}\left(n\right)}$

$=1-\frac{t_{\mathrm{switch}}\·k+t_{\mathrm{ref}}\left(n\right)}{((c_{\mathrm{read}}+c_{\mathrm{write}})\·t_{\mathrm{group}}+t_{\mathrm{switch}})\·k+t_{\mathrm{ref}}\left(n\right)}---\left(9\right)$

e_θ是表示毛带宽多好地转换为净带宽的度量。尽管这是相关联的数，总效率需要考虑调度中的组可能不完全与所请求的相对应。

条件a≠β导致针对读取或写入的过度分配。这对于混合效率e_mix具有负面影响，所述混合效率定义为所请求的和所提供的读取/写入比率之间的差。

e_mix＝|α-β|    (10)

将总效率e_total用作该应用中的效率度量，其中后端调度θ的总效率e_total定义为调度效率e_θ和混合效率e_mix之间的乘积。

分配方案确定如何在后端调度中分布脉冲串，以保证系统中的请求者的带宽要求。为了提供受保证的服务，分配方案不得不提供针对请求者的隔离，使得其被保护免受其他请求者行为的影响。公知为请求者保护的这种性质在实时系统中是重要的，以防止客户端的过询问(over asking)和使用另一个客户端所需的资源。通常，通过使用表示在准予另一个请求者的存取之前最大将服务多少个周期、脉冲串或请求的具有信用(credit)形式的当前值(currency)来完成保护。

在这里更详细地描述本发明优选实施例中分配方法之前，简单的参考带宽分配领域中的相关工作。Lin等人[10]在服务时间段中分配可编程个数的服务周期。这意味着分配毛带宽，但是该公开没有提供确定是否保证带宽的足够信息。在[17]中，在服务时间段中分配多个请求，只要请求的大小是固定的，则将其转换为毛带宽保证。

本发明目的在于分配和保证净带宽。在这里更详细所述的优选实施例中，通过保证每服务时间段的后端调度中的多个脉冲串，在比[17]中稍加精细的粒度水平上解决分配问题。这个稍加精细的粒度水平使得能够实现更宽范围的动态调度算法。

根据本发明的系统和方法保证在预定义的时间段期间，请求者获得对于存储器的特定量的净带宽Ar。这以等式11和静态调度的脉冲串而方便地表示。向请求者保证每p中的a_r脉冲串。这意味着向请求者分配可用带宽S′_θ的一部分，其由总带宽和后端调度的效率来定义。

$A_r=\frac{a_r}{p}\·{S^{\′}}_{\mathrm{\θ}}---\left(11\right)$

对于所分配的比率，使得无论如何不会向请求者的集合R分配比可用的更多带宽，意味着等式12必须成立。

$\underset{\∀r\∈R}{\mathrm{\Σ}}\frac{a_r}{p}\≤1---\left(12\right)$

优选地，在不选择使用特定的前端调度算法的情况下应该保证净带宽。为了不限制调度算法，应该允许按照任意顺序调度请求者，因为这使得利用调度算法的定义解决了等待时间和缓冲之间的折衷。为了实现这种情况，对于请求者的性质和所使用的调度算法进行以下假设。

全部请求者具有相等长度的服务时间段。

请求者可以使用任意脉冲串，与目的存储体和方向无关。

请求者r不能在p中得到多于a_r的脉冲串。

后一个假设不会应用于每一种情况。将在说明书的另一个部分中讨论如何放松该假设。这三个假设简化了调度，使得可以任意地进行。这是图13中所示的情况：可以将任意脉冲串在其分配中授予任意的请求者。

大多数调度器算法要求他们的性质(特别对于带宽保证)是有效的，使得请求者r被积压(backlogged)，即他们的请求队列不为空。这遵循以下事实：不会服务请求，除非所述请求是可用的。

请求者的服务时间段在图13中是对齐的。这是特别的情况，并且该性质不是所要求的。本分配方案不但允许服务时间段是未对齐的，而且允许是滑动的(sliding)。该概念在图14中解释。允许滑动服务时间段的优势在于：已经空闲的请求者受益于立刻的带宽保证，并且不必等待服务时间段重新开始，该延迟取决于调度的粒度和请求者的服务质量水平而潜在地很长。图14中所示的情况是具有以上相同先决条件而可调度的。请求者的服务时间段不会开始，直到存在针对调度的请求。因此，保证了请求者r在服务时间段中的a_r脉冲串。

当后端调度驱动存储器存取时，需要预先知道的是，请求者具有可用于存储体的组合以及时间段p中出现的方向的脉冲串。这个要求一般利用请求者可以使用任意脉冲串的假设来限定，与目的存储体和方向以及请求者被积压的要求无关。

对于服务时间段p的长度存在一些限制。假设服务时间段横跨整数个基本组。这防止了所提供的读取/写入混合不会在不同的服务时间段之间变化，并且保证在图15所示的两个方向中存在足够的脉冲串。该图示出了具有不同的读取/写入混合的四个服务时间段。可以将服务时间段横跨整数个基本组的假设在以下等式中表示。

p·x＝k；  p，x，k∈N    (13)

其中x是限定在后端调度的一次循环中时段p的重复次数的变量。可以将等式13表示为x需要是k的因子。该情况如图16所示。该图示出了当服务时间段处于比后端调度更精细的粒度水平时x的有效值。

否则，可以在比后端调度更高的粒度水平上选择p。

在这种情况下，p需要与后端调度的循环次数i相对应。

然后，等式14代替等式13。这种情况如图17所示。

p＝k·i    k，p，i∈N    (14)

以上假设确保了服务时间段具有特定的读取/写入混合。然而，该分配方案不会递送硬实时带宽保证。如果请求者改变方向，则事务(transaction)边界引起问题，如图12所示。

在所示情况中，向单独的请求者分配全部脉冲串。一旦读取脉冲串结束，不能使用多个脉冲串，因为他们处于错误的方向。这提示了关于请求者的另一个假设：请求者仅请求读取或者写入，但不是这两者。

进一步考虑具有图18中所示的交错存储器映射的情况。这示出了使用交错存储器映射引起不是任意可调度的情况。请求者不具有沿除了可用方向之外的任意方向行进的脉冲串，但是脉冲串的任意调度仍然可以导致浪费。如果r₀得到头三个脉冲串，那么没有人可以使用第四个脉冲串，即使没有请求者行为其也会被浪费。这可能导致一些请求者不能满足其保证。预先确定请求者将请求哪个存储体减轻了该问题。这可以使用两种存储体存取模式中的一种来实现：存储器知晓IP设计以及分割(partitioning)。可以将这两个方法都用于产生净带宽的硬实时保证。

存储器知晓IP设计在这里意味着利用目标存储器的多存储体架构来设计的系统。这可以包括使得每个存储器存取依次请求全部存储体，并且因此获得了优选地通过结构在存储体上平衡的系统。分割系统保证了可以调度请求，以及仅当没有积压请求者时才会浪费时隙。分割带来了一些挑战，并且影响解决方案的效率。这在说明书的其他地方讨论。

在[10、17]中，每一个服务时间段的周期和请求的个数手动地确定，并且在设备设置中进行编程。优选地是使该步骤自动化，并且提供从规范中得出这种编程的分配函数。

现在更加详细地考虑分配函数。首先，需要计算服务时间段中所请求的脉冲串的个数。为此目的，根据等式15计算每一秒中后端调度循环的次数，即通过计算一秒中可用时钟周期的个数并且将其除以循环后端调度一次所需的周期个数t_θ。

$n_{\mathrm{\θ}}=\frac{\frac{1}{t_{\mathrm{CLK}}}}{t_{\mathrm{\θ}}}---\left(15\right)$

随后，将每一秒中的带宽需求转换为每一个服务时间段的需求，其中w表示请求者的带宽需求，S_burst表示在存储器中编程的脉冲串大小(在这种情况下是8)，以及s_word表示字宽。等式16示出了如何计算该脉冲串需求。因为其没有舍入，也称作实数(real)需求。

$n_{\mathrm{real}}=\frac{\frac{\mathrm{\ω}}{C_{\mathrm{burst}}\·C_{\mathrm{word}}}}{n_{\mathrm{\θ}}\·x},n_{\mathrm{real}}\∈R^{+}---\left(16\right)$

优选地，需要分配给请求者的脉冲串的个数(实际需求)是请求者的请求大小的倍数。按照这种方式，在一个服务时间段中总是对请求进行服务，这对于最差情况等待时间限制有益。然而，这也增加了在分配期间的离散化误差的效应，因此减小了对于具有较短服务时间段或较大请求大小的系统的存储器效率。针对请求者r的实际需求在等式17中计算。

由于上述离散化误差，所请求脉冲串的实际和实数个数之间的比率是过分配的测量。

现在示出了如何计算调度解。调度解γ由通过后端调度θ和服务时间段x的定义形成的元组所组成。

如前所述，后端调度的非线性性质使其难以通过分析计算找到最优解。然而，可以通过在减小的搜索空间中的穷举搜索找到合适的解。因为所述算法计算了针对不同的使用情况离线(offline)的调度，其不具有实时要求，使得穷举检索是可行的选择。然而，所述检索空间被限制为所述算法的运行时间是可预测的。

所述算法包括在连续的刷新、读取组、写入组和可能的服务时间段(分别是n、c_read、c_write和x)个数上重复的四个嵌套循环。存储器支持的连续刷新的个数限制了刷新循环。对于全部DDR存储器，该个数是8。由于它们的相互依赖性和对分配的依赖性，读取和写入组循环更加难以限制。k中针对每一个解决方案的唯一因子的个数限制了可能的服务时间段。对于每一个解而计算效率，如说明书的其他地方所述，假定带宽分配是成功的并满足等待时间限制。如果在其他组中存在等待时间违反，除非在该方向中也添加了更多的组，搜索空间通过没有在一个方向添加另外的组的限制。如果读取和写入等待时间两者都受到相同解的违反，那么利用现有的刷新设置不能找到更好的有效解。这意味着如果不提供绝对最大值READ MAX和WRETE MAX，则等待时间计算限制了循环。通过针对一组有效解来选择最优解而结束所述算法。优化标准可以从存储器效率或最低平均等待时间到最有效分配而变化。

图19示出了用于计算后端调度解的算法。

在步骤S1至S4中，所述算法分别初始化了在后端调度的循环期间的连续刷新的个数n、连续的读取组的个数c_read、连续的写入组的个数c_write、以及服务时间段x的个数。例如，在1时初始化这些个数。

在步骤S5中，验证使用参数n、c_read、c_write、和x的后端调度是否遵循请求者的带宽和等待时间限制。如果是，则在步骤S6中存储该参数组。在步骤S7中验证是否已经针对参数n、c_read、c_write检查了全部服务时间段。如果不是，则在步骤S8中选择针对x的下一个值，并且重复步骤S5。

如果实际上已经检查了全部服务时间段，则在步骤S9中验证是否达到写入组的最大个数。如果不是，则在步骤S10中将写入组c_write的个数递增1，控制流继续进行到步骤S4。如果实际上达到了写入组c_write的最大个数，在步骤S11中验证是否也达到读取组的最大个数。如果不是，则在步骤S12中将读取组c_read的个数递增1，控制流继续进行到步骤S3。如果实际上已经达到了读取组的最大个数，在步骤S1 3中验证是否也达到了刷新的最大个数。如果不是，则在步骤S14中将刷新个数n递增1。如果实际上是，已经检查了全部可能的组合，算法通过在步骤S15中选择已存储的解中的最优解来完成算法。图19中所示的算法进一步地优化为具有两个附加步骤S16和S17。如果发现在步骤S5中使用参数n、c_read、c_write、x的后端调度不遵循请求者的带宽和等待时间限制，则在步骤S16中验证是否存在读取违反。如果是，则针对写入组个数的循环被打破，因为写入组个数进一步的增加将仅会进一步恶化读取等待时间。代替地，控制流继续进行到步骤S11。如果不存在针对读取等待时间的违反，则控制流继续进行到步骤S17。在步骤S17中，验证是否存在针对写入等待时间的违反。如果打破了针对读取组个数的循环，则读取组个数的进一步增加将仅会进一步恶化写入等待时间。代替地，控制流继续进行到步骤S13。如果不存在针对写入等待时间的违反，则控制流继续进行到步骤S7。

分配方案保证通过分配函数确定的多个脉冲串在每一个服务时间段服务于请求者。引入动态前端调度，在固定的后端调度和分配方案之间进行桥接。通过根据请求者的服务质量水平动态地分布已分配的脉冲串，增加了灵活性。

这里涉及到的调度算法的五个一般性质是：工作保持(conservation)、公平性、保护、灵活性和简单性。

可以将调度算法分类为工作保持或非工作保持。

工作保持算法当存在需要调度的事情时从不空闲。在非工作保持环境中，请求与合格(eligibility)时间相关联，并且直到此时才进行调度，即使存储器可能是空闲的。应该理解的是，工作保持算法产生了比非工作保持更低的平均等待时间，因为其实现了更高的平均吞吐量。非工作保持调度算法的优点是它们可以通过恰好及时地提供数据来减小缓冲，以及它们限制了抖动。在[18，19]中综述了多个工作保持和非工作保持调度算法。

公平的调度算法期望根据它们的分配按照平衡的方式服务请求者。完美的公平性通常在等式18中表示，其中s_k表示在半开的时间间隔[t0；t1)中给予请求者k的服务量。

t₁，t₂以及k，j∈R

$|\frac{s_k(t_0,t_1)}{a_k}-\frac{s_j(t_0,t_1)}{a_j}|=0---\left(18\right)$

根据等式18可以得出，完美的公平性只能在其中工作无限可分的系统(流体系统)中实现。在[13]中提出了针对这种系统的调度算法。如果所考虑的系统不是流体系统，则使用等式18中更一般化的表达。已经建议了以这种类型的公平性限制而工作的几种调度算法[3，4，13，16]。

$|\frac{s_k(t_0,t_1)}{a_k}-\frac{s_j(t_0,t_1)}{a_j}|<\mathrm{\&kappa;}---\left(19\right)$

根据等式19清楚的是，对于公平性κ的限制随系统中粒度水平而增加。因此可以在对SDRAM脉冲串而不是请求进行调度的系统中产生具有更高公平性的算法，因为这是对流体系统的更近逼近。在这一方面，更精细的粒度水平是有利的。公平性影响缓冲。信道缓冲器在到达和消费过程之间进行桥接。存储器控制器确定消费过程，但是假设到达过程是未知的。为此原因，必须假设这些过程具有最大相位失配。较高水平的公平性使得消费过程几乎不是脉冲串状的，引起缓冲器更均匀地消耗(drain)。这使得最差情况和平均情况缓冲更接近。

公平性对等待时间有二元影响。当对相同大小的请求进行交错时，最差情况等待时间保持相同而平均等待时间增加，因为针对请求的服务完成得更晚。该影响随着更精细的粒度而增加。如果请求具有不同的大小，公平性防止了较小的请求不被较大的请求阻塞，并且免于接收较高的等待时间以及不合理的等待/服务比率。

在本实施例中，分配方案提供了某种意义上的公平性：请求者在服务时间段中得到它们已分配个数的脉冲串，时间段越小公平性水平越高。前端调度器根据所分配的个数动态地指派存储器。

已经在采用FCFS算法的分组交换网络中观察到：主机可以通过增加其传输率来要求任意百分比的带宽。这使得故障或怀有恶意的主机影响了给予行为良好的主机的服务。Nagle[11]通过使用多输出队列并且按照循环复用(Round Robin)方式对其服务来解决该问题。这提供了隔离，并且保护了主机免受其他主机行为的影响。

保护在提供受保证的服务的系统中是基础的，并且为此原因将该性质内置到分配方案中，如前所述，并且与所使用的调度算法无关地提供该性质。过询问导致缓冲器填满，这可以引起有损系统中的数据丢失，或者引起流控制停止较少损耗系统中的发生器(producer)。任意一种方式都不会中断其他请求者的服务。

调度算法必须是灵活的并且满足通信量特性和性能要求。很好地识别出这些类型的通信量及它们的请求。许多存储器控制器通过引入通信量等级来处理这些不同的要求。尽管存储器控制器有很大不同，但选定的通信量等级非常类似，因为它们与公知的通信量类型相对应。标识出三种普通的通信量等级：

低等待时间(LL)

高带宽(HB)

最佳成就(BE)

低等待时间通信量等级目标在于对于等待时间非常敏感的请求者。在大多数存储器控制器中，该等级的请求者具有最高的优先级，至少与它们在其分配内部停留的一样长[10，12，16，17]。在Lin等人的[10]中他们试图使等待时间最小化使得该通信量等级内的请求预占(pre-empt)较低优先级的其他请求。这以存储器效率和可预测性为代价而减小了等待时间。一些存储器控制器放弃重新排序低等待时间请求，以便保持等待时间下降。

将高带宽等级用于流请求者。在一些系统中，他们对于等待时间没有限制，允许对该通信量等级中的请求重新排序，因此牺牲等待时间以有利于存储器效率。

在[10，16，17]中找到最佳成就的通信量等级，并且这些请求在系统中具有最低的优先级。他们不具有受保证的带宽或者对等待时间的限制，但是一旦更高优先级的请求者留下带宽时就对他们进行服务。重要的是切记，如果留下的带宽平均来说比在这种通信量等级中来自请求者的所请求速率低，则必须丢弃请求以防止溢出。

存在对于调度复杂性的限制。在硬件上实现并且高速运行必须是可行的。可用于仲裁的时间取决于所使用的服务单元的大小。在具有待调度的基本单元的该实现中是8个字的DDR脉冲串。这意味着每四个时钟周期需要重新仲裁，针对DDR2-400与20ns相对应，针对DDR2-667与12ns相对应。这提供了仲裁器速度的下限。

在硬实时系统中，最差情况性能是极度重要的，并且如果提供保证则必须是众所周知的。使用模块化方法来计算针对请求的最差情况等待时间。将最差情况等待时间计算为等待时间资源个数的总和。他们是：

在完成之前沿请求方向所需的脉冲串；

读取/写入切换和沿干扰方向行进的脉冲串；

干扰的刷新组；

到达/仲裁失配。

以下分析保持了一般性，使得其对于遵照分配方案所提出的公平性限制的全部调度算法都是有效的。可以通过检查具体的算法来推导更为紧密的限制。所述分析并非针对特定的服务质量方案。然而，其确实要求在所使用的优先级水平之间的部分排序的存在。

作为最差情况，假设请求在来自其他组的干扰最大化的时刻到达。对于请求的最差情况到达刚好在沿干扰方向行进的脉冲串的最后序列之前结束。在这种情况下，不但不能用的脉冲串的最大个数准备用于调度，且每一个请求具有在最差情况等待时间中包括的至少一个刷新。图20示出了针对读取和写入的后端调度的最差情况位置。首先，计算满足请求者r的σ字的请求所需的脉冲串的个数。将请求转换为脉冲串的个数σ_burst，例如8个字以匹配调度器的粒度。

现在考虑沿请求者的方向需要多少个脉冲串以保证请求完成。请求需要沿适当方向上的σ_burst个脉冲串以完成。因为没有假设调度算法的公平性，假设这些尽可能地晚。在该阶段，优先级开始行动。可以将请求者强制为等待沿相同方向具有相等或更高优先级的全部其他请求者。定义集合R’_r以包含所有这样的请求者。

因此在沿通过等式21计算的右方向的脉冲串个数n_left完成该请求。该等式计算除了a_r之外的R’_r中的全部请求者的组合分配，因为针对待完成的请求，r只要求τ_burst≤a_r个脉冲串。如果将请求者分割为特定的存储体，则所计算的值必须与存储体的个数相乘，因为n_banks脉冲串中仅有一个可用于对请求进行服务。

$n_{\mathrm{left}}=\left(\underset{\&ForAll;k\&Element;{R^{\&prime;}}_r}{\mathrm{\&Sigma;}}{a}_r\left(d\right)\right)-a_r\left(d\right)+{\mathrm{\&sigma;}}_{\mathrm{burst}}---\left(21\right)$

进行等待以获得沿右方向的n_left脉冲串的总数可以针对读取和写入而改变，因为连续脉冲串的个数c_read和c_write可能不同。等式23计算了沿干扰方向的脉冲串的时间损耗，包括通过等式22计算的切换的实际个数n_switches。因子c_interfering与沿干扰方向行进的连续脉冲串的个数相对应，并且因此等于针对写入请求的c_read和针对读取请求的c_write。

t_direction＝n_switches·(t_switch+c_interfering·t_burst)    (23)

如前所总结的，最差情况等待时间总是包含至少一个刷新组。对于后端调度的每次循环，存在附加的刷新组。由于针对服务时间段的限制，将刷新组的个数方便地以后端调度的持续时间和服务时间段的持续时间的比例x来表达。对事务产生干扰的刷新的个数在等式24中计算。

如果请求刚好在作出仲裁决定之后变为合格的，则会丧失直到重新仲裁的周期。该影响随着更长的仲裁时间段而增加，因此对具有存储器知晓存储体存取模式的系统(如等式25所示)比分割的系统(等式26)的影响更大。

t_mismatch＝4·n_banks-1    (25)

t_mismatch＝4-1＝3    (26)

现在通过组合各种等待时间来源来计算最差情况等待时间。这在等式27中示出，其中t_period是服务时间段中的周期个数，t_burst是脉冲串所需周期的个数；以及t_ref是刷新组中周期的个数。t_lat是以时钟周期表达的最差情况等待时间。

t_lat＝n_left·t_burst+t_direction+n_ref·t_ref+t_mismatch(27)

尽管存在影响最差情况等待时间的许多因素，处理请求的等待时间较大程度的受到n_left的影响。这意味着通过向敏感的请求者赋予高优先级并且通过仔细地选择存储体存取模式和调度算法来实现低等待时间。等式27和23还示出了可以通过使n_direction最小化来进一步减小等待时间。这是通过限制后端调度中的最大连续读取和写入组的个数并且以较低等待时间来交换较低存储器效率而实现的。

所提出的带宽分配方案的目的是在调度算法中尽可能少地设置限制。该分配方案表明所使用的算法必须在服务时间段中向每一个请求者提供所分配个数的脉冲串。没有关于向请求者指派其已分配个数的脉冲串的顺序有关的假设，提供了调度算法选择中的更大灵活性。

图21示意性地示出了根据本发明的算法。

在步骤S1中，前端调度器从请求者接收存储器存取请求。

在步骤S2中，确定所请求的存取的类型，例如写入/读取的方向、以及希望存取的存储体。

在步骤S3中，将所请求的存取的类型与根据后端调度针对各个时间窗口授权的存取类型进行比较。

在步骤S4中，产生包含输入请求的选择，所述输入请求具有针对相关的时间窗口的指定存取类型。

在步骤S5中，动态调度算法向在这些请求之一指派其余选择。然后，算法重复步骤S1以调度存储器的下一个脉冲串。为了清楚起见，按照时间先后顺序示出了步骤S1至S3。然而，本领域普通技术人员应该理解的是，这些步骤可以按照流水线的方式执行。

步骤S5可以通过传统的动态调度算法来执行，例如DifictRound-Robin(DDR)调度算法。该算法的两种变体在[16]中介绍。本实现基于所述算法之一，称为DDR+。将DDR+设计为具有高公平性水平的快速分组交换算法。所述算法在具有可变大小的分组的水平上操作，与在本模型中考虑的请求非常类似，并且易于修改为与脉冲串进行工作。在本实施例中采用两个通信量等级，低等待时间和高带宽。在本实施例中，假定每一个请求者具有硬实时保证，因此忽视了最佳成就通信量。

因为后端调度已经决定了存储体和特定脉冲串的方向，只考虑沿该方向行进的请求，因此组成了适合于调度的请求者的子集。将与DDR+的激活列表类似的列表针对每一个服务质量水平以FCFS顺序而维持。当请求到达空的请求缓冲器时，将先前空闲的请求者添加到相应的列表。取决于所应用的算法的两个变体，以两种方式之一来维持这些列表。第一变体在请求水平上进行调度，并且不从合格的子集中选择另一个请求，直到整个请求完成为止。当请求完成时，将所述请求者添加到列表底部，假定请求队列中存在更多的请求。所述算法的第二变体在脉冲串水平上操作，并且针对每个已调度的脉冲串将请求者移动至列表的底部。

第一变体减小了交错量，并且尽管最差情况等待时间保持相同，也会提供更低的平均等待时间。所需要的缓冲量与到达的脉冲串、消耗过程和最差情况等待时间成比例。对于这两个变体，到达过程和最差情况等待时间是未改变的，但是第一变体具有更多的脉冲串消耗，并且因此具有更大的最差情况缓冲需求。

按照FCFS顺序来检查列表，并且对第一合格请求者进行调度。

为了向较低的等待时间的请求者给出他们所请求的服务质量，他们总是首先得到服务。如果不存在积压的低等待时间请求者，或者如果他们用完了分配信用，选出高带宽请求者。该情况如图22所示。

所述算法的FCFS性质增加了超过所述分配方案的公平性，这意味着可以得出比针对更一般的情况而计算的更紧密的等待时间限制。

根据本发明的存储器控制器模型的模型以SystemC实现，并且使用Aethereal片上网络仿真器来进行仿真，如[5]中所述。使用电子数据表(spreadsheet)来逐一登记(specify)请求者，并且利用通信量发生器进行仿真。针对请求者r的通信量发生器以等式28中计算的时间段周期性地发送请求。

${10}^9\frac{{\mathrm{\&sigma;}}_r}{{\mathrm{\&omega;}}_r}---\left(28\right)$

适合所述规范的网络通过如[6]中所述的自动工具流来产生。将全部请求在作为受保证的服务通信量的网络上传输，所述受保证的服务通信量确保时间相关性能保证的有序无损递送。为了使等待时间测量与根据分析模型的结果可比较，强制使请求的服务不会停止(stall)，同时等待写入数据的到来。这是通过使写入请求适合于当其数据全部到达时的调度来完成的。

在表3中示出了在测试环境中使用的示例系统。该系统具有11个请求者，r₀，......r₁₀∈R，并且基于具有两个滤波器的视频处理平台的规范。对请求者的带宽要求进行缩放以实现针对具有1600MB/s的峰值带宽的32位DDR2-400存储器的合适负载。所指定的净带宽请求与峰值带宽的约70％相对应。同样，将具有三个请求者(r₈、r₉和r₁₀)的等待时间敏感CPU添加到系统。

表3针对示例视频处理系统的请求者的规范

请求者

方向

请求大

带宽

最大等

通信量

分割

		小[B]	[MB/s]	待时间[ns]	等级
							r0	写入	128	144.0	6000	HB	0
r1	写入	128	72.0	6000	HB	1
							r2	读取	128	144.0	6000	HB	0
r3	读取	128	72.0	6000	HB	1
							r4	写入	128	144.0	6000	HB	2
r5	写入	128	144.0	6000	HB	3
							r6	读取	128	144.0	6000	HB	2
r7	读取	128	144.0	6000	HB	3
							r8	读取	128	50.0	1300	LL	1
r9	读取	128	20.0	1300	LL	1
							r10	写入	128	50.0	1300	LL	1

负载和服务等待时间没有被积极地指定，以便使用分割和存储器知晓存储体存取模式两者而找到的解来比较结果。针对全部请求者将请求大小设定为128B(4个脉冲串)以与存储器知晓存取模式兼容。这对于经由共享的存储器的高带宽请求者之间的通信或者对于从等级2高速缓冲存储器中的高速缓存未命中(miss)导致的通信并非过度。

产生后端调度，提供满足请求者的等待时间限制的最有效解。

将示例系统如表3所示的分割。两个滤波器的每一个均具有四个请求者，用于读取和写入亮度和色度值。将一个读取和一个写入请求者分割到每一个存储体中，并且将CPU分割为具有最低负载的存储体。这假设CPU所需的数据位于存储体中，或者所述CPU与滤波器无关。

分割的系统难以在存储体上均匀地平衡，引起分配失败。该问题在附录B中讨论。针对分割的系统所计算的调度解如等式29所示。

γ_partitioned＝((1；8；6)；3)    (29)

根据该调度解，所述调度针对每一个刷新组具有8个读取组和6个写入组。后端调度的每一个循环重复服务时间段三次。

根据等式4和所使用的SDRAM的规范，后端调度的每一个循环的可用时间是1537个周期。因此，其满足等式7，重复基本组的次数k是6。因为针对每一个循环重复服务时间段3次，服务时间段与两个基本组相对应。因为将基本组重复6次，在调度中存在总数为(8+6)*6＝84个读取/写入组。每一个读取/写入组包含四个SDRAM脉冲串，导致调度中总共84*4＝336个SDRAM脉冲串。因此，在一个服务时间段中的SDRAM脉冲串的数量等于336/3＝112。在分配表中分配的脉冲串是SDRAM脉冲串，但是应该注意的是将他们以4的倍数来分配，因为所述组按顺序地存取全部存储体。

所计算的调度的效率是95.8％，意味着刷新组和读取/写入切换占据小于可用带宽的5％。这是有效的毛带宽到净带宽的转换。

基本组由8个读取组和之后的6个写入组组成。这对于规定的读取/写入比率不是非常好的匹配，这导致78.5％的混合效率。可以实现对于所请求比率的更接近的逼近，但是这具有不希望的效果。按照脉冲串大小的倍数进行的分配引起调度中的较小变化，显著地改变了请求者的分配。如果添加另一个写入组，则引起针对低等待时间请求者的最差情况等待时间的强烈增加。

将服务时间段确定为由三个基本组组成，导致针对后端调度的每一个循环的三个服务时间段。使服务时间段比调度更短，这降低了最差情况等待时间限制。如果去除读取组，则不再可能维持较短的服务时间段，因为这引起刷新前的重复个数k的变化。这再次引起等待时间需求失败。

较短服务时间段的结果是存在较少的脉冲串，由112代替336，以向请求者分配，增加了分配期间离散化误差的重要性。表4示出了带宽分配的结果。

表4针对分割的系统每个服务时间段分配的脉冲串

请求者	分配的脉冲串
		r0	12
r1	8
		r2	12
r3	8
		r4	12
r5	12
		r6	12
r7	12

r8	4
		r9	4
r10	4

该调度方案的分配导致分配711.6MB/s以覆盖针对读取所请求的574.0MB/s。将656.9MB/s分配给仅要求554.0MB/s的写入。这导致由于较大的21.3％离散化导致的总过分配。该系统的总效率在等式30中计算。

e_total＝e_θ·e_mix＝0.752＝75.2％    (30)

针对存储器知晓系统的调度方案看起来与分割系统的调度方案不同，如等式31所示：

γ_aware＝((2；10；10)；9)        (31)

基本组在该调度中较长，并且由10个读取和10个写入组组成。这导致了更少的读取/写入切换，对于存储器效率是有利的。

存储器知晓调度对于该特定使用情况更有效地结束，具有96.9％的调度效率。该系统的混合效率是96.5％，因为同样地许多读取和写入组公平地接近所请求的比率。请求组包含两个刷新命令，使得该调度近似为分割系统的两倍长。

服务时间段等于一个基本组调度，只产生80个脉冲串以针对该具体调度来分配。该分配如表5所示。

表5针对存储器知晓系统的每个服务时间段所分配的脉冲串

请求者	分配的脉冲串
		r0	8
r1	4
		r2	8
r3	4
		r4	8
r5	4
		r6	8
r7	8
		r8	4
r9	4
		r10	4

短的服务时间段对于分配不是较好的，因为离散误差变得非常显著。针对读取请求分配697.7MB/s，针对写入请求分配620.2MB/s。

该系统的总效率在等式32中计算。所述等式示出了所述效率显著高于存储器知晓系统，因为需要减小引起针对分割系统的混合效率的强烈减小的服务时间段。

e_total＝e_θ·e_mix＝0.935＝93.5％    (32)

现在，在仿真环境中提供对递送给请求者的净带宽的分析。仿真时间是10⁶ns，与大于后端调度的13000个循环相对应。在请求到达网络上的存储器控制器之前存在一些初始延迟，但是仿真时间比结果收敛所需的时间要多得多。

图23示出了提供给存储器知晓系统中的请求者的累积带宽。对于分割系统的结果未示出，因为他们如所期望的几乎相等。所述结果是在目标等级中结束的多条直线，如表6所示。所递送的带宽与所请求缩放以适合仿真时间很好地相对应。将最小差异归结于初始延迟。这意味着将净带宽递送实时地递送至请求者。

表6在10⁶ns之后递送给请求者的净带宽

请求者	净带宽[B]
		r0	143744
r1	71840
		r2	143872
r3	71936
		r4	143744
r5	143744
		r6	143872
r7	143872
		r8	50048
r9	20096
		r10	49920

如果进一步增加带宽请求，分割系统陷入问题。然而，存储器知晓系统随着高带宽请求者的负载增加而进一步地缩放。所述系统使用等式33中所示的调度解，以89.3％的毛负载适当地进行仿真，而等式时间限制保持相同。

γ_bandwidth＝((1；4；4)；1)    (33)

随后，在针对最小、平均和最大等待时间所观察到的值，针对两个系统考虑等待时间作为通过仿真模型中的请求者所体验。将所测量的最小和最大值与通过分析模型计算的理论限制相比较。主要通过脉冲串大小和存取模式来确定最小值。最大测量的等待时间取决于互连工具的到达过程、分配方案以及调度算法。感兴趣的是将该值与最差情况理论限制相比较，因为这表示最差情况出现的频率。应该保持平均等待时间较低，因为这影响系统的性能。该值也取决于到达过程、分配方案以及调度算法。

图24示出了针对在使用分割和请求水平调度的仿真实施例中观察到的等待时间的上述关键特征。将请求者分割为不同的存储体会影响等待时间，因为n_banks脉冲串中只有一个对于请求者是有用的，与优先级无关。这意味着对于大于单独的脉冲串的请求不能实现较低的最小等待时间。如表7中所示，许多请求者遇到了260nm的理论最小限制。最大测量值接近其理论限制(在括号中所示)，因为分割消除了仲裁中的一部分竞争。该具体系统中的存储体只具有一个读取和一个写入请求者，除了还覆盖(house)CPU的三个低等待时间请求者的存储体1。该图清楚地示出了分割给该存储体的请求者具有显著增加的最大等待时间，如理论限制所示。这也反映为增大的平均等待时间。还应该注意的是，针对这些请求者，平均值和最大值之间的差稍微更大。这反映了对于沿相同方向具有相等或更高优先级的其他请求者让他们的请求同时可用不是非常普通的。至于灵活性的考虑，显而易见的是该系统不会向敏感的请求者提供低等待时间。对此存在两个原因。首先，沿干扰方向的脉冲串会引起延迟，这对于该设计是固有的。其次，分割将优先级显著地限制为每个传统为基础，引起高优先级请求者变为分割给不同存储体的低优先级请求者。这是分割的限制。

表7使用分割和请求水平调度的最小、平均和最大等待时间。

在括号中可以找到分析限制。

请求者	最小[ns]	平均[ns]	最大[ns]
				r0	280.0(260.0)	718.8	1105.0(1105.0)
r1	260.0(260.0)	1048.7	2095.0(2095.0)
				r2	260.0(260.0)	537.8	945.0(945.0)
r3	260.0(260.0)	767.8	2095.0(2095.0)
				r4	280.0(260.0)	721.2	1105.0(1105.0)
r5	305.0(260.0)	724.9	1105.0(1105.0)
				r6	260.0(260.0)	539.3	945.0(945.0)
r7	260.0(260.0)	541	945.0(945.0)
				r8	260.0(260.0)	533	945.0(1265.0)
r9	260.0(260.0)	766.1	1265.0(1265.0
				r10	260.0(260.0)	656.5	1105.0(1105.0)

改变调度器以脉冲串级别而不是请求级别而工作，导致针对r8的平均等待时间的12.4％的增加。

从分割切换到存储器知晓设计相当程度上改变了结果，如图25所示。将请求者同时针对四个连续的脉冲串进行调度。因为请求者理想地立刻开始并被授予四个连续的脉冲串，所以利用这种存取模式的最小测量等待时间比分割系统中的更小。最大测量等待时间比理论限制小，如表8所示，因为并非系统中的全部请求者可以具有在共享的互连上同时可用的请求。与分割系统相比，平均等待时间对于全部请求者均较低。在高带宽和低等待时间请求者之间的平均等待时间中差别是可见的，示出了优先级对于使服务多样化是有用的。

表8使用存储器知晓IP设计的最小、平均和最大等待时间。

在括号中可以找到分析限制。

请求者	最小[ns]	平均[ns]	最大[ns]
				r0	80.0(80.0)	455.5	1160.0(1655.0)
r1	80.0(80.0)	445.3	1125.0(1735.0)
				r2	80.0(80.0)	454.6	1270.0(1735.0)
r3	80.0(80.0)	520.3	1305.0(1815.0)
				r4	80.0(80.0)	499.2	1205.0(1655.0)

r5	80.0(80.0)	429.8	1165.0(1655.0)
				r6	80.0(80.0)	534.9	1345.0(1735.0)
r7	80.0(80.0)	586.7	1405.0(1735.0)
				r8	80.0(80.0)	354.1	985.0(1255.0)
r9	80.0(80.0)	360.4	1065.0(1255.0)
				r10	80.0(80.0)	336	1085.0(1175.0)

该存储器知晓系统明显地能够递送比分割系统更低的等待时间。实际上，分割系统不能够提出具有比存储器知晓系统更低的等待时间的解。如果将优化标准改变为找到针对低等待时间请求者具有最低平均最差情况等待时间的解，则存储器知晓系统的潜力得以显现。所计算的调度解在等式34中示出。

γ_latency＝((1；2；2)；3)    (34)

该后端调度比前一个后端调度短，因为在刷新组中只包括一个刷新命令。基本组由两个读取组和两个写入组组成，这有助于以调度效率下降到90.0％为成本以助于最差情况等待时间。因为读取组的个数仍然等于写入组的个数，混合效率保持为96.5％。

服务时间段由三个基本组(或者112个脉冲串)组成，并且导致14.0％的过分配。图26示出了针对该实施例所测量的等待时间。

针对低等待时间请求者的测量和理论最差情况等待时间近似平分，如表9所示。新解决方案的紧密限制也影响了请求者的平均测量等待时间，其减小了30～45％。

高带宽请求者没有被新的优化标准考虑，导致增加的理论最差情况等待时间限制。

表9在等待时间优化的系统中使用存储器知晓IP设计的最小、平均和最大等待时间。

在括号中可以找到分析限制。

请求者	最小[ns]	平均[ns]	最大[ns]
				r0	80.0(80.0)	385.4	835.0(1940.0)
r1	105.0(80.0)	299.5	780.0(2210.0)
				r2	80.0(80.0)	439.3	1045.0(2210.0)

r3	80.0(80.0)	565.8	1125.0(2290.0)
				r4	80.0(80.0)	340.2	865.0(1940.0)
r5	80.0(80.0)	277	785.0(1940.0)
				r6	80.0(80.0)	358.5	1080.0(2210.0)
r7	80.0(80.0)	339.5	1235.0(2210.0)
				r8	80.0(80.0)	195.3	445.0(540.0)
r9	80.0(80.0)	252.4	415.0(540.0)
				r10	80.0(80.0)	200.3	425.0(460.0)

这些平均情况通过发送请求者不会在服务时间段p中得到大于a_r的脉冲串的要求并且通过分布系统中的松弛(slack)带宽进一步地改进。这是通过当对其已分配的脉冲串进行服务时将请求者降级为最佳成就优先级来实现的。当预算内没有请求者是合格的时，这些请求者按照FCFS顺序服务。该改进导致平均测量等待时间2.6％的平均减小。

根据本发明，在指派存储器之前定义了其中存取存储器的顺序。动态调度算法选择存储器请求之一，假定其遵循预定义的顺序。按照这种方式，可以精确获知可用于存储器的净带宽。然而，存储器控制器是灵活的，因为动态地调度预定义的存储器存取选项。注意：本发明的保护范围不局限于这里所述的实施例。可以将存储器控制器的一部分实现为硬件、软件或其组合。本发明的保护范围也不会受到权利要求中的附图标记的限制。词语“包括”不排除除了权利要求中所述的其他部分。元件中的词语不排除多个这些元件。形成本发明的装置可以按照专用硬件的形式或可编程的共用目的处理器来实现。本发明包括每一个新特征及其特征组合。

[引用文献]

[1]C.M.Aras et all.“Real-time communication in packet-switched networks.“InProceedings of the IEEE，volurne 82，pages122-139，January 1994.

[2]ARM.PrimeCell Dynamic Memory Controller(PL340)，r0p0 edition，June2004.

[3]Brahim Bcnsaou et all.“Credit-based fair queuing(cbfq)：a simple servicc-schedulingalgorithm for packet-switebed networks.IEEE/ACM Trans.New.9(5)：591-604，2001.

[4]A.Demers et all.“Anlylisis and simulation of a fair queuing algorithm.”In SIGCOMM

[89]：Symposium proceedings on Communications architectures & protocols pages 1-12.ACM Press，1989.

[5]Santiago Gonzalcz Pestaria et all.“Cost-performance trade-offs in networks on chip：Asimulation-based approach.“In DATE′04：Proceedings of the conference on Design.Automation and Test in Europe pages 764-769，Feb 2004.

[6]Kees Goossens et all.“Adesign flow for application-specific networks on chip withguaranteed performance to accelerate SOC design and verification.In DATE′05：Proceedings of the confenence on Design，Autemstion and Test in Europe，pages 1182-1187，Washington，DC，USA，2005.IEEE Computer Society.

[7]Francoisc Harmszc et all.“Memory arbitration and cache managiment in stream-basedsystems.”In DATE，pages 257-262，2000.

[8]S.Heitheeker，A et all.“A mixed QoS SDRAM controller for FPGA-based high-endimage processing.In IEEE Workshop on Signal Processing Systems，page 322-327.IEEE.Aug 2003.

[9]IEDEC Solid State Technology Association，IEDEC Solid State Technology Association2004，2500 Wilson Boulevard，Arlington，VA 22201-3834.DDR2 SDRAMSpecification，jesd79-2a edition，Jan 2004.

[10]Tzu-Chieh Lin et all.“Quality-aware memory controller for multimedia platform soc，InIEEE Workshop on Signal Processing Systems，SIPS 2003，pages 328-333，Aurust 2003，

[11]John B.Nagle.“On packet switches with infinite”IEEE Transactions onCommonications，COM-35(4)：435{438，April 1987.

[12]Clara Otero Perez et all.“Resource reservations in shared-memory multiprocessorSOCs.”In Peter van der Stok，editor，Dynamic and Robust Streaming In And BetweenConnected Consumer-Electronics Devices，Kluwer，2005.

[13]Abbay K. Parckh Robert G.Gallager.“A generalizcd proccssor sharing approach toflow control in integrated services networks：the single-node case.IEE/ACM Trans.Netw.1(3)：344-357，1993.

[14]E.Rijpkema.et all.“Trade offs in the design of a router with both guaranteed and best-effort services for networks on chip.IEEE Proceedings Computers and Digital Technique，150(5)：294-302，Sep 2003.

[15]Scolt Rixner et.All“Memory access scbeduling，“In ISCA 00：Proceedings of the 27thannual internatiounal sympusium on Computer architecture.pages 128-138.ACM Press，2000，

[16]M.Shreedhar and George Vargbese.Efficient fair queuing using deficit round robin.InSIGOOMM，pages 231-242，1995.

[17]Wolf-Dictrich Wober.“Efficient Shared DRAM Subsystems for SOCs-”Sonics Inc，2001.

[18]Hui Zhang.“Service disciplines for guaranteed performance service in packet-switching networks.”Proceedings of the IEEE，83(10)：1374-96，October 1995.

[19]Hui Zhang and Srinivasan Keshav.“Comparison of rate-based service disciplines “InSIGOOMM 91：Proceedings of the conference on Communications architccture &protocols，pages 113-121.ACM Press，1991.

Claims (7)

1.一种用于控制多个请求者对共享存储器的存取的方法，其中所述方法包括针对连续的时间窗口重复的以下步骤：

从不同的请求者接收存取请求(S1)；

确定所述请求所请求的存取的类型(S2)；

将所请求的存取类型与根据后端调度针对各个时间窗口授权的存取类型进行比较(S3)；

产生输入请求的第一选择，所述输入请求具有针对相关的时间窗口的指定存取类型(S4)；

从第一选择中动态地选择所述请求之一(S5)。

2.一种用于控制多个请求者(1A、1B、1C)对共享存储器(50)的存取的存储器控制器(30)，所述存储器控制器包括：

输入(31、...、31C)，用于从所述多个请求者接收对于所述存储器(50)的存取请求；

仲裁器(35)，用于根据包括基本组序列的预定后端调度，动态地准予所述请求之一。

3.根据权利要求2所述的存储器控制器，其中，所述存储器具有至少两个存储体，并且其中所述后端调度提供分离的时间窗口，用于按照交错方式对不同的存储体进行存取。

4.根据权利要求2所述的存储器控制器，其中，所述后端调度是固定的。

5.根据权利要求2所述的存储器控制器，包括用于允许用户对所述后端调度进行编程的装置。

6.根据权利要求2所述的存储器控制器，其中调度器具有用于动态地更新所述后端调度的装置。

7.一种数据处理系统，包括多个请求者(1A、1B、1C)、存储器(50)、以及根据权利要求2至6中任一项所述的控制器(30)，用于控制所述请求者对所述存储器的存取。

Images