E-Book
123,99 €

Boolean Circuit Rewiring E-Book

Tak-Kei Lam

0,0

123,99 €

Sammeln Sie Punkte in unserem Gutscheinprogramm und kaufen Sie E-Books und Hörbücher mit bis zu 100% Rabatt.

Mehr erfahren.

Herausgeber: John Wiley & Sons
Kategorie: Wissenschaft und neue Technologien
Sprache: Englisch

Beschreibung

Demonstrates techniques which will allow rewiring rates of over 95%, enabling adoption of deep sub-micron chips for industrial applications

Logic synthesis is an essential part of the modern digital IC design process in semi-conductor industry. This book discusses a logic synthesis technique called “rewiring” and its latest technical advancement in term of rewirability. Rewiring technique has surfaced in academic research since 1993 and there is currently no book available on the market which systematically and comprehensively discusses this rewiring technology. The authors cover logic transformation techniques with concentration on rewiring. For many decades, the effect of wiring on logic structures has been ignored due to an ideal view of wires and their negligible role in the circuit performance. However in today’s semiconductor technology wiring is the major player in circuit performance degeneration and logic synthesis engines can be improved to deal with this through wire-based transformations. This book introduces the automatic test pattern generation (ATPG)-based rewiring techniques, which are recently active in the realm of logic synthesis/verification of VLSI/SOC designs.

Unique comprehensive coverage of semiconductor rewiring techniques written by leading researchers in the field
Provides complete coverage of rewiring from an introductory to intermediate level
Rewiring is explained as a flexible technique for Boolean logic synthesis, introducing the concept of Boolean circuit transformation and testing, with examples
Readers can directly apply the described techniques to real-world VLSI design issues
Focuses on the automatic test pattern generation (ATPG) based rewiring methods although some non-ATPG based rewiring methods such as graph based alternative wiring (GBAW), and “set of pairs of functions to be distinguished” (SPFD) based rewiring are also discussed

A valuable resource for researchers and postgraduate students in VLSI and SoC design, as well as digital design engineers, EDA software developers, and design automation experts that specialize in the synthesis and optimization of logical circuits.

Details

Sie lesen das E-Book in den Legimi-Apps auf:

Android

iOS

von Legimi
zertifizierten E-Readern

Seitenzahl: 363

Veröffentlichungsjahr: 2016

Bewertungen

0,0

Rezensionen(0 Rezensionen)

Leseprobe

Cover

Title Page

List of Figures

List of Tables

Preface

Introduction

Chapter 1: Preliminaries

1.1 Boolean Circuits

1.2 Redundancy and Stuck-at Faults

1.3 Automatic Test Pattern Generation (ATPG)

1.4 Dominators

1.5 Mandatory Assignments and Recursive Learning

1.6 Graph Theory and Boolean Circuits

References

Chapter 2: Concept of Logic Rewiring

2.1 What is Rewiring?

2.2 ATPG-based Rewiring Techniques

2.3 Non-ATPG-based Rewiring Techniques

2.4 Why are Rewiring Techniques Important?

References

Chapter 3: Add-First and Non-ATPG-Based Rewiring Techniques

3.1 Redundancy Addition and Removal (RAR)

3.2 Node-Based Network Addition and Removal (NAR)

3.3 Other Rewiring Techniques

References

Chapter 4: Delete-First Rewiring Techniques

4.1 IRRA

4.2 ECR

4.3 FECR

4.4 Cut-Based Error Cancellation Rewiring

References

Chapter 5: Applications

5.1 Area Reduction

5.2 Postplacement Optimization

5.3 ECO Timing Optimization

5.4 Area Reduction in FPGA Technology Mapping

5.5 FPGA Postlayout Routing Optimization

5.6 Logic Synthesis for Low Power Using Clock Gating and Rewiring

References

Chapter 6: Summary

Index

End User License Agreement

Pages

xii

xiii

xiv

xvii

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

211

213

214

Guide

Cover

Table of Contents

Preface

Introduction

Begin Reading

List of Illustrations

Chapter 1: Preliminaries

Figure 1.1 Basic logic gates

Figure 1.2 Directed acyclic graph representation of a circuit. (a) A directed acyclic graph; (b) a Boolean circuit

Figure 1.3 Stuck-at fault

Figure 1.4 Untestable stuck-at fault

Figure 1.5 Unjustified AND/OR gates and their complete justifications

Figure 1.6 Example of recursive learning. (a) Gate with preassigned value: ; (b) justifications (I) for , , and ; (c) justifications (II) for , , and ; (d) justifications (III) for , , and ; (e) values implied from

Chapter 2: Concept of Logic Rewiring

Figure 2.1 Example of rewiring. (a) Original circuit where a target wire is selected; (b) addition of an alternative wire; (c) rewired circuit

Figure 2.2 Redundancy addition and removal. (a) Identification of redundant wires; (b) addition of wire and removal of wire

Figure 2.3 Identification of alternative wires in REWIRE. (a) Identification of alternative wires by dominators; (b) identification of alternative wires by FMAs

Figure 2.4 Mutual target and alternative wires

Figure 2.5 Uncontrollability implication for AND, OR, and NOT gates

Figure 2.6 Unobservability implication for AND, OR, and NOT gates

Figure 2.7 Examples of delete-first rewiring/error cancellation

Figure 2.8 General abstract view of error cancellation

Figure 2.9 Example of rewiring by logic addition. (a) Original circuit; (b) alternative circuit; (c) simplified alternative circuit

Figure 2.10 Examples of dynamic dominators

Figure 2.11 Example of an irredundant alternative wire

Figure 2.12 Error propagation of and the error frontiers

Figure 2.13 Multiple alternatives wires

Figure 2.14 Sample graph-based alternate wiring patterns. (a) Sample pattern I; (b) II; (c) III

Figure 2.15 DAG representations of the sample GBAW patterns. (a) Sample graph pattern I; (b) II; (c) III

Figure 2.16 Implementation I of

Figure 2.17 Karnaugh maps of . (a) ; (b)

Figure 2.20 Karnaugh maps of . (a) ; (b)

Figure 2.21 Implementation II of

Figure 2.22 New Karnaugh maps of . (a) ; (b)

Figure 2.23 New Karnaugh maps of . (a) ; (b)

Figure 2.24 SPFD-based rewiring

Figure 2.25 Circuit with timing violation

Figure 2.26 Circuit without timing violation after rewiring

Chapter 3: Add-First and Non-ATPG-Based Rewiring Techniques

Figure 3.1 Complete set of transformations for single alternative wire addition

Figure 3.2 Example of node merging

Figure 3.3 Signatures and ODC masks

Figure 3.4 Eight ways to construct an alternative node and their corresponding sufficient conditions. (a) ; (b) ; (c) ; (d) ; (e) ; (f) ; (g) ; (h)

Figure 3.5 SPFD: Example 1

Figure 3.6 SPFD: Example 2

Figure 3.7 SPFD-based local rewiring

Figure 3.8 SPFD-based global rewiring

Figure 3.9 SPFD-GR:

GR_Modify_Logic_2

Example

Figure 3.10 SPFD-ER: Example

Chapter 4: Delete-First Rewiring Techniques

Figure 4.1 General abstract view of error cancellation

Figure 4.2 Source mandatory assignments

Figure 4.3 Rectification network

Figure 4.4 Simplified rectification network

Figure 4.5 Destination nodes of alternative wires. (a) Rectification network for destination gate with MA value or 0; and (b) or 1

Figure 4.6 Source mandatory assignments of fault

Figure 4.7 Removal of semi-redundant and redundant SMAs

Figure 4.8 Substitution rules of source mandatory assignments for AND and OR gates. (a) Rule 1; (b) Rule 2; (c) Rule 3; (d) Rule 4; (e) Rule 5;

Figure 4.9 IRRA rewiring

Figure 4.10 Identification of SMA under recursive learning

Figure 4.11 Examples of dynamic dominators

Figure 4.12 Examples of error cancellation rules

Figure 4.13 Generalized wire addition and removal

Figure 4.14 Rectification network

Figure 4.15 Destination identification

Figure 4.16 Empirical runtime of IRRA

Figure 4.17 Empirical runtime of ECR

Figure 4.18 An error cancelled at dominator that does not have side input

Figure 4.19 Error propagation of _error

Figure 4.20 Error flow graphs (a) without semi-MA and (b) with semi-MA

Figure 4.21 Structural view of error cancellation. (a) 1-to-1 error cancellation; (b) multi-error cancellation

Figure 4.22 Example of flow-graph-based error cancellation rewiring (FECR). (a) Addition of the rectification network –first approach; (b) rewired circuit –first approach

Figure 4.23 Example of flow-graph-based error cancellation rewiring (FECR). (a) Addition of the rectification network –second approach; (b) rewired circuit –second approach

Figure 4.24 Example of and

Figure 4.25 Relationship between dominators and error cuts

Figure 4.26 Error propagation using dominators. (a) Original circuit; (b) identification of dominators; (c) identification of mandatory assignments

Figure 4.27 Example of and E-frontier shifting

Figure 4.28 Error propagation using error frontier

Figure 4.29 Flow of error-frontier-based error propagation

Figure 4.30 Locating new single-node frontier. (a) Original error frontier; (b) new error frontier

Figure 4.31 Locating new multi-node frontier. (a) Original error frontier; (b) -MA propagation; (c) -MA propagation; (d) new error frontier

Figure 4.32 Locating new error frontier with inconsistent -MA propagation. (a) Original error frontier; (b) inconsistent -MA propagation; (c) new error frontier

Figure 4.33 Relationship between (a) dominator-based propagation and (b) error-frontier-based propagations

Figure 4.34 Construction of an error graph. (a) Error propagation; (b) error graph

Figure 4.35 Cut enumeration

Figure 4.36 Simplification of rectification networks by node merging. (a) Rectification networks at and ; (b) rewired circuit

Figure 4.37 Structural view of -to- error cancellation

Figure 4.38 Sub-circuit for rewiring. (a) Collect gates for sub-circuit; (b) create virtual primary IO

Figure 4.39 Rewiring ability of CECR for different window sizes. (a) Rewiring rates for different window sizes; (b) CPU times for different window sizes

Chapter 5: Applications

Figure 5.1 Example of ODCs and node merging

Figure 5.2 Typical greedy decaying effect in bin-packing router (Wu and Marek-Sadowska 1995)

Figure 5.3 Example of orthogonal greedy coupling (Wu and Marek-Sadowska 1995). (a) Algorithm alone; (b) algorithm coupled

Figure 5.4 Difference between node merging and rewiring. (a) Original netlist; (b) removing with by node merging; (c) removing node by rewiring

Figure 5.5 Example of coupling rewiring and node merging. (a) Rewiring for ODCs shifting; (b) netlist after rewiring and node merging

Figure 5.6 Rewiring for perturbation

Figure 5.7 Reduction of HPWL by logic rewiring. (a) Initial circuit in logical view; (b) initial circuit in physical view; (c) optimized circuit in logical view; (d) optimized circuit in physical view

Figure 5.8 Estimation of HPWL of a single fanout net. (a) Before removing TW; (b) after removing TW

Figure 5.9 Estimation of HPWL of multiple fanout nets. (a) Before removing TW; (b) after removing TW

Figure 5.10 HPWL increase due to AW addition. (a) Before adding AW; (b) after adding AW

Figure 5.11 Revised HPWL estimation when TW and AW have the same source. (a) Before adding AW; (b) after adding AW

Figure 5.12 Revised HPWL estimation when AW is in the fanin cone of TW. (a) Before adding AW; (b) after adding AW

Figure 5.13 Figure Slack distribution graph of an industrial design

Figure 5.14 Optimizing circuit from slack mountain boundary resulting in more delay improvement. (a) Initial slack contour; (b) initial slack mountain; (c) optimizing slack mountain from peak first; (d) optimizing slack mountain from boundary first

Figure 5.15 Example of AW selection

Figure 5.16 Fanout gates of TW and AW

Figure 5.17 Slack mountain being smoothed down by timing optimization (valley areas are not shown for clarity). (a) Slack mountain of initial circuit; (b) slack mountain of optimized circuit

Figure 5.18 Example of ECO path optimization. (a) Before ECO optimization; (b) after ECO optimization

Figure 5.19 N

EGO

-R

OUT

flow. (a) original netlist; (b) iteration 1; (c) iteration 2; (d) iteration 3; (e) N

EGO

-R

OUT

result; (f) DCP result

Figure 5.20 R

ESTRUCTURING

flow. (a) Original netlist; (b) rewired netlist

Figure 5.21 Framework flow

Figure 5.22 Rewiring improvement upon already optimal graph-based tech map. (a) Optimal mapping without logic perturbation: depth = 3, area = 9; (b) improved mapping after logic perturbation: depth = 3, area = 8

Figure 5.23 Conventional FPGA EDA flow

Figure 5.24 Alternative function construction using MAs

Figure 5.25 Layout-driven synthesis using alternative functions

Figure 5.26 Example of external/internal wires

Figure 5.27 Example of postlayout logic perturbation by ATPG-based rewiring

Figure 5.28 Example of multiple-wire addition

Figure 5.29 Example of extra LUT addition

Figure 5.30 Rules for identifying alternative candidates

Figure 5.31 Example of an “existing” alternative wire () (Rule 2)

Figure 5.32 Example of gate duplication in technology mapping ()

Figure 5.33 Example of destination LUT expansion () (Rule 4)

Figure 5.34 Work flow of rewiring-based FPGA router

Figure 5.35 Example of clock gating implementation. (a) A sequential circuit; (b) clock-gated sequential circuit

Figure 5.37 Examples of clock gating. (a) Clock gating; (b) observability don't cares based clock gating; (c) idle-based clock gating

Figure 5.36 Flip-flops that are mutually unobservable

Figure 5.38 Rewiring strategy I

Figure 5.39 Rewiring strategy II

Figure 5.40 Rewiring strategy III

List of Tables

Chapter 1: Preliminaries

Table 1.1 Behavior of the basic Boolean operators

Chapter 2: Concept of Logic Rewiring

Table 2.1 Truth Table and minterms of logical AND function

Table 2.2 SPFDs of the gates in Figure 2.16

Table 2.3 SPFDs of the gates in Figure 2.21

Chapter 3: Add-First and Non-ATPG-Based Rewiring Techniques

Table 3.1 Comparison of rewiring ability of SPFD-based rewiring algorithms for four-LUT FPGA designs

Table 3.2 Comparison of rewiring ability for different atomic SPFD assignment methods

Chapter 4: Delete-First Rewiring Techniques

Table 4.1 CPU time analysis for IRRA

Table 4.2 CPU time analysis for ECR

Table 4.3 Comparison on combinational benchmarks between IRRA and ECR

Table 4.4 Comparison on sequential benchmarks between IRRA and ECR

Table 4.5 Comparison on combinational benchmarks between NAR and ECR

Table 4.6 FPGA technology mapping for ILR combined with different rewiring engines on optimized benchmarks, LUT size = 4

Table 4.7 Comparison between ECR and FECR

Table 4.8 Effectiveness of different windowing sizes

Table 4.9 Comparison between ECR, FECR, and CECR

Table 4.10 Detailed statistics for CECR

Table 4.11 Effectiveness of windowing technique

Chapter 5: Applications

Table 5.1 Experimental results of area reduction by using approaches in Plaza et al. (2007) and Chen and Wang (2010) and our approach

Table 5.2 Iterations of optimization in our approach

Table 5.3 Benchmark information

Table 5.4 Real versus estimated HPWL reduction

Table 5.5 Effectiveness of our framework for wirelength reduction of placement and global routing

Table 5.6 Effectiveness of our algorithm compared to the traditional peak-first algorithm and a recent work

Table 5.7 Comparison of our algorithm and the DCP algorithm

Table 5.8 Results of depth-ILR followed by area-ILR with FlowSYN ()

Table 5.9 Result of area-ILR over DAOMap ()

Table 5.10 Result of area-ILR over DAOMap ()

Table 5.11 Result of Area-ILR over IMap ()

Table 5.12 Result of Area-ILR over IMap ()

Table 5.13 Result of Area-ILR over imfs lutpack in ABC()

Table 5.14 Result of Area-ILR on Commercial Benchmarks ()

Table 5.15 Effect of area-ILR on VPR Delay performance ()

Table 5.16 Effect of area-ILR on delay performance in commercial FPGAs ()

Table 5.17 Result of area-ILR on circuits synthesized by BDS-pga ()

Table 5.18 : Number of terminals versus net weight

Table 5.19 Experimental results on rewiring-based FPGA router

Table 5.20 Experimental results on rewiring-based technology mapping and routing

Table 5.21 Postlayout optimization by SPFD-ER

Table 5.22 Total cell areas of the circuits

Table 5.23 Power dissipation statistics

Boolean Circuit Rewiring:

Bridging Logical and Physical Designs

Tak–Kei Lam

The Chinese University of Hong Kong, Hong Kong, P. R. China

Wai–Chung Tang

Queen Mary University of London, UK

Xing Wei

Easy–Logic Technology Ltd. Hong Kong, Hong Kong, P. R. China

Yi Diao

Easy–Logic Technology Ltd. Hong Kong, Hong Kong, P. R. China

David Yu–Liang Wu

Easy–Logic Technology Ltd. Hong Kong, Hong Kong, P. R. China

This edition first published 2016

Registered office

John Wiley & Sons Singapore Pte Ltd, 1 Fusionopolis Walk, #07-01 Solaris South Tower, Singapore 138628.

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data applied for.

ISBN: 9781118750117

A catalogue record for this book is available from the British Library.

List of Figures

Figure 1.1

Basic logic gates

Figure 1.2

Directed acyclic graph representation of a circuit. (a) A directed acyclic graph; (b) a Boolean circuit

Figure 1.3

Stuck-at fault

Figure 1.4

Untestable stuck-at fault

Figure 1.5

Unjustified AND/OR gates and their complete justifications

Figure 1.6

Example of recursive learning. (a) Gate with preassigned value:

; (b) justifications (I) for

, and

; (c) justifications (II) for

, and

; (d) justifications (III) for

, and

; (e) values implied from

Figure 2.1

Example of rewiring. (a) Original circuit where a target wire is selected; (b) addition of an alternative wire; (c) rewired circuit

Figure 2.2

Redundancy addition and removal. (a) Identification of redundant wires; (b) addition of wire

and removal of wire

Figure 2.3

Identification of alternative wires in REWIRE. (a) Identification of alternative wires by dominators; (b) identification of alternative wires by FMAs

Figure 2.4

Mutual target and alternative wires

Figure 2.5

Uncontrollability implication for AND, OR, and NOT gates

Figure 2.6

Unobservability implication for AND, OR, and NOT gates

Figure 2.7

Examples of delete-first rewiring/error cancellation

Figure 2.8

General abstract view of error cancellation

Figure 2.9

Example of rewiring by logic addition. (a) Original circuit; (b) alternative circuit; (c) simplified alternative circuit

Figure 2.10

Examples of dynamic dominators

Figure 2.11

Example of an irredundant alternative wire

Figure 2.12

Error propagation of

and the error frontiers

Figure 2.13

Multiple alternatives wires

Figure 2.14

Sample graph-based alternate wiring patterns. (a) Sample pattern I; (b) II; (c) III

Figure 2.15

DAG representations of the sample GBAW patterns. (a) Sample graph pattern I; (b) II; (c) III

Figure 2.16

Implementation I of

Figure 2.17

Karnaugh maps of

. (a)

; (b)

Figure 2.18

Karnaugh maps of

. (a)

; (b)

Figure 2.19

Karnaugh maps of

. (a)

; (b)

Figure 2.20

Karnaugh maps of

. (a)

; (b)

Figure 2.21

Implementation II of

Figure 2.22

New Karnaugh maps of

. (a)

; (b)

Figure 2.23

New Karnaugh maps of

. (a)

; (b)

Figure 2.24

SPFD-based rewiring

Figure 2.25

Circuit with timing violation

Figure 2.26

Circuit without timing violation after rewiring

Figure 3.1

Complete set of transformations for single alternative wire addition

Figure 3.2

Example of node merging

Figure 3.3

Signatures and ODC masks

Figure 3.4

Eight ways to construct an alternative node and their corresponding sufficient conditions. (a)

; (b)

; (c)

; (d)

; (e)

; (f)

; (g)

; (h)

Figure 3.5

SPFD: Example 1

Figure 3.6

SPFD: Example 2

Figure 3.7

SPFD-based local rewiring

Figure 3.8

SPFD-based global rewiring

Figure 3.9

SPFD-GR:

GR_Modify_Logic_2

Example

Figure 3.10

SPFD-ER: Example

Figure 4.1

General abstract view of error cancellation

Figure 4.2

Source mandatory assignments

Figure 4.3

Rectification network

Figure 4.4

Simplified rectification network

Figure 4.5

Destination nodes of alternative wires. (a) Rectification network for destination gate with MA value

or 0; and (b)

or 1

Figure 4.6

Source mandatory assignments of fault

Figure 4.7

Removal of semi-redundant and redundant SMAs

Figure 4.8

Substitution rules of source mandatory assignments for AND and OR gates. (a) Rule 1; (b) Rule 2; (c) Rule 3; (d) Rule 4; (e) Rule 5;

Figure 4.9

IRRA rewiring

Figure 4.10

Identification of SMA under recursive learning

Figure 4.11

Examples of dynamic dominators

Figure 4.12

Examples of error cancellation rules

Figure 4.13

Generalized wire addition and removal

Figure 4.14

Rectification network

Figure 4.15

Destination identification

Figure 4.16

Empirical runtime of IRRA

Figure 4.17

Empirical runtime of ECR

Figure 4.18

An error cancelled at dominator that does not have side input

Figure 4.19

Error propagation of

_error

Figure 4.20

Error flow graphs (a) without semi-MA and (b) with semi-MA

Figure 4.21

Structural view of error cancellation. (a) 1-to-1 error cancellation; (b) multi-error cancellation

Figure 4.22

Example of flow-graph-based error cancellation rewiring (FECR). (a) Addition of the rectification network –first approach; (b) rewired circuit –first approach

Figure 4.23

Example of flow-graph-based error cancellation rewiring (FECR). (a) Addition of the rectification network –second approach; (b) rewired circuit –second approach

Figure 4.24

Example of

and

Figure 4.25

Relationship between dominators and error cuts

Figure 4.26

Error propagation using dominators. (a) Original circuit; (b) identification of dominators; (c) identification of mandatory assignments

Figure 4.27

Example of

and E-frontier shifting

Figure 4.28

Error propagation using error frontier

Figure 4.29

Flow of error-frontier-based error propagation

Figure 4.30

Locating new single-node frontier. (a) Original error frontier; (b) new error frontier

Figure 4.31

Locating new multi-node frontier. (a) Original error frontier; (b)

-MA propagation; (c)

-MA propagation; (d) new error frontier

Figure 4.32

Locating new error frontier with inconsistent

-MA propagation. (a) Original error frontier; (b) inconsistent

-MA propagation; (c) new error frontier

Figure 4.33

Relationship between (a) dominator-based propagation and (b) error-frontier-based propagations

Figure 4.34

Construction of an error graph. (a) Error propagation; (b) error graph

Figure 4.35

Cut enumeration

Figure 4.36

Simplification of rectification networks by node merging. (a) Rectification networks at

and

; (b) rewired circuit

Figure 4.37

Structural view of

-to-

error cancellation

Figure 4.38

Sub-circuit for rewiring. (a) Collect gates for sub-circuit; (b) create virtual primary IO

Figure 4.39

Rewiring ability of CECR for different window sizes. (a) Rewiring rates for different window sizes; (b) CPU times for different window sizes

Figure 5.1

Example of ODCs and node merging

Figure 5.2

Typical greedy decaying effect in bin-packing router (Wu and Marek-Sadowska 1995)

Figure 5.3

Example of orthogonal greedy coupling (Wu and Marek-Sadowska 1995). (a) Algorithm alone; (b) algorithm coupled

Figure 5.4

Difference between node merging and rewiring. (a) Original netlist; (b) removing

with

by node merging; (c) removing node

by rewiring

Figure 5.5

Example of coupling rewiring and node merging. (a) Rewiring for ODCs shifting; (b) netlist after rewiring and node merging

Figure 5.6

Rewiring for perturbation

Figure 5.7

Reduction of HPWL by logic rewiring. (a) Initial circuit in logical view; (b) initial circuit in physical view; (c) optimized circuit in logical view; (d) optimized circuit in physical view

Figure 5.8

Estimation of HPWL of a single fanout net. (a) Before removing TW; (b) after removing TW

Figure 5.9

Estimation of HPWL of multiple fanout nets. (a) Before removing TW; (b) after removing TW

Figure 5.10

HPWL increase due to AW addition. (a) Before adding AW; (b) after adding AW

Figure 5.11

Revised HPWL estimation when TW and AW have the same source. (a) Before adding AW; (b) after adding AW

Figure 5.12

Revised HPWL estimation when AW is in the fanin cone of TW. (a) Before adding AW; (b) after adding AW

Figure 5.13

Figure Slack distribution graph of an industrial design

Figure 5.14

Optimizing circuit from slack mountain boundary resulting in more delay improvement. (a) Initial slack contour; (b) initial slack mountain; (c) optimizing slack mountain from peak first; (d) optimizing slack mountain from boundary first

Figure 5.15

Example of AW selection

Figure 5.16

Fanout gates of TW and AW

Figure 5.17

Slack mountain being smoothed down by timing optimization (valley areas are not shown for clarity). (a) Slack mountain of initial circuit; (b) slack mountain of optimized circuit

Figure 5.18

Example of ECO path optimization. (a) Before ECO optimization; (b) after ECO optimization

Figure 5.19

EGO

-R

OUT

flow. (a) original netlist; (b) iteration 1; (c) iteration 2; (d) iteration 3; (e) N

EGO

-R

OUT

result; (f) DCP result

Figure 5.20

ESTRUCTURING

flow. (a) Original netlist; (b) rewired netlist

Figure 5.21

Framework flow

Figure 5.22

Rewiring improvement upon already optimal graph-based tech map. (a) Optimal mapping without logic perturbation: depth = 3, area = 9; (b) improved mapping after logic perturbation: depth = 3, area = 8

Figure 5.23

Conventional FPGA EDA flow

Figure 5.24

Alternative function construction using MAs

Figure 5.25

Layout-driven synthesis using alternative functions

Figure 5.26

Example of external/internal wires

Figure 5.27

Example of postlayout logic perturbation by ATPG-based rewiring

Figure 5.28

Example of multiple-wire addition

List of Tables

Table 1.1Behavior of the basic Boolean operators

Table 2.1 Truth table and minterms of logical AND function

Table 2.2 SPFDs of the gates in Figure 2.16

Table 2.3 SPFDs of the gates in Figure 2.21

Table 3.1 Comparison of rewiring ability of SPFD-based rewiring algorithms for four-LUT FPGA designs

Table 3.2 Comparison of rewiring ability for different atomic SPFD assignment methods

Table 4.1 CPU time analysis for IRRA

Table 4.2 CPU time analysis for ECR

Table 4.3 Comparison on combinational benchmarks between IRRA and ECR

Table 4.4 Comparison on sequential benchmarks between IRRA and ECR

Table 4.5 Comparison on combinational benchmarks between NAR and ECR

Table 4.6 FPGA technology mapping for ILR combined with different rewiring engines on optimized benchmarks, LUT size = 4

Table 4.7 Comparison between ECR and FECR

Table 4.8 Effectiveness of different windowing sizes

Table 4.9 Comparison between ECR, FECR, and CECR

Table 4.10 Detailed statistics for CECR

Table 4.11 Effectiveness of windowing technique

Table 5.1 Experimental results of area reduction by using approaches in Plaza et al. (2007) and Chen and Wang (2010) and our approach

Table 5.2 Iterations of optimization in our approach

Table 5.3 Benchmark information

Table 5.4 Real versus estimated HPWL reduction

Table 5.5 Effectiveness of our framework for wirelength reduction of placement and global routing

Table 5.6Effectiveness of our algorithm compared to the traditional peak-first algorithm and a recent work

Table 5.7 Comparison of our algorithm and the DCP algorithm

Table 5.8 Results of depth-ILR followed by area-ILR with FlowSYN ()

Table 5.9 Result of area-ILR over DAOMap ()

Table 5.10 Result of area-ILR over DAOMap ()

Table 5.11 Result of Area-ILR over IMap ()

Table 5.12 Result of Area-ILR over IMap ()

Table 5.13 Result of Area-ILR over imfs lutpack in ABC()

Table 5.14 Result of Area-ILR on Commercial Benchmarks ()

Table 5.15 Effect of area-ILR on VPR Delay performance ()

Table 5.16 Effect of area-ILR on delay performance in commercial FPGAs ()

Table 5.17 Result of area-ILR on circuits synthesized by BDS-pga ()

Table 5.18: Number of terminals versus net weight

Table 5.19 Experimental results on rewiring-based FPGA router

Table 5.20 Experimental results on rewiring-based technology mapping and routing

Table 5.21

Preface

Our group has been working on wire-based logic restructuring (rewiring) for over a decade. Over the years, we have published numerous conference and journal papers on rewiring. As a recent major milestone, we have developed a rewiring scheme that reaches a near-complete rewiring rate (). This result demonstrates the high power of this kind of logic transformation techniques and the great potential of applying them on modern electronic design automation (EDA) tools.

Because of the aggressive and continuous scaling down of transistor sizes, to 45, 22 nm, and even below 16 nm, wires have become a dominant factor affecting circuit performance. Hence, rewiring is particularly suitable for today's nanometer technologies.

We could not find a book that focuses on and discusses rewiring techniques. Since rewiring techniques have become much more practical in nanometer technologies, we felt there was a need to publish a reference book to provide readers with the key ideas.

This book is of introductory to intermediate level. We hope this book will help in popularizing science, and the readers will find this book interesting and informative.

Tak-Kei Lam, Wai-Chung Tang, Xing Wei,Yi Diao, and David Yu-Liang Wu

Introduction

The concepts of various major rewiring techniques are explained throughout the book gradually. First, readers will be presented with the basic ideas of rewiring. Next, the technical details of each kind of rewiring technique will be discussed in detail. Finally, the applications of rewiring techniques in various electronic design automation (EDA) areas will be introduced.

Intended Audience

Students studying computer/electronic engineering, academic staff, and even EDA engineers are the intended readers of this book. The readers should have some basic knowledge of Boolean algebra, logic gates, and graph theory. For readers without the related advanced knowledge, essential concepts will be introduced and explained throughout the book.

Type Conventions

The following conventions are used in this book:

Mathematical symbols and names of circuit elements, such as

and

, are typeset in this font.

Codes are typeset in this font.

Acknowledgments

Many people have contributed to this book in the forms of research output, implementations of algorithms, suggestions for content, and, last but not least, simply being encouraging. This book could never have been completed without their generous effort. We are very grateful to the following people for all they have done:

The authors of RAMBO, REWIRE, RAMFIRE, GBAW, IRRA, NAR, ECR, FECR, CECR, SPFD-based and all other rewiring techniques.

The authors of the typesetting system and the plugins.

Chapter 1Preliminaries

1.1 Boolean Circuits

A Boolean variable is a variable whose value can only be either 0 (false) or 1 (true) or unknown. Every Boolean variable has two literals. They are the normal form and the negation/complement of the variable. The negation of a variable always evaluates to the opposite value of the variable. Suppose is a Boolean variable; then its negation is . When is 1, is 0; when is 0, is 1. The literals of variable are then and .

A function consisting of Boolean variables is known as a Boolean function. It is a mapping between Boolean spaces. For example, the function is a mapping between the input space of Boolean variables and the output space of Boolean variables. We use to indicate the input variables or input values of the Boolean function .

The mapping between Boolean spaces is achieved by Boolean operators. The basic Boolean operators (operations) AND, OR, NOT, XOR, and XNOR are denoted as, and , respectively, in this book. We may omit the symbol for clarity. The behavior of the basic operators is listed in Table 1.1. Complex Boolean operators can be derived from these basic operators. In fact, only AND and NOT, or only OR and NOT, are sufficient to derive all other Boolean operations.

Table 1.1 Behavior of the basic Boolean operators

Operator

When will it returns true?

AND

All of its operands are true

Any one of its operands is true

NOT

Its operand is false

XOR

Both of its operands have different values

XNOR

Both of its operands have the same values

An example of Boolean function is , which computes the logical conjunction of variables and . A Boolean function may contain literals. The Boolean function is such an example that computes the logical conjunction of variable and the negation of variable . It may be surprising for readers who are not familiar with Boolean algebra to see a function . This function is actually nothing special but is normal and valid. It just means that, among the three variables, the value of variable is “don't care.” That is to say, the value of can be either 0 or 1, and . For another example, the function can be expanded into .

Observability don't cares (ODCs) (Damiani and De Micheli 1990) of a Boolean variable are the conditions under which the variable is not affecting any of the primary outputs. For example, if an input of an AND gate has the controlling value 0, its set of other inputs are unobservable no matter what values they have. The ODC of is . Satisfiability don't cares (SDCs) of a circuit node represent the local input patterns at the node that cannot be generated by the node's fanins. As a trivial example of SDC, if we connect all inputs of a two-input AND gate to a common signal, the values of its inputs can never be or .

Many rules in ordinary algebra, such as commutative addition and multiplication, associative addition and multiplication, and variable distribution, can be applied into Boolean algebra. Therefore, function . For each of the conjunction term, it can be expanded by connecting it with all combinations of the literals of the missing variables by conjunction. Some additional important rules that are obeyed in Boolean algebra only include and . Regarding our example, it can be expanded as follows:

Other rules can be derived from the basic rules easily. Since Boolean algebra is a vast area of study, even the elementary topics can cover a whole book. In this book, we shall not cover every detail.

Boolean functions can be realized in hardware using logic gates. A Boolean circuit or Boolean network is composed of gates and implements some Boolean functions. We simply use circuits or networks to represent Boolean circuits when the meaning is clear in the context. Figure 1.1 illustrates the logic gates implementing the basic Boolean functions. An example circuit composed of AND, OR, and NOT gates is shown in Figure 1.2(b). For gate , its inputs are and , so it is implementing the function . Regarding gate , its function is .

Figure 1.1 Basic logic gates

Figure 1.2 Directed acyclic graph representation of a circuit. (a) A directed acyclic graph; (b) a Boolean circuit

A less famous Boolean operator is the cofactor. The cofactor of a Boolean function with respect to a variable is . Suppose , , and . Similarly, the cofactor of a Boolean function with respect to the complement of a variable is . Suppose , . Every Boolean function can be expressed using Shannon's expansion. For example, . An example of a function with multiple inputs is

In general, Boolean circuits can be represented by directed acyclic graphs (DAGs). A DAG is a kind of graph in which two vertices may be connected by an edge pointing to either one of the vertices, such that there are no loops in the graph. With regard to a circuit, the vertices of its corresponding graph represent its gates, and the edges of the graph represent its wires. An example of a DAG is illustrated in Figure 1.2(a). It is in fact the corresponding graph representation for the circuit in Figure 1.2(b). For instance, the node in the graph represents the OR gate , and the edge from to corresponds to the target wire indicated in the figure.

Each node in a DAG is therefore associated with a Boolean function. Edges pointing toward a node are known as the fanins of the node, and edges leaving the node are known as the fanouts of the node. The source of a wire connecting to has a fanout , and the destination of the wire has a fanin . The number of fanins of a node is called the in-degree/fanin number of the node, which is denoted by . Similarly, the number of fanouts of node is called the out-degree/fanout number and is denoted by . A special case of a DAG is the and-inverter graph (AIG) in which every node represents an AND gate. The values of the edges may be complemented to implement all Boolean functions.

In a circuit, the nodes whose fanin numbers are 0 or have no fanins are known as primary inputs (PIs), and the nodes whose fanout numbers are 0 or have no fanouts are known as primary outputs (POs).

Node is a transitive fanin (TFI) of node if there is a path from node to node . Node is said to be a transitive fanout (TFO) of node if is reachable from node . All TFIs of a node form the TFI cone of the node, and all TFOs of a node form the TFO cone of the node.

The most famous problem regarding Boolean circuits is the Boolean satisfiability problem. It is always known as the SAT problem. This problem is to determine whether there is any assignment of values to the variables of a given Boolean function such that the function can be evaluated to 1. For the Boolean function , the value assignments allows to evaluate to 1. It is a solution that satisfies this SAT problem instance.

1.2 Redundancy and Stuck-at Faults

Tausende von E-Books und Hörbücher

Ihre Zahl wächst ständig und Sie haben eine Fixpreisgarantie.

Sie haben über uns geschrieben: