基于Petri-Net的目标机描述的初步研究.doc

基于Petri Net的目标机描述的初步研究

A Primary Study in the Architecture Description Language based on Petri-Net

Abstract: Retargetability is especially important in compilers, and architecture 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 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 an efficient method in the future.

Key words: Architecture Description Language, Petri Net, Modeling, Execution

摘 要：在编译程序中，可重定向性非常重要，而目标机描述是实现可重定向性的核心环节。本文研究了用Petri网模型对目标机进行描述的问题。Petri网的并发性等特点使得它在作为目标机描述语言有一定的优势，但是目前在该领域中的研究并不多。我们在对一个简单的CPU设计进行Petri网建模的过程中，总结了一些建模的基本方法并讨论了适用的Petri网模型。在这些工作的基础上，今后可以对更复杂的目标机进行建模，并逐渐形成一套有效的建模方法。
关键词：目标机描述语言、Petri网、建模、执行

1 引言
在编译程序中，可重定向性是一个重要的追求目标。它的原因有很多，如：
(1) 现代计算机系统结构呈多样性的态势。
(2) 相对于计算机硬件技术的迅猛发展，系统软件和工具的开发周期更长、费用更高。
(3) 许多应用系统，特别是嵌入式系统，需要用到宿主机上具有重定向能力的交叉开发工具。
(4) 在软硬件协同设计过程中，目标机环境并不可用，系统结构设计方案也是多变的。

目标机描述是实现可重定向性的核心环节。对目标机的描述可分为结构级、行为级和这两种的混合。结构级以描述各功能部件的结构及其互联关系为主。行为级以指令集系统结构的描述为主。
服务于可重定向编译程序的目标机描述语言，至少应该包含行为级的描述，多数都不同程度地包含结构级信息的描述。但是，当前的目标机描述语言中结构级信息的描述能力和分析使用能力较弱，并且缺乏形式化的方法。这就是这个题目的研究意义之所在。
使用Petri网[1][2]作为目标机描述语言在这方面具有一些优势，原因是：
(1) Petri网在描述并发性，资源流动、依赖与共享等方面优于其它的形式模型。
(2) Petri网具有简单、易理解的图形表示。
(3) Petri网具有较强的行为分析、模拟（执行）和正确性（安全性和活性）验证能力。

本文首先根据任务的特点，选择了一种适合的Petri网模型作为目标机描述语言。然后，我们选定了一个单发射5级流水CPU作为建模对象。我们完成了对该CPU的建模，并运用一些验证手段和模拟器来验证其正确性。在建模的过程中，我们总结了一些基本方法并讨论了适用于目标机建模的Petri网模型。
第二章介绍了Petri网模型的选择。第三章介绍了建模中的一些基本方法。第四章作了小结并展望今后的工作。

2 Petri网模型
Petri网的种类很多，从简单的库所/变迁网，到有色网，到更复杂的Petri网，如：对象Petri网、随机Petri网、时间Petri网……
越复杂的Petri网模型往往具有越强的建模能力，但是同时也削弱了其模拟、分析和验证的能力，并且不具备足够的简洁、有效性。所以，我们需要找一种适用于描述体系结构的Petri网模型来使用，既要有足够的建模能力，又要简洁以满足模拟的需要。
2.1 基本模型
Petri网的基本元素是：Token、库所和变迁（包括输入弧、输出弧）。
CPU中的通用寄存器、指令寄存器和内存等部件包含了指令、寄存器值和内存值等数据，这些信息需要保存在Petri网的Token中。Token是最适合存放变化的数据的Petri网元素。
寄存器堆、内存、流水步间寄存器等部件是存储上述数据的地方；而Petri网中Token是存放在库所中的。所以这些部件就建模成Petri网的库所。
每一个流水步的执行中，数据发生了变化，所以对应于Petri网的变迁（数据的变化由Token的变化表示出来）。我们很自然地把每个流水步建模成一个变迁。

从描述能力上来说，有色网[3]基本能够满足我们的需求。但是由于CPU等建模对象的复杂性，使得用有色网建模得到的模型会比较复杂：有很多库所；一个变迁要涉及到许多Token。所以，我们在有色网的基础上，向对象网[5][6][6]的方向作一些扩展，使得模型简洁一些，也减少了建模中可能出现的错误。
具体的扩展为：一个Token中可以包含多个属性值（有色网的一个Token中只有一个属性值）。
举例来说：一个有色网的Token可以是红、黄、蓝三种颜色之一；一个对象网的Token除了具有颜色的属性（可以是红、黄、蓝中任一种颜色）之外，还可以具有大小的属性（可以是大、中或小的）。
2.2 并发特性
Petri网具有并发的特性，所以它可以很自然地描述多个流水步的并发操作。
但是普通的Petri网并没有对可同时触发的变迁的触发次序做出规定，而我们要建模的CPU的指令执行方式是顺序发射顺序执行，因此就会引出如下图的问题。

图2.1 顺序错乱的指令执行示意图
上面的示意图中有两个流水步，两个流水步的变迁的触发条件都是从输入弧中输入任何一个Token，输出还是该Token。
在时刻1，流水线中有两条指令：黑色的Token代表的指令执行顺序在前，且完成了第一个流水步；灰色的Token代表的指令执行顺序在后。此时，流水步1和流水步2这两个变迁都可以触发。在没有规定触发发生的顺序的前提下，有可能会发生流水步2先触发的情况。触发之后就是时刻2的情形。
在时刻2，两个Token（指令）都在第二个库所中。此时，流水步2既可以绑定黑色的Token触发，也可以绑定灰色的Token触发。在未规定其触发顺序的情况下，就有可能先绑定灰色Token触发，成为时刻3的情形。这样顺序靠后的灰色Token就先于黑色的Token完成了两个流水步。但是，这种情况是我们所不希望看到的。
所以，我们必须要进一步做出某种限制，来避免这种情况的发生。

通过上述的例子的分析过程，我们可以发现2种途径来避免其发生：
(1) 在任意时刻，都并发触发尽可能多的变迁。
(2) 在库所中给Token建立一个先进先出队列。库所中先加入的Token必须被先取走。
第一种方案中的“尽可能”多不是最大值的意思，而是极大值的意思。相当于对任意随机选择的可触发的Token，先把它的每条输入弧上需要的Token都取走，而不马上产生输出弧上应该产生的新Token，然后继续随机挑选一个可以触发的变迁，重复此操作，直到找不到可触发的变迁为止。当不能再触发变迁时，把前面积累下来的未及时生成的Token添加到相应的库所中，开始下一轮。它的优点是变迁并发触发与流水线并发执行的本质完全吻合；它的缺点是模拟的时候增加了一些要求，需要模拟器配合实现。
第二种方案中，选用的Petri网模型也有比较大的变动。它还有一个缺点是，不能要求所有的库所都先进先出。因为对一些与流水线操作无直接关系的部分，比如寄存器堆，不能要求它们中的Token也必须先进先出。其结果就是，我们仅对部分库所规定Token要先进先出。Petri网模型变得很复杂，不是我们所希望的。
综合之后，我们推荐第一种方案。使用第一种方案给建模带来了一个限制——每个流水步只能经过一个变迁。下一章的部分就介绍怎么克服这个限制。

3 建模
对CPU建模是一项比较大的工程，不可能一蹴而就。把目标机部件逐个进行建模，使得建模结果与目标机部件能够一一对应，既是一种常规的建模思路，也能避免建模过程中的遗漏。
在建模的过程中，可能会有一些部件难以构建得和目标机设计完全一致。此时可以做一些小的改变，但必须十分小心。一定要保证在整体上和目标机设计是一致的。
3.1 内存访问
因为内存中的数据是可变的，所以我们把内存设计为一个Token。它是一个相当大的Token，包含了许多属性，每一个属性对应了一个内存中的一个字节。
在需要读写内存数据的流水步里，我们为了能够对内存数据进行操作，就必须在该流水步对应的变迁中把内存Token从内存库所中取出来。然后，我们可以从中读取一个字节为其他的Token设置值，或者修改它的某一位的值。最后，我们要把内存Token放回内存库所中，使得以后能够继续访问内存。

图3.1 内存访问建模示意图
因为一个Token在一个时刻不能同时被两个变迁取走，所以在这样的设计中，同一时刻只能有一个流水步访问内存。当有两个流水步需要同时访问内存的时候，就必须把其中的一个暂停，以避免访问冲突。我们拿来建模的目标机本身就有这种内存访问互斥的性质，它的设计中已经包含了内存访问互斥的处理，所以不需要我们在建模的时候做特殊处理，只要把它的设计完全表示出来即可。
3.2 通用寄存器堆访问
寄存器堆的建模可以参照内存建模。但是，两者之间也有一些差异：
l 存储的数据量上的差异：内存中存储的数据很多，在M数量级以上；寄存器堆中存储的数据一般就几十个。
l 访问方式上的差异：一个时刻只能访问一个内存数据；在寄存器堆中，一个时刻能够读写多个不同寄存器的值。
如果我们完全照搬内存的建模方式，用一个Token来保存所有通用寄存器的值，那么它就不能满足我们的需求——多个流水步（变迁）可能需要同时访问通用寄存器堆 在经典5级流水的译码和写回步都需要访问通用寄存器。
。
所以，我们需要作出一些变化。把每个通用寄存器的值保存在一个Token中，其中有两个字段（属性），第一个字段标识寄存器的编号，第二个字段记录寄存器的值。这样在寄存器堆中就有多个Token。满足了并发访问多个寄存器的需求。
需要注意的是，在该模型下仍然不能同时读写同一个寄存器，因为含有该寄存器的值的Token只有一个，不可能同时取出两个来。如果我们需要在一个流水步（变迁）中访问两个寄存器 在译码ID流水步就有这样的需要。
，这两个寄存器可能是不同的也可能是相同的，就需要在建模的时候用一点技巧。

图3.2 同时读取两个寄存器的值的模型示意图
上图中，白色的Token为寄存器Token，第一个数值是寄存器的编号，第二个是寄存器的值。黑色的Token是要读取值的寄存器的标号，范围在0~3。
变迁有两类绑定，分别对应每一条弧上的上下两行。第一类绑定是要读取的两个寄存器是同一个的情况，它们的编号都是n1。在这类绑定下只要将编号为n1的寄存器Token取出，得到它的值后再放回。第二类绑定是读取两个不同的寄存器n1和n2的值，这是一般的情况。在这类绑定下要从寄存器堆库所中将编号为n1的寄存器Token和编号为n2的寄存器Token都取出，得到它们的值后再放回。
上面讨论的是在一个变迁中需要访问两个寄存器的情况。如果是在两个变迁中都需要访问内存，则必须在建模时让两个变迁不会去同时访问同一个寄存器，否则在模拟时就可能发生意外。具体内容将在后面讨论。
3.3 控制信号的争夺
因为信号所表示的值只能通过Token进行传递。一个流水段对应的变迁想要获得某个信号，就必须把包含这个信号的Token作为变迁输入。但是一个Token在一个时刻只能作为一个变迁的输入。当有多个流水段需要同时读取一个信号值时，就会产生多个变迁争夺一个Token的情况。为了使得各流水段可以并发执行，我们需要把这个信号复制多份，也就是把这个Token复制多份。同时，为了避免不必要的混淆，我们把存放这些Token的库所也复制多份，每个库所（及其中的Token）负责向一个需要读取该信号的流水段提供信号值。
3.4 数据的访问冲突
上一小结的方法可以解决一个信号被多个流水段用到的问题，但是这些信号都只是一次性使用的。这种方法对访问 访问是指在一个变迁中，需要先从一个库所中取出包含数据的Token，进行操作后，再放回原来的库所。
内存、通用寄存器等部件中的数据的操作不适用。
试想如果我们把某通用寄存器Token也复制一份，供两个变迁（流水步）同时各取走一个。那么当我们要修改寄存器的值时，就要把两个Token都取来，修改他们的值属性。这样，当我们需要同时读和写同一寄存器时，还是会发生访问冲突。所以，这不是一个正确的解决方法。
要解决该问题，必须对多个存在访问冲突可能的变迁（流水步）进行协同设计，排定一个优先级。将高优先级的变迁在下一时刻要访问的资源的编号 资源编号是一个控制信号。
传递过来 传递的方法参见3.3节。
，作为变迁T的一个输入。然后通过变迁守卫确保在下一时刻T不会和高优先级的变迁争用同一个数据资源。
3.5 数据的选择性写入
向一个寄存器写入数据的操作的建模结果是：变迁触发后，向表示寄存器的库所输出一个Token，该Token含有要写入的值。
如果一个寄存器的写入值有两个来源，需要通过一个控制信号来决定究竟选择哪个写入时，我们就要根据信号的值，决定究竟向库所中放入哪个Token。需要注意，我们只能放入一个Token。如果两个写入值是在同一个变迁中计算得到的，那么我们可以在输出赋值部分用条件判断语句来进行区别，只产生包含实际选用值的一个Token。
如果两个写入值来自于不同的变迁的输出，情况就有点复杂了。为了要得到可能的写入值，两个Token都必须生成，但是它们又不能都输出到一个库所中，因为只有一个是有效的。
这样的情况发生在PC寄存器上，通过一个二路选择器，PC寄存器的值有可能来自于IF流水步（上一个PC+指令字长），也可能来自于EX流水步（跳转地址）。
由于我们不容易协调究竟让哪个流水步的变迁向该寄存器的库所输出Token，所以我们只能把该寄存器（库所）一拆为二，每个负责接收一路数据值。对需要读取该寄存器的值的变迁，分拆后的两个库所均作为它的输入，各输入一个Token，并且把数据选择信号传送到这个变迁中。此时再根据情况选择正确的数据。相当于把数据选择滞后了一拍。

4 小结和展望
在建模的过程中，各种控制信号可能是最令人头疼的，经常会顾此失彼。在涉及控制信号的建模时，保证每个存储信号的库所中始终只有一个Token，会减少产生错误的可能。
从使用的Petri网模型的角度来说，我们现在使用的只是有色网的一个加强，对一些数据进行了组合，还没有到对象网的水平。为了能使得建模后的结果更简洁，我们还需要加强数据封装性，向对象网靠拢。
从Petri网层次[3]的角度来说，我们可以把每个流水段对应一个变迁的建模结果看成第一层。如果我们把第一层中的每个变迁继续细化，细化后的模型能更好地与目标机中的每个部件对应起来。需要注意的是，如2.2节所述，在执行时必须保持在第一层次上变迁的并发触发。
在这次实验的过程中，我们做了一个Petri网模拟器，用来执行建模得到的Petri网，帮助验证模型的正确性。今后，我们打算用一些其他的Petri网工具作一些编辑、验证等工作。其途径就是用PNML（Petri Net Markup Language）[7]来描述我们的建模结果。PNML是一种被广泛接受的Petri网描述语言，被许多Petri网工具所支持。
有了这次实践作为基础，下一步我们就可以尝试用Petri网对更复杂的、更有应用价值的目标机进行建模。

References:
[1] T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 1989, Vol. 77, No 4, pp. 541-580.
[2] J. Peterson. Petri Net Theory and the Modeling of Systems. Englewood Cliffs, NJ: Prentice-Hall, 1981.
[3] Claude Girault, Rüdiger Valk. Petri Nets for Systems Engineering, A Guide to Modeling, Verification, and Applications(王生原，余鹏，霍金键译). 北京：电子工业出版社, 2005.
[4] R.Valk. Petri Nets as Token Objects—An Introduction to Elementary Object Nets. Proceedings of 19th International Conference on the Application and Theory of Petri Nets, 1998, pp. 1-25.
[5] CA Lakos. From Coloured Petri Nets to Object Petri Nets. Proceedings of 16th International Conference on the Application and Theory of Petri Nets, 1995, pp. 278-297.
[6] C.Sibertin-Blanc. Cooperative Nets. Proceedings of 15th International Conference on the Application and Theory of Petri Nets. LNCS 815, Zaragoza, Spain, Springer-Verlag, 1994, pp 471-490.
[7] J Billington, et al. Petri Net Markup Language: Concepts, Technology, and Tools. Proc. Int'l Conf. Applications and Theory of Petri Nets 2003, W. van der Aalst and E. Best eds., LNCS, vol. 2679, Springer, 2003, pp. 483--505.