Wstęp do Pracy Magisterskiej

Napisałem już kilka pierwszych stron – tych teoretycznych – mojej pracy magisterskiej. Przedstawiam wam streszczenie, wstęp, cel i zakres mojej pracy.

Streszczenie:

„Praca prezentuje współczesne podejście do tworzenia oprogramowania na platformy wieloprocesorowe. Opisano podstawy przetwarzania równoległego oraz przedstawiono sprzętowe i programowe mechanizmy jego realizacji. W pracy skupiono się na konstrukcjach kodu sekwencyjnego, które mogą podlegać zrównolegleniu. Wyróżniono kilka konstrukcji, które następnie poddano szczegółowej analizie. Rezultatem pracy jest zbiór algorytmów, które na podstawie statycznej analizy sekwencyjnego kodu programu pozwalają stwierdzić, czy dane fragmenty kodu mogą zostać zrównoleglone. Algorytmy te również pokazują, w jaki sposób należy przekształcić istniejące konstrukcje tak, aby można je było wykonać równolegle. Jeden z zaproponowanych algorytmów został zaimplementowany w aplikacji demonstracyjnej, która analizuje programy sekwencyjne stworzone w języku C#.”

Wstęp:

„W branży informatycznej istnieje przekonanie, że na każdy wyprodukowany układ scalony można znaleźć oprogramowanie, które w pewien zamierzony sposób wykorzysta wszystkie dostępne zasoby. Ta nieformalna zależność powodowała rozwój zarówno sprzętu, jak i oprogramowania, który pozwolił m.in. na stworzenie graficznych interfejsów użytkownika i produkcję trójwymiarowych gier 3D. Trend ten utrzymuje się nadal, zmuszając producentów do tworzenia coraz to bardziej wydajnych układów.

Dotychczas przyspieszanie procesorów polegało m.in. na zwiększaniu częstotliwości zegara, powiększaniu pamięci podręcznej oraz optymalizacji wykonania kodu. Zwiększająca się zgodnie z prawem Moora (1) liczba tranzystorów w układzie scalonym pozwalała na wszystkie te modyfikacje. Jednak w roku 2003 producenci napotkali trudności w zwiększaniu częstotliwości swoich układów – przeszkodą były ograniczenia wykorzystywanych materiałów, m.in. krzemu. Dopóki nie zakończą się badania nad nowymi rodzajami tranzystorów, jakie prowadzi, np. Intel (2), prędkości procesorów dostępnych na rynku nie ulegną znaczącym zmianom. Inżynierowie postanowili zmienić kierunek rozwoju procesorów i zamiast poszukiwać metody na ciągłe przyspieszanie zegarów, zdecydowali się umieszczać kilka jednostek obliczeniowych w jednym układzie. W ten sposób powstały nowe architektury – wielordzeniowe, które zrewolucjonizowały rynek komputerów osobistych. Procesory jednordzeniowe zostały całkowicie wyparte z rynku, a ich miejsca zajęły 2-, 4- i 8-rdzeniowe jednostki obliczeniowe.

Mimo przemian w architekturze komputerów i wprowadzeniu wielu jednostek obliczeniowych, programiści nadal tworzą rozwiązania kierowane na maszyny jednordzeniowe. Takie programy nie są w stanie wykorzystać zasobów wielordzeniowych maszyn, przez co użytkownicy nie odczują różnicy w działaniu aplikacji niezależnie od tego, czy będzie ona uruchomiona na 1- czy 4-rdzeniowym procesorze. Aplikacje tego typu stanowią większość produkowanego w dzisiejszych czasach oprogramowania. Inżynierowie nie posiadają wystarczającej wiedzy w kwestii tworzenia rozwiązań równoległych, uważają tę dziedzinę za zbyt trudną i czasochłonną w realizacji. Trudnością może być również fakt, że człowiek – z założenia istota myśląca – posiada sekwencyjną świadomość postrzegania świata. Potrzeba jest zatem zestawu narzędzi, które pomogą programiście w opanowaniu równoległości, wskażą możliwe zagrożenia wynikające z przetwarzania równoległego i pomogą je zlikwidować. Na rynku istnieją narzędzia wspomagające tworzenie aplikacji na nowe platformy, jednak brakuje rozwiązań pomagających przystosowywać istniejące aplikacje do nowych środowisk.”

Cel i zakres pracy:

„Celem pracy jest stworzenie i implementacja algorytmów, które w podanym kodzie sekwencyjnego programu potrafiłyby znaleźć fragmenty możliwe do zrównoleglenia. Algorytmy te powinny także ocenić, czy zmiana danego fragmentu programu w sposób pozwalający wykonać go równolegle, przyniesie wzrost wydajności aplikacji (np. skróci czas jej wykonania). Do budowy algorytmów powinny zostać użyte różne metody analizy kodu źródłowego i testowania oprogramowania. Statyczna analiza kodu pozwoli zbadać przepływ sterowania i zależności danych fragmentów kodu, a testowanie pomoże w oszacowaniu zmian w wydajności.

Praca zapoznaje czytelnika z podstawami programowania równoległego oraz możliwościami jego wykorzystania w projektach zorientowanych na architektury wielordzeniowe. Zostanie zaprezentowana różnica między zwykłym – sekwencyjnym – modelem tworzenia oprogramowania a modelem równoległym. Opisane zostaną podstawowe prawa z dziedziny obliczeń równoległych (m.in. granice przyspieszania i warunki Bernsteina (3)). Przedstawione zostaną różne metody zrównoleglenia, poczynając od architektur komputerów po najnowsze biblioteki programistyczne.

Druga część pracy jest poświęcona analizie konstrukcji kodu sekwencyjnego, które mogą podlegać zrównolegleniu. Opisano dokładnie różne warianty występowania wybranych konstrukcji oraz zaproponowano możliwe podejście zrównoleglenia. Na tej podstawie stworzono algorytmy.

W ostatniej części pracy przedstawiona jest aplikacja demonstracyjna, w której zaimplementowano jeden z zaproponowanych algorytmów. Stworzone narzędzie potrafi analizować kod w języku C# (4) i wskazywać w nim te fragmenty, które można zrównoleglić.”

[Aktualizacja]

Praca zaliczona na 5 :)

Parallel Programming with Microsoft .NET E-BOOK

Darmowa pozycja dla wszystkich fanów rozwiązań równoległych. Microsoft Press wydał e-book na temat gorącego ostatnimi czasy, programowania równoległego. Książka na 224 (anglojęzycznych) stronach przedstawia idee zrównoleglania, oraz prezentuje przykłady oparte oczywiście o Parallel Extensions w .NET Framework 4.0

Przykładowe rozdziały to Parallel Loops, Parallel Tasks, Dynamic Task Paralelism, Debugging and Profiling Parallel Applications. Na CodePlex umieszczono również pełne kody używane w książce.

Pozycja pobowiązkowa!

Linki:

Promuj

Programowanie Równoległe a Google

W ostatnim poście krótko recenzowałem „The Google Story”, ale nie wspomniałem o bardzo ważnej rzeczy, która świetnie komponuje się z ostatnimi wpisami na moim blogu. Chodzi oczywiście o programowanie równoległe.

Twórcy Google jako pierwszych serwerów użyli ręcznie składanych PC połączonych w jedną sieć. Zdecydowali się na takie rozwiązanie, ponieważ koszty zakupów komercyjnych maszyn znacznie przekraczały założony budżet. To posunięcie było strzałem w 10! Magia jednak tkwiła nie tyle w komputerach, co w specjalnie napisanym oprogramowaniu – i tu przechodzimy do kwestii programowania równoległego.

Założeniem Larry’ego oraz Sergey’a było pobranie całego internetu do siebie i zindeksowanie go na miejscu. Jak wiemy, informacja w sieci waży znacznie więcej niż możliwości pamięciowe pojedynczego blaszaka, tak więc trzeba było całą tę informację rozłożyć na wiele maszyn. Zapytanie o dowolną frazę musiało zatem również trafiać do wielu komputerów w googlowskiej pajęczynie. Aplikacja, którą stworzyli jeszcze wtedy studenci, była kunsztem programowania równoległego. Należało rozłożyć zadanie wyszukiwania danej frazy na wiele podzadań i oddelegować je do innych wolnych zasobów. Należało znaleźć odpowiedź na następujące pytania:

  • Jak podzielić zadanie?
  • Które maszyny mogą wykonać dane podzadanie? (np. polskie zasoby są tylko na niektórych serwerach)
  • Które serwery są bardziej obciążone, a które mniej?

Wszystkie te pytania zadają sobie dziś twórcy aplikacji wielowątkowych/równoległych, myśląc nie o serwerach, ale np. o rdzeniach procesora. Bez programowania równoległego nie było by Google, bez Google nie byłoby… nic?

Nie trzeba było drogich rozwiązań, marnowanie pieniędzy na support i płacenie za markę (jaką niewątpliwe jest np. IBM). Programowanie równoległe odegrało znaczącą rolę w budowaniu giganta z Mountain View, a mogę dać głowę, że w erze informacji, w jakiej dzisiaj się znajdujemy, odegra równie wielką rolę w budowaniu rozwiązań, z których będziemy korzystać za kilka lat.

Promuj

Microsoft Biology Foundation

Microsoft Research opublikował pierwszą wersję Biology Foundation – zestawu narzędzi kierowanych do specjalistów od bioinformatyki, które stanowi rozszerzenie dla platformy .NET. Pierwsza wersja zawiera zbiór parserów, umożliwiających czytanie z popularnych formatów wykorzystywanych w bioinformatyce, a także zestaw algorytmów do manipulowania DNA, RNA oraz sekwencją białek. Ponadto rozszerzenie zawiera connectory do biolgicznych web serwisów takich jak NCBI BLAST.

Piszę o tym, ponieważ wiekszość zaimplementowanych algorytmów w tej bibliotece wykorzystuje potencjał Parallel Extensions. Algorytmy takie dają się łatwo zrównoleglić, ponieważ zawierają etapy, które można podzielić na mniejsze niezależne części, mogące zachodzić równolegle.

Zapraszam na stronę projektu.

Źródło: MSDN Blogs > External Research Team Blog

Promuj

Go Parallel, Be Master

Jeśli widzieliście moją prezentację o Programowaniu Równoległym, wiecie, że nie jest mi obcy temat równoległości, wielowątkowości i wieloprocesorowości, uff…. Teraz ta znajomość wchodzi na inny poziom. Moja praca magisterska, której obrona planowana jest na luty 2011 r., będzie ściśle powiązana z tym zagadnieniem. Tematem jest paralelizm aplikacji oraz jego weryfikacja. W skrócie: mam wymyślić, jak w możliwie automatyczny sposób zrównoleglić aplikację oraz w jaki sposób zweryfikować takie zrównoleglenie.

Pierwsza część polega na zbudowaniu narzędzia (prawdopodobnie pluginu do Visual Studio), który będzie podpowiadał programiście, które elementy kodu można zrównoleglić oraz jak to zrobić, używając znanych metod i rozwiązań. Druga część, ściśle powiązana z pierwszą, ma na celu zweryfikowanie, czy podział aplikacji na niezależne, równoległe ciągi instrukcji nie zmieni jego zachowania w każdym możliwym przypadku szeregowania; ma być to dowód formalny.

Jak widać, zagadnienie nie jest trywialne, więc na początek będę musiał się troszkę podszkolić, przekopać przez tony literatury i kodu źródłowego. W cyklu notek opatrzonych tagiem „magister” będę na bieżąco raportował moje postępy. Zatem zaczynajmy…

Jeśli chodzi o programowanie równoległe (używając tej nazwy, będą odnosił się jednocześnie do programowania wielowątkowego i wieloprocesorowego), to na samym początku należy opanować podstawy. Czym jest wątek, proces, deadlock, mutex, monitor? Nie będę tego opisywał, ale proponuję samodzielnie poczytać i pomyśleć. Dodatkowo polecam serię artykułów o wielowątkowości na blogu Piotra Zielińskiego. Zostały tam opisane wspomniane elementy oraz ich zastosowanie w środowisku .NET.

Celem pierwszego etapu mojej pracy jest zapoznanie się z możliwie jak największa liczbą zaawansowanych rozwiązań do kontroli/wprowadzania równoległości. Przez zaawansowane mam na myśli wszystko poza klasycznym mutexem, semaforem czy monitorem. Oczywiście w tych rozwiązaniach takie właśnie mechanizmy zostały użyte, ale głęboko, głęboko, pod maską. Programiście zostaje za to udostępniony zupełnie inny, bardziej przyjazny interfejs. Na początek Parallel Extensions…

Nie będę się powtarzał i odsyłam zainteresowanych do mojego artykułu na CodeGuru (część 1, bo 2 nigdy nie powstała – mój błąd). Opisuję tam podstawy tego rozwiązania, wyjaśniam, jak to naprawdę działa, i kiedy należy takie mechanizmy stosować. Dodatkowo zachęcam do subskrypcji blogu zespołu rozwijającego ten produkt – PFX Team. Przynajmniej raz na tydzień pojawia się nowa notka opisująca pewną funkcjonalność produktu. Wspomnieć należy również o Parallel Computing Developer Center w strukturach portalu MSDN. Zebrano tam dziesiątki artykułów, przykładów, screencastów i wywiadów z osobami odpowiedzialnymi za projekt. Polecam!

Na koniec warto wspomnieć o konkurencyjnym rozwiązaniu dla języków C/C++  – OpenMP.

Promuj

Prezentacja o Programowaniu Równoległym

We wrześniu 2008 roku w naszym dotnetowym kole działającym przy Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej ustalaliśmy szczegóły organizacji wydarzenia IT Academic Day na naszej uczelni. Rafał Maciąg, przewodniczący koła, zaproponował, aby ktoś z nas przygotował coś na tę okazję. Oprócz prezentacji takich firm jak ABC Data, Kasperksy, K2, miała mieć miejsce jeszcze jedna, studencka.  Nie zgłosił się żaden chętny, a i mi trudno było wyobrazić siebie w takiej roli. Jedynym argumentem był fakt, że interesowałem się wtedy jeszcze dość egzotycznym zagadnieniem, jakim jest Programowanie Równoległe. Temat pasował idealnie. Decyzja zapadła.

Do dyspozycji miałem bardzo wczesną wersję biblioteki Parallel Extensions (Lipiec 2008), tworzonej jeszcze w ramach Microsoft Research. Przygotowałem prezentacje, dema, pytania (były nagrody), no i oczywiście przemowę. Tydzień przed wydarzeniem Microsoft wypuścił CTP (Community Technology Preview) środowiska Visual Studio 2010. Upieczemy dwie pieczenie na jednym ogniu, pomyślałem. Pierwsza publiczna demonstracja Visual Studio 2010 w Polsce przypadła właśnie mnie (nie słyszałem, żeby ktoś pokazał to środowisko wcześniej, w końcu ja zrobiłem to kilka dni po premierze, wybaczcie mi skromność). Na wydziałowym, 4 rdzeniowym serwerze, zamontowaliśmy wspólnie z Rafałem obraz, wykorzystując technologię Hyper-V, i wypuściliśmy zdalny pulpit na świat. Wszystko dopięliśmy na ostatni guzik. W dniu konferencji tłumów nie było, co nie zmniejszyło jednak stresu. Moja prezentacja była przedostatnia, za to poprzednie wystarczająco wysoko podniosły poprzeczkę. 3.. 2… 1… Start!

Jeden slajd, drugi… ani się obejrzałem, a zaczęło brakować mi czasu, miałem tylko godzinę. Ostatecznie nie pokazałem wszystkich dem, za to wszystkie dostępne nagrody (książki i office’y) rozdałem w mig! Kurcze, naprawdę mnie słuchali i znali odpowiedzi na podchwytliwe pytania, a myślałem, że zostanie coś dla mnie… Żartuję! Dzisiaj, ponad 1,5 roku po tym wydarzeniu, żałuję, że nie zagłębiłem się w temat programowania równoległego jeszcze bardziej. W tym momencie wiem niewiele więcej, a temat poszerzył się n-krotnie. Moja praca inżynierska była, rzecz jasna, ważniejsza. Ale uwaga… moja praca magisterska będzie się bardzo wiązać z tym zagadnieniem, a dokładnie, z weryfikacją aplikacji równoległych.

Z wydarzenia, oprócz doświadczenia w prezentacjach, został mi jeszcze power point, artykuł na codeguru (pierwsza część) oraz źródła przedstawianych aplikacji. Jeśli ktoś nie miał przyjemności pracować z biblioteką ParallelFX, myślę, że będzie to dobra lektura. Dodatkowo w prezentacji zawarłem animacje przedstawiające prace menadżera zadań TPL (Task Parallel Library). Polecam!

Załączniki:

Pamięć Transakcyjna - STM [502.94 kB]
Parallel Extensions Presentation [3.21 MB]

Promuj