PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 15

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Selection of search strategies for solving 3-SAT problems
Pułka A.
International Journal of Applied Mathematics and Computer Science
|
2014
|
Vol. 24, no. 2
283--297
EN
The paper concerns the problem of Boolean satisfiability checking, which is recognized as one of the most important issues in the field of modern digital electronic system verification and design. The paper analyzes different strategies and scenarios of the proving process, and presents a modified and extended version of the author’s FUDASAT algorithm. The original FUDASAT methodology is an intuitive approach that employs a commonsense reasoning methodology. The main objective of the work is to investigate the SAT-solving process and try to formulate a set of rules controlling the reasoning process of the FUDASAT inference engine. In comparison with the author’s previous works, the paper introduces new mechanisms: hypergraph analysis, multiple variable assignments and search space pruning algorithms. The approach considers only 3-SAT class functions, although a generalization of the method is discussed as well. The presented approach has been tested on various benchmarks and compared with the original pure FUDASAT algorithm as well as with other algorithms known from the literature. Finally, the benefits of the proposed SAT solving technique are summarized.
2
Synteza i implementacja układu sterowania w strukturze FPGA opisanego językiem SFC zgodnego z IEC61131
Milik A., Pułka A.
Elektronika : konstrukcje, technologie, zastosowania
|
2014
|
Vol. 55, nr 12
17-20
PL
Artykuł przedstawia opracowany całościowy proces syntezy wielokontekstrowego sprzętowego układu sterowania implementowanego w strukturach FPGA. Dedykowana struktura sprzętowa pozwala na zdecydowane zredukowanie czasu przetwarzania w porównaniu z rozwiązaniami programowymi. Program podlegający syntezie jest opisany językiem SFC zgodnie z normą IEC61131-3. W procesie syntezy wykorzystano oryginalną grafową metodę reprezentacji postaci pośredniej programu sterowania. Metoda konstruowania postaci pośredniej zachowuje własności przetwarzania, ujawniając zadania równoległe. Opracowano również metodę odwzorowania technologicznego dla tablicowych układów FPGA. W celu porównania przedstawiono rezultaty implementacji opracowanej metody oraz bezpośredniego odwzorowania postaci grafowej.
EN
The paper presents the synthesis and implementation algorithms of multiple context logic controller implemented in a FPGA. A massively parallel hardware execution of control algorithms is utilized that significantly reduces the throughput time. The input program is written in the SFC according to the IEC61131-3 standard. An originally developed intermediate representation based on data flow graph has been used for processing. The graph building algorithm maintains sequential dependencies and reveals parallel tasks in program. Developed method of scheduling and mapping is dedicated for LUT based FPGA devices. The paper is concluded with exemplary implementation comparison of greedy direct mapping and developed FPGA architecture optimized method.
3
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.
4
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.
5
Content available Measurement aspects of genome pattern investigations - hardware implementation
Pułka A., Milik A.
Metrology and Measurement Systems
|
2012
|
Vol. 19, nr 1
49-62
EN
The work presented in the paper concerns a very important problem of searching for string alignments. The authors show that the problem of a genome pattern alignment could be interpreted and defined as a measuring task, where the distance between two (or more) patterns is investigated. The problem originates from modern computation biology. Hardware-based implementations have been driving out software solutions in the field recently. The complex programmable devices have become very commonly applied. The paper introduces a new, optimized approach based on the Smith-Waterman dynamic programming algorithm. The original algorithm is modified in order to simplify data-path processing and take advantage of the properties offered by FPGA devices. The results obtained with the proposed methodology allow to reduce the size of the functional block and radically speed up the processing time. This approach is very competitive compared with other related works.
6
Content available Implementacja wyrażeń arytmetycznych w rekonfigurowalnych sterownikach logicznych
Milik A., Pułka A.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 8
842-844
PL
W artykule przedstawiono metodę odwzorowania operacji arytmetycznych przeznaczoną dla rekonfigurowalnych sterowników logicznych. Istotą opracowanej metody jest wykorzystanie własności układów sprzętowych oraz architektury FPGA. W procesie implementacji brane są pod uwagę czas realizacji obliczeń oraz ograniczone zasoby logiczne. W oparciu o metodę szacowania czasu propagacji zrealizowano metodę łańcuchowego łączenia operacji kombinacyjnych pozwalającą na wykonanie wielu operacji w cyklu obliczeniowym.
EN
The paper presents a package for arithmetic operation synthesis dedicated for reconfigurable logic controllers. Different representations (graphical or textual) commonly used are handled. The synthesis process starts from transforming algorithm representation into a data flow graph. The constant reduction and the tree height reduction optimization method are applied to the flow graph (Fig. 2). The developed method combines the ALAP and list allocation strategies with original elements. The main constraint is put to the number of available logic resources that can be allocated. The procedure attempts to allocate resources assuring it proper utilization in a calculation process. Together with resource allocation the operation scheduling is performed. During operation assignment the propagation time based concept of operation scheduling is used. The proposed method allows using sequential and combinatorial units. Operations are chained inside one state until total combinatorial propagation time does not exceed the assumed cycle time. This allows reducing the required number of calculation cycles by introducing combinatorial chains of operations (Figs. 3 and 4). Finally, an example of PID controller implementation is considered and compared with previous manual implementations (Fig. 5). Introducing the automatic implementation method allows reducing radically the calculation time (2.18 times) with little increase in hardware resources (+18%) (see Tab. 1).
7
Content available 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.
8
Content available Two heuristic alghorithms for test point selection in analog circuit diagnoses
Pułka A.
Metrology and Measurement Systems
|
2011
|
Vol. 18, nr 1
115-128
EN
The paper presents a heuristic approach to the problem of analog circuit diagnosis. Different optimization techniques in the field of test point selection are discussed. Two new algorithms: SALTO and COSMO have been introduced. Both searching procedures have been implemented in a form of the expert system in PROLOG language. The proposed methodologies have been exemplified on benchmark circuits. The obtained results have been compared to the others achieved by different approaches in the field and the benefits of the proposed methodology have been emphasized. The inference engine of the heuristic algorithms has been presented and the expert system knowledge-base construction discussed.
9
Content available An Efficient Hardware Implementation of Smith-Waterman Algorithm Based on the Incremental Approach
Pułka A., Milik A.
International Journal of Electronics and Telecommunications
|
2011
|
Vol. 57, No. 4
489-496
EN
The paper presents optimized hardware structure applied to genome alignment search. The proposed methodology is based on dynamic programming. The authors show how starting from the original Smith-Waterman approach, the algorithm can be optimized and the evaluation process simplified and speeded-up. The main idea is based on the observations of growth trends in the adjacent cells of the systolic array, which leads to the incremental approach. Moreover various coding styles are discussed and the best technique allowing further reduction of resources is selected. The entire processing unit utilizes fully pipelined structure that is well balanced trade-off between performance and resource requirements. The proposed technique is implemented in modern FPGA structures and obtained results proved efficiency of the methodology comparing to other approaches in the field.
10
An effective SAT-Solving mechanism with backtrack controlled by FDL
Pułka A.
Elektronika : konstrukcje, technologie, zastosowania
|
2011
|
Vol. 52, nr 12
21-25
EN
This work presents a novel approach to SAT solving problem based on commonsense reasoning methodology. The methodology has been implemented and tested in PROLOG. Discussion of different modern approaches to the satisfiability that have been published recently is presented. A parallelism between the SAT solving problem and non-monotonic extensions verifying is given. The new algorithm of SAT solving based on fuzzy default reasoning (FDL) theory FUDASAT and cumulativity of CNF formulas is defined. Optimal backtracking search methodology is explained on examples. Some experiments on various benchmarks show the efficiency and advantages of the proposed methodology.
PL
Artykuł przedstawia nowe podejście do problemu badania spełnialności formuł logicznych oparte na metodzie wnioskowania zdroworozsądkowego. Zaproponowana metoda została zaimplementowana i przetestowana w środowisku języka PROLOG. Przeprowadzono szczegółową dyskusję dotyczącą istniejących nowoczesnych technik sprawdzania spełnialności formuł logicznych, które zostały opublikowane w ostatnich latach. Przedstawiono podobieństwa między problemem badania spełnialności formuł logicznych a weryfikacją rozszerzeń w logice niemonotonicznej. Sformułowano podstawowe założenia nowego algorytmu FUDASAT badania spełnialności formuł logicznych opartego na wnioskowaniu FDL oraz zdefiniowano problem kumulacyjności formuł w postaci normalnej CNF. Metoda optymalnego przeszukiwania podczas nawrotów została opisana na przykładach. Eksperymenty przeprowadzone na zestawach wzorcowych pokazują zalety proponowanej metody.
11
Strategia weryfikacji systemu na chipie oparta na mechaniźmie FDL
Pułka A.
Elektronika : konstrukcje, technologie, zastosowania
|
2010
|
Vol. 51, nr 12
87-90
PL
Artykuł dotyczy zagadnień weryfikacji formalnej złożonych systemów elektronicznych, tzw. SoC. W pracy zaproponowano nowe oryginalne podejście do planowania strategi weryfikacji opartej o wnioskowanie zdroworozsądkowe. Opisano formalną metodologię mechanizmu planowania bazującą na rozproszonej logice domniemań FDL (Fuzzy Default Logic). Zdefiniowano wieloetapową strategię weryfikacji w postaci narzędzia systemu weryfikacji związanej z określoną platformą sprzętowo-programową. Metodologia została zweryfikowana na prototypowej platformie SoC połączonej magistralą AMBA. Pokazano zalety proponowanego podejścia.
EN
The paper deals with problem of the formal verification of complex electronic embedded systems. A new commonsense strategy is proposed. The formal methodology of the inference engine modeling based on Fuzzy Default Logic is given. The multistage verification strategy as the platform dependent verification (PDV) toolset is defined. The methodology has been validated on examples on a prototype AMBA-based virtual SoC platform working with SystemVerilog verification procedures. The advantages of the presented methodology have been emphasized.
12
Generacja cykli fundamentalnych metodą dynamicznego budowania drzewa grafu
Pułka A., Golly Ł.
Elektronika : konstrukcje, technologie, zastosowania
|
2010
|
Vol. 51, nr 12
75-77
PL
Tematem artykułu jest oryginalny algorytm umożliwiający wyznaczanie najmniejszych cykli fundamentalnych w grafie nieskierowanym. Zaprezentowane podejście wykorzystuje specyficzną reprezentację grafu w postaci trójkątnej macierzy sąsiedztwa. Na podstawie wyznaczonych cykli algorytm buduje drzewo grafu dodając kolejno wyznaczone w poprzednim kroku cykle. Zaprezentowano kolejne kroki algorytmu wraz z przykładem oraz porównano go z innymi metodami. Na koniec, przedstawiono wyniki eksperymentalne oraz wnioski pokazujące zalety zastosowanej metody.
EN
The paper introduces the original algorithm of finding minimal fundamental cycles in the undirected graph. The presented approach uses a specific graph representation of the triangular neighborhood matrix for finding minimal cycles. Then the algorithm generates the graph tree by adding these cycles. The methodology is described step by step on examples and compared to other approaches in the field. Finally, the results of some tests and conclusions emphasizing the advantages of the algorithm summarize the work.
13
Dynamiczna rekonfiguracja wątków w systemach czasu rzeczywistego pracujacych w warunkach pełnej powtarzalności czasowej
Pułka A., Milik A.
Elektronika : konstrukcje, technologie, zastosowania
|
2010
|
Vol. 51, nr 12
40-43
PL
Artykuł dotyczy zagadnień projektowania systemów czasu rzeczywistego z powtarzalnością, czasową. W pracy zaproponowano nową, oryginalną, architekturę wielozadaniową, elektronicznego systemu wbudowanego z przeplotem wątków. Opisano poszczególne elementy składowe systemu, szczególny nacisk położono na programowalny kontroler przeplotu, jednostkę odpowiedzialną za sterowanie kolejnością przetwarzanych wątków w potoku. Zaproponowano dodatkowe rozwiązanie układu arbitrażowego SDPA pracującego w tle, którego zadanie polega na dynamicznej rekonfiguracji przetwarzanych zadań. Przedstawiono uzyskane rezultaty implementacyjne i symulacyjne. Przedstawiono wnioski końcowe podkreślające elastyczność i uniwersalność zaproponowanego rozwiązania.
EN
The paper concerns design of real time systems that meet precision time (PRET) requirements. A new, original architecture of the multithread embedded system with programmable interleaved pipelining is introduced. Main components are described with special attention devoted to the interleave controller. This element of the system is responsible for controlling of the order of threads loaded into the processor's pipeline. The idea of shadow deadline processing arbiter responsible for dynamic reconfiguration of performed threads (tasks) is given. Results of the implementation and simulation of different arbitration schemes are discussed. Conclusions emphasizing the flexibility and advantages of the proposed solution summarize the paper.
14
Analiza efektywności i kosztów sprzętowej realizacji filtrów cyfrowych o zadanej liniowej charakterystyce fazowej
Milik A., Pułka A., Konopacki J.
Elektronika : konstrukcje, technologie, zastosowania
|
2010
|
Vol. 51, nr 9
40-44
PL
Artykuł porusza kluczowe zagadnienia związane z projektowaniem filtrów cyfrowych o pożądanej liniowej charakterystyce fazowej. Autorzy zaproponowali własną metodologię implementacji filtrów typu SOI oraz NOI. Następnie uzyskane rezultaty (struktury filtrów) zostały przeanalizowane teoretycznie pod kątem ich złożoności obliczeniowej. Wyniki tej analizy zostały zweryfikowane poprzez syntezę sprzętową struktur SOI oraz NOI w programowalnych układach logicznych typu FPGA. Dokonana została optymalizacja pod kątem jak najefektywniejszego wykorzystania dostępnych zasobów. Do realizacji użyto nowoczesne środowisko do modelowania i symulacji układów Active-HDL, które umożliwia współpracę z programem MATLAB.
EN
The paper deals with digital filters design with required linear phase characteristic. The authors proposed a new methodology of digital IIR and FIR filters implementation. The obtained results (filter structures) have been analyzed towards their computation complexity. Results of this analysis have been verified by the logic synthesis of IIR and FIR in FPGA. Then the structures have been optimized for best circuits resources utilization. The modern modeling and cosimulation environment Alcdec's Active-HDL with MATLAB has been used to complete the entire task.
15
Content available Wielordzeniowa jednostka centralna sterownika logicznego z czasowo-deterministycznym oprogramowaniem
Milik A., Pułka A.
Pomiary Automatyka Kontrola
|
2009
|
R. 55, nr 8
681-683
PL
Maszyna deterministyczna czasowo, w odróżnieniu od typowej realizacji programowej pozwala na bardzo precyzyjną realizację zadania w czasie. Problem kolejności przetwarzania i dostępu do danych wspólnych, występujący we współbieżnej realizacji wielu zadań jest łatwy do opanowania. Artykuł przedstawia próbę implementacji wieloprocesorowej jednostki centralnej, wykorzystującej mechanizmy zapewniające determinizm czasowy. Obok implementacji przedstawiono również metodykę generacji wielowątkowego programu sterowania.
EN
Modern processors are optimized to execute instructions as fast as it is possible. A program is written in timeless domain. Problems of data integrity arise when facing a problem of concurrent multithread execution. The shared variables that are used by different threads must be processed in proper order, otherwise race conditions may occur, leading to incorrect results. A precision timed CPU helps to execute tasks in the precisely defined period of time. Time dependencies between properly scheduled tasks at compile time allow preserving the proper order of data processing. The proposed multi core CPU (Fig. 2) consists of 4 CPUs equipped with: local memory (MEM), time control units (TC - Fig. 3) and shared memory (SH_MEM). Time control unit allows controlling the execution time of a current task. The CPU loads to the TC required period of time and starts task execution. When the task is completed, CPU notifies TC which disables the instruction execution until passing the given period of time. The shared memory is constructed of dual port memory. It is equipped with arbitration unit with priority rotation that is able to properly split access requests. The control program is compiled to intermediate form of a directed acyclic graph (DAG - Fig. 1) which is then used to optimize the given problem and for scheduling purposes (Fig. 5).
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.