Parallel processing of frame-based networks.

This Project involved the development of a simulation of a rectangular array of Processing Elements (PE's), with a dedicated frame based knowledge representation language. The main objective of the Project was to analyse and quantify the gain in speed of execution in a parallel environment, as compared with serial processing.The computational model of the language consisted of two main components: the knowledge base, and the replicated/distributed inference engine. The knowledge base was assumed to represent real world knowledge, in that it consisted of a large volume of information, which was divided into domains and hierarchies.When a query is made, appropriate portions of the knowledge base are mapped to the array of PEs on a one-to-one basis (one frame/PE), where each PE is capable of performing any relevant operations itself.The execution of a query is based on the propagation of messages across the array of PEs, where each message is contained in a data packet. Each packet holds the query-frame, created by interacting with the user, together with other relevant information used for knowledge manipulation.The main inference mechanism in the system is based on the parallel inheritance of properties, where each data packet carries inherited data from higher level to lower level frames, within the appropriate hierarchies. As each packet arrives at a PE which contains a relevant frame, a series of matching, and consequently, inheritance operations are performed.An algorithm, superimposed at the highest level of the system, computes time delays in relation to the overall architecture of the machine. There are two main operations for which time penalties are calculated : frame-processing and communication. The frame processing involves matching and inheritance operations, and the communication operation involves message passing and data packet traversal.During each execution cycle, the time penalties for both processing and communication are computed and stored in a file. These files are then used by a graphics package which transforms the numerical data into a set of graphs. These graphs are utilised in the analysis of the behaviour of the simulation. The analysis of the test-runs, and of their associated graphs, has yielded positive and encouraging results, demonstrating that there can be an average of a 35 fold gain in the speed of execution.