CN104714782A - Matrix data element identification serialization method and system - Google Patents

Abstract

The invention discloses a matrix data element identification continuous method and system, relating to the computer field. The method includes: for N computing nodes, each computing node participating in the calculation reads the data element of the matrix partition assigned to the computing node in the matrix data; each computing node participating in the computing identifies Propagation rules, keep the data identifiers in the read data elements locally or send them to the corresponding computing nodes, and receive the data identifiers sent by the remaining N-1 computing nodes, and obtain the final data processed by the computing nodes identification; each calculation node participating in the calculation performs serialization according to the final data identification, and obtains a first identification corresponding to each data identification; each calculation node participating in the calculation notifies the corresponding relationship between the first identification and the original data identification to other computing nodes. For large-scale matrix data, serialization can be carried out in parallel through each computing node, which speeds up the speed of serialization and improves the efficiency of data processing.

Description

Method and system for continuous identification of matrix data elements

technical field

The invention relates to the field of computers, in particular to a method and system for continuous identification of matrix data elements.

Background technique

In large-scale parallel computing, a very important type of calculation is the calculation of matrices or vectors. Usually, the description matrix adopts triplets of (Rowkey, colkey, value) (where Rowkey, colkey are the row label and column label respectively, and value is the actual stored data content), so that the sparse storage method can be used to reduce the storage space. The user then divides the matrix by row (Rowkey) or column (colkey), and distributes the data to multiple computing nodes (that is, computing servers), so as to achieve the purpose of parallel computing. Usually, in order to uniquely identify each data element in the matrix, the input Rowkey and colkey adopt a signature with more digits (64 bits, 128 bits). In the actual calculation process, Rowkey and colkey are only used as a subscript and do not require a lot of digits. Therefore, in order to reduce the memory storage space of the node and facilitate sequential access during calculation, it is often necessary to continuously id the key and colkey, that is, convert both Rowkey and colkey into continuous 0-N integer columns.

In the prior art, there is a serial id method to id the storage identifier of matrix data, that is, a computing node is used to obtain the data elements in the matrix one by one and id their row and column labels , but the processing efficiency of this method is low and the time is long.

Contents of the invention

In view of the above problems, the present invention is proposed to provide a matrix data element identifier serialization device and a corresponding matrix data element identifier serialization method that overcome the above problems or at least partially solve the above problems.

According to one aspect of the present invention, a method for continuous identification of matrix data elements is provided, including:

For N computing nodes, each computing node participating in the calculation reads the data elements of the matrix block assigned to the computing node in the matrix data;

Each computing node participating in the calculation keeps the data identifier in the read data element locally or sends it to the corresponding computing node according to the preset data identifier spreading rule, and receives the data sent by the remaining N-1 computing nodes identification, obtaining the final data identification processed by the computing node;

Each computing node participating in the calculation performs serialization according to the final data identifier, and obtains a first identifier corresponding to each data identifier;

Each computing node participating in the calculation notifies other computing nodes of the correspondence between the first identifier and the original data identifier.

Optionally, the data elements of the matrix block allocated to the computing node in the matrix data read by each computing node participating in the computing include:

Each computing node participating in the calculation reads the data elements in the matrix data that are divided into blocks by rows, or data elements that are divided into blocks by columns.

Optionally, said each computing node participating in the calculation, according to the preset data identifier spreading rule, retaining the data identifier in the read data element locally or sending it to the corresponding computing node includes:

Each computing node participating in the calculation keeps the column identifier in the read data element locally or sends it to the corresponding computing node according to the column identifier spreading rule of the threshold; and receives the column identifier sent by other N-1 computing nodes .

Optionally, each computing node participating in the calculation performs serialization according to the final data identifier, and obtaining the first identifier corresponding to each data identifier includes:

Each computing node participating in the calculation generates a row identifier vector according to the local row identifier, and serializes the row identifier vector to obtain the first row identifier corresponding to each row identifier;

Each computing node participating in the calculation deduplicates the local column identifiers to generate column identifier vectors, and serializes the column identifier vectors to obtain the first column identifier corresponding to each column identifier.

Optionally, each computing node participating in the computing notifying other computing nodes of the correspondence between the first identifier and the original data identifier includes:

Each computing node participating in the calculation notifies other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier.

Optionally, each of the computing nodes participating in the calculation retains the data identifier in the read data element locally or sends it to the corresponding computing node according to the preset data identifier spreading rule, including:

Each computing node participating in the calculation keeps the row ID in the read data element locally or sends it to the corresponding computing node according to the row ID spreading rule of the threshold; and receives the row ID sent by other computing nodes.

Optionally, each computing node participating in the calculation performs serialization according to the final data identifier, and obtaining the first identifier corresponding to each data identifier includes:

Each computing node participating in the calculation generates a row identification vector according to the local column identification, and serializes the column identification vector to obtain the first column identification corresponding to each column identification;

Each computing node participating in the calculation deduplicates the local row ID to generate a row ID vector, and serializes the row ID vector to obtain the first row ID corresponding to each row ID.

Optionally, each computing node participating in the computing notifying other computing nodes of the correspondence between the first identifier and the original data identifier includes:

Each computing node participating in the calculation notifies other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier.

Optionally, the continuous vector includes:

Each calculation node i participating in the calculation counts the total number of identifiers Ni to be calculated, and notifies the other calculation nodes of the total number;

Each computing node participating in the calculation calculates the first logo starting from the node according to the total number Ni of the logos to be calculated by each computing node;

Each computing node participating in the calculation serializes the identification vector of the node according to the initial first identification of the node, and obtains the corresponding first identification.

According to another aspect of the present invention, a matrix data element identification continuous system is provided, including:

N computing nodes;

Each computing node involved in computing includes:

The data reading module is suitable for each computing node participating in the computing to read the data elements of the matrix block assigned to the computing node in the matrix data;

The spreading and receiving module is suitable for each computing node participating in the calculation to keep the data identifier in the read data element locally or send it to the corresponding computing node according to the preset data identifier walking rule, and receive the remaining N - a data identifier sent by a computing node, to obtain the final data identifier processed by the computing node;

A serialization module, adapted for each computing node participating in the calculation to perform serialization according to the final data identifier, and obtain a first identifier corresponding to each data identifier;

The notification module is adapted for each computing node participating in the computing to notify other computing nodes of the corresponding relationship between the first identifier and the original data identifier.

Optionally, the data reading module is further adapted to:

Each computing node participating in the calculation reads the data elements in the matrix data that are divided into blocks by rows, or data elements that are divided into blocks by columns.

Optionally, when each computing node participating in the calculation reads the data elements divided by rows in the matrix data, the spreading and receiving module includes:

The column spreading and receiving module is suitable for each computing node participating in the calculation to keep the column identification in the read data element locally or send it to the corresponding computing node according to the column identification spreading rule of the threshold; and receive other N- A column ID sent by a compute node.

Optionally, the serialization module includes:

The first row serialization module is suitable for each computing node participating in the calculation to generate a row identifier vector according to the local row identifier, and to serialize the row identifier vector to obtain the first row identifier corresponding to each row identifier;

The first column serialization module is suitable for each computing node participating in the calculation to deduplicate the local column ID and generate a column ID vector, and serialize the column ID vector to obtain the first column corresponding to each column ID logo.

Optionally, the notification module includes:

The first notification module is adapted for each computing node participating in the calculation to notify other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier.

Optionally, when each computing node participating in the calculation reads the data elements in the matrix data divided by columns, the dispersing and receiving module includes:

The row dispersal and receiving module is suitable for each computing node participating in the calculation to retain the row identifier in the read data element locally or send it to the corresponding computing node according to the row identifier dispersal rule of the threshold; and receive other calculation The row ID sent by the node.

Optionally, the serialization module includes:

The second column continuation module is suitable for each calculation node participating in the calculation to generate a row identification vector according to the local column identification, and perform serialization on the column identification vector to obtain the first column identification corresponding to each column identification;

The second row continuation module is suitable for each computing node participating in the calculation to de-duplicate the local row ID and generate a row ID vector, and perform serialization on the row ID vector to obtain the first row corresponding to each row ID logo.

Optionally, the notification module includes:

The second notification module is adapted for each computing node participating in the calculation to notify other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier.

Optionally, the first column continuation module, the first row continuation module, the second column continuation module, and the second row continuation module include:

A statistics module, suitable for each calculation node i participating in the calculation to count the total number of identifications Ni to be calculated, and notify the other calculation nodes of the total number;

The initial identification calculation module is suitable for each calculation node participating in the calculation to calculate the initial first identification of the node according to the total number of identifications Ni to be calculated by each calculation node;

The vector continuation module is adapted for each computing node participating in the calculation to serialize the identification vector of the node according to the initial first identification of the node to obtain the corresponding first identification. Compared with the prior art, the present invention includes the following advantages:

In the present invention, each computing node participating in the calculation reads the data elements of the corresponding matrix block from the server that stores the matrix data elements, and then sends the data identification in the data element to the corresponding calculation data of this type according to the spreading rules of the data identification. In the identified computing nodes, each computing node that participates in the calculation will generate a data identification vector for each data identification obtained, and continue each component (that is, the data identification) in the data identification vector to obtain the corresponding to each component. Then each computing node participating in the calculation notifies other computing nodes of the corresponding relationship between the locally calculated data ID and the first ID, and then other computing nodes can learn the continuity of the data elements that need to be calculated locally. The first logo after conversion. In this process, for large-scale matrix data, serialization can be carried out in parallel through each computing node, which speeds up the serialization speed and improves the data processing efficiency.

The above description is only an overview of the technical solution of the present invention. In order to better understand the technical means of the present invention, it can be implemented according to the contents of the description, and in order to make the above and other purposes, features and advantages of the present invention more obvious and understandable , the specific embodiments of the present invention are enumerated below.

Description of drawings

Various other advantages and benefits will become apparent to those of ordinary skill in the art upon reading the following detailed description of the preferred embodiment. The drawings are only for the purpose of illustrating a preferred embodiment and are not to be considered as limiting the invention. Also throughout the drawings, the same reference numerals are used to designate the same parts. In the attached picture:

Fig. 1 shows a schematic flow chart of Embodiment 1 of a method for continuous identification of matrix data elements according to an embodiment of the present invention;

Fig. 2 shows a schematic diagram of matrix data storage logic according to an embodiment of the present invention;

Fig. 3 is a schematic flowchart of Embodiment 2 of a method for continuous identification of matrix data elements according to an embodiment of the present invention;

Fig. 4 shows a schematic diagram of a data identification broadcast logic according to an embodiment of the present invention;

Fig. 5 is a schematic flow chart of Embodiment 3 of a method for continuous identification of matrix data elements according to an embodiment of the present invention;

FIG. 6 is a schematic structural diagram of Embodiment 1 of a matrix data element identification serialization system according to an embodiment of the present invention;

Fig. 7 shows a schematic structural diagram of Embodiment 2 of a matrix data element identification serialization system according to an embodiment of the present invention; and

Fig. 8 shows a schematic structural diagram of Embodiment 3 of a matrix data element identification serialization system according to an embodiment of the present invention.

detailed description

Exemplary embodiments of the present disclosure will be described in more detail below with reference to the accompanying drawings. Although exemplary embodiments of the present disclosure are shown in the drawings, it should be understood that the present disclosure may be embodied in various forms and should not be limited to the embodiments set forth herein. Rather, these embodiments are provided for more thorough understanding of the present disclosure and to fully convey the scope of the present disclosure to those skilled in the art.

Referring to Fig. 1, it shows a schematic flow chart of Embodiment 1 of a method for continuous identification of matrix data elements according to the present invention, which may specifically include:

Step 110, for N computing nodes, each computing node participating in the computing reads the data elements of the matrix block assigned to the computing node in the matrix data;

In the embodiment of the present invention, the matrix data is stored in a designated data server, such as log data, and the logical storage method may be in the form of a matrix. As shown in Figure 2, value is the actual data content, such as log data, ColKeyi (i=1, 2...M) is the column label of the corresponding value, and RowKeyi (i=1, 2...N) is the corresponding value row mark. In the sparse matrix, there may be a certain number of non-zero elements (that is, actual data) in each row and column, and a large number of zero elements (zero elements have no data and are not stored).

Then, for N computing nodes (that is, N computing servers) used for computing, it is first necessary to divide the matrix data in Figure 1 into blocks in advance, for example, divide them into N blocks by row (N is less than or equal to the number of rows, generally The number of lower computing nodes is much smaller than the number of rows and columns of the matrix), and then N is assigned to a computing node, and the computing node performs processing.

Then, before the actual calculation, each computing node needs to read the data of the corresponding matrix block according to the pre-specified matrix block. For example, there are currently 10 computing nodes, matrix data of 10,000 rows*10,000 columns, among which the data of the 1st to 1000th row is allocated to the computing node 1, the data of the 1001st to 2000th row is allocated to the computing node 2, ... the 9001st~ 10,000 rows of data are allocated to computing node 10, and then computing nodes 1 to 10 respectively read the corresponding 1,000 rows of data.

Step 120, each computing node participating in the calculation keeps the data identifier in the read data element locally or sends it to the corresponding computing node according to the preset data identifier spreading rule, and receives the remaining N-1 computing nodes The sent data identifier, to obtain the final data identifier processed by the computing node;

In the embodiment of the present invention, in order to serialize (i.e. idize) the data identification of the matrix data in parallel using each computing node, the matrix data of each node can be sent to a certain data identification with the same attribute according to a certain rule. computing nodes for processing. That is to say, each computing node participating in the calculation will calculate the data identifier of each data element currently read according to the preset data identifier distribution rules, and send the data identifier to the calculation corresponding to the calculation result according to the calculation result. node. At the same time, each computing node participating in the calculation also receives the data identification sent by other computing nodes to the node. Then in the end, each computing node participating in the calculation saves the unsent data identifier and the data identifier sent to the node by other computing nodes.

In this way, each computing node participating in the calculation only processes a part of data identifiers, and the data identifiers processed by each computing node are different from each other.

In the embodiment of this application, the communication between computing nodes is carried out through MPI (Message Passing Interface, message passing interface; a message passing programming interface, and a multilingual function library for implementing a series of interfaces is provided at the same time).

That is, each computing node participating in the calculation retains the data identifier in the read data element locally or sends it to the corresponding computing node through MPI according to the preset data identifier spreading rule, and receives the remaining N-1 computing nodes The sent data identifier is used to obtain the final data identifier processed by the computing node.

Step 130, each computing node participating in the calculation performs serialization according to the final data identifier, and obtains a first identifier corresponding to each data identifier;

As mentioned above, each computing node participating in the calculation finally saves the unsent data identifier and the data identifier sent to the node by other computing nodes, then each computing node participating in the calculation performs serialization based on the above-mentioned final data identifier.

Wherein, when performing serialization, each computing node participating in the calculation generates a data identification vector according to the final data identification and performs vector serialization to obtain a first identification corresponding to each data identification.

Step 140, each computing node participating in the calculation notifies other computing nodes of the correspondence between the first identifier and the original data identifier.

Since the serialization of data identification is carried out in the process, and in order to make the processes of other computing nodes know synchronously, it is necessary for each computing node participating in the calculation to convert the corresponding relationship between the data identification obtained by the current id and the first identification Notify other computing nodes so that the entire computing system globally knows the correspondence between the data identifier and the first identifier, so that the subsequent calculation process can make it convenient for each process to store the data of the corresponding matrix block in the memory with the first identifier.

In this step, each computing node participating in the calculation notifies other computing nodes of the corresponding relationship between the first identifier and the original data identifier through MPI.

Referring to FIG. 3 , it shows a schematic flow diagram of Embodiment 2 of a method for continuous identification of matrix data elements according to the present invention, which may specifically include:

Step 210, for the N computing nodes, each computing node participating in the calculation reads the row-blocked data elements in the matrix data.

That is, the matrix data in FIG. 2 is divided into N row blocks by row, and the N row blocks are respectively allocated to a computing node for calculation.

Then each computing node participating in the computing reads the data elements of several rows assigned to the computing node. That is, the computing node reads the matrix elements by row label until the matrix elements of the row labels within its range are completely read.

Step 220, each computing node participating in the calculation keeps the column identifier in the read data element locally or sends it to the corresponding computing node according to the column identifier spreading rule of the threshold; and receives the other N-1 computing nodes sending The column ID for .

In the embodiment of the present invention, firstly, a global column label (Colkey) distribution rule can be defined, and the column label of each data element is distributed to the corresponding computing node, such as the rule:

R→(RANK＝COLKEY%NODES) Formula (1)

The above formula is to take the remainder of ColKey against the total number of computing nodes Nodes, and each type of remainder corresponds to one computing node R. For example, there are a total of 4 computing nodes A, B, C, and D, and the remainder is 0, 1, 2, and 3, then the remainder 0 corresponds to computing node A, the remainder 1 corresponds to computing node B, the remainder 2 corresponds to computing node C, and the remainder 3 may correspond to compute node D.

Then the computing node calculates the currently read matrix elements, that is, (Rowkey, colkey, value), the colkey in it using the formula (1), and sends the colkey to the corresponding computing node according to the correspondence between the calculation result and the computing node . Each computing node participating in the calculation also receives the colkey calculated by other computing nodes according to the formula (1) and then sends it to the node colkey.

Step 230, each computing node participating in the calculation generates a row identifier vector according to the local row identifier, and serializes the row identifier vector to obtain the first row identifier corresponding to each row identifier;

Step 240 , each computing node participating in the calculation deduplicates the local column identifiers to generate a column identifier vector, and serializes the column identifier vector to obtain a first column identifier corresponding to each column identifier.

In step 230', it also includes: merging the same column labels. That is to say, there is only one copy of each colkey.

From steps 230 and 240, after the first communication between computing nodes, each computing node participating in the calculation saves a part of the column key (colkey) and the row key (rowkey) that the node is currently assigned to process the row matrix block . Then you can generate a row vector for the rowkey saved in this node, colkey generates a column vector, and then perform serialization (idization) to obtain the corresponding relationship between the row identifier and the first row identifier (the serialized identifier), and the column identifier and The corresponding relationship of the first column identifier (the serialized identifier), that is, (RowKey->RowId) and (ColKey->ColId).

Among them, for the continuation of row vectors and column vectors, the methods used include:

Step S11, each calculation node i participating in the calculation counts the total number of identifiers N _i to be calculated, and notifies the other calculation nodes of the total number;

Step S12, each computing node participating in the calculation calculates the first identifier starting from the node according to the total number N _i of identifiers to be calculated by each computing node;

Step S13 , each computing node participating in the calculation serializes the identification vector of the node according to the initial first identification of the node, and obtains the corresponding first identification.

Let's take a column vector as an example to illustrate:

1. For N computing nodes, count the number N _i of components in its column vector for each computing node participating in the calculation;

2. Each computing node i calls the MPI_Allgather function to broadcast the number of components N _i of this node to other N-1 computing nodes, and receive the number of components broadcast by other N-1 computing nodes, and obtain each computing node participating in the calculation the number of components computed by i;

3. For each calculation node i participating in the calculation, calculate the starting (first column identification) ID number of this node according to the following formula (2):

$\mathrm{StartID}=\underset{i=0}{\overset{\mathrm{rank}-1}{\mathrm{\Σ}}}{N}_i$ ...Formula (2)

Wherein, N _i is the component number of computing node i, and rank is the serial number of the current computing node (rank can be set to 0...n, where rank=0, StarID=0).

4. Each computing node participating in the calculation idizes each component of the column vector of the node according to the initial ID number of the node.

Of course, in this application, other forms can also be used for the continuous ID of each computing node in the two-dimensional structure form (RowKey->RowId) and (ColKey->ColId), which is limited by the embodiment of the present invention.

Also, optionally, include:

Step S21, setting multiple working threads inside the computing node, and assigning the row components processed by the node to each working thread in turn;

Step S22, using each worker thread to perform connection id processing on the corresponding data.

Optionally, the use of each worker thread to perform connection id processing on the corresponding data includes:

Step S31 For any worker thread,

Determine whether the currently processed data is the last piece of data processed by itself;

If so, end and exit the processing flow;

If not, assign an id to the current data and trigger the processing of the next piece of data.

Optionally, the triggering the processing of the next piece of data includes: performing connection id processing on the next piece of data by using atomic increment atomic_inc.

In the above-mentioned process of idizing components, it is generally divided into row component processing and column component processing, that is, each computing node participating in the calculation obtains the row component data of other computing nodes to calculate the row component, and each When a computing node participating in the calculation calculates the column component, it obtains the column component data of other computing nodes for calculation.

Through the calculation of the above-mentioned components, the data is not sequentially processed in one queue, but processed in parallel in multiple queues, and its processing speed is greatly improved compared with the id-based processing in the prior art. The more nodes processed in parallel, the faster the data will be processed. Adopting the embodiment of the present invention can shorten the time of data storage, especially for large-scale data storage, can save time and increase the storage rate, meet the time requirement of large-scale data storage, and save system resources.

Step 250, each computing node participating in the calculation notifies other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier.

In the embodiment of the present invention, since the row vector processed by each computing node participating in the calculation is the row table of the matrix data that needs to be processed, that is, the matrix data is divided into each computing node participating in the calculation by row, so (RowKey ->RowId) and the local RowKey are in one-to-one correspondence. However, (ColKey->ColId) is not in one-to-one correspondence with the local ColKey, and each row of data may contain all columns, so (ColKey->ColId) needs to be globalized, that is, each computing node participating in the calculation will localize the id The obtained (ColKey->ColId) is broadcast to other N-1 calculation nodes, referring to Figure 4, which is the broadcast of each (ColKey->ColId) of each calculation node participating in the calculation to other calculation nodes in this embodiment A schematic diagram. The (ColKey->ColId) calculated by each computing node participating in the calculation is broadcast to the corresponding colkey of other computing nodes. In this way, for global computing nodes, (ColKey->ColId) calculated by all computing nodes and (RowKey->RowId) of the node itself can be recorded.

Among them, the MPI_Allgather interface of MPI broadcasts the local (ColKey->ColId) to all other computing nodes.

Then, each computing node participating in the calculation can store its value in the memory according to its (RowKey->RowId) and (ColKey->ColId) when calculating the data elements of its row block. It is easy to know the data boundaries.

Referring to FIG. 5 , it shows a schematic flow diagram of Embodiment 2 of a method for continuous identification of matrix data elements according to the present invention, which may specifically include:

Step 310, for the N computing nodes, each computing node participating in the calculation reads the data elements in the matrix data divided by column.

That is, the matrix data in Figure 2 is divided into N row blocks by column, and the N column blocks are respectively assigned to a computing node for calculation. Then each computing node participating in the calculation reads the data elements of several columns assigned to the computing node.

Step 320 , each computing node participating in the calculation saves the row ID in the read data element locally or sends it to the corresponding computing node according to the row ID spreading rule of the threshold; and receives the row ID sent by other computing nodes.

In the embodiment of the present invention, firstly, a global column label (Colkey) distribution rule can be defined, and the column label of each data element is distributed to the corresponding computing node, such as the rule:

R→(RANK＝ROWKEY%NODES) formula (3)

Then the computing node calculates the currently read matrix elements, that is, (Rowkey, colkey, value), the rowkey in it using the formula (3), and sends the rowkey to the corresponding computing node according to the corresponding relationship between the calculation result and the computing node . Each computing node participating in the calculation also receives the rowkey calculated by other computing nodes according to the formula (3) and then sends the rowkey to this node.

Step 330, each computing node participating in the calculation generates a row identifier vector according to the local column identifier, and serializes the column identifier vector to obtain a first column identifier corresponding to each column identifier;

Step 340 , each computing node participating in the calculation deduplicates the local row IDs to generate a row ID vector, and serializes the row ID vectors to obtain the first row ID corresponding to each row ID.

In step 330', it also includes: merging the same row labels. That is, it is guaranteed that each rowkey has only one copy.

After the first communication, in steps 320 and 330, each computing node participating in the calculation saves a part of the row key (rowkey) and the column key (colkey) of the node currently assigned to process the row matrix block. Then you can generate a row vector for the rowkey saved in this node, colkey generates a column vector, and then perform serialization (idization) to obtain the corresponding relationship between the row identifier and the first row identifier (the serialized identifier), and the column identifier and The corresponding relationship of the first column identifier (the serialized identifier), that is, (RowKey->RowId) and (ColKey->ColId).

It can also be calculated using steps S11 to S13 and formula (2).

Step 350, each computing node participating in the calculation notifies other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier.

In this embodiment (colKey->colId) is in one-to-one correspondence with the local colKey. However, (rowKey->ColId) and the local rowKey are not one-to-one correspondence, and each row of data may contain all columns, so (rowKey->rowId) needs to be globalized, that is, each computing node participating in the calculation will localize the id The obtained (rowKey->rowId) is broadcast to other N-1 calculation sections.

The basic principle of this embodiment is similar to that of the second embodiment, and will not be described in detail here.

Referring to Fig. 6, it shows a schematic structural diagram of Embodiment 1 of a matrix data element identification serialization system according to the present invention, including:

N computing nodes;

Each computing node 400 participating in computing includes:

The data reading module 410 is adapted for each computing node participating in the computing to read the data elements of the matrix block assigned to the computing node in the matrix data;

The spreading and receiving module 420 is adapted to keep the data identification in the read data element locally or send it to the corresponding computing node according to the preset data identification spreading rules for each computing node participating in the calculation, and receive the remaining N - a data identifier sent by a computing node, to obtain the final data identifier processed by the computing node;

The serialization module 430 is adapted to serialize each computing node participating in the calculation according to the final data identifier, and obtain a first identifier corresponding to each data identifier;

The notification module 440 is adapted for each computing node participating in computing to notify other computing nodes of the correspondence between the first identifier and the original data identifier.

Optionally, the data reading module is further adapted to:

Each computing node participating in the calculation reads the data elements in the matrix data that are divided into blocks by rows, or data elements that are divided into blocks by columns.

Optionally, when each computing node participating in the calculation reads the data elements divided by rows in the matrix data, the spreading and receiving module includes:

The column spreading and receiving module is suitable for each computing node participating in the calculation to keep the column identification in the read data element locally or send it to the corresponding computing node according to the column identification spreading rule of the threshold; and receive other N- A column ID sent by a compute node.

Optionally, the serialization module includes:

The first row serialization module is suitable for each computing node participating in the calculation to generate a row identifier vector according to the local row identifier, and serialize the row identifier vector to obtain the first row identifier corresponding to each row identifier;

The first column serialization module is suitable for each computing node participating in the calculation to deduplicate the local column ID and generate a column ID vector, and serialize the column ID vector to obtain the first column corresponding to each column ID logo.

Optionally, the notification module includes:

The first notification module is adapted for each computing node participating in the calculation to notify other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier.

Optionally, when each computing node participating in the calculation reads the data elements in the matrix data divided by columns, the dispersing and receiving module includes:

The row spreading and receiving module is suitable for each computing node participating in the calculation to keep the row identifier in the read data element locally or send it to the corresponding computing node according to the row identifier spreading rule of the threshold; and receive other computing nodes The row ID sent.

Optionally, the serialization module includes:

The second column continuation module is suitable for each calculation node participating in the calculation to generate a row identification vector according to the local column identification, and perform serialization on the column identification vector to obtain the first column identification corresponding to each column identification;

The second row continuation module is suitable for each computing node participating in the calculation to de-duplicate the local row ID and generate a row ID vector, and perform serialization on the row ID vector to obtain the first row corresponding to each row ID logo.

Optionally, the notification module includes:

The second notification module is adapted for each computing node participating in the calculation to notify other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier.

Optionally, the first column continuation module, the first row continuation module, the second column continuation module, and the second row continuation module include:

A statistics module, suitable for each calculation node i participating in the calculation to count the total number of identifications Ni to be calculated, and notify the other calculation nodes of the total number;

The initial identification calculation module is suitable for each calculation node participating in the calculation to calculate the initial first identification of the node according to the total number of identifications Ni to be calculated by each calculation node;

The vector continuation module is adapted for each computing node participating in the calculation to serialize the identification vector of the node according to the initial first identification of the node to obtain the corresponding first identification.

Referring to Fig. 7, it shows a schematic structural diagram of Embodiment 2 of a matrix data element identification serialization system according to the present invention, including:

N computing nodes;

Each computing node 500 participating in computing includes:

Data reading module 510, each computing node participating in the calculation reads the data elements in the matrix data divided by rows;

The column spreading and receiving module 520 is adapted to keep the column identification in the read data element locally or send it to the corresponding computing node according to the column identification spreading rule of the threshold for each computing node participating in the calculation; and receive other N - 1 column identifier sent by the compute node;

The first row serialization module 530 is adapted for each computing node participating in the calculation to generate a row identifier vector according to the local row identifier, and serialize the row identifier vector to obtain the first row identifier corresponding to each row identifier;

The first column serialization module 540 is adapted for each computing node participating in the calculation to deduplicate the local column ID and generate a column ID vector, and to serialize the column ID vector to obtain the first column ID corresponding to each column ID. Column ID.

The first notification module 550 is adapted for each computing node participating in the calculation to notify other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier.

Referring to Fig. 8, it shows a schematic structural diagram of Embodiment 2 of a matrix data element identification serialization system according to the present invention, including:

N computing nodes;

Each computing node 600 participating in computing includes:

Data reading module 610, each computing node participating in the calculation reads the data elements in the matrix data divided into columns;

Row spreading and receiving module 620, adapted to each computing node participating in the calculation according to the row identifier spreading rule of the threshold, keeping the row identifier in the read data element locally or sending it to the corresponding computing node; and receiving other calculation The row ID sent by the node.

The second column continuation module 630 is suitable for each computing node participating in the calculation to generate a row identification vector according to the local column identification, and to perform serialization on the column identification vector to obtain the first column identification corresponding to each column identification;

The second row continuation module 640 is suitable for each computing node participating in the calculation to de-duplicate the local row ID and generate a row ID vector, and perform serialization on the row ID vector to obtain the first row ID corresponding to each row ID Row ID.

The second notification module 650 is adapted for each computing node participating in the calculation to notify other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier.

The algorithms and displays presented herein are not inherently related to any particular computer, virtual system, or other device. Various generic systems can also be used with the teachings based on this. The structure required to construct such a system is apparent from the above description. Furthermore, the present invention is not specific to any particular programming language. It should be understood that various programming languages can be used to implement the content of the present invention described herein, and the above description of specific languages is for disclosing the best mode of the present invention.

In the description provided herein, numerous specific details are set forth. However, it is understood that embodiments of the invention may be practiced without these specific details. In some instances, well-known methods, structures and techniques have not been shown in detail in order not to obscure the understanding of this description.

Similarly, it should be appreciated that in the foregoing description of exemplary embodiments of the invention, in order to streamline this disclosure and to facilitate an understanding of one or more of the various inventive aspects, various features of the invention are sometimes grouped together in a single embodiment, figure, or its description. This method of disclosure, however, is not to be interpreted as reflecting an intention that the claimed invention requires more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive aspects lie in less than all features of a single foregoing disclosed embodiment. Thus, the claims following the Detailed Description are hereby expressly incorporated into this Detailed Description, with each claim standing on its own as a separate embodiment of this invention.

Those skilled in the art can understand that the modules in the device in the embodiment can be adaptively changed and arranged in one or more devices different from the embodiment. Modules or units or components in the embodiments may be combined into one module or unit or component, and furthermore may be divided into a plurality of submodules or subunits or subassemblies. All features disclosed in this specification (including accompanying claims, abstract and drawings) and any method or method so disclosed may be used in any combination, except that at least some of such features and/or processes or units are mutually exclusive. All processes or units of equipment are combined. Each feature disclosed in this specification (including accompanying claims, abstract and drawings) may be replaced by alternative features serving the same, equivalent or similar purpose, unless expressly stated otherwise.

Furthermore, those skilled in the art will understand that although some embodiments described herein include some features included in other embodiments but not others, combinations of features from different embodiments are meant to be within the scope of the invention. and form different embodiments. For example, in the following claims, any of the claimed embodiments may be used in any combination.

The various component embodiments of the present invention may be implemented in hardware, or in software modules running on one or more processors, or in a combination thereof. Those skilled in the art should understand that a microprocessor or a digital signal processor (DSP) can be used in practice to implement a matrix data element identification serialization device according to an embodiment of the present invention. Full functionality. The present invention can also be implemented as an apparatus or an apparatus program (for example, a computer program and a computer program product) for performing a part or all of the methods described herein. Such a program for realizing the present invention may be stored on a computer-readable medium, or may be in the form of one or more signals. Such a signal may be downloaded from an Internet site, or provided on a carrier signal, or provided in any other form.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word "comprising" does not exclude the presence of elements or steps not listed in a claim. The word "a" or "an" preceding an element does not exclude the presence of a plurality of such elements. The invention can be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In a unit claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The use of the words first, second, and third, etc. does not indicate any order. These words can be interpreted as names.

Claims (18)

1. A matrix data element identification continuous method, is characterized in that, comprises: For N computing nodes, each computing node participating in the calculation reads the data elements of the matrix block assigned to the computing node in the matrix data; Each computing node participating in the calculation keeps the data identifier in the read data element locally or sends it to the corresponding computing node according to the preset data identifier spreading rule, and receives the data sent by the remaining N-1 computing nodes identification, obtaining the final data identification processed by the computing node; Each computing node participating in the calculation performs serialization according to the final data identifier, and obtains a first identifier corresponding to each data identifier; Each computing node participating in the calculation notifies other computing nodes of the correspondence between the first identifier and the original data identifier. 2. The method according to claim 1, wherein the data elements of the matrix block assigned to the computing node in the matrix data read by each computing node participating in the computing include: Each computing node participating in the calculation reads the data elements in the matrix data that are divided into blocks by rows, or data elements that are divided into blocks by columns. 3. The method according to claim 2, wherein each computing node participating in the calculation keeps the data identifier in the read data element locally or sends it to The corresponding computing nodes include: Each computing node participating in the calculation keeps the column identifier in the read data element locally or sends it to the corresponding computing node according to the column identifier spreading rule of the threshold; and receives the column identifier sent by other N-1 computing nodes . 4. The method according to claim 3, wherein each computing node participating in the calculation is serialized according to the final data identifier, and obtaining the first identifier corresponding to each data identifier comprises: Each computing node participating in the calculation generates a row identifier vector according to the local row identifier, and serializes the row identifier vector to obtain the first row identifier corresponding to each row identifier; Each computing node participating in the calculation deduplicates the local column identifiers to generate column identifier vectors, and serializes the column identifier vectors to obtain the first column identifier corresponding to each column identifier. 5. The method according to claim 4, wherein said each computing node participating in the calculation notifies other computing nodes of the correspondence between the first identifier and the original data identifier comprising: Each computing node participating in the calculation notifies other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier. 6. The method according to claim 2, wherein each computing node participating in the calculation keeps the data identifier in the read data element locally or sends it to The corresponding computing nodes include: Each computing node participating in the calculation keeps the row ID in the read data element locally or sends it to the corresponding computing node according to the row ID spreading rule of the threshold; and receives the row ID sent by other computing nodes. 7. The method according to claim 6, wherein each computing node participating in the calculation is serialized according to the final data identifier, and obtaining the first identifier corresponding to each data identifier comprises: Each computing node participating in the calculation generates a row identification vector according to the local column identification, and serializes the column identification vector to obtain the first column identification corresponding to each column identification; Each computing node participating in the calculation deduplicates the local row ID to generate a row ID vector, and serializes the row ID vector to obtain the first row ID corresponding to each row ID. 8. The method according to claim 7, wherein said each computing node participating in the calculation notifies other computing nodes of the correspondence between the first identifier and the original data identifier comprising: Each computing node participating in the calculation notifies other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier. 9. The method according to claim 4 or 7, wherein said continuous vector comprises: Each calculation node i participating in the calculation counts the total number of identifiers Ni to be calculated, and notifies the other calculation nodes of the total number; Each computing node participating in the calculation calculates the first logo starting from the node according to the total number Ni of the logos to be calculated by each computing node; Each computing node participating in the calculation serializes the identification vector of the node according to the initial first identification of the node, and obtains the corresponding first identification. 10. A continuous matrix data element identification system, characterized in that it comprises: N computing nodes; Each computing node involved in computing includes: The data reading module is suitable for each computing node participating in the computing to read the data elements of the matrix block assigned to the computing node in the matrix data; The spreading and receiving module is suitable for each computing node participating in the calculation to retain the data identifier in the read data element locally or send it to the corresponding computing node according to the preset data identifier spreading rule, and receive the remaining N- A data identifier sent by a computing node to obtain a final data identifier processed by the computing node; A serialization module, adapted for each computing node participating in the calculation to perform serialization according to the final data identifier, and obtain a first identifier corresponding to each data identifier; The notification module is adapted for each computing node participating in the computing to notify other computing nodes of the corresponding relationship between the first identifier and the original data identifier. 11. The system according to claim 10, wherein the data reading module is further adapted to: Each computing node participating in the calculation reads the data elements in the matrix data that are divided into blocks by rows, or data elements that are divided into blocks by columns. 12. The system of claim 11, wherein: When each computing node participating in the calculation reads the data elements divided by rows in the matrix data, the spreading and receiving module includes: The column spreading and receiving module is suitable for each computing node participating in the calculation to keep the column identification in the read data element locally or send it to the corresponding computing node according to the column identification spreading rule of the threshold; and receive other N- A column identifier sent by a compute node. 13. The system according to claim 12, wherein the serialization module comprises: The first row serialization module is suitable for each computing node participating in the calculation to generate a row identifier vector according to the local row identifier, and to serialize the row identifier vector to obtain the first row identifier corresponding to each row identifier; The first column serialization module is suitable for each computing node participating in the calculation to deduplicate the local column ID and generate a column ID vector, and serialize the column ID vector to obtain the first column corresponding to each column ID logo. 14. The system according to claim 13, wherein the notification module comprises: The first notification module is adapted for each computing node participating in the calculation to notify other computing nodes of the first column identifier according to the corresponding relationship between the first column identifier and the original column identifier. 15. The system of claim 11, wherein: When each calculation node participating in the calculation reads the data elements in the matrix data divided by columns, the spreading and receiving module includes: The row spreading and receiving module is suitable for each computing node participating in the calculation to keep the row identifier in the read data element locally or send it to the corresponding computing node according to the row identifier spreading rule of the threshold; and receive other computing nodes The row ID sent. 16. The system according to claim 15, wherein the serialization module comprises: The second column continuation module is suitable for each calculation node participating in the calculation to generate a row identification vector according to the local column identification, and perform serialization on the column identification vector to obtain the first column identification corresponding to each column identification; The second row continuation module is suitable for each computing node participating in the calculation to de-duplicate the local row ID and generate a row ID vector, and perform serialization on the row ID vector to obtain the first row corresponding to each row ID logo. 17. The system according to claim 16, wherein the notification module comprises: The second notification module is adapted for each computing node participating in the calculation to notify other computing nodes of the first row identifier according to the corresponding relationship between the first row identifier and the original row identifier. 18. The system according to claim 14 or 16, wherein the first column continuation module, the first row continuation module, the second column continuation module, and the second row continuation module include: A statistics module, suitable for each calculation node i participating in the calculation to count the total number of identifications Ni to be calculated, and notify the other calculation nodes of the total number; The initial identification calculation module is suitable for each calculation node participating in the calculation to calculate the initial first identification of the node according to the total number of identifications Ni to be calculated by each calculation node; The vector continuation module is adapted for each computing node participating in the calculation to serialize the identification vector of the node according to the initial first identification of the node to obtain the corresponding first identification.