Treści programowe

Wykłady

1. Podstawowe typy architektur i pojęcia z nimi związane.
2. Problemy w implementacji architektury potokowej i superskalarnej; metody ich rozwiązywania i wynikające z nich podukłady mikroprocesorów.
3. Charakterystyka architektury wybranych współczesnych procesorów wykorzystywanych w urządzeniach stacjonarnych, mobilnych oraz superkomputerach.
4. Komunikacja pomiędzy procesorem, pamięcią a urządzeniami wejścia/wyjścia.
5. Charakterystyka architektury wybranych komputerów stacjonarnych oraz urządzeń mobilnych.
6. Współczesne pamięci operacyjne / podstawowe parametry statyczne i dynamiczne.
7. Typy magistral i ich parametry.
8. Benchmarki.
9. Charakterystyka mikrokomputerów jednoukładowych i ich przeznaczenie.

Ćwiczenia

1. Analiza szybkości wykonywania operacji stało- i zmiennoprzecinkowych.

2. Analiza cyklu rozkazowego i potoku rozkazowego w jednym rdzeniu procesora jedno i wielordzeniowego.

3. Komunikacja z pamięcią oraz z urządzeniami wejścia/wyjścia oraz obsługa przerwań.

4. Analiza działania wybranych instrukcji i przykładowych programów w asemblerze wybranego procesora.

5. Tworzenie przykładowych programów w asemblerze z wykorzystaniem instrukcji warunkowych i pętli.

6. Oprogramowanie układu sterującego dla przykładowego zadania (np. sterowanie światłami na skrzyżowaniu, obsługą żądań przywołania windy itp.).

Organizacja

1. Jeśli ktoś jest zainteresowany, proponuję włączyć kamerę - na tej podstawie sprawdzam obecność
2. Aktywność generuje plusy
3. Wyniki, rezultaty z ćwiczeń proszę wklejać na czat
4. Zaliczenie przedmiotu - kolokwium lub projekt
   1. Jeśli kolokwium to odbędzie się na przedostatnich zajęciach (zakres ściśle powiązany ze skryptem)
   2. Jeśli projekt, to prezentacja na ostatnich zajęciach - najprawdopodobniej stworzenie symulatora, powiązanego z tematyką zajęć.
5. Zajęcia mają formułę warsztatów
   1. Trochę omawiamy temat
   2. Przeklejamy przykładowe programy lub programujemy je
6. W dowolnym momencie proszę pytać o cokolwiek co jest związane z tematyką zajęć

Wstęp

Kilka problemów związanych z architekturą procesora i organizacją systemu komputerowego:

1. Reordering instrukcji: Procesory mogą zmieniać kolejność wykonywania instrukcji, aby zoptymalizować wydajność. Może to prowadzić do problemów związanych z synchronizacją wątków i niezdefiniowanym zachowaniem. Aby temu zapobiec, można użyć odpowiednich metod synchronizacji, takich jak muteksy, blokady czy bariery pamięci.

2. Efekty związane z pamięcią cache: Dostęp do pamięci ma istotny wpływ na wydajność programu. Wysokiej wydajności algorytmy powinny być zaprojektowane z uwzględnieniem hierarchii pamięci, tak aby minimalizować opóźnienia związane z odwołaniami do pamięci. Można to osiągnąć, stosując techniki optymalizacji, takie jak blokowanie, użycie pamięci lokalnej czy cache-oblivious algorithms.

3. Równoczesność i współbieżność: Wykorzystanie wielowątkowości i wielordzeniowości procesorów może prowadzić do problemów związanych z dostępem do wspólnych zasobów, takich jak dane czy urządzenia wejścia/wyjścia. Aby zapewnić poprawną współpracę wątków, można stosować mechanizmy synchronizacji (muteksy, semafory, blokady) oraz techniki programowania równoległego, takie jak zadania, przetwarzanie równoległe czy potoki.

4. Wydajność arytmetyki zmiennoprzecinkowej: Obliczenia zmiennoprzecinkowe różnią się wydajnością w zależności od architektury procesora. Aby uzyskać najlepszą wydajność, można stosować optymalizacje specyficzne dla danego procesora, takie jak wektoryzacja, instrukcje SIMD czy optymalizacja obliczeń matematycznych.

5. Obsługa błędów sprzętowych: Błędy sprzętowe, takie jak błędy parzystości czy uszkodzenia pamięci, mogą wpłynąć na poprawność działania programu. Można zastosować techniki wykrywania i naprawy błędów, takie jak korekcja błędów pamięci czy sprawdzanie parzystości, aby zminimalizować ryzyko wprowadzenia błędów przez sprzęt.

Aby uniknąć tych problemów i zapewnić poprawne działanie programu, ważne jest zapoznanie się z architekturą procesora, na którym ma być uruchomiony program, oraz zastosowanie odpowiednich technik programowania i optymalizacji. Oto kilka dodatkowych wskazówek:

6. Endianness: Kolejność bajtów w reprezentacji liczb wielobajtowych (little-endian lub big-endian) różni się między różnymi architekturami procesorów.

7. Wydajność operacji wejścia/wyjścia: Operacje wejścia/wyjścia mają znaczący wpływ na wydajność aplikacji. W przypadku programów wymagających intensywnego przepływu danych, należy zastosować techniki buforowania, asynchronicznych operacji wejścia/wyjścia oraz optymalizować użycie systemów plików i urządzeń wejścia/wyjścia.

8. Granice stronicowania: Dostęp do pamięci może być niejednorodny z powodu granic stronicowania. Aby uniknąć opóźnień związanych z przenoszeniem danych między stronami pamięci, można zastosować techniki takie jak wyrównywanie stronicowania (page alignment), stosowanie dużych stron (huge pages) czy ograniczenie fragmentacji pamięci.

9. Architektura NUMA (Non-Uniform Memory Access): W przypadku systemów wieloprocesorowych z architekturą NUMA, dostęp do pamięci może być wolniejszy dla niektórych rdzeni procesora. Aby zoptymalizować wydajność programów na takich systemach, można stosować techniki takie jak lokalność danych, afinitet rdzeni czy specjalne funkcje alokacji pamięci, takie jak numa_alloc_onnode i numa_bind.

10. Wsparcie dla instrukcji specyficznych dla procesora: Niektóre procesory mają instrukcje, które pozwalają na bardziej efektywne wykonanie określonych operacji. Można skorzystać z tych instrukcji, pisząc kod w asemblerze lub korzystając z bibliotek, które wykorzystują te instrukcje, takie jak biblioteki matematyczne czy algorytmiczne.

Aby uniknąć problemów związanych z architekturą procesora i organizacją systemu komputerowego, ważne jest, aby programować z uwzględnieniem tych zagadnień. Dobrym podejściem jest też korzystanie z bibliotek i narzędzi, które już zostały zoptymalizowane pod kątem różnych architektur i systemów.

Ref:

• Measuring Jitter and Latency
• logic gate simulator
• WSL !!
• VirtualBox
• Mingw-w64
• The microarchitecture of Intel, AMD, and VIA CPUs

• Architektura systoliczna - np. Edge TPU
• Google Coral Edge TPU explained in depth
• Cell (PS3) - PowerPC (PPE) + 7 x „Synergistic Processing Elements” (SPEs) PlayStation 3
• Hardware for Deep Learning
• Unlocking the Secrets of GPU Architecture
• A CPU is a compiler

Reprezentacja liczb

System dziesiętny

Liczba 13910 jest zapisana w systemie dziesiętnym, co oznacza, że każda pozycja odpowiada potędze liczby 10. System pozycyjny to sposób zapisu liczb, w którym wartość liczby zależy od wartości cyfr i ich pozycji. W systemie wagowym wartość liczby jest sumą iloczynów cyfr i wag pozycji, gdzie wagi pozycji są potęgami podstawy systemu.

Liczba 13910 z rozbiciem na wagi poszczególnych pozycji:

1 * 10^4 + 
3 * 10^3 + 
9 * 10^2 + 
1 * 10^1 + 
0 * 10^0 =

10000 + 3000 + 900 + 10 + 0 = 13910

System binarny

Konwersja liczby 13910 na zapis binarny:

13910 : 2 = 6955 (reszta: 0)
6955  : 2 = 3477 (reszta: 1)
3477  : 2 = 1738 (reszta: 1)
1738  : 2 = 869  (reszta: 0)
869   : 2 = 434  (reszta: 1)
434   : 2 = 217  (reszta: 0)
217   : 2 = 108  (reszta: 1)
108   : 2 = 54   (reszta: 0)
54    : 2 = 27   (reszta: 0)
27    : 2 = 13   (reszta: 1)
13    : 2 = 6    (reszta: 1)
6     : 2 = 3    (reszta: 0)
3     : 2 = 1    (reszta: 1)
1     : 2 = 0    (reszta: 1)

Liczba binarna: 11 0110 0101 0110

Ćwiczenie

Zamienić na liczbę w notacji binarnej za pomocą powyższej metody:

• 19
• 1977

Naturalny kod binarny to sposób zapisu liczb, w którym wartość liczby jest sumą iloczynów cyfr i wag pozycji, gdzie wagi pozycji są potęgami liczby 2.

Liczba 1011 0101 z rozbiciem na wagi poszczególnych pozycji:

1 * 2^7 + 
0 * 2^6 + 
1 * 2^5 + 
1 * 2^4 + 
0 * 2^3 + 
1 * 2^2 + 
0 * 2^1 + 
1 * 2^0 = 

128 + 32 + 16 + 4 + 1 = 181

System szesnastkowy

Aby przekonwertować liczbę binarną 1011011100101101 na szesnastkowy, można ją podzielić na grupy po 4 bity i przypisać im wartości szesnastkowe:

1011 0111 0010 1101
   B    7    2    D

Liczba szesnastkowa: B72D

Przechowywanie danych w komputerach

Narysować pamięć

Dane w komputerze są przechowywane w postaci binarnej, czyli za pomocą bitów (0 i 1). System binarny został wybrany ze względu na prostotę realizacji elektronicznej (wysokie i niskie napięcie) oraz łatwość przetwarzania informacji.

Rejestr to mały obszar pamięci w procesorze, używany do przechowywania wartości, które są obecnie przetwarzane. Słowo to ciąg bitów, który odpowiada długości rejestru lub jednostki przetwarzania danych.

Załóżmy, że mamy rejestr 8-bitowy. Aby zapisać wartość 139 (10001011) w rejestrze, wystarczy ustawić bity na odpowiednie wartości: 10001011

Ile bitów jest potrzebnych na zapisanie liczby 139, 255, 269, 513?

139: 8 bitów (10001011)
255: 8 bitów (11111111)
269: 9 bitów (100001101)
513: 10 bitów (1000000001)

Liczba potrzebnych bitów do zapisania każdej z tych liczb zależy od ich wartości w postaci binarnej. Aby określić minimalną ilość bitów potrzebną do zapisania danej liczby, można zastosować funkcję logarytmu dwójkowego (lub log2), a następnie zaokrąglić wynik w górę do najbliższej liczby całkowitej.

1

math.ceil( math.log2(269) )

Co to jest rejestr?

Nadmiar i niedomiar

Ćwiczenie

• Czy wynik operacji mieści się w 8-bitowym rejestrze? (nadmiar czy niedomiar)
• Ile bitów potrzeba do reprezentacji wyniku?

1. Dodawanie:

    A = 127 (01111111)
    B = 4 (00000100)
    A + B = 131 (10000011)
   

2. Dodawanie:

    A = 139 (10001011)
    B = 147 (10010011)
    A + B = 286 (1 00010010) 
    efekt nadmiaru, wynik nie mieści się w 8-bitowym rejestrze.
   

W drugim przypadku mamy do czynienia z nadmiarem, co oznacza, że wynik przekracza maksymalną wartość, która może być przechowywana w 8-bitowym rejestrze (255).

3. Odejmowanie:

    A = 115 (01110011)
    B = 5 (00000101)
    C = A - B = 110 (01101110)
   

4. Odejmowanie:

    A = 129 (10000001)
    B = 167 (10100111)
    C = A - B = -38 (11011010)
    efekt niedomiaru, ponieważ wynik jest liczbą ujemną.
   

Liczby ujemne

1. Z bitem znaku
2. U2

Aby zapisać liczbę -2 w 8-bitowym rejestrze, używamy kodu U2 (Uzupełnienie do 2):

-2 = 11111110

Przykład dla liczby 10110101:

1. Jako liczba dodatnia:

    1 * 2^7 + 
    0 * 2^6 + 
    1 * 2^5 + 
    1 * 2^4 + 
    0 * 2^3 + 
    1 * 2^2 + 
    0 * 2^1 + 
    1 * 2^0 = 
   
    128 + 32 + 16 + 4 + 1 = 181
   

2. Jako liczba ujemna (w kodzie U2):

   ~1011 0101 + 1 = 
    0100 1010 + 1 = 0100 1011
   
    co daje: 64 + 8 + 2 + 1 = 75, 
    więc liczba to -75.
   

Interpretacja liczby zależy od kontekstu. W przypadku liczb ujemnych często stosowany jest kod U2.

Kod U2

Uzupełnienie do 2, to metoda reprezentacji liczb całkowitych, zarówno dodatnich, jak i ujemnych, w systemie binarnym. W kodzie U2 liczby dodatnie są reprezentowane tak samo jak w naturalnym kodzie binarnym, natomiast liczby ujemne są reprezentowane jako dopełnienie do 2 liczby bezwzględnej.

Obliczanie reprezentację liczby ujemnej w kodzie U2:

1. Przekształć wartość bezwzględną liczby ujemnej na postać binarną.
2. Odwróć bity (zmień 0 na 1 i 1 na 0).
3. Dodaj 1 do wyniku.

Przykłady:

1. Przykład dla liczby -3:

   1. Wartość bezwzględna: 3 (w binarnym: 0000 0011)
   2. Odwrócenie bitów: 1111 1100
   3. Dodanie 1: 1111 1100 + 1 = 1111 1101
   
   Kod U2 dla liczby -3: 1111 1101
   

2. Przykład dla liczby -7:

   1. Wartość bezwzględna: 7 (w binarnym: 0000 0111)
   2. Odwrócenie bitów: 1111 1000
   3. Dodanie 1: 1111 1000 + 1 = 1111 1001
   
   Kod U2 dla liczby -7: 1111 1001
   

Kod U2 jest często stosowany w komputerach, ponieważ pozwala na wykonywanie operacji dodawania i odejmowania przy użyciu tego samego sprzętu, niezależnie od znaku liczb.

Ćwiczenie

1. -7
2. -117

Liczby rzeczywiste

11 i 5/16 = 11.3125

Liczba 11 w postaci binarnej to 1011.

5/16 jako ułamek binarny to 0.0101 ponieważ

 1 * (1/2)^3 + 
 0 * (1/2)^4 + 
 1 * (1/2)^5)

0.3125 * 2 = 0.625 -> 0
0.625  * 2 = 1.25  -> 1
0.25   * 2 = 0.5   -> 0
0.5    * 2 = 1     -> 1

Liczba 11 i 5/16 w postaci binarnej to: 1011.0101

Potrzebujemy 8 bitów na zapisanie tej liczby. Można zapisać ją w rejestrze jako liczba stałoprzecinkowa (zakładając, że przecinek jest zawsze pomiędzy bitami 3 i 4) lub używając notacji zmiennoprzecinkowej, która pozwala na zapisanie liczby z określoną precyzją i zakresem.

Zamiana na postać binarną

Aby przekształcić liczbę dziesiętną 10.75 na liczbę binarną, należy przekształcić osobno jej część całkowitą i część ułamkową.

1. Konwersja części całkowitej:

    Liczba całkowita: 10
    Postępujemy według metody dzielenia przez 2:
   
    10 / 2 = 5, reszta: 0
     5 / 2 = 2, reszta: 1
     2 / 2 = 1, reszta: 0
     1 / 2 = 0, reszta: 1
   
    Czytamy reszty od dołu do góry: 1010
   

2. Konwersja części ułamkowej:

    Liczba ułamkowa: 0.75
    Postępujemy według metody mnożenia przez 2:
    0.75 * 2 = 1.5 (zapisujemy cyfrę 1)
    0.50 * 2 = 1.0 (zapisujemy cyfrę 1)
   
    Czytam od góry do dołu: 11
   

Teraz, aby uzyskać postać binarną liczby 10.75, łączymy część całkowitą (1010) i część ułamkową (11) za pomocą przecinka binarnego: 1010.11

Stąd wynika, że liczba dziesiętna 10.75 jest równa liczbie binarnej 1010.11

Uwaga Podczas konwersji liczby ułamkowej dziesiętnej na liczbę binarną za pomocą metody mnożenia przez 2, należy zakończyć mnożenie w jednym z następujących przypadków:

1. Gdy wartość ułamkowa po mnożeniu wynosi dokładnie 0. Wtedy wszystkie kolejne mnożenia również będą dawały 0, a kolejne cyfry binarne po przecinku będą się składały wyłącznie z zer. W takiej sytuacji nie > ma potrzeby kontynuować obliczeń.

2. Gdy osiągniesz żądaną precyzję. W praktyce, liczby binarne używane w komputerach mają ograniczoną precyzję (np. w przypadku liczb zmiennoprzecinkowych w standardzie IEEE-754). W związku z tym możemy > zakończyć mnożenie po osiągnięciu określonej liczby cyfr binarnych po przecinku.

3. Gdy zauważysz cykliczne powtarzanie się wzoru cyfr. W niektórych przypadkach, liczby ułamkowe dziesiętne mają nieskończoną reprezentację binarną, która powtarza się cyklicznie. Kiedy zauważysz taki wzór, > możesz zakończyć mnożenie i zaokrąglić wynik do żądanej precyzji.

Należy pamiętać, że niektóre liczby ułamkowe dziesiętne mają nieskończoną reprezentację binarną, która nie wykazuje cyklicznego powtarzania się wzoru. W takich przypadkach, można zakończyć mnożenie, gdy > osiągnięta zostanie żądana precyzja, biorąc pod uwagę ograniczenia sprzętowe lub wymagania dotyczące zaokrąglenia.

Przykłady

1. Liczba dziesiętna 0.5:

    0.5 * 2 = 1.0 (zapisujemy cyfrę 1)
    Binarnie: 0.1
   

2. Liczba dziesiętna 0.25:

    0.25 * 2 = 0.5 (zapisujemy cyfrę 0)
    0.5 * 2 = 1.0 (zapisujemy cyfrę 1)
    Binarnie: 0.01
   

3. Liczba dziesiętna 0.625:

    0.625 * 2 = 1.25 (zapisujemy cyfrę 1)
    0.25 * 2 = 0.5 (zapisujemy cyfrę 0)
    0.5 * 2 = 1.0 (zapisujemy cyfrę 1)
    Binarnie: 0.101
   

4. Liczba dziesiętna 0.375:

    0.375 * 2 = 0.75 (zapisujemy cyfrę 0)
    0.75 * 2 = 1.5 (zapisujemy cyfrę 1)
    0.5 * 2 = 1.0 (zapisujemy cyfrę 1)
    Binarnie: 0.011
   

5. Liczba dziesiętna 0.1977:

    0.1977 * 2 = 0.3954 -> (0.0)
    0.3954 * 2 = 0.7908 -> (0.00)
    0.7908 * 2 = 1.5816 -> (0.001)
    0.5816 * 2 = 1.1632 -> (0.0011)
    0.1632 * 2 = 0.3264 -> (0.00110)
    0.3264 * 2 = 0.6528 -> (0.001100)
    0.6528 * 2 = 1.3056 -> (0.0011001)
   

Warto zauważyć, że niektóre liczby ułamkowe w systemie dziesiętnym nie mają dokładnej reprezentacji w systemie binarnym.

6. Liczba dziesiętna 0.1:

    0.1 * 2 = 0.2 (zapisujemy cyfrę 0)
    0.2 * 2 = 0.4 (zapisujemy cyfrę 0)
    0.4 * 2 = 0.8 (zapisujemy cyfrę 0)
    0.8 * 2 = 1.6 (zapisujemy cyfrę 1)
    0.6 * 2 = 1.2 (zapisujemy cyfrę 1)
    0.2 * 2 = 0.4 (zapisujemy cyfrę 0)
    ...
    Binarnie: 0.0001100110011... (cyfry się powtarzają)
   

W takich przypadkach reprezentacja binarna będzie nieskończoną liczbą cyfr po przecinku i musi zostać zaokrąglona, aby zmieścić się w określonym formacie, takim jak standard IEEE-754.

Notacja zmiennoprzecinkowa

W komputerach najczęściej stosowaną notacją zmiennoprzecinkową jest standard IEEE-754. Standard ten definiuje formaty reprezentacji liczb zmiennoprzecinkowych, takie jak pojedyncza precyzja (32 bity) i podwójna precyzja (64 bity). Standard IEEE-754 pozwala na zapisanie liczb z określoną precyzją, zakresem i specjalnymi wartościami (takimi jak nieskończoność i NaN). Na niektórych platformach dostępny jest typ half-float (NVidia CUDA) o połowicznej precyzji (16 bitów)

Reprezentacja liczby zmiennoprzecinkowej w standardzie IEEE-754 składa się z trzech części:

1. Znak (Sign) - jeden bit, który reprezentuje znak liczby (0 - dodatnia, 1 - ujemna).
2. Wykładnik (Exponent) - ciąg bitów reprezentujący wykładnik liczby, przesunięty o wartość stałą (bias). Dla formatu pojedynczej precyzji przesunięcie wynosi 127, a dla podwójnej precyzji wynosi 1023.
3. Mantysa (Significand) - ciąg bitów reprezentujący wartość liczby znormalizowanej, ale bez pierwszego bitu (1), który jest zawsze niejawny (chyba że liczba jest denormalizowana).

Tworzenie reprezentacji binarnej liczby zmiennoprzecinkowej w standardzie IEEE-754:

1. Określ znak liczby (0 dla dodatniej, 1 dla ujemnej).
2. Zamienić część dziesiętną oraz ułamkową na postać binarną.
3. Przekształć liczbę na postać znormalizowaną w notacji naukowej (1.x * 2^n).
4. Oblicz wykładnik, dodając przesunięcie (bias) do n (wykładnik notacji naukowej).
5. Przekształć mantysę na postać binarną, pomijając pierwszy bit (1).
6. Złożyć reprezentację z części znakowej, wykładnika i mantysy.

Przykład:

Chcemy zapisać liczbę 10.75 jako liczbę zmiennoprzecinkową w standardzie IEEE-754 (pojedyncza precyzja).

1. Liczba jest dodatnia, więc znak to 0.
2. Postać binarną: 10.75 = 1010.11
3. Postać znormalizowana: 1.01011 * 2^3
4. Wykładnik: 3 + 127 (bias) = 130, w postaci binarnej: 10000010
5. Mantysa (bez pierwszego bitu): 0101100… (w sumie 23 bity)
6. Składamy reprezentację: 0 10000010 01011000000000000000000

Reprezentacja liczby 10.75 w standardzie IEEE-754 (pojedyncza precyzja) to:

32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9  8  7  6  5  4  3  2  1
0  1  0  0  0  0  0  1  0  0  1  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

1 * 2^3 * 1.34375 = 10.75

Ref:

• http://www.cburch.com/books/float/
• Float Toy
• What Every Computer Scientist Should Know About Floating-Point Arithmetic

Kolejność bajtów

Przykład reprezentacji liczby 32-bitowej (4-bajtowej) w różnych kolejnościach bajtów:

Wartość: 0x12345678

• Little-endian: 78 56 34 12
• Big-endian: 12 34 56 78

Poniżej znajduje się przykładowy program w C++, który demonstruje różne kolejności bajtów:

Lab_01:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <cstdint>

union EndianTest {
    uint32_t i;
    uint8_t c[4];
};

int main() {
    EndianTest test;
    test.i = 0x12345678;

    std::cout << "System ma następującą kolejność bajtów: ";
    if (test.c[0] == 0x78 && test.c[1] == 0x56 && test.c[2] == 0x34 && test.c[3] == 0x12) {
        std::cout << "Little-endian" << std::endl;
    } else if (test.c[0] == 0x12 && test.c[1] == 0x34 && test.c[2] == 0x56 && test.c[3] == 0x78) {
        std::cout << "Big-endian" << std::endl;
    } else {
        std::cout << "Nieznana" << std::endl;
    }

    return 0;
}

Różne procesory używają różnych kolejności bajtów:

• Little-endian: Procesory Intel x86, x86-64 oraz większość mikrokontrolerów ARM (w trybie little-endian).
• Big-endian: Procesory Motorola 68k, PowerPC, IBM z/Architecture, a także niektóre mikrokontrolery ARM (w trybie big-endian).

Wybór kolejności bajtów jest często wynikiem decyzji projektowych, które miały na celu ułatwienie lub optymalizację wykonywania określonych operacji. Little-endian jest popularne ze względu na prostotę dodawania i odejmowania liczb o zmiennej długości oraz łatwiejszą obsługę liczb o mniejszej precyzji w reprezentacji o większej precyzji. Big-endian jest częściej stosowany w systemach, które muszą współpracować z sieciami komputerowymi, gdzie bajty są przesyłane od najbardziej znaczącego do najmniej znaczącego, co ułatwia interpretację wartości przesyłanych danych.

Ref:

• Jak to jest z tym little-endian

Wykonywania operacji stało- i zmiennoprzecinkowych:

FPU (Floating Point Unit) to podzespoły procesora odpowiedzialne za wykonywanie operacji arytmetycznych na liczbach zmiennoprzecinkowych. Liczba jednostek FPU może się różnić w zależności od architektury i modelu procesora. Oto kilka przykładów:

1. Intel Core i7-8700K (8. generacja Core)

• 6 rdzeni, każdy z jednostką FPU - 6 jednostek FPU.

2. AMD Ryzen 7 3700X (3. generacja Ryzen)

• 8 rdzeni, każdy z jednostką FPU - 8 jednostek FPU.

3. Apple M1 (ARM-based)

• 8 rdzeni CPU (4 wysokiej wydajności i 4 energooszczędne), każdy z jednostką FPU - 8 jednostek FPU.

4. IBM POWER9

• 12 lub 24 rdzenie, w zależności od konfiguracji. Każdy rdzeń ma jedną jednostkę FPU - 12 lub 24 jednostki FPU.

5. NVIDIA A100 (GPU)

• W przypadku GPU, jednostki FPU są zintegrowane z procesorami strumieniowymi (CUDA cores). NVIDIA A100 posiada 6912 rdzeni CUDA.

Warto zauważyć, że w przypadku GPU, jednostki FPU mogą być wykorzystywane do obliczeń równoległych, ale zwykle nie są one traktowane jako oddzielne jednostki, tak jak w przypadku CPU.

Porównanie czasu wykonywania

Porównanie czasu wykonywania dodawania, odejmowania, mnożenia i dzielenia dla liczby stałoprzecinkowej (int) i zmiennoprzecinkowej (float, double).

1. Utwórz program, który generuje losowe liczby int oraz float (lub double) i wykonuje podstawowe operacje matematyczne.
2. Zmierz czas wykonania każdej operacji dla różnych precyzji.
3. Porównaj wyniki i zastanów się nad wpływem precyzji na czas wykonania operacji.

Lab_02:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <iostream>
#include <iomanip>
#include <chrono>
#include <random>
#include <vector>

using namespace std;
using namespace std::chrono;

template <typename T,std::enable_if_t<std::is_integral<T>::value, bool> =true>
T generateRandomNumber(T min, T max)
{
    static random_device rd;
    static mt19937 gen(rd());
    uniform_int_distribution<T> dist(min, max);
    return dist(gen);
}

template <typename T,std::enable_if_t<std::is_floating_point<T>::value, bool> = true>
T generateRandomNumber(T min, T max)
{
    static random_device rd;
    static mt19937 gen(rd());
    uniform_real_distribution<T> dist(min, max);
    return dist(gen);
}


template <typename T>
T complex_operation(T a, T b)
{
    T result = (a + b) * (a - b) / (a * b); // +std::sin(a) - std::cos(b);
    return result;
}

template <typename T>
void perform_operations(const std::string& data_type)
{
    const auto num_operations = 10LL;

    std::vector<T> a(num_operations), b(num_operations);

    for (int i = 0; i < num_operations; ++i) 
    {
        a[i] = static_cast<T>(generateRandomNumber<T>(1, 1000));
        b[i] = static_cast<T>(generateRandomNumber<T>(1, 1000));
    }

    T result = 0;
    auto start = high_resolution_clock::now();
    for (auto i = 0; i < num_operations; ++i) 
        result += complex_operation(a[i], b[i]);
    

    const auto end = high_resolution_clock::now();
    const duration<double, std::milli> elapsed = end - start;

    std::cout << "Time taken for " << data_type << ": " << elapsed.count() << " ms" << " " << result << std::endl;
}


int main()
{
    perform_operations<int>("int");
    perform_operations<float>("float");
    perform_operations<double>("double");

    return 0;
}

Ten program w C++ analizuje wpływ precyzji zmiennoprzecinkowej na czas wykonania operacji. Wykonuje on podstawowe operacje matematyczne (+, -, *, /) na liczbach całkowitychoraz zmiennoprzecinkowych o różnych precyzjach (float, double) i mierzy czas wykonania tych operacji za pomocą biblioteki <chrono>.

Po skompilowaniu i uruchomieniu programu, na konsoli zostaną wyświetlone wyniki czasu wykonania operacji dla różnych precyzji. Należy przeanalizować wyniki i zastanowić się nad wpływem precyzji na czas wykonania operacji.

Obliczanie czasu wykonywania operacji na macierzach stało- i zmiennoprzecinkowych.

1. Napisz program, który mnoży dwie macierze o ustalonych rozmiarach, używając typów stałoprzecinkowych (int) oraz zmiennoprzecinkowych (float, double).
2. Zmierz czas wykonania mnożenia macierzy dla różnych rozmiarów macierzy.
3. Porównaj wyniki i omów znaczenie różnic w czasie wykonania dla różnych typów danych.

Lab_04:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <chrono>
#include <vector>

using namespace std;
using namespace std::chrono;

template <typename T>
void multiply_matrices(const vector<vector<T>> &matrix1, const vector<vector<T>> &matrix2, vector<vector<T>> &result) {
    size_t rows = matrix1.size();
    size_t cols = matrix2[0].size();
    size_t inner = matrix1[0].size();

    for (size_t i = 0; i < rows; ++i) {
        for (size_t j = 0; j < cols; ++j) {
            result[i][j] = 0;
            for (size_t k = 0; k < inner; ++k) {
                result[i][j] += matrix1[i][k] * matrix2[k][j];
            }
        }
    }
}

template <typename T>
void test_matrix_multiplication(int size, const string &type_name) {
    // Inicjalizacja macierzy
    vector<vector<T>> matrix1(size, vector<T>(size, static_cast<T>(2)));
    vector<vector<T>> matrix2(size, vector<T>(size, static_cast<T>(3)));
    vector<vector<T>> result(size, vector<T>(size, static_cast<T>(0)));

    // Mierzenie czasu mnożenia macierzy
    auto start_time = high_resolution_clock::now();
    multiply_matrices(matrix1, matrix2, result);
    auto end_time = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(end_time - start_time).count();
    cout << "Czas wykonania mnożenia macierzy " << size << "x" << size << " dla typu " << type_name << ": " << duration << " milisekund" << endl;
}

int main() {
    // Przetestuj mnożenie macierzy dla różnych rozmiarów i typów danych
    test_matrix_multiplication<int>(100, "int");
    test_matrix_multiplication<float>(100, "float");
    test_matrix_multiplication<double>(100, "double");

    test_matrix_multiplication<int>(500, "int");
    test_matrix_multiplication<float>(500, "float");
    test_matrix_multiplication<double>(500, "double");

    test_matrix_multiplication<int>(1000, "int");
    test_matrix_multiplication<float>(1000, "float");
    test_matrix_multiplication<double>(1000, "double");

    cout << "Porównaj wyniki i omów znaczenie różnic w czasie wykonania dla różnych typów danych." << endl;

    return 0;
}

Program mnoży dwie macierze o ustalonych rozmiarach, używając typów stałoprzecinkowych (int) oraz zmiennoprzecinkowych (float, double). Następnie, mierzy czas wykonania mnożenia macierzy dla różnych rozmiarów macierzy (100x100, 500x500, 1000x1000) i porównuje wyniki dla różnych typów danych.

Po skompilowaniu i uruchomieniu programu, na konsoli zostaną wyświetlone wyniki czasu wykonania mnożenia macierzy dla różnych rozmiarów macierzy i typów danych. Porównaj wyniki i omów znaczenie różnic w czasie wykonania dla różnych typów danych.

Wyniki mogą się różnić w zależności od sprzętu i kompilatora. Analizuj różnice między typami danych (stałoprzecinkowe i zmiennoprzecinkowe) oraz rozmiarami macierzy. Zwróć uwagę na to, jak zmienia się czas wykonania w zależności od typu danych i rozmiaru macierzy. Zastanów się, jak te różnice wpływają na wydajność w praktycznych zastosowaniach, takich jak obliczenia naukowe, analiza danych czy grafika komputerowa.

W praktyce, wybór między typami danych zależy od wymagań dotyczących precyzji, wydajności i dostępnych zasobów. W przypadku obliczeń naukowych i analizy danych, precyzja może być kluczowa, ale jednocześnie może wpłynąć na czas wykonania. W grafice komputerowej, mniejsza precyzja może być akceptowalna, ale szybsze obliczenia mogą być kluczowe dla płynności działania aplikacji.

Eksperyment z optymalizacją kodu.

1. Napisz prosty program, który wykonuje operacje matematyczne na liczbach stało- i zmiennoprzecinkowych.
2. Skompiluj i uruchom program z różnymi poziomami optymalizacji (np. -O0, -O1, -O2, -O3).
3. Porównaj czas wykonania programu dla różnych poziomów optymalizacji i zastanów się, jak optymalizacja wpływa na wydajność operacji stało- i zmiennoprzecinkowych.

Wprowadzenie do instrukcji SIMD.

1. Zapoznaj się z instrukcjami SIMD (Single Instruction, Multiple Data) dostępnymi dla Twojego procesora (np. SSE, AVX).
2. Napisz program, który wykonuje operacje matematyczne na wektorach liczb stało- i zmiennoprzecinkowych, wykorzystując instrukcje SIMD.
3. Porównaj czas wykonania operacji wektorowych z użyciem SIMD do czasu wykonania operacji

Aby użyć instrukcji SIMD w C++, możemy wykorzystać bibliotekę immintrin.h, która obsługuje instrukcje SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, AVX, AVX2 i AVX-512.

Poniżej znajduje się przykład programu w C++, który wykonuje operacje dodawania na wektorach liczb stało- i zmiennoprzecinkowych, wykorzystując instrukcje SIMD. Porównuje czas wykonania operacji wektorowych z użyciem SIMD do czasu wykonania operacji bez SIMD.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <iostream>
#include <chrono>
#include <vector>
#include <immintrin.h>

using namespace std;
using namespace std::chrono;

const int vector_size = 1000000;

template <typename T>
void add_vectors(const vector<T> &a, const vector<T> &b, vector<T> &result) {
    for (size_t i = 0; i < a.size(); ++i) {
        result[i] = a[i] + b[i];
    }
}

void add_vectors_simd(const vector<float> &a, const vector<float> &b, vector<float> &result) {
    size_t simd_length = a.size() / 8;

    for (size_t i = 0; i < simd_length; ++i) {
        __m256 vec_a = _mm256_loadu_ps(&a[i * 8]);
        __m256 vec_b = _mm256_loadu_ps(&b[i * 8]);
        __m256 vec_result = _mm256_add_ps(vec_a, vec_b);
        _mm256_storeu_ps(&result[i * 8], vec_result);
    }
}

template <typename T>
void test_add_vectors(const string &type_name) {
    vector<T> a(vector_size, static_cast<T>(1));
    vector<T> b(vector_size, static_cast<T>(2));
    vector<T> result(vector_size, static_cast<T>(0));

    auto start_time = high_resolution_clock::now();
    add_vectors(a, b, result);
    auto end_time = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(end_time - start_time).count();
    cout << "Czas wykonania dodawania wektorów bez SIMD dla " << type_name << ": " << duration << " ms" << endl;
}

void test_add_vectors_simd_float() {
    vector<float> a(vector_size, 1.0f);
    vector<float> b(vector_size, 2.0f);
    vector<float> result(vector_size, 0.0f);

    auto start_time = high_resolution_clock::now();
    add_vectors_simd(a, b, result);
    auto end_time = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(end_time - start_time).count();
    cout << "Czas wykonania dodawania wektorów z użyciem SIMD dla float: " << duration << " ms" << endl;
}

int main() {
    test_add_vectors<int>("int");
    test_add_vectors<float>("float");
    test_add_vectors<double>("double");

    test_add_vectors_simd_float();

    return 0;
}

W tym przypadku, używamy instrukcji SIMD dla operacji dodawania wektorów zmiennoprzecinkowych (float). Program porównuje czas wykonania operacji wektorowych z użyciem SIMD do czasu wykonania operacji bez SIMD dla typów int, float i double. Po skompilowaniu i uruchomieniu programu, na konsoli zostaną wyświetlone wyniki czasu wykonania dodawania wektorów dla różnych typów danych, zarówno z użyciem SIMD, jak i bez.

Wyniki mogą się różnić w zależności od sprzętu i kompilatora, ale zazwyczaj SIMD przyspiesza obliczenia wektorowe, gdyż pozwala na wykonywanie operacji na wielu elementach danych jednocześnie.

W praktyce, wykorzystanie SIMD może prowadzić do znacznego przyspieszenia obliczeń wektorowych, szczególnie w zastosowaniach, takich jak grafika komputerowa, analiza danych czy przetwarzanie sygnałów. Jednak warto pamiętać, że nie wszystkie operacje mogą być przyspieszone przy użyciu SIMD, a także, że optymalizacja przy użyciu SIMD może zwiększyć złożoność kodu i utrudnić jego utrzymanie.

Ref:

• Native code performance on modern CPUs

Porównawczy kod w asemblerze

Poniżej znajduje się przykład programu napisanego w asemblerze x86, który porównuje czas wykonania operacji dodawania, odejmowania, mnożenia i dzielenia dla liczby stałoprzecinkowej (int) i zmiennoprzecinkowej (float, double). Program korzysta z polecenia RDTSC do mierzenia czasu wykonania operacji.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

format PE GUI 4.0
entry start

include 'win32w.inc'

section '.text' code readable executable

start:

    ; Licznik petli dla liczby staloprzecinkowej (int)
    mov ecx, [iterations]

    ; Pobranie czasu startowego
    rdtsc
    mov edi, eax

int_loop:

    mov eax, [int_a]
    mov ebx, [int_b]

    ; Dodawanie
    add eax, ebx

    ; Odejmowanie
    sub eax, ebx

    ; Mnozenie
    imul eax, ebx

    ; Dzielenie
    xor edx, edx
    idiv ebx

    ; Nastepna iteracja
    loop int_loop

    ; Pobranie czasu koncowego
    rdtsc
    sub eax, edi
    mov [int_duration], eax

    ; Licznik petli dla liczby zmiennoprzecinkowej (float)
    mov ecx, [iterations]

    ; Pobranie czasu startowego
    rdtsc
    mov edi, eax

float_loop:
    ; Wczytanie liczb zmiennoprzecinkowych do rejestrów
    fld [float_a]
    fld [float_b]

    ; Dodawanie
    faddp st1, st0

    ; Odejmowanie
    fsubp st1, st0

    ; Mnozenie
    fmulp st1, st0

    ; Dzielenie
    fdivp st1, st0

    ; Nastepna iteracja
    loop float_loop

    ; Pobranie czasu koncowego
    rdtsc
    sub eax, edi
    mov [float_duration], eax

    ; Zakonczenie programu
    invoke ExitProcess, 0

section '.data' data readable writeable

  iterations dd 1000000

  ; Stale dla liczb staloprzecinkowych
  int_a dd 123
  int_b dd 456

  ; Stale dla liczb zmiennoprzecinkowych
  float_a dd 123.456f
  float_b dd 456.789f

  ; Rezerwacja miejsca na zmienne
  int_duration dd ?
  float_duration dd ?

section '.idata' import data readable writeable

  library kernel32,'KERNEL32.DLL',\
  user32,'USER32.DLL'

  include 'api\kernel32.inc'
  include 'api\user32.inc'

Aby skompilować i uruchomić program, można użyć narzędzi NASM i LD lub fasm

Należy pamiętać, że ten program nie wypisuje wyników na ekran, ale przechowuje je w zarezerwowanych zmiennych int_duration i float_duration. Aby wyświetlić wyniki, można dodać kod odpowiedzialny za wypisanie wartości na ekran, korzystając z systemu wywołań (syscalls) lub użyć debuggera, aby przejrzeć wartości tych zmiennych

Ref:

• x64dbg

Architektura von Neumana

Architektura komputerów Von-Neumanna, zaproponowana przez Johna von Neumanna, opiera się na koncepcji przechowywania programów w pamięci komputera. Wcześniej, maszyny liczące były projektowane tak, aby wykonywać jedno konkretne zadanie i nie można było ich przeprogramować. Architektura von Neumanna wprowadziła założenie, że programy i dane mogą być przechowywane w tej samej pamięci, co umożliwiło rozwój maszyn uniwersalnych, które mogą wykonywać różne zadania.

Podstawowe elementy architektury von Neumanna obejmują:

1. Pamięć: Służy do przechowywania danych i programów. Pamięć może być podzielona na dwie części: pamięć operacyjną (RAM) i pamięć trwałą (np. dysk twardy).

2. Procesor: Składa się z jednostki arytmetyczno-logicznej (ALU) oraz jednostki sterującej. ALU wykonuje operacje arytmetyczne i logiczne na danych, podczas gdy jednostka sterująca zarządza sekwencją operacji, odczytuje instrukcje z pamięci i decyduje, jakie operacje mają zostać wykonane.

3. Wejście/wyjście (I/O): Odpowiada za komunikację z urządzeniami zewnętrznymi, takimi jak klawiatura, mysz, monitor, drukarka itp.

4. System komunikacji: Składa się z szyny danych, szyny adresowej i szyny kontrolnej, które łączą poszczególne elementy komputera i umożliwiają wymianę informacji między nimi.

Architektura komputerów Von-Neumanna jest podstawą dla większości współczesnych komputerów i urządzeń, takich jak komputery osobiste, laptopy, serwery czy smartfony. Wraz z postępem technologicznym i rozwojem układów scalonych oraz mikroprocesorów, architektura von Neumanna została udoskonalona i przekształcona, ale jej podstawowe zasady wciąż pozostają aktualne.

ISA (Instruction set architecture) i posiada trzy podstawowe jednostki:

1. Centralna Jednostka Przetwarzająca (CPU)
   1. Control Unit(CU)
   2. Jednostka arytmetyczna i logiczna (ALU)
   3. Rejestry
2. Jednostka pamięci głównej
3. Urządzenie wejścia/wyjścia

Przykładowa symulacja architektury

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

using System;

class ControlUnit
{
    public int ProgramCounter { get; set; }
    public int MemoryAddressRegister { get; set; }
    public int MemoryDataRegister { get; set; }
    public int CurrentInstructionRegister { get; set; }
    public int InstructionBufferRegister { get; set; }

    public ControlUnit()
    {
        ProgramCounter = 0;
        MemoryAddressRegister = 0;
        MemoryDataRegister = 0;
        CurrentInstructionRegister = 0;
        InstructionBufferRegister = 0;
    }

    public void FetchInstruction()
    {
    }

    public void ExecuteInstruction()
    {
    }
}

class ALU
{
    public int Accumulator { get; set; }

    public ALU()
    {
        Accumulator = 0;
    }

    public void Add(int a, int b)
    {
    }

    public void Subtract(int a, int b)
    {
    }

    public void Compare(int a, int b)
    {
    }

    public void PerformLogicOperation(int a, int b, string operation)
    {
    }

    public void ShiftBits(int value, string direction, int amount)
    {
    }
}

class CPU
{
    public ControlUnit ControlUnit { get; set; }
    public ALU Alu { get; set; }

    public CPU()
    {
        ControlUnit = new ControlUnit();
        Alu = new ALU();
    }

    public void Run()
    {
    }
}

class MainMemory
{
    public int[] Memory { get; set; }

    public MainMemory(int size)
    {
        Memory = new int[size];
    }

    public void Read(int address)
    {
    }

    public void Write(int address, int value)
    {
    }
}

class IODevice
{
    public void InputData()
    {
    }

    public void OutputData(int data)
    {
    }
}

class Computer
{
    public CPU Cpu { get; set; }
    public MainMemory Memory { get; set; }
    public IODevice IoDevice { get; set; }

    public Computer(int memorySize)
    {
        Cpu = new CPU();
        Memory = new MainMemory(memorySize);
        IoDevice = new IODevice();
    }

    public void LoadProgram(int[] program)
    {
    }

    public void Run()
    {
    }
}

class Program
{
    static void Main(string[] args)
    {
        Computer computer = new Computer(memorySize: 1024);
        // Load a program into the computer
        // computer.LoadProgram(program);
        computer.Run();
    }
}

Przykład Lab_31.py

Instrukcje symulatora

Procesor posiada tylko jeden rejestr, akumulator A. Możliwe jest adresowanie bezpośrednie i pośrednie. Załóżmy, że akumulator jest 32bitowy.

• HLT - Zatrzymanie pracy
• LDA <> - Załadowanie do A danych z adresu
• STA - Wpisanie pod zadany adres w argumencie, wartości z rejestru A
• LDI - Załadowanie do A danych z adresu wskzanego pod podanym adresem
• INP - Załadowanie danych do A z urządzenia we/wy
• OUT - Wysłanie wartości A na wyjście
• ADD - Dodanie wartości z pamięci wskazanej przez argument do A
• SUB - Odjęcie od A wartości z pamięci wskazanej przez argument
• CMP - Porównanie A z wartoścą pamięci wskazanej przez argument, wynik w A 0 jesli równe, 1 jeśli różne
• MOV - Wpisanie do A bezpośredniej wartości
• INC - Zwiększenie A o jeden
• DEC - Zmniejszenie A o jeden
• JMP - Skok bezwarunkowy
• JZ - Skok jeśli A jest równe zero

Składnia assemblera:

:etykieta - etykieta, wskazująca na miejsce w pamięci

@etykieta - poinformowanie kompilator, aby zamienił wskazanie na adres etykiety w pamięci

Przykłady:

Wypisanie liczby 10 na wyjście

1
2
3
4

    MOV 10
    OUT

    HLT

Dodawanie

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    MOV 10
    STA @value 

    MOV 15
    ADD @value

    OUT

    HLT

:value
    0

Adresowanie bezpośrednie

1
2
3
4
5
6
7

    LDA @location
    OUT

    HLT

:value
    42

Adresowanie pośrednie

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    LDI @location
    OUT

    MOV 42
    STA @value
    LDI @location
    OUT
    
    HLT

:location
    @value
:value
    37

Pętla

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    MOV 10
:loop
    OUT
    DEC
    JZ @exit
    JMP @loop

:exit
    OUT
    HLT

Ćwiczenia

dodac dwie liczby znajdujące się w pamięci

1
2
3

:value
    3
    141

• wypisac liczby znajdujące się w pamięci az napotkamy 0:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

:value
    3
    141
    5
    92
    65
    35
    89
    79
    0

• zsumować liczby znajdujące się w pamięci, zakończyć jak napotkamy 0:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

:value
    1
    2
    3
    4
    5
    6
    7
    8
    0

• wypisac na wyjście kolejne wartości ciągu fibonacciego, kilka pierwszych. Dla uproszczenia można dwie początkowe zapisać od razu w kodzie, np.:

1
2
3
4
5

    :fib1
    0
    
    :fib2
    1

Symulator

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409

var ioDevice = new IODevice();
var computer = new Computer(256, ioDevice);

var compiler = new Compiler();
var compiledProgram = compiler.Compile(sourceCode_dump);

computer.LoadProgram(compiledProgram);
computer.Run();

enum OpCode
{
    HLT = 0x00,
    LDA = 0x01,
    STA = 0x02,
    LDI = 0x03,
    INP = 0x04,
    OUT = 0x05,
    ADD = 0x06,
    SUB = 0x07,
    CMP = 0x08,
    MOV = 0x09,
    INC = 0x0a,
    DEC = 0x0b,
    JMP = 0x0c,
    JZ  = 0x0d,
    MEM = 0x0e,

    DB  = 0x0
}

class ControlUnit
{
    private bool _debug;

    private int ProgramCounter { get; set; }
    private int MemoryAddressRegister { get; set; }
    private int MemoryDataRegister { get; set; }
    private int CurrentInstructionRegister { get; set; }


    public ControlUnit(bool debug = false)
    {
        _debug = debug;

        ProgramCounter = 0;
        MemoryAddressRegister = 0;
        MemoryDataRegister = 0;
        CurrentInstructionRegister = 0;
    }

    public void FetchInstruction(MainMemory memory)
    {
        MemoryAddressRegister = ProgramCounter;
        MemoryDataRegister = memory.Read(MemoryAddressRegister);
        CurrentInstructionRegister = MemoryDataRegister;
        ProgramCounter += 1;
    }

    public void PrintInstruction(OpCode opcode, CPU cpu, MainMemory memory, IODevice ioDevice)
    {
        if (!_debug)
            return;

        Console.WriteLine($"#{ProgramCounter:X3} A:{cpu.ALU.Accumulator:X3} ({cpu.ALU.Accumulator:D3}) -> {opcode.ToString()} {MemoryAddressRegister:X3} {MemoryDataRegister:X3}");
    }

    public bool ExecuteInstruction(CPU cpu, MainMemory memory, IODevice ioDevice)
    {
        var instruction = (OpCode)CurrentInstructionRegister;
        
        PrintInstruction(instruction, cpu, memory, ioDevice);

        switch (instruction)
        {
            case OpCode.HLT:
                Console.WriteLine($"HALT encountered at address {ProgramCounter:X2}");
                return false;
            case OpCode.LDA:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                MemoryDataRegister = memory.Read(MemoryAddressRegister);
                cpu.ALU.Accumulator = MemoryDataRegister;
                
                ProgramCounter += 1;
                break;
            case OpCode.LDI:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                MemoryAddressRegister = memory.Read(MemoryAddressRegister);
                MemoryDataRegister = memory.Read(MemoryAddressRegister);
                cpu.ALU.Accumulator = MemoryDataRegister;
                
                ProgramCounter += 1;
                break;
            case OpCode.STA:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                MemoryDataRegister = cpu.ALU.Accumulator;
                memory.Write(MemoryAddressRegister, MemoryDataRegister);

                ProgramCounter += 1;
                break;
            case OpCode.INP:
                cpu.ALU.Accumulator = ioDevice.InputData();
                break;
            case OpCode.OUT:
                ioDevice.OutputData(cpu.ALU.Accumulator);
                break;
            case OpCode.MEM:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                for (var i = 0; i < cpu.ALU.Accumulator; i++)
                {
                    var data = memory.Read(MemoryAddressRegister + i);
                    ioDevice.OutputData(data);
                }

                ProgramCounter++;
                break;
            case OpCode.ADD:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                MemoryDataRegister = memory.Read(MemoryAddressRegister);
                cpu.ALU.Add(MemoryDataRegister);

                ProgramCounter += 1;
                break;
            case OpCode.SUB:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                MemoryDataRegister = memory.Read(MemoryAddressRegister);
                cpu.ALU.Subtract(MemoryDataRegister);
                
                ProgramCounter += 1;
                break;
            case OpCode.CMP:
                MemoryAddressRegister = memory.Read(ProgramCounter);
                MemoryDataRegister = memory.Read(MemoryAddressRegister);
                cpu.ALU.Compare(MemoryDataRegister);
                
                ProgramCounter += 1;
                break;
            case OpCode.MOV:
                var value = memory.Read(ProgramCounter);
                cpu.ALU.Accumulator = value;
                PrintInstruction(instruction, cpu, memory, ioDevice);
                
                ProgramCounter += 1;
                break;
            case OpCode.INC:
                cpu.ALU.Accumulator += 1;
                break;
            case OpCode.DEC:
                cpu.ALU.Accumulator -= 1;
                break;
            case OpCode.JMP:
                var targetAddress = memory.Read(ProgramCounter);
                
                ProgramCounter = targetAddress;
                break;
            case OpCode.JZ:
                targetAddress = memory.Read(ProgramCounter);
                if (cpu.ALU.Accumulator == 0)
                    ProgramCounter = targetAddress;
                else
                    ProgramCounter += 1;

                break;
            default:
                Console.WriteLine($"Unsupported instruction: {instruction} -> HALT");
                return false;
        }

        return true;
    }
}

class ALU
{
    public int Accumulator { get; set; }

    public ALU()
    {
        Accumulator = 0;
    }

    public void Add(int b)
    {
        Accumulator += b;
    }

    public void Subtract(int b)
    {
        Accumulator -= b;
    }

    public void Compare(int b)
    {
        Accumulator = (Accumulator - b) == 0 ? 0 : 1;
    }
}

class CPU
{
    public ControlUnit ControlUnit { get; }
    public ALU ALU { get; }

    public CPU()
    {
        ControlUnit = new ControlUnit(true);
        ALU = new ALU();
    }

    public void Run(MainMemory memory, IODevice ioDevice)
    {
        var running = true;
        while (running)
        {
            ControlUnit.FetchInstruction(memory);
            running = ControlUnit.ExecuteInstruction(this, memory, ioDevice);
        }
    }
}

class MainMemory
{
    public int[] Memory { get; }

    public MainMemory(int size)
    {
        Memory = new int[size];
    }

    public int Read(int address)
    {
        return Memory[address];
    }

    public void Write(int address, int value)
    {
        Memory[address] = value;
    }
}

class IODevice
{
    public int InputData()
    {
        return 42;
    }

    public void OutputData(int data)
    {
        Console.WriteLine($"Output: {data}");
    }
}

class Computer
{
    public CPU Cpu { get; }
    public MainMemory Memory { get; }
    public IODevice IoDevice { get; }
    public Dictionary<string, int> Labels { get; }
    public int Offset { get; set; }

    public Computer(int memorySize, IODevice ioDevice)
    {
        Cpu = new CPU();
        Memory = new MainMemory(memorySize);
        IoDevice = ioDevice;
        Labels = new Dictionary<string, int>();
        Offset = 0;
    }

    public void LoadProgram(List<int> program)
    {
        for (var i = 0; i < program.Count; i++)
            Memory.Write(i, program[i]);

        Console.WriteLine("Program loaded into memory");
    }

    public void Run()
    {
        Console.WriteLine("Running program...");
        Cpu.Run(Memory, IoDevice);
    }
}

class Compiler
{
    private readonly Dictionary<string, int> _labels;

    private static readonly Regex LabelRegex = new Regex(@"\s*:\s*(\w+)");


    public Compiler()
    {
        _labels = new Dictionary<string, int>();
    }

    private static string RemoveComment(string line)
    {
        var commentIndex = line.IndexOf('#');

        return commentIndex != -1 ? line.Substring(0, commentIndex).Trim() : line.Trim();
    }

    private int ParseOperand(string token)
    {
        int operand;

        if (token.StartsWith("@"))
        {
            var label = token.Substring(1, token.Length - 1);
            if (_labels.ContainsKey(label))
                operand = _labels[label];
            else
                throw new NotSupportedException($"Label not found: {token}");
        }
        else
            try
            {
                operand = int.Parse(token);
            }
            catch
            {
                throw new NotSupportedException($"Unknown token: {token}");
            }

        return operand;
    }

    public List<int> Compile(string sourceCode)
    {
        var compiledProgram = new List<int>();
        var lines = sourceCode.Split(new[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);

        // First pass - process labels
        var offset = 0;
        var index = 0;
        foreach (var line in lines)
        {
            var trimmedLine = RemoveComment(line);
            if (trimmedLine.Length == 0)
                continue;

            var match = LabelRegex.Match(trimmedLine);

            if (match.Success)
            {
                _labels.Add(match.Groups[1].Value, index - offset);
                offset++;
            }

            var tokens = trimmedLine.Split(' ', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
            index += tokens.Length;

        }

        // Second pass - compile instructions
        foreach (var line in lines)
        {
            var trimmedLine = RemoveComment(line);
            if (trimmedLine.Length == 0)
                continue;

            if (trimmedLine.StartsWith(':')) 
                continue;

            var operand = 0;
            var tokens = trimmedLine.Split(' ', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);

            if (Enum.TryParse(tokens[0].ToUpper(), out OpCode opCode))
            {
                compiledProgram.Add((int)opCode);

                if (tokens.Length <= 1) 
                    continue;

                operand = ParseOperand(tokens[1]);
                compiledProgram.Add(operand);
            }
            else
            {
                // try to convert to a number
                operand = ParseOperand(tokens[0]);
                compiledProgram.Add(operand);
            }
        }

        DumpByteCode(compiledProgram);

        return compiledProgram;
    }

    private static void DumpByteCode(List<int> compiledProgram)
    {
        Console.WriteLine("Compiled byte-code:");

        var separator = "\n";
        for (var index = 0; index < compiledProgram.Count; index++)
        {
            Console.Write($"{index:X2}|");
            separator += "--|";
        }

        Console.WriteLine(separator);

        foreach (var op in compiledProgram)
            Console.Write($"{op:X2}|");

        Console.WriteLine("\n");
    }
}

Analiza cyklu rozkazowego

Zdefiniowanie cyklu rozkazowego i jego faz (pobieranie, dekodowanie, wykonanie, dostęp do pamięci i zapis wyniku).

Cykl rozkazowy to sekwencja kroków, które wykonuje procesor w celu pobrania, zdekodowania i wykonania pojedynczego rozkazu. Cykl rozkazowy składa się z pięciu głównych faz, które są realizowane sekwencyjnie:

1. Pobieranie (Fetch): W tej fazie procesor pobiera rozkaz z pamięci. Wartość licznika rozkazów (Program Counter, PC) wskazuje na adres pamięci, z którego rozkaz ma być pobrany. Po pobraniu rozkazu, licznik rozkazów jest zwiększany o rozmiar rozkazu, aby wskazać na kolejny rozkaz.

2. Dekodowanie (Decode): Pobrany rozkaz jest dekodowany przez jednostkę dekodującą procesora, która interpretuje go i ustala, jakie operacje należy wykonać oraz które rejestry i/lub wartości są używane jako argumenty.

3. Wykonanie (Execute): W tej fazie jednostka wykonawcza procesora przeprowadza operacje zdefiniowane przez rozkaz. Może to obejmować działania arytmetyczne, logiczne, przesunięcia bitowe lub inne operacje. Wynik tych operacji jest przechowywany w rejestrze tymczasowym.

4. Dostęp do pamięci (Memory Access): Jeśli rozkaz wymaga dostępu do pamięci, na przykład w celu odczytania lub zapisania wartości, w tej fazie procesor odczytuje dane z pamięci lub zapisuje je w odpowiednim miejscu.

5. Zapis wyniku (Write-back): W tej ostatniej fazie wynik operacji, przechowywany w rejestrze tymczasowym, jest zapisywany do odpowiedniego rejestru procesora lub do pamięci, jeśli jest to wymagane.

Przykład analizy cyklu rozkazowego:

Rozważmy prosty przykład dodawania dwóch liczb, przechowywanych w rejestrach R1 i R2, a wynik ma być zapisany w rejestrze R3. Rozkaz może wyglądać tak: ADD R3, R1, R2

1. Pobieranie: Procesor pobiera rozkaz ADD z adresu wskazanego przez licznik rozkazów (PC) i zwiększa wartość PC.
2. Dekodowanie: Jednostka dekodująca interpretuje rozkaz jako operację dodawania, gdzie R1 i R2 są argumentami, a wynik ma być zapisany w R3.
3. Wykonanie: Jednostka wykonawcza dodaje wartości z rejestru R1 i R2, a wynik przechowuje w rejestrze tymczasowym.
4. Dostęp do pamięci: W tym przypadku nie ma potrzeby dostępu do pamięci, ponieważ wszystkie wartości są przechowywane w rejestrach.
5. Zapis wyniku: Wynik dodawania, przechowywany w rejestrze tymczasow

Etapy cyklu rozkazowego.

Przyjmijmy prosty zestaw rozkazów oparty na hipotetycznym procesorze z ograniczoną architekturą. Rozkazy:

1. LOAD R1, (ADDR) - Ładuje wartość z pamięci o adresie ADDR do rejestru R1.
2. STORE (ADDR), R1 - Zapisuje wartość z rejestru R1 do pamięci o adresie ADDR.
3. ADD R1, R2 - Dodaje wartości z rejestru R1 i R2, a wynik zapisuje w rejestrze R1.
4. SUB R1, R2 - Odejmuje wartość rejestru R2 od wartości rejestru R1, a wynik zapisuje w rejestrze R1.
5. JUMP ADDR - Bezwarunkowy skok do adresu ADDR.
6. JNZERO R1, ADDR - Skok warunkowy do względnego adresu ADDR, jeśli wartość w rejestrze R1 jest różna od 0.

Omówienie poszczególnych etapów cyklu rozkazowego dla każdego z rozkazów:

1. LOAD R1, (ADDR):

   • Pobieranie: Procesor pobiera rozkaz LOAD z pamięci.
   • Dekodowanie: Dekodowanie rozkazu LOAD i identyfikacja rejestru R1 oraz adresu pamięci ADDR.
   • Wykonanie: Brak operacji wykonawczych dla tego rozkazu.
   • Dostęp do pamięci: Odczyt wartości z pamięci o adresie ADDR.
   • Zapis wyniku: Zapisanie odczytanej wartości do rejestru R1.

2. STORE (ADDR), R1:

   • Pobieranie: Procesor pobiera rozkaz STORE z pamięci.
   • Dekodowanie: Dekodowanie rozkazu STORE i identyfikacja rejestru R1 oraz adresu pamięci ADDR.
   • Wykonanie: Brak operacji wykonawczych dla tego rozkazu.
   • Dostęp do pamięci: Zapis wartości z rejestru R1 do pamięci o adresie ADDR.
   • Zapis wyniku: Brak operacji zapisu wyniku, ponieważ wynik został już zapisany w pamięci.

3. ADD R1, R2:

   • Pobieranie: Procesor pobiera rozkaz ADD z pamięci.
   • Dekodowanie: Dekodowanie rozkazu ADD i identyfikacja rejestrów R1 i R2.
   • Wykonanie: Dodawanie wartości z rejestru R1 i R2, a wynik przechowuje w rejestrze tymczasowym.
   • Dostęp do pamięci: Brak dostępu do pamięci, ponieważ wszystkie wartości są przechowywane w rejestrach.
   • Zapis wyniku: Zapisanie wyniku dodawania do rejestru R1.

4. SUB R1, R2:

   • Pobieranie: Procesor pobiera rozkaz SUB z pamięci.
   • Dekodowanie: Dekodowanie rozkazu SUB i identyfikacja rejestrów R1 i R2.
   • Wykonanie: Odejmowanie wartości rejestru R2 od wartości rejestru R1, a wynik przechowuje w rejestrze tymczasowym.
   • Dostęp do pamięci: Brak dostępu do pamięci, ponieważ wszystkie wartości są przechowywane w rejestrach.
   • Zapis wyniku: Zapisanie wyniku odejmowania do rejestru R1.

5. JUMP ADDR:

   • Pobieranie: Procesor pobiera rozkaz JUMP z pamięci.
   • Dekodowanie: Dekodowanie rozkazu JUMP i identyfikacja adresu ADDR.
   • Wykonanie: Aktualizacja licznika rozkazów (PC) na wartość ADDR.
   • Dostęp do pamięci: Brak dostępu do pamięci.
   • Zapis wyniku: Brak operacji zapisu wyniku, ponieważ wynik został już zaktualizowany w liczniku rozkazów (PC).

6. JNZERO R1, ADDR:

   • Pobieranie: Procesor pobiera rozkaz JZERO z pamięci.
   • Dekodowanie: Dekodowanie rozkazu JZERO i identyfikacja rejestru R1 oraz adresu ADDR.
   • Wykonanie: Sprawdzenie, czy wartość w rejestrze R1 wynosi 0.
   • Dostęp do pamięci: Brak dostępu do pamięci.
   • Zapis wyniku: Jeśli wartość w rejestrze R1 wynosi 0, aktualizacja licznika rozkazów (PC) o wartość ADDR. W przeciwnym razie PC zostaje zwiększone do kolejnego rozkazu.

Dla każdego z tych rozkazów analiza cyklu rozkazowego obejmuje omówienie poszczególnych faz (pobieranie, dekodowanie, wykonanie, dostęp do pamięci i zapis wyniku) oraz zrozumienie, jak procesor wykonuje te rozkazy sekwencyjnie. W przypadku procesorów z potokiem rozkazowym, kolejne rozkazy mogą być przetwarzane równocześnie w różnych fazach, zwiększając przepustowość procesora i efektywnie przyspieszając wykonywanie programu.

Prosty symulator cyklu rozkazowego

Lab_06:

Ćwiczenie:

1. Proszę uruchomić pierwszy program: Lab_06_a
2. Proszę opisać kolejne cykle rozkazowe, jakie wykonuje procesor

1
2
3
4
5
6
7

memory = [10, 6, 7, 2, 1, 0, 0]
instructions = [
    ("LOAD",  0, 0),
    ("LOAD",  1, 2),
    ("ADD",   0, 1),
    ("STORE", 0, 0),
]

3. Proszę uruchomić drugi program: Lab_06_b

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

memory = [10, 6, 7, 2, 1, 0, 0]
instructions = [
    ("LOAD",  0, 0),
    ("LOAD",  1, 2),
    ("ADD",   0, 1),
    ("STORE", 0, 0),

    ("LOAD",  3, 1),
    ("LOAD",  2, 3),
    ("SUB",   3, 2),
    ("STORE", 1, 3),

    ("JNZERO", 3, -9),
]

4. Proszę opisać cykle rozkazowe dla ostatniej instrukcji.
5. Jakie jest działa drugi program? Proszę opisać.

Analiza potoku rozkazowego:

Potok rozkazowego i jego cele (zwiększenie przepustowości, równoległe wykonanie rozkazów).

Potok rozkazowy (ang. instruction pipeline) to technika wykorzystywana w mikroarchitekturze procesorów, mająca na celu zwiększenie przepustowości i wydajności przez równoczesne wykonywanie kilku rozkazów w różnych etapach ich przetwarzania. Potok rozkazowy dzieli cykl rozkazowy na kilka etapów, z których każdy może być przetwarzany równocześnie przez różne jednostki wykonawcze procesora. Dzięki temu, zamiast czekać na zakończenie jednego rozkazu, procesor może przetwarzać kolejne rozkazy, zwiększając przepustowość i efektywnie przyspieszając wykonywanie programu.

Cele potoku rozkazowego:

1. Zwiększenie przepustowości: Potok rozkazowy pozwala na równoczesne przetwarzanie kilku rozkazów w różnych etapach cyklu rozkazowego, co zwiększa przepustowość procesora i pozwala na szybsze wykonanie programu.

2. Równoległe wykonanie rozkazów: Potok rozkazowy pozwala na równoczesne wykonywanie różnych operacji w różnych jednostkach wykonawczych procesora, co oznacza, że procesor może jednocześnie wykonywać operacje na różnych danych, zwiększając wydajność obliczeń.

Przykład potoku rozkazowego

Załóżmy, że mamy prosty procesor z czterema etapami cyklu rozkazowego: pobieranie (IF - Instruction Fetch), dekodowanie (ID - Instruction Decode), wykonanie (EX - Execute) i zapis wyniku (WB - Write Back). Potok rozkazowy dla tego procesora będzie miał cztery etapy, które można wykonać równocześnie dla różnych rozkazów.

1
2
3
4

  Rozkaz 1: IF -> ID -> EX -> WB
  Rozkaz 2:    -> IF -> ID -> EX -> WB
  Rozkaz 3:          -> IF -> ID -> EX -> WB
  Rozkaz 4:                -> IF -> ID -> EX -> WB

Jak widać na powyższym przykładzie, potok rozkazowy pozwala na równoczesne przetwarzanie kilku rozkazów w różnych etapach cyklu rozkazowego. W momencie, gdy pierwszy rozkaz jest w fazie wykonania (EX), drugi rozkaz jest w fazie dekodowania (ID), a trzeci rozkaz jest pobierany (IF). Dzięki temu procesor może jednocześnie pracować nad różnymi rozkazami, zwiększając swoją przepustowość i wydajność.

Jednakże, potok rozkazowy wprowadza również pewne wyzwania, takie jak zarządzanie hazardami (ang. hazards). Hazardy to sytuacje, w których wynik jednego rozkazu jest potrzebny przez następny rozkaz, a potok rozkazowy musi zarządzać tymi zależnościami, aby uniknąć konflikty lub zależności.

Istnieją trzy główne rodzaje hazardów:

1. Hazardy strukturalne: Występują, gdy różne rozkazy próbują jednocześnie korzystać z tego samego zasobu procesora, takiego jak jednostka wykonawcza, pamięć czy rejestry. Hazardy strukturalne mogą prowadzić do opóźnień lub konieczności oczekiwania przez niektóre rozkazy na dostęp do zasobów.

   Sposoby minimalizowania hazardów strukturalnych:

   1. Wprowadzenie dodatkowych zasobów: Zwiększenie liczby jednostek wykonawczych, pamięci czy rejestrów może zmniejszyć ryzyko wystąpienia konfliktów.
   2. Replikacja zasobów: Dodatkowe zasoby pozwalają na równoczesne korzystanie z nich przez różne rozkazy.
   3. Wykorzystanie buforów i kolejkowania: Buforowanie i kolejkowanie operacji może pomóc w zarządzaniu dostępem do zasobów i zmniejszyć opóźnienia.

2. Hazardy danych: Występują, gdy jeden rozkaz jest zależny od wyniku innego rozkazu, który jeszcze nie został zakończony. Hazardy danych mogą prowadzić do nieprawidłowych wyników, jeśli nie zostaną odpowiednio obsłużone.

   Sposoby minimalizowania hazardów danych:

   1. Przesunięcie potoku (stalling): Wstrzymywanie wykonywania zależnego rozkazu aż do momentu, gdy wynik potrzebny dla tego rozkazu będzie dostępny.
   2. Przekształcanie potoku (forwarding): Przekazanie wyniku zależnego rozkazu bezpośrednio do kolejnego rozkazu, bez konieczności zapisywania wyniku w rejestrze.
   3. Przeplanowanie rozkazów: Kompilator lub procesor może próbować zmienić kolejność rozkazów, aby zmniejszyć zależności i poprawić wydajność potoku rozkazowego.

3. Hazardy kontroli: Występują, gdy kolejność wykonywania rozkazów ulega zmianie z powodu instrukcji warunkowych, takich jak skoki czy instrukcje warunkowe. Hazardy kontroli mogą prowadzić do niepotrzebnego wypełnienia potoku rozkazów i straty wydajności.

Ref:

• Branch prediction examples

Sposoby minimalizowania hazardów kontroli:

1. Przewidywanie rozgałęzień (branch prediction): Procesor próbuje przewidywać, czy dane rozgałęzienie zostanie wykonane, i wstępnie ładuje odpowiednie rozkazy do potoku rozkazowego.
2. Opóźnianie rozgałęzienia (branch delay slot): Procesor pozwala na wykonanie jednego lub kilku rozkazów po instrukcji rozgałęzienia, zanim rzeczywista zmiana przepływu sterowania zostanie wprowadzona. Kompilator może umieścić niezależne rozkazy w tych opóźnionych miejscach, aby zmniejszyć straty wydajności spowodowane hazardami kontroli.
3. Wykonanie spekulatywne (speculative execution): Procesor wykonuje obie ścieżki po rozgałęzieniu warunkowym, jednocześnie śledząc poprawność wyników. Gdy warunek rozgałęzienia zostanie ostatecznie wyznaczony, procesor odrzuca wyniki niewłaściwej ścieżki i kontynuuje wykonanie poprawnej ścieżki.

Ref: Interesująca podatność związana z SE (side-channel) - Spectre - wiki Spectre Attacks: Exploiting Speculative Execution Meltdown Security Vulnerability Meltdown Proof-of-Concept

Podatność Spectre dotyczy złośliwego wykorzystania spekulatywnego wykonania instrukcji przez procesor w celu uzyskania dostępu do poufnych informacji.

Przetwarzanie wielowątkowe (multithreading): Procesor może przełączać się między różnymi wątkami wykonawczymi, gdy napotyka hazardy kontroli. Pozwala to na utrzymanie potoku rozkazowego aktywnym i wydajnym, nawet gdy jeden wątek oczekuje na wynik rozgałęzienia.

W praktyce zaawansowane mikroarchitektury procesorów stosują różne techniki, aby zarządzać hazardami potoku rozkazowego i zwiększać wydajność procesora. Optymalizacja wykorzystania potoku rozkazowego, zarządzanie hazardami oraz przyspieszenie wykonywania programów są kluczowe dla osiągnięcia wysokiej wydajności w nowoczesnych procesorach.

Przykładowe sposoby minimalizacji hazardów

1. Hazard strukturalny: Załóżmy, że mamy procesor z jednym modułem ALU (Arithmetic Logic Unit) i poniższymi rozkazami do wykonania:

1
2
3

Rozkaz 1: ADD R1, R2, R3
Rozkaz 2: MUL R4, R5, R6
Rozkaz 3: SUB R7, R8, R9

Wszystkie trzy rozkazy wymagają dostępu do ALU. W celu zapobieżenia hazardom strukturalnym, procesor może:

1. Wprowadzić dodatkowe moduły ALU, aby umożliwić równoczesne wykonywanie różnych operacji.

2. Zastosować buforowanie i kolejkowanie operacji, aby zarządzać dostępem do ALU i zmniejszyć opóźnienia.

3. Hazard danych: Załóżmy, że mamy następujący ciąg rozkazów:

1
2
3

Rozkaz 1: ADD R1, R2, R3
Rozkaz 2: SUB R4, R1, R5
Rozkaz 3: MUL R6, R4, R7

Wynik rozkazu 1 (ADD) jest używany jako wejście dla rozkazu 2 (SUB), a wynik rozkazu 2 jest używany jako wejście dla rozkazu 3 (MUL). W celu zarządzania hazardami danych, procesor może:

1. Wstrzymać wykonywanie rozkazu 2 (stalling), aż do momentu, gdy wynik rozkazu 1 będzie dostępny.

2. Zastosować przekształcanie potoku (forwarding), przekazując wynik rozkazu 1 bezpośrednio do rozkazu 2, bez konieczności zapisywania wyniku w rejestrze.

3. Hazard kontroli: Załóżmy, że mamy następujący ciąg rozkazów z instrukcją warunkowego skoku:

1
2
3
4

Rozkaz_1: CMP R1, R2
Rozkaz_2: JNE label
Rozkaz_3: ADD R3, R4, R5
label:    MUL R6, R7, R8

W przypadku hazardu kontroli spowodowanego przez instrukcję warunkowego skoku (JNE), procesor może:

1. Zastosować przewidywanie rozgałęzień (branch prediction), próbując przewidzieć, czy skok zostanie wykonany, i wstępnie ładując odpowiednie rozkazy do potoku rozkazowego.
2. Wykorzystać opóźnienie rozgałęzienia (branch delay slot), umieszczając jeden lub więcej niezależnych rozkazów po instrukcji skoku, które zostaną wykonane przed rzeczywistym skokiem

W praktyce, zaawansowane mikroarchitektury procesorów stosują różne techniki, aby zarządzać hazardami potoku rozkazowego i zwiększać wydajność procesora, takie jak przewidywanie rozgałęzień, optymalizacja wykonywania potoku czy wykorzystanie wielowątkowości.

Zadanie z symulacją: symulator potoku rozkazowego dla prostego procesora, uwzględniając hazardy.

Hazard danych

Prosty procesor z potokiem rozkazowym o 4 etapach (IF - pobieranie rozkazu, ID - dekodowanie, EX - wykonanie, WB - zapis wyniku)

Lab_07

Powyższy symulator wykonuje sekwencję rozkazów (program) na prostym procesorze. Wprowadza wstrzymanie (stalling) potoku, gdy wykryje hazard danych, co pozwala na zaktualizowanie wartości rejestru przed przekazaniem go do kolejnego rozkazu. Symulator wyświetla etap potoku dla każdego rozkazu oraz numer cyklu. Po zakończeniu symulacji wyświetlane są końcowe wartości rejestrów procesora.

Hazard kontroli

Symulator prostego procesora z uwzględnieniem hazardu kontroli (branch hazard). Procesor ten ma prosty potok rozkazów o pięciu etapach: pobieranie rozkazu (IF), dekodowanie (ID), wykonanie (EX), dostęp do pamięci (MEM) i zapis wyniku (WB).

Lab_07 + branch predictor

Symulator wykonuje sekwencję rozkazów na prostym procesorze z potokiem rozkazowym. Wprowadza wstrzymanie (stalling) potoku, gdy wykryje hazard kontroli (branch hazard), co pozwala na zaktualizowanie wartości PC przed pobraniem kolejnego rozkazu. Symulator wyświetla etap potoku dla każdego rozkazu oraz numer cyklu. Po zakończeniu symulacji wyświetlane są końcowe wartości rejestrów procesora.

Instruction reordering

Uwaga: Warto zauważyć, że efekty takie jak reordering instrukcji są zależne od architektury procesora, a w przypadku niektórych implementacji może być trudno uzyskać te efekty w sposób powtarzalny.

Oto prosty program w C++, który ilustruje reordering instrukcji na procesorze x86:

Lab_10

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

// Set either of these to 1 to prevent CPU reordering
#define USE_CPU_FENCE              0
#define USE_SINGLE_HW_THREAD       0  // Supported on Linux, but not Cygwin or PS3

#if USE_SINGLE_HW_THREAD
#include <sched.h>
#endif


//-------------------------------------
//  MersenneTwister
//  A thread-safe random number generator with good randomness
//  in a small number of instructions. We'll use it to introduce
//  random timing delays.
//-------------------------------------
#define MT_IA  397
#define MT_LEN 624

class MersenneTwister
{
    unsigned int m_buffer[MT_LEN];
    int m_index;

public:
    MersenneTwister(unsigned int seed);
    // Declare noinline so that the function call acts as a compiler barrier:
    unsigned int integer() __attribute__((noinline));
};

MersenneTwister::MersenneTwister(unsigned int seed)
{
    // Initialize by filling with the seed, then iterating
    // the algorithm a bunch of times to shuffle things up.
    for (int i = 0; i < MT_LEN; i++)
        m_buffer[i] = seed;
    m_index = 0;
    for (int i = 0; i < MT_LEN * 100; i++)
        integer();
}

unsigned int MersenneTwister::integer()
{
    // Indices
    int i = m_index;
    int i2 = m_index + 1; if (i2 >= MT_LEN) i2 = 0; // wrap-around
    int j = m_index + MT_IA; if (j >= MT_LEN) j -= MT_LEN; // wrap-around

    // Twist
    unsigned int s = (m_buffer[i] & 0x80000000) | (m_buffer[i2] & 0x7fffffff);
    unsigned int r = m_buffer[j] ^ (s >> 1) ^ ((s & 1) * 0x9908B0DF);
    m_buffer[m_index] = r;
    m_index = i2;

    // Swizzle
    r ^= (r >> 11);
    r ^= (r << 7) & 0x9d2c5680UL;
    r ^= (r << 15) & 0xefc60000UL;
    r ^= (r >> 18);
    return r;
}


//-------------------------------------
//  Main program, as decribed in the post
//-------------------------------------
sem_t beginSema1;
sem_t beginSema2;
sem_t endSema;

int X, Y;
int r1, r2;

void* thread1Func(void* param)
{
    MersenneTwister random(1);
    for (;;)
    {
        sem_wait(&beginSema1);  // Wait for signal
        while (random.integer() % 8 != 0) {}  // Random delay

        // ----- THE TRANSACTION! -----
        X = 1;
#if USE_CPU_FENCE
        asm volatile("mfence" ::: "memory");  // Prevent CPU reordering
#else
        //asm volatile("" ::: "memory");  // Prevent compiler reordering
#endif
        r1 = Y;

        sem_post(&endSema);  // Notify transaction complete
    }
    return NULL;  // Never returns
};

void* thread2Func(void* param)
{
    MersenneTwister random(2);
    for (;;)
    {
        sem_wait(&beginSema2);  // Wait for signal
        while (random.integer() % 8 != 0) {}  // Random delay

        // ----- THE TRANSACTION! -----
        Y = 1;
#if USE_CPU_FENCE
        asm volatile("mfence" ::: "memory");  // Prevent CPU reordering
#else
        //asm volatile("" ::: "memory");  // Prevent compiler reordering
#endif
        r2 = X;

        sem_post(&endSema);  // Notify transaction complete
    }
    return NULL;  // Never returns
};

int main()
{
    // Initialize the semaphores
    sem_init(&beginSema1, 0, 0);
    sem_init(&beginSema2, 0, 0);
    sem_init(&endSema, 0, 0);

    // Spawn the threads
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread1Func, NULL);
    pthread_create(&thread2, NULL, thread2Func, NULL);

#if USE_SINGLE_HW_THREAD
    // Force thread affinities to the same cpu core.
    cpu_set_t cpus;
    CPU_ZERO(&cpus);
    CPU_SET(0, &cpus);
    pthread_setaffinity_np(thread1, sizeof(cpu_set_t), &cpus);
    pthread_setaffinity_np(thread2, sizeof(cpu_set_t), &cpus);
#endif

    // Repeat the experiment ad infinitum
    int detected = 0;
    for (int iterations = 1; ; iterations++)
    {
        // Reset X and Y
        X = 0;
        Y = 0;
        // Signal both threads
        sem_post(&beginSema1);
        sem_post(&beginSema2);
        // Wait for both threads
        sem_wait(&endSema);
        sem_wait(&endSema);
        // Check if there was a simultaneous reorder
        if (r1 == 0 && r2 == 0)
        {
            detected++;
            printf("%d reorders detected after %d iterations\n", detected, iterations);
        }
    }
    return 0;  // Never returns
}