專題期末書面報告Obstacle-AvoidingRectilinearClockRoutingwithPreferredDirections一、摘要（Abstract）在超大型積體電路(VLSI)的IC設計中，clockrouting一直是一個很重要的議題，因為在實務操作上，有非常多的問題要考慮。因此在這個專題裡，題目便將原本極度複雜的routing問題簡化：主要是尋找n-pinnet的最短連線，並且以水平線與垂直線來做連接，來避免發生傾斜線段。在連線的時候，必須要避過題目所給定的障礙物，這邊的障礙物就代表了超大型積體電路(VLSI)的IC設計內之晶片。並且有要求在不同的layer，有它連線的方向性，若不遵守其方向性，則所需要花費的cost將會非常大，但是在switch內，則可以行走的方向會剛好和原本那層所規定的方向相反，此外，switch的邊緣也都是可以行走的，這些走法所花費的cost都是極小的。這在超大型積體電路(VLSI)的IC設計中極為重要，它可以手動地增加switchdirectionregion來增加連線的可能性，最常用到此技術的就是當IC中有許多晶片時。除了所有點連接起來的線要越短越好之外，另外要考慮的問題就是clockskew的問題，即要讓同一個net中的每一個sink，與source的連線長度盡量一致，如此才不會發生當有些點已經收到訊號了，另外有些點要等待很久才會收到訊號，這樣容易產生出來的結果不正確。二、簡介（Introduction）2.1問題描述（ProblemDescription）在一個三維空間中，最多十五層的layer（layer可以看成是數學表示中的z軸），由下往上分別編號為1、2、3、…、15。每一層的面積大小最大是10000000*10000000（即以數學表示法為(x,y)從(0,0)到(10000000,10000000)），每個Net最多要被連接的點（即在VLSI的IC設計中的n-pin）是二十個，並且在每一個測試檔裡，Net最多只會有10000條。Net中的所有點都必須以水平線和垂直線連接起來，並且需要避開障礙物。每一層layer除了有特定的線段方向性必須遵守外，它還有routingpitch（即thespacingoftheroutinggrids）必須要遵守，在VLSI的IC設計中，雖然會希望IC體積可以越小越好，但是如果線段之間距離太近，會相互影響到，反而是不好的，因此這邊的routingpitch即是在模擬現實中IC連線的情況。此外，Net中每個點的連線，除了要避開障礙物，以及遵守每一層layer的方向和routingpitch，它的連線線段，不可以和其他的Net相交，簡單來說：就是對於ANet而言，BNet的連線線段可以當作是ANet的障礙物。當將所有Net的所有點全部連接後，要計算出totalwirelength和totalroutingcost，前者表示所用到的實際線段，後者表示整個系統的clockskew，這兩者都是越小越好。2.2軟體功能及特性（FunctionsandFeatures）整個程式執行的速度，以理論上分析，會比較快。因為我們寫作的程式中，沒有用到遞迴的方法，只是做一般的ifelse判斷式。三、演算法（Algorithms）我們所用的演算法是讓他盡量向終點前進，只要遇到障礙物，就讓他移動到障礙物前方，一開始就先把依距離排序好的點，一次兩個點互相連接，直到找完從１到N-1條線，就算是完成了整條線段的演算法。我們的讀檔複雜度是O(n),避開障礙物的複雜度是O(n)產生連線的演算法複雜度是O(n^2)加入線段的複雜度是O(n)排序起始點的複雜度是O(n*lg(n))四、實作（Implementation）4.1資料結構（DataStructures）將資料一行一行讀入，以開頭的字母判斷資料為何，存入建立好的資料結構裡。因為題目已經規定最多一萬條線（即一萬條Net），而且每條線最多一開始有二十個點，所以我們就先開出了一個10000*10000的陣列來存放。比如說：（i，j）＝（2，5）表示的是它存放了Net2的第五個點的資訊，其中包括x、y和layer。4.2程式流程(Flow)讀檔→排序→連線→計算totalwirelength和totalroutingcost→存檔五、實驗結果(ExperimentalResults)5.1工作平台及程式語言(PlatformandProgrammingLanguage)工作平台：Linux作業系統程式語言：c++編譯器：g++5.2測試檔輸出(TestOutput)Input:.chip(100100)(1000800).layer51H1030