Advances in microelectronics allow the integration of more andmore functionality on a single chip. Emerging system-on-a-chiparchitectures include a large amount of heterogeneous componentsand are of increasing complexity. Applications using thesearchitectures require many low-level details in order to yield anefficient implementation. On the other hand constanttime-to-market pressure on electronic systems demands a shortdesign process that allows to model a system at a highabstraction level, not taking low-level implementation detailsinto account. Clearly there is a significant abstraction gapbetween an ideal model for specification and another one forimplementation. This abstraction gap has to be addressed bymethodologies for electronic system design. This thesis presents the ForSyDe (Formal System Design)methodology, which has been developed with the objective to movesystem design to a higher level of abstraction and to bridge theabstraction gap by transformational design refinement. ForSyDe isbased on carefully selected formal foundations. The initialspecification model uses a synchronous model of computation,which separates communication from computation and has anabstract notion of time. ForSyDe uses the concept of processconstructors to implement the synchronous model, to allow fordesign transformation and the mapping of a refined model onto thetarget architecture. The specification model is refined into adetailed implementation model by the stepwise application ofwell-defined design transformation rules. These rules are eithersemantic preserving or they inflict a design decision modifyingthe semantics. These design decisions are used to introduce thelow-level implementation details that are needed for an efficientimplementation. The implementation model is mapped onto thecomponents of the target architecture. At present ForSyDe modelscan be mapped onto VHDL or C/C++ in order to allow commercialtools to generate custom hardware or sequential software. Thethesis uses a digital equalizer to illustrate the concepts andpotential of ForSyDe. Electronic System Design, Hardware/Software Co-Design,Electrical Engineering

Today's advanced digital devices are enormously complex and incorporate many functions. In order to capture the system functionality and to be able to analyze the needs for a final implementation more efficiently, the entry point of the system development process is pushed to a higher level of abstraction. System level design methodologies describe the initial system model without considering lower level implementation details and the objective of the design development process is to introduce lower level details through design refinement. In practice this kind of refinement process may entail non-semantic-preserving changes in the system description, and introduce new behaviors in the system functionality. In spite of new behaviors, a model formed by the refinement may still satisfy the design constraints and to realize the expected system. Due to the size of the involved models and the huge abstraction gap, the direct verification of a detailed implementation model against the abstract system model is quite impossible. However, the verification task can be considerably simplified, if each refinement step and its local implications are verified separately. One main idea of the Formal System Design (ForSyDe) methodology is to break the design process into smaller refinement steps that can be individually understood, analyzed and verified. The topic of this thesis is the verification of refinement steps in ForSyDe and similar methodologies. It proposes verification attributes attached to each non-semantic-preserving transformation. The attributes include critical properties that have to be preserved by transformations. Verification properties are defined as temporal logic expressions and the actual verification is done with the SMV model checker. The mapping rules of ForSyDe models to the SMV language are provided. In addition to properties, the verification attributes include abstraction techniques to reduce the size of the models and to make verification tractable. For computation refinements, the author defines the polynomial abstraction technique, that addresses verification of DSP applications at a high abstraction level. Due to the size of models, predefined properties target only the local correctness of refined design blocks and the global influence has to be examined separately. In order to compensate the influence of temporal refinements, the thesis provides two novel synchronization techniques. The proposed verification and synchronization techniques have been applied to relevant applications in the computation area and to communication protocols. / QC 20100816

<p>Advances in microelectronics allow the integration of more andmore functionality on a single chip. Emerging system-on-a-chiparchitectures include a large amount of heterogeneous componentsand are of increasing complexity. Applications using thesearchitectures require many low-level details in order to yield anefficient implementation. On the other hand constanttime-to-market pressure on electronic systems demands a shortdesign process that allows to model a system at a highabstraction level, not taking low-level implementation detailsinto account. Clearly there is a significant abstraction gapbetween an ideal model for specification and another one forimplementation. This abstraction gap has to be addressed bymethodologies for electronic system design.</p><p>This thesis presents the ForSyDe (Formal System Design)methodology, which has been developed with the objective to movesystem design to a higher level of abstraction and to bridge theabstraction gap by transformational design refinement. ForSyDe isbased on carefully selected formal foundations. The initialspecification model uses a synchronous model of computation,which separates communication from computation and has anabstract notion of time. ForSyDe uses the concept of processconstructors to implement the synchronous model, to allow fordesign transformation and the mapping of a refined model onto thetarget architecture. The specification model is refined into adetailed implementation model by the stepwise application ofwell-defined design transformation rules. These rules are eithersemantic preserving or they inflict a design decision modifyingthe semantics. These design decisions are used to introduce thelow-level implementation details that are needed for an efficientimplementation. The implementation model is mapped onto thecomponents of the target architecture. At present ForSyDe modelscan be mapped onto VHDL or C/C++ in order to allow commercialtools to generate custom hardware or sequential software. Thethesis uses a digital equalizer to illustrate the concepts andpotential of ForSyDe.</p><p>Electronic System Design, Hardware/Software Co-Design,Electrical Engineering</p>

Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. These algorithms take advantage of suitable representations of the Boolean functions in order to be efficient. The first two algorithms compute simple-disjoint and disjoint-support decompositions. They are based on representing the target function by a Reduced Ordered Binary Decision Diagram (BDD). Unlike other BDD-based algorithms, the presented ones can deal with larger target functions and produce more decompositions without requiring expensive manipulations of the representation, particularly BDD reordering. The third algorithm also finds disjoint-support decompositions, but it is based on a technique which integrates circuit graph analysis and BDD-based decomposition. The combination of the two approaches results in an algorithm which is more robust than a purely BDD-based one, and that improves both the quality of the results and the running time. The fourth algorithm uses circuit graph analysis to obtain non-disjoint decompositions. We show that the problem of computing non-disjoint decompositions can be reduced to the problem of computing multiple-vertex dominators. We also prove that multiple-vertex dominators can be found in polynomial time. This result is important because there is no known polynomial time algorithm for computing all non-disjoint decompositions of a Boolean function. The fifth algorithm provides an efficient means to decompose a function at the circuit graph level, by using information derived from a BDD representation. This is done without the expensive circuit re-synthesis normally associated with BDD-based decomposition approaches. Finally we present two publications that resulted from the many detours we have taken along the winding path of our research.

Functional decomposition aims at finding efficient representations for Boolean functions. It is used in many applications, including multi-level logic synthesis, formal verification, and testing. This dissertation presents novel heuristic algorithms for functional decomposition. These algorithms take advantage of suitable representations of the Boolean functions in order to be efficient. The first two algorithms compute simple-disjoint and disjoint-support decompositions. They are based on representing the target function by a Reduced Ordered Binary Decision Diagram (BDD). Unlike other BDD-based algorithms, the presented ones can deal with larger target functions and produce more decompositions without requiring expensive manipulations of the representation, particularly BDD reordering. The third algorithm also finds disjoint-support decompositions, but it is based on a technique which integrates circuit graph analysis and BDD-based decomposition. The combination of the two approaches results in an algorithm which is more robust than a purely BDD-based one, and that improves both the quality of the results and the running time. The fourth algorithm uses circuit graph analysis to obtain non-disjoint decompositions. We show that the problem of computing non-disjoint decompositions can be reduced to the problem of computing multiple-vertex dominators. We also prove that multiple-vertex dominators can be found in polynomial time. This result is important because there is no known polynomial time algorithm for computing all non-disjoint decompositions of a Boolean function. The fifth algorithm provides an efficient means to decompose a function at the circuit graph level, by using information derived from a BDD representation. This is done without the expensive circuit re-synthesis normally associated with BDD-based decomposition approaches. Finally we present two publications that resulted from the many detours we have taken along the winding path of our research. / QC 20100909