Sterowanie w programach równoległych oparte na spójnych stanach aplikacji

Abstract

Praca uzasadnia tezę, że sterowanie oparte o analizę stanów globalnych aplikacji dla wybranych klas problemów umożliwia poprawną i wygodną strukturalizację sterowania w programach, przy uzyskaniu nie gorszej, a w wielu wypadkach lepszej, wydajności obliczeniowej, niż przy użyciu klasycznych metod sterowania, polegających na specyfikacji sterowania i obliczeń przemieszanych z komunikacją poprzez przesyłanie komunikatów.

Przegląd stosowanych metod sterowania i synchronizacji w programach równoległych i ich usystematyzowanie pozwoliły określić pożądane cechy tych metod. Uzyskane zestawienie doprowadziło do wniosku, że korzystne byłoby opracowanie mechanizmu sterowania wykonaniem programów równoległych, który działa w środowiskach rozproszonych, a zarazem daje programiście wygodę charakterystyczną dla metod bazujących na wspólnych zasobach, pozwala na określanie sposobu działania stosowanych w programie prymitywów sterujących oraz jest niezależny od mechanizmów przekazywania danych. Wymienione postulaty spełnia metoda sterowania, w której decyzje sterujące podejmowane są na podstawie analizy stanu globalnego aplikacji.

W pracy przedstawione są podstawy teoretyczne określania globalnych spójnych stanów oraz sposoby (modalności) wartościowania predykatów określonych na stanach globalnych. Szczególną uwagę zwrócono na stany spójne konstruowane w oparciu o znaczniki czasu rzeczywistego w systemach z częściowo zsynchronizowanymi zegarami lokalnymi, zwane silnie spójnymi stanami globalnymi (SCGS). Zdecydowano wykorzystać monitorowanie na bieżąco SCGS i wartościowanie predykatów globalnych w modalności Instantly w proponowanej metodzie sterowania wykonaniem programów.

Znany z literatury algorytm wykrywania SCGS został poprawiony. Opracowano nowe algorytmy wykrywania SCGS, pozwalające wykrywać więcej/szybciej SCGS. Algorytmy te wykorzystują: znajomość maksymalnego czasu transmisji komunikatu do monitora, znajomość minimalnego czasu trwania stanów lokalnych procesów, znajomość maksymalnego błędu synchronizacji zegarów lokalnych pomiędzy poszczególnymi parami procesów. Standardowe podejście, w którym pojedynczy centralny monitor zbiera informacje o stanach lokalnych procesów, konstruuje globalne stany spójne i wartościuje na nich predykaty, zostało rozszerzone do formy zhierarchizowanej. Umożliwiło to rozdzielenie obliczeń związanych z konstrukcją SCGS, oraz realizację hierarchicznego sterowania, charakteryzującego się lepszą efektywnością i skalowalnością.

Proponowana metoda sterowania zakłada, że spełnienie zdefiniowanych predykatów globalnych ma wpływać na zachowanie procesów. Rozważono możliwe sposoby reakcji procesów na na spełnienie predykatów. Wybrano asynchroniczną reakcję na przybycie sygnału oznaczającego spełnienie predykatu. Sygnał aktywuje skojarzony z nim kod. Na czas wykonania tego kodu główne obliczenia w procesie są wstrzymywane. Alternatywnie, sygnał sterujący może spowodować porzucenie bieżących obliczeń i przejście do dalszej części kodu programu. Wprowadzony mechanizm regionów w kodzie programu reguluje czy i kiedy proces powinien zareagować na przybycie sygnału sterującego.

Za pomocą opracowanego symulatora środowiska obliczeniowego eksperymentalnie sprawdzono charakterystyki opracowanych algorytmów wykrywania SCGS oraz realizowanego za ich pomocą sterowania. Charakterystyki te zostały określone przy użyciu wprowadzonych miar efektywności.

Praktyczna weryfikacja proponowanej metody sterowania zrealizowana została za pomocą systemu PS-GRADE. PS-GRADE to system graficznego projektowania programów równoległych, w którym do podstawowego mechanizmu przekazywania komunikatów dodano sterowanie za pomocą predykatów globalnych. Realizacja asynchronicznej reakcji na sygnały sterujące poprawiła wydajność systemu PS-GRADE względem wersji posługującej się samym przekazywaniem komunikatów, pozwalając unikać oczekiwania na przybycie komunikatu.

Wyniki testów efektywności proponowanej metody sterowania zrealizowane z użyciem wybranych aplikacji, przeprowadzone w systemie PS-GRADE oraz przy użyciu symulatora pokazały, że postawiona a wstępie teza jest prawdziwa.

The dissertation proves the thesis, that for a chosen set of problems, parallel program control based on an analysis of application global states forms a convenient framework for control design and implementation, while providing the same or better efficiency, than in the case of the use of classic control methods. By classic control methods in parallel programming we mean a sequence of computational and control statements interleaved with message passing instructions, executed by each application process.

The dissertation presents an overview of existing parallel program control methods. These methods are analyzed and systematized according to a number of their features. The analysis leads to an observation, that a desirable (from a programmer point of view) control mechanism for parallel programs should work in distributed environments, while being as easy to use as control mechanisms in centralized environments. Further, it should support a customization of control primitives, to let a programmer define necessary primitives and then concentrate on high-level application design. Finally, the sought-for mechanism should be independent from data transfer methods. Such a control mechanism has not been described and implemented yet. We claim (and subsequently we show), that a parallel program control method, in which control decisions are based on the analysis of application global states, has all the desired features mentioned above.

Having stated, that application global states are the key element for the newly proposed control method, we present foundations of the theory of consistent global states. In a distributed system it is not possible to capture the system state at once, because there in no common clock and processes can exchange information only using messages. Message transfer takes unspecified amount of time, so we cannot learn, what is/was the state of all the processes at a specified moment. While most of the researchers pay their attention to distributed systems equipped with logical clocks, allowing for ordering events according the their cause-effect relation and for a construction of the consistent global state lattice, we deal with systems equipped with partially synchronized real time local clocks. Such systems are popular nowadays. There are different methods for clock synchronization available, some of them based entirely on software (e.g. NTP), some on hardware (e.g. GPS clock), some on both. Stoller has presented a theory of consistent global states constructed with the use of partially synchronized real time clocks (SCGS). We adopt this theory because SCGS can be observed relatively easy on-line with a low computational overhead and they represent actual application states (as opposite to a lattice of possible application states obtainable with the use of logical clocks).

A global predicate is a function defined on a global state, giving a boolean result. By evaluating on-line properly defined global predicates on detected SCGS, we can monitor if the execution of a parallel application proceeds as desired. Informing the processes about predicate fulfillments and triggering a proper reaction of the processes upon receiving this information realize the application control.

We assume an existence of a dedicated process, called synchronizer, which gathers reports from processes about their local states. The programmer has to define what is the content of the state reports and when every process should send them. The synchronizer is responsible for SCGS detection, global predicate evaluation and control signal dispatching. A signal carries information about a fulfillment of a particular global predicate. The SCGS detection algorithm (run by synchronizers in our design), known from the literature, has been improved in this dissertation. Also new algorithms have been developed. The new algorithms use special features available in some systems to improve the number of detected SCGS and the speed of SCGS detection. The special features are as follows: o Message transfer time to the synchronizer is bounded and the bound is known. o Process local states last always longer than a given parameter. o Instead of a single global clock synchronization quality, clock synchronization errors between each pair of processes are used.

A single centralized synchronizer can easily become overloaded as it must process all the incoming state reports, detect SCGS and evaluate predicates on them. To alleviate this problem, we proposed a hierarchical version of SCGS detection algorithm. Using it, we developed a hierarchical control system, in which a number of hierarchically organized synchronizers work together to compute SCGS and control the execution of an application in a hierarchical way. In this way we improved strongly the efficiency and scalability of the proposed control method.

As we have mentioned above, in the proposed control method a process should properly react when a global predicate is fulfilled. We have considered a number of ways, in which a process can respond for a predicate fulfillment. Asynchronous reaction on control signal arrivals has been chosen. The control signals are sent by a synchronizer and they carry information about fulfillment of a global predicate. Arrival of a signal activates a prescribed fragment of the program code. The main computations performed by the process are suspended until the activated fragment completes. Alternatively, a control signal can cause the current computations to be abandoned. Then, the execution of the next part of the program starts immediately. We introduced a notion of code regions to be able to specify when a process should react on arrival of a control signal and which code fragment should be activated by a signal arrival. By introducing asynchronous reactions we avoided passive waiting for control decisions – a process does not need to stop and wait until a control decision based on global application state is taken and delivered, but it can perform computations continuously until interrupted.

By presenting the application control logic in the form of global predicates contained in synchronizers and thus decoupling the control from the main application code we obtained a convenient framework, which can be used for implementation of parallel program control.

We have developed a simulation environment in which we have tested the proposed control method. Using the simulations, we have analyzed the characteristics of the SCGS detection algorithms described above. Special control efficiency measures were defined to quantify the performance of the control system for different variants of SCGS algorithms. We have showed how chosen application parameters influence the control efficiency and which SCGS algorithms are better in what circumstances.

Apart from simulations, we verified the proposed program control method practically. For this purpose we developed a real programming environment, called PS-GRADE, supporting the proposed control method. The PS-GRADE system is a graphical programming environment. A programmer draws processes and their interconnections, and then he/she draws a control diagram for each process to specify its behavior. PS-GRADE uses message passing for application data transfers between processes. Additionally, global predicates defined within special synchronizer processes can be used for high-level application control. The asynchronous reaction on signal arrivals proved to be very useful in PS-GRADE. PS-GRADE does not facilitate non-blocking message reception and the asynchronous reactions can be used to emulate it. Thanks to it, the achieved performance increased significantly in tested applications, as compared to pure message passing implementations.

The combined test results have fully defended the thesis put in the first paragraph.