Wyniki wyszukiwania - BazTech

1

Running a workflow without workflows: a basic algorithm for dynamically constructing and traversing an implied Directed Acyclic Graphin a non-deterministic environment

Smilianets Fedir, Finogenov Oleksii

Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska

|

2024

|

T. 14, nr 1

115--118

EN

This paper introduces a novel algorithm for dynamically constructing and traversing Directed Acyclic Graphs (DAGs) in workflow systems, particularly targeting distributed computation and data processing domains. Traditional workflow managementsystems rely on explicitly defined, rigid DAGs, which can be cumbersome to maintain, especially in response to frequent changes or updates in the system. Our proposed algorithm circumvents the need for explicit DAG construction, instead opting for a dynamic approach that iteratively builds and executes the workflow based on available data and operations, through a combination of entities like Data Kinds, Operators, and Data Units, the algorithm implicitly forms a DAG, thereby simplifying the process of workflow management. We demonstrate the algorithm’s functionality and assess its performance through a series of tests in a simulated environment. The paper discusses the implications of this approach, especially focusing on cycle avoidance and computational complexity, and suggests future enhancements and potential applications.

PL

W artykule przedstawiono nowy algorytm dynamicznego konstruowania i przejść skierowanych grafów acyklicznych (DAG) w systemach zarządzania przepływem pracy, w szczególności tych ukierunkowanych na domeny obliczeń rozproszonych i przetwarzania danych. Tradycyjne systemy zarządzania przepływem pracy opierają się na jawnie zdefiniowanych, sztywnych grafach DAG, które mogą być uciążliwe w utrzymaniu, zwłaszczaw odpowiedzi na częste zmiany lub aktualizacje systemu. Proponowany algorytm pozwala uniknąć konieczności jawnego konstruowania SAG, zamiast tego wybierając dynamiczne podejście, które iteracyjnie buduje i wykonuje przepływy pracy w oparciu o dostępne dane i operacje. Korzystając z kombinacji jednostek, takich jak typ danych, operator i element danych, algorytm niejawnie buduje DAG, upraszczając w ten sposób proces zarządzania przepływami pracy. Demonstrujemy funkcjonalność algorytmu i oceniamy jego wydajność za pomocą serii testów w symulowanym środowisku. W artykule omówiono implikacje tego podejścia, ze szczególnym uwzględnieniem unikania pętli i złożoności obliczeniowej, a także zasugerowano dalsze ulepszenia i potencjalne zastosowania.

2

Timing analysis of multitask systems in SystemC environment

Golly Ł., Pułka A.

Elektronika : konstrukcje, technologie, zastosowania

|

2013

|

Vol. 54, nr 2

17-22

EN

The paper concerns design and modeling of real time systems with strong timing requirements. The problem is presented and analyzed on high level abstract models implemented in SystemC - a modern tool for electronic embedded systems design. The paper outlines advantages of transaction level modeling technique, which is very efficient for complex systems and well suited in SystemC environment. The authors define the universal kernel for functionality, communication and timing issues modeling. The problem has been analyzed on various examples of multitasks' scenarios composed of set of worst case timing benchmark algorithms (WCET). Results obtained during many experiments with models have proved the flexibility and efficiency of the proposed approach to the multitask systems modeling.

PL

Artykuł dotyczy zagadnień projektowania oraz modelowania systemów czasu rzeczywistego o istotnych wymaganiach czasowych. Problem został przedstawiony i przeanalizowany na abstrakcyjnych modelach zaimplementowanych w języku SystemC - nowoczesnym narzędziu do projektowania elektronicznych systemów wbudowanych. W artykule podkreślono korzyści techniki modelowania na poziomie transakcji, która jest bardzo wydajna w odniesieniu do złożonych systemów, a język SystemC bardzo dobrze nadaje się do stosowania tej techniki modelowania. Autorzy zdefiniowali uniwersalny rdzeń swojego środowiska do modelowania zagadnień związanych z funkcjonalnością, komunikacją oraz zależnościami czasowymi. Problem został przeanalizowany na wielu przykładach wielozadaniowych scenariuszy złożonych z zbioru standardowych wzorcowych algorytmów przeznaczonych do czasowej analizy najgorszego przypadku (WCET). Wyniki otrzymane podczas szeregu eksperymentów na modelach dowiodły, że zaproponowane podejście do zagadnienia modelowania systemów wielozadaniowych jest bardzo elastyczne i wydajne.

3

Time predictable systems based on pipeline processor with interleaving of hardware threads

Golly Ł, Pułka A

Elektronika : konstrukcje, technologie, zastosowania

|

2013

|

Vol. 54, nr 12

36-40

EN

The paper presents the microarchitecture of highly predictable real-time systems based on pipeline processor with the idea of thread interleaving. The abstract model of such to real-time electronic embedded systems is given. The authors put their main efforts to obtain highly repeatable and time predictable applications with strong timing requirements. The problem is presented and analyzed on high level abstract models implemented in SystemC – a modern tool for electronic embedded systems design and prototyping. The paper investigates issues concerning the threads’ communication with the memory system. A special threads suspending mechanism has been proposed. The presented issues have been analyzed on various examples of multitasks’ scenarios composed of set of worst case Mälardalen benchmark programs (WCET ). The optimal scheduling scenarios with flexible usage of available resources with respect to the timing constraints have been analyzed. The presented methodology proved to be a good tool for high level system models analysis.

PL

Artykuł przedstawia mikroarchitekturę przewidywalnego czasowo systemu opartą na procesorze potokowym, w którym zastosowano ideę przeplotu wątków. Przedstawiono abstrakcyjny model takiego procesora zastosowanego do aplikacji pracujących w elektronicznych systemach wbudowanych czasu rzeczywistego. Autorzy położyli główny nacisk na uzyskanie wysoce powtarzalnego i przewidywalnego czasowo systemu pracującego przy silnych wymaganiach czasowych. Problem został przeanalizowany na modelach zaimplementowanych na wysokim poziomie abstrakcji w języku SystemC. W artykule przeprowadzono również badania dotyczące zagadnień komunikacji wątków z systemem pamięci. Zaproponowano specjalny mechanizm zawieszania pracy wątków. Omawiane zagadnienia zostały przedstawione na przykładach wielozadaniowych scenariuszy złożonych z zbioru standardowych wzorcowych algorytmów Mälardalen przeznaczonych do czasowej analizy najgorszego przypadku (WCET ). Dokonano analizy optymalnych scenariuszy harmonogramowania zadań z elastycznym wykorzystaniem dostępnych zasobów przy narzuconych wymaganiach czasowych. Zaprezentowana metoda pokazała, że stanowi dobre narzędzie analizy modeli systemów wysokiego poziomu.

4

Metoda dekompozycji algorytmów przetwarzania obrazów dla implementacji w układach FPGA

Pamuła W.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 6

648-651

PL

Artykuł prezentuje metodę dekompozycji algorytmów przetwarzania obrazów na potok przetwarzania zrealizowany z użyciem sparametryzowanych modułów. Moduły realizują niskopoziomowe operacje na pikselach obrazu oraz śledzenie zmian w wyliczonym opisie klatki obrazu. Uznano taki zakres operacji za wystarczający dla opracowania wideo detektorów obiektów. Wykorzystywany jest szeregowy strumień wideo z kamery. Implementacje dowodzą skuteczności zastosowania metody. Uzyskano prędkość przetwarzania przewyższającą wymagania pracy w czasie rzeczywistym oraz znaczną zdolność do modyfikacji własności rozwiązań.

EN

Efficient decomposition of image processing algorithms is of paramount importance in designing FPGA based video detectors of objects for use, for instance, in surveillance systems or in road traffic control applications. Efficiency appraisal is done taking into account resource utilisation, capability of introducing new processing features and components costs. Real time processing adds additional constraints on this task. Available development tools do not facilitate the design process. The paper presents a method for decomposing the image processing algorithm into an efficient processing pipeline of parameterised components. The components perform low level image processing tasks and content tracking operations. Such a set of processing operations is adequate for designing video detectors of objects. Components for carrying out feature calculations using convolutions, morphology operators and corner detectors are presented. Their architecture is optimised for serial video streams, which provide the image contents using horizontal scanning. FPGA resource requirements are estimated for devices of leading manufacturers. The estimated processing speed exceeds the requirements of real time operation. Special attention is directed to pipelining calculations, streamlining multi operand computations, fast determination of minimum, median and maximum of values. An implementation of a video object detector, using a low cost FPGA, is presented proving the feasibility of this approach.

5

Efektywna implementacja algorytmu wyszukiwania wzorców genetycznych

Milik A., Pułka A.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 1

15-18

PL

W artykule zaprezentowano implementację algorytmu obliczającego stopień podobieństwa sekwencji znaków (genów) do zadanego wzorca. Algorytm wywodzi się z biologii obliczeniowej. Rozwiązania programowe wymagają znacznych zasobów sprzętowych oraz czasu. W badaniach nad algorytmem główny nacisk położono na poznanie jego własności i ich wykorzystanie przy implementacji. Pozwoliło to stworzyć bardzo oryginalna implementację zapewniającą niezwykle oszczędne gospodarowanie zasobami w układzie programowalnym jak i uzyskanie bardzo wysokich częstotliwości pracy.

EN

The paper describes implementation of the computation algorithm in modern, complex programmable hardware devices. The presented algorithm originates from computation biology and works on very long chains of symbols which come from reference patterns of the genome. The software solutions in this field are very limited and need large time and space resources. The main research efforts were aimed at investigating the properties of the searching algorithm. Especially, the influence of the penalty values assigned to the mismatch, insertion and deletion on the algorithm was analysed. This allowed obtaining a completely new algorithm offering extremely efficient implementation and exhibiting the outstanding performance. The Virtex 5 FPGA family was considered to be a target family for the searching algorithm based on the dynamic programming idea. The obtained results are very promising and show the dominance of the dedicated platform over the general purpose PC-based systems.