1. 假設兩矩形的點和點連接,那算是有連接的關係?

ans: NO. (不算)

2. 在測試檔test31中的label檔案有重複的label名稱。
如果遇到這種情形是找出不同label間的路徑還是相同label也要考慮?

ans: We should treat these labels with same label name as a group.
From the topology, there will be multiple paths between the two different label groups.
And there is connected path(s) between any two different labels.
These labels help to identify the shorted path between the two different label groups.
The program should be able to identify a shortest path from these paths.
For Example,

              1                  2                              3
VDD+--------------+---------------+------------------------+VSS
     13 |                                      | 14                          | 15
VDD+-------------------------------+------------+----------+VSS
     16 |                     4                       5              6      |
          |                                                                     | 17
VDD +------+--------+--------+------------------+---------+VSS
              7         8          9            11                  12

Numbers 1 - 17 represent the shapes, there are so many paths between VDD to VSS,
while the shortest one would be
VDD (the middle one) through Shape 4 to Shape 14 to Shape 3 to VSS (the top one).
　

3.
I want to make sure a shortest path on two different nets is determined by

the number of polygons only.(I mean it is not to include the number of vias

,right
　

ans: Yes, only the shapes of interconnect layers (metal1 and metal2).
　

4. 每個test case會不會有超過兩種的label??
是不是所有的test case 都會有short存在？

ans:

In order to simplify the problem,
Yes, each test case contains exactly two different names of labels; and it really has short problem.
　

5. 我想請問一個問題~就是當兩個node上有超過一條以上的最短路徑時
我們需要將所有的最短路徑都表示出來嗎??
還是只要表示其中一條就可以囉??
舉例 : a -> b 上有三條最短路徑
a -> c -> d -> b
a -> 1 -> 2 -> b
a -> e -> f -> b
這三條的路徑數都是相同且都是最短路徑
那是要三條都表示出來嗎??
還是只要表示其中一條就可以囉?
　

ans: We encourage you to report all of the paths into different output files.
While at least one of the shortest path should be output.
　

6. 我請問一下,在test31這個測試檔中,是否會有兩的label的座標點打到同一個矩形上,
如果會發生這種情形時,我們該如何處理??

ans:

If the label names are the same, then it is OK.
If the label names are different, then it's a short; and the output for such case is very simple,
i.e. just the rectangle they are located on.

Please note, you should also check with the ATTACH layerName for the labels;
maybe, they are attached to different layer shape (one attached to MET1, the other attached to MET2);
then, it will be a different situation.

If you could, please send me the label names and the coordinates of the two labels you found for
this specific testcase (test31). I can double check it for you.
　

---------------------------------------------------------------------------------------------------

6.1. 因為test31裡面所有的label name都是打入同一層 layer (都是metal2)
在label name = VSS 座標為 (1300.3 , 3.75) 和 ( 0.5 , 4 ) 這兩個label 都會落入 ( 0 , 1.5 ) ( 1300.5 , 6 ) 這個矩形當中
而label name = VSS 座標為 ( 0.25 , 253.25 ) 和 ( 1300.35 , 253.25 ) 這兩個label 都會落入 ( 0 , 251.25 ) ( 1300.5 , 255.75 ) 這個矩形當中

ans:

因為打在同一個矩形的這兩個label name 都是 VSS, 所以是OK的. They just confirm that the rectangle
they attached is really for VSS. 我們可以將這兩個label所在的點, 例如 (1300.3 , 3.75) 及 ( 0.5 , 4 ), 當成
同一個起始點for path tracing.
　

8. 在題目pdf檔裡面的的evalution那段...
"Number of interconnect shapes in the output"
是什麼意思??
　

ans:

It means number of shapes (number of lines) reported in the output file. I.e. those shapes (metal1 & metal2) belonging
to a net identified as short. It is 7 for the case shown in the example of the problem statement (pdf/doc document).
Since there are 7 shapes reported in the output file.

9. 一個via在"同一層"有沒有可能連到兩個以上的metal?
因為在test31裡面好像有這種情形發生...
　

ans: It's possible. As long as these metals shapes are abutting (i.e. belonging to the same polygon/net);
就如下圖 .

10. 有關label的判斷-----

1. 如果label給的座標落在同一層的兩個metal的邊緣
    這樣應該兩個metal都要算對吧??
2. 如果是降的話, 在測試檔test22裡面, 應該沒有multiple shortest path吧??
    因為根據test22的label裡面第四行, 以及metal1中第2, 3行
    這兩個metal應該同樣為終點(假設VDD為終點)吧??
    降子最短路徑應該是:
0.000 0.000 56.000 209.000(metal1)
|
0.000 209.000 942.000 226.000(metal1)
|
523.000 51.500 542.000 225.500(metal2)
|
161.000 52.000 1061.000 69.000(metal1)
四個吧???

3. 不過如果label第四行從原來的 1061.00 52.00 改成讓Y座標小於52,
    應該就有multiple shortest path了...
    還是這就是readme裡面說的combining the errors of test21 and test23 ?

    不知道有沒有算錯... 錯了請多包含... ^^"

    p.s.隨件附上用mfc畫出來的layout圖...

ans:

1. Both of the metal shapes need to be considered when we are tracing the shorted path.
It appears at the lower-right corner with label name VDD.
您原來附的圖好像上下顛倒了. 重新附上rotated 後的圖 with label names highlighted.

2. In the figure of file spapa_test22_A, several shorted paths are highlighted with different colors (there are more not highlighted).
You are right that the shape of rectangle (1005,0 ) (1061, 52), filled with cyan color, could be ignored in counting the
"number of connected shapes" for the shorted path since there is no other shape connected to it -- it is definitely belonging
to VDD and does not cause confusion.
So, there is only one shortest path --- highlighted by the line with green color.
　

3. Your comments about the fourth label coordination are correct and valid.
Sorry for the confusion.
　

11.

1. 之前的問題9所問的：一個via在"同一層"有沒有可能連到兩個以上的metal"
那照回答來看，是否表示via不一定要完全都在metal rectangle之內

2. 還是必須那同一層的metal互相相連，所以via才可以有橫跨一個metal rectangle的情形出現？

3. 那下面這2個case可以說算是相連的情況嗎？

Black：via Blue：metal2 Red：metal1
Case 1 Case 2

4. 會有單獨的via存在或是只跟其中一層metal rectangle overlap的情形發生嗎？
類似底下這樣

ans:

1. via 一定會被metal1, metal2 完全包住, 但不一定只在單一個 metal rectangle 之內

2.是的

3.都不算. 基本上這兩個cases 都違反Design Rule.
Testcases中應該不會有這些狀況才對

4.No. If there is, please just ignore it.
　

12.

若在白色的metal 1中有metal-11與metal-12相鄰,並且在另一層還有一個metal 2與它們重疊,除此之外,有一個via正好打在此兩相鄰metal 1的邊上。設此via的右邊正好與metal-11與metal-12相鄰的邊重合,請問在這種情況下: (1)metal 2必須藉由metal-11才能與metal-12連通,或是(2)因為via的邊有與metal-12的邊相鄰,所以也視為metal-12可以直接藉由via連通到metal 2,而不需要透過metal-11才能與metal 2連通?

ans:

For this case, Metal1-11 through via to Metal2 would be enough.
Since this via is fully enclosed by Metal-11, we can ignore Metal-12 which does not enclose (or overlap) the via, but only with edge touched.
　

13.

1. A、B、C是指紅色的矩形，1、2、3是指藍色的矩形
依照上圖，如果要從下面綠色的小點走到上面綠色的小點，哪麼路徑的算法
� 3、2、B、C （表示A、1可算是直接相連或是B、2也是）
� 3、2、1、A、B、C （表示要經過這些via那麼4個矩形都要算才可）
不知道是採用上面哪一種算法？

2.
在問題6中依照回答來看，有可能一個矩形同時被標上屬於同一layer的VSS跟VDD的label，那麼這種case的最短路徑就是這個矩形本身，可是這種case的all path要如何列出呢？這種case應該不算是短路問題而是設計錯誤所以只需列出這個矩形嗎？或是在列path時可以將此矩形當作是一個沒有label存在的矩形來計算path嗎？
　

ans:

較正確的表示應採用第二種, 即3、2、1、A、B、C
We need to include all of shapes fully enclosing the via(s), if the via(s) is on the shorted paths.
　

We can treat this special case as a shorted path. The iteration of short location will finally come
to such situation, so that we know where the short is exactly located. Normally, this rectangle is
wrongly placed in the layout and the designers need to correct it. You may refer to the reference paper.
　

14.

1.請問一下加分的部分，是說只要是短路的路徑就要output出來，但是這條路徑不一定要是最短的，是這個意思嗎？(因為問題5的回答好像是只針對最短路徑跟題目上的加分要求有些不同，所以想弄清楚^^||)

2.路徑是要rectangle的集合來代表，那麼如果將其中某些矩形的順序掉換一下，也就是從VSS到VDD的依序走的rectangle不同，這樣可以算是另一條的路徑嗎？還是只要集合中的rectangle 是一模一樣的，那麼不管順序一論都當成一條路徑來計算？
　

ans:

1.Yes. 加分的部分: 只要是短路的路徑就要output出來，但是這條路徑不一定要是最短的.
　

2. If you could report the rectangles in an order (either from VSS or from VDD) that would be a plus. It would be very helpful
if the users want to trace the layout with the text report.
Since we have the scheme to show the results in graphics, it does not matter the order of the rectangles reported.
The output path should be unique, i.e. 只要集合中的rectangle 是一模一樣的，那麼不管順序一論都當成一條路徑來計算.
　

15.

設在白色的metal 1中(有metal-11與metal-12相鄰),在另一層還有藍色的metal 2 (且metal-21與metal-22相鄰),除此之外,metal-21和metal-22均與metal-11重疊,同時, metal-22也與metal-12重疊。若有一個via正好打在此兩相鄰metal 1的邊上,設此via亦正好打在metal-21與metal-22相鄰的邊上,請問:(1)metal-12必須藉由metal-11或metal-22才能與metal-21連通?還是(2)因為via的右半部打在metal-12上,via的左半部也打在metal-21上,所以也視為metal-12可以直接藉由via連通到metal-21,而不需要透過metal-11或metal-22才與metal-21連通?(3)在此同時,metal-11可否算是直接與metal-21和metal-22相通?

ans:

The guideline would be, all of the connect layers’ shapes need to be reported once their enclosed via(s) is in the path.
If we trace the path from Metal-12, and decide to trace up to metal2 through the via,
� Since the via is partially enclosed by Metal-12 and Metal-11 encloses it also, Metal-11 needs to be included in the path
� Get Metal-21 and Metal-22 enclosing this via. Both of Metal-21 and Metal-22 need to be included in the path once we select this via into the path -- no matter the path goes to the left-hand side from Metal-21 or to the right-hand side from Metal-22.
So, for this case, all of the four shapes should be reported.
　

16. [通告]

主辦單位已經將郵寄報告以及FTP上傳作品的方式公布於參賽手冊(April 22, 2004版本), 敬請盡速至競賽網頁下載. 另外, FTP站也已開放上傳作品, 也請盡速確認能否成功登入.

若有任何疑問, 請來信 cad@cs.nthu.edu.tw
謝謝
　

17.

(1)設藍色是metal 1,紅色是metal 2,在以下電路圖中,
有一條最短路徑從(VDD)1�2�3�4(VSS),
此時若要找multiple paths,是否能找到另一條路徑: (VDD)1�2�3�4(VSS)�5(VSS)

(2)想請教multiple paths 的判斷條件取決於什麼?
(不同的判斷條件會有不同的multiple paths輸出)
是否為“只要任意VDD到任意VSS有路徑連通,並且任意一個metal在一條路徑中
只能被經過一次的情況下,這就算是一條multiple paths之一嗎?”
Ex:以網頁上問題2的答案圖示為例:
此圖的multiple paths 是否包括以下幾條:
VDD�1�2�3�VSS
VDD�1�2�3�15�VSS
VDD� 1�2�3�15�17�VSS
VDD�16�13�1�2�3�15�17�VSS
VDD� 1�2�3�15�6�5�4�16�7�8�9�11�12�VSS
:

              1                  2                              3
VDD+--------------+---------------+------------------------+VSS
     13 |                                      | 14                          | 15
VDD+-------------------------------+------------+----------+VSS
     16 |                     4                       5              6      |
          |                                                                     | 17
VDD +------+--------+--------+------------------+---------+VSS
              7         8          9            11                  12

　

ans:

(1) Yes. The path (VDD)1�2�3�4(VSS)�5(VSS) could be treated as another shorted path.

(2) Basically, yes. While if the program is smart enough, the shapes of 13, 16, 15, 17 should be ignored and not considered in the shorted paths. For example, shape 13 connected to VDD in both sides directly, it is definitely correct.