Method and circuit for processing digital signals representative of vectors or tuples of the same dimension and application thereof to sets having any cardinality and to vectors or tuples of any dimensions

A method of processing digital signals representative of vectors referred to as tuples of varying dimensions, said processing being carried out between pairs of vectors Xi with components {xki} of a first set of vectors R and of vectors Yi with components {yki} of a second set of vectors S, said processing comprising causing pairs of said vectors Xi, Yi to meet so as to bring together components of the same order k{xki};

• {yki} and effecting computation on said components, said method comprising the steps of:
• partitioning said sets of vectors into partition vectors of dimension p;
• completing any partition vector having a dimension less than p with components of arbitrary value;
• designating said first set of vectors as spatial meeting data, corresponding to a succession in time of spatial meeting data vectors rk formed by the partition vectors of said first set;
• designating said second set of vectors as input data, said input data being formed from at least one partition vector of said second set of vectors;
• and
• meeting in space and in time of said input data and spatial meeting data using parallel processing, said parallel processing being organized as a two-dimensional network of cells for processing said components {xki} and {yki} of same order k, one of the dimensions of said two-dimensional network referred to as the x dimension being assigned to said succession in time of spatial meeting data vectors Rk and the other dimension of said two-dimensional network referred to as the y dimension being assigned to the input data so as to perform a spatial parallelism processing in which an input data vector meets in parallel a plurality of spatial meeting data vectors and a time parallelism processing in which a plurality of input data vectors are processed in parallel.

A circuit for processing digital signals representative of vectors referred to as tuples of the same dimension p, the processing being carried out between pairs of vectors Xi with components {xki} of a first set of vectors R and vectors Yi with components {yki} of a second set of vectors S, said processing comprising causing pairs of vectors Xi, Yi to meet so as to bring together components of the same order k{xki};

• {yki} and for carrying out a computation on said components, said circuit comprising:
• first means for storing one of the sets of vectors R in the form of spatial meeting data, said stored spatial meeting data being able to be read as a succession in time of spatial meeting data vectors Rk formed by said vectors Xi;
• second means for storing the other set of vectors S in the form of input data, said stored input data being formed from at least one vector Yi of said other set S of vectors;
• computing means for receiving said spatial meeting data from said first storing means and said input data from said second storing means and for providing a meeting in space and time of the input data and the spatial meeting data using parallel processing, said computing means comprising as a two-dimensional network of cells for processing said components {xki} and {yki} of the same order, said succession in time of spatial meeting data vectors being assigned to one of the dimensions x of said two-dimensional network and the input data being assigned to the other dimension y of this network so as to perform a spatial parallelism processing in which an input data vector meets in parallel a plurality of spatial meeting data vectors and a time parallelism processing in which a plurality of input data vectors are processed in parallel.

A circuit for comparing relations in a data base, each relation being formed by a set of tuples each having a plurality of attributes, the comparison being carried out between pairs of attributes R.A of a first set of tuples R and attributes S.A of a second set of tuples S, said processing comprising causing pairs of attributes R.A, S.A to meet so as to bring together components of the same order {R.Ai};

• {S.Ai} and for comparing said components, said circuit comprising:
• means for chopping said sets of tuples into sets of partition tuples having a number of attributes p;
• first means for storing said first set of partition tuples in the form of spatial meeting data, said stored spatial meeting data being able to be read as a succession in time of spatial meeting data tuples Rk formed by said attributes R.A;
• second means for storing said second set of partition tuples in the form of input data, said input data being formed from at least one attribute S.A of said second set S of tuples;
• and
• computing means, receiving said spatial meeting data from said first storing means and said input data from said second storing means, for providing a meeting in space and time of the input data and the spatial meeting data using parallel processing, said computing means being formed as a two-dimensional network of cells for processing said components {R.Ai} and {S.Ai} of the same order, said succession in time of spatial meeting data vectors being assigned to one of the dimensions x of said two-dimensional network and the input data being assigned to the other dimension y of this network so as to perform a spatial parallelism processing in which an input data attribute meets in parallel several spatial meeting data tuples and a time parallelism processing in which several input data attributes are processed in parallel, each processing cell forming the computing means, in order to carry out an elementary comparison, being formed by an elementary processor comprising:
• a digital comparator for responding to the test R.A=S.A, R.S<S.A, where R.A and S.A are either attributes or parts of attributes,
• a programmable control unit which responds to one of the following tests R.A<S.A, R.A=<S.A, R.A=S.A, R.A.>=S.A, or R.A>S.A, said programmable control unit delivering a result bit of value 1 on a positive response to the test considered and a result bit of value 0 in the opposite case, and
• a programmable unit for re-combining said result bit delivered by said programmable control unit for the test considered with a prior intermediate result bit.

A system for processing digital signals representative of vectors referred to as tuples of the same dimension p of a data base, said system comprising a plurality of circuits connected in parallel, each circuit of said system carrying out processing between pairs of vectors Xi with components {xki} of a first set of vectors R and vectors Yi with components {yki} of a second set of vectors S, said processing comprising causing said pairs of vectors Xi, Yi to meet so as to bring together components of the same order k{xki};

• {yki} and for carrying out a computation on said components, each of said circuits comprising:
• first means for storing one of the set of vectors R in the form of spatial meeting data, said stored spatial meeting data being able to be read as a succession in time of spatial meeting data vectors Rk formed by said vectors Xi;
• second means for storing the other set of vectors S in the form of input data, said input data being formed from at least one vector Yi of said other set S of vectors;
• computing means for receiving spatial meeting data from the first storing means and input data from said second storing means and for providing a meeting in space and time of the input data and the spatial meeting data using parallel processing, said computing means being formed as a two-dimensional network of cells for processing said components {xki} and {yki} of the same order, said succession in time of spatial meeting data vectors being assigned to one of the dimensions x of said two-dimensional network and the input data being assigned to the other dimension y of this network so as to perform a spatial parallelism processing in which an input data vector meets in parallel several spatial meeting data vectors and a time parallelism processing in which several input data vectors are processed in parallel;
• and
• said first and second storing means each comprising;
• a working memory plane in which a sub-set of corresponding vectors is stored during processing, said working memory plane being directly interconnected by a parallel interconnection to the processing cells of said two-dimensional network along the dimension to which said corresponding data is assigned, and
• a phantom memory plane interconnected to a mass memory and to said working memory plane respectively, said phantom memory plane acting as an auxiliary memory of the working memory plane for a sub-set of corresponding vectors of a higher order during the processing of said sub-set of corresponding vectors;
• each circuit receiving respectively at its working memory plane and phantom memory plane of said first storing means a partition R'1, R'2, . . . , R'k of the set of spatial meeting data vectors, said working memory plane and phantom memory plane of said second storing means receiving in parallel the input data vectors, which increases the cardinality of the sets of spatial meeting data tuples processed without modifying the bit rate, for the same processing time.