Problem 3: K-Way Netlist Partitioning
-
Q1: [2001/03/23]
請問現在給的input data有些格式在說明文件沒提到，
* 開始二行一定會給 Cell 與 Net 的個數嗎?
* 所有 Cell的名字裡的號碼，會從1到Cell數，且其中不會跳號嗎?
A1: [2001/03/28]
1. The cell and net numbers are for your
own reference. We won't give the numbers
in every file. So please treat the
lines which start with "#" as comments
and skip them in your program.
2. There could be some net/cell numbers
missing in the test cases.
-
Q2: [2001/03/27]
在給定的測試檔中 ,都有給Cell,Net的總數及k值,如p3-1.in中的前三行
# Total CELL Count : 16743
# Total NET Count : 14605
3
請問在隱藏的測試檔中也有給嗎?是一樣的格式嗎?
A2: [2001/03/28]
The value of k will be given in each test case while the numbers of cells and nets
may be omitted. So you should treat each line starting with "#" as a comment and
skip it in your program.
-
Q3: [2001/04/15]
請問測試檔的 NET1 NET2 ... 有何意義嗎
因為通常這種格式 應該都是採用例如以下的方式
vertex 相鄰 vertex
c1 c2 c4 c3
c2 c1 c5 c6
c3 c1 c4
不曉得是否可以確定一下 真的是用 NET的格式嗎 謝謝
A3: [2001/04/24]
The input format given in the testcases is quite standard in real-world applications.
For example,
NET n1 c2 c3 c4;
describes a net n1 connecting to three cells, c2, c3, and c4 (thus, n1 is a three-terminal
net). Here we don't specify the source of this net. In your format, the net name is missing.
In fact, the net name is quite useful in real applications for reporting some important
information.
-
Q4: [2001/05/29]
請問 是否可在執行時除輸入NetList file外, 另外指定一些參數輸入?
還是一定要寫在程式內?
A4: [2001/05/31]
For the input format, please do follow the description listed in the problem set
because your program will be verified by a verification program.
-
Q5: [2001/05/31]
請問Problem 3 指定的輸出入格式是什麼? 請告知。
ex1a. 如 範例中 所提:
eevlsicad> k-way-part p3-1.in xxx.out 可加參數嗎?
ex1b.
eevlsicad> k-way-part p3-1.in xxx.out retry:1000次 retry-time-limit:1hour
ex2
eevlsicad> k-way-part p3-1.in
please choice sth by judge factor....
please keyin output filename: abc.out
ex3
eevlsicad> k-way-part p3-1.in > xxx.out
若 program 全由 verification program 來驗證，
而我們發展出幾種特色相近，不同的調整performance的參數，
可變通的方式
eevlsicad> k-way-part-method1a p3-1.in xxx.out
eevlsicad> k-way-part-method1b p3-1.in xxx.out para1
eevlsicad> k-way-part-method1c p3-1.in xxx.out para2
但還是有些可貴的、幾近直觀的參數， 須由交談式interactive來判斷決定，
如此也要割捨!?如此就不列入評量，那就太令人感到遺憾了...
所以 指定 的 輸出入格式是只有ex1a型?
A5: [2001/06/01]
Please see Sections 2 and 3 in the problem set for the input/output format.
All programs will be tested based on one set of parameters, if any.
The test engineers from industry won't tune any parameter for you.
Therefore, you should make your best parameter as default.
Nevertheless, this doesn't imply that you are not allow to apply any other set of parameters.
You may still list your results on different sets of parameters in your written report.
Also, you will have a chance to show those effects during the oral presentation if you
advance to the 2nd-round review on July 6.
-
Q6: [2001/05/31]
the definition of balance conditions...?
balanced groups G1, G2, G3, …,GK
.............
The objective of the K-way partitioning problem is to
minimize , under the constraint that the number of cells in group Gi,
denoted by #(Gi), satisfy the size constraints 0.9n/K <= #(Gi) <= 1.1n/K,
for all i = 1, 2, …, K.
若 k=6 而恰巧 #(G1) = #(G2) = #(G3) = #(G4) = #(G5) = 0.9n/K = 0.9n/6 有最小 total cuts，
顯然 #(G6) = 1 - 0.9n/6 * 5 = 1 - 4.5n /6 = 1.5n/6 不合，此組解須放棄....
是否失去 k-way mincut partitioning 原題所追求的精神?
是否改為
1.至少 k-1 組 符合 0.9n/K <= #(Gi) <= 1.1n/K
2.或 固定 6(k) 等份中線，1/6, 2/6, ... 5/6 此 5中線 上下 10%
所以一份最大 10%+ 100% + 10%=120%
一份最小 100% - 10% - 10%=80%
3.或 硬性規定 n/k - 1 <= #(Gi) <= n/k + 1?
4.或 固定 6(k) 等份中線，1/6, 2/6, ... 5/6 此 5中線 上下 5%
所以一份最大 5%+ 100% + 5%=110%
一份最小 100% - 5% - 5%= 90%
即 0.95n/K <= #(Gi) <= 1.05n/K,
A6: [2001/06/01]
The balance condition 0.9n/K <= #(Gi) <= 1.1n/K is quite reasonable.
It says that the size of each partition must be within 10% of the
average size. For the circuit partitioning problem, we are not only
interested in finding a "min-cut partitioning," but also a "balanced
partitioning."
For any questions, send e-mails to cad@cis.nctu.edu.tw.
Last modified: June 1, 2001