《基于Petri Net的目标机描述的初步研究》由会员分享，可在线阅读，更多相关《基于Petri Net的目标机描述的初步研究（8页珍藏版）》请在金锄头文库上搜索。
1、基于Petri Net的目标机描述的初步研究符文杰清华大学 计算机科学与技术系，北京 100084A Primary Study in the Architecture Description Language based on Petri-NetWenjie FUDepartment of Computer Science and Technology, Tsinghua University, Beijing 100084, ChinaAbstract: Retargetability is especially important in compilers, and architectu
2、re description is one of the key elements for such a purpose. The paper studies how to specify the architecture using some kinds of Petri Net models. The concurrency and other properties Petri Net has make it certain advantages as an Architecture Description Language, but the current research in the
3、 field is not so much. During the progress of modeling a simple CPU design using Petri Net, we conclude some general ideas of the modeling work and discuss some different Petri Net models which can be used. On the basis of these work, we can carry out more complicated architecture model and develop
4、an efficient method in the future.Key words: Architecture Description Language, Petri Net, Modeling, Execution摘 要：在编译程序中，可重定向性非常重要，而目标机描述是实现可重定向性的核心环节。本文研究了用Petri网模型对目标机进行描述的问题。Petri网的并发性等特点使得它在作为目标机描述语言有一定的优势，但是目前在该领域中的研究并不多。我们在对一个简单的CPU设计进行Petri网建模的过程中，总结了一些建模的基本方法并讨论了适用的Petri网模型。在这些工作的基础上，今后可以对更复
5、杂的目标机进行建模，并逐渐形成一套有效的建模方法。关键词：目标机描述语言、Petri网、建模、执行1 引言在编译程序中，可重定向性是一个重要的追求目标。它的原因有很多，如：(1) 现代计算机系统结构呈多样性的态势。(2) 相对于计算机硬件技术的迅猛发展，系统软件和工具的开发周期更长、费用更高。(3) 许多应用系统，特别是嵌入式系统，需要用到宿主机上具有重定向能力的交叉开发工具。(4) 在软硬件协同设计过程中，目标机环境并不可用，系统结构设计方案也是多变的。目标机描述是实现可重定向性的核心环节。对目标机的描述可分为结构级、行为级和这两种的混合。结构级以描述各功能部件的结构及其互联关系为主。行为级
6、以指令集系统结构的描述为主。服务于可重定向编译程序的目标机描述语言，至少应该包含行为级的描述，多数都不同程度地包含结构级信息的描述。但是，当前的目标机描述语言中结构级信息的描述能力和分析使用能力较弱，并且缺乏形式化的方法。这就是这个题目的研究意义之所在。使用Petri网12作为目标机描述语言在这方面具有一些优势，原因是：(1) Petri网在描述并发性，资源流动、依赖与共享等方面优于其它的形式模型。(2) Petri网具有简单、易理解的图形表示。(3) Petri网具有较强的行为分析、模拟（执行）和正确性（安全性和活性）验证能力。本文首先根据任务的特点，选择了一种适合的Petri网模型作为目标
7、机描述语言。然后，我们选定了一个单发射5级流水CPU作为建模对象。我们完成了对该CPU的建模，并运用一些验证手段和模拟器来验证其正确性。在建模的过程中，我们总结了一些基本方法并讨论了适用于目标机建模的Petri网模型。第二章介绍了Petri网模型的选择。第三章介绍了建模中的一些基本方法。第四章作了小结并展望今后的工作。2 Petri网模型Petri网的种类很多，从简单的库所/变迁网，到有色网，到更复杂的Petri网，如：对象Petri网、随机Petri网、时间Petri网越复杂的Petri网模型往往具有越强的建模能力，但是同时也削弱了其模拟、分析和验证的能力，并且不具备足够的简洁、有效性。所以
8、，我们需要找一种适用于描述体系结构的Petri网模型来使用，既要有足够的建模能力，又要简洁以满足模拟的需要。2.1 基本模型Petri网的基本元素是：Token、库所和变迁（包括输入弧、输出弧）。CPU中的通用寄存器、指令寄存器和内存等部件包含了指令、寄存器值和内存值等数据，这些信息需要保存在Petri网的Token中。Token是最适合存放变化的数据的Petri网元素。寄存器堆、内存、流水步间寄存器等部件是存储上述数据的地方；而Petri网中Token是存放在库所中的。所以这些部件就建模成Petri网的库所。每一个流水步的执行中，数据发生了变化，所以对应于Petri网的变迁（数据的变化由To
9、ken的变化表示出来）。我们很自然地把每个流水步建模成一个变迁。从描述能力上来说，有色网3基本能够满足我们的需求。但是由于CPU等建模对象的复杂性，使得用有色网建模得到的模型会比较复杂：有很多库所；一个变迁要涉及到许多Token。所以，我们在有色网的基础上，向对象网566的方向作一些扩展，使得模型简洁一些，也减少了建模中可能出现的错误。具体的扩展为：一个Token中可以包含多个属性值（有色网的一个Token中只有一个属性值）。举例来说：一个有色网的Token可以是红、黄、蓝三种颜色之一；一个对象网的Token除了具有颜色的属性（可以是红、黄、蓝中任一种颜色）之外，还可以具有大小的属性（可以是大
10、、中或小的）。2.2 并发特性Petri网具有并发的特性，所以它可以很自然地描述多个流水步的并发操作。但是普通的Petri网并没有对可同时触发的变迁的触发次序做出规定，而我们要建模的CPU的指令执行方式是顺序发射顺序执行，因此就会引出如下图的问题。图2.1 顺序错乱的指令执行示意图上面的示意图中有两个流水步，两个流水步的变迁的触发条件都是从输入弧中输入任何一个Token，输出还是该Token。在时刻1，流水线中有两条指令：黑色的Token代表的指令执行顺序在前，且完成了第一个流水步；灰色的Token代表的指令执行顺序在后。此时，流水步1和流水步2这两个变迁都可以触发。在没有规定触发发生的顺序的
11、前提下，有可能会发生流水步2先触发的情况。触发之后就是时刻2的情形。在时刻2，两个Token（指令）都在第二个库所中。此时，流水步2既可以绑定黑色的Token触发，也可以绑定灰色的Token触发。在未规定其触发顺序的情况下，就有可能先绑定灰色Token触发，成为时刻3的情形。这样顺序靠后的灰色Token就先于黑色的Token完成了两个流水步。但是，这种情况是我们所不希望看到的。所以，我们必须要进一步做出某种限制，来避免这种情况的发生。通过上述的例子的分析过程，我们可以发现2种途径来避免其发生：(1) 在任意时刻，都并发触发尽可能多的变迁。(2) 在库所中给Token建立一个先进先出队列。库所中
12、先加入的Token必须被先取走。第一种方案中的“尽可能”多不是最大值的意思，而是极大值的意思。相当于对任意随机选择的可触发的Token，先把它的每条输入弧上需要的Token都取走，而不马上产生输出弧上应该产生的新Token，然后继续随机挑选一个可以触发的变迁，重复此操作，直到找不到可触发的变迁为止。当不能再触发变迁时，把前面积累下来的未及时生成的Token添加到相应的库所中，开始下一轮。它的优点是变迁并发触发与流水线并发执行的本质完全吻合；它的缺点是模拟的时候增加了一些要求，需要模拟器配合实现。第二种方案中，选用的Petri网模型也有比较大的变动。它还有一个缺点是，不能要求所有的库所都先进先出
13、。因为对一些与流水线操作无直接关系的部分，比如寄存器堆，不能要求它们中的Token也必须先进先出。其结果就是，我们仅对部分库所规定Token要先进先出。Petri网模型变得很复杂，不是我们所希望的。综合之后，我们推荐第一种方案。使用第一种方案给建模带来了一个限制每个流水步只能经过一个变迁。下一章的部分就介绍怎么克服这个限制。3 建模对CPU建模是一项比较大的工程，不可能一蹴而就。把目标机部件逐个进行建模，使得建模结果与目标机部件能够一一对应，既是一种常规的建模思路，也能避免建模过程中的遗漏。在建模的过程中，可能会有一些部件难以构建得和目标机设计完全一致。此时可以做一些小的改变，但必须十分小心。
14、一定要保证在整体上和目标机设计是一致的。3.1 内存访问因为内存中的数据是可变的，所以我们把内存设计为一个Token。它是一个相当大的Token，包含了许多属性，每一个属性对应了一个内存中的一个字节。在需要读写内存数据的流水步里，我们为了能够对内存数据进行操作，就必须在该流水步对应的变迁中把内存Token从内存库所中取出来。然后，我们可以从中读取一个字节为其他的Token设置值，或者修改它的某一位的值。最后，我们要把内存Token放回内存库所中，使得以后能够继续访问内存。图3.1 内存访问建模示意图因为一个Token在一个时刻不能同时被两个变迁取走，所以在这样的设计中，同一时刻只能有一个流水步
15、访问内存。当有两个流水步需要同时访问内存的时候，就必须把其中的一个暂停，以避免访问冲突。我们拿来建模的目标机本身就有这种内存访问互斥的性质，它的设计中已经包含了内存访问互斥的处理，所以不需要我们在建模的时候做特殊处理，只要把它的设计完全表示出来即可。3.2 通用寄存器堆访问寄存器堆的建模可以参照内存建模。但是，两者之间也有一些差异：l 存储的数据量上的差异：内存中存储的数据很多，在M数量级以上；寄存器堆中存储的数据一般就几十个。l 访问方式上的差异：一个时刻只能访问一个内存数据；在寄存器堆中，一个时刻能够读写多个不同寄存器的值。如果我们完全照搬内存的建模方式，用一个Token来保存所有通用寄存
16、器的值，那么它就不能满足我们的需求多个流水步（变迁）可能需要同时访问通用寄存器堆 在经典5级流水的译码和写回步都需要访问通用寄存器。所以，我们需要作出一些变化。把每个通用寄存器的值保存在一个Token中，其中有两个字段（属性），第一个字段标识寄存器的编号，第二个字段记录寄存器的值。这样在寄存器堆中就有多个Token。满足了并发访问多个寄存器的需求。需要注意的是，在该模型下仍然不能同时读写同一个寄存器，因为含有该寄存器的值的Token只有一个，不可能同时取出两个来。如果我们需要在一个流水步（变迁）中访问两个寄存器 在译码ID流水步就有这样的需要。，这两个寄存器可能是不同的也可能是相同的，就需要在建模的时候用一点技巧。
