Abstract
在本篇論文中，我們探討了一個channel routing 上的問題，其特點在於channel 上的接點分割成幾個組，而每一組的任意兩個端點都可以互換。這個問題可以應用到許多方面，而最為人所知的是由logic equivalence 這個性質來分割。Kobayashi 和Drozd 在1984年發表的論文中對此問題最早加以研究。隨後又有幾篇論文也對其探討，而在1986年由Leong 證實了這是一個NP-com-plete的問題。在這幾篇論文中可以得知，這種端點可以交換的channel 所需的繞線面積小於固定端點的channel 。例如在Kobayashi 的論文中，對於Deutsch 的difficult example 做分割後，省下了34％的面積，使用的channel 寬度從28減少到19，而在本篇論文中，我們使之減少到17。我們用三個變數組成的cost function 來評估某一個assignment。這三個分別是routability, channel density，和horizontal span 。而結果也證實了我們的cost function 較以往的準確。除此之外，我們又分別用iterative improvement，Simulatedannealing ，及sequence heuristic來比較執行的效率及效果。結論是sequence heuristic都是最好的，它的速度及效果。結論是sequence heruistic都是最好的，它的速度較simulated annealing 快了數十倍之多，而結果一樣的好。