|
|
Magic Mailing List |
|
From: Andrew Lines (lines AT avlsi DOT com) Date: Wed May 24 2000 - 01:56:09 EDT
We've been using "half-generic" contacts for a while now. We even taped out a 650,000 transistor test chip with them. These contacts are simply "paint" that lives in one plane and has electrical connectivity to the plane above. Unlike Magic's actual contacts, they can be arbitrarily stacked. They are somewhat harder to edit, as the top metal layer is not strictly associated with the contact, but merely caps it. This is similar to the MOSIS generic contacts, but at least they plow and interact nicely in the lower plane. However, this approach has lead me to discover a very obscure bug in Magic, probably one which nobody else has ever seen. The bug is in DBconnect.c, which recursively selects electrically connected tiles and copies them to a destination buffer. The non-heirarchical algorithm, DBSrConnect, uses two passes with a mark and clear algorithm to avoid infinite loops in circular connections. So does the extractor (I hope...). However, the heirarchical select, DBTreeCopyConnect, uses a one-pass algorithm which performs a rather tricky and convoluted test to decide when to terminate the recursive search. Given the current tile, it checks the destination buffer to see if there is already connected paint in the same plane as the tile which completely covers the area of the tile. If so, it assumes all connected stuff from there on has already been handled. There is special case code which checks that if the tile is a contact, the destination buffer is already painted with the image of that contact (not just electrically connected material in the same plane). Therin lies the problem. With the half-generic contacts, the special case code isn't triggered, so Magic might see that the area is already covered by m2, paint an m3c on top of it, and terminate the recursion. It fails to reach any m3 connected to the m3c. The MOSIS generic contacts aren't affected by the bug because they lie on their own planes. OK, so how do I fix this? 1) A simple mark and clear algorithm won't work well, because the same tiles may be used in different subcells. (I tried this and it won't work). 2) Storing all visited subcell/tile pairs and searching for every new tile would be slow, even if we kept a sorted set. And it wastes memory. 3) I could declare these half-generic contacts as a new type of "contact" which would trigger the special case code. This is pretty silly, considering you could still screw this up in the techfile. 4) Use a more sophisticated test for termination. It should terminate the recursive search if and only if painting the new tile is vacuous. This of course relies on the compose rules, so that you can declare a rule like "paint m2 m3c m3c" and have it figure things out. So if I try approach 4, does anybody have a good suggestion on how to paint a new rectangle and return an indication of wheather the data structure was actually modified? This would be the best all around solution, avoiding both the special case contact code and fixing the bug.
|
|
|
|