Symbolic calculation system, symbolic calculation method and parallel circuit simulation system
First Claim
Patent Images
1. A symbolic calculation 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 said element processor, and an interconnection network which interconnects said plurality of nodes, wherein said element processors of said plurality of nodes are capable of cooperating with each other,said symbolic calculation system comprising a first computer which is connected to said 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 said matrix, wherein each of said plurality of nodes corresponds to each row set divided by said first computer, and each of said element processor executes the predetermined program stored in said program area thereby each of said plurality of nodes:
- adds entries specifying nonzero elements contained in the row sets associated with said plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with said 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 said matrix, by cooperating with other nodes;
replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, by cooperating with other nodes;
replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said 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 said matrix including the rows and/or columns replaced with each other, and further adding entries specifying the obtained fill-ins to said plurality of entry sets to said entry sets.
2 Assignments
0 Petitions
Accused Products
Abstract
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.
23 Citations
35 Claims
-
1. A symbolic calculation 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 said element processor, and an interconnection network which interconnects said plurality of nodes, wherein said element processors of said plurality of nodes are capable of cooperating with each other,
said symbolic calculation system comprising a first computer which is connected to said 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 said matrix, wherein each of said plurality of nodes corresponds to each row set divided by said first computer, and each of said element processor executes the predetermined program stored in said program area thereby each of said plurality of nodes: -
adds entries specifying nonzero elements contained in the row sets associated with said plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with said 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 said matrix, by cooperating with other nodes;
replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, by cooperating with other nodes;
replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said 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 said matrix including the rows and/or columns replaced with each other, and further adding entries specifying the obtained fill-ins to said plurality of entry sets to said entry sets. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. 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 said element processor, and an interconnection network which interconnects said plurality of nodes, wherein said element processors of said plurality of nodes are capable of cooperating with each other,
said parallel circuit simulation system comprising a first computer which is connected to said interconnection network, said 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 said plurality of nodes, wherein each of said element processor executes the predetermined program stored in said program area thereby said plurality of nodes: -
executes symbolic calculation on the circuit piece matrix transmitted by said 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, said parallel circuit simulation system comprises;
a second computer which is connected to said 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 said 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 said matrix, and which transmits the plurality of row sets to said plurality of nodes respectively, wherein each element processor executes the predetermined program stored in the program area, thereby each of said plurality of nodes further;
adds entries specifying nonzero elements contained in the row sets associated with said plurality of nodes to a plurality of entry sets which are in one-to-one correspondence with said 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 said matrix, by cooperating with other nodes;
replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, by cooperating with other nodes;
replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said 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 said matrix including the rows and/or columns replaced with each other, and further adds entries specifying the obtained fill-ins to said plurality of entry sets to said entry sets. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A symbolic calculation system for performing 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 said matrix;
a plurality of first entry adders, each of which is associated with one of said plurality of row sets divided by said matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with said plurality of first entry adders to a plurality of entry sets which are in one-to-one correspondence with said 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 said matrix;
a pivot replacer which replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, and replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with said 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 said matrix including the rows and columns replaced with each other by said pivot replacer, and which add entries specifying the obtained fill-ins to said plurality of entry sets to which the entries have been added by said plurality of first entry adders that are in one-to-one correspondence with said plurality of second entry adders. - View Dependent Claims (17, 18, 19, 20, 21, 22)
said pivot replacer comprises a replacement array storage which stores a replacement array specifying the replaced rows and columns included in said matrix, and a supplier which supplies the replacement array stored in said replacement array storage to each of said plurality of second entry adders; and
in accordance with the replacement array supplied from said pivot replacer, each of said plurality of second entry adders obtains the fill-ins associated therewith from said plurality of fill-ins which occur in eliminating the unknown in regard to said matrix including the replaced rows and columns.
-
-
18. The symbolic calculation system according to claim 16, wherein:
-
said symbolic calculation system further comprises a plurality of nodes each including one of said plurality of first entry adders and a corresponding one of said plurality of second entry adders;
the first and second entry adders included in each of said plurality of nodes respectively comprise an in-row entry number storage which stores an in-row entry number array whose elements represent the number of entries contained in each row included in an associated one of said plurality of row sets and an in-column entry number storage which stores an in-column entry number array whose elements represent the number of entries contained in each column included in the associated one of said plurality of row sets; and
said pivot selector comprises a first adder which obtains first addition results by adding together elements corresponding in order to each other, among the elements forming in-row entry number arrays stored in a plurality of in-row entry number storages which said plurality of first entry adders comprise, a second adder which obtains second addition results by adding together elements corresponding in order to each other, among the elements forming in-column entry number arrays stored in a plurality of in-column number storages which said plurality of second entry adders comprise, a multiplier which obtains multiplication results by multiplying together ones of the first and second addition results which correspond to each row-column pair containing a common diagonal element in said matrix, a specifier which specifies to which row-column pair in said matrix a minimum one of values of the multiplication results corresponds, and a determiner which determines, as said first variable, a value representing the row-column pair specified by said specifying means.
-
-
19. The symbolic calculation system according to claim 18, wherein:
-
said pivot replacer comprises a replacement array storage which stores a replacement array specifying the replaced rows and columns included in said matrix, and a supplier which supplies the replacement array stored in said replacement array storage to each of said plurality of second entry adders; and
in accordance with the replacement array supplied from said pivot replacer, each of said plurality of second entry adders obtains the fill-ins associated therewith from said plurality of fill-ins which occur in eliminating the unknown in regard to said matrix including the replaced rows and columns.
-
-
20. The symbolic calculation system according to claim 19, further comprising a matrix compressor which compresses said matrix, based on contents of said plurality of entry sets to which the entries have been added by said plurality of first entry adders and said plurality of second entry adders.
-
21. The symbolic calculation system according to claim 20, wherein said matrix compressor includes a compressor which compresses said matrix by creating data representing elements in said matrix which are specified by the entries contained in said plurality of entry sets to which the entries have been added by said plurality of first entry adders and said plurality of second entry adders.
-
22. The symbolic calculation system according to claim 20, further comprising a numerical value calculator which creates a lower left rectangular matrix and an upper right triangular matrix, based on said matrix as compressed, and performs a forward substitution with respect to said lower left rectangular matrix and performs a backward substitution with respect to said 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.
-
23. A symbolic calculation system for performing a symbolic calculation to solve simultaneous linear equations, comprising:
-
a plurality of first entry adders, each of which is 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 said plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with said 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 said matrix;
a pivot replacer which replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, and which replaces one column specified by said first variable and another column specified by said second variable, among columns of said matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with said 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 said matrix including the rows and columns replaced with each other by said pivot replacer, and which add entries specifying the obtained fill-ins to said plurality of entry sets to which the entries have been added by said plurality of first entry adders that are in one-to-one correspondence with said plurality of second entry adders. - View Dependent Claims (24, 25, 26, 27, 28)
said pivot replacer comprises a replacement array storage which stores a replacement array specifying the replaced rows and columns included in said matrix, and a supplier which supplies the replacement array stored in said replacement array storage to each of said plurality of second entry adders; and
in accordance with the replacement array supplied from said pivot replacer, each of said plurality of second entry adders obtains the fill-ins associated therewith from said plurality of fill-ins which occur in eliminating the unknown in regard to said matrix including the replaced rows and columns.
-
-
26. The symbolic calculation system according to claim 23, wherein:
-
said symbolic calculation system further comprises a plurality of nodes each including one of said plurality of first entry adders and a corresponding one of said plurality of second entry adders;
the first and second entry adders included in each of said plurality of nodes respectively comprise an in-row entry number storage which stores an in-row entry number array whose elements represent the number of entries contained in each row included in an associated one of said plurality of row arrays and an in-column entry number storage which stores an in-column entry number array whose elements represent the number of entries contained in each column included in the associated one of said plurality of row sets; and
said pivot selector comprises a first adder which obtains first addition results by adding together elements corresponding in order to each other, among the elements forming in-row entry number arrays stored in a plurality of in-row entry number storing storages which said plurality of first entry adders comprise, a second adder which obtains second addition results by adding together elements corresponding in order to each other, among the elements forming in-column entry number arrays stored in a plurality of in-column number storages which said plurality of second entry adders comprise, a multiplier which obtains multiplication results by multiplying together ones of the first and second addition results which correspond to each row-column pair containing a common diagonal element in said matrix, a specifier which specifies to which row-column pair in said matrix a minimum one of values of the multiplication results corresponds, and a determiner which determines, as said first variable, a value representing the row-column pair specified by said specifying means.
-
-
27. The symbolic calculation system according to claim 23, further comprising a matrix compressor which compresses said matrix, based on contents of said plurality of entry sets to which the entries have been added by said plurality of first entry adders and said plurality of second entry adders.
-
28. The symbolic calculation system according to claim 27, further comprising a numerical value calculator which creates a lower left rectangular matrix and an upper right triangular matrix, based on said matrix as compressed, and performs a forward substitution with respect to said lower left rectangular matrix and performs a backward substitution with respect to said 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.
-
29. 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 said matrix;
adding, in parallel, entries specifying nonzero elements contained in said plurality of row sets divided by said dividing to a plurality of entry sets which are in one-to-one correspondence with said 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 said matrix;
replacing one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, and replacing one column specified by said first variable and another column specified by said second variable with each other, among columns of said matrix; and
obtaining, in parallel, fill-ins belonging to said plurality of row sets from a plurality of fill-ins which occur in eliminating the unknown in regard to said matrix including the rows and columns replaced with each other by said replacing, and adding, in parallel, entries specifying the obtained fill-ins to said plurality of entry sets to which the entries specifying the nonzero elements contained in said plurality of row sets have been added in parallel. - View Dependent Claims (30)
-
-
31. 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 said partial circuits divided by said circuit divider, and which create partial circuit matrices representing circuit equations of the partial circuits associated with said plurality of partial circuit matrix calculators;
a plurality of partial circuit symbolic calculators, each of which is associated with one of said 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 said plurality of partial circuit matrix calculators;
a plurality of partial circuit numerical calculators, each of which is associated with one of said 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 said 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 said partial circuits, based on solutions of the circuit equations of said partial circuits which have been solved by said plurality of partial circuit numerical calculators;
a combination circuit symbolic calculator which performs symbolic calculations based on the combination circuit matrix created by said combination circuit matrix calculator; and
a combination circuit numerical calculator which solves the circuit equations of said combination circuit by performing numerical calculations using calculation results obtained as a result of the symbolic calculations performed by said combination circuit symbolic calculator;
wherein said combination circuit symbolic calculator comprises;
a matrix divider which divides said combination circuit matrix into a plurality of row sets each comprising at least one of rows of said combination circuit matrix;
a plurality of first entry adders, each of which is associated with one of said plurality of row sets divided by said matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with said plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with said 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 said combination circuit matrix;
a pivot replacer which replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said combination circuit matrix, and which replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said combination circuit matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with said 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 said combination circuit matrix including the rows and columns replaced with each other by said pivot replacer, and which add entries specifying the obtained fill-ins to said plurality of entry sets to which the entries have been added by said plurality of first entry adders that are in one-to-one correspondence with said plurality of second entry adders. - View Dependent Claims (32, 33)
said combination circuit symbolic calculator further comprises a plurality of nodes each including one of said plurality of first entry adders and a corresponding one of said plurality of second entry adders;
the first and second entry adders included in each of said plurality of nodes respectively comprise an in-row entry number storage which stores an in-row entry number array whose elements represent the number of entries contained in each row included in an associated one of said plurality of row sets and an in-column entry number storage which stores an in-column entry number array whose elements represent the number of entries contained in each column included in the associated one of said plurality of row sets; and
said pivot selector comprises a first adder which obtains first addition results by adding together elements corresponding in order to each other, among the elements forming in-row entry number arrays stored in a plurality of in-row entry number storages which said plurality of first entry adders comprise, a second adder which obtains second addition results by adding together elements corresponding in order to each other, among the elements forming in-column entry number arrays stored in a plurality of in-column number storages which said plurality of second entry adders comprise, a multiplier which obtains multiplication results by multiplying together ones of the first and second addition results which correspond to each row-column pair containing a common diagonal element in said combination circuit matrix, a specifier which specifies to which row-column pair in said combination circuit matrix a minimum one of values of the multiplication results corresponds, and a determiner which determines, as said first variable, a value representing the row-column pair specified by said specifying means.
-
-
33. The parallel circuit simulation system according to claim 31, further comprising a matrix compressor which compresses said combination circuit matrix, based on contents of said plurality of entry sets to which the entries have been added by said plurality of first entry adders and said plurality of second entry adders.
-
34. 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 said matrix;
a plurality of first entry adders, each of which is associated with one of said plurality of row sets divided by said matrix divider, and which add entries specifying nonzero elements contained in the row sets associated with said plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with said 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 said matrix;
a pivot replacer which replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, and which replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with said 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 said matrix including the rows and columns replaced with each other by said pivot replacer, and which add entries specifying the obtained fill-ins to said plurality of entry sets to which the entries have been added by said plurality of first entry adders that are in one-to-one correspondence with said plurality of second entry adders.
-
-
35. 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 said matrix;
a plurality of first entry adders, each of which is associated with one of said plurality of row sets divided by said matrix dividers, and which add entries specifying nonzero elements contained in the row sets associated with said plurality of first entry adders to a plurality of entry sets that are in one-to-one correspondence with said 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 said matrix;
a pivot replacer which replaces one row specified by said first variable and another row specified by said second variable with each other, among the rows of said matrix, and which replaces one column specified by said first variable and another column specified by said second variable with each other, among columns of said matrix; and
a plurality of second entry adders, provided in one-to-one correspondence with said 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 said matrix including the rows and columns replaced with each other by said pivot replacer, and which add entries specifying the obtained fill-ins to said plurality of entry sets to which the entries have been added by said plurality of first entry adders that are in one-to-one correspondence with said plurality of second entry adders.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeNEC Electronics Corporation (Renesas Electronics Corporation)
-
Original AssigneeNEC Electronics Corporation (Renesas Electronics Corporation)
-
InventorsHachiya, Koutaro
-
Primary Examiner(s)Broda, Samuel
-
Assistant Examiner(s)PHAN, THAI Q
-
Application NumberUS09/307,977Time in Patent Office1,625 DaysField of Search703/2, 708/446, 708/7, 712/7, 712/35, 712/203US Class Current703/2CPC Class CodesG06F 17/12 Simultaneous equations , e....
