Method and apparatus for circuit simulation using parallel processors including memory arrangements and matrix decomposition synchronization

• US 5,157,778 A
• Filed: 04/23/1990
• Issued: 10/20/1992
• Est. Priority Date: 08/20/1986
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Greenberg, Steven S., Bischoff, Gabriel P.
• Primary Examiner(s): Anderson, Lawrence E.
• Assistant Examiner(s): MOHAMED, AYNI Y
• Application Number:
  US07/513,017
• Time in Patent Office: 911 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/750.5, 395/800, 395/500
• US Class Current: 703/14
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A digital data processing system including a plurality of processors processes a program in parallel to load process data into a two-dimensional matrix having a plurality of matrix entries. So that the processors will not have to synchronize loading of process data into particular locations in the matrix, the matrix has a third dimension defining a plurality of memory locations, with each series of locations along the third dimension being associated with one of the matrix entries. Each processor initially loads preliminary process data into a memory location along the third dimension. After that has been completed, each processor generates process data for an entry of the two-dimensional matrix from the preliminary process data in the locations along the third dimension related thereto. Since the processors separately load preliminary process data into different memory locations, along the third dimension, there is no conflict with accessing of memory locations among the various processors during generation of preliminary process data. Further, since the processors can separately generate process data for different matrix entries from the preliminary data, there is no conflict in accessing of the memory locations among the various processors during of the process data.

Claims

1. In a digital data processing system including a plurality of processors which operate in parallel to produce a set of data results and store said data results in a corresponding set of entries in a memory shared by said processors, addresses of said set of entries being arranged so that the stored set of data results represents a two-dimensional matrix, a computer-implemented method for generating said data results comprising the computer-implemented steps of

assigning multiple storage locations in said memory for at least some of said set of entries,

generating with said processors a plurality of partial results to be used to format least some of said set of data results, and storing the partial results for a given data result in the multiple storage locations assigned to the entry that corresponds with said given data result, whereby multiple processors can access the memory simultaneously to store said partial results for said given data result, and

generating with said processors said data results for said entries based on the partial results that have been stored in the multiple storage locations assigned to each said entry, and storing said data results in said set of entries.

2. The method of claim 1 wherein the step of generating said data results includes summing said partial results stored in said multiple storage locations assigned to at least one of said entries.

3. In a digital data processing system including a plurality of processors which operate in parallel to produce a set of data results and store said data results in a corresponding set of entries in a memory charted by said processors, addresses of said set of entries being arranged so that the stored set of data results represents a two-dimensional matrix in a first area of said memory, an arrangement for generating said data results comprising

a second, working area of said memory that includes multiple storage locations assigned to at least some of said set of entries,

said processors including:

means for generating a plurality of partial results to be used to format least some of said set of data results and for storing the partial results of a given data result in the multiple storage locations assigned to the entry that corresponds with said given data result, whereby multiple processors can access the memory simultaneously to store said partial results for said given data result, and

means for generating said data results for said entries based on the partial results that have been stored in the multiple storage locations assigned to each said entry, and for storing said data results in said set of entries.

4. The system of claim 3 wherein said means for generating said data results includes means for summing said partial results stored in said multiple locations assigned to at least one of said entries.

5. In a digital data processing system including a plurality of processors and memory shared by the processors, a computer-implemented method for controlling said system to solve multivariable circuit equations for circuits having a plurality of nodes at least some of which have a plurality of circuit elements connected thereto, comprising the computer-implemented steps of

establishing in said memory a set of entries the addresses of which are arranged so that the entries represent a two-dimensional matrix, each one of said entries corresponding to one of said nodes,

assigning multiple storage locations in said memory for at least some of said set of entries, each one of said multiple storage locations for any entry corresponding to one circuit element connected to the node that corresponds to said entry,

generating with said processors in parallel a plurality of partial results for said circuit elements, and storing the partial results in said memory such that the partial results for the circuit elements connected to a given node are stored in the multiple storage locations assigned to the entry corresponding to said node, whereby multiple processors can access the memory simultaneously to store the partial results for said entry, and

generating with said processors data results for said nodes based on the partial results that have been stored in the multiple storage locations assigned to the respective entries that correspond with said nodes, and storing said data results in said set of entries.

6. The method of claim 5 wherein the step of generating said data results includes summing said partial results stored in said multiple locations assigned to at least one of said entries.

7. In a digital data processing system including a plurality of processors and a memory shared by the processors, an arrangement for controlling said system to solve multi-variable circuit equations for circuits having a plurality of nodes at least some of which have a plurality of circuit elements connected thereto, comprising

a set of entries in a first area of said memory the addresses of which are arranged so that the entries represent a two-dimensional matrix, each one of said entries corresponding to one of said nodes,

a second, working area of said memory that includes multiple storage locations assigned to at least some of said set of entries, each one of said multiple storage locations for an entry corresponding to one circuit element connected to the node that corresponds to said entry,

said processors each including:

means for generating, in parallel with other said processors, a plurality of partial results for said circuit elements and for storing the partial results in said second area of memory such that the partial results for the circuit elements connected to a given node are stored in the multiple storage locations assigned to the entry that corresponds to said node, whereby multiple processors can access the memory simultaneously to store the partial results for said entry, and

means for generating data results for said nodes based on the partial results that have been stored in the multiple storage locations assigned to the respective entries that correspond to said nodes, and storing said data results in said set of entries.

8. The system of claim 7 wherein said means for generating said data results includes means for summing said partial results stored in said multiple locations assigned to at least one of said entries.

9. In a digital data processing system including a plurality of processors which operate in parallel to produce a set of data results and store said data results in a memory shared by said processors, a computer-implemented method comprising the computer-implemented steps of

generating with said processors multiple partial results for at least some of the set of data results, and storing said partial results in corresponding to multiple storage locations in said memory such that multiple processors can access the memory simultaneously to store their partial results,

enabling said processors to generate said set of data results based other partial results that have been stored in said memory and to store said data results in a set of entries in said memory, said set of entries having addresses that correspond to each other so that the stored set of data results represents a two-dimensional matrix, and

processing, with at least one of said processors, said data results to solve a plurality of multi-variable equations represented by said matrix.

10. In a digital data processing system including a plurality of processors which operate in parallel to produce a set of data results and store said data results in a memory shared by said processors, an arrangement comprising

means for generating multiple partial result with said processors for at least some of the set of data results and storing said partial results in corresponding multiple storage locations in said memory such that multiple processors can access the memory simultaneously to store their partial results,

means for enabling said processors to generate said set of data results based on the partial results that have been stored in said memory and to store said data results in a set of entries in said memory, said set of entries having addresses that are arranged so that the stored set of data results represents a two-dimensional matrix, and

means for processing said data results with at least one of said processors to solve a plurality of multi-variable equations represented by said matrix.