Success

#Begin Computer Science Stuff

So yesterday I finished putting some touches on my metisSplit method and it is working now with pretty awesome results. The largest reducion in overlaps comes with designs with a large number of standard cells and small number of macros. In designs with almost all macros, it doesnt reduce overlap too much (there arent that many blocks to place), but it does end up with what seems to be better placement. On average though, verus metisBisection, it places more blocks outside of the original placement area but places much less blocks on top of each other. Over the next week I am going to have to figure out which one is more desirable.

But the important thing is it handles the exactFit test case perfectly, which is really exciting.

Hacks that I made to the original method.

- Rounded up any cut line to be to the nearest integer. This hack was made after seeing the exactfit test case divide the area in half, leaving a 5 X 2.5 area with 5 1x1 blocks to be placed in it. That configuration made it impossible to fit things exactly. For at least the simple cases (which are important), this hack seems to overcome this obstacle extremely well and allowed for perfect placement in the exactfit testcase.

- There were some cases when a block would fit the max dimension of the area to be split, causing a 100 - 0 area split and 100 - 0 netlist split. This resulted in an infinite loop as neither the area or the netlist would ever change and shit would go crazy and seg fault. "Fixed" this solution by adding a simple check to see if it was 100% of the area and if so, make the cut line at the half mark and continue. This has worked but I need to find a better method than just cutting at the half line, which I believe is the soul cause of the overlaps that I see in designs coming out of metis split.

- There were other cases where the netlist divsion should have been like %66.66 and %33.333 but do to the size of the blocks, the netlist split kept coming out 100 - 0. Eventually, the blocks would resolve themselves in subsequent recursions, but there was a problem that there was a null node being created that was throwing seg faults during the printing stage. Fix to this was to check if the size of the netlist for a node was 0 and if it was, dont create that node. This case was particularly interesting because even though the netlist wasnt being split at all with the subsequent nodes, the area was being split a little bit, so the direction of the split would eventually correct itself and placement would come out fine. This might be a way to handle the above situation. Instead of just making the cutline at 50%, perhaps I should only do it a little bit each time though, such as making it a 90% cut. The first time it probably wouldnt correct it, but after enough recursions, it would possibly correct itself, leaving a more optimal solution.

The only concern that I am having with metisSplit is that it tends to leave a lot of white space internally in the design. I was toying with the idea of moving toward a minCut metis split and thereby theoretically moving all the white space to the outside of the design, but minCut can go horribly wrong some times. Still, its worth a shot and might try it this weekend.

#END Computer Science Stuff