TOLEDO'97

Tutorial A-B:
Quality-driven Design of Electronic Systems

Speaker

Abstract

The importance of the electronic system's market, technology revolution, explosion of new market competitors, high requirements of embedded systems, and many other factors create a situation in which the quality-driven design is a necessity. The aim of this tutorial is to provide and discuss some theoretical and methodological foundations of the quality-driven design and to consider some implications of the modern quality concepts on design exploration techniques, design decision making, design reuse and design validation. The tutorial will be illustrated with examples from the field of system-level design and logic design.

Contents

  1. Introduction
  2. Quality Definitions
  3. Quality Models
  4. Quality-driven Design
  5. Design System
  6. Quality-Driven Design Space Exploration
  7. Design Decision Making
  8. Design Validation
  9. Design Reuse
  10. Conclusion

Extended Abstract

Electronic systems play a remarkable role in today's life. They are used in virtually all fields of human activity: at home, in office, hospital, shop, bank, factory, plain, car etc. The social expectations related to them are growing rapidly. Furthermore, the share of application and customer-specific systems with low or medium production volumes continues to grow and the critical character and complexity of numerous embedded systems (e.g. measurement and control systems in military, nuclear, plant, space, avionic, automotive and medical instrumentation) impose extremely high quality requirements. The effectiveness and efficiency of designing is extremely important for this class of systems. Finally, the technology revolution, the importance of the electronic system application market and the explosion of new market competitors make for extremely fierce competition in the market. In this situation, some of the most important goals of industry are the reduction of costs and time to market, while simultaneously increasing the power and quality of systems. Quality-driven design is a necessity. But the task of designing high-quality, complex and powerful systems to tight schedules is quite new and difficult. As a designer community, we are beginning to acquire ideas and collect experience in this field.

The main aim of this tutorial is to provide and discuss some theoretical and methodological foundations of the quality-driven design and to show some directions for further work in this field. We try to show what is needed, why it is needed, and how can it be achieved. Another aim is to consider some important implications of the modern quality concepts on design exploration techniques and tools, design decision making, design reuse and design validation.

Actually, what is quality? Many various definitions of quality can be found in literature. Tin this tutorial, we discuss he most used and cited of them [4][5][23][26]. However, we have real problems with all these definitions. Their most serious drawbacks are the following:

None of these definitions is precise enough to enable the systematic consideration, measurement and comparison of quality, which are necessary for bringing into effect the quality-driven design.

They focus exclusively on a product being designed and do not account for design, fabrication, usage and disposal of the product; however, the engineered systems are purposive, i.e. solve a certain real-life problem, and the original problem is solved by designing, fabrication, usage and disposing of the system. Thus,the electronic system is only a kernel problem solver and all these processes together with the system form a complete problem solver. Therefore, quality must account for the total systemic solution.

They make an assumption of given, perfectly known and inviolable customer's needs (expectations, requirements), while the customer may specify the requirements poorly and such requirements may result in a system which will create danger, damage environment or squander scarce resources. For the above reasons, we proposed a new definition: quality of a purposive systemic solution is its total effectiveness and efficiency in solving the original real-life problem [39]. Here, the degree to which a solution attains its goals is called its effectiveness and the degree to which a solution uses resources in order to realize its aims is called its efficiency. Effectiveness and efficiency of a systemic solution together decide its grade of excellence. Their aggregation expresses quality. In turn, effectiveness and efficiency will be defined in terms of measurable parameters. In this way, quality can be measured and compared. The quality of a system itself can now be considered as a quality of a sub-solution of the total systemic solution and as such, it is a derivative of the total solution's quality.

However, even with this new definition of quality not all difficulties are overcome. First of all, the recognition of a design problem as well as the nature of a solution are subjective to a high degree. Secondly, design does not concern the reality as it is, but as it will possibly be realized. Moreover, the electronic system design problems are complex, multi-aspect, dynamic, and ill-structured. Their ill-structure means that: there is no definitive formulation of the problem, any problem formulation may be inconsistent, formulations of the problem are solution dependent, proposing and considering solutions is a means for understanding the problem, and there is no definitive solution to the problem. Furthermore, it is very difficult to find precise relations between various aspects of the effectiveness and between the different forms of energy and mattery used to attain the system's aim and even more difficult to express them as one uniform measure. Also, there is a trade-off as well between effectiveness and efficiency as among different their aspects. Finally, the required quality or its perception can change in time. Therefore, quality cannot be well defined, but it can and should be modelled.

Well-structured models of the required/delivered quality are extremely important. They can serve to conceptualize, denote, analyse and communicate the customer's and designer's ideas, to guide the design process, to enable the explicit and well organized design decision making, to show that the requirements and the solutions obtained with their use are meaningful and correct, to verify the design etc. The general model of the required system's quality should be formed just by the system requirements. However, not "the conformance to requirements" [4], but the solution of the current real life problem with a very high total effectiveness and efficiency is important. The requirements and the solutions obtained with their use should be confronted with the actual up-to-date needs many times during the design process, and replaced or modified, if necessary.

A model of the required quality, represented by the design requirements, models the design problem at a hand through the imposition of a number of requirements on the acceptable or preferred solutions, and so it can also be considered as an abstract model of a solution to the problem. Since such a model limits the space of acceptable or preferred solutions to a certain degree only, it models many solutions concurrently. Each of them fulfils all the hard constraints of the model, but different solutions can satisfy its objectives to various degrees. It is possible to distinguish three sorts of requirements in models of the design problems: functional, structural, and parametric (involving physical parameters, economic parameters etc.). All the three sorts of requirements in fact impose limits on the structure of a solution, but they do it in different ways. To be an acceptable quality model, the requirements must specify the system in a multi-dimensional space composed of functional, structural, and parametric characteristics related to all the important system life-cycle aspects. They must specify preferences of values of all the characteristics, expressed by hard constraints, objectives, and trade-off information [33][34][36]-[38]. Requirements constructed in such a way enable evaluation of solutions, their comparison and the exploitation of trade-offs. With such requirements the total system quality Q can be modelled as a function of utility levels of all the important system characteristics influencing the systems effectiveness or efficiency, i.e. Q=F(v1(x1(y)), ..., vn(xn(y))). Through providing data for the multi-criteria decision making [33][34][36]-[38], such requirements make it possible to apply the multi-criteria decision methods for invention and selection of solutions which are ''totally'' optimal.

Because of the complexity, poor structure and dynamic character of the design problems as well as the inherent and external sources of subjectiveness, uncertainty, inaccuracy, imprecision and risks, design has to be an evolutionary process in which the concepts of predicting and testing the internal and environmental characteristics, as well as learning and adapting, are very important. The main concepts of the quality driven design can be summarized as follows:

The quality-driven design is an evolutionary processes which applies the problem-solving framework of heuristic search. In this framework, the process of design problem solving can be represented by a design search tree, in which the tree's nodes correspond to various design issues (sub-problems). For each issue, a number of various alternative solutions, i.e. design options, are possible. A design decision is a choice of a particular option (or the option chosen). Each option chosen may recursively raise new issues, expanding the search tree downwards until a final design will be obtained. For each issue, we can construct the issue's requirements, composed of some functional, structural and parametric requirements extracted in an appropriate manner from the total quality model of the considered system. Creation of the well-structured quality models aims at structuring the design problems and enlarging the scope of the reasoning-based design decision making with open and rational procedures which can be automatized to a high degree. The quality models are considered to be heuristics for setting and controlling the course of design. Also, a decision model can be constructed for a certain issue, being a partial (reduced to only certain concerns) and abstract (reduced to the necessary and possible precision levels) model of the required quality, expressed in the decision-theoretical terms. The issue's decision model is aimed as a base for decision making in the scope of a certain issue. The decision models enable application of the multi-objective decision methods [33][34][36]-[38] for construction, improvement and selection of the most promising solutions.

For a certain design issue, a lot of alternative design solutions typically exist, but these alternatives are not known a priori. They must be constructed in the course of design and the construction process has to be guided by the quality models. Since the quality models give only a temporary and restricted reflection of the quality really required, posterior analysis should provide the necessary information for their modification and for acceptation or rejection of the results produced. The quality-driven design space exploration basically consists of the alternating phases of exploration of the space of abstract models of the required quality and exploration of the space of the more concrete issue's solutions obtained with the chosen quality models. Exploration of models of the required quality aims at answering the question: "What defines the right thing?" Exploration of issue's solutions for the chosen requirement models aims at answering the question: "What is the right way of realization of the required right thing?' In this way, both "let's make better things" and "let's make things better" are realized. In [21] we proposed a generic model of the quality-driven design space exploration that can be used for any design issue. In this tutorial, we explain this model troughly, and we show, how can it be applied to various design issues.

In result of the design space exploration, the considered system is defined as an appropriate decomposition into a network of sub-systems. Each sub-system solves a certain sub-problem and all sub-systems cooperating together solve the system design problem by exposing the external aggregate behaviour and characteristics which match the required behaviour and characteristics. The design process breaks down a complex system defined in abstract and non-precise terms into a structure of cooperating sub-systems defined in more concrete and precise terms, which are in turn further broken down to the simpler sub-systems that can be directly implemented with the elements and sub-systems at the designer's disposal.

The design process, as described above, can be treated as an evolutionary requirement engineering process which starts with abstract, imprecise, incomplete and possibly contradictory initial requirements (initial quality model) and, during the course of design, tries to transform them into concrete, precise, complete, coherent and directly implementable final requirements which define the system as well as its production, usage and recycling (final quality model). The initial quality model is more abstract and involves mostly some functional and parametric requirements and to a smaller extent and less explicitly the structural requirements. The final model defines the system and the related processes in a more concrete and precise way, and defines the system's structure explicitly. In general however, not only the required/delivered structure and behaviour should be refined during the design, but also the required/delivered values of parameters.

The concepts of the quality-driven design space exploration refer to the whole design process; however, a well organized exploration of the design space is especially important at the conceptual system-level. Design costs at the system level are becoming to be dominant in the total cost of a complex electronic system. The gains to be realized by design exploration at this level are typically much bigger than what we would get exclusively by local optimizations at the lower levels. Just the system-level decisions determine the optimization possibilities for the lower levels. But unfortunately, we have many more and much better design tools at the lover levels than at the system level. At the system-level, the assumptions made for a certain design often do not hold for other designs and this is especially apparent in the case of application specific systems. Comparing to the lower design levels at which the precise structure of the system sub-components is decided and where the design freedom is limited by the previous design decisions, the design problems at the conceptual level are typically more application specific, less structured, more complex and multi-aspectual. There are more factors influencing the design decisions, and their interrelations and impact on the design quality are more complex and more difficult to characterize. Comparing to the lower design levels, the design at the system level should be therefore much more focused on the exploration of models of the required quality, and in particular on the construction, analysis, evaluation and validation of the decision models. Thus, a different kind of design support is here crucial than that offered by the traditional CAD tools. We need methods and tools that allow designers make models at the high level and then support their refinement into the actual implementations. Recently, there is quite much ongoing research related to the system-level support for the functional and structural design aspects, but the parametric aspects are underestimated. Therefore in this tutorial, we focussed on the parametric models, and on the decision models in particular [22][26][32]-[34][36]-[38].

Models of the required quality are certainly not an objective reality. One cannot be to careful in analysing the quality of models and certainly cannot assume that because some designers use a model it must be good. To guarantee high quality of models and results obtained with their use, search in the model space is necessary. This search involves construction, analysis and evaluation of models as well as making decisions on their acceptation, rejection or improvement. In the context of the modern quality concepts, the question of model validity is not limited to the binary case: valid versus not valid. Such an answer is possible only in the case of hard constraints and certainty. However, along with hard constraints, models involve typically various objectives and trade-offs between them and involve uncertainty. Even the system's functional requirements can be considered either as hard constraints (if they must be fulfilled completely and precisely) or as objectives (if it is allowed to fulfil them to a certain degree). The question of validity should be therefore generalized to the question of the overall model quality. Design validation should be generalized to the evaluation of the design quality and decision making on design acceptation, rejection or improvement. The term "design validation" will be used in this sense further in the paper.

Design validation should include validation of design intentions represented by abstract models of the required quality and validation of the results obtained with these models and represented by more concrete models, prototypes and actual products. Since all the models, prototypes and products have a limited value, their analysis should provide information for their acceptation, rejection or evolution. Since models of the required quality are generally composed of structural, functional and parametric requirements, the design validation process should account not only for the system's function, but also for the system's structure and parameters.

A very powerful and important validation concept is represented by the formal correctness verification. Currently, four basic approaches to formal hardware verification can be distinguished: theorem proving [2],[12], model checking [3],[9],[29], the enumeration-simulation approach [6],[10],[27] and the reverse mapping approach [18]. The canonical character of ordered binary decision diagrams has also been used to verify combinational circuits [28]. In the tutorial, we briefly discuss and compare these approaches.

The formal correctness paradigm has however important limitations. It is effective exclusively for well-structured, formally modelled problems, i.e. in the abstract formal model space, but it cannot really account for the relations between the real-life problem and the model of the problem. Furthermore, most of today's correctness-evidence methods based on this paradigm are not efficient for complex problems.

On the other hand, the quality-driven design stresses the "totality" and implies usage of the most effective and efficient design methods and tools. Since the formal correctness paradigm is effective exclusively in the formal model space and the todays formal correctness evidence methods are not enough efficient for many design problems, designers must use some other validation concepts which are more efficient or cover different fields than the formal correctness. Consequently, validation should be performed when simultaneously using various validation means ranging from the formal correctness proof of models against their requirement specifications, through the simulation and emulation of models and testing of their prototype implementations, to the feedback from the production, field usage and utilization of systems. The models should be confronted with the actual needs directly, by analysing and simulating them, and indirectly, by analysing the results obtained with their use. Currently, the research effort is focussed on the functional validation. But of course, validation should be complete, in the sense that it has to involve the functional, structural and parametric validation. The tutorial will discuss briefly two concepts that found already a quite broad acceptance in the field of electronic system design, namely conceptual modelling and prototyping.

We will focus further on the decision model validation. Formal verification of the decision models is possible and should be applied. However, at least currently it is limited to a sort of "model checking", i.e. checking of some general formal properties which should have the models of a certain class. It is formulated in the decision theory for the case of utility and value function models [22][34][38]. However, this "model checking" can discover only some very general inconsistencies. Therefore, we proposed a method for the detection and analysis of the decision model inconsistencies [21][22] which will be presented in the tutorial.

The complexity of actual digital circuits increases by approximately ten times every six years. The average time to market for digital systems halves during the same period. Quality expectations also grow rapidly. In this situation, the simultaneous increase of design quality, designer productivity, and predictability of design performance and design cost and time is essential. Design reuse is one of the most important factors that enable us to deal with this situation and makes possible design and implementation of complex and matured systems to tight schedules. It is one of the most important aspects underlying quality-driven design. Our presentation of design reuse in the scope of this tutorial will be based on the material included in our recent paper on this subject [20] and some other publications [1][7][8][11][14][16][17][19][24] [25][31][35].

The tutorial will be illustrated with examples from the field of system-level design and logic design.

References

[1] W. Birmingham, A. Gupta, D. Siewiorek: The MICON System for Computer Design, Design Automation Conference, 1989.
[2] R.S. Boyer, J.S. Moore: A Computational Logic Handbook, Academic Press, 1088.
[3] O. Coudert, J.C. Madre: A Unified Framework for the Formal Verification of Sequential Circuits, ICCAD'90, Santa Clara, USA, pp. 126-129, Nov. 11-15, 1990.
[4] P.B. Crosby: Quality is Free, McGraw-Hill, New York, 1979.
[5] W.E. Deming: Out of the Crisis, MIT Centre for Advanced Engineering Studies, Cambridge MA, 1986.
[6] S. Devadas, H.K.T. Ma, A.R. Newton: On the Verification of Sequential Machines at the Differing Levels of Abstraction, IEEE Tr. on CAD, pp. 713-722, June 1988.
[7] N. Dutt and J. Kipps: Bridging High-Level Synthesis to RTL Technology Libraries, Design Automation Conference, June, 1991.
[8] P.A. Findlay, B. Dickinson, M. Harris: Production of Generic Syntesizable ASIC Descriptions Using VHDL, VHDL-Forum, 1993.
[9] Th. Filkorn: A Method for Symbolic Verification of Synchronous Circuits, CHDL'91, Apr. 1991.
[10] A. Ghosh, S. Devadas, A.R. Newton: Verification of Interacting Sequential Circuits, 27th DAC, pp. 213-219, 1990.
[11] E. Girczyc, S. Carlson: Increasing Design Quality and Engineering Productivity through Design Reuse, 30th Design Automation Conference, Dallas, Texas, June 1993.
[12] M. Gordon, T. Melham (eds.): Introduction to HOL: A Theorem Proving Environment for Higher Order Logic, Cambridge Univ. Press, 1993.
[13] S.L.Greenspan, J.J. Wisowaty, R.E. Bright Jr.: Product Definition Through the Design-by-Use Process, AT&T Technical Journal, p.31-40, May/June 1992.
[14] W. Guerts, F. Katthoor, and H. De Man: Heuristics Techniques for the Synthesis of Complex Functional Units, The European Conference on Design Automation, Paris, France, February 22-25, 1993.
[15] W.A. Hunt, Jr: The Mechanical Verification of Microprocessor Design, in D. Borrione (Ed.): From VHDL Descriptions to Guaranteed Correct Circuit Design, pp. 89-129, North- Holland, 1987.
[16] L. Jozwiak, J.C. Kolsteren: An Efficient Method for the Sequential General Decomposition of Sequential Machines, Microprocessing and Microprogramming, North-Holland, vol. 32, pp. 657-664, 1991.
[17] L. Jozwiak, F. Volf: An Efficient Method for Decomposition of Multiple Output Boolean Functions and Assigned Sequential Machines, EDAC - The European Conference on Design Automation, Brussels, Belgium, March 16-19, 1992, pp. 114-122.
[18] L. Jozwiak: An Efficient Verification Method for Application in Transformational Design, 21st EUROMICRO Conference, Como, Italy, September 4-7, 1995.
[19] Jozwiak: General Decomposition and Its Use in Digital Circuit Synthesis, VLSI Design: An International Journal of Custom-Chip Design, Simulation, and Testing, p. 225-248, vol.3, No 3-4, 1995.
[20] L. Jozwiak: Modern Concepts of Quality and Their Relationship to Design Reuse and Model Libraries, Current Issues in Electronic Modeling, Chapter 8, Issue 5, Kluwer Academic Publishers, 1995.
[21] L. Jozwiak: Quality-Driven Design Space Exploration in Electronic System Design, IEEE International Symposium on Industrial Electronics ISIE'96, Warsaw, Poland, June 17-20, 1966.
[22] L. Jozwiak, A. Ong: Quality-Driven Decision Making Methodology for System-Level Design, 22nd EUROMICRO Conference, Prague, Czech Republic, September 2-5, 1996.
[23] J.M. Juran: Juran on Leadership for Quality, The Free Press, New York, 1988.
[24] B. Landwehr, P. Marwedel, and R. Domer: OSCAR: Optimum Simultaneous scheduling, Allocation and Resource Binding Based on Integer Programming, EDAC, Paris, 1994.
[25] R. Lipsett, C. Schaefer, C. Ussery: VHDL: Hardware Description and Design, Kluwer Academic Publishers, 1990.
[26] R. H. Lochner and J.E. Matar: Designing for Quality, Chapman and Hall, 1990.
[27] H.K.T. Ma, S. Devadas, R.S. Wei, A. Sangiovanni-Vincentelli: Logic Verification Algorithms and their Parallel Implementations, IEEE TR. on CAD, pp. 181-189, Febr. 1989.
[28] S. Malik, A.R. Wang, R.K. Brayton. A. Sangiovanni-Vincentelli: Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment, ICCAD, p. 6-9, 1988.
[29] K.L. McMillan: Symbolic Model Checking, Kluwer, 1993.
[30] H.R. Parsaei, W.G. Sullivan: Concurrent Engineering, Chapman & Hall, London, 1993.
[31] V. Preis, S. Marz-Rossel: Aspects of Modeling a Library of Complex and Highly Flexible Components in VHDL, Workshop on Libraries, Component Modeling , and Quality Assurance, Nantes, France, April 26-27, 1995.
[32] T.L. Saaty: The Analytic Hierarchy Process, McGraw-Hill, 1980.
[33] M. Sakawa: Fuzzy Sets and Interactive Multiobjective Optimization, Plenum Press, New York, 1993.
[34] P. Vincke and M. Gassner and B. Roy: Multicriteria Decision-Aid, John Wiley and Sons, Chichester, 1992.
[35] F. Volf, L. Jozwiak: Decompositional Logic Synthesis Approach for Look Up Table FPGAs, ASIC'95 Conference, Austin, Texas, Sept. 18-22, 1995.
[36] A.P. Wierzbicki: A mathematical Basis for Satisficing Decision Making, Mathematical Modelling, vol. 3, pp.391-405, 1982.
[37] A.P. Wierzbicki: On the Completness and Constructiveness of Parametric Characterizations to Vector Optimization Problems, OR Spektrum, vol. 8,pp. 73-87, 1986.
[38] P. L. Yu: Multiple-Criteria Decision Making, Plenum Press, New York and London, 1985.
[39] L. Jozwiak: Modern Concepts of Quality and Their Relations to Model Libraries, ESPRIT/IFIP Workshop on Libraries, Component Modeling, and Quality Assurance, Nantes, France, April 26-27,1995.

chdl97@it.uc3m.es