JP2016066329A - Information processing device, information processing method, and computer program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently arrange elements contained in a matrix having one or more blocks, to a storage device.SOLUTION: An information processing device 2000 includes: a storage unit 2001 capable of storing at least data; and an arrangement unit 2002 arranging in a region continued to the storage unit 2001, data indicating elements arranged at the same position in a second matrix, for the second matrix to be at least one block contained in a first matrix.SELECTED DRAWING: Figure 20

Description

  The present invention relates to an information processing apparatus, an information processing method, and the like. In particular, the present invention relates to an information processing apparatus and the like that can efficiently arrange data represented by elements included in a matrix in a storage device.

  In recent years, a method of arranging (storing) element information (data represented by elements included in a matrix) of a large-scale matrix as an array in a storage device has been used in the fields of various numerical calculations. Hereinafter, data representing a specific matrix (data represented by all elements included in the specific matrix) may be simply referred to as “matrix data”.

  As such a technique, for example, a JDS (Jagged Diagonal Storage) storage method (see Patent Document 1 below), a CRS (Compressed Row Storage) storage method, and the like are known.

  Here, the JDS storage method will be described with reference to FIG. FIG. 1 illustrates a procedure for storing matrix data of a sparse matrix (reference numeral 100a in FIG. 1) in a storage device using the JDS storage method. In FIG. 1, row numbers (1 to 8) are assigned in the vertical direction (row direction) of the sparse matrix 100a. Also, column numbers (1 to 8) are assigned in the horizontal direction (column direction) of the sparse matrix 100a.

  In the sparse matrix 100a illustrated in FIG. 1A, a non-zero (zero) element is arranged at a position where “*” is arranged. In the sparse matrix 100a illustrated in FIG. 1A, a zero element is arranged at a place where a blank is set.

  First, in the JDS storage method, as illustrated in FIG. 1B, only non-zero elements in the sparse matrix 100a are packed in the left direction (column direction left end side). The left-justified sparse matrix is 100b.

  Next, in the JDS storage method, as illustrated in FIG. 1C, the row numbers of the respective rows in the left-justified sparse matrix 100b are rearranged in descending order of the number of non-zero elements included in the row. . The rearranged sparse matrix is defined as 100c.

  In the JDS storage method, as illustrated in FIG. 1D, the column number of each non-zero element included in the original sparse matrix 100a is stored in another array (two-dimensional array) 100d. That is, by referring to the column number stored in each element of the array 100d, it is possible to specify in which column each element included in the row to which the specific row number is allocated was present in the original sparse matrix 100a. It is.

  For example, as a specific example, the row with the row number “3” of the sparse matrix 100c will be described. In the original sparse matrix 100a, the row corresponding to the row number “3” includes the first column, the second column, the third column, the fifth column, the seventh column, and the eighth column. Has a non-zero element. Therefore, “1, 2, 3, 5, 7, 8” is set as data representing the column number in the row corresponding to the row number “3” in the array 100d.

  In the JDS storage method, the matrix data of the matrix 100c and the array 100d are respectively sequentially from the first column along the direction of the arrow DA1 (the direction from the top to the bottom in the row direction) illustrated in FIG. That is, the data are stored one-dimensionally in the storage device in order from the first column to the eighth column).

  When calculating the product of the matrix and the vector stored by the JDS storage method, the matrix data of the matrix 100c and the array storing the column number 101d are referred to in the order of the arrow DA1 shown in FIG. , Used to calculate the product.

  The following patent documents are disclosed as techniques related to such matrix operations.

  As described above, Patent Document 1 discloses a method for storing a scale irregular sparse matrix using a JDS storage method in a storage device constituting a computer.

  Patent Document 2 (Japanese Patent Application Laid-Open No. 2008-070928) discloses a calculation method for controlling so that an area for storing a coefficient matrix is held in a main memory without being paged out when a solution of simultaneous linear equations is obtained by numerical calculation. Is disclosed. The technique disclosed in Patent Document 2 retains a part of decomposed coefficient values in the main memory within a range not exceeding the free space of the main memory in the triangular decomposition operation of the coefficient matrix based on the modified Cholesky decomposition method. The technique disclosed in Patent Document 2 holds the remainder of the decomposed coefficient value in the secondary storage. The technique disclosed in Patent Document 2 compresses the coefficient matrix using the skyline method in order to reduce the memory area for storing the coefficient matrix.

  Japanese Patent Application Laid-Open No. 2002-157237 discloses a calculation method for obtaining a solution of simultaneous linear equations using an iterative method. In the technique disclosed in Patent Document 3, when an approximate solution of simultaneous linear equations is calculated using an iterative method, a multilevel incomplete block decomposition is applied to a coefficient matrix that is not an M matrix so as to accelerate the convergence of the calculation. Pre-processing using Note that the technique disclosed in Patent Document 3 stores a coefficient matrix of simultaneous linear equations after compressing the coefficient matrix in an Elpack format.

Japanese Patent Publication No. 06-0666069 JP 2008-070928 A JP 2002-157237 A

  In various numerical calculations, a matrix that can be divided into one or more blocks may be a target of calculation. Hereinafter, the “matrix that can be divided into one or more blocks” may be expressed as “matrix having one or more blocks”. In addition, such a block may be expressed as a “small matrix”.

  When a sparse matrix having one or more blocks (hereinafter sometimes referred to as “block sparse matrix”) is a target of various calculations, it is necessary to efficiently arrange (store) the matrix data of the block sparse matrix in a storage device. is there. More specifically, it is necessary to efficiently arrange (store) the elements (data represented by the elements) included in the block sparse matrix in the storage device.

  In addition, when various arithmetic processes are repeatedly executed in units of blocks included in the block sparse matrix, access (reference) to the storage device occurs in units of such blocks. For example, in a numerical calculation in which the integration of a large-scale sparse matrix and a vector occupies the main calculation cost, various arithmetic processes may be repeatedly executed in units of blocks included in the block sparse matrix.

  In order to improve the efficiency (processing speed, etc.) of arithmetic processing in various numerical calculations, it is desirable that the block sparse matrix data stored in the storage device can be efficiently accessed. That is, a block sparse matrix storage technique that enables efficient access to block sparse matrix data stored in a storage device is required.

  As described above, the storage technology for storing the block sparse matrix requires high capacity efficiency and calculation efficiency.

  The techniques disclosed in Patent Document 2 and Patent Document 3 only disclose techniques specialized for solving specific simultaneous equations, and increase the efficiency (speeding up) of operations related to block sparse matrices. It is not a directly related technology. The same applies to the coefficient matrix storage methods disclosed in the respective documents.

  The present invention has been made in view of the above circumstances.

  An object of the present invention is to provide an information processing apparatus and the like that can efficiently arrange (store) elements included in a matrix having one or more blocks in a storage device. More specifically, the present invention provides an information processing apparatus and the like that can arrange elements included in a matrix having one or more blocks in a storage device using a matrix storage method with high capacity efficiency and calculation efficiency. Is the main purpose.

  In order to achieve the above object, an information processing apparatus according to an aspect of the present invention includes the following arrangement. That is, the information processing device according to one embodiment of the present invention includes each of the second matrix with respect to at least a storage unit capable of storing data and a second matrix that is a block included in the first matrix. And an arrangement unit that arranges data representing elements arranged at the same position in a continuous area in the storage unit.

  An information processing method according to one embodiment of the present invention includes the following configuration. That is, in an information processing method according to one embodiment of the present invention, an information processing device including a storage unit capable of storing data is used for each of the above-described second matrices, which are blocks included in the first matrix. Data representing elements arranged at the same position in the second matrix is arranged in a continuous area in the storage unit.

  In addition, the same object is achieved by an information processing apparatus having the above-described configuration and a corresponding information processing method by a computer program realized by a computer, a computer-readable storage medium storing the computer program, and the like. Is also achieved.

  According to the present invention, elements included in a matrix having one or more blocks can be efficiently arranged (stored) in a storage device. More specifically, according to the present invention, there is provided an information processing apparatus and the like that can arrange elements included in a matrix having one or more blocks in a storage device using a matrix storage method with high capacity efficiency and calculation efficiency. Is possible.

FIG. 1 is a diagram illustrating a procedure for storing matrix data using the JDS storage method. FIG. 2 is a diagram illustrating a specific example of matrix data having one or more blocks. FIG. 3 is a diagram (1/3) illustrating a procedure for storing matrix data of a matrix having one or more blocks using the JDS storage method. FIG. 4 is a diagram (2/3) illustrating a procedure for storing matrix data of a matrix having one or more blocks using the JDS storage method. FIG. 5 is a diagram (3/3) illustrating a procedure for storing matrix data of a matrix having one or more blocks using the JDS storage method. FIG. 6 is a diagram illustrating a specific example of source code for implementing integration processing between a matrix stored using the JDS storage method and an arbitrary vector. FIG. 7 is a diagram illustrating a functional configuration of the information processing apparatus according to the first embodiment of this invention. FIG. 8 is a diagram illustrating a specific example of matrix data having one or more blocks. FIG. 9 is a diagram (1/3) illustrating a procedure for storing matrix data of a matrix having one or more blocks using the matrix storage method according to the first embodiment of the present invention. FIG. 10 is a diagram (2/3) illustrating a procedure for storing matrix data of one or more blocks by using the matrix storage method according to the first embodiment of this invention. FIG. 11 is a diagram (3/3) illustrating a procedure for storing matrix data of a matrix having one or more blocks using the matrix storage method according to the first embodiment of this invention. FIG. 12 is a flowchart illustrating the operation of the information processing apparatus according to the first embodiment of this invention. FIG. 13 is a diagram illustrating a specific example of source code that implements integration processing between a matrix stored using the matrix storage method according to the first embodiment of the present invention and an arbitrary vector. FIG. 14 is a flowchart illustrating the process of integration between a matrix stored using the matrix storage method and an arbitrary vector according to the first embodiment of the present invention. FIG. 15 shows the process when the integration process between the matrix stored using the matrix storage method and the arbitrary vector in the first embodiment of the present invention is optimized for a specific computer architecture. FIG. FIG. 16 is a diagram illustrating a procedure for storing matrix data of a matrix having one or more blocks using the CRS storage method. FIG. 17 is a diagram illustrating a procedure for storing matrix data of a matrix having one or more blocks using the matrix storage method according to the first embodiment of the present invention. FIG. 18 is a diagram illustrating a procedure for storing matrix data of a matrix having one or more blocks using an ELL (Ellpack) storage method. FIG. 19 is a diagram illustrating a procedure for storing matrix data of a matrix having one or more blocks using the matrix storage method according to the first embodiment of the present invention. FIG. 20 is a diagram illustrating a functional configuration of the information processing apparatus according to the first embodiment of this invention. FIG. 21 is a block diagram illustrating a hardware configuration capable of realizing the information processing apparatus according to each embodiment of the present invention.

  Next, embodiments of the present invention will be described in detail with reference to the drawings. The configurations described in the following embodiments are merely examples, and the technical scope of the present invention is not limited thereto.

  The information processing apparatus described in each embodiment uses an apparatus (a physical computer, a virtual computer, or the like) in which one or more components of the information processing apparatus are physically or logically separated. It may be configured as a realized system.

  In addition, the information processing apparatus described in each embodiment is configured as a system in which all the components of the information processing apparatus are realized by using a single device (such as a physical computer or a virtual computer). Also good.

  Prior to the description of each embodiment of the present invention, a technical background related to the present invention will be described.

  First, a configuration in which the JDS storage method is simply extended to correspond to a block sparse matrix will be described with reference to FIGS. The extended JDS storage method does not have the row numbers and column numbers of all the non-zero elements included in the sparse matrix as a reference table, but only the row numbers or column numbers of the block positions included in the sparse matrix. Hold as.

  FIG. 2 is a diagram showing a sparse matrix when each non-zero element (“*” in FIG. 1) of the JDS storage method is a block (small matrix). That is, the matrix 200 illustrated in FIG. 2 illustrates a sparse matrix having a (2 × 2) block (a 2 × 2 small matrix). As illustrated in FIG. 2, the matrix 200 is a (16 × 16) square matrix.

  In FIG. 2, row numbers (block row numbers) are assigned in units of blocks in the vertical direction (row direction) of the sparse matrix 200. A column number (block column number) is assigned in block units in the horizontal direction (column direction) of the sparse matrix 100. In the sparse matrix 200 illustrated in FIG. 2, 1 to 8 are assigned as block row numbers and 1 to 8 are assigned as block column numbers.

  In addition, each element of the (2 rows × 2 columns) type block is represented by using symbols “* 1”, “* 2”, “* 3”, and “* 4”. Such a code simply represents an arrangement position of an element in a (2 × 2) block, and does not represent specific data (value). Arbitrary data (value) can be set in each element of the (2 rows × 2 columns) type block. As in FIG. 1, the blank element in the sparse matrix 200 is a zero element.

  Similar to FIG. 1B, the blocks 300 included in the sparse matrix 200 are packed in the left direction (the region on the left end side in the column direction) to obtain the matrix 300 illustrated in FIG. 3. Note that the matrix 300 may be a modified version of the matrix 200.

  Similar to FIG. 1C, the matrix 400 illustrated in FIG. 4 is rearranged in the descending order of the number of non-zero blocks included in each block row in the matrix 300 illustrated in FIG. can get. Note that the matrix 400 may be a modified version of the matrix 300 (or the matrix 200). A non-zero block is a small matrix that is not at least a zero matrix.

  When the JDS storage method illustrated in FIG. 1 is simply expanded, the elements in each block included in the matrix 400 are stored in the storage device by the arrangement illustrated in FIG. That is, the elements in each block are stored in continuous address areas in the storage device.

  As a specific example, the elements included in the block (block row number: 3, block row number: 1) are consecutive in the storage device in the order of “* 1” “* 2” “* 3” “* 4”. Stored in the address area. Each address included in the block of (block row number: 1, block row number: 1) is in the next address region continuous to the address region in which the block of (block row number: 3, block row number: 1) is stored. Elements are stored in consecutive address areas as described above.

  For example, when calculating the product of a block sparse matrix and a vector, it is necessary to execute an operation loop in units of blocks included in the block sparse matrix. When the JDS storage method is simply extended, when an arithmetic process for a next block is executed from an arithmetic process for a certain block, elements separated by the size of the block are referred to. That is, elements that are not arranged in a continuous area in the storage device are referred to. For this reason, a loss (loss) occurs in calculation speed performance (computation efficiency) as compared with the case of accessing a continuous area in the storage device. Hereinafter, description will be made using a specific mounting example illustrated in FIG.

  FIG. 6 shows a sparse matrix stored by a method simply expanded from the above-described JDS storage method when the block matrix size is 2 (that is, a (2 × 2) type block), and an arbitrary A part of the source code of a Fortran program (computer program) that calculates a product of a vector with Fortran is a well-known programming language.

In the source code illustrated in FIG. 6, the contents represented by each variable and array are as follows. That is,
The variable “N” represents the number of blocks in the row or column direction of the original matrix (for example, the matrix 200 in FIG. 2).

    The variable “NZ” represents the number of all non-zero blocks included in the original matrix.

    The array “A” represents an array that stores the values of non-zero elements in the original matrix. For the subscript of the array “A”, for example, the original matrix is transformed into a matrix 500 illustrated in FIG. 5, and the number (index) is changed to one dimension from the top to the bottom in the row direction in order from the first column. This number is shown when it is attached.

    The array “X” represents a vector (X) to be calculated.

    The array “Y” represents an array that stores the calculation result of the product of the array “A” and the array “X”.

    The array “IA” stores the top number of each block column when the original matrix A is transformed as the matrix 500 illustrated in FIG.

    The array “JA” stores block column numbers of non-zero blocks included in the original matrix. The block row number of the Kth block is JA (K).

    The variable “MJAD” represents the maximum value of the number of non-zero blocks included in each row of the original matrix.

    The array “W” represents a work array that temporarily stores the product of the array “A” and the array “X”.

    The array IORD represents an array storing block row numbers when the original matrix is rearranged as exemplified in FIG. That is, when the block row number in the original array is “I”, the rearranged block row number is IORD (I).

  In the code illustrated in FIG. 6, when the subscript K of the 20th DO loop which is the innermost operation loop is increased by 1, the subscript KI of the array A storing the non-zero elements of the original matrix is 4 (= 2 × 2 , “X” represents a multiplication symbol, and so on. Therefore, when the block size is M (in the case of (M rows and M columns)), in the operation loop processed for each block, the addresses of the array shifted (distant) by M × M elements are repeated. Referenced. In this case, since non-consecutive addresses in the storage device are referred to (accessed), a loss (loss) occurs in calculation speed performance (calculation efficiency) compared to the case of accessing consecutive addresses.

  The information processing apparatus in each embodiment described below stores, in a storage device, continuous areas (addresses) of elements having the same position arranged in each block included in a matrix to be calculated. Thereby, when calculating a product of a sparse matrix having a block and a vector, data (array data storing non-zero elements of the sparse matrix) referred to in an operation loop executed for each block is stored in a storage device. Are arranged in a continuous area (address).

  In the following, elements having the same arrangement position in a block included in a matrix to be calculated may be expressed as “elements having the same relative position in a block”.

  Hereinafter, each embodiment of the present invention will be described.

<First Embodiment>
A first embodiment of the present invention will be described. In the following, a matrix storage method for storing an irregular sparse matrix (sparse matrix) having one or more blocks (small matrix) in an array will be described. A processing procedure for calculating the product of a matrix stored using the matrix storage method and an arbitrary vector will be described.

  First, the configuration of the information processing apparatus 700 in this embodiment will be described with reference to FIG. FIG. 7 is a block diagram illustrating a functional configuration of the information processing apparatus 700 according to this embodiment.

  The information processing measure 700 in this embodiment includes a storage unit 701 and an arrangement unit 702. Further, the information processing apparatus 700 in the present embodiment may include an arithmetic processing unit 703 and an input unit 704. These components constituting the information processing apparatus 700 may be communicably connected by any communication means. The information processing apparatus 700 may be configured with a physical computer or the like, or may be configured with a virtual computer or the like provided using a well-known virtualization technology.

The storage unit 701 provides a storage area in which various information (data) and programs (computer programs) can be stored (stored). By using identification information (for example, an address or an index (index) or the like) that can specify the position in the storage area provided by the storage unit 701, any area in the storage area may be accessible.
The storage unit 701 may be a storage device such as a physical semiconductor memory (for example, SDRAM (Synchronous Dynamic Random Access Memory) provided in the form of DIMM (Dual Inline Memory Module), for example). The storage unit 701 may be a virtual storage device provided in a virtual environment.

  The storage unit 701 holds (stores) matrix data of a matrix arranged by the arrangement unit 701 described later. The storage unit 701 provides the stored matrix data to the arithmetic processing unit 703 described later.

  Arrangement unit 701 stores matrix data of a matrix to be calculated (hereinafter may be referred to as “calculation target matrix”) in an appropriate data structure, and arranges (stores) it in storage unit 701. The placement unit 701 may be communicably connected to an input unit 704 described later, and may receive a calculation target matrix via the input unit 704.

  The arithmetic processing unit 703 executes various arithmetic processes using the matrix data stored in the storage unit 701. In a specific example described later, the arithmetic processing unit 703 performs integration between the calculation target matrix and an arbitrary vector. Note that the arithmetic processing unit 703 may receive data (for example, data representing a vector to be calculated) necessary for various calculations from an input unit 704 described later.

  The input unit 704 receives various data input to the information processing apparatus 700. The input unit 704 may accept input of the various data via various input / output devices (keyboard, mouse, display) and the like, for example. Further, the input unit 704 may accept input of the various data via an arbitrary communication network.

  Next, the operation of the information processing apparatus 700 configured as described above will be described.

  First, the procedure for storing the calculation target matrix in the storage unit 701 in the information processing apparatus 700 will be described with reference to FIGS. 8 to 12. In the specific example described below, it is assumed that the calculation target matrix is a sparse matrix having one or more blocks. The calculation target matrix may be an irregular sparse matrix.

  8 to 11 are diagrams illustrating a process of changing the matrix data of the calculation target matrix to data stored in the storage unit 701 using the matrix storage method described in the present embodiment. FIG. 12 is a flowchart illustrating a specific operation of the information processing apparatus 700.

  First, a calculation target matrix 800 having one or more blocks illustrated in FIG. 8 is input to the information processing apparatus as a calculation processing target. In this case, the input unit 704 may accept input of data representing each element of the calculation target matrix 800 (step S1201).

  In this specific example, the blocks included in the calculation target matrix are (2 rows × 2 columns) type small matrices. Elements included in each block are represented by using symbols “* 1”, “* 2”, “* 3”, and “* 4”, as in FIG. Such a code simply represents an arrangement position of an element in a (2 × 2) block, and does not represent specific data (value). Arbitrary data (value) can be set in each element of the (2 rows × 2 columns) type block. As in FIG. 2, the blank element in the matrix 800 is a zero element. In this specific example, the block is a (2 × 2) sub-matrix, but the present embodiment is not limited to this. That is, the block size may be arbitrary. The size of the calculation target matrix may be arbitrary.

  The input unit 704 passes the data representing each element of the input calculation target matrix 800 to the arrangement unit 702.

  The placement unit 702 that has received such data packs (aggregates) each block included in the computation target matrix 800 in the left end region in the column direction, as illustrated in FIG. 9 (step S1202).

  As illustrated in FIG. 10, the arrangement unit 702 rearranges the block row numbers in the descending order of the number of non-zero blocks included in each block row for the matrix aggregated in the specific area in step S1202 (step S1203). ).

  The processes in steps S1202 to S1203 may be realized using a method similar to the JDS method described above.

  Next, with respect to the blocks included in the calculation target matrix, the arrangement unit 702 lowers the elements arranged in the same position in each block (elements having the same relative position) in the row direction in the matrix rearranged in step S1203. Then, selection (extraction) is sequentially performed from the first column of the block column numbers. The placement unit 702 places (stores) the selected elements (more specifically, data representing the elements) in order in a continuous area (storage area) in the storage unit 701 (step S1204). Here, the continuous area in the storage unit 701 may be a logically continuous area (address) in the storage area provided by the storage unit 701. Further, the continuous area may be, for example, a continuous area (address) in a physical storage device configuring the storage unit 701.

  More specifically, as illustrated in FIGS. 11A to 11D, the arrangement unit 702 exemplifies elements having the same block column number in order from the first column of the block column numbers in FIG. 11. The direction is selected in the direction of the arrow DA2 (the direction from the upper end side to the lower end side in the row direction). Then, the placement unit 702 places the selected element in a continuous area in the storage device 701. Thereby, elements having the same arrangement position in each block are arranged in a continuous area in the storage device 701.

  Specifically, for example, as illustrated in FIG. 11A, the arrangement unit 702 selects an element whose arrangement position in the block is “* 1” (position (1, 1)) from each block. To do. Then, the arranging unit 702 arranges the selected elements in a continuous area in the storage unit 701 in order. Similarly, the arrangement position in each block is “* 2” (position (1, 2)), “* 3” (position (2, 1)), “* 4” (position (2, 2)). The elements existing in the storage area 701 are arranged in continuous areas.

  In other words, the arrangement unit 702 selects, in each row of the sub-matrix representing each block, data representing elements arranged in each column sequentially from the column on the left end side in the column direction toward the right end side in the column direction. The data selected from the same column is arranged in a continuous area in the storage unit 701.

  This will be described with reference to specific examples illustrated in FIGS. For example, the arrangement unit 702 sequentially selects, from each block, each element arranged in the first row of each block from the left end column (first column) to the right end side (second column) in the column direction. The data representing the elements arranged in the same column is arranged in a continuous area in the storage unit 701. The same applies to the elements arranged in the second row of each block.

  In this case, for example, as illustrated in FIG. 11, the arrangement unit 702 may divide the storage array for each element having the same relative position in the block (for example, 1101, 1102, 1103, illustrated in FIG. 11). An array for storing 1104 may be provided).

  An area in the storage unit 701 in which data representing an element at a specific position in each block is arranged and an area in the storage unit 701 in which data representing an element at another position in each block are arranged are continuous areas. It may be. In addition, between the area in the storage unit 701 in which data representing an element at a specific position in each block is arranged and the area in the storage unit 701 in which data representing an element at another position in each block is arranged, Arbitrary data or the like may be arranged.

  In the operation loop for calculating the product between the operation target matrix having a block and an arbitrary vector by the processing in step S1204, data to be referred to (array data storing elements of each block) is stored in the storage unit 701. Are arranged in a continuous area (address). A specific example of such calculation processing will be described later.

  The array for storing the column numbers of the calculation target matrix (reference numeral 800 in FIG. 8) may be the same as the JDS method described above. That is, the arrangement unit 702 separately provides an array for storing the block column numbers in the matrix 800, similarly to the array illustrated in FIG. The arrangement unit 702 may arrange such an arrangement in the storage unit 701.

  In step S1203, the arrangement unit 702 may directly arrange the elements of the blocks included in the calculation target matrix in the storage unit 701, or may generate arrangement data that can be arranged in the storage unit 701. .

  Next, the efficiency of the arithmetic processing by the matrix storage method in the present embodiment will be described by taking the integration between the calculation target matrix arranged in the storage unit 702 as described above and an arbitrary vector as a specific example.

  FIG. 13 is a part of a Fortran code for calculating a product of an arithmetic target matrix having a (2 × 2) type block stored using the matrix storage method described above and an arbitrary vector. Each variable and array has the following meaning.

    The variable “N” represents the number of blocks in the row or column direction of the original matrix (for example, the calculation target matrix 800 in FIG. 8).

    The variable “NZ” represents the number of all non-zero blocks included in the original matrix.

    The array “A” represents a two-dimensional array that stores the value of each block (element) included in the original matrix. The subscript of the first dimension of the array “A” represents the number when it is made one-dimensionally and numbered (indexed) in the direction of the arrow DA2 in order from the first column of the matrix illustrated in FIG. The subscript in the second dimension is a number representing a difference in relative position in each block.

    The array “X” represents an input vector (X) to be calculated.

    The array “Y” represents an array that stores the calculation result of the product of the array “A” and the array “X”.

    The array “IA” indicates the number of the head of each block string when the elements of each block included in the original matrix A are one-dimensionally arranged in the order illustrated in FIG. Store. That is, the number of the block having the block string number I is IA (I). In addition, the number of block matrices having the block column number I is IA (I + 1) −IA (I).

    The array “JA” stores block column numbers of non-zero blocks included in the original matrix. The block row number of the Kth block is JA (K).

    The variable “MJAD” represents the maximum value of the number of non-zero blocks included in each row of the original matrix.

    The array “W” represents a work array that temporarily stores the product of the array “A” and the array “X”.

    The array IORD represents an array that stores the block row numbers when the original matrix is rearranged as exemplified in FIG. That is, when the block row number in the original array is “I”, the rearranged block row number is IORD (I).

  In the source code illustrated in FIG. 13, when the subscript K of the 20th DO loop which is the innermost operation loop is increased by 1, the subscript of the array A storing the non-zero elements of the operation target matrix is increased by 1.

  FIG. 14 is a diagram illustrating, as a flowchart, processing focusing on the array A for the 20th DO loop processing in the Fortran code illustrated in FIG. 13. The processing according to the flowchart illustrated in FIG. 14 may be executed by the arithmetic processing unit 703.

  The DO loop process of No. 20 in FIG. 13 corresponds to an iterative process executed between the branch process in step 1402 in FIG. 14 and the process of incrementing K in step S1411.

  In the above iterative processing, reading of the array A arranged in the storage device 701 and calculation of the product of the elements of the array X are alternately repeated between steps S1403 to S1410. The number of repeated processing sounds is M × M when the block included in the calculation target fish train is a small matrix of (M rows and M columns) type.

  However, the actual processing order may be changed depending on, for example, the execution environment of the information processing apparatus 700 or the optimization of the compiler that translates the Fortran code illustrated in FIG.

  In particular, a compiler optimized for a computer architecture having a SIMD (Single Instruction Multi Data) instruction that processes a plurality of data with one instruction seems to process a plurality of reading processes and arithmetic processes from a storage device. , Generate optimized execution code.

  FIG. 15 is a flowchart illustrating the processing sequence when the execution code obtained by compiling the source code illustrated in FIG. 13 is optimized for a computer architecture having SIMD instructions. Note that the processing according to the flowchart illustrated in FIG. 15 may be executed by the arithmetic processing unit 703.

  The symbol “L” in step S1503 represents the number of instructions simultaneously processed by the SIMD instruction. In steps S1504 to S1506, the reading process of the value of the array A is repeated.

  In steps S1508 to S1510, the calculation of the product of the array A value read in steps S1504 to S1506 and the array X is repeated.

  Steps S1504 to S1506 and steps S1508 to S1510 are all repeated processes of length L or less. When optimized for a computer architecture having SIMD instructions, the iterations in steps S1504 to S1506 and S1508 to S1510 are each processed with one instruction.

  At this time, in the process of reading data of the array A in steps S1504 to S1506, the subscript K of the array A is incremented by 1. Thus, in such processing, data arranged in a continuous area (address) in the storage device (for example, the storage unit 701) is read.

  When the above-described JDS storage method is used, when data is stored in a data storage device (for example, the storage unit 701) that represents a calculation target matrix having blocks, elements in the same block are stored in a continuous area (address) in the storage device. Is done. When the process of reading data representing the calculation target matrix is repeated in units of blocks, a discontinuous area (address) is accessed in the storage device.

  On the other hand, according to the matrix storage method in the present embodiment described above, continuous areas (addresses) are accessed in the storage device when the process repeated in units of blocks is executed. Therefore, according to the matrix storage method in the present embodiment, it is expected that the access performance to the storage device is improved as compared with the JDS storage method. Along with this, it is expected that the performance of the arithmetic processing is also improved.

  As described above, according to the information processing apparatus 700 in the present embodiment, the placement unit 702 can efficiently place the elements of the calculation target matrix having one or more non-zero blocks in the storage device 701. This is because the arrangement unit 702 can compress the zero element in the calculation target matrix as in the JDS storage method, and can improve the capacity efficiency.

  The placement unit 702 stores elements having the same relative position in each non-zero block in a continuous area in the storage unit 701. As a result, since the continuous area in the storage unit 701 is accessed in the calculation process repeated in units of blocks, the arrangement unit 702 can improve the calculation efficiency. In other words, according to the present embodiment, elements included in a matrix having one or more blocks are arranged in the storage unit 701 by a method with high capacity efficiency and calculation efficiency.

<Modification of First Embodiment>
The matrix storage method described in the first embodiment can be expanded by applying to the CRS storage method, which is a well-known matrix storage method, or the ELL (Ellpack) storage method. is there. Hereinafter, a method for extending these storage methods using the matrix storage method described in the first embodiment will be described. Note that the information processing apparatus 700 in the present modification may be the same as the information processing apparatus 700 in the first embodiment, and a description thereof will be omitted. Further, since the CRS storage method and the ELL storage method are well-known techniques, a detailed description of each storage method itself is omitted.

  First, an extension of the CRS storage method using the matrix storage method described in the first embodiment will be described.

  FIG. 16 is a matrix (FIG. 9) in which elements included in each block are arranged in order toward the right side in the column direction with respect to the matrix (FIG. 9) in which the calculation target matrix illustrated in FIG. 8 is packed on the left end side in the column direction. 16 represents 1600).

  In the known CRS storage method, the elements of the matrix 1600 (data represented by the elements) are sequentially directed from the first row of the matrix 1600 illustrated in FIG. 16 in the direction of the arrow DA3 illustrated in FIG. 16 (right side in the column direction). The data is continuously stored in a storage device (for example, the storage unit 701). For this reason, the elements (“* 1” to “* 4”) in each block are arranged in a continuous area (address) in the storage device. In this case, as in the well-known JDS storage method described above, when the process of reading data representing the calculation target matrix (for example, the matrix 1600) is repeated in units of blocks, a discontinuous area (address) is accessed in the storage device. Will be.

  On the other hand, the arrangement unit 701 in this modification example arranges elements having the same relative position in each block in a continuous area (address) in the storage unit 701. More specifically, the arrangement unit 702 in this modification example selects elements included in the same block row in the direction of the arrow DA4 illustrated in FIG. 17 (right side in the column direction) in order from the first column of the block column numbers. To do. Then, the placement unit 702 places the selected element in a continuous area in the storage device 701. Thereby, elements having the same arrangement position in the (2 rows × 2 columns) type block are arranged (stored) in a continuous area (address) in the storage unit 701.

  In this case, as illustrated in FIG. 17, the arrangement unit 702 may divide an array for storing the elements one-dimensionally for each element having the same relative position in each block (for example, 1701 in FIG. 17, 1702, 1703, 1704).

  Next, an extension of the ELL storage method using the matrix storage method described in the first embodiment will be described.

  18 illustrates a matrix (FIG. 9) in which the calculation target matrix illustrated in FIG. 8 is packed on the left end side in the column direction (FIG. 9), in which elements included in each block are arranged in order in the row direction downward ( Reference numeral 1800 in FIG. Note that “* 0” in FIG. 18 indicates that zero elements are stored.

  The well-known ELL storage method is such that the elements of the matrix 1800 (data represented by the elements) are sequentially directed from the first column of the matrix 1800 illustrated in FIG. 18 in the direction of the arrow DA5 illustrated in FIG. Are continuously stored in a storage device (for example, the storage unit 701). Elements (“* 1” to “* 4”) in each block are arranged in a continuous area (address) in the storage device. In this case, as in the well-known JDS storage method described above, when the process of reading data representing the calculation target matrix (for example, the matrix 1800) is repeated in units of blocks, a discontinuous area (address) is accessed in the storage device. Will be.

  On the other hand, the arrangement unit 701 in this modification example arranges elements having the same relative position in each block in a continuous area (address) in the storage unit 701. More specifically, the arrangement unit 702 in the present modification example has a (2 rows × 2 columns) type in the direction of the arrow DA6 (lower side in the row direction) illustrated in FIG. 19 in order from the first row of the block row numbers. Elements having the same arrangement position in the block are arranged (stored) in a continuous area (address) in the storage unit 701.

  In this case, as illustrated in FIG. 19, the arrangement unit 702 may divide an array for storing the elements one-dimensionally for each element having the same relative position in each block (for example, 1901 in FIG. 19, 1902, 1903, 1904).

  As described above, according to the present embodiment, by expanding the CRS storage method and the ELL storage method, elements included in a matrix having one or more blocks can be arranged in the storage device in a method with high capacity efficiency and calculation efficiency. A simple information processing apparatus 700 can be provided.

<Second Embodiment>
Hereinafter, a second embodiment of the present invention will be described with reference to FIG. FIG. 20 is a block diagram illustrating a functional configuration of the information processing apparatus 2000 according to this embodiment.

  As illustrated in FIG. 20, the information processing apparatus 2000 according to the present embodiment includes a storage unit 2001 and an arrangement unit 2002. These components constituting the information processing apparatus 2000 may be communicably connected by any communication means. The information processing apparatus 2000 may be configured with a physical computer or the like, or may be configured with a virtual computer or the like provided using a well-known virtualization technology.

  The storage unit 2001 can store at least data. For example, the storage unit 2001 may be a storage device such as a physical semiconductor memory. The storage unit 2001 may be a virtual storage device provided in a virtual environment. Note that the storage unit 2001 may be the same as the storage unit 701 in the first embodiment.

  The arrangement unit 2002 continuously stores, in the storage unit 2001, data representing elements arranged at the same position in each second matrix with respect to the second matrix that is a block included in at least one of the first matrix. Place in the area. Note that the arrangement unit 2002 may be the same as the storage unit 702 in the first embodiment.

  According to the information processing apparatus 2000 according to the present embodiment configured as described above, the placement unit 2002 efficiently uses the elements of the first matrix having one or more blocks (second matrix) for the storage device 2001. Can be placed well.

  In addition, the arranging unit 2002 stores elements having the same relative position in the second matrix in a continuous area in the storage device 2002. As a result, in the arithmetic processing repeated in units of blocks, since continuous areas in the storage device are accessed, the arrangement unit 2002 can improve the arithmetic efficiency. That is, according to the present embodiment, the elements included in the first matrix having one or more second matrices can be arranged in the storage unit 2001 by a method with good capacity efficiency and calculation efficiency.

<Configuration of hardware and software program (computer program)>
Hereinafter, a hardware configuration capable of realizing each of the above-described embodiments will be described.

  In the following description, the information processing apparatuses (700, 2000) described in the above embodiments may be collectively referred to simply as “information processing apparatus”. In addition, each component of the information processing apparatus (for example, the storage unit (701, 2001), the arrangement unit (702, 2002), the arithmetic processing unit 703, and the input unit 704) is collectively referred to as “information processing apparatus component. May be called.

  The information processing apparatus described in each of the above embodiments may be configured by a dedicated hardware device. In that case, each component shown in each of the above drawings may be realized as hardware (an integrated circuit or the like on which processing logic is mounted) that is partially or fully integrated.

  For example, when each component is realized by hardware, an integrated circuit capable of providing each function may be implemented by SoC (System-on-a-chip) or the like. In this case, for example, data held by each component may be stored in a RAM area or a flash memory area integrated as SoC.

  In this case, a well-known communication bus may be adopted as a communication line for connecting each component. Further, the communication line connecting each component is not limited to bus connection, and each component may be connected by peer-to-peer.

  Further, the information processing apparatus described above or the components of the information processing apparatus are configured by hardware as illustrated in FIG. 21 and various software programs (computer programs) executed by the hardware. May be.

  An arithmetic device 2101 in FIG. 21 is an arithmetic processing device such as a general-purpose CPU or a microprocessor. The arithmetic device 2101 may read various software programs stored in a nonvolatile storage device 2103, which will be described later, into the storage device 2102 and execute processing according to the software programs. Note that the arithmetic processing unit 703 in the first embodiment may execute various arithmetic processes using the arithmetic device 2101.

  The storage device 2102 is a memory device such as a RAM (Random Access Memory) that can be referred to from the arithmetic device 2101, and stores software programs, various data, and the like. Note that the storage device 2102 may be a volatile memory device. Note that the storage units (701 and 2001) in each of the above embodiments may be realized using the storage device 2102.

  The nonvolatile storage device 2103 is a nonvolatile storage device such as a magnetic disk drive or a semiconductor storage device using flash memory. The nonvolatile storage device 2103 can store various software programs, data, and the like.

  The network interface 2106 is an interface device connected to a communication network, and for example, a wired and wireless LAN (Local Area Network) connection interface device or the like may be employed. Note that the input unit 704 in the first embodiment may accept various inputs via the network interface 2106.

  The drive device 2104 is, for example, a device that processes reading and writing of data with respect to an external storage medium 2105 described later.

  The external recording medium 2105 is an arbitrary recording medium capable of recording data, such as an optical disk, a magneto-optical disk, and a semiconductor flash memory.

  The input / output interface 2107 is a device that controls input / output with an external device. For example, a user or administrator of an information processing apparatus uses a variety of input / output devices (for example, a keyboard, mouse, display device, printer, etc.) connected via the input / output interface to the information processing apparatus. Various operation instructions and the like may be input. Note that the input unit 704 in the first embodiment may accept various inputs via the input / output interface 2107.

  The present invention described by taking each embodiment described above as an example configures an information processing device by the hardware device illustrated in FIG. 21, for example, and realizes the function described in each of the above embodiments for the hardware device. It may be realized by supplying possible software programs. In this case, the present invention may be realized by the arithmetic device 2101 executing the software program supplied to the device.

  In each of the above-described embodiments, each unit shown in each of the above-described drawings (for example, FIG. 7, FIG. 20, etc.) is realized as a software module, which is a function (processing) unit of a software program executed by the above-described hardware. can do. However, the division of each software module shown in these drawings is a configuration for convenience of explanation, and various configurations can be assumed for implementation.

  For example, when each unit illustrated in FIG. 7 and FIG. 20 is realized as a software module, these software modules are stored in the nonvolatile storage device 2103, and when the arithmetic device 2101 executes each process, You may comprise so that these software modules may be read to the memory | storage device 2102. FIG.

  In addition, these software modules may be configured to transmit various data to each other by an appropriate method such as shared memory or interprocess communication. With such a configuration, these software modules can be connected so as to communicate with each other.

  Further, each software program is recorded in the external storage medium 2105, and the software program is appropriately stored in the nonvolatile memory 2103 through the drive device 2104 at the shipping stage or the operation stage of the communication apparatus. It may be configured.

  In the above case, the method of supplying various software programs to the information processing apparatus is installed in the apparatus using an appropriate jig at the manufacturing stage before shipment or the maintenance stage after shipment. You may adopt the method of doing. As a method for supplying various software programs, a general procedure may be adopted at present, such as a method of downloading from the outside via a communication line such as the Internet.

  In such a case, the present invention can be understood to be constituted by a code constituting the software program or a computer-readable storage medium in which the code is recorded.

  In addition, the information processing apparatus described above or the components of the information processing apparatus include a virtual environment in which the hardware device illustrated in FIG. 21 is virtualized, and various software programs (computers) that are executed in the virtual environment. -A program). In this case, the components of the hardware device illustrated in FIG. 21 are provided as virtual devices in the virtual environment. In this case as well, the present invention can be realized with the same configuration as the case where the hardware device illustrated in FIG. 21 is configured as a physical device.

  In the above, this invention was demonstrated as an example applied to exemplary embodiment mentioned above. However, the technical scope of the present invention is not limited to the scope described in the above embodiments. It will be apparent to those skilled in the art that various modifications and improvements can be made to such embodiments. In such a case, new embodiments to which such changes or improvements are added can also be included in the technical scope of the present invention. This is clear from the matters described in the claims.

  The present invention is, for example, in the case of solving a matrix equation having a large-scale sparse matrix as a coefficient matrix using an iterative solving method (for example, a CG (Conjugate Gradient) method (conjugate gradient method)) in numerical analysis processing by a finite element method. Applicable. The present invention is particularly applicable to numerical calculation processing in which the integration of large-scale sparse matrices and vectors occupies the main calculation cost.

700 Information Processing Device 701 Storage Unit 702 Arrangement Unit 703 Arithmetic Processing Unit 704 Input Unit 2000 Information Processing Device 2001 Storage Unit 2002 Arrangement Unit 2101 Arithmetic Device 2102 Storage Device 2103 Nonvolatile Storage Device 2104 Drive Device 2105 External Storage Medium 2106 Network Interface 2107 Input Output interface

Claims (10)

Storage means for storing at least data;
An arrangement in which data representing elements arranged at the same position in each of the second matrices is arranged in a continuous area in the storage unit with respect to a second matrix which is a block included in at least one of the first matrix. And an information processing apparatus. The arrangement means includes
Aggregating the second matrix into a specific region in the first matrix;
In each row of the aggregated second matrix, sequentially select data representing elements arranged in a specific column from the column on the left end side in the column direction toward the right end side in the column direction;
The information processing apparatus according to claim 1, wherein data selected from the same specific column in each row of each second matrix is arranged in a continuous area in the storage unit. The arrangement means includes
The columns included in the first matrix are grouped for each number of columns of the block into a block column,
The rows included in the first matrix are grouped for each number of rows of the block into block rows,
For each block column, the same block column is arranged from the block row arranged at the upper end in the row direction in the first matrix toward the block row arranged at the lower end in the row direction in the first matrix. Sequentially selecting the second matrix included;
The information processing apparatus according to claim 1, wherein data representing elements arranged at the same position in the selected second matrix is arranged in a continuous area in the storage unit. The arrangement means includes
The columns included in the first matrix are grouped for each number of columns of the block into a block column,
The rows included in the first matrix are grouped for each number of rows of the block into block rows,
For each block row, the same block row from the block column arranged at the left end in the column direction in the first matrix toward the block column arranged at the right end in the column direction in the first matrix Sequentially selecting the second matrix included in
The information processing apparatus according to claim 1, wherein data representing elements arranged at the same position in the selected second matrix is arranged in a continuous area in the storage unit. The arrangement means includes
The columns included in the first matrix are grouped for each number of columns of the block into a block column,
The rows included in the first matrix are grouped for each number of rows of the block into block rows,
For each block column, sequentially select the second matrix included in the block column in descending order of the number of the second matrices included in the block row, and the same in the selected second matrix The information processing apparatus according to claim 1, wherein data representing elements arranged at positions is arranged in a continuous area in the storage unit. The arrangement means includes
In the first matrix, the block rows are rearranged in the descending order of the number of the second matrix included in the block row,
For each block column, from the block row arranged at the upper end in the row direction in the rearranged first matrix toward the block row arranged at the lower end in the row direction, the block column includes Select the second matrix sequentially,
The information processing apparatus according to claim 3, wherein data representing elements arranged at the same position in the selected second matrix is arranged in a continuous area in the storage unit. The information processing apparatus according to claim 1, wherein the second matrix is a square matrix. From the second matrix, which is an included block that is at least one block included in the first matrix, data representing elements arranged at the same position in each of the second matrices is selected, and the selected An information processing apparatus that generates arrangement data arranged so that data representing elements is arranged in a continuous area in a storage unit capable of storing data. An information processing apparatus comprising a storage means for storing data,
Information for arranging data representing elements arranged at the same position in each of the second matrices in a continuous area in the storage means for the second matrix, which is a block included in at least one of the first matrix. Processing method. In a computer having storage means for storing data,
Processing for arranging data representing elements arranged at the same position in each of the second matrices in a continuous area in the storage means for the second matrix that is at least one block included in the first matrix A computer program that runs

Images