The architecture of a pipelined microprocessor for logic programming languages is presented. The microprocessor, called PU (processing unit), is also used as a key component of AI workstations. PU has the capability to execute two different logic programming languages, KL1 for PIM/m and ESP for the AI workstation. The microprocessor has very high performance, 833 KLIPS in KL1 append and 1282 KLIPS in ESP, owing to the pipelined data typing and dereference. For efficient implementation of both languages, data typing and dereference are important. For these operations, PU has mechanisms to manipulate tagged data. The hardware architecture of PU is described, focusing on its data typing and dereference mechanisms.>

We evaluated a Prolog machine PSI (Personal Sequential Inference machine) for the purpose of improving and redesigning it. In this evaluation, we measured the execution speed and the dynamic characteristics of cache memory, register file, and branching hardware introduced for high-speed execution of Prolog programs.Execution speed of the PSI firmware interpreter was found to be comparable to that of the DEC-10 Prolog compiled code on the DEC-2060. It was also found that PSI was faster than DEC for executing programs containing much unification and backtracking that require runtime processing.With the cache memory, the hit ratio for application programs was found higher than 96%; this demonstrates that the Prolog execution has much memory access locality. The memory access frequency and the appearance ratio between Read and Write command were also investigated.Concerning the register file, use rate of each dedicated access mode was measured and effect of each mode was discussed. In the branching function we confirmed a high appearance rate of conditional branches and multi-way branches based on tag values.

Suppose that n independent tasks are to be scheduled without preemption on an unlimited number of parallel machines of two types: inexpensive slow machines and expensive fast machines. Each task requires a given processing time on a slow machine or a given smaller processing time on a fast machine. We make two different feasibility assumptions: (a) each task has a specified processing interval, the length of which is equal to the processing time on a slow machine; (b) each task has a specified starting time. For either problem type, we wish to find a feasible schedule of minimum total machine cost. It is shown that both problems are NP-hard in the strong sense. These results are complemented by polynomial algorithms for some special cases.