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

article

Free access

Fast Prolog with an extended general purpose architecture

Authors:

Bruce K. Holmer,

Michael Carlton,

William R. Bush,

Alvin M. Despain,

Joan M. Pendleton,

Tep DobryAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 18, Issue 2SI

Pages 282 - 291

https://doi.org/10.1145/325096.325154

Published: 01 May 1990 Publication History

Abstract

Most Prolog machines have been based on specialized architectures. Our goal is to start with a general purpose architecture and determine a minimal set of extensions for high performance Prolog execution. We have developed both the architecture and optimizing compiler simultaneously, drawing on results of previous implementations. We find that most Prolog specific operations can be done satisfactorily in software; however, there is a crucial set of features that the architecture must support to achieve the best Prolog performance. The emphasis of this paper is on our architecture and instruction set. The costs and benefits of the special architectural features and instructions are analyzed. Simulated performance results are presented and indicate a peak compiled Prolog performance of 3.68 million logical inferences per second.

References

[1]

L. Sterling and E. Shapiro, The Art of Prolog, MlT Press. 1986.

[2]

M. Yokota, A. Yamamoto, K. Taki. H. Nishikawa, and S. Uchida. The Design and Implementation of a Personal Sequential Inference Machine: PSI. New Generation Computing, pp. 125 - 144,1983.

[3]

T. P. Dobry, A High Performance Architecture for Prolog, Kluwer Academic Publishers, 1990.

Digital Library

[4]

V. P. SrIni. J. V. Tam, T. M. Nguyen, Y. N. Patt, A. M. Despain, M. MO and D. Ellsworth. A CMOS chip for Pmlog, Proceedings of the Inrernational Conference on Computer Design, pp. 605 - 610, October 1987.

[5]

H. Nakashima and K. Nakajima, Hardware Architecture of the Sequential Inference Machine: PSI-II, 1987 Symposium on Logic Programming, pp. 104 - 113, August 1987.

[6]

H. Benker, J. M. Beacco, S. Bescos, M. Dorochevsky, Th. Jeffre, A. Pohimann, J. Noye, B. Poterie, A. Sexton, J. C. Syre, 0. ThIbault, and G. Watzlawik, KCM: A Knowledge Crunching Machine, 16th Inrernational Symposium on Computer Architecture, pp. 186 - 194, May 1989.

Digital Library

[7]

D. H. D. Warren, An Abstract Prolog Instruction Set,' TR 309, SRI International, October 1983.

[8]

J. W. Mills, A High-Performance LOW RISC Machine for Logic Programming, Journal of Logic Programming, vol. 6. no. 1 & 2, pp. 179 - 212, January/March 1989.

Digital Library

[9]

K. Seo and T. Yokota. Design and Fabrication of Pegasus Prolog Processor, in VLSI 89, North-Holland.

[10]

A. Harsat and R. Ginosar, CARMEL-2: A Second Generation VLSI Architecture for Flat Concurrent Pmlog. Proceedings of the International Conference on Fifth Generation Computer Sjxtems, pp. 962 - 969, November 1988.

[11]

J. W. Mills, LIBRA: A High-Performance Balanced Computer Architecture for Prolog, Ph.D. Thesis, Arizona State University, December 1988.

Digital Library

[12]

G. Ratin, The 801 Minicomputer, Symposium on Architectural Support for Programming Languages and Operating Systems (ASPWS I), pp. 39 - 47. March 1982.

Digital Library

[13]

J. L. Hennessy. N. P. Jouppi, S. Przybylski, C. Rowen, and T. Gross, Design of a High Performance VLSI Processor, Third CalTech Conference on Very Large Scale Integration, pp. 33 - 54.1983.

[14]

M. G. H. Katevenis, Reduced Insrruction Ser Computer Architectures for VLSI, MIT Press. 1985.

Digital Library

[15]

P. Steenkiste and J. Hennessy, Tags and Type Checking in LISP: Hardware and Software Approaches, Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPWS II), pp. 50 - 59, October 1987.

Digital Library

[16]

A. Chang and M. F. Mergen. 801 Storage: Architecture and Programming, ACM Transactions on Computer Systems, vol. 6, no. 1. pp. 28 - 50, February 1988.

Digital Library

[17]

R. Carlson, The Bottom-Up Design of a Prolog Architecture, Report No. UCB/CSD 89/536, University of California, Berkeley, May 1989.

Digital Library

[18]

P. Van Roy, B. Demoen, and Y. D. Wiiems, Improving the Execution Speed of Compiled Prolog with Modes, Clause Selection, and Determinism, in TAPSOFT '87. Lecture Notes in Computer Science, 250, pp. 111 - 125, March 1987.

Digital Library

[19]

M. Carlton, B. Sane. J. Pendleton, B. Holmer, and A. Despain, Cache Innovations in the BAM Microprocesscr, November 1989.

[20]

J. Pendleton. S. Kong, E. Brown, F. Dunlap, C. Marina, D. Ungar, D. Patterson, and D. Hodges, A 32-bit Microprocessor for Smalltalk, IEEE Journal of Solid State Circuiis, vol. SC- 21, no. 5, pp. 741- 749, October 1986.

[21]

P. Van Roy, An Intermediate Language to Support Prolog's Unification, in Proceedings of the North American Conference on Logic Programming, ed. Lusk & Overbeek, pp. 1148 - 1164, MIT Press. October 1989.

[22]

J. Beer, The Occur-Check Problem Revisited, Journal of Logic Programming, vol. 5, no. 3, pp. 243 - 261, September 1988.

Digital Library

[23]

P. Van Roy, Can Logic Programming Execute as Fast as Imperative Pmgramming?, ph. D. Thesis (in preparation).

Digital Library

[24]

S. K. Debray and D. S. Warren, Automatic Mode Inference for Prolog Programs. 1986 Symposium on Logic Programming, pp. 78 - 88, September 1986.

[25]

D. M. Ungar, The Design and Evaluation of a High Performance Smalltalk System, MtT Press, 1987.

Digital Library

[26]

B. Sano, Performance vs. Cost of the BAM, December 1989.

[27]

G. Borriello, A. R. Cherenson, P. B. Danzig, and M. N. Nelson, RlSCs vs. ClSCs for Prolog: A Case Study, Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS II), pp. 136 - 145, October 1987.

Digital Library

[28]

R. Haygood, A Prolog Benchmark Suite for Aquarius, Report No. UCB/CSD 89/509, University of California, Berkeley, April 1989.

Digital Library

Cited By

Costa ADe Gloria AFaraboschi POlivieri MWolfe AMangione-Smith W(1993)An analysis of dynamic scheduling techniques for symbolic applicationsProceedings of the 26th annual international symposium on Microarchitecture10.5555/255235.255284(185-191)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.5555/255235.255284
Shimada KKoike HTanaka H(1993)UNIRED II: The high performance inference processor for the parallel inference machine PIE64New Generation Computing10.1007/BF0303717811:3-4(251-269)Online publication date: Sep-1993
https://doi.org/10.1007/BF03037178
Noyé J(1992)The KCM system: Speeding-up logic programming through hardware supportLogic Programming and Automated Reasoning10.1007/BFb0013099(496-498)Online publication date: 1992
https://doi.org/10.1007/BFb0013099
Show More Cited By

Index Terms

Fast Prolog with an extended general purpose architecture
1. Computer systems organization
2. Hardware

Recommendations

Fast Prolog with an extended general purpose architecture
ISCA '90: Proceedings of the 17th annual international symposium on Computer Architecture

Most Prolog machines have been based on specialized architectures. Our goal is to start with a general purpose architecture and determine a minimal set of extensions for high performance Prolog execution. We have developed both the architecture and ...
General purpose languages should be metalanguages
PEPM '10: Proceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation

In his paper, The Next 700 Programming Languages, the late Landin writes that "most programming languages are partly a way of expressing things in terms of other things and partly a basic set of given things." Landin tries to separate the general ...
A high performance architecture for prolog

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 18, Issue 2SI

Special Issue: Proceedings of the 17th annual international symposium on Computer Architecture

June 1990

356 pages

ISSN:0163-5964

DOI:10.1145/325096

Issue’s Table of Contents

ISCA '90: Proceedings of the 17th annual international symposium on Computer Architecture
May 1990
378 pages
ISBN:0897913663
DOI:10.1145/325164
Chairmen:
Jean-Loup Baer,
Larry Snyder,
James Goodman

Copyright © 1990 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Published in SIGARCH Volume 18, Issue 2SI

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
522
Total Downloads

Downloads (Last 12 months)99
Downloads (Last 6 weeks)21

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Costa ADe Gloria AFaraboschi POlivieri MWolfe AMangione-Smith W(1993)An analysis of dynamic scheduling techniques for symbolic applicationsProceedings of the 26th annual international symposium on Microarchitecture10.5555/255235.255284(185-191)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.5555/255235.255284
Shimada KKoike HTanaka H(1993)UNIRED II: The high performance inference processor for the parallel inference machine PIE64New Generation Computing10.1007/BF0303717811:3-4(251-269)Online publication date: Sep-1993
https://doi.org/10.1007/BF03037178
Noyé J(1992)The KCM system: Speeding-up logic programming through hardware supportLogic Programming and Automated Reasoning10.1007/BFb0013099(496-498)Online publication date: 1992
https://doi.org/10.1007/BFb0013099
Dorochevsky MNoyé JThibault O(1991)Has dedicated hardware for Prolog a future ?Processing Declarative Knowledge10.1007/BFb0013518(17-31)Online publication date: 1991
https://doi.org/10.1007/BFb0013518
Getzinger T(2005)The costs and benefits of abstract interpretation-driven Prolog optimizationStatic Analysis10.1007/3-540-58485-4_30(1-25)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58485-4_30
Lopes RCastro LCosta VMueller FChilimbi TDing C(2002)From simulation to practiceProceedings of the 2002 workshop on Memory system performance10.1145/773146.773045(56-64)Online publication date: 16-Jun-2002
https://dl.acm.org/doi/10.1145/773146.773045
Lopes RCastro LCosta V(2002)From simulation to practiceACM SIGPLAN Notices10.1145/773039.77304538:2 supplement(56-64)Online publication date: 16-Jun-2002
https://dl.acm.org/doi/10.1145/773039.773045
Ducassé MNoyé J(2000)Tracing Prolog programs by source instrumentation is efficient enoughThe Journal of Logic Programming10.1016/S0743-1066(99)00061-843:2(157-172)Online publication date: May-2000
https://doi.org/10.1016/S0743-1066(99)00061-8
Holmer BMermet J(1994)A tool for processor instruction set designProceedings of the conference on European design automation10.5555/198174.198232(150-155)Online publication date: 23-Sep-1994
https://dl.acm.org/doi/10.5555/198174.198232
Huang IDespain ALorenzetti M(1994)Synthesis of instruction sets for pipelined microprocessorsProceedings of the 31st annual Design Automation Conference10.1145/196244.196250(5-11)Online publication date: 6-Jun-1994
https://dl.acm.org/doi/10.1145/196244.196250
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Issue’s Table of Contents