SIEĆ PRZETASOWANA (perfect shuffle)

n=2^k

i= 0,1,...n-1

i 2i mod(n-1) - łączą tasowania

2i 2i+1 - łączą wymiany

c=3

p=(3n-4)/2=)(n)

d=2 logn-1=0(logn)

• transpozycja macierzy

• mnożenie macierzy

• sortowanie

• algorytmy grafowe

HIPERSZEŚCIAN (n sześcian, ang. hypercube, n-cube)

n=2^k

k sąsiadów

0,1...,n-1 - wymiar hipersześcianu

00000

00100 połączone, bo różnią się 1 bitem

01100

2 3

0 1

10 11

8 9

14 15 7

12 13

6

4 5

k=0 •

k=1 • • c=logn -mnożenie macierzy

k=2 d=nlogn/2=0(nlogn) -sortowanie

d=logn=0(logn) -szybka transformata

-algorytmy grafowe

k=3 -obliczanie wartości wektorów

DYNAMICZNE SIECI POŁĄCZEŃ

Połączenia są rekonfikurowalne przez wykorzystanie

Demultiplekser Multiplekser

p-wyjściowy q-wejściowy

1

1

2 2

p q

sieć jednostopniowa

0(n²)

bardzo kosztowne

p,q<n

sieć recyrkulacyjna

SPOSOBY POŁĄCZEŃ

PROCESORY - PAMIĘĆ WSPÓLNA

System ze wspólna magistralą (common bus; time-shared bus)

• • • • • •

• • • • • •

• mała zależność funkcjonalna

• mały koszt

• łatwość rekonfiguracji

• konieczność zapewnienia dużej niezawodności

• „wąskie gardło” systemu

Sposoby rozwiązywania konfliktów

• metoda priorytetów statycznych - każdy układ w systemie ma swój priorytet

arbitrator - steruje dostępem magistrali

łańcuch urządzeń

• metoda priorytetów dynamicznych

• metoda stałego kwantu czasu

• 
  
  
  
  
  
  
  metoda kolejowa FIFO

SYSTEMY Z PRZEŁĄCZNICĄ KRZYŻOWĄ (crossbar switch)

.............

• • •

- duża złożoność funkcjonalna

• • •

- duża przepustowość

....... ................ ........................ ...........

• • • - trudność rozbudowy

• • •

0

1

2

3

4

5

6

7

Jednostka we/wy

Moduł pamięci

Moduł pamięci

Jednostka we/wy

procesor

procesor

Moduł pamięci

Moduł pamięci

Moduł pamięci

procesor

procesor

Jednostki we/wy

Jednostki we/wy

---