A CM-5 supercomputer - one of PARKA's platforms
A CM-5 supercomputer - one of PARKA's platforms
PARKA is a frame-based knowledge representation system which uses the massive parallelism of the Connection Machine (CM) to perform certain inferences extremely rapidly. PARKA performs property inheritance, set-theoretic inferences, and inferences on partonomic relations. To date, the system has been implemented both on the CM-2 and CM-5 massively parallel supercomputers made by Thinking Machines Corporation. The Connection Machine supports a SIMD (Single Instruction stream, Multiple Data stream) programming model in which each processor (the CM-2 has up to 65536 of them) either performs the same instruction or sits idle.PARKA computes property inheritance inferences using a version of Touretzky's inferential distance ordering algorithm (IDO). Examples of such inferences are "Where are all the tanks?" or "How many trucks are yellow?". This algorithm uses the SIMD model of the CM-2 to spread markers across the semantic network. The propagation of these markers is controlled so that property values are passed to the proper frames along the is-a hierarchy. Inheritance inferences can be performed in O(d), where d is the depth of the semantic network along the is-a relation (assuming the number of processors exceeds the number of frames, so d is approximately equal to log n).
Queries for the values of individual properties can be assembled to provide a ``recognition'' capability. These queries are useful for identifying frames which are similar to a target description. Such queries have the form "P1(x,c1) & P2(x,C2) & ... & Pm(x,Cm)", where Pi is a slot relating frame x with value Ci. PARKA can compute these queries in time O(d+m) by "pipelining" (a technique where as many as d property inheritance queries can be processed simultaneously). Most serial systems take time O(mb^d) for such queries (b is the average downward branching factor of the semantic network). PARKA has been tested on randomly constructed semantic networks with as many as 256,000 frames. On Lenat's Cyc knowledge base of about 32,000 frames and 120,000 links, PARKA was able to perform complex recognition queries (up to 22 properties) on this knowledge base in less than one second.