Circuit Partitioning 

In our simulator, the "Cascading-Oriented Partitioning" strategy is used 
for circuit partitioning to attain high-quality load distribution.

Firstly, COP makes several clusters by grouping gates that are connected 
to each other into a cascade-form. Then, the clusters are cut or merged to 
adjust their sizes. Finally, the clusters are assigned to processors at random. 

This scheme provides adequate partitioning solutions that satisfy these 
three requirements: load balancing, keeping inter-PE communication fre-
quency low and extracting a lot of parallelism. 




Figure 4: Cascading-Oriented Partitioning


Performance Measurement 

We simulated five sequential circuits on the PIM/m machine. These were 
benchmark data for ISCAS'89. Table 1 shows the size (# of gates) of the 
target circuits. Figure 5 indicates the performance of the simulator. 



Circuits
s38584
s38417
s35932
s15850
s13207
# of gates
27,965
31,995
26,433
13,354
11,965

Table 1: Size of the circuits 


In the best case, 537K events/sec performance and 166-fold speedup were 
attained using 256 processors. 


					- 55 -