Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T21:08:57.245Z Has data issue: false hasContentIssue false
  • English
  • Français

Parallelism in knowledge-based machines

Published online by Cambridge University Press:  07 July 2009

Apostolos N. Refenes
Apostolos N. Refenes
Affiliation:
Department of Computer Science, University College London, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

The application area of knowledge-based expert systems is currently providing the main stimulus for developing powerful, parallel computer architectures. Languages for programming knowledge-based applications divide into four broad classes: Functional languages (e.g. LISP), Logic languages (e.g. PROLOG), Rule-Based languages (e.g. OPS5), and, what we refer to as self-organizing networks (e.g. BOLTZMANN machines).

Despite their many differences, a common problem for all language classes and their supporting machine architectures is parallelism: how to de-compose a single computation into a number of parallel tasks that can be distributed across an ensemble of processors. The aim of this paper is to review the four types of language for programming knowledge-based expert systems, and their supporting parallel machine architectures. In doing so we analyze the concepts and relationships that exist between the programming languages and their parallel machine architectures in terms of their strengths and limitations for exploiting parallelization.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 4 , Issue 1 , March 1989 , pp. 53 - 71
Copyright
Copyright © Cambridge University Press 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abenson, H and Sussman, GJ, 1984. Structure and Interpretation of Computer Programs, Massachusetts: The MIT PressGoogle Scholar
Church, A, 1941. The Calculi of Lambda-Conversion, New Jersey: Princeton University PressGoogle Scholar
Clarke, TIW et al. , 1980. “SKIM—The S, K, I Reduction Machine”, Proc. 1980 LISP Conf.StanfordCrossRefGoogle Scholar
Darlington, J and Reeve, M, 1983. “ALICE and the Parallel Evaluation of Logic Programs”, 10th Int. Symp. on Computer ArchitectureGoogle Scholar
Keller, RM et al. , 1978. “A loosely coupled applicative multiprocessing system”, Proc. Nat. Computer Conf.,AFIPS Press, pp 861–870Google Scholar
Keller, RM et al. , 1984. “REDIFLOW Multiprocessing”, Proc. IEEE COMPCON Spring 84, pp 410–414Google Scholar
Kluge, WE, 1979. “The architecture of a reduction language machine hardware model”, Tech. Rep. ISF-Rep. 79.03, Gesellschaft fur Mathematik und Datenverarbeitung MBH Bonn.Google Scholar
Kluge, W and Schmittgen, C, 1987. “Reduction Languages and Reduction Systems”, In: Future Parallel Computers, Lecture Note in Computer Science, vol. 272, Treleaven, P and Vanneschi, M, eds, pp 153–182CrossRefGoogle Scholar
Moon, D, 1985. “Architecture of the Symbolics 3600”, Proc. Twelth. Int. Symp. on Computer Architecture, pp 76–83CrossRefGoogle Scholar
Peyton-Jones, S et al. , 1985. “GRIP—a Parallel Graph Reduction Machine”, University College London, Dept. of Computer Science, Technical Report 1665Google Scholar
Richards, H, 1985. “An Overview of the Burroughs NORMA”, Internal Report Burroughs Corp, Austin Research CentreGoogle Scholar
Rieger, C et al. , 1981. “ZMOB: A new computing engine for AI”, Proc. 7th IJCAI-81, Vancouver, pp 955–960Google Scholar
Bibel, W and Buchberger, B, 1983. “Towards a Connection Machine for Logical Inference”, Proc. Int. Sym. on Fifth Generation and Super Computers, Rotterdam, December 11–13, 1984, Future Generations Computer Systems 1 (3) pp 177–188CrossRefGoogle Scholar
Clocksin, W and Mellish, C, 1981. Programming in PROLOG, New York: Springer-Verlag.Google Scholar
van Emden, MH and Kowalski, RA, 1976. “The Semantics of Predicate Calculus as a Programming Language”, JACM 23 (4) pp 733–742CrossRefGoogle Scholar
Gonzales-Rubio, R and Rohmer, J, 1985. “From databases to Artificial Intelligence: A Hardware Point of view”, Les Arcs, France: AIS, NATOGoogle Scholar
Kowalski, R, 1979. Logic for Problem Solving, Amsterdam: North-HollandGoogle Scholar
Moto-oka, T. et al. , 1984. “The Architecture of a Parallel Engine PIE”, Proc. Int. Con. on Fifth Generation Computer Systems, Tokyo, pp 479–488Google Scholar
Onai, R et al. , 1984. “An Approach to a Parallel Inference Machine Based on Control-Driven and Data-Driven Mechanisms”, Tech. Rep. TR-042, ICOTGoogle Scholar
Sohma, Y et al. , 1985. “A New Parallel Inference Mechanism Based on Sequential Processing”, Proc. IFIP TC-10 Work. Conf. on Fifth Gen. Comp. Arch,UMIST ManchesterGoogle Scholar
Tick, E and Warren, DHD, 1984. “Towards a Pipelined Prolog-Processor”, Proc. 1984 Int. Sym. on Logic ProgrammingCrossRefGoogle Scholar
Uchida, S et al. , 1983. “Outline of a Personal Sequential Inference Machine: PSI”, New Generation Computing 1 (1)CrossRefGoogle Scholar
Warren, DHD, 1977. “IMPLEMENTING PROLOG—compiling predicate logic programs”, Dept. of Artificial Intelligence, Univ. of Edinburgh, Research Report No. 39Google Scholar
BBN, 1985. “BUTTERFLY Parallel Processor Overview”, Tech. Rep. Bolt Beranek and Newman Labs. Inc., Cambridge, MAGoogle Scholar
Brownston, L et al. , 1985. Programming Expert Systems in OPS5, New York: Addison-WesleyGoogle Scholar
Davis, AL and Robison, SV, 1985. “The Architecture of the FAIM-1 Symbolic Multiprocessing System”, Proc. Int. Joint Conf. on Artificial Intelligence, pp 32–38Google Scholar
Forgy, CL, 1981. “The OPS5 user's Manual”, Tech. Report CMU-CS-81–135, Computer Science Department, Carnegie-Mellon UniversityGoogle Scholar
Forgy, CL, 1982. “Rete: A Fast Algorithm for the Many Pattern/Many Object Match Problem”, Artificial Intelligence 19 pp. 17–37CrossRefGoogle Scholar
Forgy, C et al. , 1984. “Initial Assessment of Architectures for Production Systems”, Proc. Nat. Conf. for Artificial Intelligence AAAI '84, pp 116–120Google Scholar
Hayes-Roth, F et al. , 1983. Building Expert Systems, New York: Addison-WesleyGoogle Scholar
Hillyer, BK and Shaw, DE, 1983. “Rapid Execution of AI Production Systems on the NON-VON Supercomputer”, Tech. Rep., Dept. of Comp. Sc., Columbia Univ., New YorkGoogle Scholar
Stolfo, SJ and Shaw, DE, 1982. “DADO: A Tree-Structured Machine Architecture for Production Systems”, Proc. Nat. Conf. on AI AAAI-82, pp 242–246Google Scholar
Fahlman, S, 1980. “Design sketch for a million-element NETL machine”, Proc. AAAI–80, Stanford, pp 249–251Google Scholar
Fahlman, SE et al. , 1983. “Massively Parallel Architectures for AI: NETL, Thistle and Boltzmann Machines”, Proc. Nat. Conf. of AI, AAAI-83, pp 109–113Google Scholar
Feldman, JA, 1985. “CONNECTIONS”, Byte 10 (4) pp 277–284Google Scholar
Hillis, WD, 1984. “The Connection Machine: A computer architecture based on cellular automata”, Cellular Automata, Farmer, et al., ed, pp 213–229CrossRefGoogle Scholar
Ohbuchi, R, 1985. “Overview of Parallel Processing Research in Japan”, IBM Japan Science Institute, JSI Research Report TR87–0003Google Scholar
Treleaven, PC et al. , 1982. “Data Driven and Demand Driven Computer Architecture”, ACM Computing Surveys 14 (1) pp 93–143CrossRefGoogle Scholar
Barren, I et al. , 1983. “Transputer does 5 or more MIPS even when not used in parallel”, Electronics 56 (23) pp 109–115Google Scholar
May, D, Shepard, R and Keane, C, 1987. “Communicating sequential processes: Transputer and Occam”, In: Treleaven, PC and Vaneschi, M, eds, Future Parallel Computers, New York: Springier VerlagGoogle Scholar