Wyniki wyszukiwania - BazTech

1

Adding parallelism to sequential programs : a combined method

Daszczuk Wiktor B., Czejdo Danny B., Grześkowiak Wojciech

International Journal of Electronics and Telecommunications

|

2024

|

Vol. 70, No. 1

135--144

EN

The article outlines a contemporary method for creating software for multi-processor computers. It describes the identification of parallelizable sequential code structures. Three structures were found and then carefully examined. The algorithms used to determine whether or not certain parts of code may be parallelized result from static analysis. The techniques demonstrate how, if possible, existing sequential structures might be transformed into parallel-running programs. A dynamic evaluation is also a part of our process, and it can be used to assess the efficiency of the parallel programs that are developed. As a tool for sequential programs, the algorithms have been implemented in C#. All proposed methods were discussed using a common benchmark.

2

Designing multithreaded software based on concurrency in the problem domain

Sanden Bo I.

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

|

2021

|

Vol. 25, No 2

183--201

EN

Event-sequence modeling is a thread-architectural style for event-driven software. It bases the set of threads in a multithreaded program on an event-sequence model of the problem domain. Each event sequence is a time-ordered set of event occurrences in the domain. (It is often defined by a state machine.) An event-sequence model is a set of event sequences that together cover all relevant event occurrences in the domain. Occurrences in one event sequence are generally concurrent with those in other sequences. The event-sequence modeling approach leads to architectures consisting of threads, each based on an event sequence, and shared objects. The threads can run concurrently on different cores/processors except when they must have exclusive access to some shared object. This paper defines these concepts and illustrates them with examples.

3

Causal-Consistent Replay Reversible Semantics for Message Passing Concurrent Programs

Lanese Ivan, Palacios Adrián, Vidal Germán

Fundamenta Informaticae

|

2021

|

Vol. 178, nr 3

229--266

EN

Causal-consistent reversible debugging is an innovative technique for debugging concurrent systems. It allows one to go back in the execution focusing on the actions that most likely caused a visible misbehavior. When such an action is selected, the debugger undoes it, including all and only its consequences. This operation is called a causal-consistent rollback. In this way, the user can avoid being distracted by the actions of other, unrelated processes. In this work, we introduce its dual notion: causal-consistent replay. We allow the user to record an execution of a running program and, in contrast to traditional replay debuggers, to reproduce a visible misbehavior inside the debugger including all and only its causes. Furthermore, we present a unified framework that combines both causal-consistent replay and causal-consistent rollback. Although most of the ideas that we present are rather general, we focus on a popular functional and concurrent programming language based on message passing: Erlang.

4

Causal Reasoning for Safety in Hennessy Milner Logic

Caltais Georgiana, Mousavi Mohammad Reza, Singh Hargurbir

Fundamenta Informaticae

|

2020

|

Vol. 173, nr 2-3

217--251

EN

Determining and computing root causes in system failures is a significant issue in science and engineering. In this paper, we introduce a notion of causality for explaining counter-examples in system analysis based on formal models. The counter-examples are produced by checking for hazardous situations expressed in the Hennessy-Milner Logic, in the context of Labelled Transition System models. We also introduce CauseJMu, a tool for automatically identifying such causal computations within a system model. CauseJMu relies on encoding causality in terms of an extension of Hennessy-Milner Logic to recursive formulae with data. The encodings enable deciding whether a certain computation is causal or not, using the mCRL2 model checker.

5

Using erlang in research and education in a technical university

Petrov I., Alexeyenko A., Ivanova G.

Computer Science

|

2018

|

Vol. 19 (3)

333--343

EN

This paper addresses the problem of using functional programming (FP) languages for research and educational purposes. In order to identify the problems associated with the use of FP languages such as Erlang, an experiment consisting of two surveys was performed. The first survey was anonymous and aimed at establishing whether the participants prefer object-oriented or functional coding. The second one was a survey made after the students finished an Erlang course. The results of these two surveys demonstrate that functional programming is underrated with no apparent reasons. Possible steps to address this problem are suggested.

6

Strategie niskopoziomowego programowania współbieżnego platformy .NET

Wichary P., Jóźwiak I., Szczepanik M.

Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska

|

2017

|

z. 113

517--527

PL

W artykule przedstawiono mechanizmy związane z programowaniem współbieżnym na niskim poziomie abstrakcji. Na podstawie literatury światowej wyróżniono zbiór pojęć podstawowych dotyczących współbieżności. Wskazano mechanizmy pomagające w rozwiązaniu problemu wzajemnego wykluczania przy użyciu konstrukcji językowych platformy .NET. Opisano sposoby uzyskania synchronizacji wątków wraz z opisem ich wad i zalet.

EN

The article presents issues related to low level concurrent programming. Based on world literature, a collection of basic notions of concurrency has been distinguished. Indicators that help to solve the mutual exclusion problem using the .NET language constructs. Describes ways to get thread synchronization once with a description of their drawbacks and advantages.

7

Type-driven development of concurrent communicating systems

Brady E.

Computer Science

|

2017

|

Vol. 18 (3)

219--240

EN

Modern software systems rely on communication, for example mobile applcations communicating with a central server, distributed systems coordinaing a telecommunications network, or concurrent systems handling events and processes in a desktop application. However, reasoning about concurrent prgrams is hard, since we must reason about each process and the order in which communication might happen between processes. In this paper, I describe a type-driven approach to implementing communicating concurrent programs, using the dependently typed programming language Idris. I show how the type system can be used to describe resource access protocols (such as controlling access to a file handle) and verify that programs correctly follow those prtools. Finally, I show how to use the type system to reason about the order of communication between concurrent processes, ensuring that each end of a communication channel follows a defined protocol.

8

Factored Cost-Optimal Planning Using Message Passing Algorithms

Jezequel L., Fabre E.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 4

369--401

EN

This paper proposes an approach to solve cost-optimal factored planning problems. Planning consists in organizing actions in order to reach some predefined goal. In factored planning one considers several interacting planning problems and has to design an action plan for each of them. But one must also guarantee that all these local plans are compatible: actions shared among several problems must be jointly performed or jointly rejected. We enrich the problem with the extra requirement that the global plan computed in this modular manner must also minimize the sum of all action costs. A solution is provided to this problem, based on classical message passing algorithms, known as belief propagation in the setting of Bayesian networks. Here, messages carry complex information under the form of weighted (or (min; +)) automata, and all computations are performed with these objects. At the time our first paper on this topic was published, this method was the only one to solve cost-optimal factored planning problems in a modular way. Since then, new approaches were proposed. Experiments on classical benchmarks show that it is a valuable alternative to existing methods.

9

Visualisation of concurrent processes

Mikulski Ł, Piątkowski M.

Control and Cybernetics

|

2013

|

Vol. 42, no. 3

699-725

EN

Mazurkiewicz traces are a widely used model for describing the languages of concurrent systems computations. The causal structure of atomic actions occurring in a process modeled as a trace generates a partial order. Hasse diagrams of such order are very common structures used for presentation and investigation in the concurrency theory, especially from the behavioural perspective. We present effective algorithms for Hasse diagrams construction and transformation. Later on, we use them for enumeration of all linearisations of the partial order that represents a concurrent process. Additionally, we attach the flexible visual implementation of all considered Algorithms.

10

Zachowanie spójności danych w wybranych systemach NoSQL

Augustyn D., Bajerski P., Brzeski R..

Studia Informatica

|

2012

|

Vol. 33, nr 2A

27-48

PL

Zachowanie spójności przetwarzanych danych jest problemem ogólnym, w szczególności dotyczącym systemów NoSQL, w których efektywność przetwarzania jest czynnikiem najistotniejszym. Wysoką efektywność przetwarzania w bazach NoSQL osiąga się przez uproszczenie mechanizmów wewnętrznych, w tym, częściowo, kosztem utrudnienia programowania – aplikacje korzystające z baz NoSQL muszą zawierać kod odpowiedzialny za utrzymanie spójności danych. Programowe metody zachowania spójności przetwarzanych danych rozważono w kontekście wybranych systemów NoSQL: MongoDB, Mircosoft Windows Azure, Apache Cassandra, Oracle NoSQL.

EN

Consistency preservation is a general problem in data processing, especially in NoSQL systems. NoSQL databases introduce a new approach, in which the efficiency is a major feature. It is partially achieved at the expense of some difficulties of programming. The application should handle situations which may introduce inconsistency in data. The paper presents the methods of data consistency preservation in selected NoSQL: MongoDB, Mircosoft Windows Azure, Apache Cassandra, Oracle NoSQL.

11

Wyznaczanie pokrycia sieci Petriego przez SM-komponenty z wykorzystaniem przeszukiwania grafów

Karatkiewicz A., Wiśniewski R.

Przegląd Elektrotechniczny

|

2012

|

R. 88, nr 8

141-144

PL

W artykule przedstawiono nową metodę dekompozycji na składowe automatowe żywych i bezpiecznych sieci Petriego, należących do klasy rozszerzonych sieci swobodnego wyboru (EFC). Metoda polega na przeszukiwaniu grafu sieci, biorąc pod uwagę relację współbieżności pomiędzy miejscami sieci. Przedstawiono i omówiono wyniki wstępnych eksperymentów, które pokazują dużą skuteczność metody względem rozwiązań ogólnie stosowanych, szczególnie w przypadku sieci zawierających wiele miejsc wzajemnie współbieżnych.

EN

In the paper a new method of state machine decomposition of live and safe Petri net that belongs to the Extended Free-Choice class is presented. The method is based on search of the net graph, taking into account concurrency relation between places of the net. The method can be divided into two main steps. In the first one concurrency relation between particular places of the Petri net is computed. Next, the main decomposition process is performed, where subsequent SM-components are calculated. At the first step the method operates on the structure of the net. It is based on the modified algorithm, initially proposed by A.V. Kovalyov in [1]. Such an algorithm permits to find the concurrency relations between places in the Free Choice nets in a polynomial time. Next, the subsequent SM-components are computed. To find each SM-component, a graph-search algorithm is applied. Moreover, the concurrency relation obtained in the first step of proposed method is also taken into account. The method has polynomial computational complexity, unlike most of other methods of such decomposition. It is proved that the first step of an algorithm can be executed in a polynomial time in a case of a Extended Free Choice nets. Furthermore, the graph-search algorithm operates in a linear time, thus the whole decomposition process can be performed in a polynomial time.

12

Application of Clojure Language to Build Multitasking Simulation Tool

Koziński W.

Przegląd Elektrotechniczny

|

2012

|

R. 88, nr 2

110-114

EN

Simulation tool for various kinds of planar vehicles is presented. Each of vehicle is treated as separate object and executed in a thread. Such approach leads to multithreaded system, where concurrency rules have to be obeyed. The proper software tool has to be selected. One of candidates is Java language, with TimerTask objects or Executors, other one is newly developed language Clojure. The Clojure language is interpreted and executed by Java Virtual Machine and possesses many features, which are helpful to build multithreaded, concurrent systems.

PL

Prezentowane jest narzędzie do symulowania ruchu pojazdów na płaszczyźnie. Każdy pojazd traktowany jest jako oddzielny obiekt i wykonywany w wątku. Takie podejście prowadzi do systemu wielowątkowego, w którym muszą być zachowane zasady budowy bezpiecznych programów współbieżnych. Istotnym jest wybór właściwego narzędzia. Jedną z możliwości jest wybór języka Java. Inną możliwością jest wybór języka Clojure wykonywanego przez wirtualną maszynę języka Java.

13

Causal Behavioural Profiles - Efficient Computation, Applications and Evaluation

Weidlich M., Mendling J., Polyvyanyy A., Weske M.

Fundamenta Informaticae

|

2011

|

Vol. 113, nr 3/4

399-435

EN

Analysis of behavioural consistency is an important aspect of software engineering. In process and service management, consistency verification of behavioural models has manifold applications. For instance, a business process model used as system specification and a corresponding workflow model used as implementation have to be consistent. Another example would be the analysis to what degree a process log of executed business operations is consistent with the corresponding normative process model. Typically, existing notions of behaviour equivalence, such as bisimulation and trace equivalence, are applied as consistency notions. Still, these notions are exponential in computation and yield a Boolean result. In many cases, however, a quantification of behavioural deviation is needed along with concepts to isolate the source of deviation. In this article, we propose causal behavioural profiles as the basis for a consistency notion. These profiles capture essential behavioural information, such as order, exclusiveness, and causality between pairs of activities of a process model. Consistency based on these profiles is weaker than trace equivalence, but can be computed efficiently for a broad class of models. In this article, we introduce techniques for the computation of causal behavioural profiles using structural decomposition techniques for sound free-choice workflow systems if unstructured net fragments are acyclic or can be traced back to S- or T-nets. We also elaborate on the findings of applying our technique to three industry model collections.

14

A Kleene-Schützenberger Theorem for Trace Series over Bounded Lattices

Huschenbett M.

Fundamenta Informaticae

|

2011

|

Vol. 112, nr 2/3

171-191

EN

We study weighted trace automata with weights in strong bimonoids. Traces form a generalization of words that allow to model concurrency; strong bimonoids are algebraic structures that can be regarded as "semirings without distributivity". A very important example for the latter are bounded lattices, especially non-distributive ones. We show that if both operations of the bimonoid are locally finite, then the classes of recognizable and mc-rational trace series coincide and, in general, are properly contained in the class of c-rational series. Moreover, if, in addition, in the bimonoid the addition is idempotent and the multiplication is commutative, then all three classes coincide.

15

The conception of concurrent Petri net and its synthesis

Piech H., Skibińska W.

Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej

|

2010

|

Vol. 9, nr 1

165-176

EN

Petri net is form of bipartite graph. Schemes in form of Petri (PT) net permit modeling systems, objects, automata etc. Petri model becomes virtual prototype of represented system. Natural phenomena in PT nets is concurrent realized actions. It is guarantee by organization of fired transitions system. That are realized sequentially as singly or grouped procedures. In our approach we propose treat placements in standard connections with input and output system transitions. It is deeply form of concurrent because of unify structure of joining with all others placements. In this conception it's also possibility to fix sequence of fired transitions. Proposed concurrent PT net expand possibility of functional model dealing by invariant combinations of weights structures.

16

PSF - A Retrospective

Veltin G.J.

Fundamenta Informaticae

|

2010

|

Vol. 100, nr 1/4

181-227

EN

Modern day computer architectures offer ever-increasing support for parallel processing, still it turns out to be quite difficult for programmers and therefore programs to tap into these parallel resources. To benefit from real general-purpose parallel computing we claim that it is likely that a paradigm shift is needed in the way we think about programming. This change of thought in turn will need to be reflected in future programming languages as well. We think that the field of process algebra provides thorough insight in how to reason about the construction of software for concurrent systems and will be one of the enabling technologies supporting this transition. The wish to connect process algebra, a mathematical theory, to the world of computer-readable and executable specifications led to the development of PSF (Process Specification Formalism). PSF is an implementation of the process algebra ACP (Algebra of Communicating Processes) integrating ASF (Algebraic Specification Formalism) to specify algebraic data types. One of the first publications on PSF appeared in Fundamenta Informaticae in 1990. Here we stated as the first sentence of the abstract: "Traditional methods for programming sequential machines are inadequate for specifying parallel systems". Unfortunately, though some advancements have been made since 1990, we can still uphold this statement 20 years later. This current report documents the developments that lead to the construction of PSF and the 1990 publication and moreover it also documents how PSF and its tools have evolved since 1990 taking the conclusion and the outlook for future work from the original article as a reference point. Using the knowledge gained both in constructing tools for PSF and in using PSF to specify concurrent systems, we will judge, discuss and criticise the design decisions taken and show paths for future developments.

17

Application of Concurrency in the Asynchronous Design of Write-after-read Operations

Toosizade N., Zaky S.G.

Fundamenta Informaticae

|

2009

|

Vol. 95, nr 1

31-52

EN

This paper introduces enhancements to the synthesis of circuits that involve write-afterread (WAR) operations and use the four-phase handshake protocol. The paper demonstrates that the use of edge-triggering makes possible many useful trade-offs among speed, area and powerdelay product. Significant increases in speed are possible as a result of increased concurrency in the circuit's operation, which compensates for much of the penalty associated with the down phase of the four-phase protocol. It is also shown that concurrency can be increased by the judicious insertion of T-elements in the system's control structure. Simulation results for a 16-bit accumulator showed a speed increase of 50% and a reduction of 23% in the power-delay product. The speed of a radix-4 Booth multiplier increased by over 27% and its area and energy consumption were reduced by 5%. These results were derived using test circuits synthesized by Balsa and implemented in Synopsys using 180-nm technology.

18

Collaborative processing of XML documents in Internet

Sikorski A.

Theoretical and Applied Informatics

|

2008

|

Vol. 20, No. 4

229-244

EN

In order to enable eective collaboration on XML documents published in Internet, we propose an indexing technique making use of nodes labeling. In particular we consider two types of locks, acquired by multiple user transactions on segments of a document. These segments correspond to paths and ranges – defined by labels, with the document subtree being a special case of a range. We put forward algorithms for consolidation of shared locks that define a continuous covering, a way of initial processing simplifying and accelerating the lock manager. Two algorithms for the lock manager are framed with the use of XML labels for both the 2PL protocol and the cooperative one. We also point to some interesting ties between the lock management and the shortest path problem. Our motivation is given in the context of the SEDNA native XML DB isolation rules, however, our technique is useful for most of the fine-granular lock protocols.

PL

Ze względu na swa elastyczność oraz poparcie formatu przez znaczące gremia standaryzacyjne XML stał się powszechnie stosowanym sposobem udostępniania i wymiany danych, popularnym zwłaszcza w Internecie. Dokument XML można postrzegać również jako instancję, co prawda dość ograniczoną funkcjonalnie, obiektowej bazy danych, na której możliwe jest współbieżnie wykonywanie operacji aktualizujących. Jeżeli aktualizacje zasobu danych mają się odbywać współbieżnie, to konieczne jest ich synchronizowanie za pomocą odpowiedniego menedżera, zarządzającego blokowaniem węzłów XML i udostępnianiem odpowiednich danych. Zaproponowane w pracy rozwiązanie oparte jest na wykorzystaniu tzw. etykiet węzłów dokumentu XML [5],[6], do celów identyfikacji blokowanych obiektów i obsługi stanu menedżera blokad. Pojawienie się etykiet związane jest z pracami [7],[8] nad efektywnym wykonywaniem zapytań XPath, mającymi na celu optymalizację algorytmu wyznaczania tzw. złączenia strukturalnego (odpowiednik złączenia relacyjnego znanego z SQL). Okazuje się, że wartości etykiety mogą w wydajny sposób definiować pewne podzbiory węzłów dokumentu XML, podlegające blokowaniu przez menedżera współbieżności, umożliwiając tym samym implementację złożonych reguł współbieżności. Kluczowe dla wydajnego zarządzania współbieżnością jest operowanie takimi podzbiorami węzłów jak: ścieżka, poddrzewo czy zakres wierzchołków (wierzchołki o etykietach mających wartości z określonego przedziału). Chociaż rozwiązanie jest prezentowane w kontekście dokumentów XML i reguł współbieżnego przetwarzania bazy XML Sedna [2], to możliwe jest jego stosowanie do celów synchronizacji współbieżnego przetwarzania hierarchicznych (drzewiastych) struktur danych (Fig.4.). Blokady zakładane na zbiorach sa są przykładami szczególnych blokad predykatowych (intensjonalnych), których obsługa jest możliwa w czasie log(n), względem liczby założonych blokad. Predykaty te są formułami o postaciach zależnych jedynie od typu zbioru (tj. drzewo, ścieżka , zakres), zawierającymi wartości etykiet. Należy też zwrócić uwagę, że liczba n od której zależy złożoność obsługi blokady, jest na ogół dużo mniejsza od liczby zablokowanych węzłów dokumentów, ponieważ blokady zakładane mogą być na całych zbiorach.

19

Interpreted Nets

Czaja L.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 3-4

283-293

EN

The nets considered here are an extension of Petri nets in two aspects. In the semantic aspect, there is no one firing rule common to all transitions, but every transition is treated as an operator on data stored in its entry places and return results in its exit places. A state (marking) is a mapping of places (variables) into a given data structure, while interpretation is a mapping of transitions into a set of state transformers. Locality of transition's activity is like in Petri nets. In the structural aspect, entry and exit places to a transition are ordered. A concatenation of such nets is defined, hence their calculus (a monoid). This allows for combining small nets into large ones, in particular designing a computation and control parts separately, then putting them together into one. Such extended nets may produce, in particular, other nets. A number of properties of the operation on nets and their decomposition are demonstrated.

20

Communication Dualism in Distributed Systems with Petri Net Interpretation

Chrobot S., Daszczuk W.

Theoretical and Applied Informatics

|

2006

|

Vol. 18, nr 4

261-278

EN

In the paper notion of communication dualism id formalized and explained in Petri net interpretation. We considcr communication dualism a basic property of communication in distributcd systems. The formalization is done in the Integrated Model of Distributed Systems (IMDS) where synchronous communication, as wcll as asynchronous message-passing and variable-sharing are modeled in a common framework. In the light of this property, communication in distributed systems can be seen as a two-dimensional phenomenon with passing being its spatial dimension and sharing its temporal dimension. Any distributed system can be modeled as a composition of message-passes asynchronous processes or as a composition of variable-sharing asynchronous processes. A method of automatic process extraction in Petri net interpretation of IMDS is presented.

PL

W artykule zdefiniowano pojęcie dualizmu komunikacyjnego oraz przedstawiono jego interpretację w sieci Petri. Dualizm komunikacyjny jest uznawany przez autorów za fundamentalną własność komunikacji w systemach rozproszonych. Formalizację przeprowadzono przy użyciu Zintegrowanego Modelu Systemów Rozproszonych (IMDS), w którym wprowadzono elementy pamięciowe rezydujące w węzłach i elementy przesyłane adresowane do węzłów. Podstawowym elementem dynamicznym jest akcja polegająca na spotkaniu elementu pamięciowego z elementem przesyłanym i wygenerowanie na ich miejsce zbioru nowych elementów pamięciowych i przesyłanych. Formalizm IMDS w jednolitej strukturze obejmuje komunikację synchroniczną i asynchroniczną, zarówno opartą o przesyłanie meldunków jak i o współdzielenie zmiennych. Z punktu widzenia dualizmu komunikacyjnego komunikacja jest dwuwymiarowym zjawiskiem, w którym przesyłanie meldunków odbywa się w wymiarze przestrzennym a współdzielenie zmiennych w wymiarze czasowym. Każdy system rozproszony może być przedstawiony jako złożenie asynchronicznych procesów przesyłających komunikaty lub jako złożenie asynchronicznych procesów współdzielących zmienne. Przedstawiono dwie kanoniczne dekompozycje systemów na procesy rezydentne z jednej strony i procesy podróżne z drugiej. W dekompozycji na procesy rezydentne wartości zmiennych są wewnętrznym sposobem komunikacji w procesie, a przesyłanie meldunków jest komunikacją międzyprocesową. W dekompozycji na procesy podróżne meldunki stanowią wewnętrzną komunikację w procesie, a współdzielenie zmiennych jest komunikacją międzyprocesową. Wprowadzono interpretację elementów pamięciowych i przesyłanych jako miejsc w sieci Petri, wykonania akcji jako odpalenia przejścia w sieci Petri, oraz interpretację ciągu odpaleń przejść poprzez miejsca określonego typu jako procesów. Przedstawiono sposób powoływania i zakańczania procesów. Podano sposób automatycznego wyodrębnienia procesów rezydentnych i podróżnych systemu w interpretacji IMDS przy pomocy sieci Petri.