More Web Proxy on the site http://driver.im/

Article

Program Slicing of Hardware Description Languages

Authors:

Edmund M. Clarke,

Masahiro Fujita,

Sreeranga P. Rajan,

Thomas W. Reps,

Subash Shankar,

Tim TeitelbaumAuthors Info & Claims

CHARME '99: Proceedings of the 10th IFIP WG 10.5 Advanced Research Working Conference on Correct Hardware Design and Verification Methods

Pages 298 - 312

Published: 27 September 1999 Publication History

Abstract

Hardware description languages (HDLs) are used today to describe circuits at all levels. In large HDL programs, there is a need for source code reduction techniques to address a myriad of problems in formal verification, design, simulation, and testing. Program slicing is a static program analysis technique that allows an analyst to automatically extract portions of programs relevant to the aspects being analyzed. We extend program slicing to HDLs, thus allowing for automatic program reduction to allow the user to focus on relevant code portions. We have implemented a VHDL slicing tool composed of a general inter-procedural slicer and a front-end that captures VHDL execution semantics. This paper provides an overview of program slicing, a discussion of how to slice VHDL programs, a description of the resulting tool, and a brief overview of some applications and experimental results.

References

[1]

E.M. Clarke, E.A. Emerson, and A.P. Sistla. Automatic verification of finite-state concurrent systems using temporal logic specifications. ACM Transactions on Programming Languages and Systems, 8(2):244-263, April 1986.

[2]

D. DÉharbe, S. Shankar, and E.M. Clarke. Model checking VHDL with CV. In Formal Methods in Computer Aided Design (FMCAD), page to appear, 1997.

[3]

M. Weiser. Program slicing. IEEE Transactions on Software Engineering, 10(4):352-357, 1984.

[4]

M. Weiser. Program slices: Formal, psychological, and practical investigations of an automatic program abstraction method. PhD thesis, University of Michigan, 1979.

[5]

K.J. Ottenstein and L.M. Ottenstein. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pages 177-184, New York, NY, 1984. ACM Press.

[6]

J. Ferrante, K. Ottenstein, and J. Warren. The program dependence graph and its use in optimization. ACM Transactions on Programming Languages and Systems, 3(9):319-349, 1987.

[7]

S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems, 12(1):26-60, January 1990.

[8]

S. Horwitz, T. Reps, M. Sagiv, and G. Rosay. Speeding up slicing. In Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, pages 11-20, New York, NY, December 1994. ACM Press.

[9]

F. Tip. A survey of program slicing techniques. Technical Report CS-R9438, Centrum voor Wiskunde en Informatica, 1994.

[10]

D. Binkley and K. Gallagher. Program slicing. In M. Zelkowitz, editor, Advances in Computers, Vol. 43. Academic Press, San Diego, CA, 1996.

[11]

K.B. Gallagher and J.R. Lyle. Using program slicing in software maintenance. IEEE Transactions on Software Engineering, SE-17(8):751-761, August 1991.

[12]

J. Lyle and M. Weiser. Experiments on slicing-based debugging tools. In Proceedings of the First Conference on Empirical Studies of Programming, June 1986.

[13]

D. Binkley. Using semantic differencing to reduce the cost of regression testing. In Proceedings of the 1992 Conference on Software Maintenance (Orlando, FL, November 9-12, 1992), pages 41-50, 1992.

[14]

S. Bates and S. Horwitz. Incremental program testing using program dependence graphs. In ACM Symposium on Principles of Programming Languages, pages 384- 396, 1993.

[15]

S. Horwitz, J. Prins, and T. Reps. Integrating non-interfering versions of programs. ACM Transactions on Programming Languages and Systems, 11(3):345-387, July 1989.

[16]

S. Horwitz. Identifying the semantic and textual differences between two versions of a program. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 234-245, 1990.

[17]

T. Reps and T. Turnidge. Program specialization via program slicing. In O. Danvy, R. Glueck, and P. Thiemann, editors, Proc. of the Dagstuhl Seminar on Partial Evaluation, volume 1110 of Lecture Notes in Computer Science, pages 409-429, Schloss Dagstuhl, Wadern, Germany, February 1996. Springer-Verlag.

[18]

J.Q. Ning, A. Engberts, and W. Kozaczynski. Automated support for legacy code understanding. Communications of the ACM, 37(5):50-57, May 1994.

[19]

D. Jackson and E.J. Rollins. A new model of program dependences for reverse engineering. SIGSOFT 94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes, 19, December 1994.

[20]

T. Reps and G. Rosay. Precise interprocedural chopping. SIGSOFT 95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, (Washington, DC, October 10-13, 1995), ACM SIGSOFT Software Engineering Notes, 20(4), 1995.

[21]

D. Binkley. Precise executable interprocedural slices. ACM Letters on Programming Languages and Systems, 2:31-45, 1993.

[22]

M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE- 10(4):352-357, July 1984.

[23]

IEEE. IEEE Standard VHDL Language Reference Manual, 1987. Std 1076-1987.

[24]

E.M. Clarke, M. Fujita, S.P. Rajan, T. Reps, S. Shankar, and T. Teitelbaum. Program slicing of hardware description languages. Technical Report CMU-CS- 99-103, Carnegie Mellon University, 1999.

[25]

M. Iwaihara, M. Nomura, S. Ichinose, and H. Yasuura. Program slicing on VHDL descriptions and its applications. In Asian Pacific Conference on Hardware Description Languages (APCHDL), pages 132-139, 1996.

[26]

S. Ichinose, M. Iwaihara, and H. Yasuura. Program slicing on VHDL descriptions and its evaluation. Technical report, Kyushu University, 1998.

[27]

L. Millett and T. Teitelbaum. Slicing promela and its applications to protocol understanding and analysis. In 4th International SPIN Workshop, pages 75-83, 1998.

[28]

Robert P. Kurshan. "Computer-Aided Verification of Coordinating Processes". Princeton University Press, 1994.

[29]

T. Reps. Program analysis via graph reachability. In Proc. of ILPS '97: Int. Logic Programming Symposium, pages 5-19, Cambridge, MA, 1997. M.I.T.

Cited By

Chen TRucker ASuh GPrvulovic M(2015)Execution time prediction for energy-efficient hardware acceleratorsProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830798(457-469)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830798
Liu LVasudevan S(2014)Scaling Input Stimulus Generation through Hybrid Static and Dynamic Analysis of RTLACM Transactions on Design Automation of Electronic Systems10.1145/267654920:1(1-33)Online publication date: 18-Nov-2014
https://dl.acm.org/doi/10.1145/2676549
Malburg JFinder AFey GMacii E(2013)Tuning dynamic data flow analysis to support design understandingProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485572(1179-1184)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485572
Show More Cited By

Program Slicing of Hardware Description Languages

Recommendations

The VHSIC hardware description language (VHDL) program
DAC '84: Proceedings of the 21st Design Automation Conference

The emergence of the importance of VLSI design automation and the VLSI custom/semicustom industry has spurred a wide-spread interest in hardware description languages. Starting in 1981, the VHSIC Program has acted as a catalyst to develop a standard ...
Abstract Program Slicing: An Abstract Interpretation-Based Approach to Program Slicing

In the present article, we formally define the notion of abstract program slicing, a general form of program slicing where properties of data are considered instead of their exact value. This approach is applied to a language with numeric and reference ...
Characterizing the Expressivity of Game Description Languages
PRICAI 2019: Trends in Artificial Intelligence
Abstract
Bisimulations are a key notion to study the expressive power of a modal language. This paper studies the expressiveness of Game Description Language (GDL) and its epistemic extension EGDL through a bisimulations approach. We first define a notion ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CHARME '99: Proceedings of the 10th IFIP WG 10.5 Advanced Research Working Conference on Correct Hardware Design and Verification Methods

September 1999

364 pages

ISBN:3540665595

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 27 September 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen TRucker ASuh GPrvulovic M(2015)Execution time prediction for energy-efficient hardware acceleratorsProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830798(457-469)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830798
Liu LVasudevan S(2014)Scaling Input Stimulus Generation through Hybrid Static and Dynamic Analysis of RTLACM Transactions on Design Automation of Electronic Systems10.1145/267654920:1(1-33)Online publication date: 18-Nov-2014
https://dl.acm.org/doi/10.1145/2676549
Malburg JFinder AFey GMacii E(2013)Tuning dynamic data flow analysis to support design understandingProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485572(1179-1184)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485572
Liu LVasudevan SAyala JJones AMadden PCoskun A(2013)Scaling RTL property checking using feasible path analysisand decompositionProceedings of the 23rd ACM international conference on Great lakes symposium on VLSI10.1145/2483028.2483086(173-178)Online publication date: 2-May-2013
https://dl.acm.org/doi/10.1145/2483028.2483086
Liu LLin CVasudevan SHu A(2012)Word level feature discovery to enhance quality of assertion miningProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429424(210-217)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429424
Malburg JFinder AFey GGroeneveld PSciuto DHassoun S(2012)Automated feature localization for hardware designs using coverage metricsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228529(941-946)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228529
Kumar JLiu LVasudevan SBjesse PSlobodová A(2011)Scaling probabilistic timing verification of hardware using abstractions in design source codeProceedings of the International Conference on Formal Methods in Computer-Aided Design10.5555/2157654.2157684(196-205)Online publication date: 30-Oct-2011
https://dl.acm.org/doi/10.5555/2157654.2157684
Viswanath VAbraham JHunt WGielen G(2006)Automatic insertion of low power annotations in RTL for pipelined microprocessorsProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131616(496-501)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131616
Peischl BWotawa F(2006)Automated Source-Level Error Localization in Hardware DesignsIEEE Design & Test10.1109/MDT.2006.523:1(8-19)Online publication date: 1-Jan-2006
https://dl.acm.org/doi/10.1109/MDT.2006.5
Dwyer MHatcliff JHoosier MRanganath VRobby Wallentine T(2006)Evaluating the effectiveness of slicing for model reduction of concurrent object-oriented programsProceedings of the 12th international conference on Tools and Algorithms for the Construction and Analysis of Systems10.1007/11691372_5(73-89)Online publication date: 25-Mar-2006
https://dl.acm.org/doi/10.1007/11691372_5
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents