定時電路設計問題：定時電路是一個VLSI 芯片的關鍵部件，這里給出一個定時電路的
簡單模型：一棵具有n 片樹葉的完全平衡二叉樹（其中，n 是2 的冪）。這顆樹的每條
邊e 有一個對應的長度le（le>0）。從根到一片給定樹葉的距離是從根到這片樹葉的路徑
上的所有邊的長度之和。
根產生一個時鐘信號，它沿著這些邊傳播到樹葉，信號到達一片給定樹葉所用的時間是
與從根到這片樹葉的距離成比例的。如果所有的樹葉到根的距離都不相同，那么信號不會在同一時間到達樹葉，這是定時電
路設計中的一個大問題，我們需要樹葉完全同步，全都同時接受這個信號，為做到這一
點，我們將不得不增加某些邊的長度，以使得所有根到樹葉的路徑有同樣的長度，如果
我們達到這個要求，那么這棵樹（帶有它的新邊長）將稱為零傾斜的。我們的優化目標
是以某種保持所有邊長之和最小的方式達到零傾斜。給出了一個增長某些邊長的算法，使得得到的樹有零傾斜并且總邊長最小。
標簽：
VLSI
定時電路
設計問題
芯片
上傳時間：
2016-08-28
上傳用戶：zhangyi99104144
