A parallel Bees Algorithm implementation on GPU

“A parallel Bees Algorithm implementation on GPU” başlıklı makale Journal of Systems Architecture dergisinin 2014 yılında yayınlanan 60.sayısının 271-279.sayfalarında yayınlanmıştır. Makaleyi Guo-Heng Luo, Sheng-Kai Huang, Yue-Shan Chang ve Shyan-Ming Yuan yazmıştır.

Makaleyi indirmek için:
A-parallel-Bees-Algorithm-implementation-on-GPU
Çalışmada Arı Algoritması için paralel bir yaklaşım geliştirilerek CUBA(CUDA based Bees Algorithm) ismi verilmiştir.

Arı Algoritması bal arılarından esinlenen, popülasyon tabanlı bir arama optimizasyon problem çözüm yaklaşımıdır. Hem komşuluk aramasını, hem de rastgele aramayı kullanır. Sürü zekası tabanlı yaklaşımlar optimizasyon problemlerinin çözüm sürelerini hayli düşürmüştür. Bu yaklaşımlar paralelleştirme yöntemiyle çok daha hızlı bir şekilde sonuca ulaşacak şekilde yeniden uyarlanmaktadır. Burada çözüm kalitesini artırma gibi bir hedef yoktur. Arı Algoritmasına için daha önce sunulan paralel yaklaşımda kolonilerin mevcut işlemcilere bölünmesi esasına göre bir yol izlenmiştir. (H. Narasimhan, Parallel artificial bee colony (PABC) algorithm, in: 2009 World
Congress on Nature & Biologically Inspired Computing, 2009, pp. 306–311.)

Konuyla ilgili benzer bir çalışmada(A.K.R. Mohamad Idris, M.W. Mustafa, A Parallel Bees Algorithm for ATC
enhancement in modern electrical network, in: 2010 Fourth Asia International
Conference on Mathematical/Analytical Modelling and Computer, Simulation,
2010, pp. 450–455.) modern elektrik ağlarında mevcut transfer yeteneğini artırmaya yönelik paralel arı algoritması önerilmiştir.

Arı algoritmasının FPGA (Field Programmable Gate Array – Alanda Programlanabilir Kapı Dizileri) ile de uygulamasının yapıldığına dikkat çekilerek şimdiye kadar GPU üzerinde bir çalışma yapılmadığı belirtilmiştir. Çalışmanın ana amacının GPU üzerinde çalışan paralel arı algoritmasını dizayn etmek ve uygulamak olduğu açıklanmıştır.

Arı algoritmasının temel akış diyagramı:

Parametreler:
n (number of scout bees),
m (number of sites selected out of n visited sites),
e (number of best sites out of m selected sites),
nep (number of bees recruited for best e sites),
nsp (number of bees recruited for the other (m–e) selected sites),
ngh (initial size of patches which includes site and its neighbourhood)
stopping criterion

Komşuluk Daraltma(Neighbourhood shrinking)

Çiçek parçaları : a = {a1. . ., an} olarak tanımlanır ve:

t o anda bulunulan iterasyon sayısını vermektedir.

Yerel bir noktada takılmayı engellemek için gelişimin olmadığı iterasyonlarda değer 0,8 oranında küçültülür.

Kaynağın Terk Edilmesi

Belirli bir iterasyon sonucunda iyileşme sağlanamadıysa işlem durdurulur. Daha iyi bir sonuç üretecek nokta kalmadıysa rastgele bir noktadan yeni bir arama başlatılabilir. İlgili çalışmada da bu tür modifikasyonların yapıldığı bir çalışmadaki(D.T. Pham, M. Castellani, The Bees Algorithm: modelling foraging behaviour to
solve continuous optimization problems, Proceeding of Institute Mechanical Engineering, C: Journal of Mechanical Engineering and Science 223 (12) (2009) 2919–2938.) Arı algoritması kullanılmıştır.

Esnek AC İletim Sistemleri (FACTS) cihazlarının yerleşimi için yapılan bir ilgili bir çalışma incelenmiştir. Bu çalışmada mevcut transfer yeteneği maksimize edilmek istenmektedir. Çalışmada Bees Algorithm (BA), Genetic Algorithm (GA) ve Parallel Genetic Algorithms (PGA) ile güzel sonuçlar elde edilmiş lakin BCO, GPU ile çalışır vaziyete getirilmemiştir.

Oluşturulan paralel yaklaşımda her bir thread kendi kolonisindeki bir bal arısını temsil etmektedir. Koloniler thread ID’lerine göre farklı bloklara bölünmektedir. Her blokta algoritma bağımsız olarak çalıştırılmaktadır. Her iterasyonda değişen bilgiler shared memory’e eklenerek diğer bloklarla paylaşımı sağlanmaktadır. Global memory ile her iterasyonda erişime geçilmemesi gecikme zamanının azalmasına ve boşa zaman harcanmasının önüne geçilmesine zemin hazırlamıştır. Farklı bloklardaki koloniler birbirleriyle iletişime geçmemektedir çünkü shared memory farklı blocklar tarafından erişilebilir değildir.

Paralel olarak rastgele bir şekilde başlangıç değerleri oluşturulur.
Paralel olarak arıların değerleri ile fitness’lar hesaplanır.
Paralel olarak Odd–Even Sorting algorithm(Tek Çift Sıralama Algoritması) ile sıralamanın yapıldığı belirtilmektedir. Tek Çift Sıralama Algoritması, Bubble Sort temelli paralel bir sıralama algoritmasıdır ve n/2 adımda sıralama işlemini gerçekleştirmektedir.

Bir bloktaki koloni sayısı = Bir bloktaki thread sayısı/ Her kolonideki arı sayısı şeklinde tanımlanmıştır.
BlockDim = 256 ve N = 8 ise her blokta 32 koloni bulunmaktadır.

Çalışmada 9 farklı kıyaslama fonksiyonu kullanılmıştır:

Sonuçlar incelendiğinde paralel yaklaşım kıyas fonksiyonlara bağlı olarak 13-56 kat arasında hızlı çalışmaktadır.