Tematyka grantu

Nowe metody kompleksowej analizy współbieżnych systemów obliczeniowych

 

Uniwersytet Mikołaja Kopernika w Toruniu,
Wydział Matematyki i Informatyki

 

Głównym celem projektu jest opracowanie nowych matematycznych metod opisu i badania systemów obliczeniowych z semantyką krokową (kładącą nacisk na jednocześne wykonanie wielu akcji) dopuszczających samo-współbieżność (rozumianą jako zezwolenie na jednoczesne wykonywanie akcji nierozróżnialnych przez model). Główna hipoteza badawcza zakłada, iż systemy realizujące asynchroniczny dostęp do pamięci mogą być precyzyjnie modelowane przy użyciu matematycznych formalizmów dopuszczających samo-współbieżność. W skład projektu wchodzi pięć powiązanych ze sobą podtematów:

 

  • Sieci Pertriego jako narzędzie do modelowania i 
    analizy systemów współbieżnych
    .
Sieci Petriego są matematycznym modelem systemów współbieżnych, bardzo popularnym dzięki precyzyjnej definicji, dużej różnorodności i łatwej wizualizacji za pomocą grafów dwudzielnych. Planowane są badania nad sieciami z semantyką krokową dopuszczającą samo-współbieżność w różnych klasach sieci Petriego. Z punktu widzenia zastosowań w modelowaniu systemów współbieżnych implementowanych jako podzespoły elektroniczne, bardzo istotną rolę odgrywają sieci bezpieczne i rozszerzenia sieci elementarnych. We wszystkich tych modelach miejsca w sieci są zamarkowane binarnie. Powoduje to oczywisty brak samo-współbieżności. Szczególną uwagę planujemy poświęcić sieciom k-bezpiecznym, w których możliwe jest wprowadzenie semantyki dopuszczającej samo-współbieżność. Przy jednoczesnej prostocie i rozstrzygalności podstawowych problemów, daje to bardzo obiecujący model w kontekście badań nad wielordzeniowymi jednostkami obliczeniowymi.

 

  • Ślady obliczeń jako narzędzie do modelowania i 
    analizy systemów współbieżnych
    .
Naturalne uzupełnienie dla opisu struktury systemu, który dają sieci, oferuje teoria języków formalnych. Poprzez utożsamienie ze sobą obliczeń konkretnego systemu, które różnią się tylko kolejnością wykonania akcji niezależnych, definiowane są tzw. ślady obliczeń. Pierwotny model zaproponowany w roku 1977 przez A. Mazurkiewicza doczekał się wielu rozszerzeń, wśród których wymienić należy ślady zagregowane. Pozwalają one zidentyfikować nie tylko współbieżność i kauzalność, ale również słabą kauzalność i serializowalność. Semantyka krokowa zastosowana w dotychczasowych podejściach wyklucza samo-współbieżność. Daje jednak duży potencjał i całe spektrum możliwości w opisie tego zjawiska, które planujemy wykorzystać przy realizacji projektu. Odpowiednie poluźnienie rygoru nakładanego na możliwe relacje między dwoma wystąpieniami tej samej akcji pozwala pokryć zachowania opisywane przez ślady uogólnione oraz ST-ślady. W nurt teorio-językowy wpisuje się też główny cel projektu – stworzenie struktury semantycznej dla systemów samo-współbieżnych.

 

  • Pojęcie trwałości w systemach współbieżnych.
Trwałość, jako własność definiująca pewną podklasę sieci Petriego, została zaproponowana przez Robertsona i Landwebera i w tym kontekście została szeroko zbadana. Okazuje się też ona bardzo pożądaną własnością modeli systemów współbieżnych. Podejmowae były też, bazujące na semantyce przeplotowej, próby wykorzystania trwałych zbiorów akcji w weryfikacji podatności systemu na zakleszczenia. Wstępne badania pozwoliły wyodrębnić dwa pojęcia wywodzące się z pierwotnej definicji sieci trwałych, odnoszące się do pojedynczych tranzycji, kroków współbieżnych i markingów sieci: trwałość i pokojowość. Stanowi to punkt wyjścia dla dalszych badań prowadzonych w ramach tego podtematu.

 

  • Algorytmy.
Zagadnienia algorytmiczne teorii języków formalnych czy teorii grafów są intensywnie rozwijane od wielu lat. Dużo mniejszy nacisk kładziony jest na rozstrzygalne zagadnienia związane z teorią śladów, w której wiele zagadnień jest naturalnym rozszerzeniem problemów klasycznych. W ramach tego zadania chcemy zaproponować współbieżne wersje algorytmów rozwiązujących klasyczne problemy (nie uwzględniające częściowej przemienności) oraz stworzyć bibliotekę Javy umożliwiającą wygodne i wydajne operowanie obiektami badanymi w ramach pozostałych zadań. W szczególności zajmiemy się reprezentacjami grafowymi procesów współbieżnych, metodami wydajnego przeglądania opisów teoriojęzykowych takich procesów czy zagadnieniami związanymi z występowaniem powtórzeń uwzględniających równoważność śladową.

 

  • Architektura wielordzeniowa.
Główną motywacją dla badań prowadzonych w pozostałych podzadaniach jest praktyczne zastosowanie uzyskanych wyników dla systemów wielordzeniowych. Doskonałym przykładem takich systemów są karty GPU. Ich głównym atutem jest szeroka dostępność oraz niezbyt wygórowana cena. Dodatkowym argumentem przemawiającym na ich korzyść (w porównaniu do klasycznych procesorów wielordzeniowych) jest różnica w stosunku ceny do mocy obliczeniowej wypadająca na korzyść kart GPU.

Wykonawcy grantu

Kierownik grantu:

  • dr Łukasz Mikulski

Główni wykonawcy grantu:

  • dr Kamila Barylska
  • dr Anna Gogolińska (oficjalnie dołączyła w roku 2017)
  • dr Marcin Piątkowski

Prace realizowane w ramach grantu

Artykuły naukowe:

  • K. Barylska, Persistency and Nonviolence Decision Problems in P/T-Nets with Step Semantics
  • K. Barylska, E. Best, E. Erofeev, Ł. Mikulski, M. PiątkowskiConditions for Petri Net Solvable Binary Words
  • K. Barylska, E. Erofeev, Ł. MikulskiM. PiątkowskiGenerating All Minimal Petri Net Unsolvable Binary Words
  • K. Barylska, M. Koutny, Ł. MikulskiM. PiątkowskiReversible Computation vs. Reversibility in Petri Nets
  • K. Barylska, Ł. MikulskiOn Decidability of Persistence Notions
  • J. Fernandes, M. Koutny, Ł. Mikulski, M. Pietkiewicz-Koutny, D. Sokolov, A. Yakovlev, Persistent and Nonviolent Steps and the Design of GALS Systems
  • A. Gogolińska, Ł. Mikulski, M. PiątkowskiGPU computations and memory access model based on Petri nets
  • R. Janicki, J. Kleijn, M. Koutny, Ł. MikulskiAlphabets of acyclic invariant structures
  • R. Janicki, J. Kleijn, M. Koutny, Ł. MikulskiCharacterising Concurrent Histories
  • R. Janicki, J. Kleijn, M. Koutny, Ł. MikulskiClassifying invariant structures of step traces
  • R. Janicki, J. Kleijn, M. Koutny, Ł. MikulskiInvariant structures and dependence relations
  • R. Janicki, J. Kleijn, M. Koutny, Ł. Mikulski, Step Traces
  • M. Koutny, Ł. Mikulski, M. Pietkiewicz-Koutny, An extension of the taxonomy of persistent and nonviolent steps
  • Ł. Mikulski, A. Niewiadomski, M. Piątkowski, S. Smyczyński, Generating CA-Plans from Multisets of Services
  • Ł. MikulskiM. Piątkowski, W. Rytter, Square-Free Words over Partially Commutative Alphabets

Referaty konferencyjne (recenzowane):

  • K. BarylskaOn Binary Words Being Petri Net Solvable
  • K. BarylskaOn Decidability of Persistent Notions
  • K. BarylskaPersistency and Nonviolence Decision Problems in P/T-Nets with Step Semantics
  • K. BarylskaReversible Computation vs. Reversibility in Petri Nets
  • A. GogolińskaGPU computations and memory access model based on Petri nets
  • Ł. MikulskiOn Generation of Context Abstract Plans
  • Ł. MikulskiOrder Structures for Subclasses of Generalised Traces
  • M. PiątkowskiGenerating All Minimal Petri Net Unsolvable Binary Words
  • M. PiątkowskiReduction of order structures
  • M. PiątkowskiSquare-Free Words over Partially Commutative Alphabets

Inne:

  • K. Barylska, O pewnych uogólnieniach pojęcia trwałości (w sieciach Petriego), referat na Seminarium Informatycznym (Uniwersytet Mikołaja Kopernika w Toruniu)
  • K. BarylskaOn Binary Words Being Petri Net Solvable, zaproszony referat na seminarium grupy SCARE (Carl von Ossietzky Universitat w Oldenburgu)
  • K. Barylska, On Decidability of Persistent Notions, Newcastle Workshop on Theory of Concurrency (Uniwersytet w Newcastle)
  • K. Barylska, Reversible Computations vs Reversibility, referat na Forum Informatyki Teoretycznej (Uniwersytet Warszawski)
  • K. Barylska, Syntetyzowalne słowa binarne, referat na Seminarium Informatycznym (Uniwersytet Mikołaja Kopernika w Toruniu)
  • A. Gogolińska, GPU computations and memory access model based on Petri nets, referat na Forum Informatyki Teoretycznej (Uniwersytet Warszawski)
  • A. Gogolińska, Model dostępu do pamięci GPU z użyciem sieci Petriego, referat na Seminarium Informatycznym (Uniwersytet Mikołaja Kopernika w Toruniu)
  • A. Gogolińska, Proste modele złożonych układów biologicznych oparte na sieciach Petriego, referat na Seminarium Informatycznym (Uniwersytet Mikołaja Kopernika w Toruniu)
  • Ł. MikulskiProjekt, implementacja i obsługa strony internetowej grantu nr 2013/09/D/ST6/03928
  • Ł. MikulskiGeneralizing Mazurkiewicz Traces, zaproszony referat na seminarium grupy SCARE (Carl von Ossietzky Universitat w Oldenburgu)
  • Ł. MikulskiGeneralizing Mazurkiewicz Traces, zaproszony referat na seminarium sieci naukowej LAMAS (PJATK w Gdańsku)
  • Ł. Mikulski, O odwracalności w sieciach Petriego, referat na Seminarium Informatycznym (Uniwersytet Mikołaja Kopernika w Toruniu)
  • Ł. MikulskiOn Concurrency Paradigms, zaproszony referat na seminarium grupy FOCUS (Uniwersytet w Bolonii)
  • Ł. Mikulski, Przypadek brzegowy dla nieskończonych słów bezkwadratowych, referat na Seminarium Informatycznym (Uniwersytet Mikołaja Kopernika w Toruniu)
  • Ł. Mikulski, Reversible Computations vs. Reversibility, Newcastle Workshop on Theory of Concurrency (Uniwersytet w Newcastle)
  • Ł. MikulskiSquare-free words over partially commutative alphabets, zaproszony referat na seminarium w LIACS (Uniwersytet w Lejdzie)
  • Ł. Mikulski, A. Niewiadomski, M. Piątkowski, S. Smyczyński, plakat On Generation of Context-Abstract Plans, prezentowany podczas PNSE'14 (Uniwersytet w Tunisie)
  • M. PiątkowskiRepetitions in words over partially commutative alphabets, zaproszony referat na seminarium wydziałowym (Uniwersytet w Helsinkach)

Wyjazdy (konferencje i wizyty studyjne) finansowane z grantu

Konferencje międzynarodowe: