Persistent and Nonviolent Steps and the Design of GALS Systems
Persistent and Nonviolent Steps and the Design of GALS Systems
复制标题
持久和非暴力步骤以及 GALS 系统的设计
DOI：
10.3233/fi-2015-1173
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
Alex Yakovlev
中科院分区：
文献类型：
--
作者：
Lukasz Mikulski;Marta Pietkiewicz-Koutny;Danil Sokolov;Alex Yakovlev
如果在整个操作过程中，启用的活动不能随后被任何其他活动阻止执行，则并发系统是持久的。这通常是非常理想的甚至是必要的属性；特别是，如果系统要以硬件实现。在过去的 40 年里，持久性已经被研究并应用于实际实现中，假设每个活动都是单个原子操作，例如可以通过 Petri 网的单个转换来表示。在本文中，我们研究了 VLSI 电路背景下 GALS 全局异步局部同步系统的行为。系统的规范以 Petri 网的形式给出。我们的目标是通过将并发事件分组在一起来重新设计系统以优化信号管理。查看给定 Petri 网的并发可达性图，我们有兴趣发现出现在“捆绑包”中的事件，以便它们都可以在单个时钟周期内执行。捆绑包的最佳候选者是在相同配置中一遍又一遍地出现和重新出现的事件集，形成“持久”事件集。到目前为止，仅在顺序语义的背景下考虑持久性。在本文中，我们转向基于步骤的执行领域，不仅考虑持久性且不能被其他步骤禁用的步骤，而且还考虑非暴力且不能禁用其他步骤的步骤。然后，我们引入了捆绑的正式定义，并提出了一种算法来修剪系统的行为，以便只保留捆绑的步骤。修剪后的可达性图代表了重新设计的系统的行为，而该系统又可以使用网络综合的标准技术在新的 Petri 网络中实现。所提出的算法修剪持久网络和安全网络的可达性图，留下代表最大并发步骤的束。
A concurrent system is persistent if throughout its operation no activity which became enabled can subsequently be prevented from being executed by any other activity. This is often a highly desirable or even necessary property; in particular, if the system is to be implemented in hardware. Over the past 40 years, persistence has been investigated and applied in practical implementations assuming that each activity is a single atomic action which can be represented, for example, by a single transition of a Petri net. In this paper we investigate the behaviour of GALS Globally Asynchronous Locally Synchronous systems in the context of VLSI circuits. The specification of a system is given in the form of a Petri net. Our aim is to re-design the system to optimise signal management, by grouping together concurrent events. Looking at the concurrent reachability graph of the given Petri net, we are interested in discovering events that appear in 'bundles', so that they all can be executed in a single clock tick. The best candidates for bundles are sets of events that appear and re-appear over and over again in the same configurations, forming 'persistent' sets of events. Persistence was considered so far only in the context of sequential semantics. In this paper, we move to the realm of step based execution and consider not only steps which are persistent and cannot be disabled by other steps, but also steps which are nonviolent and cannot disable other steps. We then introduce a formal definition of a bundle and propose an algorithm to prune the behaviour of a system, so that only bundled steps remain. The pruned reachability graph represents the behaviour of a re-engineered system, which in turn can be implemented in a new Petri net using the standard techniques of net synthesis. The proposed algorithm prunes reachability graphs of persistent and safe nets leaving bundles that represent maximally concurrent steps.
登录
查看更多内容
DOI：
10.1145/322077.322079
发表时间：
1978-07
期刊：
J. ACM
影响因子：
--
作者：
L. Landweber;E. Robertson
通讯作者：
L. Landweber;E. Robertson
DOI：
10.1007/978-3-642-38697-8_11
发表时间：
2013-06
期刊：
--
影响因子：
--
作者：
Johnson Fernandes;M. Koutny;Marta Pietkiewicz-Koutny;D. Sokolov;A. Yakovlev
通讯作者：
Johnson Fernandes;M. Koutny;Marta Pietkiewicz-Koutny;D. Sokolov;A. Yakovlev
DOI：
10.1007/978-3-642-38697-8_12
发表时间：
2013-06
期刊：
--
影响因子：
--
作者：
M. Koutny;Lukasz Mikulski;Marta Pietkiewicz-Koutny
通讯作者：
M. Koutny;Lukasz Mikulski;Marta Pietkiewicz-Koutny
DOI：
10.1016/j.entcs.2009.07.028
发表时间：
2009-08
期刊：
--
影响因子：
--
作者：
S. Dasgupta;A. Yakovlev
通讯作者：
S. Dasgupta;A. Yakovlev
DOI：
--
发表时间：
2010-10
期刊：
--
影响因子：
--
作者：
Jens Spars;Steve B. Furber
通讯作者：
Jens Spars;Steve B. Furber