1. 請問 在 Performance Evaluation. 裡, "sum of cell areas" 的意思為何?
    如下圖主辦單位所提供的例子 Fig.5 :
    sum of cell areas = ( 圖 a 中 綠色部分面積和)
                             或者
                             = ( 圖 b 中 綠色部分面積和)
..........(a)

..........(b)

ans: Fig. 5 中, 有三個cells, 分別是Top, A 和 B.

"sum of cell areas" 是這三個cells中分別計算綠色部份的
面積, 再加起來
　

2.

(1) 簡化每一個cell area 越多越佳嗎??﹝就如同是你圖四上面的為例子，是儘量可以A跟B的area併入到最少的面積的結果
為較好的還是最多的面積為最好的﹞例如有兩組的人的結果都是正確的，一組可以把是top+A+B=1000+200+100
另外一組是 =800 +300+200
這樣子是以哪一個人的作品較好?

(2) 圖四中的top是否也為一個cell，還是多只有A跟B

ans:

先回答(2), Top 也是一個cell

(1) 以圖四為例, Top+A+B 越小越好, 如果兩個不同的答案面積和一樣, 就是一樣好
但是你假設的問題不會發生, 因為Flatten的面積是一樣的, 也就是說, 以圖四為例,
因為正確的答案必須沒有Overlap, 所以 Top+2A+3B = constant.

如果是 800+300+200 與 1000+200+200, 那前面一組比較好
但是以下三組是一樣好 700+500+100, 800+300+200, 900+100+300
　

3. 關於圖五，TOP層當中那塊重疊不規則的圖形﹝非矩形﹞，應該如何表示成題目要求的output格式
　

ans: 它原是兩個矩型重疊而成, 你不用將它表示成一個polygon.
只要將那兩個矩型的坐標正確地表示在Top cell中即可

Performance evaluation時, 測試單位會算出正確的polygon
面積的
　

4. The polygons in different cells might be overlapped
hierarchically. This is not good for some operations
applied on the layout data.

請問2層之間,有overlap的部份,是會造成什麼樣的不好呢?

是會產生平行版效應之類的嗎?
　

ans: 跟平行版無關  不管在hierarchy的哪裡
所有的polygons都是同一層的幾何形狀
hierarchy中的上下關係  不是IC製程中一層層間的關係

一個簡單的運用是面積的計算  我們想計算將hieararchy的資料打平後的面積
但是打平會產生太多的polygons  而導致程式memory不夠用的問題
如果Removing overlapping後  那莫只要單獨計算每一個cell中的面積
在將hierarchy中buttom up的將面積加總上來 就可以算對了

另一個例子是  請找出所有(真實)面積小於1000的polygons
答案必須是有hierarchy的  但當然要跟打平了的答案等值
也是做完Overlapping removing後  一個一個cell做  就得到答案
　

5. 請問以下情況發生時,視為overlapping嗎?
TOP有reference A與reference B.
TOP本身與AB皆無overlapping,但AB之間有overlapping.
並且AB間並不具有直接的hierarchical的relationship
(即若是將A reference到的cell與其任何sub reference都不含B
 反之 B 亦同)
(如附圖,其中綠色部份為top的rectangle,紅色部份為A的,藍色部份為B的
AB 有重疊的範圍用紫色表示.)

若是視為overlapping
那麼是可以任意移動到A或B(假設不會對其它的overlapping判斷產生影響)
或這要將兩個一起移動到top?
　

ans: 是的  是overlapping
答案怎樣都可以  只要是沒有"Overlapping"

另一個重點是不能改變hierarchy的結構
也就是output file中所有BGNREF...ENDREF敘述
都是不能改變的  要跟input file的一樣
改變的只有每一個cell中的矩形而已
　

6. Please note the following statements:

The output file should not change the structure of the hierarchy.
Student can only move rectangles up/down in hierarchy.  He or she
could not move, delete or insert any cell references.
　

7. After our programs are launched by the following
command:
  % a.out case1.dat TOP
We will generate the output file "result.dat". The
format of "result.dat" is like the output file for
Fig.3 described on page 5. Besides "result.dat", will
we output the area of TOP cell, speed and memory
consumption on screen? If we must output these
information, should we follow some fixed formats?(What
is the function of the second argument?)
　

ans: No need to output other things.

But, to print out run-time and memory will be appriciated.
But I will check it by myself.  Because of overlapping
of rectangles, it is not a trival thing to calculate the
real area.   You need not to do it.
　

8.

(1) 雖然測試檔尚未上線,但基於程式的評估可能需要一些關於系統規模的參數,
比如說polygon的數目,一般狀況下的overlapping程度,以及最後整個top layer的大小
(這邊大小指的是flatten以後,能包住所有rectangle的矩形)
請問可以在測試檔上線前提供一個order嗎?

(2) 又,請問如果不利用de-overlapping的資料計算面積,是否對評分有影響.
並且
  % a.out  case1.dat TOP
此時計算TOP面積之後,程式算完面積,輸出的形式為何呢?

(3) 另外,關於X,Y,並未限制為unsigned,意思是說如果有一個envelope包住整個cell
的所有rectangle的話,(0,0)參考點並不一定落於頂點上的意思嗎?

(4) 最後,請問可以額外限制input的XY 必須有GCD = d == 1 這個條件嗎?
　

ans:

(1) I have no idea now.  I will try to provide larger testcases.

(2) The problem doesn't ask for calculating the area.  You need to
"de-overlapping".  Removing overlapping is what this problem
asks for.    The cell-level area is used to evaluate "how good"
the result is.

(3) For X and Y, please use signed "int".  Yes, (0,0) might not be
located in the envelope of a cell.

(4) There is no restriction such that  "GCD of X and Y == 1".

9.

ans: The answer is Yes.  This is one kind of overlapping in the hierarchy.

　

10.

能否解釋一下問題與回答中，問題2 的ans提到的

"如果是 800+300+200 與 1000+200+200, 那前面一組比較好
 但是以下三組是一樣好 700+500+100, 800+300+200, 900+100+300"

請問比較的依據為何呢？

ans: The rule is the smaller the sum of all cell-level areas, the better.
It has been mentions in the problem document.

800+300+200 < 1000+200+200
700+500+100 == 800+300+200 == 900+100+300
　

問題2：(1) 簡化每一個cell area 越多越佳嗎??﹝就如同是你圖四上面的為例子，是儘量可以A跟B的area併入到最少的面積的結果
為較好的還是最多的面積為最好的﹞例如有兩組的人的結果都是正確的，一組可以把是top+A+B=1000+200+100
另外一組是 =800 +300+200
這樣子是以哪一個人的作品較好?
　

1000+200+100 == 800+300+200, therefore they are of the same good.

In general, the parent cell 'A' will have "many" child cell 'B'.
For example, suppose A has 10 references of B. The result should be
better is you can keep more areas in B.

For two different results, one might be better for one cell but worse for
another cell. There may be many goods and bads. Therefore, the rule is
defined to consider the sum of all cell-by-cell areas.
　

11.

1.On page 5: The result that explodes fewer polygons
is considered as a better result. 請問是否"explode
fewer polygons", "sum of cell
areas"就會比較小?(如果兩者沒有直接的關係,那我們要follow前者還是後者?)
2.% a.out case1.dat TOP
請問參數TOP的作用為何?
是否不論第2個參數為何,我們都必須remove"所有的overlapping"?
以Fig. 4 為例,當我們下command:% a.out case1.dat A時,
output file中要輸出那些資訊?(是cell TOP,A,B remove
overlapping後的結果,還是僅需輸出cell A,B remove overlapping後的結果)
　

ans:

1. In general, if you explode fewer polygons, you will
get a smaller sum of of cell areas. Think about it.
What is the result if you explode all B's polygons
for the example in Page 1?

2. A given input file might have multiple "top" cells.
It is a legal input. When the "top" cell is specified,
then the hierarchy is decided. Only the overlapping with
respect to that hierarchy of cells is considered to remove.
　

12. 請問關於題目中說的cell可以旋轉90 180 270或對X軸翻轉
是每個cell可以個別旋轉還是說都一樣呢？
例如假設A cell包含5個B cell，那這5個B可以各自旋轉不同的角度嗎？
附圖為自己想的題目中fig 4的 最佳解，將A 包含的B對X軸翻轉，同時將top cell中右邊的A旋轉180度
請問這是合法的解答嗎？

ans:

在A中的每一個B的instance都可以有自己的角度

你想的解答是不對的, 你誤解了題目的意思, Output不能
改變Input的hierarchy(不可以增加或減少references,
不可以改變角度...), Output是要移進或移出Polygons,
而且不改變Flatten的幾何形狀也沒有hierarchical overlapping.
　

13.

1.關於題目中reference 到的cell 之旋轉與翻轉，假設Cell A reference到 Cell B，應該有八種情況
將我的理解製成附圖，不知道我的理解是否正確？
（請注意：此圖中的<Reflection> 和<Rotation>位置寫反了。）

2.Cell的reference會不會有循環的情況呢？(例如A ref 到B, B ref到 C, C ref到 A)

ans:

1. 是8種情形沒錯
2. 不會
　

14. NOTE:

We have proposed two testcases for Problem 4 Hierarchical
Overlapping Removing. The file names shows their top cell names.
Support the executable is "a.out". Please run the testcase with

a.out V07Q.dat V07Q
a.out ALLL.dat ALLL
　

15.

1. input檔中，CELL 的 "name" 應該有個MAX_STRING_LENGTH 的限制吧！
2. 「讀檔的時間」會算在performance上嗎？
　

ans:

1. I think you may take 1024 as the max string length.

2. The input reading time is including.
　

16.

請問input file中，cell出現的順序會依照hierarchy的高低嗎?(從底層給起，最後一個是top cell)

例如：Fig.1的input file一定是以下這樣嗎?

BGNLIB

BGNCEL B

BGNRECT 0 0 10 20 ENDRECT

BGNRECT 20 0 30 20 ENDRECT

ENDCEL

BGNCEL A

BGNREF B 20 10 0 0 ENDREF

BGNRECT 10 40 40 50 ENDRECT

BGNREF B 60 10 0 0 ENDREF

BGNRECT 80 20 90 50 ENDRECT

ENDCEL

ENDLIB

(A參考到B，所以B要先被定義，接著才定義A)


ans: 沒有一定的先後順序
　

17.

以下面的圖為例，假如在input時的輸入為a.out file A

這樣是不是只要考慮在A這個Cell的overlap，在圖中TOP的rectangle和Cell A的overlap就不予考慮?

ans: 是的
　

18. 在做完overlapping removing後,output file是否輸出input file中"所有"的cell?還是只能輸出在hierarchy中的cell?
　

ans: 只要輸出所要求計算的cell的hierarchy部分
　

19.

請問input
file中,cell內的rectangle會不會彼此有overlap?(如下,cell
A內的兩個rectangle有overlap!)
BGNLIB
...
BGNCEL A
BGNRECT 0 0 10 10 ENDRECT
BGNRECT 5 5 12 12 ENDRECT
ENDCEL
...
ENDLIB
　

ans: 會
這個例子是合法的
　

20.

請問同個CELL會彼此overlapping嗎？
例如 TOP reference 到2個A，然後這兩個A彼此有overlapping
(如 問與答 第5項 那種情形，但改成top 與 兩個A)
這樣也需要將A的方塊 explode到top嗎？

ans:

1. 會 這是可以的

2. 必須explode

　

21.

針對Q&A 20.我想請問為什麼須要explode?在題目Page 2.中有提到"the objective of the problem is to produce another hierarchy of data such that there is no hierarchical overlapping of polygons between different cells",以附加圖檔來看,cell A reference cell B兩次,cell B間彼此有overlap,可是between cell A and cell B, there is no hierarchical overlapping.而且即使不explode到cell A,在算cell A的area的時候,只要將cell B的area *2就ok了.所以對於這種情形,我不曉得為什麼一定要explode.

ans:

如果Cell B彼此有overlap,  x2不會得到正確的面積吧
計算面積只是overlap removing的一項應用
如果只是要計算面積  不一定要overlap removing也可以算的出來
　

22.

BGNLIB

BGNCEL A

BGNREF B 20 10 0 0 ENDREF

BGNRECT 10 40 40 50 ENDRECT

BGNREF B 60 10 0 0 ENDREF

BGNRECT 80 20 90 50 ENDRECT

ENDCEL

BGNCEL B

BGNRECT 0 0 10 20 ENDRECT

BGNRECT 20 0 30 20 ENDRECT

ENDCEL

ENDLIB

代表的圗為

那如果A 參考到的B有做逆時針旋轉180度，也就是

BGNCEL A

BGNREF B 20 10 0 2 ENDREF

BGNRECT 10 40 40 50 ENDRECT

BGNREF B 60 10 0 0 ENDREF

BGNRECT 80 20 90 50 ENDRECT

ENDCEL



那BGNREF B 20 10 0 2 ENDREF 的20 10，是不是指原來B的(0,0)這個點?

也就是說圖形變成

　

或是BGNREF B 20 10 0 2 ENDREF 的20 10，是指經過旋轉後的ref cell，新的左下角座標?

ans:

是(旋轉或翻轉後的)B中的原點(0,0)落在A中的座標
　

23.

請問第22題......
意思就是說flection後或rotation後的左下角座標是(20,10)????
　

ans:

不是左下角, 是B的(0,0)落在A中的位置,
只是恰好在這個例子中, B的左下角剛好是B的(0,0),
試想如果B中一個polygon都沒有, 如何定義左下角.

問題22的第二個圖是對 "BGNREF B 20 10 0 2" 正確的解釋.

另外請大家也回頭看第五問題的答案說明. 請注意
"BGNREF ... ENDREF" 敘述定義了cell間的hierarchy,
與cell內的polygon多寡無關, 而"左下角"會受polygon多寡影響.
再強調一次, 各位的output必須與input有相同的 "BGNREF.."敘述,
因為題目要求相同的hierarchy.
　

24.

上圖 B 的寬和高為 30和20
請問 A的寬高為何?

ans:

本題與cell的寬高無關 不需要定義它
圖中A的框框只是表示哪些東西在它裡面
不表示A的寬高 框框也與A的原點無關
　

25.

 請問 rotation與reflection是否不需要考慮所有ancestor的影響.
亦或 A ref B, B ref C,
當 A 並非以 0 0 ref到B時,在展開C時也要對應B相對於A的orientation做
座標的修正?
　

ans:

答案是要

這個問題在題目的定義中應該很清楚
如果對這個答案還有疑問 請務必再思考
　

26. [通告]

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

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

27.

承上次的問題,
請問: 若與cell的寬高無關, 那上圖中block a 旋轉90度後的x座標如何決定 ?

ans:

舉個例子
===============================
BGNCEL A
BGNREF B 10 0 0 1 ENDREF
ENDCEL

BGNCEL B
BGNRECT 20 10 50 30 ENDRECT
ENDCEL
==============================
BGNCEL AA
BGNREF BB 10 0 0 0 ENDREF
ENDCEL

BGNCEL BB
BGNRECT -30 20 -10 50 ENDRECT
ENDCEL
==============================
BGNCEL AAA
BGNRECT -20 20 0 50 ENDRECT
ENDCEL
=============================

B中的矩形對B的原點旋轉90度後  就會像BB
把BB的原點放在(10,0)的點上  就會像AAA

A, AA, AAA都表示了相同的一個layout