Linear sifting of decision diagrams and its application in synthesis
Identifieur interne : 000C89 ( PascalFrancis/Checkpoint ); précédent : 000C88; suivant : 000C90Linear sifting of decision diagrams and its application in synthesis
Auteurs : Christoph Meinel [Allemagne] ; F. Somenzi ; T. TheobaldSource :
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems [ 0278-0070 ] ; 2000.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
We propose a new algorithm, called linear sifting, for the optimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. The new algorithm is applicable to large examples, and in many cases leads to substantially more compact diagrams when compared to simple variable reordering. We also show in what sense linear transformations complement variable reordering and how the technique can be applied to verification issues. Going a step further, we discuss a synthesis scenario where-due to the complexity of the target function-it is inevitable to decompose the function in a preprocessing step. By using linear sifting it is possible to extract a linear filter and, hence, to achieve the necessary decomposition. Using this method we were able to synthesize functions with standard tools which fail otherwise.
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:00-0342583Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Linear sifting of decision diagrams and its application in synthesis</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Univ Trier</s1><s2>Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Somenzi, F" sort="Somenzi, F" uniqKey="Somenzi F" first="F." last="Somenzi">F. Somenzi</name></author><author><name sortKey="Theobald, T" sort="Theobald, T" uniqKey="Theobald T" first="T." last="Theobald">T. Theobald</name></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">00-0342583</idno><date when="2000">2000</date><idno type="stanalyst">PASCAL 00-0342583 EI</idno><idno type="RBID">Pascal:00-0342583</idno><idno type="wicri:Area/PascalFrancis/Corpus">000F28</idno><idno type="wicri:Area/PascalFrancis/Curation">000041</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000C89</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C89</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Linear sifting of decision diagrams and its application in synthesis</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Univ Trier</s1><s2>Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><wicri:noRegion>Univ Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Somenzi, F" sort="Somenzi, F" uniqKey="Somenzi F" first="F." last="Somenzi">F. Somenzi</name></author><author><name sortKey="Theobald, T" sort="Theobald, T" uniqKey="Theobald T" first="T." last="Theobald">T. Theobald</name></author></analytic><series><title level="j" type="main">IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</title><title level="j" type="abbreviated">IEEE Trans Comput Aided Des Integr Circuits Syst</title><idno type="ISSN">0278-0070</idno><imprint><date when="2000">2000</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</title><title level="j" type="abbreviated">IEEE Trans Comput Aided Des Integr Circuits Syst</title><idno type="ISSN">0278-0070</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Binary decision diagrams</term><term>Boolean functions</term><term>Combinatorial circuits</term><term>Data structures</term><term>Decision diagrams</term><term>Experiments</term><term>Linear sifting</term><term>Linear transformations</term><term>Mathematical transformations</term><term>Matrix algebra</term><term>Optimization</term><term>Spectrum analysis</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Expérience</term><term>Optimisation</term><term>Algorithme</term><term>Transformation mathématique</term><term>Fonction booléenne</term><term>Algèbre matricielle</term><term>Analyse spectre</term><term>Circuit combinatoire</term><term>Structure donnée</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We propose a new algorithm, called linear sifting, for the optimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. The new algorithm is applicable to large examples, and in many cases leads to substantially more compact diagrams when compared to simple variable reordering. We also show in what sense linear transformations complement variable reordering and how the technique can be applied to verification issues. Going a step further, we discuss a synthesis scenario where-due to the complexity of the target function-it is inevitable to decompose the function in a preprocessing step. By using linear sifting it is possible to extract a linear filter and, hence, to achieve the necessary decomposition. Using this method we were able to synthesize functions with standard tools which fail otherwise.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0278-0070</s0></fA01><fA03 i2="1"><s0>IEEE Trans Comput Aided Des Integr Circuits Syst</s0></fA03><fA05><s2>19</s2></fA05><fA06><s2>5</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Linear sifting of decision diagrams and its application in synthesis</s1></fA08><fA11 i1="01" i2="1"><s1>MEINEL (C.)</s1></fA11><fA11 i1="02" i2="1"><s1>SOMENZI (F.)</s1></fA11><fA11 i1="03" i2="1"><s1>THEOBALD (T.)</s1></fA11><fA14 i1="01"><s1>Univ Trier</s1><s2>Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></fA14><fA20><s1>521-533</s1></fA20><fA21><s1>2000</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>222 X</s2></fA43><fA44><s0>A100</s0></fA44><fA45><s0>36 Refs.</s0></fA45><fA47 i1="01" i2="1"><s0>00-0342583</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</s0></fA64><fA66 i1="01"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>We propose a new algorithm, called linear sifting, for the optimization of decision diagrams that combines the efficiency of sifting and the power of linear transformations. The new algorithm is applicable to large examples, and in many cases leads to substantially more compact diagrams when compared to simple variable reordering. We also show in what sense linear transformations complement variable reordering and how the technique can be applied to verification issues. Going a step further, we discuss a synthesis scenario where-due to the complexity of the target function-it is inevitable to decompose the function in a preprocessing step. By using linear sifting it is possible to extract a linear filter and, hence, to achieve the necessary decomposition. Using this method we were able to synthesize functions with standard tools which fail otherwise.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02B07B</s0></fC02><fC02 i1="02" i2="X"><s0>001D01A</s0></fC02><fC02 i1="03" i2="X"><s0>001A02B</s0></fC02><fC02 i1="04" i2="X"><s0>001D02A</s0></fC02><fC02 i1="05" i2="X"><s0>001A02D</s0></fC02><fC02 i1="06" i2="X"><s0>001D02A04</s0></fC02><fC03 i1="01" i2="1" l="ENG"><s0>Decision diagrams</s0><s4>INC</s4></fC03><fC03 i1="02" i2="1" l="ENG"><s0>Linear sifting</s0><s4>INC</s4></fC03><fC03 i1="03" i2="1" l="ENG"><s0>Linear transformations</s0><s4>INC</s4></fC03><fC03 i1="04" i2="1" l="ENG"><s0>Binary decision diagrams</s0><s4>INC</s4></fC03><fC03 i1="05" i2="1" l="FRE"><s0>Expérience</s0></fC03><fC03 i1="05" i2="1" l="ENG"><s0>Experiments</s0></fC03><fC03 i1="06" i2="1" l="FRE"><s0>Optimisation</s0></fC03><fC03 i1="06" i2="1" l="ENG"><s0>Optimization</s0></fC03><fC03 i1="07" i2="1" l="FRE"><s0>Algorithme</s0></fC03><fC03 i1="07" i2="1" l="ENG"><s0>Algorithms</s0></fC03><fC03 i1="08" i2="1" l="FRE"><s0>Transformation mathématique</s0></fC03><fC03 i1="08" i2="1" l="ENG"><s0>Mathematical transformations</s0></fC03><fC03 i1="09" i2="1" l="FRE"><s0>Fonction booléenne</s0></fC03><fC03 i1="09" i2="1" l="ENG"><s0>Boolean functions</s0></fC03><fC03 i1="10" i2="1" l="FRE"><s0>Algèbre matricielle</s0></fC03><fC03 i1="10" i2="1" l="ENG"><s0>Matrix algebra</s0></fC03><fC03 i1="11" i2="1" l="FRE"><s0>Analyse spectre</s0></fC03><fC03 i1="11" i2="1" l="ENG"><s0>Spectrum analysis</s0></fC03><fC03 i1="12" i2="1" l="FRE"><s0>Circuit combinatoire</s0></fC03><fC03 i1="12" i2="1" l="ENG"><s0>Combinatorial circuits</s0></fC03><fC03 i1="13" i2="1" l="FRE"><s0>Structure donnée</s0><s3>P</s3></fC03><fC03 i1="13" i2="1" l="ENG"><s0>Data structures</s0><s3>P</s3></fC03><fN21><s1>234</s1></fN21></pA></standard></inist><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><noCountry><name sortKey="Somenzi, F" sort="Somenzi, F" uniqKey="Somenzi F" first="F." last="Somenzi">F. Somenzi</name><name sortKey="Theobald, T" sort="Theobald, T" uniqKey="Theobald T" first="T." last="Theobald">T. Theobald</name></noCountry><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C89 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000C89 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:00-0342583
|texte= Linear sifting of decision diagrams and its application in synthesis
}}
| This area was generated with Dilib version V0.6.31. |  |