Paralel Programlama Nedir?

Share

Geleneksel yöntemlerde programlar seri hesaplamalar şeklinde yazılır.

  • —Program bir bilgisayarda bir işlemci tarafından yürütülür.
  • —Problem farklı komut serilerine bölünür.
  • —Her komut bir diğerinden sonra işleme alınır.
  • —Birim zamanda sadece bir komut işlenir.

serialProblem

Basit şekliyle paralel programla, bir problemin çözümünde birden çok hesaplama kaynağının aynı anda kullanılmasıdır.

  • —Problemin çözümünde birden çok işlemci kullanılır.
  • —Problem eşzamanlı çözülmek için farklı parçalara bölünür.
  • —Her parça farklı komut serilerine bölünür.
  • —Komutlar aynı anda farklı işlemciler üzerinde işlenir.

parallelProblem

Nerelerde kullanilir?

—Bilim ve mühendislik alanlarda

  • Bioscience, Biotechnology, Genetics
  • Chemistry, Molecular Sciences
  • Mechanical Engineering
  • Computer Science, Mathematics

—Endüstriyel ve ticari alanlarda

  • Databases, data mining
  • Web search engines, web based business services
  • Financial and economic modeling

​Neden kullanilir?

—Zaman ve para kazanmak

  • Teorik olarak bir işe daha fazla kaynak ayrıldığında tamamlanması daha kısa sürer ayrıca paralel bilgisayarların maliyetleri süper ilgisayarlara göre daha ucuz.

—Büyük problemleri çözmek

  • Çok büyük yada karmaşık problemlerin tek bilgisayarda çözümü çok zor yada imkansız olmakta.

—Aynı anda kullanımı sağlamak

  • Tek bilgisayarda birim zamanda bir işlem yapılmakta fakat birden fazla bilgisayarda çok daha fazla iş aynı anda yapılır. Özellikle binlerce kişinin aynı anda kullandığı sistemlerde.

—Lokal olmayan kaynakların kullanımı

  • Network üzerinden yada internetten diğer bilgisayarların kaynaklarının kullanılabilir.

—Seri programlamanın limitleri

  • İşlemci teknolojisinin küçülme sınırları.
  • Ekonomik limitler. Bir işlemcinin daha hızlı yapılabilmesi maliyetli.

​Konsept ve termoloji

—Tek işlem, tek data (Single instruction, single data (SISD))

  • Seri bilgisayarlardır.
  • Birim zamanda sadece tek bir işlem yapılır.
  • Birim zamanda sadece tek bir data akışı kullanılır.

sisd

—Tek işlem, çoklu data (Single instruction, multiple data (SIMD))

  • Paralel bilgisayar çeşididir.
  • Birim zamanda sadece tek bir işlem yapılır.
  • Birden çok data akışı kullanılır.
  • Senkronizedir.

simd

—Çoklu işlem, tek data (Multiple instruction, single data (MISD))

  • Paralel bilgisayar çeşididir.
  • Birim zamanda birden çok işlem yapılır.
  • Birim zamanda sadece tek bir data akışı kullanılır.

misd

—Çoklu işlem, çoklu data (Multiple instruction, multiple data (MIMD))

  • Paralel bilgisayar çeşididir.
  • Birim zamanda birden çok işlem yapılır.
  • Birden çok data akışı kullanılır.
  • Senkron yada asenkron olabilir.

mimd

Bellek Yapısı

—Paylaşımlı bellek(Shared Memory)

Genel özellikleri

  • Paralel bilgisayarlarda çeşitli paylaşımlı bellek çeşitleri vardır fakat genel olarak bütün işlemciler belleğe global adres uzayından erişir.
  • Çoklu işlemciler işlemlerini kendi başlarına yaparlar fakat aynı bellek kaynağını paylaşırlar.
  • Bir işlemcinin bellek alanında yaptığı değişiklik bütün işlemciler tarafından görülür.
  • Paylaşımlı bellek kullanan bilgisayarlar belleğe ulaşım zamanlarına göre iki ana sınıfa ayrılırlar UMA ve NUM
  • Uniform Memory Access (UMA):

    • Simetrik çoklu işlemcili (SMP) bilgisayarlarda kullanılır.

    • Belleğe erişim ve erişim hızları eşittir

​​shared_mem

  • Non-Uniform Memory Access (NUMA):

     

    • Fiziksel olarak birbirlerine bağlı iki yada daha fazla SMP’den oluşur.
    • Bir SMP direk olarak diğer SMP’lerin belleklerine ulaşabilir.
    • Bütün işlemciler bütün belleklere aynı erişim süresine sahip değildir.

​​numa

Paylaşımlı belleğin avantajları:

  • —Bellek erişimi için global adres uzayının kullanılması programlama açısından kullanıcı dostudur.
  • —İşlemciler arası data paylaşımı hızlıdır.

Paylaşımlı belleğin dezavantajları:

  • —Paylaşımlı belleği kullanan işlemci sayısı artırılırsa işlemci bellek arasındaki trafik artacağından darboğaz oluşturur.
  • —Belleğin senkronizasyonu ve belleğe doğru şekilde erişilmesi programcının sorumluluğundadır.

Dağıtık bellek (Distributed Memory)

—Genel özellikleri

  • Dağıtık belleklerde bellekler arası iletişim ağı vardır.
  • ​​distributed_mem
  • İşlemcilerin kendi lokal bellekleri vardır. Bir işlemci diğer bellek adreslerini bilmez bu yüzden bellek adresleri için global adres uzayı konsepti yoktur.
  • Her işlemci kendi belleğini organize eder ve yaptığı değişiklikler diğer işlemcilerin belleklerini etkilemez.
  • —Avantajları

     

    • İşlemci sayısı artarsa orantılı olarak bellekte artar.
    • Her işlemci kendi belleğine hemen erişebilir ağ iletişimi ile uğraşmaz.
  • —Dezavantajları

     

    • İşlemciler arası data iletişiminin detaylarından programcı sorunludur.
    • Bellek erişim süreleri farklılık gösterebilir.

Karma bellek (Hybrid Distributed-Shared Memory)

  • —Günümüzde daha çok karma bellek yapısıkullanılıyor.

—hybrid_mem—

  • ——Her bellek modülünün ait olduğu bir işlemci topluluğu var bu kısım paylaşımlı bellek oluyor.
  • —Her bellek işlemci topluluğu da birbirleriyle ağ üzerinden bağlı bu kısımda dağıtık bellek oluyor.
  • —Bu sistem paylaşımlı ve dağıtık bellek sistemlerinin avantaj ve dezavantajlarını hepsini taşıyor.
     

—Paralel algoritmalar

Böl ve Yönet (Divide & Conquer)

  • —Böl ve Yönet algoritması, orijinal problemi daha kolay çözmek için, problemi alt problemlere bölen, bölünen alt problemleri çözen, orijinal problemin çözümünü oluşturmak için, alt problemlerin çözümlerini birleştiren bir algoritmadır. —Böl ve yönet paradigması program modülaritesini yükseltir, genellikle basit ve verimli algoritmalara yol açar. Bu nedenle sıralı algoritma tasarımcıları için güçlü bir araç olduğu kanıtlanmıştır. Böl ve yönet paralel algoritma tasarımı daha da önemli bir rol oynamaktadır. İlk adımda oluşturduğunuz alt problemler genellikle bağımsız olduğundan, bunlar paralel olarak çözülebilir. Genellikle alt problemler özyinelemeli olarak çözülür ve böylece bir sonraki bölme adımında paralel olarak çözülecek daha çok alt problem elde edilir. —Ancak bilinmelidir ki, yüksek derecede bir paralel algoritma elde etmek için, böl ve yönet’in bölme ve birleştirme adımlarının paralelize (birlikte yürütülmesi) olması gerekir. Orijinal problemi mümkün olduğunca çok sayıda alt probleme bölerek, paralel olarak çözmek paralel algoritmalarda oldukça yaygındır. Paralel Böl ve Yönet örneği için, sıralı Merge Sort algoritması düşünün. Merge sort, n adet girilmiş elemanı alır ve onları sıralayarak geri verir. Bu algoritma, n elemanlı bir dizi iki parçaya bölünüp, bölünen her dizi öz yineli olarak sıralanıp ve sıralanmış yarı diziler tekrar birleştirilerek çalışır.

Paralel İşaretçi Teknikleri

  • —Listeler, ağaçlar, graflar gibi geleneksel sıralı tekniklerin bir çoğunu paralel tekniklere çevirmek kolay değildir. Örneğin  bağlı liste elementlerin dolaşmak, ağaç düğümlerini sıralı gezmek, graflarda derinlik öncelikli dolaşmak sıralı tekniklerdir. Şans eseri bu teknikler, neredeyse aynı kuvvetteki paralel tekniklerle genellikle yer değiştirilebilir. —Paralel algoritmaların tasarımı, iş karmaşıklığını en aza indirecek düzeyde olması önemlidir. İşaretçi atlama tekniği bağlı liste ve ağaç yapıları için kullanılan yaygın bir teknik olup paralel programlama tekniklerinde sık kullanılan bir yöntemdir. —Basit olarak ifade etmek gerekirse işlem dizisinde bir elemanın adresini diğerinin değerine atama işlemidir.
Rastgeleleştirme (Randomization)
  • —Paralel algoritmalarda rastgele sayılar kullanılır. İşlemciler rastgele sayıları kullanarak genelde iyi sonuçlara ulaşmak amacıyla komutları yerel olarak işleyebilirler. Rastgele sayıların paralel programlamada en yaygın kullanılan 3 örneği; örnekleme, simetri kırılması ve yük dengelemedir

    —Örnekleme

    • ​Rastgeleliliğin paralel programlama kullanımının bir çeşidi de bir element setinden temsilci örneğin seçilmesidir. Genellikle problem seçilen bu örnekle çözülür. Bu örnekte kullanılan çözüm yöntemi, orijinal veri setinin çözümü için bir rehber oluşturmuş olur.  Örneğin, elimizde bir tamsayı kümesi var ve biz bunu sıralamak istiyoruz. Bunu tamsayı kümesini alt kümelere bölerek ve her bir kümeyi kendi içinde sıralayarak bu işi yapabiliriz. Bu algoritmanın iyi çalışması için, kümelerin birbiri ile örtüşmeyen sayı değerleri ile temsil edilmesi ve her bir kümenin yaklaşık olarak eşit sayıda anahtar içermesi gerekmektedir. Rastgele örneklem, aralık sınırlarının belirlenmesinde kullanılır. Öncelikle her bir işlemci kendi rastgele örneklem anahtarlarını seçer. Sonra seçilen bütün anahtarlar birlikte sıralanır. Son olarak bu anahtarlar sınır değerler olarak kullanılır. Bu tarz rastgele örnekleme ayrıca birçok paralel hesaplama geometrisinde, graflarda ve kelime eşleştirme algoritmalarında da kullanılmaktadır

    Simetri Kırılması

    • —Rastgeleliliğin bir başka kullanımı da simetri kırılmasındadır. Örneğin, bir çizgede bağımsız düğümler setinin seçilmesi problemini düşünelim. (birbiri ile komşu olamayan düğümler seti bağımsız düğümlerdir.) diğer bütün düğümlerle paralel olarak her bir düğümün bağımsız düğümler setine katılıp katılmaması gerektiğine karar verilmesi gerektiğini düşünün. Eğer düğümlerden birisinin bağımsız düğümler setine katılmasına karar verilirse, ona komşu olan diğer bütün düğümlerin sete katılmaması gerekmektedir. Eğer her bir düğümün yerel yapısı aynıysa, her bir düğüm eşit sayıda komşuya sahipse, hangi düğümlerin sete katılacağına anlık olarak karar vermek oldukça zordur. Böyle zor bir çıkmaz durum, düğümler arasındaki simetriyi kırmak için rastgeleliliğin kullanılmasıyla çözülebilir.

    Yük dengeleme

    • —Rastgeleliliğin üçüncü kullanım şeklide yük dengelemedir. Çok büyük miktardaki veri kümesini yaklaşık olarak eşit büyüklükte alt kümelere hızlıca ayırmanın bir yolu da her bir maddeyi rastgele olarak alt kümelere atamaktır.  Bu teknik en iyi, alt kümelerin ortalama boyutu en azından logaritmik olarak ilk veri kümesinin boyutlarında olduğu zamanlarda çalışır.

Sonuç

Günümüzde kullanılan bilgisayar donanımları çok çekirdekli olmasına rağmen, kullandığımız yazılımların çok az bir kısmı paralel olarak programlanmıştır. Bu sebeple seri programlanan bu yazılımlar donanımı etkili olarak kullanamamakta ve kullanıcının zaman kaybetmesine sebep olmaktadır. Paralel programlamada 3 temel algoritma kullanılmaktadır. Paralel programlama algoritmalarının kendine özgü kullanım alanı bulunmaktadır. Hangi algoritmanın kullanılacağı ya da programın paralel programlamaya uygun olup olmadığı programın yapısıyla doğrudan ilgilidir. Bu sebeple herhangi bir paralel programlama algoritmasının diğerinden daha iyi ya da kötü olduğunu söylemek mümkün değildir. Fakat paralel programlamanın temel mantığında bir problemi küçük parçalara ayırmak olduğu için en sık kullanılan algoritmanın “böl ve yönet” algoritması olduğu söylenebilir. Çok çekirdekli işlemcilerin kişisel ve taşınabilir bilgisayarlarda dahi yaygınlaşması paralel programlamaya duyulan ihtiyacı ve bu alanda yapılan araştırmaların önemini her geçen gün arttırmaktadır.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

© Copyright 2000 – 2019 Hermes İletişim, Tüm Hakları Saklıdır.
İletişim: 0(232)483-0444destek@hermesiletisim.netcrm@hermesiletisim.net

hermesiletisim.net