Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1997-07-15
2001-04-24
Maung, Zarni (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S028000, C717S152000, C717S152000, C717S152000, C717S152000, C717S152000
Reexamination Certificate
active
06223281
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data processing and specifically to a method of processing data using a parallel form of an algorithm which is normally run serially.
BACKGROUND OF THE INVENTION
An inherently serial data processing program is one in which a data processing unit processes program steps one-at-a-time and each successive step of the program further changes the results of the preceding step. Thus, each program step changes the total state of the data processing result in a serial fashion. These types of inherently serial programs can often be computation intensive. For example, data mining programs involve a large quantity of data records being analyzed in order to determine previously hidden trends or groupings in such data. In certain types of data mining algorithms, each record of the database is analyzed one-after-another (serially) and the resultant model (used, e.g., in trend prediction) is continuously updated based on the results of each of the serial computations.
While such serial processing gives a very precise result (since each and every data record is used in continuously altering the resultant model), a great deal of processing time is required.
Parallel processing techniques are known, in which a plurality of data processing units are provided and a separate processing unit is assigned, for example, its own mutually exclusive set of local data items, which may be data records, to process. This greatly shortens the overall computation time. If such a technique were applied to an inherently serial process, however, results quite different from the serial case would be attained, thus dissuading such parallel techniques from being used for such an inherently serial process where a specific result is desired.
That is, in such an inherently serial process, where a specific result is required, each processing step is always performed using the state of the resultant model as it was modified by the immediately preceding processing step. This will give the specific required result, since every data record is always processed with full knowledge of how each preceding data record has altered the resultant data model. However, if the total number of data records were divided amongst a plurality of parallel processing units, each processing unit would process its local data independently of the results being attained by the other processing units. Each data record would not be processed with full knowledge of how each preceding data record has altered the resultant data model. Accordingly, parallel processing will not give the same final result as would be attained using serial processing.
Thus, parallel processing techniques have not generally been applied to inherently serial processes where a specific result is required. Parallel techniques have been instead used to run other types of programs where it is not so important to take into account the processed effect of each successive data record. Inherently serial processes in which a specific result is required thus have traditionally suffered from long computation times due to the fact that each data item must be serially processed.
SUMMARY OF THE INVENTION
According to the present invention, an inherently serial program is processed in parallel, thus leading to higher processing speeds, while maintaining a controllable approximation to the specific result obtained from a serial running of the program. This goal has been attained based on the fact that the desired degree of closeness between a parallel result and the serial result depends on the particular inherently serial program being run and the type of analysis being performed. That is, some inherently serial processes require a “fine-tuned” result while for others a “coarser” result is acceptable.
Specifically, when the processing takes place in parallel, a processing phase occurs. The processing taking place at each parallel branch is divided into a number of parallel phases. Between these phases, the individual processing results attained by the parallel processing units of each parallel branch are combined. The number of data items processed by each processing unit of a parallel processing system during each parallel phase can be used to control the degree of closeness to the serial result. The less data items processed during each parallel phase, the closer the parallel result will be to the serial result.
During a parallel phase local data items are processed by the processing units, in such a way that each processing unit assumes that there are no other processing elements and that only the local processing unit is going to affect the resultant model. Then, after each processing unit has processed its respective set of data items, the results obtained by each processing unit are collated and the resultant model is altered based on the collated result and communicated to each of the parallel processing units. Then, each processing unit processes another set of data items and the processing, collating, resultant model altering and communicating steps are repeated until a decision is made that no more processing is required, for example, there are no more data items left to be processed. During this process the number of data items processed during each phase can be dynamically altered to correspondingly alter the degree of closeness to the result which would be attained using serial processing.
Thus, the invention is drawn to a method of computer processing an inherently serial program involving the sequential processing of data items, comprising steps of: selecting a number, nPara, of data items to be processed by each of a plurality of processing units of a parallel processing system, with the selection being dependent on the desired degree of closeness between the parallel result and the result which would be attained if the program were run serially; communicating the nPara data items to each processing unit; processing said nPara data items by each respective processing unit; collating the processing results obtained by each processing unit; altering the overall result based on the collated result; and distributing the altered overall result to each processing unit for further processing of remaining data items.
REFERENCES:
patent: 4901224 (1990-02-01), Ewert
patent: 4980824 (1990-12-01), Tulpule et al.
patent: 5088034 (1992-02-01), Ihara et al.
patent: 5148547 (1992-09-01), Kahle et al.
patent: 5151991 (1992-09-01), Iwasawa et al.
patent: 5230053 (1993-07-01), Zaiki
patent: 5506998 (1996-04-01), Kato et al.
patent: 2261968 (1993-06-01), None
patent: WO96/02883 (1996-02-01), None
Bird Colin Leonard
Lingenfelder Christoph
Phippen Robert William
Wallis Graham Derek
Farrell Timothy M.
International Business Machines - Corporation
Kappos David J.
Maung Zarni
Nguyen Dzung C.
LandOfFree
Method of controlling the degree of parallelism when... 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 of controlling the degree of parallelism when..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of controlling the degree of parallelism when... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2525152