An instruction fetch unit for a graph reduction machine
Pages 82 - 91
Abstract
The G-machine provides architecture support for the evaluation of functional programming languages by graph reduction. This paper describes an instruction fetch unit for such an architecture that provides a high throughput of instructions, low latency and adequate elasticity in the instruction pipeline. This performance is achieved by a hybrid instruction set and a decoupled RISC architecture. The hybrid instruction set consists of complex instructions that reflect the abstract architecture and simple instructions that reflect the hardware implementation. The instruction fetch unit performs translation from complex instruction to a sequence of simple instructions which can be executed rapidly. A suitable mix of techniques, including cache, buffers and the translation scheme, provide the memory bandwidth required to feed a RISC execution unit. The simulation results identify the performance gains, maximum throughput and minimum latency achieved by various techniques. Results achieved here are in general applicable to von Neumann architectures.
References
[1]
Anderson, D. W., Sparacio, F. J. and Tomasulo, R. M., "The Model 91: Machine Philosophy and Instruction Handling," IBM Journal of Research and Development, vol. 11(January 1967), .
[2]
Augustsson, L., "A Compiler for Lazy ML," Prec. ACM Syrup. on LISP and Functional Programming, Austin, Texas, August 1984, pp. 218-227.
[3]
Backus, J., "Can programming be liberated from yon Neumann Style A functional style and its algebra of programs," Communications of the A CM, vol. 21, 8 (August 1978), pp. 613-641.
[4]
Bain, W. L., A Multi-tasking facility for C., April 1985.
[5]
Colwell, R. P., III, C. Y. H., Jensen, E. D., Sprunt, H. M. B. and Kollar, C. P., "Instruction Sets and Beyond: Computers, Complexity and Controversy," Computer, September 1985.
[6]
Edwards, D. B. G., Knowles, A. E. and Woods, J. V., "MU6-G: A new design to achieve mainframe performance from a mini-sized computer," SIGARCH Newsletter (ACM), vol. 8, 6 (June 1980), Prec. ACM SIGARCH Symp. on Computer Architecture.
[7]
Farahmand-nia, S., Kuo, S. L. and Rankin, L., Simulation of the G.machine Instruction Fetch and Translation Unit, Dept. of Computer Sc. & Eng., Oregon Graduate Center, May 1985.
[8]
Flynn, M. J., 'Tery High-Speed Computing Systems," Proceedings of the IEEE, vol. 54, 12 (December 1966), pp. 1901-1909.
[9]
Hailpern, B. T. and Hitson, B. L., "S-1 Architecture Manual," Teeh. report STAN-CS-79-715, Computer Systems Lab., Stanford University, 1979.
[10]
Hennessy, J. L., Jouppi, N., Baskett, F. and Gill, J., "MIPS: A VLSI Processor Architecture," Proc. CMU Conference on VLSI Systems and Computations, October 1981, pp. Computer Science Press.
[11]
Hsieh, J. T., Pleszkun, A. R. and Vernon, M. K., "Performance Evaluation of A Pipeline VLSI Architecture Using the Graph Model Behaviour (GMB)," Proceedings CHDL 85, August 1985.
[12]
Ibbett, R. N., The Architecture of High Performance Computers, (Macmillan Press 1982), 1982, pp. Springer Verlag.
[13]
Johnsson, T., The G-machine -- an abstract architecture for graph-reduction, Dept. of Computer Sciences, Chalmers Univ. of Technology, Gothenburg, 1983.
[14]
Johnsson, T., "Efficient compilation of lazy evaluation," Proc. of 1984 ACM SIGPLAN Notices Conf. on Compiler Constr, June, 1984.
[15]
Katevenis, M. G. H., "Reduced Instruction Set Computer Architecture for VLSI," Ph.D Thesis, Report No. UCB/Computer Science Department 83/141, EECS, University of California, Berkeley, October 1983.
[16]
Kieburtz, R. B., "G-machine Programmers Guide," Internal Document, Dept. of Computer Sc. & Eng., Oregon Graduate Center, August 1984.
[17]
Kieburtz, R. B., Private discussion., 1984.
[18]
Kieburtz, R. B., "Control of the Instruction Fetch Unit," Internal Document, Dept. of Computer Sc. & Eng., Oregon Graduate Center, April 1985.
[19]
Kieburtz, R. B., "The G-machine: a fast, graphreduction evaluator," Proe. of IFIP Conf. on Functional Prog. Lang. and Computer Arch., Nancy, 1985.
[20]
Kuo, S. L. and Sutton, R., "," Internal Report, December 1985.
[21]
Lampson, B. W., McDaniel, G. and Ornstein, S. M., "An Instruction Fetch Unit for a High-performance Personal Computer," IEEE Transactions on Computers, vol. C-33, 8 (August 1984), .
[22]
Lavington, S. H., "The Manchester Mark 1 and Atlas: A Historical Perspective," Communications of the ACM (ACM), vol. 21, 1 (January 1978), .
[23]
Lee, J. K. F. and Smith, A. J., "Branch Prediction Strategies and Branch Target Buffer Design," IEEE Computer Magazine, vol. 17, 1 (1984), .
[24]
Morris, D. and Ibbett, R. N., The MU5 Computer System, 1979, pp. Springer Vcrlag.
[25]
Patterson, D. A. and Sequin, C., "A VLSI RISC," Computer, vol. 15, 9 (September 1982), pp. 8-21.
[26]
Patterson, D. A., Garrison, P., Hill, M., Lioupis, D., Nyberg, C., Sippel, T. and Dyke, K. V., "Architecture of a VLSI Instruction Cache for a RISC," Proc. ACM SIGARCH Syrup. on Computer Architecture, June 1983.
[27]
Patterson, D., "Reduced Instruction Set Computers," Communications of the ACM, vol. 28, 1 (January 1985),.
[28]
Radin, G., "The 801 Minicomputer," Proc. SIGARCH/SIGPLAN Notices Symp. on Arch. Support for Prog. Languages and Operating Systems, 1982.
[29]
Sachs, H. and Hollingsworth, W., "A High Performance 846,000 Transistor UNIX Engine - The Fairchild Clipper," ICCD 85, October 1985, pp. 342-346.
[30]
Sarangi, A., "Simulation and Performance Evaluation of a Graph Reduction Machine Architecture," Masters Thesis, Oregon Graduate Center, 1984.
[31]
Smith, J. E., "A Study of Branch Prediction Strategies," Proc. ACM SIGARCH Syrup. on Computer Architecture, May 1981.
[32]
Smith, A. J., "Cache Evaluation and the Impact of Workload Choice," SIGARCIt Newsletter - l2th Annual Int. Symposium on Computer Architecture, vol. 13, 3 (June 1985), pp. 64-73.
[33]
Smith, J. E. and Goodman, J. R., "Instruction Cache Replacement Policies and Organisations," IEEE Transactions On Computers, vol. C-34, 3 (March 1985), .
[34]
Turner, D. A., "New implementation techniques for applicative languages," Software, Practice & Experience, vol. 9, 1 (1979), .
[35]
Wilkes, M. V., "Keeping Jump Instructions out of the Pipeline of a RISC like Computer," ACM SIGARCHNewsletter, vol. 11, 5 (1983), .
[36]
Woods, J. V., Knowles, A. E., Lomas, P. B. and Edwards, D. B. G., "The MU6-G Computer System," To appear in IEE CDT, 1986.
[37]
"A Simple Design May Pay Off Big For Hewlett- Packard," Electronics, March 3, 1986, pp. 39-44.
Index Terms
- An instruction fetch unit for a graph reduction machine
Recommendations
An instruction fetch unit for a graph reduction machine
Special Issue: Proceedings of the 13th annual international symposium on Computer architecture (ISCA '86)The G-machine provides architecture support for the evaluation of functional programming languages by graph reduction. This paper describes an instruction fetch unit for such an architecture that provides a high throughput of instructions, low latency ...
An Instruction Fetch Unit for a High-Performance Personal Computer
The instruction fetch unit (IFU) of the Dorado personal computer speeds up the emulation of instructions by prefetching, decoding, and preparing later instructions in parallel with the execution of earlier ones. It dispatches the machine's microcoded ...
Increasing the instruction fetch rate via block-structured instruction set architectures
MICRO 29: Proceedings of the 29th annual ACM/IEEE international symposium on MicroarchitectureTo exploit larger amounts of instruction level parallelism, processors are being built with wider issue widths and larger numbers of functional units. Instruction fetch rate must also be increased in order to effectively exploit the performance ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 May 1986
Check for updates
Qualifiers
- Article
Acceptance Rates
Overall Acceptance Rate 543 of 3,203 submissions, 17%
Upcoming Conference
ISCA '25
- Sponsor:
- sigarch
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 382Total Downloads
- Downloads (Last 12 months)63
- Downloads (Last 6 weeks)22
Reflects downloads up to 03 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in