Apparatus for managing relationships between objects

Abstract

For any pair of two distinct objects (i, j) and for each relationship that may exist between said two objects, the management apparatus includes a memory element RMP(i,j) for storing either the existence or the non-existence of said relationship. This memory element includes an input corresponding to a first object (i) and an input corresponding to a second object (j), which inputs are connected to two individual buses (CC(j), LC(i)) corresponding respectively to said two objects. These two inputs must receive two respective control signals simultaneously in order to write information in said element indicating either the existence or the non-existence of a relationship between these two objects. In a preferred embodiment, the input corresponding to the first object must receive a read signal for the memory element to restore said information on an output corresponding to the second object; and the input corresponding to the second input must receive a read signal for the memory element to restore said information on an output corresponding to the first object. These memory elements are organized in a triangular array (TN') if the relationship is symmetrical. The apparatus is applicable to asynchronous transfer mode telecommunications switching systems.

Claims

What is claimed is:

1. An apparatus for managing relationships between individually identifiable objects in a finite address field, wherein for each pair of two distinct objects including a first object X and a respective second object Y, a particular relationship may operably exist to associate said first object X and said second object Y, the apparatus comprising:

an array of relationship memory elements for storing relationship information indicating the existence or the non-existence of said relationship between respective pairs of first objects X and second objects Y,

said array having at least two dimensions and formed by a plurality of buses capable of conveying object selection signals and operation control signals, and wherein a relationship memory element is situated at a cross-point between two individual buses, that are orthogonal to each other among said plurality of buses making up said array, each individual bus corresponding to a respective object and operable to convey at least one selection signal for selecting said respective object;

each said relationship memory element includes a logic circuit operable to receive at least one selection signal and operable to receive at least one operation control signal to write or read relationship information in said relationship memory element; and

a logic means coupled to bus access points to supply the buses with said object selection signals, and to receive from the buses relationship information read from the relationship memory elements.

2. The apparatus according to claim 1 for managing relationships that are not necessarily symmetrical between two distinct objects in a set of objects comprising N objects, wherein the plurality of buses comprise:

N column control buses, corresponding respectively to the N objects, and respectively controlling N columns of relationship memory elements;

N row control buses, corresponding to the N rows of relationship memory elements; each row control bus forming a cross-point with each column control bus; and

wherein the array of relationship memory elements comprises N(N-1) relationship memory elements to operably store each relationship relating a respective first object and a respective second object out of N distinct objects; said relationship memory elements located at cross-points between the column control buses and the row control buses, with the exception of cross-points situated on a diagonal of the array.

3. The apparatus according to claim 1 for managing symmetrical relationships in a set of objects comprising N objects, wherein the plurality of buses comprise:

N individual buses corresponding respectively to the N objects, each individual bus having a first branch and a second branch sharing a common end; each individual bus forming a cross-point with each of the other buses of said N individual buses;

wherein the array of relationship memory elements includes ##EQU3## relationship memory elements (RMP(I,K)), to operably store each symmetrical relationship that may associate a respective first object and a respective second object in said set of N objects;

wherein the relationship memory elements storing the relationship information between the objects of rank i=1 to K-1 and the object of rank K, for K lying in the range 1 to N, are situated at cross-points between the first branch of the individual bus corresponding to said object of rank K, and the second branches of respective individual buses corresponding to the objects of ranks i=1 to K-1; and

wherein the relationship memory elements storing relationship information between the object of rank K and the objects of ranks j=K+1 to N are situated at cross-points between the second branch of the individual bus corresponding to said object of rank K, and the first branches of respective individual buses corresponding to the objects of ranks j=K+1 to N.

4. The apparatus according to claim 1, wherein the logic circuit of a relationship memory element situated at the cross-point of an individual bus corresponding to a first object X and an individual bus corresponding to a second object Y comprises read authorizing means for authorizing the reading of relationship information stored at said relationship memory element, if said read authorizing means receives at least one selection signal conveyed by the individual bus corresponding to the first object, and for authorizing the reading of said information if it receives at least one selection signal conveyed by the individual bus corresponding to the second object; the information read being restored at least on the individual bus corresponding to the second object Y when the selection signal is received on the individual bus corresponding to the first object, and the information read is restored at least on the individual bus corresponding to the first object X when the selection signal is received on the individual bus corresponding to the second object.

5. The apparatus according to claim 1, wherein said apparatus is operable to enable an operation of writing relationship information in the relationship memory element to store information indicating the existence or the non-existence of a relationship between a first object and a second object, by explicitly selecting said first and second objects, the logic circuit of said relationship memory element further includes write authorizing means for authorizing the writing of relationship information concerning a relationship between said first object X and said second object Y if said write authorizing means simultaneously receives at least one selection signal conveyed by the individual bus corresponding to the first object X, and at least one selection signal conveyed by the individual bus corresponding to the second object Y.

6. The apparatus according to claim 1, wherein each individual bus, corresponding to a respective object is operable to convey at least first and second selection signals to select the object by assigning the object to at least one group of first and second groups of objects concerned by a writing operation;

wherein the logic circuit of each relationship memory element includes write authorizing means for authorizing a writing operation in the relationship memory element if, simultaneously:

at least the first selection signal relating to the first group is present on the individual bus corresponding to the first object X; and

at least the second selection signal relating to the second group is present on the individual bus corresponding to the second object Y.

7. The apparatus according to claim 6, wherein the logic means coupled to the bus access points includes:

supplying means for supplying a first combination of values of the selection signals to each individual bus corresponding to an object which is to be assigned exclusively to the first group (A) for a given writing operation;

second supplying means for supplying a second combination of values of the selection signals to each individual bus corresponding to an object which is to be assigned exclusively to the second group (B) for said given writing operation; and

third supplying means for supplying a third combination of values of the selection signals to each individual bus corresponding to an object which is to be assigned both to the first group and to the second group for said given writing operation;

wherein to write information indicating the existence or the non-existence of a relationship associating each first object in a first subset of predetermined objects with each second object in a second subset of predetermined objects, without performing the same writing operation for relationships between the objects belonging exclusively to the first subset, or performing the same writing operation for relationships between the objects belonging exclusively to the second subset, the logic means supplies:

the first combination of values to the individual buses corresponding to the objects belonging exclusively to the first subset or to the second subset, one of the two subsets being chosen arbitrarily so as to assign these objects exclusively to the first group (A);

the second combination of values to the individual buses corresponding to the objects belonging exclusively to the second subset so as to assign these objects exclusively to the second group (B); and

the third combination of values to the individual buses corresponding to any objects belonging simultaneously to both the first and second subsets so as to assign these objects exclusively to the second group (B).

8. The apparatus according to claim 1, wherein the logic circuit of each relationship memory element includes operation authorization means for authorizing an operation if the logic circuit receives at least one of:

object selection signal and operation control signal supplied by one of the two individual buses at a cross-point where the relationship memory element is situated, for an operation based on selecting a single object, the other object being arbitrary and

two object selection signals and operation control signals simultaneously supplied respectively by the two individual buses at the cross-point where said relationship memory element is situated for an operation based on selecting two objects.

9. The apparatus according to claim 8, wherein each individual bus corresponding to an object is operable to convey:

at least one signal for selecting an object and controlling writing of information indicating the existence of a relationship between said object and another object;

at least one signal for selecting an object and for controlling writing of information indicating the non-existence of a relationship between said object and another object;

at least one signal for selecting an object and controlling reading of information indicating the existence or the non-existence of a relationship between said object and another object; and

at least one read output signal conveyed an access point of the bus.

10. The apparatus according to claim 1, further comprising an operation control bus (OC) common to all of the relationship memory elements and operable to convey at least one non-specific operation control signal

wherein the logic control circuit of each relationship memory element further includes means for authorizing an operation if the logic control circuit receives simultaneously at least one operation control signal operation control bus, and at least one selection signal conveyed by at least one individual bus.

11. The apparatus according to claim 8, wherein each individual bus corresponding to an object is operable to convey:

at least one read output signal for conveying read information to an access point of said bus; and

said apparatus further comprises an operation control bus common to all of the relationship memory elements is operable to convey at least:

a common signal for controlling an operation of writing information indicating the existence of a relationship between said object and another object;

a common signal for controlling an operation of writing information indicating the non-existence of a relationship between said object and another object; and

a common signal for controlling an operation of reading information indicating the existence or the non-existence of a relationship between said object and another object.

12. The apparatus according to claim 1, wherein said apparatus is operable to perform a first complex operation said first complex operation comprising writing common information indicating the existence or the non-existence of relationships between a given object and all of the other objects simultaneously

wherein said buses are capable of conveying a combination of signals to all of the relationship memory elements that are capable of storing relationship information concerning relationships between the given object and all of the other objects, said combination of signals being specific to the given object and specific to the first complex operation, so as to select the given object and so as to cause the first complex operation to be performed;

wherein the logic means coupled to the access points of the buses include means for transmitting the combination of signals over the buses;

and wherein the logic circuit of each relationship memory element (RMP1 (X, Y); RMP2 (X, Y)) includes a first authorizing means (OC1; OC'1) for authorizing writing of relationship information in the relationship memory element, if the logic circuit receives said combination of signals.

13. The apparatus according to claim 1, wherein said apparatus is operable to perform a plurality of different operations simultaneously, the operations respectively belonging to subsets of disjoint possible operations, wherein

each individual bus is operable to convey a plurality of distinct selection signals supplied by the logic means coupled to the access points of the buses; and

the logic circuit of each relationship memory element includes means for authorizing performance of all of the operations belonging to a subset when the circuit receives at least one of:

a selection signal conveyed by one of the two individual buses that form a crosspoint where a respective relationship memory element is situated, said selection signal being allocated specifically to the subset of operations, in the case of a subset of operations based on selecting a single object; and

a combination of two different selection signals respectively conveyed by the two individual buses that form across point where a respective relationship element is situated, the combination of two selection signals being allocated specifically to the subset of operations, in the case of a subset of operations based on simultaneously selecting two objects.

14. The apparatus according to claim 13, wherein said apparatus is operable to perform a first write operation and a different second write operation simultaneously, for relationships between two selected objects, each of the write operations belonging to a distinct subset of possible operations,

wherein each individual bus (B0(P), B0(P); B0(N), B0 (N); B0 (Q), B0 is operable to convey at least two distinct types of selection signals; and

the logic circuit of each relationship memory element includes means for authorizing:

the first write operation when the logic circuit receives a first combination (IST1 (P).IST1 (Q)=1) made up of two selection signals respectively supplied by the two individual buses that form a crosspoint where a respective relationship memory element is situated; and

the second write operation when the logic circuit receives a second combination made up of two selection signals respectively supplied by the two individual buses that form a crosspoints where a respective relationship memory element is situated.

15. The apparatus according to claim 12, wherein for said first complex operation, each individual bus corresponding to a given object is operable to convey said combination of signals specific to the given object and specific to the first complex operation; and

wherein the logic means coupled to the access points of the individual buses include means for supplying said combination of signals to the individual bus corresponding to each given object;

wherein the logic circuit of each relationship memory element further includes means authorizing writing of information indicating the non-existence of a relationship in the relationship memory element if said combination of signals is conveyed by one of the two individual buses that form a crosspoint where the respective relationship memory element is situated.

16. The apparatus according to claim 12, wherein said combination of signals specific to a given object and specific to the fist complex operation is made up firstly of a selection signal corresponding to the given object and secondly of a releasing control signal conveyed by an operation control bus that is common to all of the relationship memory elements;

wherein the logic means coupled to the access points of the buses include means for simultaneously applying the releasing control signal to the operation control bus, and the selection signal (SSA.sub.X =1; RD.sub.P =1) to the individual bus corresponding to each given object;

wherein the logic circuit of each relationship memory element further includes a second authorizing means for authorizing writing of information, indicating the non-existence of a relationship in the relationship memory element if the releasing control signal is applied to the operation control bus, and if, simultaneously, the selection signal is applied to one of the two individual buses (B02 (X), B02 (Y); B03 (X), B0'3 (Y)) that form a crosspoint where the respective relationship memory element is situated.

17. The apparatus according to claim 13, wherein said apparatus is operable to perform a second complex operation said second complex operation comprising two simultaneous read operations for reading all of the relationship information indicating the existence or the non-existence of relationships established between at least one object and any other object for a first read operation (La), and between at least one other object and any other object for a second read operation, the identified objects being split up into two distinct groups referred to as output groups relating respectively to the first and second read operations;

wherein the individual bus corresponding to each object is operable to transmit a first read selection signal a second read selection signal, the first and second read selection signals being distinct and specific to the second complex operation; and wherein the individual bus is operable to transmit a first read output signal, and for transmitting a second read output signal, the first and second read output signals being specific to the second complex operation;

logic means including means for supplying the first read selection signal, and means for supplying the second read selection signal to the individual buses; the first read selection signal and the second read selection signal being supplied respectively to the individual buses corresponding respectively to each object from which a first read operation is to be performed, and to each object from which a second read operation is to be performed; and the logic means include means for receiving the first and second read output signals that may be conveyed by each individual bus; and

wherein the logic circuit of each relationship memory element relating to the first object and to the second object further includes means for authorizing four read operations, that may or may not be simultaneous, for reading the relationship memory element such that:

a first read operation from the first object is performed if the first read selection signal is conveyed by the individual bus corresponding to the first object;

a second read operation from the first object is performed if the second read selection signal is conveyed by the individual bus corresponding to the first object;

a first read operation from the second object is performed if the first read selection signal (RSA.sub.Y ; SSA.sub.Y) is conveyed by the individual bus corresponding to the second object; and

a second read operation from the second object is performed if the second read selection signal (RSB.sub.Y ; SSB.sub.Y) is conveyed by the individual bus corresponding to the second object.

18. The apparatus according to claim 17, wherein each of the first and second read selection signals also constitutes a read operation control signal;

and wherein the means for performing the four possible read operations depends on the first and second read selection signals and read operation control signals that are received by the logic circuit.

19. The apparatus according to claim 17, further comprising an operation control bus that is common to all of the elements and is operable to convey a non-specific read control signal {(RD) that is common to the first and second read operations (La, Lb);

wherein the logic means include means for further supplying the non-specific read control signal to the operation control bus; and

wherein the means for performing the four read operations operates only if the logic circuit further receives the non-specific read control signal.

20. The apparatus according to claim 4 wherein said apparatus is operable to perform a third complex operation, said third complex operation comprising reading by propagation from a reference object so as to identify all of the objects having direct or indirect relationships with the reference object, said apparatus further comprising:

a bus that is common to all access points of the selection buses, and that is operable to convey an operation control signal specific to the third complex operation; and

wherein the logic means coupled to the access points of the individual buses includes, for each individual bus (B01 (K), B)'1 (K); B02 (K), B0 corresponding to an object logic means supplying at least one selection signal to the bus if a read output signal is present on the bus, and if the operation control signal specific to the third complex operation is present on the bus that is common to all of the access points.

21. The apparatus according to claim 20, wherein a selection signal supplied by the logic means coupled to the access points of the selection buses also constitutes a read operation control signal for the relationship memory elements.

22. The apparatus according to claim 20 further comprising an operation control bus that is common to all of the relationship memory elements (RMP1"(X,Y); RMP2 (X,Y))" and that is operable to convey at least one non-specific operation control signal;

wherein the read authorizing means authorizes a reading operation only if the logic circuit receives the non-specific read control signal; and

wherein the logic means coupled to the access points of the individual buses further supply the non-specific read control signal to the operation control bus that is common to all of the elements, simultaneously with selection signal.

23. The apparatus according to claim 20 wherein said apparatus is operable to perform a fourth complex operation, said fourth complex operation comprising: identifying and releasing, by propagation, direct or indirect relationships between a given object and any other object, wherein the logic means supplies:

a selection signal to the bus corresponding to the given object; and

an operation control signal specific to the third complex operation, to the bus that is common to all of the access points of the buses to identify all of the objects that have direct or indirect relationships with the given object;

wherein the logic means further receives read output signals identifying by propagation each object that has a relationship with the given object;

supplies a selection signal to the individual bus of each object identified by propagation; and

supplies at least to the elements storing information indicating the existence of relationships between the given object and the objects identified by propagation, a combination of selection and releasing control signals so as to write in each of the relationship memory elements information indicating the non-existence of a relationship.

24. The apparatus according to claim 23, wherein the logic means includes:

means for supplying a selection signal to the individual bus of each object identified by propagation during both a first time interval and a second interval; the selection signal also constituting a read control signal; and

means for supplying a selection signal to the individual bus of each object identified by propagation during the second time interval only; the combination of the selection signal and the control signal during the second time interval causing information to be written indicating the non-existence of a relationship.

25. The apparatus according to claim 23, further comprising an operation control bus that is common to all of the elements and is operable to convey a non-specific control signal that is specific to the first complex operation; and

wherein the logic means further includes:

means for supplying a selection signal to the individual bus of each object identifying by propagation during both a first time interval and a second time interval;

means for supplying a read control signal to the operation control bus during both the first time interval and the second time interval; and

means for supplying a non-specific signal to the operation control bus (OC) during the second time interval only, so as to write information indicating the non-existence of a relationship.

26. The apparatus according to claim 14, wherein said apparatus is operable to perform a fifth complex operation said fifth complex relationship comprising releasing a relationship between a first object and any second object and setting up a new first relationship (P-N) between the first object and a third object and a new second relationship between the third object and the second object,

wherein the logic means coupled to the access points of the buses include means for simultaneously supplying:

a selection signal of a first type to the individual buses of the first object and of the second object; and

a selection signal of a second type (RT2, ST2, SS2) to the individual bus of the third object;

and wherein the logic circuit of each relationship memory element includes means for performing the following:

a first write operation comprising writing information indicating the non-existence of a relationship, when the logic circuit receives a first combination of two signals (RT1.sub.P.RT1.sub.Q =1; SS1.sub.P.SS1.sub.Q =1) made up of two signals of the first type over the two individual buses that form a cross-point where a respective relationship memory element is situated; and

a second write operation comprising writing information indicating the existence of a relationship, when the logic circuit receives a second combination of selection signals made up of a signal of the first type and of a signal of the second type over respective ones of the two selection buses that form a crosspoint where the relationship memory element is situated.

27. The apparatus according to claim 12, wherein said apparatus is operable to perform a sixth complex operation said sixth complex operation comprising releasing relationships existing between a given object, referred to as an "object to be removed" and at the most two other objects referred to as "adjacent objects" in a linear chain of relationships between objects, and setting up a relationship directly between the two adjacent objects

wherein said sixth complex comprises a first operation for reading the relationship memory elements storing information indicating the existence of any relationships between the object to be removed and any other object; and a second operation for writing information, indicating the existence of a relationship, in a relationship memory element, relating to two adjacent objects identified by the first operation wherein said first and second operations are performed consecutively during a first time interval and

wherein the logic means coupled to the access points of the buses includes a first operation means for supplying, during the first operation, a first selection and operation control signal (RS.sub.E =1; RD.sub.E =1), applied to the individual bus of the object to e removed to cause reading to be performed in the elements storing the relationships between the object to be removed and all of the other objects; and

said management apparatus further includes a second operation logic means for propagating a second selection and operation control signal relating to the second operation, said second operation logic means being coupled to the individual buses to supply said second selection and operation control signal to the individual bus of an object if the bus is conveying a read output signal so as to write information indicating the existence of a relationship between two adjacent objects identified by the first operation;

and wherein said means to perform the first complex operation is used in a second time interval to release the relationships existing between the object to be removed and the adjacent objects.

28. The apparatus according to claim 27, further comprising a propagation control bus that is common to all of the relationship memory elements, and that transmits a "propagation control" signal (EC=1) specific to the sixth complex during the first time interval ;

logic means for writing information indicating the existence of a relationship between the adjacent objects, produces a write control signal over each individual bus corresponding to an adjacent object to which the relationship memory element is connected, if:

the common propagation control signal specific to the sixth operation is present on the propagation control bus;

and, simultaneously, a read control signal (RS.sub.E =1) is present on the individual bus corresponding to the object to be removed (E); and

and the relationship information read in the relationship memory element indicates the existence of a relationship;

said apparatus further includes means for writing information indicating the existence of a relationship when the logic circuit simultaneously receives two write control signals for causing information to be written indicating the existence of a relationship, the signals being received over respective ones of the two individual buses to which the respective relationship memory element is connected; and.

29. The apparatus according to claim 27, further comprising a propagation control bus that is common to all of the access points and that is capable of transmitting a common propagation control signal specific to the sixth complex operation;

wherein the logic means coupled to the access points of the control buses includes:

means for transmitting during the first time interval the common propagation control signal specific to the sixth complex operation;

wherein for each individual bus corresponding to an object, means for supplying a selection and write control signal for causing information to be written indicating the existence of a relationship, if the propagation control signal specific to the sixth complex operation is active, and if, simultaneously, a read output signal indicating the existence of a relationship between the object to be removed and at least one adjacent object is active on the individual bus; and

means for ceasing transmission during the second time interval, the propagation control signal specific to the sixth complex operation and for transmitting the releasing signal specific to the first complex operation and causing information to be written indicating the non-existence of a relationship, the releasing signal being transmitted over the bus corresponding to the object to be removed, so as to release all of the relationships between the object to be removed and any other objects;

and wherein the logic circuit of each relationship memory element further includes:

means for writing information indicating the existence of a relationship when the logic circuit simultaneously receives two individual selection and write control signals for causing information to be written indicating the existence of a relationship, the signals being received over respective ones of the two individual buses that form a cross-point to which the respective relationship memory element is connected; and

means for writing information indicating the non-existence of a relationship when the logic circuit receives the releasing control signal specific to the first complex operation, for releasing a relationship with the object to be removed.

30. the apparatus according to claim 27, further comprising an identification and propagation bus that is common to all of the relationship memory elements, and that is operable to transmit an identification and propagation control signal specific to the sixth complex operation, and a releasing control signal;

wherein the logic circuit of each relationship memory element includes:

logic means for supplying a "write control propagation" signal for writing information indicating the existence of a relationship, over one of the two individual buses that form a crosspoint where the respective relationship memory element is situated, if a read output signal indicating the existence of a relationship is supplied to the bus by the relationship memory element, and if, simultaneously, the identification and propagation control signal specific to the sixth complex operation is applied; and

means for writing information indicating the non-existence of a relationship, in the relationship memory element, if the releasing control signal is applied to the identification and propagation bus, and if, simultaneously, a selection and read control signal (RD.sub.E =1) is applied to one of the individual buses that intersect each other at the relationship memory element;

and wherein the logic means coupled to access points of the control buses include means for:

activating the following simultaneously during the first time interval:

the identification and propagation control signal specific to the sixth complex operation, over the identification and propagation bus;

the selection and read control signal over the individual bus corresponding to an object to be removed; and

the write control signal over the identification and propagation bus, so as to write information indicating the existence of a relationship between two objects adjacent to the object to be removed; and said logic means coupled to the access points further comprises:

means for activating the following simultaneously during the second time interval:

the selection and read control signal over the individual bus corresponding to the object to be removed; and

the releasing control signal over the identification and propagation bus, so as to write information indicating the non-existence of any relationship between the object to be removed and all of the other objects.

31. The apparatus according to claim 4, wherein when the logic circuit of the relationship memory element performs a read operation, said logic circuit restores relationship information simultaneously over the individual bus corresponding to the first object, and over the individual bus corresponding to the second object, if said logic circuit receives a selection signal via at least one of the two individual buses, as well as a read control signal.

32. The apparatus according to claim 1, wherein said apparatus is operable to restore at least one read output signal at an access point corresponding to an object, said read output signal indicating the existence or the non-existence of at least one relationship with the object X, wherein each memory element includes:

an output relating to the first object X and that is connected to as least one conductor of the bus corresponding to the first object; X all the outputs relating to the first object X being connected together and constituting a wired-OR transmitting at least one read output signal to the access point relating to the first object; and

an output (01(Y); 02(Y)) relating to the second object Y and that is connected to at least one conductor of the bus (B0'1(Y); B0'2(Y)) corresponding to the second object; all of the outputs relating to the second object being connected together and constituting a wired-OR transmitting at least one read output signal to the access point relating to the second object.

33. The apparatus according to claim 1, wherein to limit a reading operation to relationships concerning the objects belonging to a known subset, the logic means further include filter logic means that are coupled to the relationship memory element outputs relating to the objects, and that do not take account of the signals supplied by said outputs, during a read operation.

34. The apparatus according to claim 1, wherein each relationship memory element stores a single bit indicating the existence or non-existence of relationship between said first object X and said second object Y.

35. The apparatus according to claim 34, wherein the relationship information stored in each relationship memory element corresponds to a temporal relationship between said first object X and said second object Y.

36. The apparatus according to claim 34, wherein the relationship information stored in each relationship memory element corresponds to a priority relationship between said first object X and said second object Y .

Description

The invention relates to an apparatus for managing relationships between objects that are individually identifiable in a finite address field, and more particularly to an apparatus for real time applications. Each relationship associates two objects belonging to the same set of objects, or belonging to two respective sets containing objects of the same type or of different types. The term "relationship" should be understood broadly since the particular relationship may vary as a function of the application under consideration. Also, a given object may be associated with one or more other objects by one or more relationships of different kinds.

A particularly important application lies in the field of telecommunications, and more particularly in the field of managing relationships between cells transferred in asynchronous mode. An asynchronous transfer mode (ATM) switching system includes one or more buffer memories for temporary storage of cells to be switched. The buffer memory is generally used as a queue, e.g. of the first-in first-out (FIFO) type. In this first example of an application, it is necessary to manage order relationships between the various locations of the buffer memory to indicate the queue order of cells which are stored in respective ones of said locations.

In this application, the relationship is of the type "next cell in the queue" and it associates one cell which is situated at a certain location in the buffer memory with another cell that is "next" and that is situated in some other location in the buffer memory. In general, for a buffer memory that is shared by a plurality of queues, that other location is not an adjacent location, since locations are released in an order which is random and they are reused as they are released.

Conventionally, the order of respective cells in a queue is managed by managing cell identifiers, such as the addresses of the memory locations containing the cells. For example, to store the queue order of cells stored in a buffer memory, their addresses are written in successive addresses of a so-called "address memory", which is write addressed by a write pointer incremented by unity after each write operation, and read addressed by a read pointer that is incremented by unity after each read operation. The order in which the addresses are written in consecutive rows of this memory determines the order in which the cells will be read back from the buffer memory.

Another conventional method for managing the order of cells in a queue consists in making up a list of addresses that are chained in a random access memory referred to as a "link memory". Locations in the link memory correspond to respective locations in the buffer memory. Each location in the link memory contains an address which is the next address to be used, both for reading the next cell in the buffer memory and for reading the next address to be used in the link memory. Such a method of managing order between cells is described, for example, in European patent application No. 0 441 787 (Henrion 18).

In those two conventional examples of managing the order between cells in a queue, the explicit identifiers used are cell addresses, while the relationships between cells remain implicit.

There exists another type of relationship which does not define a special order or a special classification of objects, but rather that they belong to the same subset or group of objects, with all of the objects of the subset under consideration having exactly the same characteristics with respect to this relationship. In the field of telecommunications, an example of such a relationship is to be found between cells that are to be restored by a buffer memory during the same time interval for the purpose of resequencing cells in an order corresponding to their order of arrival. When a cell arrives in the switching system under consideration, the system associates therewith a time label indicating the time interval during which the cell is to be restored on one of the outlets of the switching system. All of the cells which are associated with the same time label are then associated with said time label by a special relationship of the "belonging to a subset" type, without there being any order relationship between the various cells belonging to the set. Such a method of resequencing cells is described, for example, in European patent application No. 0 438 415 (Henrion 17).

To manage such groupings in a set of non-ordered objects, it is conventional to use:

a queue memory in which the cells remain long enough for late cells to catch up with others having the same time label; and

a stack to which all of the cells having said label are transferred in no particular order other than that of the time labels of each subset of cells.

Known methods of managing relationships between objects in sets of objects that are ordered or not ordered, are conventionally implemented by means of conventional random access memories or by means of contents-addressable memories. Implementing those known methods always reduces to storing object identifiers, not identifiers of relationships between objects. It is thus the manner in which object identifiers are stored, e.g. as a function of their order in a queue, which determines implicitly the order relationships between the objects. As a result, conventional apparatuses for managing objects by means of implicit relationships suffer from the following limitations:

The time required for executing management operations becomes prohibitive if it is necessary to manage a plurality of relationships during the same operation; for example to find and rearrange relationships when an object is to be added or removed from a given set.

Implementing apparatus for managing a plurality of relationships is extremely complex because the management of implicit relationships is distributed in a plurality of distinct memories containing object identifiers for the purpose of saving time by enabling operations to be performed in parallel. Complexity increases rapidly with the number of memories and with the number of parallel paths needed to interconnect the various accesses to the memories: conductors for selecting a memory element; conductors for controlling writing; and conductors for controlling reading.

The object of the invention is to propose apparatus for managing relationships between objects, which apparatus satisfies real time constraints better, and therefore makes it possible to consider management operations that are more complex than those performed at present (parallel execution and/or combined execution of a plurality of unit operations), implying one or more types of relationship within the same set of objects or within a structure comprising a plurality of sets of objects.

For example, in the field of asynchronous transfer mode switching systems, it may be advantageous to manage a plurality of relationships in an ordered set of cells, the relationships respectively indicating: the next cell, the preceding cell, the first cell of an ordered list, and the last cell of an ordered list. In a non-ordered subset of cells, it may be advantageous to manage relationships between a cell and each of the other cells, or between each cell and a cell considered as a reference for the subset under consideration. Managing such "belonging-to" relationships makes it possible to group cells together in different priority levels concerning cell loss and/or delay to apply to each cell; in cell resequencing groups; in outlet queues; etc.

The invention provides apparatus for managing relationships between individually identifiable objects in a finite address field,

characterized in that for each pair of two distinct objects, referred to as a first object and a second object, and for each relationship that may associate these two objects, the apparatus includes a "relationship" memory element for storing "relationship" information indicating the existence or the non-existence of said relationship;

in that said relationship memory elements are structured in an array having at least two dimensions by means of a plurality of buses capable of conveying object selection signals and operation control signals, each element being situated at a cross-point between two "individual" buses, each individual bus corresponding to a respective object and being suitable for conveying at least one "selection" signal for selecting said object;

in that each element includes a logic circuit capable of receiving at least one selection signal and capable of receiving at least one operation control signal to write or read relationship information in said element; and

in that the apparatus includes logic means coupled to bus access points to supply them with operation control signals, to supply them with object- selection signals, and to receive from them information read in the relationship memory elements.

in that the apparatus includes logic means coupled to bus access points to supply them with at least operation control signals and object selection signals; and to receive information read in the relationship memory elements.

The apparatus characterized in this way thus manages relationships between two objects directly, i.e. explicitly, instead of managing them indirectly, since each memory element serves to store or to restore the existence or the non-existence of a relationship between two objects by direct addressing, by activating individual buses corresponding to the objects.

The apparatus characterized in this way provides much faster processing speed than prior art apparatuses since it makes it possible to access relationship information directly by a bus array. This distributed array structure provides very fast access to each memory element corresponding to a relationship between two objects. Also, read activation of an individual bus corresponding to a given object gives access in a single operation to all of the memory elements storing the relationships established between said object and the other objects of the set. A single read operation thus makes it possible to know all of these relationships simultaneously. The time required is thus very short. Similarly a single write operation makes it possible to store the existence or the non-existence of a plurality of relationships simultaneously.

A preferred embodiment of the apparatus of the invention for managing relationships that are not necessarily symmetrical between two distinct objects in a set of objects comprising N objects, is characterized in that the individual buses comprise:

N column control buses, corresponding respectively to the N objects, and respectively controlling N columns of elements;

N row control buses, corresponding to the N objects, and respectively controlling N rows of elements; each row control bus having a cross-point with each column control bus; and

in that the relationship management apparatus comprises N(N-1) memory elements for each relationship capable of relating two out of N distinct objects; said elements being situated at cross-points between the column control buses and the row control buses, with the exception of cross-points situated on a diagonal of the array.

Another preferred embodiment of the apparatus of the invention for managing symmetrical relationships in a set of N objects is characterized in that it comprises N individual buses corresponding respectively to the N objects, each individual bus having a first branch and a second branch sharing a common end; and each individual bus having a cross-point with each of the other buses of said N buses;

in that the relationship management apparatus includes ##EQU1## relationship memory elements, for each symmetrical relationship that may associate two distinct objects in said set of N objects;

in that the memory elements storing the relationship information between the objects of rank i=1 to K-1 and the object of rank K, for K lying in the range 1 to N, are situated at cross-points between the first branch of the individual bus corresponding to said object of rank K, and the second branches of the respective individual buses corresponding to the objects of ranks i=1 to K-1; and

in that the memory elements storing relationship information between the object of rank K and the objects of ranks j=K+1 to N are situated at cross-points between the second branch of the individual bus corresponding to said object of rank K, and the first branches of the respective individual buses corresponding to the objects of ranks j=K+1 to N.

This embodiment presents the advantage of being particularly simple since it makes it possible with N access points to manage symmetrical relationships between N objects, while using only 1/2(N.sup.2 -N) memory elements. It is usable for most relationships since they are generally symmetrical. For example, if a cell A is placed in front of a cell B, then it is clear that the cell B is placed behind the cell A when use is made of the cells being sequenced in a known order. There is then no need to store both of these redundant relationships.

In certain particular applications, this structure also makes it possible to gain access simultaneously to relationships between first and second subsets of the set of memory elements without simultaneously accessing the relationships between the objects within the same subset. Access is then both fast and selective.

The invention will be better understood and other characteristics will appear from the following description of embodiments and from the accompanying drawings:

FIGS. 1 to 4 are diagrams summarizing four embodiments of the apparatus of the invention;

FIG. 5 is a diagram summarizing a first embodiment of a relationship memory element for the apparatus of the invention;

FIG. 6 shows an "orthogonal" bus and an access point corresponding to a given object, for controlling the embodiment shown in FIG. 5;

FIG. 7 is a diagram summarizing a variant of the first embodiment shown in FIG. 5;

FIG. 8 shows how management apparatus including memory elements such as the element shown in FIG. 5 operates, during a reading operation for reading relationships between objects of two subsets A and B (when reading is performed from A);

FIG. 9 is a diagram summarizing an embodiment of apparatus of the invention including memory elements such as the element shown in FIG. 5, and showing how it operates when an operation is performed on relationships relating the objects of a subset S of a set of objects;

FIG. 10 shows the problem that arises when a writing operation concerns two subsets of objects (S1 and S2);

FIG. 11 is a diagram summarizing a second embodiment of a relationship memory element for the apparatus of the invention;

FIG. 12 shows an "orthogonal" bus and an access point corresponding to a given object, for controlling the embodiment shown in FIG. 10;

FIG. 13 shows how management apparatus including memory elements such as the element shown in FIG. 10 operates, during reading of all of the relationships existing between a single object and all of the other objects in the set under consideration;

FIGS. 14 and 15 show two operating variants of the same apparatus during two variants of the same write operation performed on relationships relating the objects of a subset S1 and the objects of a subset S2 (where S1 and S2 are disjoint), with the exception of all of the relationships between the objects of the same subset;

FIGS. 16 and 17 are diagrams summarizing a variant embodiment of the apparatus of the invention that includes memory elements such as the element shown in FIG. 5, and showing how it operates while a write operation is being performed on relationships relating the objects of a subset S1 and the objects of a subset S2, where S1 and S2 are disjoint;

FIG. 18 shows another use of management apparatus including memory elements such as-the element shown in FIG. 11, during a write operation for writing relationships between objects of two arbitrary and non-disjoint subsets S1 and S2;

FIG. 19 is a diagram summarizing a variant of the second embodiment shown in FIG. 11;

FIGS. 20 to 22 show the use of the apparatus of the invention in managing relationships between a plurality of static subsets of objects respectively grouping together objects belonging to different categories;

FIGS. 23 to 26 show four elementary structures of relationships making it possible to manage the objects of a dynamic subset;

FIG. 27 shows the read operation for reading the relationships existing between a given object and the objects belonging to three distinct subsets;

FIGS. 28 and 29 show a write operation concerning relationships between objects belonging to two groups;

FIGS. 30 and 31 show a first complex operation consisting in releasing any relationship existing between an object and any other object;

FIG. 32 is a diagram summarizing a variant of the first embodiment of a relationship memory element, which variant makes it possible to perform the first complex operation;

FIG. 33 is a diagram summarizing a variant of the second embodiment, which variant makes it possible to perform the first complex operation;

FIGS. 34 and 35 show a second complex operation consisting in two simultaneous read operations for reading all of the relationships existing between two given objects and other objects, with the output being separated into respective groups for the objects identified by the two read operations;

FIG. 36 is a diagram summarizing a variant of the first embodiment, which variant makes it possible to perform the second complex operation;

FIG. 37 is a diagram summarizing a variant of the second embodiment, which variant makes it possible to perform the second complex operation;

FIG. 38 shows a third complex operation consisting in reading by propagation;

FIG. 39 is a diagram summarizing a variant embodiment of the access point shown in FIG. 6, which variant includes additional logic means for performing the third complex operation;

FIG. 40 is a diagram summarizing a variant embodiment of the access point shown in FIG. 12, which variant includes additional logic means for performing the third complex operation;

FIG. 41 shows a fourth complex operation consisting in releasing the relationships by propagation;

FIG. 42 is a diagram summarizing a variant embodiment of the access point shown in FIG. 6, which variant makes it possible to perform the fourth complex operation;

FIG. 43 is a timing diagram showing how this variant operates;

FIG. 44 is a diagram summarizing a variant embodiment of the access point shown in FIG. 12, which variant includes additional means making it possible to perform the fourth complex operation;

FIG. 45 is a timing diagram showing how the fourth complex operation is performed;

FIG. 46 shows a fifth complex operation consisting in releasing a relationship between two objects and in inserting a new object between the two objects by establishing two new relationships;

FIG. 47 shows how the fifth complex operation is implemented;

FIGS. 48 and 49 are diagrams summarizing two variants of the first embodiment, which variants include additional logic means for making it possible to perform the fifth complex operation;

FIGS. 50 and 51 are diagrams summarizing two variants of the second embodiment, which variants include additional logic means for making it possible to perform the fifth complex operation;

FIG. 52 shows a sixth complex operation consisting in removing a known object E from a linear chain of objects related by relationships without knowing its adjacent objects, and in automatically establishing a direct relationship between the two possible adjacent objects that flanked the removed object;

FIG. 53 is a diagram summarizing a variant of the first embodiment, which variant includes additional logic means compared with the variant shown in FIG. 30, so as to make it possible to perform the sixth complex operation;

FIG. 54 is a timing diagram showing how this variant operates;

FIG. 55 is a diagram summarizing a variant embodiment of the access point shown in FIG. 12, which variant includes additional logic means making it possible to perform the sixth complex operation;

FIG. 56 is a diagram summarizing a third embodiment of a relationship memory element for the apparatus of the invention, this variant including additional logic means making it possible to perform the first complex operation and the sixth complex operation, i.e. releasing all of the relationships existing between a given object and any other object, then automatically establishing relationships between the objects which were previously related indirectly via the given object;

FIG. 57 is a timing diagram showing how the variant operates for performing the sixth complex operation; and

FIGS. 58 and 59 respectively show variants of the first and second embodiment.

FIG. 1 is a diagram summarizing a portion of a non-optimized first embodiment of the apparatus of the invention. This portion comprises a square array SN constituted by a matrix of memory elements RMP, each element storing the existence or the non-existence of a relationship that could associate two objects belonging to the same set E constituted by N objects that are respectively identifiable by N distinct identifiers: Nos. 1, . . . , N. Initially, we consider the case of a uniform set E, i.e. a set made up of objects belonging to a single category. For example, they may all be cells or they may all be time intervals.

The logic circuits that make use of the stored information are not shown. The array SN has N rows and N columns, each row and each column comprising N elements RMP. The elements RMP are placed at the cross-points of row buses LC(1) . . . LC(N) serving the respective rows of the matrix and column buses CC(1) . . . CC(N) serving respective columns of the matrix.

The existence of a relationship, e.g. between the Xth object and the Yth object, taken in that order, is stored by writing a 1-value bit in the element RMP(X,Y) situated at the cross-point between buses CC(X) and LC(Y). The existence or the non-existence of a relationship between these two objects can be determined by reading the contents of this element.

Write and read control of the buses is described below. The term "bus" is used to cover any conventional means for conveying the same signal to or from a set of memory elements. The simplest embodiment comprises one conductor per signal, but other conventional embodiments implementing multiplexing can be used in apparatus of the invention.

Such a structure requires N.sup.2 memory elements RMP for a set E constituted by N objects. It can quickly be seen that some of the elements are not useful. Those situated on the diagonal of the matrix, shown in dashed lines, are not useful since no object has a relationship with itself. Also, the relationships encountered in practice are generally symmetrical relationships: being reciprocal or inverse. For reciprocal relationships, if an object X has a certain relationship with an object Y, then the object Y has the same relationship with the object X. For example, the relationship "identical to" is symmetrical. For inverse relationships, if the object X has a certain relationship with the object Y, then Y has a fully specified inverse relationship with the object X. For example, considering the order of arrival of a sequence of objects in the context of processing said objects sequentially in the order of their arrival: if an object X arrived before an object Y, then it can be deduced implicitly that the object Y arrived after the object X, and it is therefore not necessary to store the existence of the second relationship.

FIG. 2 is a diagram summarizing a portion of a second embodiment of the apparatus of the invention, optimized for a symmetrical relationship. It comprises a triangular array TN of memory elements. As in FIG. 1, the logic circuits that make use of the stored information are not shown. The matrix of memory elements has been simplified by omitting the memory elements situated on the diagonal and those situated on one-half of the matrix, as defined by said diagonal. The buses CC(1) and LC(N) are omitted since neither of them serves any memory elements.

For example, by using the column bus CC(K) and the row bus LC(1) . . . LC(K-1), for given K less than or equal to N, it is possible to write or read information representing the existence or the non-existence of a relationship between an object of rank K and K-1 other objects Nos. 1, . . . , K-1. The corresponding elements RMP are shown in black. Below, the object of rank K is called object K.

By using the column buses CC(K+1), . . . , CC(N) and the row bus LC(K), it is also possible to write or to read in the elements RMP information indicating the existence or the non-existence of relationships between object K and the objects K+1, . . . , N. The corresponding elements RMP are shown with shading. It can thus be seen that the buses CC(K) and LC(K) are used simultaneously for writing or reading information concerning relationships between the object K and all of the other objects in the set of objects 1, . . . , N. It is possible to connect these two buses together at a common point referred to below as the access point for object K, and written AP(K).

FIG. 3 is a diagram summarizing a third embodiment of the apparatus of the invention that is optimized for a symmetrical relationship and in which there is only one access point AP(K) for each object K, with K lying in the range 1 to N. It comprises a triangular array TN' having, for example, the form of a right-angle triangle. The N column buses CC(X) and the N row buses LC(Y) are replaced by N "orthogonal" buses each comprising two mutually orthogonal branches sharing a common end connected to an access point. Each orthogonal bus corresponds to a respective object. For example, access point AP(K) corresponding to the object of rank K in a set of N objects is connected to an orthogonal bus comprising a branch BO(K) and a branch BO'(K) which branches are respectively parallel to the two sides of the array TN' that are at right angles.

To store information representing the existence or the non-existence of a symmetrical relationship between two distinct objects selected from N, this array TN' comprises ##EQU2## memory elements RMP. The memory elements RMP(i,K) that store relationship information between the object of rank K, for K selected in the range 1 to N, and the objects of ranks i=1 to K-1, are situated at the respective cross-points between the branch BO(K) and the branches BO'(i) of the respective orthogonal buses corresponding to objects of ranks i=1 to K-1. The memory elements RMP(j,K) that store relationship information between the object of rank K and the objects of ranks j=K+1 to N are situated at the cross-points between the branch BO'(K) of the orthogonal bus corresponding to the object of rank K, and the branches BO(j) of the respective control buses corresponding to the objects of ranks j=K+1 to N.

All of the access points AP(1), . . . , AP(N) of the triangular array TN' are connected to logic means LM to provide the control buses with read control signals and write control signals to manage the relationships between the objects.

Below, only symmetrical relationships are considered and the memory element storing the existence or the non-existence of a relationship between an object X and an object Y, and the symmetrical relationship, is written RMP(X,Y) or RMP(Y,X).

The examples of array structure described herein have control buses in the form of mutually orthogonal straight segments. However any other form could be used providing each bus corresponding to an object has at least one cross-point with each of the control buses corresponding to the other objects, since each memory element must be situated at a cross-point between two buses.

FIG. 4 is a perspective diagram summarizing a fourth embodiment of the array which is distributed over three space dimensions. This embodiment is optimized for a symmetrical relationship between four objects No. 1, . . . , No. 4. It comprises four orthogonal buses each constituted by a first branch and a second branch, with the exception of one of the buses in which the second branch is not useful. This fourth embodiment comprises three superposed triangular layers:

a layer TN1 in which the first branches BO(1), . . . , BO(4) of the orthogonal buses are situated;

a layer TN2 in which six relationship memory elements are situated such as the element RMP(3,4) which stores the existence or the non-existence of a relationship between object No. 3 and object No. 4; and

a layer TN3 in which the second branches BO'(1), BO'(2), and BO'(3) of the orthogonal buses are situated.

The first branches BO(1), . . . , BO(4) are connected respectively to four access points AP(1), . . . , AP(4). The branches BO(1), BO(2), and BO(3) are respectively connected to the second branches BO'(1), BO'(2), and BO'(3) by buses BV(1), BV(2), and BV(3) which are orthogonal to the planes of the three layers. Each memory element is connected to the first branch of an orthogonal bus and to the second branch of another orthogonal bus by a plurality of links which are orthogonal to the planes of the layers TN1, TN2, and TN3. For example, memory element RMP(3,4) is connected to branch BO'(3) by a plurality of links L3; and it is connected to the branch BO(4) by a plurality of links L4.

In the same set of N objects, two types of relationship may exist simultaneously between objects: relationships which are mutually exclusive, and relationships which are not exclusive:

When all of the relationships are exclusive, i.e. if there can be only one relationship between two objects in the set belonging to two given categories at any instant, the nature of the relationship between two objects can remain implicit since it can be deduced from the category of each of the two objects. A single relationship memory element can then manage the existence of a relationship between two objects whatever the nature of the relationship. For example, when each of the two objects is either a cell or a time position, there exists three kinds of relationship which are exclusive depending on whether the two objects both belong to the same "cell" category, or both belong to the same "time position" category, or belong respectively to the "cell" category and to the "time position" category.

When the relationships are non-exclusive, and therefore capable of existing simultaneously between two given objects, the array of the management apparatus must include a plurality of memory elements per pair of objects in order to be able to store the existence or non-existence of each of the possible relationships. This array comprises either one memory element per relationship, or else a restricted number of memory elements, with the data representing the existence or the non-existence of each relationship being encoded. For example, the existence or non-existence of six relationships called relationships of types 1, 2, 3, . . . , 6 can be encoded and stored by means of three memory elements by storing the following binary words:

    ______________________________________
    000            No relationship
    001            Relationship of type 1
    010            Relationship of type 2
    011            Relationship of type 3
    100            Relationships of types 2 and 3
    101            Relationships of types 2 and 4
    110            Relationship of type 5
    111            Relationships of types 5 and 6
    ______________________________________