Modern computer chips have on the order of millions of elements to be placed on them in order to achieve the desired functionality. The arrangement of these elements on the placement area can have a huge impact on how the chip will perform. A better placement will result in shorter wire length which amounts to less power used and faster performances. My problem concerns the optimal placement of these computer chip elements on the placement area. The problem input is a description of the placement area, a list of elements with their width and height, and a netlist describing the connections between the elements. The output to the problem is a list of x,y coordinates for each cell on the placement area such that the placement of the elements yields an optimal result measured in terms of wire length. However, to find the optimal solution to the problem is an NP complete problem, meaning it is infeasible to find the guaranteed optimal solution, therefore any method we adopt to solve the problem will be an approximation of the optimal solution.
The problem divides down into three sub-categories. The first category is known as standard cell placement which concerns the placement of elements that have different widths, but all have one standard height.
The next category is known as macro block placement which concerns the placement of elements that are all very "large" meaning that they have varying widths and heights significantly bigger than the standard height.
The third category is known as mixed block placement which, as the name implies, concerns the placement of both standard cells and macro blocks. This problem is unique because the simplistic techniques used in the standard cell placement cant handle the macro blocks because of their non-standard height and the techniques used in macro block placement can not scale to handle the large number of standard cells in the designs. It is the mixed block placement that I am addressing this summer.
A current way of addressing the problem is a technique known as recursive bisection. Previously, at each step, the method sought to divided the placement area and the netlist of cells in half. The process would repeat until there was only one cell per area, at which point the cell would be placed into that location. The netlist of cells is divided in half according to total cell area. However, this method would ignore circumstances in which the dimensions of macro blocks exceed half of the area to be split. In this case, blocks would end up being stacked upon each other because of the overlap of the macro block. Obviously, such a design is not possible and is considered illegal. To address this problem, after the recursive bisection is complete, a legalization step takes place. There are many different possible legalizers, but the functionality of a legalizer is to take a design that contains overlaps and shift the blocks in a minimal way so that the design contains no overlaps at the end of legalization. However, legalization has no knowledge of wire length, therefore the more work the legalizer has to do, the greater the wire length becomes. So it becomes necessary to have the legalizer do the minimal amount of work required, thus we need to reduce overlaps during placement.
My focus is to reduce the number of overlaps during the recursive bisection placement process.

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.

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

Summer thus far...

So this summer, I was lucky enough to land a position at an REU (Research Experience for Undergrads) at my school, Binghamton University. So effective late May, I have been in Bing spending my days in front of a computer screen. It has actually been a lot of fun. Im working with Professor Madden on some of his circuit design software, except that I dont need to know anything about how circuits work, which is good for me. The general idea is that you have these blocks that represent something that needs to be on the chip and you have to arrange them somehow. A modern chip can have millions of blocks, thus making the task pretty much impossible for humans to do, so we get computers to do it. But the placement of these blocks on the circuit can make a huge difference in the performance of the chips. Better placement means faster processes. So essentially, I have a bunch of rectangles that need to be placed on a larger rectangle in the most efficient way possible. But there is a catch. This problem is computationally intractable, meaning that the absolute correct answer cant be reached in any reasonable amount of time. If one did write the software to do this, it wouldnt finish running before a giant asteroid hit Earth (april 13th, 2029). So anything we do are approximations of the correct answer, which is why there is debate in the field on the best way to do it. Its a really cool problem and has a lot to do with algorithms. In this blog, I am going to be writing a lot about my progress and they are usually meant for myself rather than anyone else.

Beyond that, I am also serving as the Teaching Assistant for cs 240, which is also pretty fun in itself.

The only downside to this summer gig is that its pretty lonely up here. The Binghamton I knew during the normal year is certainly gone and replaced with a very empty place. So when all of my high school friends are home and together, I am at college while all of my college friends are off doing there own thing. Plus, Alia isnt here, which is the biggest problem with this arrangement. But the other kids in my program are pretty cool and smart, so its not all bad. It has certainly become infinitely more fun since the beginning weeks.



I have taken up longboarding, which is ridiculously awesome. It has cost me a lot in terms of cuts and bruises, but it is still ridiculously fun.

Until another time.

Inaugural Blog

Starting this for a few reasons, none of them are really any good though. I guess sometimes its nice to articulate thoughts and at least believe for a few seconds that they are recieved by someone besides yourself. Also, I sometimes need to write down some stuff for my own sake, like ideas that I will forget or progress reports on my research or something. Plus, practicing my writing skills is always a good thing.