Wyniki wyszukiwania - BazTech

1

Szeregowanie zadań elastycznych

Błażewicz J., Kovalyov M., Machowiak M., Trystram D., Węglarz J.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 134

67-79

PL

Przedstawiono tutaj problem szeregowania n niezależnych zadań w systemie procesorów równoległych. Zadania są elastyczne, tj. zadanie może być wykonywane przez kilka procesorów jednocześnie oraz prędkość wykonywania zadania jest nieliniową funkcją od ilości procesorów przydzielonych do niego. Całkowita liczba procesorów w systemie wynosi m i jest to górna granica liczby procesorów, które mogą być używane przez wszystkie zadania w tym samym czasie. Dodatkowym założeniem jest podzielność zadań oraz możliwość zmiany liczby procesorów przydzielonych do zadania w trakcie jego wykonywania. Celem jest znalezienie uszeregowania, dla którego czas zakończenia wszystkich zadań jest najkrótszy z możliwych. Prezentowany jest prosty algorytm o złożoności 0(n), rozwiązujący ten problem w przypadku, kiedy wszystkie funkcje prędkości wykonywania są wypukłe. Jeżeli funkcje te są wszystkie wklęsłe, przedstawiono algorytm pakowania prostokątów (PACK), który rozwiązuje ten problem w czasie wielomianowym.

EN

The problem of optimal scheduling n independent tasks on a parallel processor system is studied. The tasks are malleable, i.e. a task may be executed by several processors simultaneously and the processing speed of a task is a non-linear function of the number of processors allotted to it. The total number of processors is m and it is an upper bound on the number of processors that can be used by all the tasks simultaneously. It is assumed that the tasks are preemptable and the number of processors allotted to one task may change during its execution. The objective is to find a schedule for which the makespan, is minimized. An 0(n) algorithm is presented to solve this problem when all the processing speed functions are convex. If these functions are all concave the rectangles packing (PACK) algorithm is presented, which solves the problem in polynomial time.

2

Suboptimal approaches to scheduling malleable tasks

Błażewicz J., Machowiak M., Mounié G., Trystram D.

Computational Methods in Science and Technology

|

2000

|

Vol. 6

25-40

EN

In the paper, the problem of scheduling a set of n malleable tasks on m parallel computers is considered. The tasks may be executed by several processors simultaneously and the processing speed of a task is a function of the number of processors alloted. The problem is motivated by real-life applications of parallel computer systems in scientific computing of highly parallelizable tasks. Starting from the continuous version of the problem (i. e. where the tasks may require a fractional part of the resources), we propose a general approximation algorithm with a performance guarantee equal to 2. Then, some improvements are derived that lead to a very good average behavior of the scheduling algorithm.

3

List scheduling of general task graphs under LogP model

Kalinowski T., Kort I., Trystram D.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

1998

|

nr 865

3-18

EN

The aim of this report is to assess the applicability of the list scheduling approach to the LogP model. More precisely, we present two adaptations of the Earliest Task First (ETF) heuristic. Then, we establish an upper bound on list schedules under LogP model. Finally, we present an extensive experimental study for different graph classes and model instances.

PL

Celem pracy jest ocena przydatności algorytmów listowych dla modelu LogP. W raporcie przedstawiono rozszerzenia algorytmu ETF, w których uwzględniono wymagania nakładane przez ten model. Ustalono wartość górnego ograniczenia na długość obliczonego uszeregowania oraz zaprezentowano wyniki symulacyjne dla różnych klas grafów programu i parametrów systemu.