基于规则的事件触发程序到硬件引擎的映射

理论计算机科学电子笔记124（2005）63-80www.elsevier.com/locate/entcs基于规则的事件触发程序到硬件引擎的映射器Car stenAlbre cht aandAndreasC. DinggbAI ITUTEOFCOMputeRENGINEERINGING，UNIVERSITYYOFLUUEBECK，D-23538LUEBECK，GermanybIBMZurichResarchLaboratory，CH-8804Ru？schlikon，Switzerl和摘要在本文中，我们描述了RERAL编译器。RERAL是一种基于规则的事件驱动路由算法语言。它用于配置常规网络的路由器，如并行计算机或计算机集群中的路由器。该语言结合了谓词逻辑派生的函数表达式和基于Petri网的并行性。高性能要求（路由决策不应超过几纳秒）意味着编译器中的复杂优化方法，特别是，注意程序层次结构，展开循环并将高级程序片段映射到可用的特定于应用程序的硬件单元。我们还指出了一个新的应用领域的概念，即管理的存储器接口的片上系统的带宽利用率增加。关键词：高级硬件建模，专用编程语言，规则库编译器1介绍计算机或嵌入式系统的许多组件使用固定硬件、处理单元和可配置硬件的组合。对于后者，已知有各种各样的配置方法，但其中大多数都需要详细了解架构，工具问题和硬件相关方面，如时序和资源约束。当系统必须由专家编程时，这项任务的复杂性是可以接受的。然而，需要更高的抽象层，以允许非专家有效地使用可编程硬件结构，并使专家更有效率。1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.07.01564C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63在本文中，我们介绍了一个基于规则的语言和它的工具环境，创建来描述路由算法的配置互连网络的并行计算机或计算机集群。第二个应用，最近被证明是感兴趣的，是在片上系统（SoC）中的存储器接口使用的中期控制。这两个应用程序的共同点是，• 应用领域的几个方面被组合，• 输入由无限系列的无关外部事件（如消息到达或片上CPU中的缓存未命中）形成，并且• 在可编程组件的反应中存在一些自由度。所有这些性质都反映在语言RERAL（基于规则的事件驱动的路由-一种出租语言）中。顾名思义，它结合了事件触发的并行计算和基于规则的表达式的描述能力。通过使用编译工具，可以将程序转换为可以应用于在几个时钟周期内执行复杂算法操作的VLSI可实现的规则评估引擎特别是，一个分层描述的路由决策是可扩展的，这样它可以被存储在一个小的片上存储器，和个人的评估需要只有一个访问这个存储器由于复杂的地址生成。在本文中，我们首先介绍了这两个应用领域的背景（第3节），重点是路由算法。特别是，我们激发了语言的模块化特征以及并行性和功能复杂性的必要方面。目标体系结构只是粗略描述，以便为语言的介绍（第4节）和编译过程的讨论（第5节）留出更多空间。具体来说，我们演示了如何使用基于统一的方法来提取规则评估引擎中硬件构建块的特定功能。如果此功能性分布在用户程序中的几个规则上，则必须由编译器检测以保持硬件独立性。2相关工作相关的学科是广泛的;基于规则的系统通常用于软件世界。然而，描述一个专门的硬件系统，只有低层次的描述与规则库的相似性在使用中。我们已经被告知，[ 15 ]中描述的工具我们没有验证这一点，想指出的是，我们的编译器执行许多特定于硬件的操作，C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6365通用工具可能没有涵盖的版本。一个例子是在没有乘法的情况下为高维数组生成寻址逻辑[9]。从给定的语法自动生成扫描器和解析器是一种成熟的技术，我们使用Eli[13]来实现这一目的。对于编译器的实现，我们使用了函数式编程语言Haskell的解释器Hugs [16]。该语言的模式匹配功能，用于处理复杂数据结构的丰富功能集，包括自动内存处理，提供了一个框架，在该框架中，编译器中所需的转换可以在高抽象级别上描述。Log/IC软件包中所使用的状态机的专有描述语言与非常基本的规则有一些相似之处。Neonetworks宣布了一款名为StreamProcessor的芯片，用于网络应用程序，据称可以在“超级计算机规模”上利用并行性，并有一个名为“规则处理器”的构建块。然而，有关这项技术的信息一直是保密的，该公司已经停业。关于并行计算机网络中的路由，Summerville et al. 在[18]中提出了位模式关联路由器的架构它们用一种伪语言来描述它们的路由算法，这种伪语言与RERAL中使用的基本模式非常相似目标硬件使用模式匹配电路阵列，它类似于三进制CAM（内容可寻址存储器）。由于在所提出的路由引擎中既没有专用的算术电路也没有其他专门的组件，因此只能执行简单的路由算法，而不会大量增加关联电路。在基于互联网协议（IP）的网络领域中，由于IP寻址的分层组织，路由规则很流行。因此，有许多处理规则的架构，它们将范围检查和IP地址中的前缀匹配与端口号的范围检查一个例子是[19]。由于执行了并行检查，因此硬件排序随允许的规则数量而变化。面向记忆的变体也在使用中，例如[17]。基于IP的路由需要动态更改规则集的选项，因此定义了规则集的映射在高抽象级别上，硬件中的表示必须非常有效地可计算。所有这些方法都对规则的结构施加了很大的限制，特别是它们限制了可以应用于变量输入的操作类型。此外，对于对一种类型的事件的反应，仅考虑一个规则集。规则的反应非常简单，例如在防火墙中的drop/non-drop决定这些限制阻碍了实施。66C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63高级算法，如将在下一节介绍的算法。3应用领域正如第1节所指出的，我们正在考虑两个应用领域：常规网络中的路由和SoC（如网络处理器）中的内存访问带宽管理规则网络使用具有高规则性的拓扑，例如网格或超立方体。它们是并行计算机，特别是PC集群的重要组成部分。规则性允许使用高级路由算法，• 允许扩展网络规模，而路由器的硬件成本几乎不变，• 根据链路或路由器负载，动态调整数据项通过网络的路径（自适应性），以及• 动态绕过故障路由器或链路（容错）。在[10]中给出了这些路由算法的良好覆盖和这类网络对于我们的目的来说，知道网络由链路和路由器组成（图1），并且在路由器处注入的数据通过链路以消息的形式传输到其他路由器，直到这些消息到达它们离开网络的目的地。路由器由地址标识，消息有一个包含目的地路由器地址的报头。有一种称为链路级数据流控制的协议，可确保数据从一个路由器到下一个路由器的无损传输。路由算法对几种不同类型的外部事件做出反应：新消息的到达，链路级的网络流控制通知所连接的链路或相邻路由器上的负载情况发生变化，网络组件故障的通知，或消息传输完成，这为下一条消息释放了资源。路由算法通常覆盖几个或多或少独立的方面。两个方面，死锁和活锁避免，确保消息在有限的时间内传输到目的地。 虽然死锁导致路由器内的消息等待时间无限长，因为它们的进一步路由循环地相互依赖，但当一个或多个消息连续通过网络而没有到达目标时，就会发生活锁情况。出于这个原因，活锁避免特别包括网络拓扑的知识，特别是C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6367Fig. 1. 一个网状网络，NARA的拓扑结构。以确定到给定路由器地址的目的地的路径。此外，路由算法包含一个本地调度，决定哪条消息是首选的资源conciliict，如链路的使用。另外两个重要的方面与避免过载和损坏的路由器或链路有关，如果可能的话它们是相关信息的收集和分发过程以及路由单个消息时的应用程序的组合路由算法NARA（New Adaptive Routing Algorithm，[5]）被用作示例。它适用于图1所示的二维网格，其中路由器的地址是整数寻址矩形中的坐标对（x，y）为了避免活锁，最小长度的路径是首选的，即如果可能的话，消息被路由为更接近目的地。死锁避免基于所谓的转向模型[14]。NARA根据Y方向上的差异来区分消息，使得其目的地具有比源更小的Y坐标的所有消息（例如从A发送到B的消息）与具有增加的Y坐标的消息分开处理，例如，C到D对于那些Y坐标增加的消息对于其他消息，同样的限制对称地适用。这种情况下的消息路径如图所示，唯一向下的部分直接通向目的节点。此外，NARA应用基于年龄的本地调度策略，如果消息在竞争空闲链路时失去对另一消息的仲裁，则该策略对事件进行计数。最后，NARA包含一种自适应方法，该方法包括对路由器中的缓冲器填充级别进行求和，68C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63\\ONin message（indir，vc，dx，dy）--消息到达--如果所有通道都在使用如果FORALLjINdeadlock free（indir，vc，dx，dy）：out chan（j，vc）>freeTHENout set（indir，vc）-deadlock free（indir，vc，dx，dy）;--如果任何最小路径是自由的如果EXISTSiIN minimal（dx，dy）：out chan（i，vc）=freeAND（FORALLjIN minimal（dx，dy）：out chan（j，vc）=freeAND平均队列（vc，i）=平均队列（vc，j））那么！send（vc，vc，indir，i），outqueue（vc，i）-消息长度（vc，indir）;--如果某些频道免费，但不是最小频道IFEXISTSiINdeadlock free（indir，vc，dx，dy）minimal（dx，dy）：out chan（i，vc）=freeAND（FORALLjINdeadlock free（indir，vc，dx，dy）minimal（dx，dy）：（meanqueue（vc，i）>=mean queue（vc，j）那么！send（vc，vc，indir，i），out queue（vc，i）-消息长度（vc，indir）;ENDin message图二. RERAL实现了NARA的主规则库，无死锁和最小是子规则库。将该信息传送到相邻路由器。如果消息到达，则检查是否有任何允许的链路可用于避免死锁。显然，该算法是复杂的，并且其描述优选地以高级语言完成。这种语言应该允许使用基本的数据类型（整数，布尔和数组），以及适当的操作（加法，比较，逻辑运算等），并且最重要的是，还允许从网络的自适应性或拓扑特性中单独描述诸如死锁避免算法的各个方面。诸如变量和事件的概念（“无论何时消息到达，都要执行以下操作”）等方面也很关键。最后，高性能要求必须在允许高并行性的语言中得到体现。大多数事件可以并发处理，但在某些情况下，需要保证原子行为，例如当分配共享资源时，例如，一个消息的链接。此外，用于执行路由算法的硬件必须提供用于存储结构化状态（变量、数组等）的资源。并且用于相应地对到达的事件执行算法。算法步骤涉及适当规则的选择，包括评估参数（例如目的地节点地址）上的算术表达式。其结果是修改状态变量，生成路由器数据传输部分的命令，以及在某些情况下生成用于进一步操作的新事件。为了实现性能目标，我们开发了一种路由引擎的架构，该架构将可配置的、特定于问题的组件组合在规则的前提和结论中用于算术表达式一个例子是基于有限有序集的容错电路[8]。规则的逻辑框架被映射C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6369到查找表。为了保持表的紧凑性，我们开发了一套压缩方法，利用规则性和对称性的算法结构。这些方法中的一些可以从算法中的模糊性中获益;例如在NARA中，对于停留在相同Y坐标级别（例如A到C）的消息存在这样一种未定义的情况：它们被实现分配到哪一类消息应用基于硬件的规则库评估的第二个领域是SoC [12]中存储器接口的管理，例如网络处理器。在诸如[11]的结构中，若干组件（网络接口、处理器核、协处理器、扩展接口）共享公共存储器接口。由于接口存储器所需的引脚数很高，因此该接口上的带宽通常是一种宝贵的资源。因此，优化其使用可以帮助构建更便宜的系统或以相同的成本实现更好的性能。然而，组件具有非常不同的访问特性;例如，比较来自数据缓存的具有固定行大小的零星内存访问模式和用于IP报头分类的树搜索引擎的固定模式。一些访问具有时间弹性，例如，脏数据高速缓存行的刷新有时可以提前完成，即，在高速缓存行被重新使用并且强制刷新之前。另一个示例是通常包含缓冲器的网络接口。取决于存储器接口上的当前和未来压力，通过所讨论的接口在该片上存储器与片上存储器之间进行数据传输的时间点可以变化。此任务的管理算法必须考虑应用程序的性能目标和各种组件（处理器，coprocessors）的利用率。在给定的过载或欠载情况下的反应必须转换为各个请求者组件的反应能力，而不会降低即将到来的周期的情况。由于这种管理问题与路由算法的相似性，我们认为，基于规则的语言的概念，结合优化编译器和应用程序定制的规则评估引擎，也可以应用。当然，必须进行包括系统模拟在内的深入研究来证明这一点。4RERAL语言本身及其定义路由算法的用法在[6]中给出。该语言的核心构建块是一条规则，由条件（前提）和命令列表（结论）组成一组规则构成规则库或子库。通常，子基是向调用者返回值的函数70C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63←--利用副作用，它们成为描述子程序和清晰地塑造代码的强大方法。与传统的编程语言（如C/C++和MODBLE-2）相比，规则库的所有规则都是并行执行的。在基于规则的调用中，相对于全局状态评估条件，并且属于所执行的结论的命令也并行地改变全局状态在这里，我们以路由算法实现为例，简要介绍RERAL的主要语法组件。常量定义CONSTANTLinkIndex：= 0..5;常数是由有限的数字、符号或常数集来声明的。这里，常量LinkIndex由6个数字0、 1、 2、 3、 4、 5组成。这些集合像类型一样使用，并构成硬件细节的高度抽象变量定义VARIABLELinkload（LinkIndex）IN 0.. 六十三岁;变量LinkLoad是一个数字数组，其中每个数字的范围为0. 63.它的大小和指数由括号中的常数给出。所有变量都有一个有限（通常很小）域，由一个集合文字或一个常数给出。基于规则的声明DEFER SUBBASETorusMinimalXDim（Xdest，Ydest）这种声明预先定义了一个有两个参数的子基。子库是规则库的一种形式它们是主要的结构元素，要么定义一个函数，要么作为具有副作用的子动作工作。声明不是必需的，但可以提高可读性。底基层定义SUBBASE opp（vc）. 结束操作此声明嵌入子基。这些点取代了一组独立的规则，这些规则的概念包含高度的并行性。每一个相关的情况下，必须涵盖至少一个规则（完整性）。触发式规则库定义ONIn message（Dir，Chan）. ENDIn消息这个规则库必须为绑定到它的每个发生的事件执行一次。由于规则库只描述功能，时间和顺序由事件的概念单独表示。规则如果vc=south，则opp north;这种结构是基于规则的语言的核心思想。它可以被看作是一个受保护的命令。一条规则代表算法的一种情况一C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6371←−规则库是某种情况区分，其中每个规则覆盖至少一种情况。它由谓词逻辑表达式表示。在这种情况下，动作是函数结果的表示。除了布尔运算符和算术表达式之外，还可以使用子基Prediction中的量化表达式EXISTSpIN{0， 1， 2， 3}：Outdoor Usage（dir，p）= FREEFORALLpIN{0， 1， 2， 3}：Outdoor Usage（dir，p）= FREE这两个表达式都是常规语言中使用的一种循环，但它们避免了常规循环的顺序性。EXISTS表达式是一种简短的形式，用于表示与有限集合的元素数量一样多的规则这里，变量p可以在结论中重用。与EXISTS表达式相反，FORALL表达式不是多个规则的缩写形式，而是同一前提下的AND表达式序列。这个变量不能在结论中重复使用，但也可以在结论中建立相同的循环，见下文。这两个表达式都引入了某种局部名称空间。事件生成（结论）！InternalSwitch（fromDir，fromChan，SOUTH，DetNetChan）;硬件的异步控制通过生成事件来完成。事件也可以用于级联多个规则解释以生成最终结果。变量分配（结论）OutLinkUsage（ToDir）OutLinkUsage（ToDir）-1规则执行是原子的，即如果变量在前提中检查并在结论中更改，则必须在相同的系统状态上执行两个规则库的并行执行。FORALL-Quantifier结论FORALLj在所有方向：！send info（info，j，total load）结论可以包含同时执行的几个命令。这同样适用于总的来说，语言消除了尽可能多的顺序依赖。请注意，在前提中应用子库并不意味着层次结构较低的子库必须在主子库之前执行。相反，层次结构只是一个更大的子基的一种表达形式，它是在一个片段中评估的。子基层次结构允许抽象硬件细节。变量的读访问不能从语法上与子基的应用区分开来。这允许引入缓存技术（消除子基调用），并通过计算原始期望值的方法来替换状态数组，72C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63∀CIMM∃其他来源因此，可以定义一个更高的接口，其在实际硬件上的实现可以再次使用规则库来完成5编译RERAL程序的编译过程简化了所有规则库。有几种变换，可以按任意顺序进行。目标是为每个事件建立一个规则库，其中包含一组最小的规则。规则的前提和结论应该是简单的表达式（简单比较的连词）和简单命令的列表。仅适用于直接硬件实现的功能（例如，一种变换的目的是通过用子基替换函数调用来检索最少数量的规则基。 另一个变换展开循环。 它们存在于使用forall或存在量化器的前提中，并且存在于使用标准forall语句来循环有限集合的所有元素的结论中。第三，搜索所有前提，以获得独立于运行时的元素，并根据结果对前提进行评估。通常，前提被简化为布尔常量，这样带有假前提的规则就被丢弃了。所有前提条件都收集在一个表中，并由标签替换，以避免多次运行时计算。详细的处理可以通过以下描述来近似• 常数的替换检查常量定义的相互依赖性以检测非法的环定义，并按它们排序以最小化替换的数量。在此转换结束时，所有常量值都将替换其符号。这一过程对随后的房地评估特别重要。• 解决量化器在前提中使用的所有FORALL（符号：）量化器通过以下等式求解：M是一个有限集合。p：M→B是一个谓词。i∈ M：p（i）p（i）替换EXISTS（Symbol：）量化器更加困难。结论可以使用所使用的变量，以便的每个元素都需要自己的规则。C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6373∨如果n∈M：p（i）则c（i）⇐⇒i∈M：如果p（i），则c（i）;M是一个有限集合。p：M→B是一个谓词。c是一个参数化的结论。这些替换通常允许在编译时减少规则前提。如果p（i）包括更多的量化器，则从最里面的量化器开始求解。• 扁平化层次结构在这里，RERAL程序的模块化结构通过内联插入子基来分解其结果是一个明显增长的规则基础。假设规则库A有l条规则，包括子库B的k个调用，A可以增长到lk−1个规则;如果子库调用分布在k个规则上，则规则库仅增长到lk−k个规则的大小。插入子碱基的顺序对效率有很大影响。假设规则库A调用子库B和C，并且B也调用C，这可以按以下方式处理一个在S中，B在A中，A作为中间结果，而在S中，C在A中，阿吉尔岛一个在S_n中，B和A，让B_n到A_n。A和B中，而非B不幸的是，不可能通过句法分析找到有效的方法。语义方面和依赖关系决定了这个问题。• 减少由于前面的步骤，每个规则库的规则数量不断增加，因此减少功能是受欢迎的。之后，每个不同的前提项需要一个硬件资源，比如比较器，每个规则需要一个表条目。这两种方法都限制在路由引擎中。由于注意层次结构和求解量化器可以在同一规则库中生成单个规则的多个副本，因此删除了多个特别是，联合国-折叠量化器允许通过评估常数的比较来进行约简。因此，考虑到布尔运算符（and）出现的频率比（或），许多规则可以跳过，因为完全评估虚假的前提。此外，算术表达式通过对变量进行排序并将其排列在不等式的一侧来规范化。每当产生新规则时，重复这些缩减步骤，以避免规则库的爆炸。··74C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63联系我们6优化规则库和子库的扩展产生了呈指数增长的规则数量。减少和控制所有这些规则对于编译器来说是相当困难的，并且在某些情况下是不可能的，因为缺少运行时信息，例如考虑动态集。考虑到每个规则需要芯片空间，规则的绝对数量是有限的。代数优化，如代数项的评估，例如比较，或删除多个副本尚未被提及。 另一个想法是找到结构，如内联插入的子库或非常小的函数，这些函数被函数调用取代，其硬件实现比规则库更节省空间。候选函数是在大集合上工作的函数当使用传统方法来实现它们时，有些方法只消耗固定的空间。在这种情况下，固定大小的函数通常优于基于规则的函数。为了定义这些结构，搜索规则库，并通过函数调用替换出现的规则，指定一个替换模式，并将每个规则转换为一阶逻辑表示，并通过统一算法进行搜索。6.1统一一般来说，统一试图通过用其他表达式替换子表达式来识别两个符号表达式。例如，假设f是一个函数符号，a和b是常数，x和y是变量，项f（a，x）和f（y，b）的统一问题可以通过替换x/b和y/a来解决，其中x/b意味着右元素b替换左元素x。这个例子的结果是x/b，y/af（a，x）=x/b，y/af（y，b）=f（a，b）。在这里，应用于一阶逻辑的语言，统一是一种句法的统一。Baader和Snyder [3]介绍了句法统一，并给出了Robinson的统一算法。 它决定一组项是否是可唯一的，并且在肯定的决定的情况下，返回最一般的唯一者，即一组替代，其对函数的约束小于所有其他可能的唯一者。这通常应用于自动定理证明器。6.2模式匹配为了塑造规则库的性能，库可以为程序提供性能优化的子库。对于每个库函数，必须定义描述高级结构和函数及其高级替代的替代模式。为了在高级程序表示中跟踪这些事件，搜索规则库的模式和每个规则C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6375⇒IFEXISTS A IN集合：[（p（A））AND（FORALL B IN集合：[（p（B））AND（（v（A）） =（v（B）））]）]则c（A）;=IFEXISTS AIN集合：[p（A）]然后c（selectminimal（Set，p（），v（）;图三.典型的模式说明。用Robinson的unification算法来检验。图3展示了示例性模式。它的规范语言是一阶项和RERAL语法的混合。左侧定义了在规则中搜索的规则模式以小写字母开头的标识符表示至少有一个参数的函数，首字母大写表示变量，关键字用大写字母书写。图3中的示例性规则模式的前提包含最小值函数，其结果被所有命令用于结论中：“如果集合中存在小于或等于所有其他元素的元素，则处理它”。模式前提类似于一阶项;只有比较运算符是预定义函数，因为它们的频率很高。所有其他功能都可以由通用功能符号确定，而无需系统已知的任何语义。结论的表示允许两个符号：变量和带有前提中定义的参数的函数。两者的组合也是可能的。变量可以匹配任何命令序列，甚至是空集.函数必须匹配至少一个依赖于指定参数的命令。在图3中，函数p（）是所有元素必须满足的附加约束;v（）是一种权重函数。 每次出现包含此模式的规则时， 前提的最内层循环，并引入库函数调用selectminimal。应用一阶统一的假设是，这两个输入都是一阶项。每一条规则和模式都被转换成一种前缀符号;甚至规则本身也是一个有两个参数的二元函数：前提和结论。图3的示例的转换结果如图4所示。由于该算法不匹配高阶项，因此没有确定语义的函数被变量替换，以便转换后的模式更通用。模式的原始含义由约束列表恢复，该约束列表包含每个泛化的约束。泛化和约束的另一个例子是同一个函数的多个频率，其中函数的每次出现都被它自己的变量替换。变量的所有替代必须是相同的函数（约束）。下面列出了恢复模式语义所需的约束76C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63（F“规则” [F“PREMISE”[F“EXISTSQ”[V“A”，V“Set”，F“AND”[V“p”， F“FORALLQ”[V“B”， V“Set”，F“AND”[V“p0”，F“LESSEQ”[V“v”，V“v0”]，F“结论”[V“c”]]，F“规则”[F“PREMISE”[F“EXISTSQ”[V“A”，V“Set”，V“p”]]， F“CONSTRUCTION”[F“FUNCTION”[V“c”，F“FUNCTION”[V“selectminimal”， V“Set”，F“FUNCTION”[V“p0”]，F“FUNCTION”[V“v”]）见图4。 转型示范模式。设置[F参数等于1 [V“c”]，F ALL ELEM [V“A”]（V“p”），F ALL ELEM [V“B”]（V“p0”），FEQUAL（V“p”）（V“p0”），F ALL ELEM [V“A”]（V“v”），F ALL ELEM [V“B”]（V“v0”），FEQUAL（V“v”）（V“v0”），C ALL ELEM [V“A”] [V“c”]]，[TP（V“A”，F“功能”[V“selectminimal”，V“Set”，F“FUNCTION”[V“p0”]，F“FUNCTION”[V“v”]]）]图五. 示例模式的约束（左）和换位（右）。• F_PARAM_EQUAL Int [函数]列表中的所有函数必须具有相同数量的参数。此约束用于确保分配给变量的序列长度相等• F_ALL_ELEM [函数]函数列表中的所有元素都必须是函数的参数• F_EQUAL函数除了参数之外，两个函数必须相等。• C_ALL_ELEM [Function] [Function]/C_ANY_ELEM [Function] [Function]第一个列表的所有变量必须被第二个列表的所有元素/至少一个元素绑定。图5显示了图3的模式及其转换的约束列表，如图4所示。转置是从目标规则派生的，并且是构建目标规则所必需的。在使用最通用的统一器之前，必须将它们应用于模式通过处理NARA的第二条规则（见图2），使用图3的模式，该算法成功地计算出最通用的unier（见图6）。这被附加到通过转换获得的换位，然后执行所有替换。最后的结果，一个包含库函数调用的规则，因为匹配的模式，如图7所示。C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6377[TP（V“A”，V“i”），TP（V“Set”， F“FUNCTION”[V“minimal”，F“SYMB”[V“dx”]，F“SYMB”[V“dy”] ]），TP（V“p”，F“EQUAL”[F“FUNCTION”[V“out chan”，F“SYMB”[V“i”]，F“SYMB”[V“vc”]]，F“SYMB”[V“free”] ]），TP（V“B”，V“j”），TP（V“p0”，F“EQUAL”[F“FUNCTION”[V“out chan”，F“SYMB”[V“j”]，F“SYMB”[V“vc”]]，F“SYMB”[V“free”] ]），TP（V“v”，F“FUNCTION”[V“meanqueue”，F“SYMB”[V“vc”]，F“SYMB”[V“i”]]），TP（V“v0”，F“FUNCTION”[V“meanqueue”，F“SYMB”[V“vc”]，F“SYMB”[V“j”] ]）]见图6。 NARA第二条规则的典型模式的最一般的统一者IFEXISTSiINminimal（dx，dy）：out chan（i，vc）==freeTHEN！send（vc，vc，indir，selectminimal（minimal（dx，dy），equal（），mean queue（）），out queue（vc，selectminimal（minimal（dx，dy），equal（），mean queue（））←消息长度（vc，indir）;见图7。 应用于NARA第二规则的示例模式的替换结果。7结果基于规则的硬件规范的编译过程和生成的实现通常是贪婪的资源。因此，特别是处理系统侧的存储器大小以及目标系统侧的可用逻辑门和定时约束限制了可处理规则的数量和复杂性。节约资源利用的函数的使用提供了实现更多规则的空间。因此，可由路由引擎执行的规则库的数量增加。将图3的模式应用于NARA（见第3节），它选择了部署约束和权重函数的集合的最小值，提供了一些支持我们方法的数字。我们的目标是减少规则的数量和缩短前提，以缩小路由引擎的表。每一个前提的比较都需要一个算术电路，并对表访问的地址长度有贡献。NARA第二条规则的扩展提供了117条规则，每个前提有7个比较利用基于统一的优化，只有13个规则，每个前提下有3个比较。 在这里，减少到规则数量是正常数量的十分之一，比较数量减半78C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）63每一个前提都实现了。不幸的是，由于几个函数的可交换性，基于归一化的优化具有高失配比。因为交换的二进制操作数，例如交换操作可能导致不匹配，所以操作数按长度排序以减少不匹配的数量。该编译器将分层描述的算法分解为几个表，每个事件触发规则库一个表。NARA的示例规则库的表需要大约1 kByte。此外，在XILINX 4000 FPGA上实现的规则评估引擎的原型实现了50 MHz的时钟频率。假设当前技术中的标准单元ASIC实现将在约500MHz下运行系统对单个事件的反应具有非常低的延迟（60ns），因为原型每个决策仅消耗三个时钟周期应用于路由，该值甚至可以满足网络对最先进的刀片服务器或高端集群的要求。8结论异构可配置硬件单元是相对较新的，因此在该领域中的编译器构造提出了新的挑战。本文所介绍的实验编译器结合了多种不同的技术，证明了使用高级抽象语言可以获得很高的性能。结合对外部事件的快速反应和编译器支持的高抽象级别，可为具有极高实时要求和有限硬件资源的问题提供执行模型。值得注意的是，这个转换系统打破了一个分层描述的路由算法，如NARA下降到一个小尺寸的几个表。此外，规则的大小和数量的减少减轻了处理系统的负担，并为更大和更复杂的规则库提供了新的空间。此外，如果将相同的方法应用于新的领域，则必须首先通过分析目标算法集来识别应用领域的关键功能。这允许将复杂的子问题直接映射到可配置的硬件单元。还可以识别预期的冗余类型，这允许选择适当的地址生成方法。由于所使用的基于统一的优化技术并不像它应该的那样由于语义统一具有很高的复杂度和计算量，因此与其他排序函数，如任何类型的权重函数，评估和组合不同模式相比，C. Albrecht，A.C.Döring/Electronic Notes in Theoretical Computer Science 124（2005）6379质量应该得到检验。引用[1] 阿尔布雷希特卡斯滕在RERAL-装配机中，对硬件进行优化。学生论文，技术报告IAB-75，计算机工程学院，吕贝克大学，德国，2001年。[2] 阿尔弗雷德五世Ravi Sethi和Je Escherey D.厄尔曼原则、技术和工具。Addison-Wesley，1988年。[3] 巴德尔，弗兰兹和韦恩斯奈德。统一理论。《自动推理手册》第8章，由Alan Robinson和AndreiVoronkov编辑，Elsevier Science Publishers B.V.，1999.[4] 伯德理查德介绍使用Haskell的函数式编程。第二版，Prentice Hall，1998年。[5] 作者：Chris M.还有迪米特·阿夫雷斯基二维网格的容错自适应路由。第一届高性能计算机体系结构国际研讨会论文集，IEEE计算机学会，1995年。[6] D？oring，AndreasC. ，GuntheherLustig，CartenAlbrcht，and dWolfga n gObel？oer.为特定于应用程序的语言编写编译器。第一届苏格兰函数式编程研讨会，1999年8月29日至9月1日，英国斯特灵。[7] D？oring，AndreasC. ，WolfgangObeléoer，GuntherLustig，anddErikMae hle.一种用于容错路由器的灵活性方案。在Proceedings of the Workshop on Fault-Tolerant Parallel and DistributedSystems ， Lecture Notes on Computer Science1388 （ 1998 ） ， 693- 713 ， Springer ，Berlin/Heidelberg。[8] D？r ing，Andr easC. 然后让我看看你。在高速网络中实现用于全状态编码的VLSI中的有限状态索引。并行和分布式处理，计算机科学讲义1800（2000），Springer。[9] D？r ing，Andr easC. ，GuntheherLustig. 在FPGA片上存储器中对多个不同类型的存储器进行基因修复。现场可编程逻辑和应用FPL 2000，计算机科学讲义1896（2000），626-[10] Duato，Jose，Sudhakar Yalamanchili，and Lionel Ni. 互连网络摩根-考夫曼出版社，2002年。[11] Gabrani ， Maria ， GeroDittmann ， AndreasD ？ oring ， AndreasHerkerrsdorf ，PatriciaSagmeister，and Jan van Lunteren.模块化服务驱动网络处理器体系结构的设计方法。