Geri Dön

GPU accelerated rectilinear steiner tree construction

GPU hızlandırmalı doğrulu steıner ağaç üretimi

  1. Tez No: 416508
  2. Yazar: DİNÇER ÖZCAN
  3. Danışmanlar: DOÇ. DR. CÜNEYT FEHMİ BAZLAMAÇCI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2015
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. AHMET BUĞRA KOKU

    DOÇ. DR. ERHAN İLHAN KONUKSEVEN

  2. 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

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET OĞUZ AKYÜZ

  3. 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

    Türkçe

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AHMET ÇINAR

  4. 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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. CEVAT ŞENER

    DOÇ. TOLGA CAN

  5. 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

    İngilizce

    2015

    Makine MühendisliğiOrta Doğu Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET HALUK AKSEL

    YRD. DOÇ. DR. CÜNEYT SERT