Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1994-08-08
2001-06-05
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06243762
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to digital data processing and, more particularly, to the execution of parallel tasks on multiprocessing systems.
Developers of multiprocessing computer systems have found it desirable to create parallel processing software tools by redesigning existing uniprocess applications. This typically involves supplementing those existing applications by adding software that partitions input data for access across multiple processors, releases that data to the processors, and gathers up the results, e.g., for display to the operator.
Although this has a tremendous appeal, it is evident that only those applications with high computation-to-I/O ratios benefit from such a simplistic approach. Moreover, as the number of processors performing an application increases, the marginal benefit of adding one more processor decreases. This is because partitioning and collection time stays the same, or increases due to additional overhead, while the per-processor processing time decreases due to greater concurrency.
An objective of the present invention is, therefore, to provide improved methods and apparatus for execution of parallel tasks on multiprocessing systems.
More particularly, an objective is to provide a high-performance, flexible, scalable and easy-to-use systems for implementing and/or executing programs for parallel execution on such systems.
A related object is to provide an improved method of interprocess access of data on multiprocessing systems.
SUMMARY OF THE INVENTION
The invention provides improvements on multiprocessing systems that have a plurality of processes, each with an associated memory, and mechanisms that permit each process to access storage locations in the memory of other processes by specifying addresses (or other such indicators) associated with those locations.
The improvement is characterized, according to one aspect of the invention, by an allocation element that allocates data buffers with portions encompassing data storage locations in one or more of the process memories. A mapping element generates addresses from storage location expressions that are made in terms of (i) the id.'s of processes in whose memories those locations reside, and (ii) offsets from a unique pointer—referred to as a pas_ptr—associated with each data buffer.
By way of example, the mapping element can generate an address for a memory location “10, pas_ptr+4,” where “10” is the process id., and “pas
—ptr+
4” refers to a location four words from the start of the corresponding data buffer portion in the memory of that process. The processes rely on the mapping element to determine addresses that can be applied to the system's data access mechanisms and, thereby, provide access to specific memory locations.
According to other aspects of the invention, a process can generate a request for creation of a distributed buffer. The allocation element responds by allocating a multi-part buffer having portions distributed among memories corresponding to a specified set of processes. The portions can be the same length, encompassing the same number of data storage locations in their respective memories. Those portions can reside at a common offset from the start of designated “heap” regions within the memories. The value of that offset can be reflected, for example, in the pas_ptr of the data buffer.
According to other aspects of the invention, a process can generate a request creation of an assembled buffer, causing the allocation element to allocate a unitary buffer on the memory of a single, specified process.
Multiple processes can generate tagged requests for allocation of a single buffer. For example, where processes #
1
, #
3
, #
4
and #
10
require access to a common buffer—distributed or assembled—each can generate a tagged request. The allocation element responds to the first such request by creating the buffer and returning to the first requester a pas_ptr. It responds to subsequent requests, simply, by returning the same pas_ptr, thereby, affording those processes access to the same distributed or assembled data buffer.
Other aspects of the invention provide still further improvements on multiprocessing systems that have a plurality of processes, each with an associated memory element, and mechanisms that permit each process to access storage locations in the memories of another process by specifying addresses (or other such indicators) associated with those locations. The improvements in this regard include providing a data buffer of the type described above, having one or more portions distributed among the process memories.
Further, a master process transmits to one or more slave processes a signal identifying a function or procedure that the slaves are to execute. That signal can be, for example, an index to a common table of pointers to function/procedure instructions. In addition, the master process transmits a signal identifying in a data buffer storage location to be used in executing the function/procedure, e.g., a pass-by-reference “argument.” The master process specifies that argument as an process id./pas_ptr expression, as described above.
The slave processes, which include mapping elements that generate addresses from process id./pas_ptr expressions, execute the requested function/procedure and access the relevant storage locations by supplying those addresses to the multiprocessing system's data access mechanisms.
According to a related aspect of the invention, the master process can supply to the slave processes multiple arguments.
According to other aspects of the invention, the master process can itself create (or spawn) the slave processes through operating system functionality provided by the multiprocessing system. Once created, each slave process can enter a wait state pending notification (e.g., via a semaphore) from the master of a command to invoke a function/procedure.
In still other aspects, the invention provides an improved digital data processor of the type having multiple functional units, e.g., multiple processes. The improvement is characterized by inclusion, in at least a selected functional unit, of a set of buffers (or scalars) that store status information, or flags, received from the other functional units. A flag-wait element associated with the selected functional unit monitors one or more of those buffers and generates a signal indicating whether values stored therein meet a specified condition (e.g., they are greater then, less then, or equal to a specified value). Where the condition is not met, the element can enter a wait state, according to one aspect of the invention.
According to other aspects of the invention, the selected functional unit can include a buffer for storing status information that unit generates itself, as well as still more sets of buffers for storing other status information from the other functional units.
In yet another aspect, the invention provides methods of generating computer programs for execution on multiprocessing systems. The method is characterized by the step of identifying in a first sequence of instructions—e.g., a user-generated computer program—selected function/procedure calls. Those calls can be identified, for example, by linking an object version of the program and noting function/procedures listed as having unidentified references.
The method further calls for generating, e.g., via an automated process, a second sequence of instructions that define the selected function/procedure. The function/procedure is generated to include instructions that (i) generate an index identifying a corresponding function/procedure to be executed by one or more slave processes, and (ii) invoke a driver sequence of instructions for transferring, to one or more slave processes, that index and arguments for use in executing that corresponding function/procedure.
According to the method, the first, second and driver sequences are executed on a master process, while a so-called third sequence of instructions in executed on the slave pr
Gogolinski James
Greene Jonathan E.
Banankhah Majid A.
Lao Sue
Mercury Computer Systems, Inc.
Nutter & McClennen & Fish LLP
Powsner David J.
LandOfFree
Methods and apparatus for data access and program generation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for data access and program generation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for data access and program generation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2495538