It is Year 2010, September. Your illustrious UC San Diego days are long behind and you and your buddies have just been hired at the most promising next generation CAD company, a company whose business plan includes ambitions of unseating the dominant CAD companies and leading the next cycle of VLSI CAD company generation in Silicon Beach (aka San Diego). You have been given a generous set of stock options with one caveat. You are supposed to implement in a little bit more than a month a VLSI layout CAD system (in addition of course to fulfilling all your other obligations in trying to help make sure that the startup survives); your stock options (and your employment contract) become moot unless you exceed expectations on this project. As time is of the essence, you return to UC San Diego to ask for at least a blueprint of the VLSI layout systems implementation.Your ex-professor (wizened now with the passage of time) offers you some recommendations, based on what you had studied in his course, CSE 144, in those auspicious fall days of 2001.
While chips have gotten even larger in the intervening time, functionality to be implemented has not failed to keep apace. So even in Year 2010 managers are asking for more functionality than what a chip can accommodate and the prognosis for increased functionality is even more pessimistic. A partitioning part seems unavoidable; since you had studied both the Kernighan-Lin and the Fidducia-Mattheyses algorithms in Fall 2001, a partitioning algorithm based on these ideas seems still the safe way to go.
Not only is this algorithm useful for chip partitioning but can also be used in partitioning into rows for a standard-cell design. Standard-cell designs continue to be popular but the design styles have reduced the complexity of placement in Year 2010 and we only need to be concerned about a 2-row design style. Partitioning still seems to be eminently a reasonable algorithm for this 2-row standard cell design style and your professor seems to recommend it, since it is bound to reduce interconnect. Still a placement within each of the rows needs to be effected. A simulated annealing type of algorithm seems to be the way to go; after all your textbook seemed to have almost the whole code written up.Yet a few modifications seem to be needed; the standard cells have unequal size widths and still a metric for evaluating the goodness of the placement needs to be agreed upon.
Finally, to complete the layout system obviously a detailed router is needed. For standard cells, a channel router is obviously the way to to go. With a standard cell design style, more channel lines can always be added, so you decide that a left edge router is the quickest, barebones way to go. You are satisfied that you now have a clean and doable implementation blueprint and rush back to your company.
Yet in the meantime while you were back on campus, your company has been undergoing severe market pressures and you find that the schedules have been tightened further. Now you find out that the project is due by Nov 26th, 2001, 1:00 PM! Of course, for a bright young UCSD graduate nothing is impossible.You hop on the nearest time machine, and off you go!