Repository files navigation

• Rohan Rajesh Kalbag
• Anubhav Bhatla

Suppose we partition the graph into sets$P_1$ and$P_2$, the sum of weights of interconnections between the two partitions is calledcut size

Thus splitting the components among two FPGAs so as to minimize the cost of interconnects (which can be represented by the quantitycut size) denoted by$C_1$ which should be minimized and also the equitable balancing of components on both FPGAS (if components are equitably balanced among both the FPGAs, we can represent this quantity by$C_2 = N(P_1) * N(P_2)$ where$N(.)$ represents the cardinality (number of nodes) of the partition) which should be maximized.

Thus, one can use the simple metricratio cut$C_1/C_2$ to ascertain and compare the quality of partitioning performed by various computer aided design partitioning algorithms. Typically a smaller value ofratio cut denotes a better partition.

A much better cost function can be modelled using co-optimization as well to get the minimization problem$min(\alpha C_1 + (1-\alpha)/C_2)$ where$0 < \alpha < 1$ is a co-optimization metric.

We try to implement graph partitioning algorithms and heuristics like theKernighan-Lin Algorithm,Clustering Based Heuristic,Hagen Kahng EIG Algorithm and compare, analyse their capability in partitioning a given graph network into two partitions and visualise them using plotting tools ofmatplotlib,networkx libraries ofPython

Create a virtual environment (only the first timeif the folder./ee677 is absent) usingpython3 -m venv ee677

To setup the virtual environment open a terminal in the directory and do the following commandsource ee677/bin/activate to activate it.

Then setup pip in the following waypip install -r requirements.txt.