Invocation architecture for generally concurrent process...

Details Invocation architecture for generally concurrent process... Invocation architecture for generally concurrent process...

1999-06-25

2001-12-04

Ellis, Richard L. (Department: 2183)

Electrical computers and digital processing systems: multicomput

Distributed data processing

C709S241000, C709S241000

Reexamination Certificate

active

06327607

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a multi-processor computer architecture, and more particularly to an invocation architecture for generally concurrent process resolution.
2. Description of the Related Art
A number of computer architectures supporting concurrent processing have been proposed.
In one kind of concurrent architecture, programs are compiled for a known, fixed configuration of processors and memory. These static systems use knowledge about the configuration of the system on which they are to be executed in order to compile their programs.
In other types of systems, a processor hierarchy designates one processor as a “master,” on which a run-time operating system or kernel makes decisions as to which of the processor will execute parts of a process. Here again, the concurrency is predetermined in terms of location of execution and the programs are compiled accordingly.
Each of these systems suffers from drawbacks. Fixed configuration systems are unable to adapt to variations in existing programs and hardware. For example, a typical system has a fixed number of processors which is a power of two and which can only be increased by filed numbers of processors. When a system is reconfigured, existing programs usually have to be re-compiled to take advantage of the new configurations. None of the existing systems is able to provide for generally concurrent process resolution which can exploit as much expressed concurrency as possible while using available resources in a flexible, automatic, optimal and distributed manner. Such a generally concurrent architecture is desirable.
SUMMARY OF THE INVENTION
Disclosed here is an invocation architecture for generally concurrent process resolution comprising a plurality of interconnected processors, some of the processors being homogeneous processors and others of the processors being special purpose processors. Each homogeneous processor is capable of invoking a connected processor to have the connected processor resolve processes. Each processor is capable of being invoked by a connected processor to resolve processes.
Program instructions defining potential processes and starting data are broadcast to all processors. The preferred programming language, referred to as the “Invocation Language” TM, is described in U.S. Pat. No. 5,355,496, which is incorporated here by reference. The Invocation Language TM expresses processes purely in terms of association relationships among places in the symbol strings used to express processes.
One processor, which may be any processor, initiates a process at a high level when it receives an “invocation,” which is a message, preferably of a prescribed form described below, naming the root processes. When the root process is susceptible of being divided into concurrently executable sub-processes, the initiating processor sends invocations for the sub-processes to neighbor processors.
Sub-processes are resolved in the same manner as the root processes. Whenever a sub-process is susceptible of being divided into concurrently executable sub-processes, the processor sends invocations to neighbor processors. Sub-processes further divide into lower-level processes, and unfold throughout the network as higher-level processes spawn lower-level invocations to neighbor processors.
In their preferred form, invocations include pointers to address of data, pointers to address where results should be returned, and address where program instructions defining the process (or sub-process) can be found. Pointers in an invocation contain all the information necessary for the process or sub-process to go forward, and the very creation of an invocation causes the process to go forward. Control over execution of the process is determined by when and where invocations are formed, which is accomplished in a general and distributed manner.
The invocation architecture provides an environment for the creation and resolution of invocations. In preferred embodiments of the present invention, each of the plurality of processors comprises an activity agent (for example, CPU), an ALU and a plurality of special purpose memories local to the activity agent. One special purpose memory, a result data cache, is used to transfer process results from the activity agent to a result memory, which is shared by all processors. Another special purpose memory, a possibility expression and input data memory, receives and stores data and process definitions (executable instructions), through a broadcast bus. Other memories include an input buffer and an output buffer, which connect to adjacent processors and are used to exchange invocations.
In some embodiments, the invocation architecture further includes a plurality of input/output controllers. The input/output controllers may include a disk controller, a tape controller, a printer controller, and a communications controller. A first global bus connects each of the homogeneous processors to each of the plurality of input/output controllers.
In some embodiments, the invocation architecture further includes a plurality of special purpose processors. The special purpose processors may include a vector processor, a string processor, a logic processor, and a database processor. A second global bus connects each of the homogeneous processors to each of the special purpose processors.
The invocation architecture described herein is capable of resolving concurrent processes by exploiting as much of the expressed concurrency as possible. The invocation architecture of the present invention is indefinitely and benignly evolvable. That is, a new general purpose processor may be added to the system, and processes will self-distribute to the newly added processor. All that is needed is that neighbors of the new processor-be notified of the existence of the new processor as a neighbor. Each new processor is a neighbor to some other processors and can be invoked by its neighboring processors.


REFERENCES:
patent: 4107773 (1978-08-01), Gilbreath et al.
patent: 4395758 (1983-07-01), Helenius et al.
patent: 4539637 (1985-09-01), DeBruler
patent: 4633387 (1986-12-01), Hartung et al.
patent: 4839798 (1989-06-01), Eguchi et al.
patent: 4845633 (1989-07-01), Furtek
patent: 5050070 (1991-09-01), Chastain et al.
patent: 5187796 (1993-02-01), Want et al.
patent: 5247662 (1993-09-01), Minemura et al.
patent: 5471622 (1995-11-01), Eadline
patent: 5537319 (1996-07-01), Schoen
patent: 5630129 (1997-05-01), Wheat
patent: 5832272 (1998-11-01), Kalantery
patent: 5919011 (1999-06-01), Watanabe et al.
patent: 5930522 (1999-07-01), Fant
patent: 0 566 739 A1 (1993-10-01), None
patent: 0 570 584 A1 (1993-11-01), None
patent: 0 578 821 A1 (1994-01-01), None
patent: WO 92/12498 (1992-07-01), None
patent: WO 92/16971 (1992-10-01), None
patent: WO9325962 (1993-12-01), None
patent: WO 94/03929 (1994-02-01), None
Brzozowski, Janusz A. & Seger, Carl-Johan H.;Asynchronous Circuits—Monographs in Computer Science; Springer-Verlag New York, Inc., 1995, New York, NY.
Stephen H. Unger, Asynchronus Sequential Switching Circuits, 1969, pp. 221-229.
Carver Mead & Lynn Conway, Introduction to VLSI Systems, 1980, pp. 242-262.
Ivan E. Sutherland, Micropipelines, Communications of the ACM, Dec. 1989, vol. 32, No. 6.
Tadashi Shibata & Tadahiro Ohmi, A Functional MOS Transistor Featuring Gate-Level Weighed Sum and Threshold Operations, IEEE Transactions On Electron Devices, Dec. 1992, vol. 39, No. 6, pp. 1444-1455.
Anthony S. Wojcik & Kwang-Ya Fang, On The Design Of Three-Valued Asynchronous Modules, IEEE Transactions On Computers, Oct. 1980, vol. C-29, No. 10, pp. 889-989.
Mark Edward Dean, Strip: A Self-Time Risc Porcessor, Stanford University Computer Systems Laboratory Technical Report No. CSL-TR-92-543, Stanford, CA, Jul. 1992.
Daniel Hampel & Robert Winder, Threshold Logic, IEEE Spectrum, May 1971, pp. 32-39.
Stamos, James W. et al., Remote Evaluation, ACM Transactions on Programming Languages and Systems, vol. 12, No. 4, Oct 1990, pp. 537-565.
Liu, Jie et al., Self-Scheduling on Distributed-Me

Affiliated with

Also associated with

Rating

Invocation architecture for generally concurrent process... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Invocation architecture for generally concurrent process..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Invocation architecture for generally concurrent process... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2601748