Sequence Compaction to Preserve Transition Frequencies Page: 2 of 16
This report is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
are used for their accuracy at least before taping out a chip . For a review of
power estimation literature, surveys by Pedram [1; 3] are valuable resources.
For a CMOS circuit, dominant source of power dissipation is dynamic transition
current. In combinational circuits, power consumption corresponding to an input
vector sequence depends only on the transitions between successive input vectors.
Thus if a given vector sequence can be transformed to a shorter one while preserving
the transition frequencies, the shorter sequence can be used to estimate power
consumption for the original. Some recent works studied this problem for both
sequential and combinational circuits. Methods proposed by Tsui et al.  and
Marculescu et al.  have the disadvantage of generating vectors that are not in
the original sequence. Huang et al.  used a two phase strategy: the first phase
derives transition profile of internal signals by a fast power estimator, and the
second phase generates a shorter sequence using this profile. Marculescu et al. 
used a Markov model to generate a compact sequence and subsequently proposed a
hierarchical model with macro and micro states to model the original sequence .
Finally, earlier results of our work were presented in . Methods for sequential
circuits have been studied in [9; 10].
This paper investigates combinatorial aspects of compacting a sequence with
invariant transition frequencies. We call this problem the Sequence Compaclion
problem. We prove the problem is NP-Complete, thus a practical solution requires
heuristics. We also propose a graph model to reduce the sequence compaction
problem to that of finding a heaviest weighted trail on a directed graph, along with a
heuristic to find such trails. In our model, each distinct vector in the input sequence
defines a vertex, and each transition is represented by a number of parallel edges.
The number of parallel edges and the weight of each edge is defined by how many
times the transition appears in the original sequence. We also discuss generating
multiple sequences with different compaction factors, as opposed to merely a single
sequence, for better accuracy with even shorter sequences.
Proposed techniques have been applied to MCNC91 circuits , using SPICE
for simulations. Experiments verify that simulation times can be significantly re-
duced with highly accurate results. Error in estimations is limited to only 2.3%,
while the simulations are 10 times faster. We also investigated the reliability of
compacted sequences. The objective of compaction is to avoid simulating long
sequences, so accuracy of an estimation is not verifiable. A compacted sequence
is reliable, if it preserves all transition frequencies. A compacted sequence might
still give a good estimation, albeit unpreserved transition frequencies, but such a
sequence is not reliable. Our experiments verify that generated sequences preserve
the transition frequencies with great accuracy, thus are reliable. Experiments also
show that solutions are very close to optimal, and scale well with higher compaction
factors and longer sequences. Experiments also confirmed that multiple sequences
grant better accuracy with even shorter simulation times.
The next section defines the problem, and proves its NP-Completeness. A graph
model to reduce the problem to that of finding a heaviest weighted trail in a di-
rected graph, and a heuristic based on this model are the subject of @ 3. Using
multiple sequences for power estimation is discussed in @ 4. Experimental results
are presented in @ 5, followed by concluding remarks and future work in @ 6.
Here’s what’s next.
This report can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Report.
Pinar, Ali & Liu, C.L. Sequence Compaction to Preserve Transition Frequencies, report, December 12, 2002; Berkeley, California. (digital.library.unt.edu/ark:/67531/metadc740885/m1/2/: accessed August 21, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.