Evaluation methods in SARA—the graph model simulator
Pages 189 - 206
Abstract
The supported methodology evolving in the SARA (System ARchitects' Apprentice) system creates a design frame-work on which increasingly powerful analytical tools are to be grafted. Control flow analyses and program verification tools have shown promise. However, in the realm of the complex systems which interest us there is a great deal of research and development to be done before we can count on the use of such powerful tools. We must always be prepared to resort to experiments for evaluation of proposed designs.
This paper describes a fundamental SARA tool, the graph model simulator. During top-down refinement of a design, the simulator is used to test consistency between the levels of abstraction. During composition, known building blocks are linked together and the composite graph model is tested relative to the lowest top-down model. Design of test environments is integrated with the multilevel design process. The SARA methodology is exemplified through design of a higher level building block to do a simple FFT.
References
[1]
Overman, W. T. "Formal Verification of GMB's", Internal Memorandum 176, Computer Science Department UCLA, Los Angeles CA, July 1977.
[2]
Estrin, G. "A Methodology for design of digital systems - supported by SARA at the age of one", AFIPS Conference Proceedings, National Computer Conference, 1978.
[3]
Campos, I. "Multilevel Modeling for Synthesis of Reliable Concurrent Software Systems", Ph.D. dissertation, Computer Science Department, University of California, Los Angeles, 1977.
[4]
Gardner R.I. "Multi-level Modeling in SARA", Proceedings of the Symposium on Design Automation and Microprocessors, Palo Alto, CA, pp. 63-66 February 1977.
[5]
Estrin, G. and R. Turn, "Automatic Assignment of Computations in a Variable Structure Computer System," IEEE Transactions on Electronic Computers, Vol. EC-12, No. 5, December 1963.
[6]
Martin, D.F. and G. Estrin, "Experiments on Models of Computations and Systems," IEEE Transactions on Electronic Computers, Vol. EC-16, No. 1, pp. 59-69, February 1967.
[7]
Martin, D. and G. Estrin, "Models of Computational Systems-Cyclic to Acyclic Graph Transformations," IEEE Transactions on Electronic Computers, Vol. EC-16, No. 1, pp. 70-79, February 1967.
[8]
Baer, J. L. E., and G. Estrin, "Bounds for Maximum Parallelism in a Bilogic Graph Model of Computation," IEEE Transactions on Computers, Vol. C-18, No. 11, November 1969.
[9]
Martin D. F. and G. Estrin, "Path Length Computations on Graph Models of Computations," IEEE Transactions on Computers, Vol. EC-18, pp. 530-536, June 1969.
[10]
Russell, E. and G. Estrin, "Measurement based automatic analysis of FORTRAN programs", AFIPS Conference Proceedings, Spring Joint Computer Conference, Vol. 34, pp. 723-732, 1969.
[11]
Bovet, D. and G. Estrin, "A Dynamic Memory Allocation Algorithm," IEEE Transactions on Computers, Vol. C-19, No. 5, pp. 403-411, May 1970.
[12]
Bovet, D. and G. Estrin, "On Static Memory Allocation in Computer Systems," IEEE Transactions on Computers, Vol. C-19, No. 6. pp. 492-503, June 1970.
[13]
Volansky, S. A. "Graph Model Analysis and Implementation of Computational Sequences", Ph.D dissertation, UCLA-ENG-7048, June 1970.
[14]
Gostelow, K. P. "Flow of Control, Resource Allocation and the Proper Termination of Programs", Ph.D Dissertation, Computer Science Department, University of California, Los Angeles, CA. 1971.
[15]
Cerf. V., "Multiprocessors, Semaphores, and a Graph Model of Computation", Ph.D. dissertation, UCLA-ENG-7223, April 1972.
[16]
Gostelow, K., V. Cerf. and G. Estrin. "Proper Termination of Flow of Control in Programs Involving Concurrent Processes," Proceeding of the ACM, Vol. 11, Boston, August 1972.
[17]
Yavne, M. "Synthesis of Properly Terminating Graphs," Computer Science Department, University of California, Los Angeles, Ca. UCLA-ENG-7434, May 1974.
[18]
Gardner, R. I. "A Methodology for Digital System Design Based on Structural and Functional Modeling", Technical Report, UCLA-ENG-7488, January 1975.
[19]
Potash, H., A. Tyrrill, D. Allen. S. Joseph and G. Estin, "DCDS Digital Simulating System," AFIPS Conference Proceedings. 1969 Fall Joint Computer Conference, Vol. 35, pp. 707-720.
[20]
Rose, C. W., F. T. Bradshaw, and S. W. Katzke, "The LOGOS Representation System," Proceedings Sixth annual IEEE Computer Conference (CompCon 72), San Fransisco, September 1972, pp. 187-190.
[21]
Ruggiero, W. "A distributed data and control driven machine: programming and architecture", Ph.D. dissertation, Computer Science Department, University of California, Los Angeles, CA, 1978.
[22]
VanMierop, D. "Design and Verification of Distributed Interacting Processes," Ph.D. dissertation, UCLA-ENG-7920, March 1979.
[23]
Ruggiero, W. et.al. "Analysis of Data Flow Models Using the SARA Graph Model of Behavior," AFIPS Conference Proceedings, National Computer Conference, June 1979.
[24]
Razouk, R., and G. Estrin, "The Graph Model of Behavior, Simulator," Proceedings of Symposium on Design Automation and Microprocessors, Palo Alto, CA, February 1977.
[25]
Razouk, R. "GMB Simulator System Reference Manual", Computer Science Department, University of California, Los Angeles, CA, January 1977.
[26]
Estrin, G., D. Hopkins, B. Coggan and S.D. Crocker, "SNUPER COMPUTER, Instrumentation Automation," AFIPS Conference Proceedings, Vol. 30, pp. 645-656, Spring Joint Computer Conference, April 1967.
[27]
Estrin, G., R.R. Muntz and R. C. Uzgalis, "Modeling, Measurement and Computer Power," AFIPS Conference Proceedings, Vol. 40, pp. 725-738, Spring Joint Computer Conference, 1972.
[28]
Proceedings of the Software Quality and Assurance Workshop, ACM Special Interest Group on Measurement and Evaluation, Vol. 7, No. 3 and 4, November 1978.
[29]
Clarke, L. A. "A system to generate test data and symbolically execute programs," IEEE Transactions on Software Engineering, Vol SE-2, pp. 215-228, Sept. 1976.
[30]
Howden, W. E. "Reliability of the path analysis testing strategy," IEEE Transactions on Software Engineering, Vol SE-2, pp.208-215, Sept. 1976.
[31]
Ramamoorthy, C.V., S.F. Ho, and W. T. Chen, "On the Automated Generation of Program Test Data," IEEE Transactions on Software Engineering, Vol SE-2, December 1976.
[32]
Gabow, H. N., S. N. Maheshwari and L. J. Osterweil, "On two Problems in the Generation of Program Test Paths," IEEE Transactions on Software Engineering, Vol. SE-2, pp. 227-231, Sept. 1976.
[33]
Howden, W. E. "Symbolic Testing and the Dissect Symbolic Evaluation System," IEEE Transactions on Software Engineering, Vol. SE-3, pp. 266-278, July 1977.
[34]
Lundstrom, S. "Adaptive Random Data Generation for computer softare testing," AFIPS Conference Proceedings, National Computer Conference, pp.505-512, 1978.
[35]
Drobman, J. "A Model-Based Design System and Methodology for Composition of Microprocessor-Based Digital Systems", Dissertation Prospectus, May 1977.
[36]
Cooley, J. W. and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier Series," Mathematics of Computation, Vol. 19, pp. 297-301, April 1965.
[37]
Cochran, W. T., et. al., "What is the Fast Fourier Transform," Proceedings of the IEEE, Vol. 55, No. 10. pp. 1664-1674, October 1967.
[38]
Bergland, G. D., "FFT Hardware Implementations - A Survey," IEEE Transactions on Audio Electroacoustics, Vol. AV-17, No. 2, pp. 104-108, June 1969.
[39]
Allen, J., "Computer Architecture for Signal Processing," Proceedings of IEEE, Vol. 63, No. 4, pp. 624-633, April 1975.
[40]
Campos, I., and G. Estrin, "SARA aided design of software for concurrent systems", AFIPS Conference Proceedings, National Computer Conference, pp. 325-336, 1978.
[41]
Fenchel, R. S., and R.R. Razouk, "ULCA SARA (System ARchitects' Apprentice) Demonstration," Computer Science Department, University of California, Los Angeles, June 1979.
[42]
Macnaghten, A.M. and C.A.R. Hoare, "Fast Fourier Transform Free From Tears," The Computer Journal, Vol. 20, No. 1. pp. 78&ndash.83, February 1977.
[43]
Noe, J. D., "A Petri Net Description of the CDC 6400," Proceedings, ACM Workshop on System Performance Evaluation, Harvard University, pp. 362-378. 1971.
[44]
Noe J. D. and G. J. Nutt, "Validation of a Trace-driven CDC 6400 Simulation," AFIPS Conference Proceeding, Spring Joint Computer conference, Vol. 40, pp. 749-757, 1972.
Index Terms
- Evaluation methods in SARA—the graph model simulator
Recommendations
Evaluation methods in SARA—the graph model simulator
SIGMETRICS '79: Proceedings of the 1979 ACM SIGMETRICS conference on Simulation, measurement and modeling of computer systemsThe supported methodology evolving in the SARA (System ARchitects' Apprentice) system creates a design frame-work on which increasingly powerful analytical tools are to be grafted. Control flow analyses and program verification tools have shown promise. ...
Evaluation methods in SARA—the graph model simulator
The supported methodology evolving in the SARA (System ARchitects' Apprentice) system creates a design frame-work on which increasingly powerful analytical tools are to be grafted. Control flow analyses and program verification tools have shown promise. ...
Model-based test prioritization heuristic methods and their evaluation
A-MOST '07: Proceedings of the 3rd international workshop on Advances in model-based testingDuring regression testing, a modified system needs to be retested using the existing test suite. Since test suites may be very large, developers are interested in detecting faults in the system as early as possible. Test prioritization orders test cases ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1979 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 August 1979
Published in SIGMETRICS Volume 8, Issue 3
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations10Total Citations
- 310Total Downloads
- Downloads (Last 12 months)44
- Downloads (Last 6 weeks)5
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in