Efficient VLSI Layout of Edge Product Networks

The interconnection network between the processor cores in multiprocessors on chip has a crucial impact on the performance. Efficient VLSI layout area of such networks can result in lower costs and better performance. Layouts with more compact area can lead in shorter wires and therefore the signal propagation through the wires may take place in shorter time. In this paper, we study the VLSI layout bounds of a new product network, called the edge graph product. Lower bounds are usually computed by the crossing number and bisection width of the topological graphs. For computing the bisection width and crossing number of the edge graph product, we use the obtained upper bound on maximal congestion. We also represent efficient upper bounds on the layout area and maximum wire length by constructing layouts based on separators and bifurcators.