This disclosure relates to a network of reduction processors for the evaluation of one or more functions which are stored in memory in the form of a series of nodes of a treelike graph where the nodes implement a variable-free applicative language. The respective function operators are reduced through a progressive series of transformations or substitutions until a result is obtained. During the reduction process, the processor transfers nodes to and from memory and performs various operations as required on those nodes. The processor can also create new nodes in memory and delete unused ones.
Programs having multiple procedures are analyzed by creating a syst This invention was made with U.S. Government support awarded by the National Science Foundation (NSF), Grant #DCR-8603356 and PYI Award #DCR-8552602. The U.S. Government has certain rights in this invention.
A data processing system is described in which the workload is divided into packets. A plurality of processors access the packets and process them by rewriting them according to predetermined rules. Packets can be of a number of different types, including XAPP and PAPP. An XAPP packet contains a function and one or more arguments in evaluated form, so that the function can be immediately applied to the arguements. A PAPP packet is similar except that its arguments may not be in evaluated form. Processing of an active PAPP packet consists of activating other packets which evaluate the arguments of the PAPP packet, and converting the PAPP to a suspended XAPP packet, awaiting return information from those other packets. The use of different packet types allows greater efficiency, by eliminating redundant actions in processing of the packets.
A method and apparatus for managing a block oriented memory of the type in which each memory block has an associated reference count representing the number of pointers to it from other memory blocks and itself. Efficient and cost-effective implementation of reference counting alleviates the need for frequent garbage collection, which is an expensive operation. The apparatus includes a hash table into which the virtual addresses of blocks of memory which equal zero are maintained. When the reference count of a block increases from zero, its virtual address is removed from the table. When the reference count of a block decreases to zero, its virtual address is inserted into the table. When the table is full, a reconciliation operation is performed to identify those addresses which are contained in a set of binding registers associated with the CPU, and any address not contained in the binding registers are evacuated into a garbage buffer for subsequent garbage collection operations. The apparatus can be implemented by a cache augmented by the hash table, providing a back-up store for the cache.
A method and a device to perform arithmetic, arithmetical, logical and related operations on numerical value elements is characterized by providing an input list including the numerical value elements to be processes, and instruction information on a predetermined number of inputs/output buses. The operation on the numerical value elements on the input list is directly controlled and performed using the instruction information. Various computing circuits adapted to perform a specific operation on the numerical value representations are connected on the input buses, thereby providing the results of their computations in parallel. The calculation in the arithmetic logical unit is performed by rewriting the elements in the input list. The result is presented as an output list. The result is then recycled, if needed, to the input list until an eventual result is obtained, each cycle of a multi-cycle operation being influenced only by the output of the result of the next preceding cycle presented on the output bus. The output list then becomes, through this recycling operation, the input list to be further processed.
A method and apparatus for performing storage and retrieval in an information storage system is disclosed which uses the hashing technique. In order to prevent contamination of the storage medium by deleted records, a hybrid hashing technique is used which uses a fast, contaminating deletion of records during times of heavy load on the system, but uses a slow, non-contaminating deletion when the load on the system is not as heavy. The slow, non-contaminating deletion automatically removes previously generated contamination in the vicinity of the slow, non-contaminating deletion, thereby automatically decontaminating the storage space. Because no long term contamination can build up in the present system, it is useful for large data bases which are heavily used and which require the fast access provided by hashing.
