Symbolic calculation system, symbolic calculation method and parallel circuit simulation system

The coefficient matrix, corresponding to the simultaneous linear equations to be solved, is divided into a plurality of row sets. The row sets as divided are processed in a parallel fashion, and entries specifying the nonzero elements contained in the first to nth row sets are added to the entry sets E1 to En. Moreover, in regard to each row set, fill-ins which take place at the time of eliminating the ith variable are obtained in a parallel fashion, and entries specifying the fill-ins are added to the entry sets E1 to En. The coefficient matrix is compressed using those entry sets E1 to En.

This application is based on Japanese Patent Application No. 10-127738 filed May 11, 1998, which application is incorporated herein by reference in its entirety.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a symbolic calculation system and a symbolic calculation method, both for performing a symbolic calculation to solve simultaneous linear equations, and also relates to a parallel circuit simulation system which effects a circuit simulation by solving the simultaneous linear equations.

2. Description of the Related Art

Generally speaking, a process for solving simultaneous linear equations involves a symbolic calculation process and a numerical calculation process. An example of the symbolic calculation process, involved in the process for solving simultaneous linear equations, is described in the third section Sparse Matrix Methods of Fundamentals of Computer-Aided Circuit Simulation (written by William J. McCalla and published in 1988).

FIG. 11 is a flowchart showing the symbolic calculation process involved in the aforementioned conventional process for solving simultaneous linear equations.

Firstly, a single entry set E is prepared, and information (entries) specifying the positions of nonzero elements contained in a coefficient matrix is sequentially added to the entry set E. Further, an array R(k) representing the number of entries contained in the k th row and an array C(k) representing the number of entries contained in the k th column are also prepared and updated at the time of adding the entries (a step S 410 ).

Next, the use of a variable i, representing a count which is incremented each time the symbolic calculation process is repeated, is declared, and the initialization procedure of substituting the value 1 for i is conducted (a step S 420 ). Following this, the value of W which results in the minimum value of R(w) C(w) is determined (a step S 430 ). In obtaining the values of R(w) and C(w) in the step S 430 , the entries specifying the elements contained in those parts of the matrix which correspond to eliminated variables and equations and the entries specifying diagonal elements are not counted.

After the value of W has been determined, the i th and w th rows of the entry set E are replaced with each other, as well as the i th and w th columns thereof (a step S 440 ). Then, fill-ins which take place at the time of eliminating the i th variable are computed, and entries specifying the fill-ins are added to the entry set E (a step S 450 ).

When the step S 450 is finished, the variable i is incremented by 1 (a step S 460 ). Next, it is determined whether the value of the variable i exceeds m 1 (a step S 470 ). When it is determined in the step S 470 that the value of the variable i does not exceed m 1, a return is made to the step S 430 . By repeating the steps S 430 to S 470 , the optimum pivot order and the positions in which the fill-ins take place can be determined.

On the other hand, when it is determined in the step S 470 that the value of the variable i exceeds m 1, the coefficient matrix is compressed using the entry set E to which the entries have been added in the steps S 410 and S 450 . Matrix data, obtained as a result of the compression, is stored in a storage area of a storage device or the like (a step S 480 ), and the process shown in the flowchart is terminated. When the process of FIG. 11 is terminated, then the numerical calculation process is conducted.

However, the conventional process for solving the simultaneous linear equations has the following drawbacks:

Firstly, in the case where a parallel computer of distributed memory type executes the symbolic calculation process, a single node has to carry out the steps of the symbolic calculation process one after another. Under this condition, the capacity of a local memory included in the node restricts the size of the coefficient matrix which can be handled.

Secondly, in the case where the coefficient matrix which is a square matrix has a size of m m (which indicates the number of rows and columns included in the coefficient matrix), the time required for completing the symbolic calculation process increases substantially in proportion to m 1 to m 3 . Hence, as the coefficient matrix size becomes large and as the number of entries which are added to the entry set becomes excessive, the symbolic calculation process cannot be finished within a practical length of time.

The above-described drawbacks occur also in the case of performing a circuit simulation which entails the process for solving simultaneous linear equations.

SUMMARY OF THE INVENTION

The present invention has been made in consideration of the above drawbacks, and it is accordingly an object of the present invention to provide a symbolic calculation system and a symbolic calculation method, which can handle a large-scale matrix and whose calculation time is short.

It is another object of the present invention to provide a parallel circuit simulation system which can perform a large-scale circuit simulation at high speed.

According to the first aspect of the present invention having the above-described objects, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:

a plurality of nodes each having an element processor and local memory including a program area which stores a predetermined program to be executed by the corresponding element processor and a work area used by the element processor, and an interconnection network which interconnects the plurality of nodes, wherein the element processors of the plurality of nodes are capable of cooperating with each other,

the symbolic calculation system comprising a first computer which is connected to the interconnection network, and which divides a matrix, representing the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix,

wherein each of the plurality of nodes corresponds to each row set divided by the first computer, and each of the element processor executes the predetermined program stored in the program area thereby each of the plurality of nodes:

adds entries specifying nonzero elements contained in the row sets associated with the plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;

sequentially attains a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix, by cooperating with other nodes;

replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, by cooperating with other nodes;

replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix, by cooperating with other nodes;

obtains fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and/or columns replaced with each other, and further adding entries specifying the obtained fill-ins to the plurality of entry sets to the entry sets.

According to this symbolic calculation systems, the plurality of nodes carry out the addition of the entries in a parallel fashion. This enables the symbolic calculation in solving the simultaneous linear equations to be performed at high speed.

In the case of realizing the aforementioned symbolic calculation systems with parallel computers of distributed memory type, the data amount corresponding to the product of the reciprocal of the number of parts in which the matrix is divided and the amount of data when a single node performs the addition of the entries to an entry set will be almost satisfactory as the amount of data to be stored in the local memory included in each of nodes which realize the plurality of first and second entry adders. In this case, the capacity of the local memory in each node does not restrict the size of the coefficient matrix which can be handled. Hence, the process for solving the simultaneous linear equations can be conducted on a large scale.

In the above-described symbolic calculation system, the first computer may be realized by any one of the plurality of nodes.

In this case, any one of the plurality of nodes may attain the first variable which determines the minimum number of calculations.

Moreover, any one of the plurality of nodes may replace one row specified by the first variable and another row specified by the second variable with each other.

Any one of the plurality of nodes may further replace one column specified by the first variable and another column specified by the second variable with each other.

The above-described symbolic calculation system may further comprise a second computer which is connected to the interconnection network and which compresses the matrix based on contents of the plurality of entry sets to which the entries have been added.

In this case, the second computer may be realized by any one of the plurality of nodes.

The above-described symbolic calculation system may further comprise a third computer which is connected to the interconnection network, and which creates a lower left rectangular matrix and an upper right triangular matrix, based on the matrix as compressed, and which performs a forward substitution with respect to the lower left rectangular matrix and performs a backward substitution with respect to the upper right rectangular matrix by using solutions obtained as a result of the forward substitution, in order to create data representing solutions of the simultaneous linear equations.

In this case, the third computer may be realized by any one of the plurality of nodes.

According to the second aspect of the present invention having the above-described objects, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:

a matrix divider which divides a matrix, representing the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;

a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;

a pivot selector which sequentially attains a first variable specifying specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;

a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and

a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot replacer, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.

According to the third aspect of the present invention, there is provided a symbolic calculation system which performs a symbolic calculation to solve simultaneous linear equations, comprising:

a plurality of first entry adders, each of which associated with one of a plurality of row sets each comprising at least one of different rows of a matrix representing the simultaneous linear equations to be solved, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;

a pivot selector which sequentially attains a first variable specifying an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;

a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and which replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and

a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot replacer, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.

According to these symbolic calculation systems, the plurality of first and second entry adders carry out the addition of the entries in a parallel fashion. This enables the symbolic calculation in solving the simultaneous linear equations to be performed at high speed.

In the case of realizing the aforementioned symbolic calculation systems with parallel computers of distributed memory type, the data amount corresponding to the product of the reciprocal of the number of parts in which the matrix is divided and the amount of data when a single node performs the addition of the entries to an entry set will be almost satisfactory as the amount of data to be stored in the local memory included in each of nodes which realize the plurality of first and second entry adders. In this case, the capacity of the local memory in each node does not restrict the size of the coefficient matrix which can be handled. Hence, the process for solving the simultaneous linear equations can be conducted on a large scale.

According to the fourth aspect of the present invention having the aforementioned objects, there is provided a parallel circuit simulation system comprising:

a plurality of nodes each having an element processor and local memory including a program area which stores a predetermined program to be executed by the corresponding element processor and a work area used by the element processor, and an interconnection network which interconnects the plurality of nodes, wherein the element processors of the plurality of nodes are capable of cooperating with each other,

the parallel circuit simulation system comprising a first computer which is connected to the interconnection network, the first computer dividing a circuit to be simulated into a plurality of circuit pieces, preparing circuit piece matrix representing circuit equations corresponding to divided circuit pieces respectively, and transmitting the prepared circuit piece matrix to the plurality of nodes,

wherein each of the element processor executes the predetermined program stored in the program area thereby the plurality of nodes:

executes symbolic calculation on the circuit piece matrix transmitted by the first computer, executes numeric calculation on the result of the symbolic calculation executed by each node, and resolves the circuit equation represented by the received circuit piece matrix,

the parallel circuit simulation system comprises:

a second computer which is connected to the interconnection network, and which prepares a circuit matrix of connected circuits including connected circuit pieces, based on the obtained resolution of the circuit equation for the circuit pieces; and

a third computer which is connected to the interconnection network, and which divides the prepared circuit matrix of the connected circuits into a plurality of row sets each comprising at least one of rows of the matrix, and which transmits the plurality of row sets to the plurality of nodes respectively,

wherein each element processor executes the predetermined program stored in the program area, thereby each of the plurality of nodes further:

adds entries specifying nonzero elements contained in the row sets associated with the plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;

sequentially attains a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix, by cooperating with other nodes;

replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, by cooperating with other nodes;

replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix, by cooperating with other nodes;

obtains fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and/or columns replaced with each other, and further adds entries specifying the obtained fill-ins to the plurality of entry sets to the entry sets.

In the above-described parallel circuit simulation system, any of the first to third computers may be realized by any one of the plurality of nodes.

The above-described parallel circuit simulation system may further comprise a fourth computer which is connected to the interconnection network, and which compresses the matrix based on contents of the plurality of entry sets to which the entries have been added.

In this case, the fourth computer may be realized by any one of the plurality of nodes.

According to the fifth aspect of the present invention having the above-described objects, there is provided a symbolic calculation method for performing a symbolic calculation to solve simultaneous linear equations, comprising:

dividing a matrix, which represents the simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;

adding, in parallel, entries specifying nonzero elements contained in the plurality of row sets divided by the dividing to a plurality of entry sets which are in one-to-one correspondence with the plurality of row sets;

sequentially attaining a first variable which specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;

replacing one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and replacing one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and

obtaining, in parallel, fill-ins belonging to the plurality of row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the replacing, and adding, in parallel, entries specifying the obtained fill-ins to the plurality of entry sets to which the entries specifying the nonzero elements contained in the plurality of row sets have been added in parallel.

The above-described symbolic calculation method may further comprise compressing the matrix, based on contents of the plurality of entry sets to which the entries specifying the nonzero elements contained in the plurality of row sets and the entries specifying the obtained fill-ins have been added.

According to the sixth aspect of the present invention having the aforementioned objects, there is provided a parallel circuit simulation system comprising:

a circuit divider which divides a circuit to be simulated into partial circuits;

a plurality of partial circuit matrix calculators, each of which is associated with one of the partial circuits divided by the circuit divider, and which creates partial circuit matrices representing circuit equations of the partial circuits associated with the plurality of partial circuit matrix calculator;

a plurality of partial circuit symbolic calculators, each of which is associated with one of the partial circuits, and which perform symbolic calculations based on the partial circuit matrices representing the circuit equations of the associated partial circuits and created by the plurality of partial circuit matrix calculators;

a plurality of partial circuit numerical calculators, each of which is associated with one of the partial circuits, and which solve the circuit equations of the associated partial circuits by performing numerical calculations using calculation results obtained as a result of the symbolic calculations which the plurality of partial circuit symbolic calculators have performed based on the partial circuit matrices representing the circuit equations of the associated circuit sections;

a combination circuit matrix calculator which creates a combination circuit matrix representing circuit equations of a combination circuit that is a combination of the partial circuits, based on solutions of the circuit equations of the partial circuits which have been solved by the plurality of partial circuit numerical calculators;

a combination circuit symbolic calculator which performs symbolic calculations based on the combination circuit matrix created by the combination circuit matrix calculator; and

a combination circuit numerical calculator which solves the circuit equations of the combination circuit by performing numerical calculations using calculation results obtained as a result of the symbolic calculations performed by the combination circuit symbolic calculator;

wherein the combination circuit symbolic calculator comprises:

a matrix divider which divides the combination circuit matrix into a plurality of row sets each comprising at least one of rows of the combination circuit matrix;

a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;

a pivot selector which sequentially attains a first variable specifying specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the combination circuit matrix;

a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the combination circuit matrix, and which replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the combination circuit matrix; and

a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to the combination circuit matrix including the rows and columns replaced with each other by the pivot replacer, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.

According to the seventh aspect of the present invention having the aforementioned objects, there is provided a computer usable storage medium containing a computer readable program stored therein for causing a computer to serve as:

a matrix divider which divides a matrix, representing simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;

a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;

a pivot selector which sequentially attains a first variable specifying an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;

a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows included in the matrix, and replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and

a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot replacer, and add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.

According to the eighth aspect of the present invention having the aforementioned objects, there is provided a program signal embedded in a carrier wave, for causing a computer to serve as:

a matrix divider which divides a matrix, representing simultaneous linear equations to be solved, into a plurality of row sets each comprising at least one of rows of the matrix;

a plurality of first entry adders, each of which is associated with one of the plurality of row sets divided by the matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with the plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with the plurality of row sets;

a pivot selector which sequentially attains a first variable specifying specifies an unknown that can be eliminated with a minimum number of calculations, among a plurality of unknowns which are designated by a second variable whose value sequentially changes from 1 up to a value equal to the number of rows included in the matrix;

a pivot replacer which replaces one row specified by the first variable and another row specified by the second variable with each other, among the rows of the matrix, and which replaces one column specified by the first variable and another column specified by the second variable with each other, among columns of the matrix; and

a plurality of second entry adders, provided in one-to-one correspondence with the plurality of first entry adders, and which obtain fill-ins belonging to the associated row sets from a plurality of fill-ins that occur in eliminating the unknown in regard to the matrix including the rows and columns replaced with each other by the pivot selector, and which add entries specifying the obtained fill-ins to the plurality of entry sets to which the entries have been added by the plurality of first entry adders that are in one-to-one correspondence with the plurality of second entry adders.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

First Embodiment

FIG. 1 is a block diagram illustrating the structure of the parallel computer adopted in the first embodiment of the present invention.

As illustrated, the parallel computer 1 has a plurality of nodes 11 to 1 L. The nodes 11 to 1 L are coupled to each other via a mutual coupling network 10 .

Each of the nodes 11 to 1 L comprises an element processor, a local memory and a bus. The reference symbols 11 a to 1 L a denote the element processors of the nodes 11 to 1 L, respectively. The reference symbols 11 b to 1 L b denote the local memories of the nodes 11 to 1 L, respectively. The reference symbols 11 c to 1 L c denote the buses of the nodes 11 to 1 L, respectively.

The element processor and local memory included in each node are connected to each other via the bus which is also included therein. The busses 11 c to 1 L c are connected to the mutual coupling network 10 .

The element processors 11 a to 1 L a exchange messages with each other through the mutual coupling network 10 . Moreover, the element processor of one node remotely accesses the local memory of another node.

By so doing, a processing request is sent from one node to another node in the parallel computer 1 . The requested processing is carried out in a parallel fashion as a result.

The local memories 11 b to 1 L b of the nodes store programs to be executed by their corresponding element processors of the nodes, and are used as work areas for the element processors.

A workstation 2 is connected to the mutual coupling network 10 of the parallel computer 1 . The workstation 2 comprises an input device 21 and an external storage device 22 . The simultaneous linear equations to be calculated (or its coefficient matrix) are input to the input device 21 of the workstation 2 . The workstation 2 sends the coefficient matrix to the parallel computer 1 , and requests the parallel computer 1 to execute a process for solving simultaneous linear equations.

The process for solving simultaneous linear equations, which is carried out by the parallel computer 1 of FIG. 1 according to the first embodiment, will now be described.

FIG. 2 is a flowchart showing the outline of the process for solving simultaneous linear equations according to the first embodiment.

The process for solving simultaneous linear equations is accomplished by sequentially executing an entry registration process (a step S 110 ), a diagonal pivoting process (a step S 120 ), a matrix compression storage process (a step S 130 ), an LU decomposition process (a step S 140 ) and a forward-backward substitution process (a step S 150 ). Of those processes, the steps S 110 to S 130 are executed as the symbolic calculation process, while the steps S 140 and S 150 are executed as the numerical calculation process.

In the step S 110 of the entry registration process, information units (entries) specifying the positions of nonzero elements in the coefficient matrix sent from the workstation 2 are added to a plurality of entry sets E.

The entry registration process is effected in a parallel fashion in units of row sets which will be explained later. In this process, the entry sets E which are a plurality of empty sets are first prepared one for each row set. Then, the entry <i, j> which indicates the intersection of the i th row and the j th column where a nonzero element in the coefficient matrix is present, is added element by element to the entry sets prepared for the row sets containing such nonzero elements.

In the step S 120 of the diagonal pivoting process, rows and columns are replaced with each other in the coefficient matrix. Of the zero elements contained in the original coefficient matrix, the elements (fill-ins) which become nonzero values as a result of the LU decomposition process, are also added to the entry sets E prepared for the row sets containing the fill-ins.

In the step S 130 of the matrix compression storage process, areas for storing nonzero elements attained after the LU decomposition process are reserved, using the entry sets E obtained through the processes up to the step S 120 . The values of the elements in the coefficient matrix are stored in the reserved areas.

In the step S 140 of the LU decomposition process, the process for factorizing the coefficient matrix into the product of a lower left triangular matrix L and an upper right triangular matrix U is performed. In this embodiment, the LU decomposition process is carried out with values being overwritten in an area in which the coefficient matrix has been stored.

In the step S 150 of the forward-backward substitution process, a linear equation expressed by the coefficient matrix is solved. In this process, when the linear equation expressed by the coefficient matrix is Ax b (where A is the coefficient matrix, x is a solution vector, and b is a right-side vector), the forward substitution procedure for obtaining the solution of Y by solving the equation Ly b and the backward substitution procedure for obtaining the solution of x by solving the equation Ux y are performed.

FIG. 3 is a flowchart which shows in detail the symbolic calculation process (the steps S 110 to S 130 ) of FIG. 2 .

In this flowchart, steps S 211 to S 21 L are executed as the process shown as the step S 110 in FIG. 2 . Steps S 220 to S 270 shown in FIG. 3 are executed as the process shown as the step S 120 in FIG. 2. A step S 280 in FIG. 3 is executed as the process shown as the step S 130 in FIG. 2 .

By operating the input device 21 of the workstation 2 , a user inputs simultaneous linear equations to be solved to the workstation 2 . Thereafter, by operating the input device 21 , the user inputs to the workstation 2 an instruction to solve the simultaneous linear equations which have been input with the input device 21 to the workstation 2 .

Then, the workstation 2 creates a coefficient matrix representing the simultaneous linear equations, and divides the coefficient matrix into a plurality of row sets. In order to facilitate understanding, the size (the number of rows) of the coefficient matrix will be hereinafter referred to as m , while the number of row sets will be referred to as n (n 1).

Next, the workstation 2 sends the created coefficient matrix to the parallel computer 1 , and requests the parallel computer 1 to execute the symbolic calculation process.

Of the element processors 11 a to 1 L a of the nodes 11 to 1 L in the parallel computer 1 , the element processor of the node which has received the request for execution of the symbolic calculation process transmits n row sets forming the coefficient matrix in one-to-one correspondence to n nodes of the nodes 11 to 1 L through the mutual coupling network 10 . The node which has received the request for execution of the symbolic calculation process may transmit one row set within the node itself through inter-process communications.

In order to facilitate understanding, let it be assumed that the node 11 has received the request for execution of the symbolic calculation process. Let it be further assumed that the nodes 11 to 1 n have received the row sets.

The n nodes, 11 to 1 n, which have received the row sets forming the coefficient matrix, operate in a parallel fashion. The element processors 11 a to 1 n a of the nodes 11 to 1 n reserve areas in their corresponding local memories of the nodes 11 to 1 n. Then, the element processors 11 a to 1 n a prepare a plurality of entry sets in one-to-one correspondence with the received row sets, and store the entry sets in the aforementioned areas.

The entry sets prepared by the element processors 11 a to 1 n a will be hereinafter referred to as the entry sets E 1 to En.

Furthermore, the element processors 11 a to 1 n a reserve areas for storing arrays R 1 to Rn in their corresponding local memories of the nodes to which the element processors 11 a to 1 n a belong. An array Rp (1 p n) is an array whose k th element represents the number Rp(k) (1 k m) of entries included in the k th row of a matrix in which those of the coefficient matrix elements which do not belong to the row set received by the node 1 p are all expressed as zero.

Moreover, the element processors 11 a to 1 n a reserve areas for storing arrays C 1 to Cn in their corresponding local memories of the nodes to which the element processors 11 a to 1 n a belong. An array Cp is an array whose k th element represents the number Cp(k) of entries included in the k th column of the matrix in which those of the coefficient matrix elements which do not belong to the row set received by the node 1 p are all expressed as zero.

Next, the element processors 11 a to 1 n a add entries specifying the nonzero elements of the elements contained in their respective row sets as received to the entry sets E 1 to En prepared by the element processors 11 a to 1 n a , respectively. When adding the entries to the entry sets E 1 to En, the element processors 11 a to 1 n a update the values of the elements contained in the arrays R 1 to Rn and C 1 to Cn (steps S 211 to S 21 n).

When the nodes 11 to 1 n have finished the steps S 211 to S 21 n, the element processor of one of the nodes 11 to 1 L in the parallel computer 1 prepares the variable i as a count to be incremented each time the symbolic calculation process is repeated, and performs the initialization procedure of substituting 1 for i (in order to facilitate understanding, let it be assumed that the element processor 11 a of the node 11 , for example, prepares the variable i).

Furthermore, the element processor 11 a reserves in the local memory 11 b an area for storing a replacement array S, and stores the replacement array S in the reserved area (a step S 220 ).

The replacement array S shows the result of the replacement of rows and columns which has been performed in the coefficient matrix by a step S 240 that will be explained later. The replacement array S contains m elements. Of the m elements, the w th element S(w) (1 w m) is a value representing in what ordinal rank the w th column of the coefficient matrix after the replacement of rows and columns in the step S 240 , was located at the point the coefficient matrix was received from the workstation 2 . It should be noted that in the step S 220 , the replacement array S is prepared in the state wherein no rows and columns have been replaced with each other.

Next, the element processor 11 a remotely accesses the local memories 11 b to 1 n of the nodes 11 to 1 n, and acquires the arrays R 1 to Rn, the arrays C 1 to Cn and the entry sets E 1 to En therefrom.

Then, the element processor 11 a attains an array R whose j th element R(j) has a value equal to the sum of the j th elements (1 j k) contained in their respective arrays R 1 to Rn.

Moreover, the element processor 11 a attains an array C whose j th element C(j) has a value equal to the sum of the j th elements contained in their respective arrays C 1 to Cn.

Further, the element processor 11 a attains a sum entry set E which corresponds to the sum of the entry sets E 1 to En.

Next, the element processor 11 a selects a variable which can be eliminated with a minimum number of calculations, from among to-be-solved variables which have not yet been eliminated (a step S 230 ).

The number of calculations required to eliminate the S(w) th variable can be derived by R(S(w)) C(S(w)). Hence, in the step S 230 , the element processor 11 a needs only determine the value of w which results in the minimum value of R(S(w)) C(S(w)).

In the step S 230 , the element processor 11 a does not count column entries representing coefficients associated with variables which have already been eliminated or row entries representing equations which have already been solved, nor does it count entries containing diagonal elements.

Next, the element processor 11 a replaces the values of S(i) and S(w) contained in the replacement array S with each other (a step S 240 ).

By so doing, the element processor 11 a replaces the i th row of the entry set E and the row (w th row) representing the variable determined in the step S 230 with each other, and also replaces the it column and the w th column with each other.

Next, the element processor 11 a transmits, as a message, the replacement array S containing the elements replaced with each other to the nodes 11 to 1 n through the mutual coupling network 10 . The element processors 11 a to 1 n a of the nodes 11 to 1 n, which have received the replacement array S, derive fill-ins which take place at the time of eliminating the i th variable from their respective row sets as received, and add entries specifying the derived fill-ins to the entry sets which the element processors 11 a to 1 n a have prepared (steps S 251 to S 25 n).

The positions where the fill-ins take place in the individual row sets can be derived if the entries of all nonzero elements contained in the i th row of the upper right triangular matrix are attained. Accordingly, the element processors 11 a to 1 n a can perform in a parallel fashion the step of adding the entries corresponding to the fill-ins to the entries set E 1 to En.

When the nodes 11 to 1 n have finished the steps S 251 to S 25 n, the element processor 11 a of the node 11 increments the value of the variable i by 1 (a step S 260 ). Further, the element processor 11 a determines whether the value of the variable i exceeds m 1 or not (a step S 270 ).

When the element processor 11 a determines in the step S 270 that the value of the variable i does not exceed m 1 , a return is made to the step S 230 . By repeating the steps S 230 to S 260 , the optimum pivot order and the positions in which the fill-in elements take place can be attained.

When the element processor 11 a determines in the step S 270 that the value of the variable i exceeds m 1, the element processor 11 a remotely access the local memories 11 b to 1 n b of the nodes 11 to 1 n, and acquires the entry sets E 1 to En therefrom. The element processor 11 a compresses the matrix, and stores the compressed matrix data in the local memory 11 b (a step S 280 ).

Such a format as one described in Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (written by R. Barrett et al. and published in 1994), for example, can be adopted as the format in which the matrix data is compressed by the step S 280 .

When the step S 280 has been finished, the symbolic calculation process ends and thereafter the numerical calculation process starts. In this process, the simultaneous linear equations, which the workstation 2 has sent to the parallel computer 1 as the coefficient matrix, are solved.

An example of the process for solving the simultaneous linear equations according to this embodiment will now be explained with reference to FIGS. 4 to

Let it be assumed that the coefficient matrix, sent from the workstation 2 to the parallel computer 1 , is a 6 6 square matrix in which the rows of elements are arranged in the following order as shown in FIG. 4 :

Let it be further assumed that the coefficient matrix shown above is divided into a row set including the upper two rows, a row set including the intermediate two rows, and a row set including the lower two rows, as shown by broken lines in FIG. 4 .

In order to facilitate understanding, let it be further assumed that the row set including the upper two rows is received by the node 11 , the row set including the intermediate two rows is received by the node 12 , and the row set including the lower two rows is received by the node 13 .

In this case, in the steps S 211 to S 213 , the nodes 11 to 13 add the entries specifying the nonzero elements contained in their respective row sets as received to the entry sets E 1 to E 3 , respectively.

As a result, the entry sets E 1 to E 3 stored in the local memories 11 b to 13 b become the following, as shown in FIG. 5 ( a ):

Further, as a result of the addition of the entries to the entry sets E 1 to E 3 , the arrays R 1 to R 3 and C 1 to C 3 stored in the local memories 11 b to 13 b become the following, as shown in FIG. 5 ( a ):

In the step S 220 , the variable i and the replacement array S, stored in the local memory 11 b of the node 11 , are initialized such that they become the following, as shown in FIG. 5 ( a ):

The pivoting process is carried out in the step S 230 . The arrays R and C at that point are as follows:

From the above, the value of w which results in the minimum value of R(S(w)) C(S(w)) is derived as 1.

Next, in the step S 240 , S(i) and S(w) are replaced with each other, and the replacement array S is sent as a message to the nodes 1 to 13 . In this case, however, since i satisfies a relationship of i w 1 when the step S 240 is executed first time, there is no difference between S(i) and S(w).

In the steps S 251 to S 253 , the entries corresponding to fill-ins which take place at the time of eliminating the S(i) th variable are added to the entry sets E 1 to E 3 .

As a result, as shown in FIG. 5 ( b ), the entry sets E 1 to E 3 are updated as follows:

As shown in FIG. 5 ( b ), the individual elements contained in the arrays R 1 to R 3 and C 1 to C 3 are also updated as follows:

In the step S 260 , the variable i is incremented such that it becomes i 2 , as shown in FIG. 5 ( b ). Then, the step S 230 is executed again.

The steps S 230 to S 260 are repeated until the variable i becomes i 5( 6 1). While those steps are being repeated, the entries specifying the fill-ins are added to the entry sets E 1 to E 3 in the steps S 251 to S 253 , as shown in FIG. 6 .

When the variable i has become i 5 , the entry sets E 1 to E 3 , the arrays R 1 to R 3 and C 1 to C 3 , the variable i and the replacement array S are as follows, as shown in FIG. 5 ( c ):

Using the entry sets E 1 to E 3 finally attained through the above-described steps, the matrix data is compressed in the step S 280 as shown in FIG. 7 , and is stored in the local memory 11 b of the node 11 .

The number of entries added to the entry sets E through the above-described steps is 24 , as seen from FIG. 5 ( c ). However, the number of entries added per row set (per node) is 8 .

Accordingly, the storage capacity of the areas which the nodes 11 to 13 need to reserve in their respective local memories 11 b to 13 b in order to store the entry sets E 1 to E 3 , can be reduced to one third of the storage capacity of an area which a single node needs to reserve in its own local memory to store an entry set in the case where the single node executes the above-described steps.

Furthermore, each of the nodes 11 to 13 need not retain the entirety of the coefficient matrix. Each of the nodes 11 to 13 needs only retain a row set whose data amount is one third of the entire coefficient matrix.

Accordingly, the storage capacity of the local memory of each node may be approximately one third of the storage capacity of a conventional local memory. In the case where the storage capacity of the local memory of each node is equal to that of a conventional local memory, then a coefficient matrix which is approximately three times as large as the coefficient matrix of the maximum size which could be conventionally handled, can be dealt with in this embodiment.

Moreover, since the nodes 11 to 13 perform the respective steps S 251 to S 253 in a parallel fashion as shown in FIG. 6 , the number of steps required to add and register the entries is nine in total. In the case where a single node performs the process for adding and registering the entries, seventeen steps are necessary in total. Accordingly, the time required to complete the process for adding and registering the entries according to this embodiment is approximately one second of that in the case where a single node performs the process.

According to this embodiment, as described above, the nodes 11 to 1 n of the parallel computer 1 execute in a parallel fashion the steps of the symbolic calculation process which is the first procedure involved in the process for solving simultaneous linear equations.

In this case, the nodes 11 to 1 n need only store their corresponding row sets forming the coefficient matrix in their respective local memories 11 b to 1 n b . Further, the local memories 11 b to 1 n b need only retain the entry sets which are in one-to-one correspondence with their respective row sets stored therein.

Therefore, the capacity of the local memories 11 b to 1 n b may be smaller than that of a conventional local memory in the case of solving simultaneous linear equations through use of a single coefficient matrix.

When the storage capacity of the local memories 11 b to 1 n b is equal to that of a conventional local memory, then the simultaneous linear equations can be solved using a coefficient matrix larger than that employed conventionally.

Further, the plurality of nodes perform in a parallel fashion the steps of adding the entries to the entry sets E 1 to E 3 . Accordingly, the time required to complete the addition of the entries is shorter than that in a conventional case.

Moreover, by transferring the replacement array S within the node 11 and from the node 11 to the other nodes 12 to 1 n, each of the nodes can derive fill-in elements without having to exchange the matrix or the row sets with each other.

Second Embodiment

Explained in the second embodiment is the case where the present invention is applied to a parallel circuit simulation which involves solving simultaneous linear equations.

In also the second embodiment, the parallel computer 1 illustrated in FIG. 1 can be adopted as hardware which performs a parallel circuit simulation.

In the second embodiment, however, circuit connection information concerning a parallel circuit to be simulated is stored as a library in the external storage device of the workstation 2 . The circuit connection information is read out from the library in accordance with instructions from the input device 21 , and is input to the parallel computer 1 .

A parallel circuit simulation process, which the parallel computer 1 illustrated in FIG. 1 executes in the second embodiment, will now be described with reference to FIG. 8 .

When the process starts, a user supplies the circuit connection information, stored as the library in the external storage device 22 of the workstation 2 , to the parallel computer 1 through the mutual coupling network 10 by operating the input device 21 (a step S 300 ).

Of the element processors 11 a to 1 L a of the nodes 11 to 1 L in the parallel computer 1 , the element processor of the node which has received the circuit connection information divides a circuit specified by the input circuit connection information into a plurality of partial circuits of the same number (i.e., L ) as the number of nodes 11 to 1 L. The division of the circuit into the partial circuits is performed by a method described in, for example, Japanese Patent Publication No. 9-319784. (In order to facilitate understanding, let it be assumed that the node 11 has received the circuit connection information.)

Then, the element processor 11 a of the node 11 transmits information, which specifies each of the partial circuits obtained as a result of the division, to the nodes 12 to 1 L through the mutual coupling network 10 (a step S 310 ). In the node 11 , the information is transmitted by the inter-process communication.

The element processor 11 a of the node 11 and the element processors 12 a to 1 L a of the nodes 12 to 1 L, which have received the information specifying the partial circuits, convert the information (a compiling operation; steps S 321 to S 32 L) to object data (matrices representing the partial circuits and parameters representing the individual elements included in the partial circuits). The steps S 321 to 32 L are those for enabling a simulation, which will be explained later, to be performed with high efficiency.

Further, the element processors 11 a to 1 L a conduct symbol processing to solve simultaneous linear equations associated with the partial circuits specified by the received information. The symbol processing for solving the simultaneous linear equations is performed in accordance with the flowchart of FIG. 8 (steps S 331 to S 33 n).

Using the results obtained by the symbol processing in the steps S 331 to S 33 L, the element processors 11 a to 1 L a perform the numerical calculation process. Thereafter, the element processors transmit the result of the numerical calculation process to one node through the mutual coupling network 10 (steps S 341 to S 34 L) (in order to facilitate understanding, let it be assumed that the element processors transmit the result of the numerical calculation process to the node 11 ). In the node 11 during the step S 341 , the result of the numerical calculation process is transmitted by the inter-process communication.

The element processor 11 a of the node 11 , which has received the result of the numerical calculation process in connection with the partial circuits, performs compiling for a combination circuit and creates a matrix representing the combination circuit, based on the object data representing the degeneracy models of the partial circuits and combination circuit information (a step S 350 ).

Next, the element processor 11 a divides the created matrix into a plurality of row sets. Then, the nodes execute in a parallel fashion the symbolic calculation process for solving combination circuit equations, in accordance with the flowchart of FIG. 8 (step S 360 ).

When the numerical calculation process has been finished and the matrix has been compressed and stored in the step S 360 , the element processor of the node which includes the local memory containing the matrix stored therein, performs the numerical calculation process (a step S 370 ) (the numerical calculation process is shown as the steps S 140 and S 150 in the flowchart of FIG. 2 ).

Having finished the step S 370 , the element processor outputs the result of the calculation process as information showing the waveform of a simulated terminal to the workstation 2 through the mutual coupling network 10 (a step S 380 ). The process shown in FIG. 8 is thus finished.

According to the second embodiment, as described above, the nodes 11 to 1 L perform parallel processing in order to solve the combination circuit equations. This enables the circuit simulation to be performed at higher speed than a conventional circuit simulation. Moreover, the circuit simulation is free from a restriction owing to the capacity of the local memories 11 b to 11 c . Therefore, the circuit simulation can be effected on a large scale.

Modifications of Embodiments

The present invention is not limited to the first or second embodiment described above, and various modifications are possible. Modifications of the embodiments will be now be explained.

In the first embodiment, explanations are made assuming that the coefficient matrix, the processing of which has been requested from the workstation 2 , are divided into n row sets. However, the coefficient matrix which the workstation 2 has requested the parallel computer 1 to process may not be divided into the row sets in advance. In this case, the node which has received the processing request can divide the coefficient matrix into row sets of an arbitrary number equal to or less than the number of nodes of the parallel computer 1 .

In the first and second embodiments, the parallel computer 1 illustrated in FIG. 1 carries out procedures other than the inputting of data (the coefficient matrix of the simultaneous linear equations and the circuit connection information) to be processed.

However, the parallel computer 1 and any other vector calculator may carry out the symbolic calculation process and the numerical calculation process, respectively. Further, the workstation 2 may execute steps other than those to be executed in a parallel fashion, and may request the parallel computer 1 to carry out the steps to be executed in a parallel fashion.

According to the second embodiment, the nodes perform the symbolic calculation process in one-to-one correspondence with the partial circuits in order to the simultaneous linear equations associated with the partial circuits. However, the nodes may perform also the symbolic calculation process in a parallel fashion, as shown in the flowchart of FIG. 3 .

Moreover, the embodiments of the present invention can be realized not only using a dedicated system, but also a general computer system. For example, a symbolic calculation system which executes the above-described operations can be attained by installing a program for executing the above-described operations into a personal computer from a medium (such as a floppy disk or the CD-ROM 3 illustrated in FIG. 9. ) containing the program stored therein.

Further, the medium from which the program is supplied to the computer may be a communication medium (which temporarily stores the program as in the case of a communication line, a communication network and a communication system). For example, the program may be posted on a bulletin board (BBS) for the communication network, and may be distributed through the network.

Moreover, as shown in FIG. 10 , the program can be distributed in the manner of supplying, from a transmitter 4 , for example, a modulated wave obtained by modulating a carrier wave in accordance with the program. In this case, the workstation or any other appropriate unit may receive the modulated wave, demodulate the program, and supply the demodulated program to the local memories 11 b to 1 L b.

The distributed program is run and executed under the control of an OS, in the same manner as other application programs, in order to carry out the above-described processes.

In the case where the OS undertakes the execution of some of the steps involved in the above-described processes or forms a part of one structural element of the present invention, the steps to be executed by the OS may be excluded from the program, and the program from which those steps have been thus excluded may be stored in the medium. In this case also, the program stored in the medium is one for causing the computer to realize individual functions or processes.

According to the present invention, as described above, the time required for completing the symbolic calculation to solve simultaneous linear equations is reduced, while the scale of a matrix which can be handled is enhanced.

Moreover, a large-scale circuit simulation can be effected at high speed.