Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-08-17
2001-09-04
Banankhah, Majid (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06286026
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to data processing having pull and push tasks.
2. Description of Related Art
In a system that emulates a multi-processing pipeline using a single-processing environment, each section of the pipeline is an instantiated function, or task, that performs one or more desired functions such as image processing functions, and sufficient data structure to self-define the state of the task. Such a system is disclosed in U. S. Pat. No. 5, 557,795 which is hereby incorporated by reference.
In operation, when a host application requires data from a raw data source to be processed, such as image data from a scanner or an image data file, a data processing pipeline is formed between the data source and the host application. The data processing pipeline inputs the raw data from the data source, processes the data so that it is in a form the host application can use, then provides it to the host application.
The image processing pipeline is formed by calling one of the functions in an image processing library, for example, and instantiating the called function to form a first task. The first task becomes an upstream-most section of the pipeline. The upstream-most pipeline section obtains a data element to be processed from the data source. In an image processing system, the data element could be a single scanline of a raster scan of an image. The data source could be a scanner, a facsimile machine, a remote computer, a sensor, or the like, outputting a serial or parallel data signal, or a block of stored data in a memory, such as a ROM, a RAM, or a disk in a disk drive. The data element can also be directly generated by the first pipeline section itself. In this last case, the data element can be obtained from the value of an initialized variable, from the state of the first pipeline section, or the like. Once the first pipeline section is instantiated, a backward or upstream link of the host application is set to the first pipeline section.
A second pipeline section is then generally needed to process the data element obtained by the first pipeline section. Therefore, the host application creates another task by instantiating one of the functions in the library to form a second pipeline section. When this second pipeline section is created, it is automatically linked to the first pipeline section. Additionally, the link of the host application is reset to the second pipeline section. If no other image processing operations are required, the link of the host application remains between the portion of the host application which requires the processed data and the second pipeline section.
Processing tasks in a pipeline processing are usually designed to interface with each other in an efficient manner so that a minimum of external controls are required to process the data. However, conventionally only similar types of processing tasks are integrated together to achieve one processing goal. This restriction is undesirable and thus new technology is required to provide greater flexibility in pipeline data processing.
SUMMARY OF THE INVENTION
This invention provides a device and method for processing data with a data processing string having push type and pull type tasks. Push tasks processes data and pushes the output of the process to downstream push tasks based on link paths. On the other hand, pull tasks sends data requests via upstream links to upstream pull tasks to acquire data for processing.
Data processing strings are usually configured with either all push tasks or all pull tasks to maintain consistency in the direction of links. The preferred embodiments of this invention provides a method and apparatus for inserting push tasks in a string of pull tasks and/or inserting pull tasks in a string of push tasks. The inserted push and pull tasks are enhanced with forward and backward message links and interface tasks are provided to interface between the inserted pull or push tasks in the strings of push or pull tasks, respectively.
When pull tasks are inserted in a push task string, a first interface task is placed between upstream push tasks and inserted pull tasks and a second interface is placed between the inserted pull tasks and downstream push tasks. When upstream push tasks pushes data into the first interface task, the first interface task invokes a forward message indicating the amount of data to the downstream inserted pull tasks. Each of the successive pull task also generate forward messages indicating the amount of data available until the information propagates to the second interface task. The second interface task then generates a data request and propagates the data request through the inserted pull tasks up to the first interface task. The first interface task responds by sending data downstream until the second interface task receives the processed data and pushes the processed data to downstream push tasks.
When push tasks are inserted in a string of pull tasks, a third interface task is inserted between upstream pull tasks and inserted push tasks and a fourth interface task is placed between the inserted push tasks and downstream pull tasks. When the downstream pull tasks sends a data request to the fourth interface task, the fourth interface task sends a backward message to upstream inserted pull tasks. The backward message is propagated through the inserted pull tasks until a backward message is sent to the third interface task. The third interface task responds by sending a data request to the upstream pull tasks which results in a first pull task pulling data from a database. When the upstream pull tasks process the data from the database and returns the data to the third interface task, the third interface task pushes the data into the inserted push tasks which results in data being pushed into the fourth interface task. When the fourth interface task receives the data pushed from the inserted push tasks, the data is returned to the downstream pull task that originally requested the data.
In view of the above, the first, second, third and fourth interface tasks as well as the forward message and backward message links enable push tasks to be inserted in a string of pull tasks and pull tasks to be inserted in a string of push tasks.
REFERENCES:
patent: 5557795 (1996-09-01), Venable
patent: 5995996 (1999-11-01), Venable et al.
Bollman James E.
Fleckenstein Patrick A.
Venable Dennis L.
Banankhah Majid
Oliff & Berridg,e PLC
Xerox Corporation
LandOfFree
Method and apparatus for integrating pull and push tasks in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for integrating pull and push tasks in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for integrating pull and push tasks in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2520173