GPU accelerated rectilinear steiner tree construction
GPU hızlandırmalı doğrulu steıner ağaç üretimi
- Tez No: 416508
- Danışmanlar: DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 100
Özet
Doğrulu Steiner Ağaç problemi elektriksel tasarım otomasyon alanının temel problemlerinden birisidir.Problem, verilen nokta kümesindeki noktaları kullanarak en kısa uzunluktaki ağaç yapısını bulmayı amaçlamaktadır. Bu amaçla ağaca Steiner noktası adı verilen yeni noktalar eklenmektedir. Doğrulu Steiner ağaç problemi NP-tam olduğu için yaklaşık çözüm veren algoritmalar ana çözüm yaklaşımı olarak görülmektedir. Bu tez değiştirilmiş RST algoritmasının GPU platformlarında paralelleştirilerek hızlandırılmasını sağlamaktadır. GPU platformları çok sayıda işlemci çekirdeği içermektedir ve GPU yüksek sayıda sayısal işlemi aynı anda gerçekleştirebilecek yeteneğe sahiptir. Ancak, GPU'nun kaynaklarının verimli kullanılabilmesi için doğrulu Steiner ağaç problemi uygun şekilde paralelleştirilmelidir. Bu çalışmada, öncelikli olarak iki güncel Steiner ağaç üretim yaklaşımı olan RST ve Değiştirilmiş RST algoritmaları detaylı olarak incelenmiştir ve paralel uygulamaya uygun adımları tespit edilmiştir. Değiştirilmiş RST algoritması hız temellidir ve özellikle büyük problem boyutlarında daha iyi performans elde etmektedir. Ayrıca, Değiştirilmiş RST algoritması paralel uygulamalar için de uygundur. Bu sebeplerden dolayı Değiştirilmiş RST yöntemi temel alınarak yeni bir paralel ve ölçeklenebilir doğrulu Steiner ağaç algoritması önerilmiştir. Önerilen algoritma bütün çözüm adımlarını paralelleştirmektedir ve GPU kaynaklarını verimli kullanmaktadır. Son olarak, algoritmanın performansını değerlendirmek amacı ile gerçek uygulamalar ve rastlantısal üretilmiş test kümeleri için simulasyon sonuçları sunulmuştur, özellikle büyük problem boyutları için önemli hızlanma değerleri gözlemlenmiştir.
Özet (Çeviri)
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.
Benzer Tezler
- GPU-accelerated adaptive unstructured road detection using close range stereo vision
Yakın mesafe stereo görüntü kullanılarak GPU ile hızlandırılmış uyumlu yapısız yol bulma
KADRİ BUĞRA ÖZÜTEMİZ
Yüksek Lisans
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. AHMET BUĞRA KOKU
DOÇ. DR. ERHAN İLHAN KONUKSEVEN
- Gpu-accelerated precomputed discrete visibility fields for real-time ray-traced dynamic scenes under environment lighting
Ortam aydınlatması altında gerçek zamanlı ışın izlemeli dinamik sahneler için ekran kartı hızlandırmalı önceden hesaplanmış ayrık görünürlük alanları
BERİL GÜNAY
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET OĞUZ AKYÜZ
- GPU ile hızlandırılmış gerçek/yarı gerçek zamanlı nesne takibi
GPU accelerated real / semi-real time object tracking
ZAFER GÜLER
Doktora
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AHMET ÇINAR
- GPU accelerated radio wave propagation modeling using ray tracing
GPU hızlandırmalı ışın izleme ile radar dalga yayılımı modellemesi
ALAETTİN ZUBAROĞLU
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. CEVAT ŞENER
DOÇ. TOLGA CAN
- GPU accelerated high-order discontinuous galerkin level set methods for incompressible multiphase flows
Çok fazlı akışlar için yüksek başarımlı yüksek seviyeli süreksiz Galerkin metodları
ALİ KARAKUŞ
Doktora
İngilizce
2015
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET HALUK AKSEL
YRD. DOÇ. DR. CÜNEYT SERT