This book describes the structure of simulators suitable for use in the design of digital electronic systems. Such systems are increasing rapidly in size and complexity, and the use of simulation provides a means to 'prototype' a design without ever building hardware. Other advantages over hardware prototyping are that sections of a design can be simulated in isolation, and that all internal signals are available. This book includes the compiled code and event driven algorithms for digital electronic system simulators, together with timing verification. Limitations of the structures are also discussed. An introduction to the problems of designing models is included, partly to point to how user models might be constructed for application specific integrated circuits (ASICs) and so on, and partly to expose the limitations of the modelling process. Simulators have two functions. The first is to confirm so far as possible that a design meets its specification. The second is to check if the test program will find a sufficient percentage of possible manufacturing faults. In the former case the user must supply test vectors. In the latter, tests can be generated by automatic means. As a guide to the use of simulators the book includes chapters which introduce the subjects of testing and design for testability. A major chapter is devoted to fault simulation. Finally, the text has an introduction to hardware accelerators and modellers. The book is suitable for electronic engineers using digital techniques, including undergraduates using design software, and postgraduates and practising engineers using simulation for the first time. It will also be useful for computer scientists needing an introduction to simulation techniques. Electronics texts for engineers and scientists Editors P. L. Jones, Electrical Engineering Laboratories, University of Manchester P. J. Spreadbury, Department of Engineering, University of Cambridge Simulation in the design of digital electronic systems Titles in this series H. Ahmed and P. J. Spreadbury Analogue and digital electronics for engineers R. L. Dalglish An introduction to control and measurement with microcomputers W. Shepherd and L. N. Hulley Power electronics and motor control T. H. O'Dell Electronic circuit design K. C. A. Smith and R. E. Alley Electrical circuits A. Basak Analogue electronic circuits and systems Simulation in the design of digital electronic systems JOHN B. GOSLING Formerly Senior Lecturer, Department of Computer Science, University of Manchester CAMBRIDGE UNIVERSITY PRESS CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paulo, Delhi, Dubai, Tokyo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www. Cambridge. org Information on this title: www.cambridge.org/9780521416566 © Cambridge University Press 1993 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 1993 A catalogue record for this publication is available from the British Library Library of Congress Cataloguing in Publication data Gosling, J. B. (John B.) Simulation in the design of digital electronic systems/John B. Gosling. p. cm. - (Electronic texts for engineers and scientists) Includes bibliographical references and index. ISBN 0 521 41656 6. - ISBN 0 521 42672 3 (pbk) 1. Digital electronics. 2. Electronic circuit design—Data processing. 3. Computer-aided design. I. Title. II. Series. TK7868.D5G666 1993 621.3815-dc20 93-14882 CIP ISBN 978-0-521-41656-6 Hardback ISBN 978-0-521-42672-5 Paperback Transferred to digital printing 2009 Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Information regarding prices, travel timetables and other factual information given in this work are correct at the time of first printing but Cambridge University Press does not guarantee the accuracy of such information thereafter. Contents Preface xiii 1 An introduction to the simulation of electronic systems 1 1.1 Introduction 1 1.2 Four aims of simulation 2 1.2.1 Functional correctness 2 1.2.2 Speed of the system 4 1.2.3 Hazard detection 5 1.2.4 Expected outputs for test and fault simulation 6 1.3 Components of a simulator 6 1.4 Levels of simulation 7 1.4.1 System design 7 1.4.2 High level 9 1.4.3 Gate level 9 1.4.4 Circuit level 10 1.4.5 Switch level 11 1.4.6 Mixed mode 12 1.5 Models 13 1.6 Test program generation 14 1.7 Fault simulation 17 1.8 Timing verification 18 1.9 Conclusion 18 2 Electronic computer aided design (ECAD) systems 20 2.1 The design process 20 2.1.1 Specification 20 viii Contents 2.1.2 Partitioning the design 22 2.1.3 Test strategy 22 2.1.4 Constructional issues 23 2.1.5 Logical design 23 2.1.6 ASIC design 24 2.1.7 Interfaces and pin limitation 25 2.2 Design capture 26 2.3 Simulation 28 2.4 Test program generation 29 2.5 Placement and routing 31 2.6 Wiring delays 34 2.7 Silicon compilation 35 2.8 Conclusion 36 3 Design for testability 37 3.1 Cost of testing 37 3.1.1 Advantages and penalties 37 3.1.2 Problem size 38 3.1.3 Combinational and sequential logic 42 3.1.4 Design for testability 43 3.2 Initialisation and resetting 43 3.3 Scan design 44 3.4 Boundary scan 47 3.5 Self-testing 51 3.5.1 Dedicated test logic 51 3.5.2 Signature analysis 51 3.5.3 Built-in logic block observation (BILBO) 52 3.6 Controllability and observability 54 3.6.1 Concepts 54 3.6.2 Controllability 56 3.6.3 Observability 60 3.6.4 Testability 61 4 Exercising the design in simulation and test 64 4.1 Objectives and approaches 64 4.1.1 Objective 64 4.1.2 Modelling faults 64 4.1.3 Assessment of test coverage 67 4.2 Testing for design faults 67 4.3 Testing for manufacturing faults 71 Contents IX 4.4 The D-algorithm 73 4.4.1 Basic ideas 73 4.4.2 Primitive D-cubes of failure 76 4.4.3 Primitive D-cubes of a logic block (propagation D-cubes) 79 4.4.4 Example of use of D-cubes 82 4.4.5 Enhancements to the D-algorithm 85 4.5 Reducing the number of test vectors 88 4.6 The MOS stuck open fault 90 4.7 High level testing 93 5 Input/output of simulation and specification of models 96 5.1 Input and output of simulation 96 5.2 Simple driver 98 5.3 Simulation output 100 5.4 Operation in parallel and in sequence 102 5.5 More general modelling facilities 107 5.5.1 WAIT 107 5.5.2 The LOOP statement 108 5.5.3 CASE statement 109 6 Simulation algorithms 111 6.1 Introduction 111 6.2 Compiled code simulation 113 6.2.1 Basic procedures 113 6.2.2 Simulator structures 115 6.2.3 Detailed example 116 6.2.4 Handling feedback 118 6.2.5 Some comments 121 6.3 Event driven simulation 122 6.3.1 Introduction 122 6.3.2 Basic procedures 124 6.4 An example - a four-gate not equivalence circuit 131 6.5 Some refinements 140 6.5.1 Affected component list and memory 140 6.5.2 Time wheel overflows 142 6.5.3 Wiring delays 143 6.6 Groups of signals 144 6.6.1 Usefulness and problems 144 6.6.2 User-defined values 145 c Contents 6.6.3 Group splitting 146 6.6.4 Group combination 148 7 Models and model design 150 7.1 Some simple models 150 7.2 Delays 152 7.3 Model of a buffer 153 7.3.1 Development of the algorithm 153 7.3.2 State machine representations 158 7.3.3 Model of a simple gate 162 7.4 Inertial delay 163 7.4.1 Equal rise and fall delays 163 7.4.2 Unequal rise and fall delays 164 7.5 A three-value model 167 7.6 A five-value model 169 7.7 Logical combinations and non-logical values 170 7.8 Signal strengths 171 7.9 Towards a model for a flip-flop 175 7.9.1 More complex models 175 7.9.2 The 74xx74 style flip-flop 175 7.9.3 The preset / clear (P_C) mode 177 7.9.4 The clock controlled mode 179 7.9.5 Timing errors 181 7.10 High level modelling 183 7.10.1 Behavioural models 183 7.10.2 Hierarchical models - structural 184 7.11 Wire gates 186 7.12 Hard models 187 7.12.1 Non-memory devices 187 7.12.2 Memory 190 8 Timing verification 192 8.1 Introduction 192 8.2 Computing the critical path 193 8.3 Methods of timing verification 195 8.3.1 Path enumeration 195 8.3.2 Block orientated path trace 196 8.4 Description of the network 196