Progess Report

Something I have to do for the REU program.

Since I gave my first presentation, I have made some good advances. In terms of the easy stuff, I have a pretty good graphical display of the placements generated by my program including the display of cut lines which has helped dramatically with diagnosing what is going on during the placement process. I have also developed a more accurate way of detecting overlaps. Previously, an overlap would be counted if one block exceeded its placement area. However, that would only count one overlap for a case where a blocked overlapped and would be placed on top of several blocks. Also, it would falsely count the case where the block overlapped the area it had been given, but didnt actually hit any blocks as a result. The new method using the GUI class to go through by rectangle object and count the number of intersections it has with other rectangles. Unfortunately, that method is O(n^2), so I am not sure how well it is going to scale up to cases with tens of thousands of blocks. If it does get ridiculously slow, I will work on a putting a better overlap counter in my placement code.

In terms of placement code, I was able to write a method because one of the previous constraints I had to work by has been lifted. I was previously under the impression that the netlist splits couldnt be changed at all and were done by number of blocks. It turns out the netlist splits are actually done by total area and I am allowed to change the netlist cuts. Now, the number of overlaps have been reduced on average by about 75%, which is really awesome. However, that was in comparison to my old methods, so thats not really useful, its just an impressive figure. With this new understanding of his methods, I coded his old method and compared that to my new method. On almost all cases, it has performed a lot better, but I have yet to do any real analysis of the results. There are a still a few issues with the placements. When I first wrote it, there were some cases that would generate infinite loops and I have removed them for the obvious cases, but I am not entirely convinced that I have seen the last of them. Also, the placement isnt what I would describe as optimal as there is a lot of internal white space with large mixed block designs. However, that might not be an issue due to the fact that this step is only one of three steps in his program.

Over this week, I am going to do some more testing, making sure my methods are correct. When I get back from break, I am going to put my methods into his code (with my professor's help) and start doing some serious analysis of the results. I want to see if the seemingly not optimal placement is corrected by the legalizer or if I have to go back to the drawing board. Also, while I am playing around with the real code, I want to do some of the other analysis methods I talked about in my first presentation such as checking out what type of overlap is the worst, etc.