Abstract
關於積體電路標準元件(Standard Cell Placement) 的問題，由於目前用程式所解出來的結果不會和用人工排列所得到的結果相差太多。所以，許多的焦點已經轉移到如何加快程式的執行速度。此篇論文主要是在一個被稱為hypercube 的多處理器系統 (multiprocessor system)上發展一個以min-cut 方法為基礎的平行演算法。我們所選用的min-cut 方法是由F-iduccia 和Mattheyses所提出，是一個能夠在線性時間複雜度(linear time comple-xity) 內完成分割工作的方法。有關我們平行化的做法是每次分割完後的每個小部份都擁有各自的處理器去執行下次的分割工作。為了配合hypercube 多處理器系統的特性與架構，我們發展了一套轉換規則將平行化的觀念實際對應到hypercube 多處理器系統上。同時，我們也製出一套處理器位置對應規則用來隨時追蹤記錄那個處理器佔據晶片上的那個角落。另外，我們也將二個相當不錯的觀念 (terminal propagation及shyffle)做些修改以適合在hypercube 架構上執行並將它們納入平行演算法中，另外還要提的是透過使用假元件(dummy cell)的技巧，不必修改被選用的 min-cut程式就能同時考慮到terminal propagation。由於本所目前沒有hypercube 機器，所以我們是在Intel 公司的iPSC模擬軟體上 (裝置在 VAX8550上) 執行我們用C 語言寫成的平行程式。