It is difficult to apply the traditional method of placing and routing 10 to 20 benchmark circuits [1, 8] in this analysis because circuits typically have only a few memories each, and so hundreds of such examples may be required to properly exercise the memory-logic connection architecture. Because it isn't feasible to gather that many benchmark circuits, our approach is to study the types of memory configurations found in systems, and then to develop a stochastic memory configuration generator based on that study.

A memory configuration is the set of all memories required by a circuit,
and consists of the number of memory *clusters*
(clusters are groups of memories which share data input or data
output subcircuits), the number of memories within each cluster,
and the width and depth of each memory.

The generator chooses the memory configuration parameters independently from probability distributions based on statistics gathered from a set of 171 custom ASIC designs. (Although we were able to obtain data on the memories in these circuits, the detailed circuits were not available).

Next, the logic sub-circuits needed to supply address and data as well as consume the data are generated and attached to the memories. The memory/logic interconnect pattern is chosen from a set of commonly occurring patterns in our example ASIC designs using measured distributions. The sub-circuits are randomly chosen from a collection of 38 MCNC circuits, which have been optimized using SIS [9] and technology-mapped to 5-input lookup tables using FlowMap [10]. The actual construction of the circuits is non-trivial and beyond the scope of this paper. Full details of the memory circuit study and construction of the generator are described in [11].

Figure 3 illustrates an example generated circuit. It has three memories, two of which receive data from a single logic source and drive a common data bus. Interconnections between the various logic sub-circuits and external input/output pins are not shown in this figure.

**Figure 3:** Example Generated Circuit

The circuits are generated without accounting for the number of memory bits
or number of independent arrays in the FPGA architecture.
Once generated, the circuits that do not fit in the target architecture
(in terms of total number of bits or number of independent arrays)
are discarded.
In the next section, we present results for architectures with
2, 4, 8, and 16 memory arrays; for each architecture we generate
circuits until we have 200 circuits that fit.
Table 1 shows statistics from the 200 circuits generated
for each architecture (*r* and Aspect Ratio will be discussed in Section 3.2).

**Table 1:** Circuit and Implementation Statistics

This stochastic generation approach was also used in [6] which studied only the memory portion of an embedded-memory FPGA.

Thu Aug 1 15:28:50 EDT 1996