example, in a DRAM circuit with 7,000 transistors, broken into 191 subcircuits, the interconnection matrix is about 200 by 200, with about 20% of its entries nonzero. [Research based on the same mathematical foundations, but without the multiple hierarchy of subcircuits, is being done at Texas Instrument Corp. (Ref 5).]

Consideration of the form of the algorithm suggested that for many problems the subcircuit processors would compute independently and then all communicate to the interconnecon processor, which would then compute and finally communicate back to the subcircuit processors. Thus it will mostly be the case that communication is many-to-one or one-to-many. Nakata felt that a bus structure had better throughput than more general organizations, such as a hypercube. He also felt that shared memory would be more efficient than message passing systems. In 1987 the NEC group developed a prototype system composed of four processors. From that experience they have developed a 64-processor system, called Cenju, after the Buddhist goddess with 1,000 arms. (Nakata feels that the maximum number of processors that can effectively be used on circuit problems is about 100.) He decided to use a distributed-shared memory. This means that there is a unique global address for the local memory in each processor, and that each processor has a local memory bus so it can access its local memory without worrying about bus contention. Since some interprocessor communication occasionally takes place, and building a common bus with high data-transfer-rate suitable to so many processors was difficult, he has designed the data bus in a hierarchical (tree-like) form.

Cenju is thus composed of 64 processors. These are divided into eight "clusters." Processors in a cluster are connected by a bus that is connected via a multistage network. Each processor

is built around a 20-MHz Motorola
MC68020 CPU that has 4 MB of dual-
ported local memory connected by a
local memory bus. The cluster bus only
needs to be accessed when communi-
cating with other processors. The design
allows up to 256 processors. Since
floating point computation is a funda-
mental part of circuit simulation, Nakata
decided to use fast Weitek WTL1167
chips instead of the Motorola MC68882
chips that are most commonly used
with MC68000 systems. An MC68882
is on the board and is used for math
functions such as sin, cos, exp, etc., but
floating point addition, subtraction,
multiplication, and division are done
through calls to the Weitek chip. Other
details of the hardware organization
can be found in Reference 6.

Nakata is a computer architect, not
a numerical analyst or a circuit designer.
In developing Cenju, he collaborated
heavily with Norio Tanabe, who has
been doing circuit simulation for many
years and is in NEC's VLSI CAD
years and is in NEC's VLSI CAD
Engineering Division. Some of the
aspects of the algorithm were done in
collaboration with other scientists in
NEC's Computer and Communication
Systems Research Division and Scien-
tific Information System Development
Ltd. (a subsidiary). For complete
addresses, see References 4 and 6.

191 for the second. When there are more subcircuits than processors, there is quite a bit of extra overhead and Nakata feels that this accounted for some degradation in performance; the matrix problem to be solved for the interconnection matrix is larger and the matrix has about 20% nonzero elements. Its solution is done serially with respect to the other phases of the calculation. Nakata feels that additional improvements would occur if the domain decomposer was more sophisticated and produced fewer subcircuits as this would directly reduce the size of the matrix. He has also made some initial efforts to parallelize solving the matrix problem, and work in this direction has improved the speedup for the large problem to over 20. Nakata has not done as much work on solving the matrix problem as Fukui at Toshiba (below), because most of the original sparse matrix solution has been parallelized in the subcircuit processors; what is left is the sparse matrix solution for the interconnection points. However, he feels that by utilizing better domain decomposition, he can substantially increase the speedup.

Nakata originally built Cenju as a special-purpose computer, but now he is studying the possibilities of using it for other applications. Nakata notes that intercluster read access is very slow due to overhead in bus-error interrupt handling and timeout control. He dealt with this in circuit simulation by utilizing, whenever possible, algorithms in which the producer of data writes that data to its consumer.

Nakata has tested the running sys-
tem on two circuits, one with about
1,700 transistors and another with about
7,000. Both are part of the control cir-
cuitry for DRAMs. Speedups were ini-
tially reported as 15 for the small cir-
cuit and 16 for the larger. The system
designer enters the circuit. With respect
to domain decomposition, Nakata and TOSHIBA'S APPROACH
Tanabe feel that it is best to take
advantage of hierarchical design used
by the designers. When that cannot be
done, a domain processor should be
available to automatically generate the
subcircuits, although for these examples
they utilized the designers' hierarchical
design, 64 subcircuits for the first and

One of the early applications of direct methods for the solution of sparse linear systems was in the solution of problems from circuit simulation. In particular, this was the main reason for the interest in sparse matrix research of scientists from the Mathematical

Sciences Department at IBM Yorktown
Heights. This group, which included
Bob Brayton, Gary Hachtel, Fred
Gustavson, Werner Liniger, and Ralph
Willoughby, conducted much funda-
mental research into sparse matrix
techniques in the late 1960s and early
1970s. In 1970, Gustavson et al. pub-
lished a paper (Ref 7) describing the
use of a code-generation approach,
which they termed GNSO (GeNerate
and Solve), to the solution of sparse
equations. The idea of the code-
generation approach is to perform a
factorization of the sparse matrix using
Gaussian elimination and to record each
arithmetic operation involved in a linear
(loop-free) set of statements. This could
be Fortran, assembler code, or in a
compressed coded format (interpreta-
tive code approach). The initial elimi-
nation might be a regular factorization
or a symbolic one, depending on sparsity
alone and not on the numerical values.
As mentioned above, in the circuit
context (and in many other application
areas) during the Newton iteration it is
required to solve several systems with
a coefficient matrix of the same struc-
ture; thus, this list of operations can be
used for these subsequent factoriza- (3) use of block elimination
tions. In the Toshiba experiments,
sometimes about 900 iterations with a
Jacobian matrix of the same structure
were required so, in common with most
other experiments using this scheme,
the initial cost of generating the loop-
free code is not reported.

compilers and may not be vectorized by
them. Since about one line of code is
generated for each entry of the factors,
this approach is most attractive when
the factors can be kept relatively sparse.
Thus it would not be of interest in the
solution of elliptic partial differential
equations but is much more suited to
the types of matrices occurring in power
the types of matrices occurring in power
systems and circuit simulation prob-
lems. Additionally, in many circuit
problems, and especially for memory
problems, and especially for memory
modules, there is a natural stability in
the devices and this is reflected in the
equations, so that diagonal pivoting is
usually stable.

Duff (Ref 8) conducted some comparisons on the early code of Gustavson, for example, and concluded that their approach was of limited use for general problems. Duff and his coauthors also comment on this approach in Reference 9 (section 9.6), where the main problems are stated to be storage (with consequent speed problems if data have to be held on auxiliary devices) and stability. Additionally, loop-free code is not well optimized by most current

These features make the codegeneration approach potentially interesting in this application. We now discuss the improvements that Fukui et al. have made to the basic method to give them a competitive code. The improvements are:

(1) generation of assembler code using
(1) generation of assembler code using
vector operations

(2) packing of integer index informa-
tion

We discuss each in turn.

Using the example from their paper (Ref 10), a fragment of generated code (in Fortran) may look like

A(1) = A(1) - B*C(2)
A(3) = A(3) - B*C(4)
A(5) = A(5) - B*C(6)

and, if the programmer groups these
statements suitably, one can see that
the indirectly addressed vector A
(addressed above through index vector
(addressed above through index vector
13 5...) is updated by a scalar multiple
of the indirectly addressed vector C
(index vector 2 4 6...). Thus, using a
GATHER on A and C and a final

SCATTER on A, the code can be vectorized on nearly all current vector computers. This gives significant gains in both the storage of the generated code and the speed of execution. On the examples in their paper (Ref 10), the savings are a factor of just under three in both storage and time. It should be noted that the difference between generating Fortran code and assembler (scalar assembler) is a factor of about 30 in time.

If two integers are packed into a 64-bit CRAY word, the constituent integers can be quickly recovered using a shift instruction. This device is used both to decrease the memory required by the address data and to speed up the code through a reduction in memory references. A 30% speedup in CPU time is reported by the authors through this device.

Fukui says that his block elimination was similar to the use of matrixvector or level 2 BLAS (Basic Linear Algebra Subroutines) in Gaussian elimination on full systems. However, it is not clear how he would do that with his current approach and it does not appear to be illustrated in the paper. From the example there, it would appear that what is done is to hold the pivot row in vector registers and use it to update all the appropriate nonpivot rows without further memory references for the pivot row. It would also be possible to update several rows as a single vector operation, but it is also not clear if this is done. The gains reported for block elimination are a factor of 1.5 in both storage and time over the vector assembler code.

Fukui et al. also discuss (Ref 10) other issues in their adaptation of SPICE-GT, based on SPICE 2G.6 from Berkeley. The one other area of main interest is in the assembly or formation of the circuit simulation matrices. It is like the assembly of a finite-element matrix and thus can easily be parallelized.

FLEXIBLE AUTOMATION

A summary of the 1990 Japan-U.S.A. Symposium on Flexible Automation, 9-13 July, in Kyoto, Japan, is given. Plant visits to IBM's 3090 manufacturing plant, Sumitomo Electric, Mitsubishi Heavy Industries, and Matsushita Electric are described.