GPU accelerated rectilinear steiner tree construction

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Elektrik ve Elektronik Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2015

Öğrenci: DİNÇER ÖZCAN

Danışman: CÜNEYT FEHMİ BAZLAMAÇCI

Özet:

The Rectilinear Steiner Tree (RST) problem is one of the fundamental problems in circuit design automation. The problem is to find the tree structure that connects all points in the input set such that total tree length is minimized. In order to reduce the total length, extra points, called Steiner points, are introduced to the tree. Since the RST problem is NP-complete, developing heuristic algorithms which can produce near optimal solutions is the primary approach to solve the problem. This thesis accelerates the Modified RST algorithm through parallelizing and using a state of art Graphics Processing Unit (GPU) platform. GPUs contain many computational units and they can provide massive computational power. However, it is not trivial to map an RST problem instance to GPU. In order to benefit from the resources of GPU, the problem has to be parallelized and suitably implemented. In this study, we thoroughly investigate two recent rectilinear Steiner tree algorithms, RST and Modified RST, and identify parallel implementation opportunities. Modified RST algorithm is speed oriented and has better performance especially on large problem instances. Moreover, it is suitable for paralel implementation. Thus, we propose a paralel and scalable RST solution based on Modified RST algorithm, which paralellizes the whole algortihm and utilizes GPU resources more efficiently. Computational results for realistic applications and random generated benchmarks are presented to evaluate our implementation. Significant speed up is observed especially for large problem sizes.