Wyniki wyszukiwania - BazTech

1

Persistent and Nonviolent Steps and the Design of GALS Systems

Fernandes J., Koutny M., Mikulski Ł, Pietkiewicz-Koutny M., Sokolov D., Yakovlev A.

Fundamenta Informaticae

|

2015

|

Vol. 137, nr 1

143--170

EN

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.

2

Flat Arbiters

Mokhov A., Khomenko V., Yakovlev A.

Fundamenta Informaticae

|

2011

|

Vol. 108, nr 1/2

63-90

EN

A new way of constructing N-way arbiters is proposed. The main idea is to perform arbitrations between all pairs of requests, and then make decision on what grant to issue based on their outcomes. Crucially, all the mutual exclusion elements in such an arbiter work in parallel. This ‘flat’ arbitration is prone to new threats such as formation of cycles (leading to deadlocks), but at the same time opens up new opportunities for designing arbitration structures with different decision policies due to the availability of the global order relation between requests. To facilitate resolution of such cycles and further developments in the context of flat arbitration, the paper presents new theoretical results, including a proof of correctness of a generic structure for the N-way arbiter decision logic. In particular, in some situations a request that lost some pairwise arbitrations has to be granted to avoid a deadlock.

3

Synthesis of Nets with Step Firing Policies

Darondeau P., Koutny M., Pietkiewicz-Koutny M., Yakovlev A.

Fundamenta Informaticae

|

2009

|

Vol. 94, nr 3/4

275-303

EN

The unconstrained step semantics of Petri nets is impractical for simulating and modelling applications. In the past, this inadequacy has been alleviated by introducing various flavours of maximally concurrent semantics, as well as priority orders. In this paper, we introduce a general way of controlling step semantics of Petri nets through step firing policies that restrict the concurrent behaviour of Petri nets and so improve their execution and modelling features. In a nutshell, a step firing policy disables at each marking a subset of enabled steps which could otherwise be executed. We discuss various examples of step firing policies and then investigate the synthesis problem for Petri nets controlled by such policies. Using generalised regions of step transition systems, we provide an axiomatic characterisation of those transition systems which can be realised as reachability graphs of Petri nets controlled by a given step firing policy. We also provide two different decision and synthesis algorithms for PT-nets and step firing policies based on linear rewards of steps, where the reward for firing a single transition is either fixed or it depends on the current net marking. The simplicity of the algorithms supports our claim that the proposed approach is practical.

4

Resolution of Encoding Conflicts by Signal Insertion and Concurrency Reduction Based on STG Unfoldings

Khomenko V., Madalinski A., Yakovlev A.

Fundamenta Informaticae

|

2008

|

Vol. 86, nr 3

299-323

EN

A combined framework for the resolution of encoding conflicts in STG unfoldings is presented, which extends previouswork by incorporating concurrency reduction in addition to signal insertion. Furthermore, a novel validity condition is proposed to justify these transformations. The method has been implemented in the CONFRES tool and applied to a number of case studies. The experimental results show that the combined framework enlarges the design space and allows for better exploration of the speed/area tradeoff.

5

Analysis of Static Data Flow Structures

Sokolov D., Poliakov I., Yakovlev A.

Fundamenta Informaticae

|

2008

|

Vol. 88, nr 4

581-610

EN

A token-based model for asynchronous data path, called static data flow structures (SDFS), is formally defined. Three token game semantics are introduced for this model, namely atomic token, spread token and counterflow. The SDFS semantics are analysed using a simple benchmark example; their advantages and drawbacks are highlighted. A combination of spread token and counterflow models, which employs the advantages of both, is presented. A technique is described for mapping the high-level SDFS token game semantics into the low level of underlying Petri nets (PNs). The PNs are employed as a back-end for verification of SDFS models. For analysis and comparison of SDFS semantics a software tool has been developed, which integrates all SDFS semantics into a consistent framework, implements their conversion into PNs and provides an interface to existing model checking tools.

6

Automating Synthesis of Asynchronous Communication Mechanisms

Gorgônio K., Xia F., Yakovlev A.

Fundamenta Informaticae

|

2007

|

Vol. 78, nr 1

75-100

EN

Asynchronous data communication mechanisms (ACMs) have been extensively studied as data connectors between independently timed processes in digital systems. In previous work, systematic ACM synthesis methods have been proposed. In this paper, we advance this work by developing algorithms and software tools which automate most of the ACM synthesis process. Firstly, an interleaving specification is constructed in the form of a state graph, and secondly, a Petri net model of an "ACM-type" is derived using the theory of regions. The method is applied to a number of "standard" writing and reading policies of ACMs with shared memory and unidirectional control variables.

7

Logic Synthesis for Asynchronous Circuits Based on STG Unfoldings and Incremental SAT

Khomenko V., Koutny M., Yakovlev A.

Fundamenta Informaticae

|

2006

|

Vol. 70, nr 1,2

49-73

EN

The behaviour of asynchronous circuits is often described by Signal Transition Graphs (STGs), which are Petri nets whose transitions are interpreted as rising and falling edges of signals. One of the crucial problems in the synthesis of such circuits is deriving equations for logic gates implementing each output signal of the circuit. This is usually done using reachability graphs. In this paper, we avoid constructing the reachability graph of an STG, which can lead to state space explosion, and instead use only the information about causality and structural conflicts between the events involved in a finite and complete prefix of its unfolding. We propose an efficient algorithm for logic synthesis based on the Incremental Boolean Satisfiability (SAT) approach. Experimental results show that this technique leads not only to huge memory savings when compared with the methods based on reachability graphs, but also to significant speedups in many cases, without affecting the quality of the solution.

8

Buffered Asynchronous Communication Mechanisms

Xia F., Hao F., Clark I., Yakovlev A., Chester E.G.

Fundamenta Informaticae

|

2006

|

Vol. 70, nr 1,2

155-170

EN

Previous work on asynchronous communication mechanisms (ACMs) has not dealt with buffered forms (with the number of data cells n>1). This paper describes a systematic design/synthesis process for ACMs with arbitrary buffer size, a series of resulting buffered ACM algorithms, and the modelling and simulation of these ACMs using Matlab, putting ACMs (esp. buffered ones) in the context of complex engineering systems.

9

Detecting State Encoding Conflicts in STG Unfoldings Using SAT

Khomenko V., Koutny M., Yakovlev A.

Fundamenta Informaticae

|

2004

|

Vol. 62, nr 2

221--241

EN

The behaviour of asynchronous circuits is often described by Signal Transition Graphs (STGs), which are Petri nets whose transitions are interpreted as rising and falling edges of signals. One of the crucial problems in the synthesis of such circuits is that of identifying whether an STG satisfies the Complete State Coding (CSC) requirement (which states that semantically different reachable states must have different binary encodings), and, if necessary, modifying the STG (by, e.g., inserting new signals helping to trace the current state) to meet this requirement. This is usually done using reachability graphs. In this paper, we avoid constructing the reachability graph of an STG, which can lead to state space explosion, and instead use only the information about causality and structural conflicts between the events involved in a finite and complete prefix of its unfolding. We propose an efficient algorithm for detection of CSC conflicts based on the Boolean Satisfiability (SAT) approach. Following the basic formulation of the state encoding conflict relationship, we present some problem-specific optimization rules. Experimental results show that this technique leads not only to huge memory savings when compared to the CSC conflicts detection methods based on reachability graphs, but also to significant speedups in many cases.