Electrical computers and digital processing systems: multicomput – Distributed data processing
Reexamination Certificate
2000-06-30
2004-07-06
Chin, Stephen (Department: 2634)
Electrical computers and digital processing systems: multicomput
Distributed data processing
C709S249000, C709S252000, C375S377000
Reexamination Certificate
active
06760744
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention concerns a digital processing device P, particularly for processing of digital data and signal structures, wherein the data and signal structures comprise repeated sequences and/or nested patterns, and wherein the processing device P generally is configured as a regular tree with n+1 levels S
0
, S
1
, . . . S
n
and of degree k.
DESCRIPTION OF THE RELATED ART
Processing of large data volumes with use of repeated or recursive operations on very large data volumes can even in a restricted number often be a bottleneck when using conventional microprocessors and is thus amenable to massively parallel solutions wherein a very large number of processing elements simultaneously execute different operations in parallel on a large data stream, but possibly also parallel operations on several data streams. If such large data volumes appear in a form of data or signal structures with repeated sequences and/or nested patterns, the processing can be made more effective by being realized in parallel on the same or several different levels
From U.S. Pat. No. 486,020 (Stolfo & al.) there is known a parallel processing device structured as a binary tree, wherein a very large number of processors each with their own I/O unit are used. Generally Stolfo & al. discloses a computer with a very large number of processors connected in a binary tree structure such that each processor apart from those which constitute the root and the leaves of the tree has a single parent processor and two child processors. The processors typically work synchronously with data which are transmitted thereto from the parent processor and communicate the results on to the nearest succeeding processors, that is the parent processors' children. Simultaneously the child processors and the parent processor may also communicate with each other. According to Stolfo & al. each node constitutes a processing element which comprises a processor in the proper sense, a read/write memory or a random access memory, and an I/O device. The I/O device provides interfaces between each processing element and its parent and child processing elements such that a substantial improvement in speed whereby data are sent through the binary tree structure is obtained. As the binary tree structure has a processing element in every single node, the processing device will generally comprise 2
n
−1 processing elements, that is 1023 processing elements if the binary tree is realized with 10 levels. In a preferred embodiment the known parallel processing device has a clock frequency of 12 MHz, which in the case of using a tree with 1023 processors which each has an average instruction cycle time of 1.8&mgr;s, provides a processing performance of about 570 million instructions per second.
A binary parallel processor of this kind may for instance be well suited for handling decomposable or partitionable data processing problems, for instance searching in large information volumes. A partitionable search problem can be defined as a problem where a query about a relation between an object x and an object set corresponds to a repeated use of a commutative and associative binary operator b which has an identity and a primitive query which is applied between a new object x and each element f in the set F. One then has a partitionable search problem when the logic function OR is combined with the primitive query “is x=f” applied between the object x and each element f i F. As mentioned by Stolfo & al a problem which consists of answering a query about set F, may be answered by combining the answers of the queries applied to arbitrary subsets of F. The problem is in other words partitionable or decomposable and well suited for rapid execution by means of parallel processing. The set F is partitioned in a number of arbitrary subsets equal to the number of available processors. The primitive query q is then applied in parallel in each processor between the unknown x which is communicated to all processors and the locally stored element f in the set F. The results are then combined in parallel by log
2
N repetitions of the operator b, as a number of computations first is executed on N/2 adjacent pairs of processors and then a corresponding number of computations on N/4 pairs of processors with the results from the first computations. The operations hence move during the process to overlying levels in the binary tree, in other words from child processors to the parent processor etc. and are repeated in parallel on each level.
There is however a number of data processing problems wherein the data and signal structures comprise repeated sequences and/or nested patterns which are such that a processing device of the kind that is disclosed in U.S. Pat. No.
4,860,201 does not provide the desired flexibility or may not at all be suited for handling the problem. A binary tree structure as disclosed therein presupposes in principle that the problem can be binary partitioned and that operations take places in parallel on the same level. However, there may be problems which demand another degree of decomposition and where processing must be able to take place in parallel, but on different levels in the tree structure. The problems can also be partitioned such that it will be desirable with a larger partitioning capacity on one and the same level in some of the subtrees in the tree structure, and this in practice requires solutions which takes its starting point in a general tree structure which not only has an arbitrary number of levels, but also arbitrary degree, while nodes in subtrees not are only connected with the parent node of the tree in question, but for instance may be connected to a node on the same or underlying levels in neighbour trees. An increased degree of connectivity in a tree structure with a desired number of levels and of arbitrary degree will hence make it possible to reconfigure the original tree structure, either in the form of reduced trees or simple or complex graphs. Simultaneously can one or more of the leaf nodes be combined and take over the function of the parent node in question.
SUMMARY OF THE INVENTION
The object to the present invention is thus to provide a processing device which particularly suited for processing large data volumes in massive parallelism and on different levels in a general tree structure, but which simultaneously also can be configured arbitrarily as nested circuits on different levels and preferably under determined conditions such that a selected configuration on the given level is generated recursively by a configuration on an underlying level. Particularly it is the object that the processing device according to the invention shall be able to realize an MIMD processing device, that is a processing device which works with multiple instructions and multiple data.
The above-mentioned and other objects are obtained according to the invention with a digital processing device which is characterized in that the processing device P is provided in the form of a circuit P
n
on the level S
n
and forms the root node of the tree, that the nearest level S
n−1
is provided nested in the circuit P
n
and comprises k circuits P
n−1
which form the child nodes of the root node, that generally an underlying level S
n−q
in the circuit P
n
, where q∈{1,2 . . . n−1}, comprises k
q
circuits P
n−q
provided nested in the k
q−1
circuits P
n−q+1
on the overlying level S
n−q+1
, each circuit P
n−q+1
on this level comprising k circuits P
n−q
, that a defined zeroth level S
n−q
=S
0
in the circuit P
n
for q=n comprises from k
n−1
+1 to k
n
circuits P
0
which constitute kernel processors in the processing device P and on this level S
0
form leaf nodes in the tree, the kernel processor P
0
being provided nested in a number of 1 to k in each of the k
n−1
circuits P
1
on the level S
1
, that each of the circuits P
1
, P
2
. . . P
n
on respe
Halaas Arne
Leistad Geirr I.
Svingen Børge
Birch & Stewart Kolasch & Birch, LLP
Chin Stephen
Fast Search & Transfer ASA
Ha Dac V.
LandOfFree
Digital processing system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital processing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital processing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218257