Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-05-08
2001-01-30
Kizou, Hassan (Department: 2738)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395430, C707S793000
Reexamination Certificate
active
06181678
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a device for sorting data elements each including a respective sort key, comprising:
storage means organized according to a binary tree with 2
n
−1 nodes numbered from 1 to 2
n
−1 which are each able to contain a data element and are distributed in n successive stages numbered from 0 to n−1, whereby stage q comprises nodes 2
q
to 2
q+1
−1; and
means of control of the binary tree for dispersing the elements to be sorted within the tree in such a way as to satisfy an ordering condition according to which, for each integer i lying between 1 and 2
n−1
−1 such that node i contains an element to be sorted, each of the nodes
2
i
and
2
i+
1 either contains no element to be sorted, or contains an element whose sort key is greater than or equal to, in the sense of a determined order relation, the sort key of the element contained in node i.
The ordering of the elements in the sort tree corresponds to what is referred to as a “heapsort” in the field of computerized sorting. In this regard, reference may be made to the work by Knuth: “The art of computer programming, Vol. 3, Sorting and searching”, Addison Wesley, 1973, pages 142-157.
By way of illustration,
FIG. 1
shows, in the case where n=4, a sort tree comprising fifteen nodes 1-15 containing data elements (of which only the sort key is represented) which satisfy the ordering condition.
Node 1 of stage 0 is referred to as the root or vertex of the tree. The 2
n−1
nodes 2
n−1
to 2
n
−1 of stage n−1 are referred to as leaves of the tree. For each node i of a stage q, the 2
n−q
−1 nodes of the tree whose numbers are of the form i2
j
+j′, where j and j′ are integers such that 0≦j<n−q and 0≦j′<2
j
, are referred to as descendants of node i (here, node i is considered to be included in its descendants). Among these descendants, the sister nodes
2
i
and
2
i+
1 of stage q+1 (if q<n−1) are referred to as children of node i. The parent of node i (if q>0) is on the other hand defined as that node of stage q−1 whose number is i/2 if i is even and (i−1)/2 if i is odd. These logic relations of parentage between the nodes of the tree are represented by arrows in FIG.
1
.
The order relation between the sort keys is arbitrary. In the case illustrated in
FIG. 1
, it is the familiar order relation between the natural integers, allowing the sorting in ascending order of the sort keys. In the case of sorting in descending order, it is clearly sufficient to invert the order relation between the keys. In
FIG. 1
, the nodes of the tree which are not occupied by elements to be sorted are regarded as each containing an element whose sort key is infinite, that is to say greater than any sort key of a data element to be sorted. One possibility for coding an infinite key is to reserve one bit of the data field containing the key for this purpose; the key will for example be regarded as infinite if this bit is at 1 and as finite otherwise. In other words, this bit indicates whether the node is free or occupied by a data element.
Once it is loaded with a set of N<2
n
ordered data elements, the sorting device is capable of delivering these N elements sequentially in N cycles in the order of the sort keys. The extracting of an element from the tree in the course of a cycle consists in reading the element located at the root of the tree and in tracing back elements of its descent in such a way as to always satisfy the ordering condition. Thus, in the case represented in
FIG. 1
, the first cycle consists in reading the element
16
located at the root, and in moving element
24
to the root, then element
38
to node
2
and finally element
623
to node
4
. This amounts to propagating the extraction command from the root towards the leaves.
In some applications, it is necessary for the control means also to be capable of responding to commands for inserting a new element to be sorted into the tree. The sorting device is then capable of delivering or of receiving elements to be sorted at each cycle. It operates as a dynamic queue on the basis of the sort keys, managed according to the order relation used, and possibly representing time tags or any other type of priority index.
In known binary sort trees, the insertion command is not propagated from the root to the leaves of the tree since, at the level of the given node it is not known a priori to which of the two children the command is to be propagated, it being appreciated that the decendance of one of the two children may be completely filled and hence be inappropriate for receiving the command. The insertion command is therefore propagated from the leaves of the tree to the root. For example, to insert an element whose sort key is
28
into the tree of
FIG. 1
, it is written to a free leaf of the tree, for example leaf
9
, and comparisons are made gradually with the elements contained in the higher nodes; thus, elements
28
and
38
will be interchanged in order to re-establish the ordering in the example considered.
Under these conditions, the preceding cycle has to be completed at the time that the element having the smallest key is extracted from the tree. Accordingly, the speed at which the device can deliver or receive data elements is limited by the duration of the cycle for processing a command, this being proportional to the number of stages n, i.e. to the logarithm of the maximum number N of elements to be sorted. In applications where this number N is large, for example a few thousand, and where high speed is required, for example greater than 500,000 elements per second, the sorting device can no longer be constructed with known electronic circuits.
In their article “A real time sorter with application to ATM traffic control” (Proc. ISS'95, April 1995, Volume 1, pages 258-262), J. W. Roberts et al. have described a sorting device which does not suffer from the above speed limitation, that is to say which is capable of delivering and receiving the elements at a rate which is a priori independent of the maximum number of elements to be sorted. However, a drawback of the latter device is that the number of logic circuits operating in parallel is proportional to N. Once the number N of elements to be sorted becomes large (a few thousand or tens of thousands as in the case of the application to an ATM cell spacer envisaged in the article), the hardware complexity of the device becomes prohibitive.
An object of the present invention is to propose a fast sorting device of limited complexity.
SUMMARY OF THE INVENTION
The invention thus proposes a device of the type indicated in the introduction, wherein the control means respond to commands for modifying the contents of the binary tree which include commands for inserting a new element to be sorted. According to the invention, the means of control comprise m successive controllers each associated with a stage or with a plurality of consecutive stages of the binary tree, m being an integer lying between 2 and n, and n−1 interface registers between successive stages, among which each of the m−1 interface registers between stage pairs associated with different controllers constitutes a pipeline register, and wherein each command for modifying the contents of the binary tree is propagated from stage
0
to stage n−1 by means of the interface registers, the pipeline register or registers allowing parallel working of the controllers.
The complexity of the device is limited by the number m of controllers which is itself at most equal to the number n of stages of the tree, i.e. to the logarithm of the maximum number of elements to be sorted. The pipeline organization of the controllers allows parallel working and a high input and output rate of elements to be sorted. This rate is independent of the number of elements to be sorted. It is a maximum when the number m of controllers is equal to the number
Ha-Duong Tuan
Moreira Serafin Soares
Kizou Hassan
MET
Pezzlo John
Piper Marbury Rudnick & Wolfe
LandOfFree
Binary-tree data element sorting device and ATM spacer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Binary-tree data element sorting device and ATM spacer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary-tree data element sorting device and ATM spacer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523220