Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Boolean Function
combinational circuit
Data Structure
Heuristic Algorithm
Logic Synthesis
Ordered Binary Decision Diagram
Related Publications
(66)
Evaluation and improvement of Boolean comparison method based on binary decision diagrams
Representing circuits more efficiently in symbolic model checking
Efficient Implementation of a BDD Package
Sample Method for Minimization of OBDDs
GraphBased Algorithms for Boolean Function Manipulation
Subscribe
Academic
Publications
Dynamic variable ordering for ordered binary decision diagrams
Dynamic variable ordering for ordered binary decision diagrams,10.1145/259794.259802,Richard L. Rudell
Edit
Dynamic variable ordering for ordered binary decision diagrams
(
Citations: 666
)
BibTex

RIS

RefWorks
Download
Richard L. Rudell
The
Ordered Binary Decision Diagram
OBDI)) has proven useful in many applications as an efficient
data structure
for reprtxenting and manipulating Boolean functions. A serious drawback of OBDD’s is the need for applicationspecijic heuristic algorithms to order the variables before processing. Further, for many problem instances in logic synthesis, the heuristic ordering algorithms which have been proposed are insufficient to allow OBDD operations to complete within a limited amount of memory. In this paper, I propose a solution to these problems based on having the OBDD package itself determine and maintain the variable order.This is done by periodically applying a minimization algorithm to reorder the variables of the OBDD to reduce its size. A new OBDD minimization algorithm,called the sifting algorithm, is proposed and appears especially eflective in reducing the size of the OBDD.Experiments with dynamic variable ordering on the problem of forming the OEIDD’s for the primary outputs of a
combinational circuit
show that many computations comp!ete using dynamic variable ordering when the same computation fails otherwise.
Conference:
International Conference on Computer Aided Design  ICCAD
, pp. 4247, 1993
DOI:
10.1145/259794.259802
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
doi.acm.org
)
(
portal.acm.org
)
More »
Citation Context
(382)
...The sifting approach was original proposed for binary decision diagrams [
40
] and used in edgecrossing minimize in circle layout [37]...
Liang Gou
.
TreeNetViz: Revealing Patterns of Networks over Tree Structures
...A specific operation has proved to be particularly effective in practice, that of swapping adjacent layers [5], [
6
]...
...Reordering algorithms are typically used in a dynamic fashion: If a size threshold is crossed during the execution of a BDD operation, reordering is triggered to reduce the size of the BDD [
6
]...
...The Sifting algorithm [
6
] works by ordering the variables according to the sizes (widths) of their layers...
Stergios Stergiou
.
Implicit Permutation Enumeration Networks and Binary Decision Diagrams...
...Sifting was originally introduced as a heuristic for vertex minimization in ordered binary decision diagrams [
18
] and later adapted for the onesided crossing minimization problem [19]...
Christian Bachmaier
,
et al.
Crossing minimization in extended level drawings of graphs
...Standard optimization techniques (e.g. sifting [
28
]) have been thereby utilized...
Mathias Soeken
,
et al.
Hierarchical Synthesis of Reversible Circuits Using Positive and Negat...
...At the same time, all basic principles in programming decision diagrams as specified in [
14
] for binary functions and in [10] for multiplevalued functions are applicable and consequently implemented...
Stanislav Stankovic
,
et al.
Heterogeneous Decision Diagrams for Applications in Harmonic Analysis ...
References
(13)
Efficient Implementation of a BDD Package
(
Citations: 870
)
Karl S. Brace
,
Richard L. Rudell
,
Randal E. Bryant
Conference:
Design Automation Conference  DAC
, pp. 4045, 1990
GraphBased Algorithms for Boolean Function Manipulation
(
Citations: 5307
)
Randal E. Bryant
Journal:
IEEE Transactions on Computers  TC
, vol. C35, no. 8, pp. 677691, 1986
Evaluation and improvement of Boolean comparison method based on binary decision diagrams
(
Citations: 195
)
Masahiro Fujita
,
Hisanori Fujisawa
,
Nobuaki Kawato
Conference:
IEEE International Conference on ComputerAided Design  ICCAD
, 1988
On variable ordering of binary decision diagrams for the application of multilevel logic synthesis
(
Citations: 168
)
Masahiro Fujita
,
Yusuke Matsunaga
,
Taeko Kakuda
Conference:
European Design and Test Conference  EURODAC
, pp. 5054, 1991
Minimazation of Binary Decision Diagrams Based on Exchanges of Variables
(
Citations: 132
)
Nagisa Ishiura
,
Hiroshi Sawada
,
Shuzo Yajima
Conference:
International Conference on Computer Aided Design  ICCAD
, pp. 472475, 1991
Sort by:
Citations
(666)
TreeNetViz: Revealing Patterns of Networks over Tree Structures
Liang Gou
Journal:
IEEE Transactions on Visualization and Computer Graphics  TVCG
, vol. 17, no. 12, pp. 24492458, 2011
Implicit Permutation Enumeration Networks and Binary Decision Diagrams Reordering
Stergios Stergiou
Published in 2011.
Crossing minimization in extended level drawings of graphs
(
Citations: 2
)
Christian Bachmaier
,
Hedi Buchner
,
Michael Forster
,
SeokHee Hong
Journal:
Discrete Applied Mathematics  DAM
, vol. 158, no. 3, pp. 159179, 2010
Hierarchical Synthesis of Reversible Circuits Using Positive and Negative Davio Decomposition
(
Citations: 1
)
Mathias Soeken
,
Robert Wille
,
Rolf Drechsler
Conference:
International Design and Test Workshop  IDT
, 2010
A Global kLevel Crossing Reduction Algorithm
Christian Bachmaier
,
FranzJosef Brandenburg
,
Wolfgang Brunner
,
Ferdinand Hübner
Conference:
Workshop on Algorithms and Computation  WALCOM
, pp. 7081, 2010