The main objective of this project is to parallelize maze creation, solution and visualization algorithms with CUDA toolkit. Implementation is performed only on Graphics Processing Unit (GPU). Speed gain from parallel implementation is measured on a GTX 460 graphics processor.
Tests and Results
All tests have been performed on a PC with Intel Core i5-2550 CPU @ 3.40 GHz and 8.00 GB RAM. The graphics processor is Nvidia GTX 460 with 336 CUDA cores and 675 MHz Base clock. The operating system is Windows 7. Tests have been done on both CPU and GPU to compare the computation times.
Tests and Results
All tests have been performed on a PC with Intel Core i5-2550 CPU @ 3.40 GHz and 8.00 GB RAM. The graphics processor is Nvidia GTX 460 with 336 CUDA cores and 675 MHz Base clock. The operating system is Windows 7. Tests have been done on both CPU and GPU to compare the computation times.
Maze creation phase.
Maze solution phase.
Maze final view. (Solution of the maze had shown with white trace)
All computations are slowed on purpose in order to show the process more clearer.
Article about this project:
Ekran Kartı ile Labirent Oluşturulup Çözüm Bulunması
Sefa BAŞER
TOBB ETÜ Ankara, TÜRKİYE
st081101036@etu.edu.tr
Kağan KABAYEL
TOBB ETÜ Ankara, TÜRKİYE
st081101020@etu.edu.tr
ÖZET
Bu makalede, labirentlerin belirli algoritmalar ile gpu üzerinde paralel bir şekilde oluşturulması ve yine GPU üzerinde oluşturulan labirentlerin paralel bir şekilde çözümü bulması üzerine yapılmış bir araştırma sunulmuştur.
Labirentlerin oluşturulması ve oluşturulan bu labirentlerin çözümü için bir çok teknik ve algoritma bulunmaktadır. Bu algoritmalar genel olarak seri çalışmak üzere tasarlanmıştır. Ancak labirentlerin yapısı gereği problem paralel olarak tamamlanmaya oldukça uygundur. Biz labirentin oluşuturulması için recursive backtracking’in paralelleştirilmiş hali ve çözülmesi için de blind alley sealer’ın parallelleştirilmiş halini tercih ettik.
Hesaplamaların paralel olarak GPU üzerinde cuda ile gerçekleştirdik ve algoritmaları paralelleştirirken özellikle ekran kartına uygun olmalarına özen gösterdik.
Bu çalışmanın bizim için paralel programlamaya bir giriş niteliği taşımasını ve ilerki çalışmalara, örneğin bilgisayar oyunlarındaki yön bulma hesaplamalarının ekran kartı üzerinde gerçekleştirilmesi, sürü hareketlerinin hesaplanması ve fizik simülasyonları gibi, ön ayak olmasını hedeflemekteyiz
1.
Labirentlerin oluşturulması ve oluşturulan bu labirentlerin çözümü için bir çok teknik ve algoritma bulunmaktadır. Bu algoritmalar genel olarak seri çalışmak üzere tasarlanmıştır. Ancak labirentlerin yapısı gereği problem paralel olarak tamamlanmaya oldukça uygundur. Biz labirentin oluşuturulması için recursive backtracking’in paralelleştirilmiş hali ve çözülmesi için de blind alley sealer’ın parallelleştirilmiş halini tercih ettik.
Hesaplamaların paralel olarak GPU üzerinde cuda ile gerçekleştirdik ve algoritmaları paralelleştirirken özellikle ekran kartına uygun olmalarına özen gösterdik.
Bu çalışmanın bizim için paralel programlamaya bir giriş niteliği taşımasını ve ilerki çalışmalara, örneğin bilgisayar oyunlarındaki yön bulma hesaplamalarının ekran kartı üzerinde gerçekleştirilmesi, sürü hareketlerinin hesaplanması ve fizik simülasyonları gibi, ön ayak olmasını hedeflemekteyiz
1.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
GİRİŞ
Labirentlerin oluşturulması için çeşitli performans değerlerine sahip algoritmalar mevcut. Her algoritmanın oluşturduğu labirentin görünümü net bir şekilde birbirinden ayırt edilebilir biçimde değişiklik göstermektedir.
Algoritmalardan bazıları ve labirenti oluşturma anındaki görüntülerine örnek verirsek:
Recursive Backtracking
Eller’s Algorithm
Kruscal’s Algorithm
Prim’s Algorithm
Recursive Division
Aldous-Broder Algorithm
Tüm bu algoritmaların çalışması tek koldan yürütülmektedir, ancak algoritmaların paralelleştirilmesi ile daha iyi bir performans sağlanabilir ve labirentin oluşturulması ve çözülmesi çok daha kısa zamanda gerçekleştirilebilir.
Oluşturulan labirentlerin çözümüyle alakalı olarak da bir çok algoritma geliştirilmiştir. Bunlardan bazıları aşağıdaki şekilde incelenmiştir:
Solutions: Labirentin olası kaç çözümünün olduğu.
Guarantee: (Çözümün hiç olmaması ihtimali de bazı algoritmalarda bulunmaktadır.) Çözümün oluşmasının garanti olup olmaması.
Memory Free: Çözüm için extra bir hafızanın gerekli olup olmadığı.
Fast: Algoritmanın yeterince hızlı olup olmadığı.
SİSTEMİN YAPISI ve İŞLEYİŞİ
Projenin gerçekleştirilmesini GPU üzerinde sağladık. Hem ekran kartlarının günümüzde çok yaygın olmasından hem de artık günümüzde çeşitli platformlar yardımı ile GPU’ların sadece grafik değil başka paralel hesaplamalarda da kullanılabilir hale gelmesinden dolayı projeyi GPU üzerinde gerçekleştirmeyi tercih ettik. Örneğin birçok paralel işlemci barındıran büyük sistemlerin aksine GPU da paralel işlemleri gerçekleştirmek için CUDA platformunu sağlayan tek bir bilgisayar ve grafik kartı yeterlidir.
Projede yapılan işlemleri üç farklı kategoriye ayırabiliriz.
Labirentin oluşturulması.
Labirentin çözülmesi.
Kullanıcıya hem labirentin oluşması hemde çözülmesini gösterebilmek için belli aralıklarla mevcut labirent görüntüsünün ekrana çizdirilmesi.
1.1LABİRENTİN OLUŞTURULMASI
Biz projemizde labirentin oluşturulması için Recursive Backtracking algoritmasının paralelleştirilmiş halini kullandık. Bu algoritma ile oluşturulan labirentler verilen örnek görüntülerde de görülebildiği gibi alışık olduğumuz labirent görüntüsünde oluyor. Ayrıca algoritmanın paralelleşmeye uygun olması bizi bu algoritmayı tercih etmeye yöneltti. Algoritma neticesinde oluşan labirent perfect maze özelliği taşımaktadır. Yani kendi içerisinde döngü barındırmamaktadır.
Parallel Recursive Backtracking
Belirlenen limit kere rasgele bir yoldan git. Giderken gittiğin yerlerde labirent yolu aç ve bu yolları gri (henüz yapımı bitirilmemiş) olarak işaretle.
Eğer gittiğin yol tıkalı ise başka bir yol bulana kadar geldiğin yoldan geri dön. Dönerken üzerinden geçtiğin yerleri beyaz (yapımı bitmiş) olarak işaretle.
Eğer geri dönerken hiçbir başka yol bulamadıysan ve son geldiğin noktada gidilebilecek her yer beyaz işaretlenmiş ise işlemi sonlandır.
Belirlenen limit dolunca (örneğin 10 adım) bölün. Aynı adımları izleyecek başka bir paralel process oluştur ve başa dön.
Bu algoritmadaki bahsi geçen limit eğer olmasaydı labirentin yollarını yapan bütün threadler her adımda bölünmeye kalkışıp birbirini engelliyeceklerdi. Bu da oluşan labirentin istenildiği gibi görünmemesine sebep oluyor. Eğer limit çok yüksek seçilirse bu sefer de algoritmadaki paralellik özelliği azalıyor. Bu sebeple labirenti oluşturan iş parçacıklara “on adım ilerle ve sonra bölün” sınırlaması konulmuştur.
Algoritmanın uygulamaya dökülmesinde ortaya çıkan bir başka sorun ise birden çok iş parçacığının aynı konuma yazmaya kalkışması sorunudur. Örneğin (3,2) konumundaki bir parçacık yukarı, (4,3) konumundaki bir başka parçacık sola doğru ilerlemeye kalkarsa ikisi de (3,3) konumuna yazmak isteyeceklerdir. Böyle bir durumun istenmeyen sonuçlara yol açmasını engellemek için şöyle bir yol tercih ettik;
yukarı gitmek isteyenler işlemlerini bitirsin
sağa gitmek isteyenler sağ taraflarındaki konumu kontrol etsin, eğer işlem yapılmamışsa işlemlerini bitirsin
aşşağı gitmek isteyenler aşşağı taraflarındaki konumu kontrol etsin, eğer işlem yapılmamışsa işlemlerini bitirsin
sola gitmek isteyenler sol taraflarındaki konumu kontrol etsin, eğer işlem yapılmamışsa işlemlerini bitirsin
Bu sayede hiçbir iş parçacığı hem birbirinin yolunu kesmeyecek hem de aynı konuma yazma çatışması da engellenmiş olacaktır.
procedure Parallel_Recursive_Backtracking()
begin
iterate_limit := 10;
create Maze[n][n];
create Process_Positions[p];
Process_Positions[0] := (1,1);
repeat
for each process i do
for j := 0 to iterate_limit do
if Process_Positions[i] = 0 then exit;
current_position := Process_Positions[i];
if Maze[current_position] = grey then
begin
next_position := select_random_direction(current_position);
if next_position = null then Maze[current_position] := white;
else
make_path(Maze, current_position, next_position);
Maze[next_position] := grey;
Process_Positions[i] := next_position;
end else
end
else
previous_position := get_previous_position(current_position);
if Maze[previous_position] = null then
Process_Positions[i] := 0;
return;
end if
else
Maze[previous_position] := white;
Process_Positions[i] := previous_position;
end else
end else
end for
synchronize();
if Process_Positions[i] != 0 then
child_process := find_dead_process();
Process_Positions[child_process] := Process_Positions[i];
end if
end for
if all Process_Positions = 0 then return;
end repeat
end
end Parallel_Recursive_Backtracking
Labirenti oluşturan iş parçacıklarının, bölünmek istedikleri zaman kendilerine boşta bekleyen bir iş parçacığı seçmesi gerekmektedir. Algoritmada bahsi geçen find_dead_process() metodu, her iş parçacığının sadece kendisine tahsis edilmiş boşta bekleyen bir başka iş parçacığı seçmesini sağlar. Hiçbir iki iş parçacığı aynı iş parçacığını çocuğu olarak seçemez.
Bu işlemi eğer basit bir şekilde gerçekleştirmek istersek; “sırayla bütün iş parçacıklar diğerlerine bakıp kendisine ait boşta bulunan bir iş parçacığını seçsin. “ diyebilirdik. Ancak p adet iş parçacığının her birisi diğerlerini beklemek durumunda kalırdı ve bu işlem O(p2) de sonuçlanırdı. Ancak bu ilemi O(p) de tamamlamak mümkündür.
procedure find_dead_process()
begin
for each process i do
if Process_Positions[i] = 0 return null;
for k := 1 to p do
if Process_Positions[(i + k) % p] = 0 then
Process_Positions[(i + k) % p] := Process_Positions[i];
return (i + k) % p;
end if
end
end for
end
end find_dead_process
626x336 büyüklüğündeki bir labirentin iş parçacığı sayısına bağlı oluşturulma süreleri
626x336 büyüklüğündeki bir labirentin iş parçacığı sayısına bağlı oluşturulma süreleri
Grafiklerde görüldüğü gibi kullanılan thread sayısı arttıkça tamamlanma süresi kısalmaktadır. Ancak bu kısalma doğrusal olarak ilerlememektedir. Thread sayısına göre hızlanma katsayısal olarak aşşağıdaki grafikteki gibidir.
Aynı anda çalışan iş parçacık sayısı belli bir doygunluğa eriştikten sonra birbirlerinin önünü tıkamakta ve bu da aynı anda çalışacak parçacık sayısına bir üst limit koymaktadır. Kullanılan iş parçacığı sayısı belli bir seviyeden sonra arttırılsa bile bu sebepten dolayı artık performansta iyileşmeye yol açmayacaktır. Daha büyük labirentler oluşturulursa bu limitte boyutlardaki artışa göre artış gösterecektir.
626x336 büyüklüğündeki bir labirentin oluşturulma anındaki zamana bağlı iş parçacığı sayısı
Yukarıdaki grafikte labirent oluşturulurken zamana bağlı iş parçacığı sayıları verilmektedir. Bu grafikte de rahatlıkla seçebileceğimiz labirentin oluşturulmasında iş parçacığı sayısı açısından üç ayrı aşama bulunmaktadır. İlk aşama iş parçacıklarının çoğalma aşamasıdır. Bu aşamada labirentte gerekli boş alan sayısı yeterince bulunduğundan iş parçacıkları sürekli bölünüp çoğalırlar. İkinci aşamada ise artık iş parçacıkları birbirinin önünü tıkamaya başladıkları için, yeni oluşan iş parçacığı ile ölenlerin sayısı birbirine denktir. Labirentte en çok alanın oluşturulduğu aşama budur. Son aşamada ise artık labirentte sadece kuytuda kalmış bazı bölgeler labirente dahil edilir ve yeni iş parçacığı nadiren üretilir.
İkinci aşamanın uzunluğunu işlem için ayrılan iş parçacığı sayısı belirler. Eğer az sayıda iş parçacığı ayrıldı ise daha sığ bir seviyede işlem ikinci aşamaya geçer ve daha uzun süre bu aşamada kalır. İş parçacığı sayısı arttıkça çalışma süresindeki kısalmanın sebebi ise işte bu ikinci aşamadaki tasarruftan kaynaklanmaktadır. Eğer iş parçacığı sayısı üst limitine kadar verilirse giderek artan ve sonrasında giderek azalan bir grafik elde ederiz, ikinci aşama gözlenemez hale gelir ve performansın üst sınırına erişiriz.
1.2LABİRENTİN ÇÖZÜLMESİ
Labirentin çözülmesinde sürekli çıkmaz sokakları yok etmek üzerine kurulmuş olan bir algoritma kullandık.
Parallel Blind Alley Sealer
Labirentin her noktasına aşşağıdaki işlemleri sürekli tekrarlayacak processler ata.
Eğer bulunduğun konumdan gidebileceğin tek bir beyaz (aktif) yer varsa: bulunduğun yeri gri (kapatılmış) olarak işaretle ve o konuma git.
Eğer gidebileceğin beyaz yolların sayısı bire eşit değilse işlemi sonlandır.
Bütün processler sonlandığında geriye sadece labirentin çıkış rotası kalmış olacaktır. Bu algoritmayı eğer projeyi başka bir platformda gerçekleştirecek olsaydık tercih etmezdik. Çünkü n2 tane processor’a ihtiyacımız olurdu, ancak GPU’lar, çok fazla thread içeren işlemleri çok hızlı biçimde tamamlayabilmek için tasarlandığından özellikle GPU için bu algoritmayı tercih ettik. Başka paralel platformlarda daha farklı algoritmaların seçilmesi uygun olacaktır.
Labirent oluşurken
Labirentin çözülmüş hali
Zamana bağlı işlem gören alan sayısı
Grafikte de görüldüğü gibi bu algoritma çok fazla çıkmaz sokak bulabildiği için en verimli olduğu zamanı labirentin daha incelenmeye yeni başlandığı ilk anlarda yapmaktadır. Daha sonrasında çıkmaz sokak sayısı azaldıkça paralel çalışan iş parçacığı sayısıda giderek azalmaktadır.
Çok daha yüksek performansa ihtiyaç olduğu durumlarda bu algoritma ilk önce çalıştırılabilir, belli bir seviyeye gelindikten sonra çıkmaz sokak sayısı önemli ölçüde azalmış olduğu için bu özel durumda daha hızlı çalışabilecek başka bir algoritmaya geçmek tercih edilebilir.
Tabi bu mevcut durumda bile 626x336 büyüklüğündeki bir labirentin çözülmesi 11~13 mikro saniye sürmektedir. Aynı büyüklükte labirentin oluşturulması ise 512 iş parçacığı ile 180~200 mikro saniye sürmekte, seri olarak oluşturulması ise 7000 mikro saniye civarını bulmaktadır. Çözüm aşamasındaki yüksek verim algoritmanın özellikle GPU için seçilmiş olmasından kaynaklanmaktadır.
procedure Parallel_Blind_Alley_Sealer(Maze[n][n])
begin
create n*n process;
for each process i do
current_position = i;
repeat
position := get_proper_position(Maze[n][n], current_position);
if position = null then return;
Maze[current_position] := grey;
current_position := position;
end repeat
end for
end
end Parallel_Blind_Alley_Sealer
procedure get_proper_position(Maze[n][n], position)
begin
proper_position := -1;
proper_position_count := 0;
control_position := (position + 1) % n * n; //right
if Maze[control_position] = white
and is_there_path(Maze, position, control_position) then
proper_position_count := proper_position_count + 1;
proper_position := control_position;
end if
control_position := (position - 1) % n * n; //left
if Maze[control_position] = white
and is_there_path(Maze, position, control_position) then
proper_position_count := proper_position_count + 1;
proper_position := control_position;
end if
control_position := (position + n) % n * n; //up
if Maze[control_position] = white
and is_there_path(Maze, position, control_position) then
proper_position_count := proper_position_count + 1;
proper_position := control_position;
end if
control_position := (position - n) % n * n; //down
if Maze[control_position] = white
and is_there_path(Maze, position, control_position) then
proper_position_count := proper_position_count + 1;
proper_position := control_position;
end if
if proper_position_count = 1 then return proper_position;
else return null;
end
end get_proper_position
Unutulmamalıdır ki bu algoritma perfect maze özelliği taşıyan labirentlerin çözümünü gösterir. Eğer labirent içerisinde döngü barındırıyorsa algoritmanın neticesinde bütün olası çözüm yolları kalır. Eğer bu çözüm yolları arasından ayrıca en kısa yolun bulunması isteniyorsa ayrıca başka bir algoritma geliştirilmelidir.
n x n lik bir labirentin blind alley sealer ile çözülmesi O(n2) de tamamlanır. Parallelleştirilmiş versiyonunda ise O(n) de tamamlamak mümkündür. Ancak n2 adet processin aynı anda çalışması gerekir ve bu da her ortamda uygulanabilir olmasını önemli ölçüde kısıtlamaktadır.
Eğer labirent herşeyin kötü gideceği şekilde oluşturulmuş ise en kötü durumda çalışma karmaşıklığı O(n2) ye çıkar. Örneğin, labirentin girişinde yol ikiye ayrılıyor ve bu yollardan birisi hiçbir yere sapmayıp doğrudan çözüme gidiyor diğeri ise hiç dallanmayıp bütün alanı geziyorsa. Bu durumda istediğiniz kadar process oluşturabiliyor olun her adımda sadece tek bir yolu eleyebilirsiniz. Toplam n2 – 2n adet adım sonrasında geriye çözüm yolu kalır.
1.3LABİRENTİN GÖRÜNTÜLENMESİ
Labirentin her noktasının çizimi diğerlerinden bağımsız olduğu için labirentin görüntülenmesi rahatlıkla paralelleştirilebilir bir işlemdir. O(n2/p) karmaşıklıkta işlem tamamlanabilir.
Show Maze
Labirentin her bir noktası için bir process oluştur.
Her process kendisi ile alakalı konumun rgb değerlerini hesaplayıp bitmap dosyasına işlesin.
Bitmap’i ekranda göster.
Örnek labirent
2.KULLANILAN PLATFORM ve ARAÇLAR
2.1PLATFORMLAR
2.1.1CUDA
2.1.1CUDA
GPU için NVIDIA'nın sunduğu PathScale tabanlı bir C derleyicisi ve C ile yazılmış algoritmaların GPU üzerinde çalışmasını sağlayan bir mimari ve teknolojidir.
2.1.2C
Projenin gerçekleştirilmesi için CUDA platformunda kullanılabilen C programlama dili.
2.2ARAÇLAR
2.2.1MICROSOFT VISUAL STUDIO 2010
2.2.1MICROSOFT VISUAL STUDIO 2010
C uygulaması geliştirmek için kullandığımız bütünleşik geliştirme ortamı (IDE), Microsoft Visual Studio 2010’dur.
3.SONUÇ
Yapmış olduğumuz çalışmaların neticesinde labirentin oluşturulması ve oluşturulduktan sonra çözülmesi sürecinde kullanmış olduğumuz algoritmaların paralelleştirilerek gerçekleştirilmesiyle performans büyük ölçüde arttırıldı. İş parçacıklarının artması aynı anda yapılan iş sayısını arttırdığından labirentin oluşturulması ve çözülmesi çok daha kısa bir zamanda tamamlandı.
Bu projemizi gerçekleştirirken gpu grafik kartını kullanmış olmamız da daha kolay ekipman edinmemizi ve de daha az bir bütçe kullanmamızı sağladı.
Elbette GPU üzerinde gerçekleştirilen tüm hesaplamalar CPU üzerinde de gayet rahat bir şekilde hesaplanabilir ancak buradaki kilit nokta gerçek zamanlı hesaplamanın yapılabilmesidir. Eğer yeterince beklersek, problemlerin çözümlerini veya simülasyon sonuçlarını CPU ile de alabiliriz, ama özellikle gerçek zamanlı elde etmemizi gerektiren bir ortam için ihtiyaç duyuyorsak (örneğin kullanıcı etkileşimli yazılımlar) hesaplamaların paralel olarak gerçekleştirilmesi bu yazılımların gerçekleştirilebilmelerine olanak sağlar. Bu sebeple Cuda ile programlama çoğunlukla fizik simülasyonları için kullanılmaktadır. Örneğin sıvıların davranışlarını hesaplamada, çarpışma simülasyonlarında, yangın simülasyonları gibi çok yüksek sayılarda partiküllerin kullanıldığı ortamlarda tercih edilmektedir.
4.GELECEK ÇALIŞMALAR
Bu çalışmanın sadece labirentlerle sınırlı kalmayacak nitelikte olduğunu düşünüyoruz. Örneğin çoğu bilgisayar oyununda birçok birimin bir noktadan diğerine gitmesi gerekmektedir, özellikle strateji oyunlarında. Bu birimlerin herbiri için en kısa yol seri olarak CPU üzerinde hesaplanmaktadır. Uygulamalardan çok azı birden fazla thread oluşturup CPU üzerinde paralel olarak hesaplamaya gitmektedir ancak bu paralellik CPU nun çekirdek sayısının kısıtlı olmasından dolayı yüksek verimde olmamaktadır. Bu tip hesaplamalar ekran kartı üzerinde çok kısa sürede yüksek paralellikle hesaplanabilir.
Bir çok akademik araştırma alanı paralel hesaplama için elverişlidir. Örneğin yapay sinir ağları, sürü davranışları ve gerçek zamanlı görüntü işleme gibi...
