动态结构进程代数的硬件建模技术

理论计算机科学电子笔记162（2006）249-254www.elsevier.com/locate/entcs动态改变硬件结构的建模乔治·米尔恩1西澳大学计算机科学与软件工程学院M002/35 Stirling Highway，Crawley WA 6009，Australia摘要给出了使用进程代数对可重构计算硬件进行建模的技术。动态变化的硬件使用具有动态排序的进程代数来建模，其中排序随时间变化。一种基于这种动态结构进程代数的编程技术的概述。关键词：进程代数，可重构计算，动态结构硬件，电路建模1介绍数字硬件是进程代数的一个自然应用领域，因为电路表现出固有的并发行为，可能是大规模并发。对数字硬件建模和验证的推动力导致了过程演算的发展，其特征受到数字逻辑中固有概念的影响。这项工作在很大程度上受到罗宾·米尔纳（RobinMilner）在CCS [11]及其前身[10]上的工作的影响，并导致了被称为Circal [6]的电路演算的发展。1990年，我们格拉斯哥斯特拉斯克莱德大学的一些人希望使用现场可编程门阵列（FPGA）作为新计算机体系结构的使能技术，该体系结构可以被编程为用于模拟空间分布的、高度并发的应用的定制机器。其基本思想相当简单;我们将展示大量细粒度并发和本地互连的系统映射到基于FPGA的架构上。由此产生的配置为我们提供了一个定制的硬件模拟器的物理系统，如EQUUID EQUIPLOW，与物理之间的1-1对应关系，1电子邮件：george@csse.uwa.edu.au1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.12.091250G.J. Milne/Electronic Notes in Theoretical Computer Science 162（2006）249+组件和实现其模型的数字逻辑区域。这样的架构现在被称为可重构计算机，例如[9，1]。 有人认为，Circal是一种合适的语言，它规定了一个系统实现为硬件，而不是作为一种语言来模拟以前设计的电路。进程代数允许我们描述相互作用的自动机系统，每个自动机由一个进程描述。这是从进程代数到FPGA逻辑的编译技术的基础，在[3，2]中描述。使用进程代数对可重构计算机进行编程的适当性在[5]中进行了研究可重构计算不同于经典的冯·诺依曼计算范式，因为程序不驻留在内存中，而是直接在数字逻辑中实现应用程序。由于该逻辑是可重复编程的，因此底层FPGA平台可以被实例化以针对每个不同的应用创建不同的定制计算机实现。此外，某些FPGA技术是动态可重构的，因为FPGA逻辑的一部分可以在另一部分运行时被重构。也就是说，我们的可编程硬件可以在运行时进行修改，而且，它具有自我修改的潜力，这是一个传统上被认为是软件世界中的诅咒的概念，正如Tony Hoare所描述的那样。 因此，动态重新配置允许硬件结构在运行时改变，与具有固定结构的传统计算系统相反。对动态变化的硬件结构进行编程的需求导致了动态结构Circal（dsCircal）的引入[8]。Circal是静态的，因为我们只能对具有固定结构的系统建模;这足以对许多类型的系统建模，例如数字硬件[7]甚至道路网络[9]。固定的静态排序的概念已被广泛用于表示具有固定拓扑的并发系统的结构。这个概念在[10]中被引入，早期的工作导致了CCS和Circal的发展。排序的概念在Circal中很重要，因为Circal复合运算符依赖于其操作数的排序一个由多个进程组成的系统采用了结构化的综合惯例，即名称相似的端口将链接在一起。进程在所有类似命名的端口上同步发生动作后更改状态。因此，我们有由保护新状态的动作的发生引起的状态变化。我们将这一概念扩展到一个保护动作也可以控制过程结构变化的概念。 也就是说，不仅仅是进入一个保持相同结构的新状态，而是进入一个具有相当不同结构的新过程。因此，在环境中其他过程的控制下，结构可以随着时间而变化。这就是动态排序的概念。动态结构Circal与Circal的不同之处在于，它允许某种过程在适当的行动控制下（可能）随时间演变。一个进程的排序被明确地表示为一个标签向量，它与相应的进程标识符并列，就像一个具有静态结构的简单进程一样，定义如下：（一）defPa， b=aP1bP2G.J. Milne/Electronic Notes in Theoretical Computer Science 162（2006）249251⟨⟩def++=1 =1212 =21=这里我们假设更新过程P1和P2（在别处定义过）具有相同的静态排序，即a，b。但是假设我们有一个名为Q的进程，它（二）defQa，b+BQ 刚果（金）c、d、e其中（3）Q2<$c，d，e<$=（c，d）Δφ+eQ<$a，b<$这捕获了一个过程Q2，它通过灭绝（空排序的空过程Δ）来响应同时动作（c，d），并通过递归返回Q来响应e事件。2一个简单的动态结构给定一个由三个过程A、B和C组成的系统，定义如下：（四）defAa，p=aA pA其中（5）defBp， t pBt B格山（六）defBq， tqB+t Bp，t（七）defCc，qcC+QC由这三个过程构成的系统可以定义如下：（八）12111252G.J. Milne/Electronic Notes in Theoretical Computer Science 162（2006）2491 =1defSY Sa，p，c，q，t Aa， p B p， t Cc，q进程A和C具有静态结构，也就是说，它们的排序在时间上保持固定。 只有进程B具有动态排序，它可以（最初）由于端口T1上的外部生成动作。因此，动作t1充当触发动作，使过程B演变为过程B1，其排序不同。进程B1可以对也是外部生成的操作t2做出反应，并切换回其作为进程B的原始化身由进程B上的触发器动作引起的结构的改变导致系统SY S的结构改变。当B演变成G.J. Milne/Electronic Notes in Theoretical Computer Science 162（2006）249253一CQB1B1，作为动作t1的结果，p链接消失，同时出现q链接。B2中的动作t2导致相反的情况发生.两个不同系统结构之间的这种演变，以及其演变回原始配置的潜力，如下图所示：AC A C一个CQppB进化为t1t2请注意，虽然我们的系统具有动态结构，但这是在固定数量的进程（本例中为三个）上改变互连。对于硬件中的动态重构，我们还需要进程的创建、消亡和可能的移动性，以及它们的互连链接的创建和销毁。进程的创建和销毁也可以在特定控制端口上发生的操作3编程 可重构硬件在冯·诺依曼计算中，执行处理器的顺序行为通常通过遵循由编程语言描述的活动序列来将输入数据操纵成输出数据。 程序、编译器和微处理器的设计最终决定了执行代码的行为。在并行世界中，计算是通过直接映射到可编程数字逻辑来实现的，类似的情况也存在。 在这种情况下，我们也可以使用一种语言来描述计算，该语言直接支持动态结构上的并发交互，如dsCircal语法所捕获的。同样，代码将执行，但不是想象dsCircal片段在顺序计算机上编译和执行，我们将专注于直接在数字逻辑中实现编码行为FPGA逻辑单元块将被分配和配置为执行固定结构的功能行为;即，由在给定时间段内不改变其结构的互连过程捕获的行为。在这段时间里，他们保持着一种固定的排序。 在此期间，随着过程通过有限集的演化，可能会实现相当不同的行为国家。然而，这个进程和它的环境之间的任何交互都将通过由它的排序表示的固定端口集当我们的过程有动态排序时，我们可以有一个过程P，它在发生之后变成另一个具有完全不同结构的Q。 一个守护行动。我们可以如下实现在这样的dsCircal过程中编码的行为：254G.J. Milne/Electronic Notes in Theoretical Computer Science 162（2006）249文本描述中间形式数字硬件实现dsCircal过程我们可以想象，可用的FPGA逻辑是有限的，只有进程P的配置块可以实现。子过程Q的编码将驻留在适当标识的存储器位置中。当使能动作发生，导致进程P演化为结构上（和行为上）不同的进程Q时，实现Q的配置将从驻留在内存中的编码构造出来。这个新的配置将覆盖P的配置块，因此当行为从P传递到Q时，我们的机器将动态地重新配置，而进程P本身在从P演变到Q时会引起重新配置。重新配置FPGA单元块所需的数据由比特流或比特序列组成。该位流被加载到RAM中，其中每个存储器位置控制FPGA的可编程门阵列的对应部分。这用于选择底层原始可配置单元（通常是门或简单ALU）的逻辑功能，同时还选择此类可配置逻辑构建块之间的互连性与dsCircal一样，原始代理集、可配置逻辑块及其连接结构都是动态的，可以随着时间而变化。位于一个位置的过程编码被称为过程基因，或简称基因。就像一条DNA链编码或映射蛋白质是如何从氨基酸序列构建的一样，我们的过程基因也编码了我们底层FPGA技术的硬件构建模块是如何构建的，当它们变得活跃时，它们就会实现所需的行为。与遗传学的类比甚至更强，因为DNA也编码时间信息，因为只有部分DNA链可能负责构建当前蛋白质，并且该蛋白质可能在DNA编码的控制下发生变化。氨基酸的特定选择和出现顺序决定了它们如何组合，从而决定了构建的蛋白质的结构从过程表达式到FPGA硬件实现的编译如下图所示：过程生成器函数采用过程编码基因并产生直接实现相应过程行为的硬件。基因是活动数据，当解释时会产生一个对象，例如块可配置的FPGA逻辑，表现出主动行为。将基因存储在一个位置并根据需要获取基因副本的能力允许我们通信过程编码。因此，两个进程的主动数字硬件实现可以通过将其标识符名称发送到接收进程来将第三进程从一个进程传送到另一个进程。 这个标识符名将由接收器“锁定相应的位置”并提取所包含的基因。然后，接收器和进程生成器可以使用该基因来产生作为配置逻辑块的通信进程的实现。然后，该活动数据，即通信过程的硬件实现，将配置逻辑块相应基因G.J. Milne/Electronic Notes in Theoretical Computer Science 162（2006）249255能够按要求执行引用[1] Barrie，P.，P. Cockshott，G. Milne和P. Shaw，高度并发机器的设计和验证，微处理器和微系统16（1992），pp. 115-123[2] 迪塞尔岛和G.Milne，行为语言编译与虚拟硬件管理。，在：R. Harlington和H. Grunbacher，editors，10th International Workshop on Field Programmable Logicand Applications（FPL 2000），Villach，Austria，Lecture Notes in Computer Science1896（2000）.707-717.[3] 迪塞尔岛和G.Milne，A hardware compiler realizing concurrent processes in reconfigurable logic，IEE Proceedings-Computers and Digital Techniques148（2001），pp.152-162.[4] Hoare，C.，编程语言设计的提示，技术报告STAN-CS-73-403，斯坦福人工智能实验室，斯坦福大学，斯坦福（1973）。[5] 李，G.和G. Milne，Programming Paradigms for Reconfigurable Computing，Microprocessors andMicrosystems29（2005），pp. 435-450[6] Milne，G.，CIRCAL和通信，并发性和时间的表示，ACM编程语言和系统交易7（1985），pp。270-298.[7] Milne，G.，“The Formal Specification and Verification of Digital Systems,” McGraw-Hill Company,[8] Milne，G.，可重构硬件系统中的动态适应模型，在：A。Stoica，编辑，第一届NASA/DOD可进化硬件研讨会，1999年7月19-21日。加州帕萨迪纳。IEEE Computer Society Press，1999，pp. 161比169[9] Milne ， G. ， P. Cockshott ， G. McCaskill 和 P. Barrie ， 在 SPACE 机 器 上 实 现 大 规 模 并 发 系 统 ， 在 ：Proceedings IEEE Workshop on FGPA26比32[10] Milne，G.和R. Milner，Concurrent Processes and Their Syntax，Journal of the ACM26（1979），pp. 302-321[11] 米尔纳河，