由於製程技術的提升，電路佈局漸趨複雜，電路佈局上的設計規則檢查(Design Rule Checking)也隨著越來越耗時。電路佈局涵蓋了許多不同的幾何多邊形，因此用來驗證電路有沒有符合技術上需求的設計規則檢查也是由幾合運算所組合而成，加上現在多機器(multi-machine)越來越普及，採用分散式的方法來處理這些幾何運算也成為了一個重要的發展方向。我們在本篇論文中便提出了一個新的分散式演算法來實作基本的幾何運算，用來減少在電路佈局上做設計規則檢查所耗費的時間，藉此節省時間上的成本。在我們的方法中，我們將電路佈局分成許多各自的小區域個別處理幾何運算，利用階層式架構來減少處理的資料量和降低運算的複雜度，不僅如此，我們利用些小技巧讓更多的幾何運算可以同步的進行，使得分散式演算法可以更有效率。設計規則檢查最重要的就是結果精確，我們的方法也可以確保在將電路佈局分成不同區域個別處理時，不會產生出錯誤的結果。在最後的實驗數據上，也可以看出我們的分散式方法是非常有效的，而且在更大更複雜的電路佈局上加速的效果更為明顯。

This thesis introduces a novel distributed algorithm for performing the layout geometry operations usually found in design rule checking, layout verification, and mask synthesis. A large number of machines are typically available to the user during the mask synthesis flow. As multiple machines/cores become more ubiquitous, even designers using layout verification tools will have access to a large set of machines. Therefore, an efficient and scalable distributed algorithm for performing sequences of layout geometry operations will be of great value to both designers and mask synthesis engineers.

This thesis presents such an algorithm. Given a layout and a sequence of layout geometry operations, the proposed algorithm divides the layout into several partitions. The given sequence of layout geometry operations is executed in parallel on different partitions. New partitions are derived from the original set of partitions and the sequence of geometry operations is repeated on larger partitions with much fewer polygons. This process continues until it produces a partition that covers the entire layout area. A key feature of the proposed algorithm is that it is correct-by-construction - i.e., each partition is guaranteed to generate a subset of the correct results. Complete and correct results are generated for each layout geometry operation for the entire layout when the operation completes execution on all the partitions. The proposed algorithm was implemented in Gearman, an open-source distributed framework. Results on large industrial layouts show good performance and scalability.

[1] Gearman. http://gearman.org/.
[2] Calibre user’s manual.
[3] Hercules user’s manual.
[4] G. E. Bier and A. R. Pleszkun ”An algorithm for design rule checking on a multiprocessor,” Proc. of Design Automation Conf., pp. 299–304, 1985.
[5] P. Banerjee, ”Parallel algorithm for VLSI computer-aided design applications,” Prentice-Hall, Englewood Cliffs, NJ, 1994.
[6] H. Folberth, J. Keinert, J. Koehl, K. Pollmann, and O. Rettig ”Method and apparatus for enabling parallel layout checking of designing VLSI-chips,” United States Patent Publication - Pub No. US 2001/6237128 B1, 2001.
[7] F. Gregoretti and Z. Segall, ”Analysis and evaluation of VLSI design rule checking implementation in a multiprocessor,” Proc. Int. Conf. Parallel Processing, pp. 7–14, 1984.
[8] N. Hedenstierna, K. O. Jeppson, ”A parallel hierarchical design rule checker,” Proc. of European Conference on Design Automation, pp. 142–146, 1992.
[9] S. Koranne, ”A high performance SIMD framework for design rule checking on Sony’s PlayStation 2 Emotion Engine
platform,” IEEE International Symposium on Quality Electronic Design, pp. 371–376, 2004.
[10] J. Marantz, ”Exploiting parallelism in VLSI CAD,” Proc. IEEE Int. Conf. Computer Design, 1986.
[11] K. MacPherson and P. Banerjee, ”Parallel algorithms for VLSI layout verification,” Journal of Parallel and Distributed Computing, Vol. 36, Issue 2, pp. 156–172, 1996.
[12] A. P. V. Pais, M. L. Andio, and C. E. T. Oliveira, ”Developing a distributed architecture for design rule checking,” Proc. of Midwest Symposium on Circuits and Systems, Vol. 2, pp. 678–681, 2001.