[PDF] [PDF] Identifying Transparent Logic in Gate-Level Circuits - People

[PDF] Transparent and non-transparent languages - Kees Hengeveld

4 transparent or simple yet opaque For instance, Turkish verbal morphology is highly complex in the sense that a single verbal word may contain a high number  

[PDF] RedalycGender activation in transparent and opaque words

This effect was possibly due to the lexical requirements of the task: lexical decision, and also because transparent words are morphologically more complex than 

97 transparent words such as mitr meter (p 91), yur&nyum

MESA BULLETIN 27 1993 97 transparent words such as mitr "meter" (p 91), yur&nyum "Uranium" (p 13) and al-kurdiyya "Kurdish" (p 12) for students at the 

[PDF] Identifying Transparent Logic in Gate-Level Circuits - People

To identify word-level operators in a gate-level circuit, it is crucial to find words and locate the boundaries (inputs/outputs) of arithmetic operators [10] The basic  

[PDF] Impact of orthographic transparency on typical and - GIPSA Lab

20 fév 2014 · both their opaque and transparent orthographies Dyslexic role in building-up specific word knowledge which is critical for lexical reading

[PDF] First language grapheme-phoneme transparency - ScholarSpace

learning of L2 words from combined written-auditory teaching Keywords: transparency, writing, reading, orthographies, decoding, second language learning,

[PDF] mots transparents anglais ce1

[PDF] jeux poétiques collège

[PDF] fiche d'identité d'une entreprise modèle

[PDF] poésie humour cycle 3

[PDF] resultat bac 2016 maroc

[PDF] cne maroc

[PDF] fiche d'identité entreprise vierge

[PDF] foie douloureux au toucher

[PDF] ostéopathie viscérale foie

[PDF] douleur projetée épaule

[PDF] ostéopathie viscérale estomac

[PDF] extrait sec total du lait

[PDF] comment calculer l'extrait sec du lait

[PDF] mouvement accéléré physique

[PDF] mouvement rectiligne ralenti

Identifying Transparent Logic in Gate-Level Circuits

Yu-Yun Dai

1, Robert K. Brayton2

1;2Department of EECS, University of California, Berkeley, U.S.A.

f

1yunmeow,2braytong@berkeley.edu

ABSTRACT

Many reasons exist for high-level information to be unavail- able for a design. Identifying high-level constructs, e.g. control paths and words, from gate-level circuits, can assist verica- tion, equivalence checking, reverse engineering, etc.. Word-level identication can be done by structural methods, but we focus on functional approaches because they only depend on depen- dencies between signals of a circuit. We introducetransparent logic, based onfunctional isomorphism, and provide algorithms to recognize control signals, data paths, internal words, and boundaries between dierent types of logic. Experiments show that the proposed algorithms can re-assemble words eectively from unstructured or synthesized circuits.

1. INTRODUCTION

In hardware, control logic regulates the data

ow and dictates circuit functionalities. Logic can be classied as that where data is simply moved from one part of a cir- cuit to another part without modifying it. Such logic is referred to astransparent. Another category transforms data by some word-level operator, e.g. a bit-vector oper- ator dened in Verilog. A third category, control, deter- mines which data is moved and when, or which operation is applied and when. Ecient recognition of such logic can benet circuit verication, e.g. [4] as a guide to ab- straction. To identify word-level operators in a gate-level circuit, it is crucial to nd words and locate the boundaries (inputs/outputs) of arithmetic operators [10]. The basic example of transparent logic is a multiplexer (MUX) structure, which selects from several data signals and forwards it unaltered towards the outputs. Identi- cation of MUXes can be performed over gate-level circuits very quickly using structural matching, but can be unreli- able, especially if synthesis has been applied. In this paper, we focus on functional approaches which do not depend on the actual gate-level structure of the cir- cuit. These can augment structure methods and provide a much more reliable technique as we show in the experi- ments. In general, functional methods, which rely only on func- tional dependencies, have been used to augment structural approaches. Examples are, Li and Subramanyan et. al. [6,11] identied internal words based onbitslice aggregation(functional ap- proach) andshapehashing(structural approach.) The candidate words found were used as boundaries of op- erators for further recognizing. Li et. al. [6,7] identied functional operators in gate- level circuits, based on an existing library of blocks. Word-level information at the primary inputs was as- sumed available, but in many applications this infor- mation is not known.Sterin et. al. [10] extracted word-level operators func- tionally, given a library of operators and a slice of logic containing inputs and outputs of such opera- tors. Word-level information was not required nor was the possible location and ordering of the inputs and outputs of an operator. We present methods to identifyfunctional transparent logic. This is inherited fromfunctional isomorphism. Us- ing this, we propose an algorithm to identify words, word- level operator boundaries, and control logic in gate-level circuits and apply this to a variety of test cases. Once operator boundaries are located (roughly), techniques like those in Sterin et. al. [10] can be used to identify the more precise location of the operators as well as their function- alities. The paper is organized as follows. Section 2 introduces functionalisomorphism. In Section 3, we describe the def- inition and propagation oftransparentlogic. Proposed al- gorithms for identifying transparent logic are given in Sec- tion 4. Experimental results are shown in Section 5, while

Section 6 concludes this paper.

2. OVERVIEW

Roughly, a transparent path in a circuit has widthnand a set of controlsfsig, which when evaluated appropriately at a mintermsi=msi, moves a data-word (widthn) from the beginning of the path to the end. Such paths can fork and join in the circuit, and can begin and end at a set of inputs, outputs or internal signals. A path is maximal if there is no transparent path that can extend it. The termi- nals of maximal transparent paths are of interest because they likely delineate the input or output of an operator, e.g. an arithmetic function. A sink terminal can have many source terminals. Each signal in a sink terminal is a Boolean function of a) data signalsDk=fdj kgin the source terminals and b) the set of associated controlsfsigof transparent segments of any path from source to sink. Such a set of functions at a sink forms an npn equivalence class (or equivalently an npn isomorphism class). Each sink bit function typically (with some exceptions) looks likefk=P j2Dk(Q i2pathmsi)dj k. The isomorphism between the inputs of any two signalsfp

andfq(wherep;q2[1;n]) in the sink terminal isdjp$djqi.e. dierent bit positions in the same data word are iso-

morphically mapped to each other, while control signalssi are isomorphically mapped into themselves. Each coe- cient (Q i2pathmsi) is the predicate of the control signals under which a path from sourcedj kto the sinkfkbecomes transparent. The predicates are disjoint. It is possible that some bits of a terminal have been inverted, hence npn equivalence is considered in the subsequent discussions. Thus a transparent path's outputs is a subset of an npn isomorphism class. The isomorphism helps distinguish be- tween dierent data-words by factoring out common pred- icates (Q i2pathmsi) in the representative function of the equivalence class.

2.1 Npn Isomorphism

Two graphs,G1(V1;E1) andG2(V2;E2), areisomorphic,

if there exists a bijective mapping,M12:V1!V2, such that any two verticesuandvare adjacent inG1, if and only ifM12(u) andM12(v) are adjacent inG2[2]. Two circuits,C1andC2, are isomorphic to each other if their logic gates and connections form two isomorphic graphs, while any gategofC1and the mapped gateM12(g) in C

2are the same type. The relation betweenC1andC2is

calledstructural isomorphism, which has been applied to reverse engineering [5]. In contrast,functional isomorphismis a relation between two signals in a circuit. A signalfin a circuit, supported by a set of other signals,Sf, is a Boolean function of these inputs:f:BjSfj!B, forB=f0;1g. In the following sections, for a Boolean variablexiwith its polaritypi, (xi)pirepresents the function:pi= 0! (xi)pixiandpi= 1!(xi)piinv(xi).

Denition 1:A pair of Boolean functionsf(x1;:::xn)

andg(y1;:::;yn) arenpn isomorphic1, if there exists a permutationof sizenand polaritiespoutandfp1;:::;png

2Bnsuch that

f(x1;:::;xn) =gpout(xp1 (1);:::;xpn (n)) (1) i.e.,gcan be made equivalent tofby selectively negating inputs, permuting inputs, and negating the output. The implied isomorphic mapping between the supports ofgand fisfyi;xpi (i)gandpiis said to be the relative polarity between inputsyiandx(i). A set of signals in a circuit, in which every pair is func- tionally npn isomorphic is called annpn isomorphism class.

2.2 Composition of Npn Isomorphism

Although improved methods for computing npn equiva- lence can be found in Soekin et. al. [9], this still can be time-consuming. This eort can be reduced immensely by proving npn isomorphism on smaller logic blocks and com- posing proved classes to obtain larger ones. Larger classes help extend paths of transparency (discussed in Section 3) in a circuit and to more reliably nd transparency bound- aries, and hence the input/output boundaries of word-level operators. The following discussion details when compositions lead to larger npn isomorphisms. Denition 2: (polar consistency) Let (f(s);g(t)) be a pair of npn isomorphic functions with sets of supports s=fsigandt=ftjg, respectively. Suppose each pair of mapped input supports,si$tj, are npn isomorphic func- tions, i.e.si(x) is npn isomorphic totj(y). Letpij outbe the relative output polarity betweensi(x) andtj(y), andpijbe the relative input polarity between inputssiandtjin the npn isomorphism betweenf(s) andg(t). The compositions f(s(x)) andg(t(y)) arepolar consistent, ifpi(i) out=pi(i), whereis the permutation in the isomorphism mapping of (f(s);g(t)). Theorem 1:The compositions of (f(s(x)),g(t(y))) are polar consistent if and only iff(s(x)) andg(t(y)) are npn1 or Negation-Permutation-Negation (NPN) equivalentisomorphic.

3. TRANSPARENT LOGIC

As stated identifying maximaltransparent logic, can be used to identify input/output boundaries of arithmetic op- erators.

3.1 Transparent Words

Intuitively, atransparent wordis a set of signals,fwkg, with supports,fSkg, where under some evaluation of\kSk (common control),fwkgis equivalent to a subset (data- word) of[kSk. In other words, the control evaluation makes the word transparent from some input data-word. Example:Outputs of a set of 2-to-1 multiplexers (MUX) controlled by the same selector signals,

C[m1 : 0] =s?A[m1 : 0] :B[m1 : 0];(2)

comprises a transparent wordC, where8j2[0;m1], (C[j] =sA[j] +s0B[j]). For this case, wordCis trans- parent from wordAor wordB, depending on the value assigned tos.

Denition 3:FunctionsW=fwkjk2[1;m]gof an npn

isomorphism class comprise anm-bittransparent word, if:

1. Each functionwk:BSk!B, has supportSk=

(Control;Datak), (i.e.Controlis the set of common signals), and each bit ofControlis isomorphically mapped into itself.

2. The following formula isTrue, (wheremcis a minterm

ofControl,denotes functional equivalence, andwkm cdenotes the co-factor of functionwk(Control;Datak) with respect tomc). (9mc8k9dki2Datak9pki(wkm c(Datak)(dki)pk i)):(3)

3. For any (wx;wy)2W, the associated isomorphic sup-

port mappingMxy, satisesMxy(Datax) =Datay. Thus a transparent wordWis conditionally (bymc) equiv- alent to an input data word [(d1i)p1 i;:::;(dmi)pm i]. Based on the above denition, the vector of conditionally equiva- lent data support bits that have a common conditionmc, D i=fd1i;:::;dmigis called aninput word.

Given a transparent word,W=fwkg, with the corre-

sponding support partitionsf(Control;Datak)g, the en- tire support set ofWcan be partitioned intoControland Data

W=SiDi. The denition of transparent words can

be restated as follows:

Denition 4: A transparent wordWis a set of npn

isomorphism functions supported by controlControland dataDataW=SiDi, such that the following formula is True: 8

Di2DataW9mc9Pi(Wmc(DataW)(Di)Pi);(4)

wherePiset of polarity bits forDi. Although, for an input wordDi, there could be multiple minterms ofControlsatisfying Formula (4), the assign- ments ofmc2Controlfor dierentDis are disjoint. Example:Consider Equation(1): for eachC[j], the sup- port setfs;A[j];B[j]gcan be partitioned intoDataj= fA[j];B[j]gandControl=fsg, such that (s= 1)) (C[j] =A[j]) and (s= 0))(C[j] =B[j]). Hence a common (control) assignment applied to all bits of the transparent word, makes them transparent from the corre- sponding supports simultaneously. The supports ofCcan be partitioned intoDataC fA[m1 : 0];B[m1;0]g, andControl fsg. Since negations of some bits of transparent words might occur during synthesis, it seems reasonable to consider the logic still as "transparent". Note that in the exam- ple:C[j] =sA[j] +s0B[j] the negation of bitC[j] can be done by negating the data inputs,A[j] andB[j]: inv(C[j]) =inv(sA[j] +s0B[j]) =s inv(A[j]) +s0inv(B[j]):(5) butC(with some phase changes) can still be considered transparent fromAandBbecause the assignments to the control bits are unchanged. In Section 3.2 and 3.3, as we compose transparent sec- tions to form a larger transparent path, we will need to re- solve cases where only some bits of a transparent word are negated. However, for composing transparencies to nd larger ones, it is required that the polarities of the inputs and outputs are consistent. This can be done by negating some of the inputs of the path (using npn isomorphism) to get a compatible polarity at the output that feeds into another transparent word.

Theorem 2:Given a transparent wordW, the negation

of any output bitwkcan be done by negating the corre- sponding input data support bits, without changing any control assignment. The upshot is that when nding another transparent sec- tion of logic and composing it to extend a transparent path, this canalwaysbe done simply by negating the inputs to get compatible polarities at the point of composition.

3.2 Composition of Transparency

Similar to the composition of npn isomorphism, larger transparent functions are frequently created by composing smaller transparent blocks.

Example:In Figure 1, wordCis transparent fromA

andBunder the control ofs1, while a second transparent block consists of wordE, transparent fromCandDunder the control ofs2. Thus (s1= 1;s2= 1)!EA, while (s1= 0;s2= 1)!EBi.e. transparency ofEfrom AandBis obtained by composing of smaller transparent blocks. If some bits ofCare negated before feeding into the MUXes controlled bys2, the composition can be done by pushing the negation to the corresponding bits ofAand Bto maintain the polar consistency.Figure 1:A transparent word can be implemented by com- posing smaller transparent words.

Denition 5: LetW=fWk(X)jk= [1;n]gbe a set of

n m-bit transparent words, and letY=fyjjj= [1;m]gbeanother transparent word with supportDataY=WSV andControlY. Suppose each input word ofYis exactly one transparent word inWor one word inV. The set of compositions,

Z=fzjg=fyj(W(X);V;ControlY)g(6)

form acompound word, and are denoted asZ=YW.

Theorem 3: AssumeYis a transparent word andWis

a set of transparent words. Letfkigbe the set of minterms ofControlk, which enableWkto be transparent from an input wordxki2Datak, andfkgbe the set of minterms ofControlYfor (YWk). Using the notation:

Control

Z=ControlYS[[kControlk];

Data

Z=VS[[kDatak],

a compound word,ZYWis a transparent word con- trolled byControlZif 8 k8i(f^kig \ f^kg 6=;) (7) isTrue, wheref^kigandf^kgarefkigandfkgextended to cubes of the larger space ofControlZ, respectively. Proof

1. Based on Theorems 1 and 2,Zcan be an npn isomor-

phism class by ipping the polarities ofWkwhenever its output polarity is not consistent with the input polarities ofyk.

2. BecauseYis a transparent word, for each input word

inV, there must exist an assignment ofControlYto enable the transparency from V.

3. Conditions satisfying Formula 7 imply that for each

input wordxkiofWk, there exists an assignment of

Control

Zsuch that a)Wkis transparent fromxki,

b) Y is transparent fromWk, and c)Yis transpar- ent fromxki. Therefore,ZYWis a transpar- ent word with (ControlZ;DataZ) as control and data supports.

3.3 Propagation of Transparency

Example:Figure 2 illustrates how a longer transparency can be composed from non transparent sections of logic.C is transparent fromAwhens1= 1, andDis transparent fromBwhens2= 1, but the logic block fromCandD toEis not transparent (there is no common control sup- port for each bit ofE). However,Eis transparent from

Awhen (s1= 1;s2= 0), while (s1= 0;s2= 1) makesE

transparent fromB.Figure 2:A longer transparent word may be composed of smaller transparent words and an npn isomorphism class. When a transparent function block is composed of non- transparent sections, it is calledpropagation of transparency. The conditions when this can happen are stated in the fol- lowing.

Denition 6: (prodeeding word) LetWbe a set ofn

m-bit transparent words, and letY(W) =fyj(W)gbe an npn isomorphism class. Suppose eachyjis supported by exactly one bit of eachWk, and the isomorphically mapped supports ofyjare always from the same word ofW. The compositions,Z=fzjg=fyj(W(X))gare said to form a proceeding word.

Theorem 4: AssumeYandWare as in Denition 6

and the supports ofWkaresupp(Wk) = (Controlk;Datak). Letfkigbe the set of minterms ofControlkwhich cause (Wkxki), andfkgbe minterms of[kControlkwhich cause (YWk). UsingControlZ=[kControlk;and Data

Z=[kDatak, a proceeding word,ZYW, is a

transparent word controlled byControlZif 8 k8i(f^kig \ fkg 6=;);(8) wheref^kigrefers tofkigextended to cubes ofControlZ. Proof

1. Similar to the proof of Theorem 3,Zcan be an npn

isomorphism class by ipping the polarities ofWkif needed.

2. For each input wordxkiinDataZ, Formula 8 im-

plies that there exists an assignment ofControlZ, such thatWkxki,YWk, and thus,Yxki, implyingZYWis a transparent word with (ControlZ;DataZ) as control and data supports.

Example:In Figure 2,W= (C;D) andf^k1g=s1s2+

s 1s

2makesCtransparent fromA, whilef^k2g=s1s2+s

1s2 makesDtransparent fromB.fkg=s1s 2(s

1s2) causes

EC(ED). Note thatf^k1g \ fkg=s1s

26=;
andf^k2g \ fkg=s

1s26=;. Thus the conditions for

propagation of transparency are met, and thereforeEis transparent fromAandB.

4. TRANSPARENCY IDENTIFICATION

The functional approach proposed for transparency iden- tication relies only on dependencies among signals. It canquotesdbs_dbs35.pdfusesText_40