Structural Decomposition of STGs

• Specification of asynchronous circuit behaviour becomes more complex as the complexity of today’s System-On-a-Chip (SOC) design increases. This also causes the Signal Transition Graphs (STGs) – interpreted Petri nets for the specification of asynchronous circuit behaviour – to become bigger and more complex, which makes it more difficult, sometimes even impossible, to synthesize an asynchronous circuit from an STG with a tool like petrify [CKK+96] or CASCADE [BEW00]. It has, therefore, been suggested to decompose the STG as a first step; this leads to a modular implementation [KWVB03] [KVWB05], which can reduce syn- thesis effort by possibly avoiding state explosion or by allowing the use of library elements. A decomposition approach for STGs was presented in [VW02] [KKT93] [Chu87a]. The decomposition algorithm by Vogler and Wollowski [VW02] is based on that of Chu [Chu87a] but is much more generally applicable than the one in [KKT93] [Chu87a], and its correctness has been proved formally in [VW02]. This dissertation begins with Petri net background described in chapter 2. It starts with a class of Petri nets called a place/transition (P/T) nets. Then STGs, the subclass of P/T nets, is viewed. Background in net decomposition is presented in chapter 3. It begins with the structural decomposition of P/T nets for analysis purposes – liveness and boundedness of the net. Then STG decomposition for synthesis from [VW02] is described. The decomposition method from [VW02] still could be improved to deal with STGs from real applications and to give better decomposition results. Some improvements for [VW02] to improve decomposition result and increase algorithm efficiency are discussed in chapter 4. These improvement ideas are suggested in [KVWB04] and some of them are have been proved formally in [VK04]. The decomposition method from [VW02] is based on net reduction to find an output block component. A large amount of work has to be done to reduce an initial specification until the final component is found. This reduction is not always possible, which causes input initially classified as irrelevant to become relevant input for the component. But under certain conditions (e.g. if structural auto-conflicts turn out to be non-dynamic) some of them could be reclassified as irrelevant. If this is not done, the specifications become unnecessarily large, which intern leads to unnecessarily large implemented circuits. Instead of reduction, a new approach, presented in chapter 5, decomposes the original net into structural components first. An initial output block component is found by composing the structural components. Then, a final output block component is obtained by net reduction. As we cope with the structure of a net most of the time, it would be useful to have a structural abstraction of the net. A structural abstraction algorithm [Kan03] is presented in chapter 6. It can improve the performance in finding an output block component in most of the cases [War05] [Taw04]. Also, the structure net is in most cases smaller than the net itself. This increases the efficiency of the decomposition algorithm because it allows the transitions contained in a node of the structure graph to be contracted at the same time if the structure graph is used as internal representation of the net. Chapter 7 discusses the application of STG decomposition in asynchronous circuit design. Application to speed independent circuits is discussed first. Af- ter that 3D circuits synthesized from extended burst mode (XBM) specifications are discussed. An algorithm for translating STG specifications to XBM specifi- cations was first suggested by [BEW99]. This algorithm first derives the state machine from the STG specification, then translates the state machine to XBM specification. An XBM specification, though it is a state machine, allows some concurrency. These concurrencies can be translated directly, without deriving all of the possible states. An algorithm which directly translates STG to XBM specifications, is presented in chapter 7.3.1. Finally DESI, a tool to decompose STGs and its decomposition results are presented.

Weitere Dienste

Verfasserangaben: Benedictus Benyamin Kangsah urn:nbn:de:hbz:386-kluedo-39991 Jochen Beister Dissertation Englisch 23.02.2015 2015 Technische Universität Kaiserslautern Technische Universität Kaiserslautern 11.07.2014 26.02.2015 X, 141 Fachbereich Elektrotechnik und Informationstechnik 0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik 6 Technik, Medizin, angewandte Wissenschaften / 620 Ingenieurwissenschaften und Maschinenbau Standard gemäß KLUEDO-Leitlinien vom 13.02.2015

$Rev: 13581$