Leading-edge VLSI systems, essentially multiprocessor systems-on-chip, have a wide range of components integrated together and operating in unison. They can be analyzed as flow networks in which the system performance depends on the bandwidth, transmission time, and queueing delay characteristics of the individual components, their connectivity and interactions, as well as the traffic patterns they encounter. The flow in various parts of the system must ideally be distributed so as to extract the maximum throughput possible with minimum end-to-end delays. Such an ideal distribution for flow networks has previously been obtained using simple electrical circuits. We demonstrate a similar methodology for typical VLSI systems and provide the necessary extensions of the theory. We empirically validate the methodology using a cycle-accurate simulation model as the reference. We find this methodology to supply better distributions in the average case and comparable distributions in the worst case as compared to standard search procedures such as random sampling and simulated annealing. The real strength is that it provides a speedup of several orders of magnitude, i.e., 3-5 orders in our experiments. Thus it is an elegant means for analyzing and optimizing the flow in VLSI systems, which can easily be incorporated into design procedures, compilers and on-chip modules for real-time allocations.

Partitioning is an important technique for solving graph based problems. The quality of partitions produced by standard methods, for example Fiduccia and Mattheyses (FM) algorithm, depends on the initial random seed partition. In order to get the best partitions, we have to run the partitioner many times with different seed partitions. In this paper, we present a heuristic for producing good seed partitions for partitioning graphs and hypergraphs by analyzing an appropriately derived resistor, current source electrical network and sorting the nodes according to their potentials. This is feasible because we use a special purpose DC analyzer which is very fast and can handle circuits of size up to a million nodes. Experiments have been performed on IBM benchmark hypergraphs on a Pentium-4 machine having 1GB RAM. For larger size hypergraphs, our method outperforms the standard random seed based FM algorithm both in terms of the partitioning time and in terms of the cut-cost.

We consider the state assignment problem as that of the decomposition of finite stare machines and transform this decomposition problem into an orthogonal partitioning problem with a certain cost function. We justify this cost function in two ways, first by using an idealized model of multi-level logic implementation, and second by empirical studies of a particular benchmark circuit. We describe a greedy algorithm to minimize this cost function. We present results obtained by running the algorithm on a set of 16 MCNC benchmarks. We compare these results with other state assignment techniques such as JEDI and NOVA. For multilevel implementations of the benchmark state machines, we find that the implementations obtained after using JEDI were, on average, 8.52% larger in area and 81.87% slower in delay than the implementations obtained using our approach. The implementations obtained after using NOVA were, on average, 4.40% larger in area and 104.96% slower in delay when compared with implementations obtained using our approach. Our scheme has the potential to serve as an alternative to conventional state assignment tools since we observe that it produces good results for larger finite state machines.

The strong link between matroids and matching is used to extend the ideas that resulted in the design of random NC (RNC) algorithms for matching to obtain RNC algorithms for the matroid union, intersection, and matching problems, and for linearly representable matroids. As a consequence, RNC algorithms for the well-known problems of finding an arborescence and a maximum cardinality set of edge-disjoint spanning trees in a graph are obtained. The key tools used are linear algebra and randomization.