Wyniki wyszukiwania - Biblioteka Nauki

1

The Parallel Image Processing on the Single-chip Multiprocessor System

100%

Gajer M.

|

2001

|

tom vol. 49, nr 1

81-99

EN

In the paper the usage of the Texas Instruments multiprocessor chip the TMS320C80 for the parallel image processing is described. 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 to implement for this system many different types of multiprocessor architecture. In the paper the results obtained during the implementation of the chosen image processing algorithms for the different architectures such as SIMD, MIMD, MISD and pipeline structure are presented. The attention is paid to the problem of the matching image processing algorithm to the proper multiprocessor architecture in order to minimise the computation time.

2

Job scheduling in multiprocessor system - demonstration tool

75%

Małolepszy A. , Janicki K.

|

1998

|

tom Vol. 6, nr 1

51-60

EN

The paper describes a program whose goal is to present various algorithms of job scheduling in multiprocessor systems. The program offers a clear presentation of selected deterministic scheduling algorithms. It. enables the user to obtain a job schedule for a given set of jobs on a certain numbers of processors in the graphic form of Gantt's diagram. Each algorithm is provided with a description of the both problem and successive algorithm steps.

3

Adaptacja algorytmu Rate Monotonic Scheduling dla potrzeb szeregowania zadań wieloprocesorowych

75%

Gajer M.

|

2006

|

tom 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.

4

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

75%

Szczerbiński Z. , Steinborn K.

|

2009

|

tom 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.

5

Szeregowanie zadań periodycznych w heterogenicznych systemach wieloprocesorowych

75%

Gajer M.

|

2012

|

tom 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.

6

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

75%

Handzel Z. , Gajer M.

|

2013

|

tom 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.

7

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

63%

Gajer M.

|

2010

|

tom 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.

8

Zastosowanie binaryzacji okresów zadań w systemach wieloprocesorowych

63%

Gajer M.

|

2006

|

tom 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.

9

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

63%

Gajer M.

|

2006

|

tom 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.