SUMMARY

This paper presents a two-level parallel implementation of a hierarchical symbolic analysis algorithm (SCAPP) on a 128 node nCUBE hypercube class parallel processor. The algorithm operates on a partitioned circuit and subdivides the processing into an outer-parallelism level and an inner-parallelism level. The algorithm can collapse to only one of the two levels based on program control and availability of processors. Each subcircuit is allocated a subcube of size one or larger and then the matrix operations are parallelised on that subcube. The algorithm is applicable to any general message passing multi-processor architecture.

I. INTRODUCTION

VLSI designers are continuously seeking faster and more efficient circuit simulation techniques for verification of both, analog and digital, integrated circuits. The current state-of-the-art in circuit simulation falls short in attempting to satisfy all the needs of today's VLSI designs. Circuit size and long simulation times have a large contribution to these shortfalls. Therefore, a major concentration of efforts now-a-days is on the reduction of overall simulation times. One of the most promising options for achieving this goal is the design of parallel algorithms that exploit parallelism in the various circuit simulation algorithms [1,2,3,4].

Symbolic circuit analysis is a simulation technique which attempts to obtain expressions for circuit variables where one or more components can be represented by symbols. Most symbolic analysis methods address circuit operation in the frequency domain [5,6,7,8,9,10,11,12,13]. However, some researchers have investigated symbolic analysis in the time domain [14, 15]. All of these methods use one of two approaches to dealing with the symbolic expressions: 1) A single expression approach where the entire function is represented by one numerator over denominator equation [16,17]. 2) A sequence of expressions approach where the transfer function is an upwardly dependent hierarchical set of equations as illustrated in example 1 (section 3) [5,6].

In this paper, a parallel implementation of the symbolic circuit simulator SCAPP (Symbolic Circuit Analysis Program with Partitioning) is presented [5,18]. SCAPP generates the frequency domain network functions for large-scale circuits. The algorithm utilises the concepts of hierarchical partitioning and hierarchical sequence of expressions to obtain the symbolic expressions for circuit variables. The number of expressions generated by SCAPP is bounded by a worst case quadratic growth as opposed to the exponential growth exhibited by other simulators introduced in past [19,20,21,22,23,24]. The basic serial algorithm was introduced in [5,18], and is summarised in Figure 1

The SCAPP algorithm consists of three major steps: Hierarchical partitioning, terminal block analysis and middle block analysis.

1. Hierarchical partitioning: This step involves identifying user defined partitions in the circuit and automatically partitioning the circuit. This is a binary partitioning scheme with capabilities of producing balanced binary tree partitions (Figure 2) [25].
2. Terminal block analysis: This analysis generates the sequence of expressions for each subcircuit independent of other subcircuits. This is the very basic property of the algorithm that makes it very suitable for parallel implementations. The analysis method is based on the concept of modified nodal analysis (MNA) [26], and reduced modified nodal analysis (RMNA) in [5]. After a circuit is partitioned using a node tearing algorithm, into p parts, each subcircuit is modeled as an n-terminal block, where the external variables are the node-to-datum voltages of the tearing nodes in addition to some branch current variables, and the internal variables are node-to-datum voltages of internal nodes plus some branch current variables. The MNA equations can be written as


where Y_n is the nodal admittance matrix (a function of the frequency variable s) that, with B, form the KCL equations for the circuit, I is the vector of branch current variables, E is the independent voltage source values, and C and D correspond to the branch relationship equations whose currents are in I. All type of dependent power sources are allowed in the analysis. The RMNA matrix is then obtained as the final representation of the block. The RMNA equations are



where I_e is the vector of external current variables, and V_e is the vector of external node variables. The ith entry of the J_e vector represents the currents entering the n-terminal block through the ith terminal, or in other words entering the ith node from another block or a power source (internal or external). E_e represents the contribution of both, external and internal, independent voltage sources to this block. The process of producing the RMNA matrix form the MNA matrix is done by successive elimination (suppression) of the rows and columns corresponding to the internal variables of the block. To reduce internal variable i (ith row and column), the following equation is used (A_Rhere represents the reduced MNA matrix and will be the RMNA matrix after the successive application of the equation to reduce all internal variables)



where a_ii is in the ith row and the ith column of A_R, A_cr is A_R with the ith row and ith column removed, and R_i and C_i are the ith row and column, respectively, with aii removed. By using the equation to suppress all internal variables, the resulting matrix is the RMNA matrix which is a compact representation of the subcircuit in terms of only its external variables.

3. Middle block analysis: This step combines solutions from terminal block analysis in a hierarchical manner, suppresses all the variables which are not requested by the analysis and generates expressions for the requested variables. The combination process for the RMNA matrices generated from the terminal block analysis is done by merging the matrices and then adding the rows corresponding to the KCL equations at the tearing nodes together, and adding the columns corresponding to the tearing nodes together. The result is a new RMNA matrix characterisation for the combined subcircuits. Now the terminal block analysis suppression process cab be applied to the new matrix.

A detailed description of the entire algorithm can be found in [5,17].

2. IDENTIFICATION OF PARALLELISM

Traditionally, serial algorithms have been independent of the architecture of the machine on which they are run. This is not the case for parallel algorithms. Finding a match between a parallel algorithm and hardware architecture is crucial to the success of parallelisation. Keeping this in mind, we attempt to identify parallelism as well as the best architecture for implementation. There are two major areas where the algorithm can be parallelised:

1. Outer Parallelism: The terminal block analysis can be completely parallelised. This is due to the fact that terminal blocks generated by the SCAPP partitioner can be analysed independent of each other. This is the outer parallelism, a direct benefit of partitioning the network.
2. Inner Parallelism: The MNA matrix generated by terminal block analysis can be reduced in parallel (equation 3). This can not be completely parallelised because of the data dependency between reduction steps. Nevertheless, partial speedups can be obtained by parallel reduction. This is inner parallelism.

Both inner and outer parallelisms are coarse grained tasks requiring very little inter-processor communication. This is well suited for the message passing parallel processors. Considering these facts and machine accessibility criteria, the nCUBE parallel processor with 128 nodes was chosen to be the parallel machine for implementing the algorithms. A description of the machine follows.

The nCUBE-2 parallel processor [27] is a member of Hypercube Multiple Instruction Multiple Data (MIMD) parallel computers consisting of up to 8192 nodes connected by a hypercube network. Each node of the machine is capable of delivering 2 MIPS and is equipped with 16 Mbytes of memory. In addition to large processing power, large I/O bandwidth is also provided. The hypercube communication network and dedicated hardware reduces communication overhead by providing log order broadcast operations. A typical broadcast operation of nCUBE is shown in Figure 3 which illustrates the steps required to broadcast a message to 8 processors.

A Sun workstation serves as the front end host processor (Figure 4). The host interface supports a UNIX like operating system, Axis. Vertex is the operating system running on the node processors. Synchronisation between node tasks is achieved by message passing mechanisms. The software support includes a set of library routines which can be called from C or FORTRAN providing mechanisms for allocating processors, loading tasks on processors and message passing between processors.

3. THE PARALLEL ALGORITHM

One of the most frequently used strategy for designing parallel algorithms is the divide and conquer strategy. In this method, the problem is broken down so as to fit nicely in the multiple processor model with minimum boundary conditions and good load balance. The analysis is carried out on the parts of the problem independent of each other. Any synchronisation between the tasks is achieved by message passing. Finally a recombination step is performed to take care of the boundary conditions. This model of computation matches the SCAPP algorithm. The following subsections illustrate how this partition-analyse-recombine strategy is adopted in this algorithm.

3.1 Partitioning

The solution to the problem of finding an optimal partition of a network is NP- complete [28]. Therefore, it is an impractical task to obtain an optimal solution for large networks. The problem is compounded by the fact that a multiple processor machine with p processors ideally requires p partitions in order to maximise efficiency and minimise computational time. Several heuristic partitioning algorithms that produce near optimal solutions in acceptable time have been discussed in the literature [29,30,31,32]. Focusing on hypercube class of processors where p is always a power of two, a partitioning scheme that produces a power of two equal sized partitions can be considered a near-optimal solution. The partitioning algorithm described in [25] is found to be suitable for this purpose. In order to keep a good load balance, the size of partitions is chosen to be a dominant partitioning criteria. Size of partitions is measured in terms of number of branches in a partition.

An obvious way of parallelising the partitioner is to divide the network into two using one processor, then divide these partitions into four using two processors and so on till P partitions are obtained. Although the scheme appears to be simple and reducing time complexity by a log factor, this is not the case. To see this fact, time complexity of both serial and parallel algorithms are obtained. The serial binary partitioning algorithm has a worst case time complexity of O(n²) where n is the problem size (For most practical circuits, the complexity of the partitioner is found to be linear [25]). The results obtained in this section hold good for this case too). The partitioner divides the problem into two problems of size n/2 each. The expressions for serial time (T_s) and parallel time (T_p) are given in equations (4) and (5), respectively.

From above expressions, it can be seen that for large number of partitions, both serial and parallel algorithms approach the same time complexity. The reason for this is the low utilisation of processors. This analysis is valid for any binary partitioning algorithm. The point is that trying to convert a serial algorithm directly into parallel algorithm need not necessarily result in large speedups. Another important point to consider here is the fact that most circuits that will benefit from the parallelisation are already pre-partitioned by design. This is because (as will be seen in the experimental results) in order to achieve practical parallelisation speedups, the size of each partition has to be large enough to prevent processor communication time from dominating the overall analysis time and therefore only large circuits will be analysed. These large circuits will be, by design, hierarchically organised (a sound and basic design practice), and hence large circuits are always pre-partitioned. Extra partitioning can always be performed on the subcircuits in order to achieve a better balance of the size of the partitions to keep all the processors busy. To eliminate the time to communicate partitions to relevant processors from partitioning processor, it was decided that each processor perform partitioning on its own and keep the relevant partitions.

3.2 Terminal Block Analysis

Once partitioning has been performed, the next step is to schedule terminal blocks to processors and reduce them in parallel. The scheme proposed here can allocate any number of partitions to any number of processors but utilisation can be maximised if number of partitions is a power of two. In order to describe the scheme, let us define p as number of processors available and P as the number of partitions. There can be three cases: p>P, p=P and p<P. The partitioner can be constrained to produce one of the first two cases. But the last case might occur for user defined partitions.

• case 1. (p > P): In this case, the hypercube is divided into P subcubes, each consisting of p/P processors. All the processors in a subcube operate on same terminal block and all the subcubes operate concurrently to reduce the terminal block using parallel reduction algorithm.
• case 2. (p=P): This is the best case for parallel algorithm. Here one terminal block is assigned to each processor. The processors carry out terminal block analysis independent of each other using serial reduction algorithm.
• case 3: (p < P): In this case, each processor performs terminal block analysis on a set of P/p terminal blocks. The reduced MNA matrix for each terminal block is stored in memory. Once all the terminal blocks belonging to one processor have been processed, the reduced MNA matrices are combined locally to produce single RMNA which is used in the recombination step.

Once scheduling of terminal blocks to processors is completed, the analysis begins with construction the MNA matrix for each terminal block. Two schemes for reducing the MNA matrix have been implemented. In the first case, there is only one processor performing reduction of the entire MNA matrix The algorithm for this scheme is exactly same as the serial algorithm used in SCAPP. The second scheme is followed in the case where a subcube with two or more processors is allocated for each terminal block analysis. This algorithm is described in following sections.

The parallel implementation of reduction of MNA matrix on a subcube consists of a controller node and worker nodes. The controller node is responsible for interfacing with the partitioning module and recombination module. This node generates a compact representation of the MNA matrix for the subcircuit assigned to the subcube. This matrix is in a form suitable for minimising communication overhead and termed as IMNA matrix. The controller node determines order of rows to be reduced and the columns to be used to reduces the rows. After completion of reduction of a row, this node writes the reduction equations to permanent storage. Figure 5 lists the steps of controller node.

The worker nodes are actually responsible for reducing the IMNA matrix. The rows of IMNA matrix are uniformly divided between these workers. The row being reduced and the column used to reduce the row are termed current row and current columns respectively. Controller node broadcasts the current row and column numbers to all workers. On receiving the row number, the worker node holding the row broadcasts the row contents to all other workers. Once current row has been received by the workers, reduction proceeds without any further communication. The reduction equations are sent back to the controller in a compact form. The controller node is responsible for decoding the compact equations and for writing them to the permanent storage unit. Figure 6 lists the steps performed by the workers.

Example 1:Consider the ladder network in Figure 7. The Symbolic MNA Matrix for the circuit is shown in Figure 8. The Initial IMNA Matrix and assignment of rows to processors is shown in Table 1. The reduction list is nodes {3,4,5}. These also refer to the rows to be suppressed. The initial symbolic sequence of expressions is shown in Table 2, and Table 3 shows the progression of the parallel algorithm.

This step involves combining RMNA matrices for different terminal blocks. A few observations can be made here. 1) Generally only a small fraction of the total network variables will be required by the analysis. 2) The goal of partitioning is to minimise number of tearing nodes. 3) Sending short messages is expensive for hypercubes because of setup overheads. 4) Hierarchical recombination results in low utilisation. These observations suggest that timing requirements for middle block analysis are small compared to other timings and it is not critical to perform middle block analysis in parallel. Experimental results confirm these observations. So it was decided to perform the middle block analysis on a single processor. All the nodes having a RMNA matrix send the matrix to the controller node in the form of single message. Controller node analyses these matrices and produces equations to reduce the RMNA matrices.

4. Speedup Analysis

The algorithm consists of serial portions as well as parallel portions. Speedup analysis is performed for the parallel sections. The actual execution time of the algorithm is equal to sum of serial time and longest parallel time. Several assumptions are made in computing theoretical speedup of the algorithm. They are:

1. Communication time is not critical: On nCUBE, broadcast operation occurs in log time on very fast communication medium. So as long as the communication is a small fraction of overall computation time this assumption remains valid.
2. Number of branches incident at a node in a circuit is a constant bounded within a constant MAX_BRANCHES_PER_NODE which in most of the circuits is approximately 4.
3. Each processor has enough memory to hold the rows assigned to it and buffer the equations for one reduction step. nCUBE processors come with enough memory to buffer large amounts of temporary data. This assumption is valid for sparse matrix reduction.
4. I/O time and parsing time is not considered: I/O can not be parallelised because the nCUBE has a single disk. Since parsing is a small fraction of overall processing, it is not considered.
5. Number of nodes in the circuit is much greater than number of processors: This assumption is justified by the fact that we are targeting large networks on a coarse grain parallel processor having a small to medium number of processors.

4.1 Speedup For Parallel Terminal Block Analysis

Figure 9 gives a scheduling diagram for serial and parallel terminal block analysis algorithms. The serial computation time of the algorithm is of order O (n²). This results in a maximum number of nodes in each processor equal to n / p. The time complexity of the analysis on a p processor machine is O (n² / p). The speedup is on the order of O(p) (Serial time / Parallel time) = n² / n²/p)

4.2 Speedup Due to Partitioning

Let n, p and P denote circuit size, number of processors available and number of partitions, respectively. The serial communication time is the time required to perform P terminal block analyses and is on the order of

Speedup is computed for three cases: P=p P<p and P>p.

• case 1: (P=p): In this case, the parallel time is the time required to perform one terminal block analysis. So the average speedup obtained is

• case 2: (P<p): Here each terminal block is assigned to p /P processors. The parallel time is the time needed to perform terminal block analysis on a terminal block of size n/P using p/P processors, which is given by O((n/P)² / p/P) = O(n² / Pp).

  Therefore, speedup for this case is


• case 3: (P>p): Here each processor is responsible for P/p terminal blocks. The parallel time is O((n/P)² * P/p) giving a speedup of

The main point is that if we can partition the network into power of two partitions with equal size, linear speedup can be obtained on Hypercube machines, no matter what the cube size is. However, as the number of processors increase, the ratio of partitioning time to analysis time starts growing and at some point becomes a significant portion of the overall analysis time. Similarly the broadcast time for large cubes is considerably larger and the assumption that communication time is small becomes invalid. These observations are discussed in detail in next section.

5. EXPERIMENTAL RESULTS

The parallel implementation of SCAPP was run on a set of test circuits. The following examples illustrate the performance and highlights the class of circuits for which the parallelisation is most suitable.

1. Band-pass filter: Consists of 5 stages and 32 nodes (Figure 10).
2. Ladder Network: Ladder of conductances consisting of 200 nodes (Figure 7).
3. Mesh: Network: Mesh of heavily interconnected conductances (Figure 11).
4. Cascade Amplifier: A chain of OPAMP amplifiers with 200 stages (Figure 12).

Timing measurements were performed on the controller node (node 0, Figure 4). The results obtained here are worst case times because the controller waits for termination the algorithm on all nodes before recording the timing information. The time recorded is the clock time as opposed to processor CPU time and hence it includes most of the overhead like buffering and waiting for messages.

It can be seen from the results in Table 4 and Figures 13 and 14, that the best speedup and efficiency is obtained when the number of partitions is equal to the number of processors available. This is due to the fact that the different terminal block analyses are independent of each other and, therefore, require no communication between processors during the analysis of the individual partitions (a property of the symbolic algorithm).

The band-pass filter (Figure 10) does not show considerable speedup. This is because this circuit is too small to be analysed in parallel. The communication and set up overhead is very high compared to analysis time. The same is true for the amplifier circuit (Figure 12) because the analysis time, a function of the interconnectivity of circuit components, is small.

The ladder and mesh circuits (Figures 7 and 11, respectively) show good speedups. This is due to the size of the networks and the dense interconnection pattern. For the ladder circuit the best figure is a speedup of 7.03 with 8 processors. For the mesh circuit, the best figure is a speedup of 9.87 with 16 processors (although 32 processors give a slightly higher speedup, 10.32, the cost is 16 extra processors which makes the 16 processor case more attractive).

6. CONCLUSIONS

The implementation of SCAPP on an nCUBE parallel processor was successful. Although the results shown in Table 4 cannot be used as a complete set of information, they are a good representation of expected results for most circuits. The results show the feasibility of performing symbolic analysis on multi-processor machines. The following comments summarise the conclusions:

1. A good partitioning scheme is very important for gaining maximum speedups. This can be achieved when number of partitions matches number of available processors, relatively equal size partitions are used, and the size of each partition is large enough to prevent communications overhead from dominating the analysis process.
2. There is a saturation limit for the ideal p (number of processors) needed to achieve maximum speedup. That number depends on broadcast time, setup time and execution time for each particular circuit or class of circuits.
3. From experimental results, large speedups can be achieved using a relatively low number of processors (8-16 processors).
4. Broadcast time will dominate if a large number of processors are used and can result in execution times larger than the serial time.
5. For our experimental results, a speedup of 7.03 on 8 processors was obtained for cascaded classes of circuits and a speedup of 9.87 on 16 processors was obtained for mesh networks (heavily interconnected circuits).

ACKNOWLEDGMENT

The above work was partially supported by a grant from the Engineering Research Institute at Iowa State University, Ames, Iowa, USA. The authors wish to thank Ames Laboratory (a Department of Energy research center) for the use of their 128 node nCUBE machine. The authors also wish to thank Dr. Gurpur Prabhu, Dr. James Davis and Dr. John Gustafson for their consultations.

REFERENCES

*Row pivot expression **note C syntax reduces symbol length

---

Table 4 Experimental results
Circuit		Filter		Ladder		Mesh		Amplifier
Nodes		32		202		256		202
Equations		78		1188		13719		298
p1	Parts2	Time 3	Speedup4	Time3	Speedup4	Time3	Speedup4	Time3	Speedup4
1	1	2.8	1.00	112.2	1.00	334.5	1.00	27.7	1.00
2		2.3	1.22	103.5	1.09	306.1	1.09	26.5	1.05
4		2.2	1.27	85.5	1.31	256.1	1.31	22.4	1.24
8		2.3	1.22	80.4	1.40	207.2	1.61	21.5	1.29
16		2.5	1.12	102.3	1.10	241.1	1.39	21.8	1.27
32		2.7	1.04	107.1	1.05	295.3	1.13	23.2	1.19
1	2	1.0	1.00	60.3	1.00	260.1	1.00	8.2	1.00
2		0.7	1.43	34.5	1.75	137.3	1.89	8.2	1.00
4		0.9	1.11	42.6	1.42	123.4	2.11	7.7	1.06
8		0.9	1.11	27.5	2.19	103.1	2.52	6.8	1.21
16		0.9	1.11	30..0	2.01	102.3	2.54	6.7	1.22
32		1.0	1.00	36.6	1.65	183.7	1.42	7.0	1.17
1	4	0.4	1.00	48.4	1.00	76.8	1.00	2.8	1.00
2		0.4	1.00	24.3	1.99	68.8	1.12	2.8	1.00
4		0.3	1.33	12.9	3.75	31.3	2.45	2.8	1.00
8		0.4	1.00	11.9	4.06	15.9	4.83	2.6	1.08
16		0.4	1.00	10.5	4.61	14.9	5.15	2.4	1.17
32		0.4	1.00	10.6	4.57	13.4	5.73	2.5	1.12
1	8	0.2	1.00	35.9	1.00	67.1	1.00	1.2	1.00
2		0.2	1.00	18.2	1.97	40.4	1.66	1.2	1.00
4		0.2	1.00	12.8	2.80	25.5	2.63	1.2	1.00
8		0.1	2.00	5.1	7.03	17.9	3.75	1.1	1.09
16		0.2	1.00	4.8	7.48	6.8	9.87	1.2	1.00
32		0.3	0.66	3.8	9.45	6.5	10.32	1.1	1.09

1 p is number of nCUBE processors.
²Parts is number of circuit partitions.
³ Time is processor run time in seconds.
⁴ Speedup is calculated as Run Time for 1 Processor/Run Time for p Processors.

---

Step 1: Hierarchical partitioning of the circuit (or recognising already pre-partitioned subcircuits) Step 2: Terminal Block Analysis: (Symbolic generation of sequence of expression for each subcircuit) 2.1. Build Symbolic MNA matrix 2.2. Reduce MNA matrix to a RMNA matrix by suppressing all internal variables. Step 3: Middle Block Analysis: 3.1 Combine solutions from terminal block analysis of subcircuits in a hierarchical manner. 3.2 Reduce the matrix to a final RMNA matrix by suppressing all internal variables.

Figure 1. SCAPP Serial Algorithm

---

Figure 2: Partitioning and analysis model of SCAPP

---

Figure 3: Typical nCUBE Data Broadcast Operation

---

Figure 4: Configuration of nCUBE-2 with 23 processors

---

Step 1: Build IMNA matrix from SCAPP MNA matrix such that a non zero entry of MNA is represented as 1 and a zero entry of MNA matrix is represented by 0 in IMNA Step 2: Load all rows of IMNA onto nCUBE nodes such that row r is assigned to processor (r mod p) Step 3: For each row r to be reduced, do the following: 3.1 Broadcast row and column numbers for current row to be reduced 3.2 Receive equations from nodes 3.3 Output equations

Figure 5. Controller algorithm for terminal block analysis

---

Step 1: Receive rows of IMNA matrix designated for processor i Step 2: Receive total rows, number of rows to be reduced. Step 3: For each row to be reduced, do the following 3.1 Receive current row and column number. 3.2 If processor i holds current row, broadcast this row else receive current row. 3.3 For rows held by processor i, Compute equations to reduce current row, and the non zero elements for next reduction step 3.4 Send equations to node 0

Figure 6. Worker algorithm for terminal block analysis

---

Figure 7: Ladder Network for example 1

---

col 2	col 3	col 4	col 5	col 6	col 7
R2C2	R2C3	0	0	0	0	(row 2)
R3C2	R3C3	R3C4	0	0	0	(row 3)
0	R2C3	R4C4	R4C5	0	0	(row 4)
0	0	R5C4	R5C5	R5C6	0	(row 5)
0	0	0	R6C5	R6C6	R6C7	(row 6)
0	0	0	0<	R7C6	R7C7	(row 7)

Figure 8: Symbolic MNA Matrix for example 1

---

Figure 9: Timing diagrams for serial and parallel terminal block analysis

---

Figure 10: Band-pass filter [6]

---

Figure 11: Mesh Network

---

Figure 12: One stage of the cascaded amplifier circuit

---

Figure 13: Speedup vs. number of processors for 8 partitions

---

Figure 14: Best speedup vs. number of partitions
(the number of processors used to achieve a given speedup is indicated on each column)

---

Pages prepared by maria
June 1998