Sıra | DOSYA ADI | Format | Bağlantı |
---|---|---|---|
01. | Gezgin Satıcı Probleminin Benzetilmiş Tavlama Yöntemiyle Çözümünde Paralel Hesaplamanın Kullanılması | pptx | Sunumu İndir |
Transkript
E M R U L L A H S O N U Ç A K A D E M I K B I L I Ş I M Ş U B A T 2 0 1 5 Gezgin Satıcı Probleminin Benzetilmiş Tavlama Yöntemiyle Çözümünde Paralel Hesaplamanın Kullanılması E M R U L L A H S O N U Ç , B A H A Ş E N , Ş A F A K B A Y I R
İçindekil er Gezgin Satıcı Problemi Benzetilmiş Tavlama Benzetilmiş Tavlama Algoritmasının Paralelleştirilme Nedenleri Literatürde Paralel Benzetilmiş Tavlama BT ile Seri GSP CPU Üzerinde Yapılan Paralelleştirme Çalışmaları GPU Üzerinde Yapılan Paralelleştirme Çalışmaları Sonuç ve Öneriler Kaynaklar 2
Gezgin Satıcı Problemi Gezgin Satıcı Problemi (GSP) bir seyyar satıcının elindeki mallarını n şehirde satmak istemesinden oluşmaktadır. Satıcı tüm şehirlere mümkün olduğu kadar en kısa yoldan ve maksimum bir kez uğrayarak turlamak istemektedir. Problemin çözümünde amaç ise satıcıya en kısa yolu sunabilmektir. 3
Gezgin Satıcı Problemi Optimizasyon konusunda başı çeken konular arasında teorisine göre yer alı . \Hesaplamanın karmaşıklığı\ çözümü NP-Tam (NP-complete) olan en önemlialgorit a problemlerinden biridir. Bu problemleri tam bir şekilde çözebilecek bir algoritma olmadığı kabul edilmektedir. Şu anda çözülmeye çalışılan en büyük problem dünya üzerinde kayıtlı yerleşimi olan her nokta için en kısa yol problemidir. Bu problem 1.904.711 şehir içermektedir 4
Gezgin Satıcı Problemi Çok şehirli GSP’leri çözmek için yaklaşık çözüm üreten sezgisel algoritmalar kullanılmaktadır. Sezgisel algoritmalar, en iyi çözüm hakkında herhangi bir garanti vermemelerine karşılık, en iyi çözüme yakın iyi bir sonucun makul bir sürede bulunmasını sağlarlar. 5
Benzetilmiş Tavlama alanınd a Amacı, Herhangi bir problemiçin geneliyileştirme (global optimization) elde etmek. Herhangi bir fonksiyonun genel minimum veya maksimum (global minimum) değerini elde etmek. Özellikle matematiksel modellerle gösterilemeyen kombinasyonel problemlerin eniyileme uygulamalarında tercih edilir. 6 Bilgisayar bilimlerinde,özellikle hesaplama kullanılmaktadır.
Benzetilmiş Tavlama Yöntem bölgesel en iyi çözümlere (local optimum) takılmamak için kullanılır. Soğutma işlemi bu algoritmada daha iyi sonuçların bulunmasını sağlayacak yeni komşu çözümlerin üretilmesini sağlar. Kirkpatrick ve arkadaşları tarafından 1983 yılında önerilmiştir. 7
Benzetilmiş Tavlama // İlk durum, enerji. // Başlangıçta en iyi çözüm. // İterasyon sayısı // İterasyon bitene kadar döngüde kal: // Sıcaklığın düşürülmesi // Yeni bir konfigürasyon seç. // Enerjiyi hesapla. s ← s0; e ← E(s) sbest ← s; ebest ← e k ← 0 while k < kmax and e > emax T ← temperature(k/kmax) snew ← neighbor(s) enew ← E(snew) if P(e, enew, T) > random() the // Yeni durum kabul edilebilir mi? s ← snew; e ← enew if e < ebest then sbest ← snew; ebest ← enew k ← k + 1 return sbest // Evet ise mevcut durumu değiştir // Enerji daha düşükse en iyi çözüm yap. // Mevcut durumu en iyisiyle değiştir // İterasyon sayısını artır. // En iyi durum bulundu. 8
Benzetilmiş Tavlama Algoritma rastgelelik üzerine kurulu bir yöntemdir. Literatürde yönteminbirden çok kez uygulandığı görülmüş ve daha iyi sonuçlar elde edilmiştir. BT’de genel olarak 4 ana parametre vardır. Bunlar: Başlangıç Sıcaklığı, Soğutma Katsayısı, Hedef Sıcaklık ve İterasyon Sayısıdır. 9
Benzetilmiş Tavlama Algoritmasının Paralelleştirilme Nedenleri 10 Seri algoritmada her adımda tek bir çözüm bulunur ve mevcut ile karşılaştırılır. Günümüzde kullanılan paralelleştirme yöntemleri kullanılarak her adımın iş parçacıklarına dağıtılmasıyla birden fazla çözüm üretilip bunlar için en uygun olanı seçebilmek mümkündür. Seri algoritma için gereken süre içerisinde paralel bir yöntemde birden fazla çözüm üretilerek daha iyi sonuç bulabilme ihtimali de artmış olmaktadır.
Literatürde Paralel Benzetilmiş Tavlama Literatürde BT ile ilgili yapılan paralelleştirme çalışmalarıGraphics Processing Unitteknolojisinin gelişmesiyle birlikte (GPU ) Centr al Processing Unit (CPU)’dan GPU’ya doğru kaymıştır. Yapılan birçok çalışmada, CPU ve GPU arasında performans değerlendirmeleri yapılmış, kriter olarak süre ve sonuçların doğruluğu değerlendirilerek analizlerde bulunulmuştur. 1 1
Literatürde Paralel Benzetilmiş Tavlama Kullanılan iş parçacığı sayısı da bir başka kriter olarak ortaya çıkmaktadır. Algoritmanın CPU üzerinde çalışırken işletim sistemi tarafından iş parçacıklarının meşgul edilmesi gibi sebepler CPU’yu bu konuda dezavantajlı hale getirildiği belirtilmiştir. Ayrıca GPU teknolojisinin gelişmesinden kaynaklı ortaya konulan yeni çalışmalar ve yaklaşımlar ile sonuçların her geçen gün daha da iyileştirildiği görülmektedir. 1 2
BT ile Seri GSP kodlanar akuygulanmıştır. GSP yaygın bir problem olduğundan paralelleştirme çalışmaları GSP üzerinde test edilmiştir. GSP için veri seti olarak TSPLIB kütüphanesinde bulunan Berlin52 veri seti kullanılmıştır. Berlin52 veri seti için optimum değer 7542’dir. 13 Öncelikle program seri olarak
BT ile Seri GSP Seri çalıştırılan programda BT’ye ait parametreler değiştirilerek probleme uygun hale getirilmeye çalışılmıştır. İterasyon sayısı olarak 1000 belirlenmiştir. Her iterasyonda yaklaşık 30000 adım test edilmiştir. Seri çalıştırılan programda BT’ye ait parametreler değiştirilerek probleme uygun hale getirilmeye çalışılmıştır. 1 4
BT ile Seri GSP Toplamda 92 adımdamaliyet indigenmiş, sonuçlar grafik olarak Şekil 1’de gösterilmiştir. En düşük maliyet 9417 olarak bulunmuştur. Programın parametre değerleri ise şunlardır: Başlangıç Sıcaklığı = 1000000000, Soğutma Katsayısı = 0.999, Hedef Sıcaklık = 0.0001, İterasyon Sayısı = 1000. 1 5
BT ile Seri GSP 21500 2000 0 18500 17000 1550 0 14000 12500 11000 9500 8000 6500 1 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 91 92 16 Seri Uygulamada Toplam Maliyet Şekil 1. BT’nin seri çalıştırılması sonucunda elde edilen maliyet değerleri.
CPU Üzerinde Yapılan Paralelleştirme Çalışmaları CPU üzerinde paralelleştirme çalıştırmaları yapılmadan önce BT’nin paralel versiyonları incelenmiş ve en optimum paralel algoritma üzerinde kodlama çalışmaları yapılmıştır. Bu algoritmanın çalışma prensibi şu adımları içerir: 1. Başlangıç sıcaklığı T ve ilk konfigürasyo n E ile algoritma ayarlanır. T ve E değerleriher bir işparçacığına gönderilir. 2. Her biriş parçacığı seri birşekilde BT algoritmasını çalıştırır ve maliyet hesabı yapar. 1 7
CPU Üzerinde Yapılan Paralelleştirme Çalışmaları 3. Her bir iş parçacığı işlemini tamamladıktan sonra elde ettiği değeri ve konfigürasyonu ana iş parçacığına gönderir. Burada en düşük enerjiye(maliyete) sahip değer ve konfigürasy on belirlenen bir karşılaştırmayöntemiyle ya da algoritma yardımıyla belirlenir. 4. Elde edilen yeni konfigürasyon tekrar iş parçacıklarına dağıtılır. 2. ve 3. adım sıcaklık değeri hedef sıcaklığa indirgene kadar tekrarlanır. Algoritma bu şekilde sonlandırılır. 1 8
CPU Üzerinde Yapılan Paralelleştirme Çalışmaları CPU üzerinden parallelleştirme çalışmalarında OpenMP kullanılmıştır. OpenMP birçok işletim sistemleri üzerinde çoğu işlemci mimarisi üzerinde Fortran, C+ +, C programlama dillerinde çoklu platform paylaşımlı bellek çoklu işlemeyi destekleyen bir uygulama geliştirme arayüzüdür. Toplamda 20 adımda maliyet indigenmiş, bu indirgeme durumlarının farklı iş parçacıkları tarafından elde edildiği görülmüştür. En düşük maliyet 8099 olarak elde edilmiştir. 1 9
CPU Üzerinde Yapılan Paralelleştirme Çalışmaları OpenMP kullanılarak CPU üzerinde 8 iş parçacığı ilerogram çalıştırılmıştır. Sonuçlar Şekil 2’te 2 0 23000 20000 17000 14000 11000 8000 5000 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 18 19 20 gösterilmiştir. Paralel Uygulamada (CPU) Toplam Maliyet Şekil 2. BT’nin CPU üzerinde paralel çalıştırılması sonucunda elde edilen maliyet değerleri.
GPU Üzerinde Yapılan Paralelleştirme Çalışmaları GPU’nun CPU’ya nazaran en önemli özelliği çekirdek sayısının fazla olmasıdır. GPU’nun binlerce iş parçacığı aynı anda işlem yapabilmekte ve paralel hesaplamaya uygun dizayn edilmesi neticesinde verimli sonuçlar elde edilebilmektedir. GPU üzerinde CUDA kullanılarak yapılan çalışmada CPU tarafında kullanılan algoritma temel alınmıştır. Algoritmanın çalıştırılması esnasındaki GPU’daki iş parçacığı sayısı CPU ile karşılaştırma açısından 8 olarak belirlenmiştir. 2 1
GPU Üzerinde Yapılan Paralelleştirme Çalışmaları 2 2 Şekil 3. CPU ve GPU yapısının karşılaştırılması. NVIDIA’nınGPU (grafik işlem birimi) kullanarak hesaplama CUDA , gücün ü büyük ölçüde artışlara olanak p rformansın da veren paralelhesaplam mimarisidir.
GPU Üzerinde Yapılan Paralelleştirme Çalışmaları maliyet 7976 olarak bulunmuştur.Toplamda 5 adımdamaliyet indirgenmiş ve Şekil 4’tegösterilmiş ir. En düşük maliyet 25. Adımda bulunmuştur. Sonraki yaklaşık 975 adımda daha uygun bir sonuç elde edilememiştir. Bu açıdan bakılacak olursa GPU’daki hesaplama yetenekleriyle sonuca daha az adımda erişilmiştir. 23 Algoritmanın çalıştırılmasısonucunda en düşük
GPU Üzerinde Yapılan Paralelleştirme Çalışmaları 0 200 0 400 0 600 0 800 0 1000 0 1200 0 1 2 3 4 5 24 Paralel Uygulamada (GPU) Toplam Maliyet Şekil 3. BT’nin GPU üzerinde paralel çalıştırılması sonucunda elde edilen maliyet değerleri.
GPU Üzerinde Yapılan Paralelleştirme Çalışmaları Yapılan çalışmalardaki ilk amaç maliyeti düşürmekolduğundan sürelerdeğerlendirilmemiştir. Gerek kriter CPU’d a olara k gerek se PU’da uygulanan paraleleştirme seri uygulamaya nazaran daha uzun sürmüştür. GPU tarafında kullanılan teknolojinin son teknoloji olmaması (Compute Capability 1.1) ve değerlendirilen veri setinin küçük boyutlu olması bunda etken olarak değerlendirilebilir. 2 5
Sonuç ve Öneriler26 Sonuca bakılacak olursa BT algoritmasının bu tarz problemler için uygun bir yöntem olduğunu söylemek mümkündür. Ayrıca problemin çözümüne göre uygun parametreler belirlemek optimum çözüm elde etmek konusunda etkilidir. İterasyon sayısının artması yani algoritmayı birden çok kez çalıştırmak daha iyi sonuçların elde edilmesine imkan sağlamak ile birlikte zaman problemini ortaya çıkarmaktadır. Çözülecek problemin boyutu arttıkça zaman problemi de büyük bir problem haline gelmektedir. Bu yüzden paralel çalışmaların bu konudaki çözümleri önemlidir.
Kaynakl ar 27 http://tr.wikipedia.org/wiki/Sezgisel_algoritma http://bilgisayarkavramlari.sadievrenseker.com/2009/ 11/23/ simulated-annealing-benzetilmis-tavlama/ http://www.yapay- zeka.org/modules/wiwimod/index.php? page=Simulated+An nealing Kirkpatrick S., Gerlatt C. D. Jr., Vecchi M.P., “Optimization by Simulated Annealing”, Science, 220, 671-680, (1983). http://163.18.62.64/wisdom/Simulated%20annealing %20ove rview.pdf (Simulated annealing overview, Franco Busetti) http://en.wikipedia.org/wiki/Simulated_annealing Petru Eles, Simulated Annealing Lecture Notes, Department of Computer and Information Science (IDA) Linköpings Iniversitet, http://www.ida.liu.se/~petel/
Kaynakl ar 28 http://en.wikipedia.org/wiki/Traveling_salesman_problem (Travelling salesman problem - Wikipedia, the free encyclopedia) http://www.matematikdunyasi.org/arsiv/PDF/03_3_37_40_ GEZ GIN.pdf (Gezgin Satıcı Problemi, Haldun SURAL) http://www.iwr.uni- heidelberg.de/groups/comopt/software/TSPLIB95/(TSPLIB - Ruprecht-Karls-Universität Heidelberg). http://www.ccs.neu.edu/course/com3620/projects/simul_an nealin g/parallel-final-report.doc (Parallel Simulated Annealing) http://openmp.org/wp/ (The OpenMP® API specification for parallel programming). http://www.nvidia.com/object/cuda_home_new.html (CUDA Parallel Computing Platform) http://docs.nvidia.com/cuda/curand/ (cuRAND:: CUDA Toolkit Documentation)
~ Son ~ 2 9 Dinlediğiniz için teşekkürler. Emrullah SONUÇ – Akademik Bilişim (Şubat 2015)