Wyniki wyszukiwania - BazTech

1

Towards the boundary between easy and hard control problems in multicast Clos networks

Obszarski P., Jastrzębski A., Kubale M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2015

|

Vol. 63, nr 3

739--744

EN

In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially solvable instances as well as a number of NP-complete cases. Our results warn of possible troubles arising in the control of Clos networks even if they are composed of small-size switches in outer stages. This is in sharp contrast to classical unicast Clos networks for which all the control problems are polynomially solvable.

2

Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi

Obszarski P., Kubale M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2009

|

T. 13, z. 2

513-519

PL

W artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.

EN

In this article we consider the problem of scheduling unit processing time multiprocessor tasks on dedicated processors with repetition and availability constraints. W present collected results of complexity of this problem for different types of instances and scheduling criteria. To describe the problem we use the model of edge coloring of hypergraphs.

3

Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych

Obszarski P.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 13

449-456

PL

Problem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem NP-trudnym. W tym artykule podejmujemy próbę zastosowania i oceny różnych algorytmów heurystycznych dla kolorowania hipergrafów. Rozważania ogólne poparte są doświadczeniami komputerowymi. Testy zaimplementowanych algorytmów przeprowadzono na hipergrafach losowych.

EN

Problem of scheduling multiprocessor tasks on dedicated processors can be easily presented with hypergraph edge coloring problem. By a hypergraph we mean a generalization of a graph in which edges may contain any number of vertices. This model can be used in many theoretical and practical applications. Hypergraph edge coloring problem is generalization of graph edge coloring so it is NP-hard. In this paper we present and try to judge differ-ent types of heuristic algorithms for hypergraph edge coloring. General considerations are supported with com-puter experiment. Tests were conducted on random hypergraphs.