DOC PREVIEW
Berkeley ECON 219B - SPFDs - A new method for specifying flexibility

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

SPFDs - A new method for specifying flexibilityMethods for Expressing Sets of FunctionsODCs and SPFDsSlide 4ISFsBuilding FSlide 7Distributing the jobInput GraphsAssigning ValuesSlide 11SPFDsImplementsCompatibleRe-implementing a FunctionSlide 16Re-implementing the Inputs to a FunctionSlide 18Re-using Old TopologySlide 20Efficient Re-implementationEnd of lecture 15Slide 23How Do We Use ThisConclusions and futureRuggedizing SPFD computationMV-SPFDs and Wire RemovalWire Removal and Wire SubstitutionDon’t Care WiresCompatible sets of don’t care wiresChoosing best subset of wiresPlacement using don’t care wiresExperiments – total wire length (placement, no routing)Wireplanning before decompositionInformation Flow Theorem1SPFDs - A new method for SPFDs - A new method for specifying flexibilityspecifying flexibilitySSets of ets of PPairs of airs of FFunctions to be unctions to be DDistinguishedistinguishedFrom the paper:From the paper:““A new Method to Express Functional A new Method to Express Functional Permissibilities for LUT Based Permissibilities for LUT Based FPGAsFPGAs and Its and Its Applications Applications ” ” by S. Yamashita, H. Sawada, and A. Nagoya, NTT by S. Yamashita, H. Sawada, and A. Nagoya, NTT Communications Science Lab., Kyoto, Japan Communications Science Lab., Kyoto, Japan ICCAD’96ICCAD’96BUTBUT:: this paper is more about a this paper is more about a new kindnew kind of “don’t of “don’t cares”, rather than about application to FPGAscares”, rather than about application to FPGAs2Methods for Expressing Methods for Expressing Sets of FunctionsSets of Functions•Don’t Cares Don’t Cares (=> incompletely specified (=> incompletely specified functions (functions (ISFsISFs))))–Satisfiability DCsSatisfiability DCs–Observability DCsObservability DCs–XDCsXDCs•ATPG Redundancy RemovalATPG Redundancy Removal•Boolean RelationsBoolean Relations•Sets of Boolean RelationsSets of Boolean Relations•SPFDs. SPFDs. (Actually, they are (Actually, they are setssets of ISFs). of ISFs).3ODCs and SPFDsODCs and SPFDsODCs:ODCs:–Different ways to compute themDifferent ways to compute them•Full method (difficult)Full method (difficult)•SubsetsSubsets–Compatible Sets of Permissible functions Compatible Sets of Permissible functions (CSPFs)(CSPFs)»(Easier to compute)(Easier to compute)–Compatible observability don’t cares Compatible observability don’t cares ((CODCsCODCs))»see Savoj thesis - generalization of CSPFssee Savoj thesis - generalization of CSPFs–CSPFs and CODCsCSPFs and CODCs•have advantage that they can be computed fast - from have advantage that they can be computed fast - from outputs to inputsoutputs to inputs•are independentare independent4ODCs and SPFDsODCs and SPFDsSPFDs:SPFDs:•like like CSPFs/CODCsCSPFs/CODCs –can be computed fast from outputs to can be computed fast from outputs to inputsinputs–are independentare independent•but but more powerfulmore powerful and and •not a subsetnot a subset of DCs ( of DCs (they are a sets of they are a sets of ISFsISFs))5ISFsISFsUsually we deal with binary ISFs.Usually we deal with binary ISFs.–They can be represented as They can be represented as complete bipartite graphscomplete bipartite graphs on on minterms.minterms.–Vertices are minterms. Set of vertices may be Vertices are minterms. Set of vertices may be subsetsubset of all of all mintermsminterms–An An edgeedge means that we need to build a function that means that we need to build a function that distinguishesdistinguishes (i.e. has different values) the two minterms on the edge.(i.e. has different values) the two minterms on the edge.A connected bipartite graph has only A connected bipartite graph has only twotwo colorings, one the colorings, one the onsetonset and the other the and the other the offsetoffset and vice versa ( and vice versa (onsetonset, , offsetoffset))offsetoffsetonsetonset6Building FBuilding FWe start with a complete bipartite graph (ISF) for F. This We start with a complete bipartite graph (ISF) for F. This gives a set of minterms that must be distinguished.gives a set of minterms that must be distinguished.FFgg11gg22gg33yy11yy22yy33xxYY space is (y space is (y11,y,y22,y,y33). ). Each yEach yii is a minterm in is a minterm in YYyy11yy33yy22yy44yy557Building FBuilding FSuppose that the inputs to F are Suppose that the inputs to F are y = (gy = (g11(x), g(x), g22(x), g(x), g33(x)). (x)). As long as {yAs long as {y11, y, y22, y, y33} are } are encodedencoded differently from {y differently from {y44, y, y55} by } by g(x), there exists a function F which implements the ISF.g(x), there exists a function F which implements the ISF.yy11yy33yy22yy44yy551 42 53001 101 100 001010 110 101 111011 010y yy yyoldoldnewnewoldoldnewnewNew F:New F:(101) 1 (001) 0(110) 1 (111) 0(010) 1f ff ff= == ==8Distributing the jobDistributing the jobWe can We can distributedistribute the “encoding” job separately to the the “encoding” job separately to the input wires.input wires.Note:Note: as long as each edge is distinguished by one of the inputs, as long as each edge is distinguished by one of the inputs, this is sufficient for a new encodingthis is sufficient for a new encoding. . yy11yy33yy22yy44yy55yy11yy22yy55yy44input 1input 1yy22yy33yy55yy44input 2input 2yy11yy33yy44yy55input 3input 39Input GraphsInput GraphsEach of the edges on the input graphs means Each of the edges on the input graphs means that the input signal gthat the input signal gii(x) has to have a (x) has to have a different value for the two nodes.different value for the two nodes.Note:Note: the graphs are bipartite, but the graphs are bipartite, but not completenot complete and may be and may be disconnecteddisconnected. In the above case, . In the above case, each graph has 4 different legal colorings.each graph has 4 different legal colorings.yy11yy22yy55yy44input 1input 1yy22yy33yy55yy44input 2input 2yy11yy33yy44yy55input 3input 310Assigning ValuesAssigning ValuesNow we can assign values to the graphs Now we can assign values to the graphs (color the (color the graphs).graphs).Thus, for exampleThus, for exampleyy11=1*1, y=1*1, y22=00*, y=00*, y33=*10, y=*10, y44=011, y=011, y55=100=100yy11yy22yy55yy44input 1input 1yy22yy33yy55yy44input 2input 2yy11yy33yy44yy55input 3input 311Assigning ValuesAssigning ValuesNote that yNote that y11, y, y22, y, y33, y, y44, y, y55 are all distinctly encoded in this


View Full Document

Berkeley ECON 219B - SPFDs - A new method for specifying flexibility

Download SPFDs - A new method for specifying flexibility
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view SPFDs - A new method for specifying flexibility and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SPFDs - A new method for specifying flexibility 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?