Wyniki wyszukiwania - BazTech

1

Wirtualizacja systemów komputerowych jako środek zapewnienia niezawodności

Chodorek R. R., Chodorek A.

Autobusy : technika, eksploatacja, systemy transportowe

|

2016

|

R. 17, nr 6

1282-1286

PL

Niniejszy artykuł poświęcony jest dyskusji nad metodami wirtualizacji sprzętu komputerowego i jej zastosowań do zapewnienia zwiększonej niezawodności systemu sprzętowo-programowego. Systemy takie mogą być stosowane obok (a w niektórych przypadkach: zamiast) tradycyjnego powielania wybranych elementów infrastruktury krytycznej. W artykule omówiono zagadnienia związane z wirtualizacją systemów komputerowych. Przedstawiono podstawowe typy wirtualizacji, jej zastosowanie i stosowane w praktyce rozwiązania. W artykule zaprezentowano również wyniki badań systemu wirtualizacji pod kątem jego wydajności, zorientowane na realizację konkretnego mechanizmu rezerw (konkretnej struktury niezawodnościowej).

EN

This article is devoted to the discussion of the methods of virtualization the hardware and its applications to ensure increased reliability of the hardware and software system. Such systems can be used alongside (and in some cases: instead of) traditional duplication of selected elements of critical infrastructure. The article discusses the issues associated with virtualization systems. The article shows the basic types of virtualization, its use and actual practices. The article presents the results of the research system virtualization for its performance-oriented implementation of specific provisioning mechanism (specific reliability structure).

2

Szeregowanie i alokacja zadań w heterogenicznym systemie wieloprocesorowym z wykorzystaniem obliczeń ewolucyjnych

Handzel Z., Gajer M.

Elektronika : konstrukcje, technologie, zastosowania

|

2013

|

Vol. 54, nr 2

79-82

PL

W artykule zaproponowano wykorzystanie techniki obliczeń ewolucyjnych na potrzeby realizacji procesu alokacji i szeregowania zadań jednoprocesorowych i dwuprocesorowych w trójprocesorowym systemie heterogenicznym. Założono, że podlegające procesowi szeregowania zadania są zadaniami przeznaczonymi dla procesorów arbitralnych, a ponadto są zadaniami niewywłaszczalnymi i niezależnymi. Na potrzeby realizacji algorytmu ewolucyjnego zastosowano hybrydowy sposób kodowania rozwiązań na materiale genetycznym osobników.

EN

In the paper we propose implementation of evolutionary computations for the purpose of uniprocessor and biprocessor task scheduling and allocation in a three-processor heterogeneous system. It is assumed that the tasks that are to be scheduled are arbitrary processors tasks. Moreover, these tasks are not pre-emptive and are independent tasks. For the sake of realization of evolutionary algorithm the hybrid coding system on the genetic material of the individuals was used.

3

Implementing the rate monotonic scheduling algorithm for heterogeneous processors

Handzel Z.

Przegląd Elektrotechniczny

|

2012

|

R. 88, nr 12a

143-145

EN

The paper discusses task scheduling issues in real-time systems with hard time constraints. In the paper, we propose to use rate monotonic scheduling for heterogeneous multiprocessor systems. Moreover, for the sake of load balancing we propose to use a genetic algorithm.

PL

W artykule rozważono zagadnienia szeregowania zadań w systemach czasu rzeczywistego z ostrymi ograniczeniami czasowymi. Rozważono możliwości wykorzystania metody rate monotonic scheduling w przypadku heterogenicznych systemów wieloprocesorowych. Ponadto w celu równoważenia obciążenia poszczególnych jednostek obliczeniowych zaproponowano wykorzystanie algorytmu genetycznego.

4

Szeregowanie zadań periodycznych w heterogenicznych systemach wieloprocesorowych

Gajer M.

Elektronika : konstrukcje, technologie, zastosowania

|

2012

|

Vol. 53, nr 4

47-51

PL

W artykule zamieszczono propozycję zastosowania techniki obliczeniowej opartej na algorytmach ewolucyjnych celem optymalizacji procesu alokacji zadań periodycznych w heterogenicznych systemach wieloprocesorowych. Rozważono przypadek szeregowania zbioru zadań periodycznych, wywłaszczałnych i niezależnych, które szeregowane są z wykorzystaniem algorytmu Rate Monotonic Scheduling. W przypadku rozważanych heterogenicznych systemów wieloprocesorowych każdy z procesorów odznacza się nieco innym poziomem mocy obliczeniowej. W związku z powyższym celem algorytmu ewolucyjnego było odnalezienie takich schematów przydziału zadań do poszczególnych procesorów, aby w ramach każdego z nich spełniony był warunek wystarczający na szeregowaIność przydzielonego do niego zbioru zadań z wykorzystaniem algorytmu Rate Monotonic Scheduling.

EN

In the paper we propose the implementation of a computational technique based on evolutionary algorithms for the purpose of optimizing the process of the periodic task allocation in heterogeneous multiprocessor systems. In the article we discuss the case of scheduling a set of periodic, pre-emptive and independent tasks that are scheduled with the use of the Rate Monotonic Scheduling algorithm. In the case of heterogeneous multiprocessor systems the computational power of each processor is slightly different. The aim of the evolutionary algorithm was to find such task allocation schemes for each of the processors so that the sufficient condition for the set of the scheduled tasks was fulfilled. The periodic tasks were scheduled with the use of the Rate Monotonic Scheduling algorithm.

5

Implementacja w układzie reprogramowalnym wieloprocesorowego systemu realizującego algorytm RANSAC

Fularz M., Kraft M.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 8

914-916

PL

W artykule opisano programową, wieloprocesorową realizację algorytmu RANSAC, który umożliwia odporną estymację modelu matematycznego z danych pomiarowych zawierających znaczący odsetek wartości odstających (ang. outliers). System został zaimplementowany w układzie FPGA w oparciu o konfigurowalne soft procesory MicroBlaze. W pracy przedstawiono opis algorytmu RANSAC, sposób jego podziału w celu przetwarzania równoległego, a także proces konfiguracji systemu wieloprocesorowego. Zaprezentowano również przyrost prędkości przetwarzania w zależności od liczby zastosowanych rdzeni procesorowych, porównano te wyniki do realizacji na komputerze klasy PC i przedstawiono zużycie zasobów układu FPGA.

EN

The paper describes a multiprocessor system implementing the RANSAC algorithm [3] which enables robust estimation of a fundamental matrix from a set of image keypoint correspondences containing some amount of outliers. The fundamental matrix encodes the relationship between two views of the same scene. The knowledge of the fundamental matrix enables e.g. the reconstruction of the scene structure. The implemented system is based on three MicroBlaze microprocessors [5] (one master, two slaves) and a dedicated hardware coprocessor connected using fast simplex link (FSL) interfaces [6]. The slave microprocessors perform the task of fundamental matrix computation from point correspondences using singular value decomposition - the so called 8-point algorithm [1, 2] (hypothesis generation). The master processor, along with the connected coprocessor, is responsible for dataflow handling and hypothesis testing using the Sampson error formula (7). The hypothesize and test framework used in RANSAC allows for largely independent task execution. The design is a development of a system described in [5]. The block diagram and dataflow diagram of the proposed solution are given in Figs. 1 and 2, respectively. Tabs. 1 and 2 summarize the use of FPGA resources. With a 100 MHz clock, the designed system is capable of processing the data at the speed which is roughly equivalent to that of the Atom N270 microprocessor clocked at 1,2 GHz. The resulting solution will be targeted at applications for which small size, weight and power consumption are critical. The design is also easily scalable - addition of more slave processors will result in additional increase in the processing speed.

6

Rozszerzenia funkcjonalne arbitrażu magistrali VME

Wiśniewski B., Szecówka-Wiśniewska B.

Elektronika : konstrukcje, technologie, zastosowania

|

2011

|

Vol. 52, nr 10

113-115

PL

Omówiono zasady arbitrażu magistrali VME i obowiązujące standardy. Przedstawiono zasady rozszerzeń funkcjonalnych arbitrażu z uwzględnieniem specyfiki laboratoryjnej. Zaproponowaną rozbudowę funkcjonalną zaprezentowano w postaci sieci działania, w odniesieniu do zminimalizowanego rozwiązania układowego.

EN

VME bus arbiter and obligatory standards are discussed. Principles of functional arbiter's expansions, are presented. Proposed functional extension in form of flow chart is shown, in relation to minimized circuit solution.

7

Symulator do badania własności systemów wieloprocesorowych

Nowicki T., Wrzosek Ł.

Symulacja w Badaniach i Rozwoju

|

2010

|

Vol. 1, nr 3

279-294

PL

W pracy przedstawiono projekt i implementację symulatora programowego systemu wieloprocesorowego. Omówiono charakterystyki takiego systemu. Zdefiniowano poszczególne elementy modelu systemu. Zaprezentowano możliwości symulatora w zakresie badań efektywności systemów wieloprocesorowych. Pokazano szczegółowe charakterystyki, jakie można uzyskać posługując się opracowanym symulatorem.

EN

In this work project and implementation of software simulator of multiprocessor system is presented. Selected characteristics of such system are discussed. Every elements of model of multiprocessor system are defined. Possibilities of simulator from the system efficiency point of view are presented. Many characteristics which can be obtained during simulation experiments of multiprocessor system exploitation are shown.

8

Szeregowanie zadań w systemach czasu rzeczywistego z zastosowaniem techniki obliczeń ewolucyjnych

Gajer M.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 10

293-298

PL

W artykule rozważono zastosowanie techniki obliczeniowej opartej na algorytmach ewolucyjnych w celu optymalizacji procesu szeregowania zadań w systemach czasu rzeczywistego z ostrymi ograniczeniami czasowymi. Na potrzeby realizacji procesu szeregowania zadań wybrana została metoda Rate Monotonic Scheduling (RMS), która bazuje na systemie przydziału priorytetów i jest przewidziana do szeregowania zbiorów wywłaszczalnych, periodycznych i niezależnych zadań. Przeprowadzone eksperymenty numeryczne wykazały, że algorytmy ewolucyjne mogą stanowić skuteczne narzędzie pozwalające na równoważenie obciążenia jednostek obliczeniowych w systemach wieloprocesorowych.

EN

In the paper we discuss the use of a computational technique based on evolutionary algorithms for the purpose of optimizing the task scheduling process in real-time computer systems with hard time constraints. The process of task scheduling was realized with the use of Rate Monotonic Scheduling (RMS) method which is based on the system of priorities assignment and is designed for scheduling sets of pre-emptive, periodic, and independent tasks. We conducted numerical experiments which prove that evolutionary algorithms can constitute an effective tool that ensures balancing the load in multiprocessor systems.

9

Rozwiązywanie numeryczne układów równań liniowych metodą kwadratu gradientów sprzężonych

Szczerbiński Z., Steinborn K.

Metody Informatyki Stosowanej

|

2009

|

nr 4 (21)

113-126

PL

W niniejszym artykule opisano metode˛ kwadratu gradientów sprzężonych rozwiązywania układów równań liniowych oraz jej programową implementację, wraz z przeprowadzonymi za jej pomoca˛ testami efektywności samej metody (skupiono się tu na dokładności wyników) oraz testami przyspieszenia działania w systemach wieloprocesorowych. Testy efektywności metody dowiodły, że metoda kwadratu gradientów sprzężonych bardzo szybko dąży do rozwiązania. Odbywa się˛ to jednak kosztem większej liczby błędów zaokrągleń , a w przypadku wersji obliczania residuum na nowo—kosztem większych oscylacji i mniejszej stabilności.W artykule wykazano, że błędy zaokrągleń , jakie pojawiają˛ się˛ w trakcie wyznaczania rozwiązania, można minimalizować stosując restartowanie metody. Przyspieszanie obliczeń, dzięki zastosowaniu systemów wieloprocesorowych, jest obecnie powszechnym rozwiązaniem, wykorzystywanym do rozwiązywania dużych układów równań liniowych.W artykule potwierdzono korzyści wynikające z ich zastosowania; zaznaczono jednak przy tym, że byłyby one (przypuszczalnie) znacznie wyraźniejsze dla większych, niż analizowane, układów równań i dla realizacji obliczeń z wykorzystaniem większych liczb procesorów. Można obecnie przewidywać dynamiczny rozwój takich badań w związku z obserwowanym od kilku lat rozwojem architektur komputerowych w kierunku zwiększania liczby procesorów w systemie (również: rdzeni w procesorze), nie zaś jedynie zwiększania częstotliwości taktów zegara, co miało przede wszystkim miejsce dotychczas (i czego kres wydaje się być bliski z powodu fizycznych ograniczeń półprzewodników, np. problemu odprowadzania ciepła, jak i ograniczenia naturalnego jakim jest skończona prędkość światła). W tym kierunku zmierzaja˛ również plany autorów niniejszego artykułu na przyszłość. Przewiduja˛ one badanie efektywności obliczeń równoległych, realizujących opisaną w artykule metodę, dla układów równań o (nawet) kilka rzędów większych rozmiarach, na platformach sprzętowych zawierających znacznie większe liczby procesorów (wyspecjalizowane klastry obliczeniowe, superkomputery).

EN

The article is concerned with issues arising in numerical solution of sparse systems of linear equations. Upon introduction to the subject of projection methods for solving such systems, the method of conjugate gradients squared is described in detail, along with its implementation both as a sequential and parallel program. Detailed analyses of both the numerical and timing results, produced by these programs while solving example linear systems, are performed. It is also described how to modify the computation process in order to obtain more accurate results.

10

Zastosowanie binaryzacji okresów zadań w systemach wieloprocesorowych

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 4

545-561

PL

Artykuł dotyczy zastosowania techniki binaryzacji okresów zadań w systemach wieloprocesorowych. Binaryzacja okresów zadań jest techniką polegającą na takiej transformacji wartości okresów zadań periodycznych, aby były wielokrotnościami (będącymi naturalną potęga liczby 2) pewnego okresu bazowego r. Zatem w systemie o okresach binarnych szeregowaniu podlegają zadania o wartościach okresów r, 2r, 4r, 8r, 16r, 32r itd. Binaryzacja okresów zadań ułatwia znalezienie ich planu szeregowania, gwarantującego dotrzymanie ograniczeń czasowych przez wszystkie zadania. Binaryzacja jest stosowana powszechnie w systemach czasu rzeczywistego o ostrych ograniczeniach czasowych. Obecnie binaryzacji wartości okresów podlegają głównie zadania przeznaczone do realizacji w systemach jednoprocesorowych. Artykuł niniejszy stanowi propozycję rozszerzenia obszaru stosowalności techniki binaryzacji okresów zadań na systemy zbudowane z większej liczby jednostek obliczeniowych. Zgodnie z propozycją autora zastosowanie binaryzacji okresów zadań wieloprocesorowych stanowi klucz do zastosowania do ich szeregowania popularnego algorytmu Rate Monotonie Scheduling. Przedstawione w artykule rozważania teoretyczne zostały zilustrowane przykładem szeregowania zadań wieloprocesorowych o okresach binarnych dla systemu zbudowanego z czterech jednostek obliczeniowych.

EN

Nowadays the real-time systems find application in many branches of industry, science and transport. The most important factor in the real-time systems is the time of execution of tasks. The results that are correct but delivered with the violation of task deadline are useless. In the case of hard real-time systems the violation of task deadline can lead to a catastrophe or even loss of human life. This is the reason why the task scheduling theory developed strongly over the last years. In the computer systems with hard real-time constraints the most popular task scheduling algorithm is Rate Monotonie Scheduling (RMS). In RMS all tasks are assigned priorities. The rule is the shorter is task period the higher priority the task obtains. In a given moment the task that is read for execution and has the highest priority is executed. If any other task with higher priority arrives the task that is executed is pre-empted and the task that came is then executed. Together with RMS binarisation is often used. Binarisation is a technique that transforms the periods of tasks in the way that only tasks with harmonic values of periods exist. Up till now binarisation was used only for a uniprocessor systems. This author proposed a new solution in which binarisation is used for multiprocessor systems as well. Scheduling and allocation of multiprocessor tasks in a multiprocessor system is NP - complete optimisation problem. This is the reason why the optimal solution for scheduling of multiprocessor task can not be found in a reasonable time. In such case only suboptimal solutions can be found. This author proposed evolutionary algorithm as a solution to multiprocessor tasks allocation and scheduling. The way in which the order of execution of task is coded on the genetic material was illustrated on the example of scheduling the tasks for four processor systems. The genetic material also allows to code the way in which the proper binarisation is chosen. There are very few tasks scheduling algorithms that could be used for a general class of tasks. There are different scheduling algorithms for uniprocessor task and multiprocessor task and for tasks that are executed on arbitrary or dedicated processors. The algorithm of tasks scheduling and allocation that was proposed by this author is a general one, because it can be used for uniprocessor and multiprocessor tasks and for dedicated, arbitrary and partially arbitrary processors.

11

Zastosowanie algorytmu Rate Monotonic Scheduling do szeregowania zadań w architekturach wieloprocesorowych o topologii hipersześcianu

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 2

141-152

PL

Artykuł stanowi propozycję rozszerzenia obszaru stosowalności popularnego algorytmu szeregujące zadania Rate Monotonic Scheduling (RMS) na przypadek zadań wieloprocesorowych. Dotychczas algorytm RMS wykorzystywany był do szeregowania zbioru niezależnych, wywłaszczalnych i periodycznych zadań przeznaczonych tylko dla jednego procesora. Rosnąca coraz bardziej popularność rozwiązań wieloprocesorowych wymusza dokonanie takiej adaptacji algorytmu RMS, aby algorytm ten nadawał się również do szeregowania zadań wieloprocesorowych. Autor skupił swoją uwagę na architekturach wieloprocesorowych o topologii hipersześcianu. Topologia ta charakteryzuje się bardzo korzystnym stosunkiem liczby połączeń komunikacyjnych pomiędzy poszczególnymi jednostkami obliczeniowymi do maksymalnej długości drogi przesyłu komunikatu, dzięki czemu stanowi jedno z bardziej popularnych rozwiązań wieloprocesorowych. Zaproponowane przez autora zastosowanie klasycznego algorytmu RMS do szeregowania zbioru zadań realizowanych w systemie równoległym o topologii hipersześcianu, polega na transformacji wartości okresów niektórych z zadań. W wyniku rozważanej transformacji wybrane zadania uzyskują identyczne wartości swoich okresów, dzięki czemu mogą zostać połączone w jedno większe tzw. superzadanie, do realizacji którego wymagana jest jednoczesna dostępność wszystkich jednostek obliczeniowych występujących w systemie. Następnie zbiór superzadań może zostać potraktowany tak, jak zbiór zadań jednoprocesorowych, do realizacji których wymagana jest jednostka obliczeniowa specjalnego typu, tzn. taka, która stanowi klaster zbudowany z odpowiedniej liczby procesorów. Jednak z punktu widzenia programu szeregującego superzadania wewnętrzna budowa jednostki obliczeniowej nie jest istotna, a szeregowane superzadania można potraktować w taki sam sposób, w jaki traktuje się zadania jednoprocesorowe, czyli można już bezpośrednio zastosować algorytm RMS. Zaprezentowana w artykule propozycja modyfikacji algorytmu RMS została zilustrowana na wybranym przykładzie szeregowania zadań dla systemu wieloprocesorowego o topologii hipersześcianu czterowymiarowego.

EN

The real-time systems are getting more and more popular. In fact most of contemporary industrail and communication systems could not do without them. The popularity of real-time systems with hard real-time constraints forced the extensive development of task scheduling theory. In the case of real-time systems with hard real-time constraints it does not suffice that the task produces logically correct results but these results must be delivered within their time constraints. In such systems even logically correct results that are delivered with the violation of their time constraints are totally useless. Moreover, the consequences of violation of time constraints can very often be quite severe and can cause the great economic losses and even losses of human lives, e.g. in the case of control systems of nuclear reactors, space ships etc. The main goal of the task scheduling theory is to prove at the stage of the system project that the time constraints for all tasks will always be met under any possible circumstances.In the case of the real-time systems with hard real-time constraints there is very often a necessity of scheduling a set of independent, pre-emptive and periodic tasks. The most popular algorithm for scheduling such set of independent, pre-emptive and periodic tasks is the Rate Monotonic Scheduling algorithm. In the case of Rate Monotonic Scheduling each task is assigned a priority. There are several rules basing on which the priorities are assigned to the tasks and then the tasks are being scheduled. First of all, the shorter the period of task is the higher priority it is assigned. Then, in a given moment, among all the tasks actually in a ready state the one is being executed that has the highest priority. If some task with higher priority enters into the ready state the task being executed is automatically pre-empted and the task with higher priority begins its execution. The pre-empted task can restart its execution only in the case if there is actually no other task with higher priority in the ready state. The Rate Monotonic Scheduling is adequate for scheduling uniprocessor tasks. This author has proposed a new method of adaptation of Rate Monotonic Scheduling theory also for the purpose of scheduling multiprocessor tasks in the multiprocessor architectures of the topology of hypercube. The clue of the method proposed by this author is concatenation of many uniprocessor and multiprocessor tasks that should form one so called supertask. In order to achieve this the periods of some tasks must be transformed, i.e. they must be shortened in such a way that several subsets of tasks of the same value of period should be made. Then each subset of tasks is treated as a uniprocesor supertask and for the set of such supertasks the Rate Monotonic Scheduling algorithm can be used directly. The method developed by this author was illustrated on the example of scheduling set of tasks for the multiprocessor system of the topology of hypercube of dimension 4. The method can be easily extended for the higher dimensions of hypercube multiprocessor architectures.

12

Adaptacja algorytmu Rate Monotonic Scheduling dla potrzeb szeregowania zadań wieloprocesorowych

Gajer M.

Informatyka Teoretyczna i Stosowana

|

2006

|

R. 6, nr 10

167-180

PL

W przypadku systemów czasu rzeczywistego o ostrych ograniczeniach czasowych czas obliczeń jest najcenniejszym zasobem. W celu zagwarantowania dochowania ograniczeń czasowych przez szeregowane zadania rozwinięto metody formalne określane mianem teorii szeregowania zadań. Jednym z najbardziej popularnych algorytmów szeregujących jest Rate Monotonie Scheduling, przeznaczony do szeregowania zadań jednoprocesorowych. Artykuł stanowi propozycję adaptacji algorytmu szeregującego zadania Rate Monotonie Scheduling dla przypadku szeregowania zadań wieloprocesorowych. Istota metody zaproponowanej przez autora polega na binaryzacji okresów szeregowanych zadań i ich łączeniu w większe jednostki zwane super-zadaniami. Zaproponowana przez autora metoda pozwala na wykorzystanie podstawowych twierdzeń związanych z Rate Monotonie Scheduling do dowodzenia szeregowalności również zbiorów zadań wieloprocesorowych.

EN

In the case of hard real-time systems the computational time is the most precious resource that must be very carefully used. The theory of task scheduling delivers formal methods that can guarantee that time constraints are met for all the tasks being scheduled. One of the most popular scheduling algorithm is Rate Monotonic Scheduling that is devoted for the purpose of scheduling uniprocessor tasks. The paper is the proposition of implementation of Rate Monotonic Scheduling also for multiprocessor tasks. The clue of the method that was proposed by this author is the application of binarization of tasks periods and concatenation of tasks into the units of higher rank that was called by this author supertasks. The method allows for the application of Rate Monotonic Scheduling theory to prove the schedulability of the set of multiprocessor tasks.

13

Adaptacja algorytmu Rate Monotonic Scheduling dla potrzeb szeregowania zadań wieloprocesorowych

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2005

|

Vol. 51, z. 3

373--385

PL

Artykuł niniejszy poświęcony został zagadnieniom związanym z szeregowaniem jed-noprocesorowych i wieloprocesorowych zadań dla systemu komputerowego zbudowanego z pewnej liczby procesorów. W systemach czasu rzeczywistego o ostrych ograniczeniach czasowych (ang. hard real-time systems) bardzo często występuje konieczność znalezienia planu szeregowania zbioru niezależnych i wywłaszczalnych zadań periodycznych. Ponadto zwykle już na etapie projektowania systemu należy wykazać w sposób formalny, że ograniczenia czasowe będą zawsze zachowane dla wszystkich zadań. W tym celu w przypadku zadań jednoprocesorowych powszechnie wykorzystywany jest algorytm RMS (ang. Rate Monotonic Scheduling) oraz związane z nim formalne metody dowodzenia szeregowalności zbioru zadań. Autor niniejszego artykułu zaproponował rozszerzenie zakresu stosowalności algorytmu RMS również dla przypadku zadań wieloprocesorowych. Podejście zaproponowane przez autora bazuje na konkatenacji zadań jedno- i wieloprocesorowych oraz na transformacji wartości okresów wybranych zadań. W artykule rozważono zarówno przypadek zbioru zadań przeznaczonych dla procesorów arbitralnych, jak i dedykowanych.

EN

The popularity and ubiquity of real-time systems with hard real-time constraints forced the extensive development of task scheduling theory. In the case of real-time systems with hard real-time constraints it does not suffice that the task produces logically correct results but these results must be delivered within their time constraints. In such systems even logically correct results but delivered with the violation of their time constraints are totally useless. Moreover, the consequences of violation of time constraints can very often be quite severe and can cause the great economic losses and even losses of human lives, e.g. in the case of control systems of nuclear reactors, space ships etc. The main goal of the task scheduling theory is to prove at the stage of the system project that the time constraints for all tasks will always be met under any possible circumstances. In the case of the real-time systems with hard real-time constraints there is very often a necessity of scheduling a set of independent, pre-emptive and periodic tasks. The most popular algorithm for scheduling such set of independent, pre-emptive and periodic tasks is the Rate Monotonic Scheduling algorithm. In the case of Rate Monotonic Scheduling each task is assigned a priority. There are several rules basing on which the priorities are assigned to the tasks and then the tasks are being scheduled. First of all. the shorter the period of task is the higher priority it is assigned. Then, in a given moment, among all the tasks actually in a ready state the one is being executed that has the highest priority. If some task with higher priority enters into the ready state the task being executed is automatically pre-empted and the task with higher priority begins its execution. The pre-empted task can restart its execution only in the case if there is actually no other task with higher priority in the ready state. The Rate Monotonic Scheduling is adequate for scheduling uniprocessor tasks. This author has not known so far any method of adaptation of Rate Monotonic Scheduling theory for the purpose of scheduling multiprocessor tasks. According with this author's knowledge the proposed by himself method of scheduling of the set of uniprocessor and multiprocessor tasks is the first method of the kind and thus has totally pioneer character. The clue of the method proposed by this author is concatenation of uniprocessor and multiprocessor tasks. In order to achieve this the periods of some tasks must be transformed, i.e. they must be shortened in such a way that several subsets of tasks are made. Then each subset of tasks is treated as a uniprocesor task and for the set of such tasks (called by this author supertasks) the Rate Monotonic Scheduling algorithm can be used directly. The method developed by this author was illustrated on the example of scheduling set of tasks for three dedicated processors. The method can be easily extended both for the case of greater number of processors and for the systems with arbitrary processors.

14

Szeregowanie niezależnych, wywłaszczalnych i periodycznych zadań wieloprocesorowych dla trzech procesorów

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2004

|

Vol. 50, z. 2

231-249

PL

W artykule poruszono tematykę szeregowania zbioru niezależnych, wywłaszczalnych i periodycznych zadań wieloprocesorowych przeznaczonych do realizacji w systemie wieloprocesorowym zbudowanym z trzech procesorów. Rozważane zadania niezależne, wywłaszczalne i periodyczne stanowią najbardziej popularną klasę zadań występujących w komputerowych systemach czasu rzeczywistego. Do szeregowania zbioru tego typu zadań wykorzystywany jest najczęściej algorytm RMS (ang. Rate Monotonic Scheduling). Równie często stosowaną techniką w połączeniu z algorytmem RMS jest binaryzacja okresów zadań, mająca na celu skrócenie długości horyzontu czasowego systemu. Dotychczas algorytm RMS stosowany był wyłącznie do szeregowania zadań jednoprocesorowych. Natomiast autorowi artykułu nic nie jest wiadomo o próbach zastosowania algorytmu RMS do szeregowania zadań wieloprocesorowych. Stąd artykuł niniejszy stanowi propozycję takiej modyfikacji algorytmu RMS, która pozwoliłaby na jego zastosowanie również do szeregowania zadań wieloprocesorowych. Zamieszczone w artykule rozważania zostały zilustrowane na przykładzie szeregowania zbioru niezależnych, wywłaszczalnych i periodycznych zadań wieloprocesorowych przeznaczonych dla trzech procesorów. Rozważono zarówno przypadek procesorów dedykowanych, jak i arbitralnych.

EN

At the present moment real-time systems constitute a well-defined and separate class of computer systems. There exist three main factors that make the real-time systems to be totally different from the so-called general-purpose computer systems. First of all in the case of real-time systems the time of computations is the most precious resource, which must be used with a lot of care and attention. Even if the results of computations are correct but they are delivered too late, they are of no value in reat-time system with hard time constraints. Second, any time constraint violation can make the controlled system unstable and thus can cause a catastrophe leading to great economic losses. And last but not least, real-time systems are in most cases integrated very closely with the object being controlled. All these factors cause the necessity of formal analysis of real-time systems before they are put into operations. It must be proved that real-time systems will behave in a deterministic way under any possible conditions and in all the possible scenarios of its work. This necessity of formal analysis of real-time systems has caused the development of task scheduling theory and mathematical methods that allow prove in a formal way that time constraint will be met for each task under any circumstances. The topic of the paper is about scheduling of the set of independent, pre-emptive, and periodic multiprocessor tasks that are to be performed in a multiprocessor system. Such independent, pre-emptive, and periodic tasks constitute the most popular class of the tasks that are to be met in real-time computer systems. In most cases the Rate Monotonic Scheduling (RMS) algorithm is used in order to schedule such set of tasks. The rules of RMS algorithm are as follows: * Each task is assigned a priority * The shorter is the period of task the higher priority is assigned to that task * In every moment only the task with the highest priority from all the tasks that are ready for execution is performed * The task can be pre-emptied by any other task with a higher priority always when such a task enters into a ready state * The pre-emptied task can be resumed only when there is no other task with a higher priority that is ready for the execution Very often a binarisation of the periods of tasks is used together with the RMS algorithm. The purpose of this is to make shorter the time horizon of the scheduled set of tasks. The time horizon is the least common multitude of the periods of all tasks. The binarisation of the periods of tasks transforms the periods in such a way that they are the multitudes of some base period. Only the multitudes that are the powers of two are allowable. According with this author knowledge, the RMS algorithm has been applied only for tasks that are executed on a single processor up till now. This author has found nothing about the trials of implementing the RMS algorithm also for scheduling multiprocessor tasks. The paper is a proposition of new approach in which the RMS algorithm is modifield in such a way that it can also been applied for the purpose of scheduling a set of multiprocessor independent, pre-emptive, and periodic tasks. The proposition of using the RMS algorithm for multiprocessor task scheduling is the following. At the beginning the binarisation of the periods of tasks is performed. Then the tasks are concatenated into so called supertasks in such a way so that the total execution time of the supertasks was as short as possible. In the next step the supertasks are treated as normal uniprocessor tasks, so the RMS algorithm can be directly applied. In the paper both the case of task for dedicated processors and for arbitrary processors is considered. These are illustrated by the scheduling of an example multiprocessor task set.

15

Wybrane zagadnienia szeregowania zadań wieloprocesorowych dla dedykowanych procesorów

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2003

|

Vol. 49, z. 2

163-173

PL

Systemy czasu rzeczywistego stanowią obecnie dobrze określoną i wyodrębnioną grupę systemów komputerowych. W systemach takich najważniejszą sprawą jest dochowywanie nałożonych na realizację zadań ograniczeń czasowych. Spełnienie wymogów czasowych wymusza często konieczność zastosowania w miejsce sekwencyjnych procesorów systemów wieloprocesorowych, które są w stanie dostarczyć wymaganego poziomu pracy obliczeniowej. Jednakże zastosowanie rozwiązań wieloprocesorowych powoduje konieczność rozwiązania niełatwego problemu szeregowania zadań wieloprocesorowych. W artykule po wstępnym wprowadzeniu w problematykę szeregownia zadań wieloprocesorowych, dokonano szczegółowej analizy przypadku szeregowania zadań wieloprocesorowych dla czterech dedykowanych procesorów. Rozważania teoretyczne zostały uzupełnione o wyniki symulacji komputerowych.

EN

In many modern computer systems multiprocessor solutions are more often applied. This concerns especially computer systems that are used in the real-time applications. At present the real-time systems constitute the well-defined class of computer systems. The real-time systems are getting more and more popular in many fields of industry and communication. The real-time systems are used to control telecommunication devices and systems, defense systems, avionics and modern factories. In fact many modern facilities cannot do without them. For example without the real-time systems there would be no nuclear power plants, space ships, jet aircrafts, modern factories with robots etc. The program realized by the real-time computer systems is divided into special tasks performing given functions. In the case of the real-time systems a very important matter is to guarantee that all the task are to be finished before their deadline points. In the case of the hard real-time systems any exceeding task deadline is absolutely intolerable. Such event if happens may lead to uncontrollable behavior of the system, which can cause a disaster, for example an aircraft carsh, a loss of human life etc. To guarantee that the task deadlines will be always met, the task scheduling theory was developed. The main goal of the task scheduling theory is to demonstrate at the system development phase that under all the possible to foreseen circumstances the task deadlines will always be met. There does not exist one universal task scheduling algorithm for all kinds of task. There are separate algorithms for periodic tasks and tasks that are event-triggered. Also there are different algorithms for tasks that are preemptive and for tasks that are not preemptive. There exist also quite different algorithms for tasks that are dedicated for one processor only and for so-called multiprocessor tasks that require for their execution two or more processor at the time. As was earlier mentioned in the case of the real-time systems the most important factor is whether the tasks meet the predefined time constraints. In order to meet the hard time constraints cery often a multiprocessor system is used in stead of a sequential system with only one processor. The multiprocessor system is expected to deliver much more computational power than a single processor system, however, the usage of a multiprocessor system requires simultaneously to solve a non-easy problem of multiprocessor task scheduling. In the paper a brif introduction to the problems of multiprocessor task scheduling is given. Further the case of scheduling a set of independent multiprocessor tasks for four dedicated processors is examined. Multiprocessor systems with four processors are very popular at the present time. For example the Texas Instruments TMS320C80 is a single-chip multiprocessor system composed of four DSP processors. Earlier Texas Instruments offered a personal computer boards with four TMS320C40 processors. The proposed algorithm of multiprocessor task scheduling was called a Divide Uniprocessor Task (DUT) algorithm, because all the tasks dedicated for a single processor are grouped together and then the whole set is divided into two subsets, one of which has the length as close as possible to the execution time of compatible tasks dedicated for orther three processors. In the paper the process of multiprocessor task scheduling is illustrated with examples and the results of computer simulations are also presented.

16

Szeregowanie wieloprocesorowych zadań okresowych dla trzech dedykowanych procesorów

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2002

|

Vol. 48, z. 1

27-51

PL

W ostatnim czasie zaobserwować można było ciągle wzrastającą popularność systemów wieloprocesorowych. Systemy takie są wykorzystywane powszechnie w urządzeniach telekomunikacyjnych, w systemach militarnych, w lotnictwie oraz w nowoczesnych fabrykach, w których zainstalowane zostały roboty przemysłowe. Teoria szeregowania zadań okresowych wywierała i nadal wywiera duży wpływ na rozwój systemów czasu rzeczywistego. Niemniej jednak w klasycznej teorii szeregowania zadań okresowych rozważany jest jedynie przypadek szeregowania zadań jednoprocesorowych - tzn. przyjmuje się, że każde z zadań w danej chwili czasu realizowane jest tylko na jednym procesorze. Mając na uwadze nieustannie wzrastającą popularność rozwiązań wieloprocesorowych, autor niniejszego artykułu opracował własny, oryginalny algorytm szeregowania zadań okresowych, który może zostać zastosowany również w przypadku szeregowania zbioru zadań wieloprocesorowych.

EN

Real-time systems are getting more and more popular. They are used among other to control telecommunication systems, defence systems, avionics, and modern factories with industrial robots. Rate-monotonic scheduling theory has had large impact on the development of real-time systems. Nevertheless in classical rate-monotonic scheduling theory it is assumed that each task is processed on one processor at a time. Motivated by the advance of parallel computing systems this author developed a novel method of implementation of rate-monotonic scheduling theory to the case of periodic multiprocessor tasks.

17

Metodyka testowania systemów pozycjonowania

Małkiński W.

Elektronika : konstrukcje, technologie, zastosowania

|

2002

|

Vol. 43, nr 12

25-28

PL

Przedstawiono metodykę interaktywnego testowania funkcjonalnego i diagnozowania napędów pozycjonujących, sterowanych w otwartych pętlach. Opisana jest również struktura przenośnego stanowiska testowego do konfigurowania i testowania wieloosiowych układów pozycjonowania sterowanych w otwartych pętlach.

EN

The article presents the method of interactive functional testing and diagnosis of multi-axes, open-loop controlled positioning systems. The structure of the portable test stage for configuring and testing of open-loop, multi-axes positioners is also described. The interactive integration of the following problems: the modification of motion parameters, test selection, test execution and test evaluation, makes it possible to determine the optimum movement parameters (such as speed, acceleration, ramp type etc.) for each axis.

18

Szeregowanie wieloprocesorowych zadań okresowych przy użyciu algorytmu RMS połączonego z binaryzacją okresów zadań

Gajer M.

Elektrotechnika i Elektronika

|

2001

|

T. 20, z. 2

88--96

PL

W ostatnim czasie zaobserwować można nieustannie wzrastającą popularność systemów wieloprocesorowych. Systemy takie są wykorzystywane powszechnie w urządzeniach telekomunikacyjnych, w systemach militarnych, w lotnictwie oraz w nowoczesnych fabгykach, w któгych zainstalowane zostały roboty przemysłowe. Teoria szeregowania zadań okresowych wywierała i nadal wywiera duży wpływ nа rozwój systemów czasu rzeczywistego. Jednak w klasycznej teorii szeregowania zadań okresowych rozważany jest jedynie przypadek szeregowania zadań jednoprocesorowych – tzn. przyjmuje się, że każde z zadań w danej chwili czasu realizowane jest jedynie nа jednym procesorze. Będąc zmotywowanym przez wzrastającą popularność rozwiązań wieloprocesorowych, autor niniejszego artykułu opracował własny, oryginalny algorytm szeregowania zadań okresowych, któгy może zostać zastosowany również w przypadku szeregowania zbioru zadań wieloprocesorowych.

EN

Real-time systems are getting more and more popular. They are used among other to control telecommunication systems, defence systems, avionics, and modern factories with industrial robots. Rate-monotonic scheduling theory has had large impact on the development of real-time systems. Nevertheless in classical rate-monotonic scheduling theory it is assumed that each task is processed at a time. Motivated by the advance of parallel computing systems this author developed a novel method of implementation of rate-monotonic scheduling theory to the case of periodic multiprocessor tasks.

19

The implementation of image processing algorithms for the multiprocessor system

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2000

|

Vol. 46, nr 2

255-272

EN

In the paper the usage of the TMS320C80 Texas Instruments multiprocessor chip for the parallel image processing is describe. In the real - time implementations of image processing algorithms the performance time is a critical parameter, so very often multiprocessor solutions must be used. The TMS320C80 is composed of one master RISC processor and four parallel DSP processors specialised for efficient image processing. Because these processors are quite loosely coupled and they communicate through the common memory, it is possible for this system to implement many different types of multiprocessor architecture. In the paper are presented the results obtained during the implementation of the chosen image processing algorithms for the different architectures such as SIMD, MISD and pipeline structure. The attentions is paid to the problem of the matching image processing algorithm to the proper multiprocessor architecture in order to minimise the computation time.

PL

Aplikacje z dziedziny przetwarzania i rozpoznawania obrazów cyfrowych, charakteryzują się dużym zapotrzebowaniem na moc obliczeniową procesorów. Związane jest to z faktem, że te same operacje, takie jak np. filtracja, wyostrzenie obrazu, detekcja krawędzi, wyrównywanie histogramu, czy też binaryzacja obrazu wykonywane muszą być dla każdego z pikseli z osobna, co przy rozmiarach obrazów rzędu kilkuset tysięcy pikseli powoduje znaczne wydłużenie czasu obliczeń. Jeżeli jeszcze obrazy te mają być przetwarzane, analizowane i rozpoznawane w czasie rzeczywistym, (jako przykład można tutaj podać system robota przemysłowego, system radarowy sterujący lotem samolotu itp.) wówczas zapewnienie dostatecznej mocy obliczeniowej staje się jeszcze ważniejszym problemem. Dostępne obecnie na rynku procesory nie zawsze są w stanie dostarczyć odpowiedniej mocy obliczeniowej, zatem konstruktorzy takich systemów coraz częściej sięgają w stronę rozwiązań wieloprocesorowych, w celu przyspieszenia obliczeń. Naprzeciw zapotrzebowaniom na moc obliczeniową ze strony aplikacji związanych z przetwarzaniem i analizą obrazów wyszła firma Texas Instruments, wypuszczając na rynek w 1995 roku pierwszy i do tej pory jedyny system wieloprocesorowy wykonany w postaci pojedyńczego układu scalonego. Istnieje wiele różnych możliwych sposobów zrównoleglenia obliczeń, związanych z przetwarzaniem obrazów. Wybór odpowiedniej konfiguracji systemu wieloprocesorowego jest niezwykle istotną sprawą, ponieważ prawidłowy dobór architektury systemu posiada decydujący wpływ na wartość współczynnika przyśpieszenia obliczeń, w przypadku operacji przetwarzania obrazów, polegających na wykonaniu operacji splotu obrazu z maską filtru, można uzyskać największe wartości współczynnika przyśpieszenia obliczeń, w przypadku zastosowania architektury typu SMD. W tym przypadku obraz dzielony jest na tyle równych części, ile procesorów posiada system, a następnie wszystkie procesory wykonują te same obliczenia dla różnych zestawów danych. Z kolei operacje przetwarzania obrazów, składające się z wielu etapów, mogą zostać najefektywniej zrównoleglone poprzez zastosowanie wieloprocesorowych struktur potokowych, gdzie każdy z etapów przetwarzania obrazu wykonywany jest przez odrębną stację potoku.

20

Wieloprocesorowa architektura procesorów sygnałowych dla potrzeb realizacji średniego poziomu przetwarzania obrazów

Wiatr K.

Elektrotechnika i Elektronika

|

2000

|

T. 19, z. 2

82--89

PL

Przedmiotem prac badawczych autora są systemy wizyjne przeznaczone dla potrzeb systemów czasu rzeczywistego, w których wymagana jest bardzo szybka realizacja złożonych algorytmów przetwarzania. Ponieważ autor dysponuje wysoko wydajną architekturą potokową specjalizowanych procesorów sprzętowych do wstępnego przetwarzania obrazów, w sferze referowanych badań skupiono się na realizacji zadań średniego i wysokiego poziomu przetwarzania obrazów. W szczególności podjęto próbę ich implementacji w procesorach sygnałowych. Biorąc pod uwagę wcześniejsze doświadczenia autora w zakresie szybkiej realizacji zadań przetwarzania obrazu, próbowano przyspieszyć pracę jednostek obliczeniowych (procesory sygnałowe) oraz transmisję danych wizyjnych pomiędzy nimi (architektura wieloprocesorowa). W wyniku tych prac, opracowano moduł wieloprocesorowy zbudowany w oparciu o procesory sygnałowe DSP56001 firmy Motorola oraz zestaw krosownic 74ABT16863, służących do przełączania danych wizyjnych podlegających przetwarzaniu pomiędzy tymi procesorami.

EN

The author's research work concerns the real-time vision systems equiped in high speed algorithm realisation. In the past author made the high power computation pipelined architecture of hardware specialised processors for image preprocessing. Presented research concerns the middle and high level image processing. In particular the author implemented these operations in the digital signal processors. The author designed high speed realisation of image processing with accelerating processors work (digital signal processors) and high speed data vision transmission between them (multiprocessors architecture). In result of these works made multiprocessors unit used Motorola digital signal processors DSP 5 6001 and crossbar switch matrix used 74A B Tl 6863 chips for switched data vision between them processors.