1. Home
  2. Field-Programmable Gate Arrays
  3. Layout problem

Layout problem

We have a graph and nodes in the graph are to be placed onto a layout. The layout has to be partitioned vertically as well as horizontally several times till it generates one slot per node. Nodes are to be assigned to vertical and horizontal partitions such that the number of edges crossing the partition is minimized. Can anybody suggest an effective procedure to deal with this problem?

As an example if we have a graph with sixteen nodes then layout has to be partitioned vertically and horizontally till the time it creates sixteen slots one per node. The idea is to decide which slot would go to which node by following the above criteria( i.e number of edges crossing a partition is minimized.

Thanks.

Reply to
Chris Jones
Loading thread data ...

Dude,

Since we're not doing the same coursework you are, the verbage is a bit hard to follow. I know what a graph is and vertical or horizontal partitions make sense... but how do nodes have edges in this context? What's a slot, now?

Perhaps there's more appropriate help available through the academic channels that posed this problem than in comp.arch.fpga where we try to help each other solve real-world problems.

Reply to
John_H

Try doing a search on the terms "graph partitioning optimization". You should find a lot of algorithms and heuristics. If you don't want to weed through all the alternatives, then try the Lin-Kernighan technique. It's fast and usually finds good solutions that are within a few percent of the optimum.

--
|| Dr. Dave Van den Bout   XESS Corp.                 (919) 363-4695 ||
|| devb@xess.com           PO Box 33091                              ||
|| http://www.xess.com     Raleigh NC 27636 USA   FAX:(919) 367-2946 ||
Reply to
Dave Vanden Bout

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.