ASK (Architektury systemów komputerowych)SO (Systemy operacyjne)
Grupy efektów kształcenia
Architektury systemów komputerowychSystemy operacyjne
Opis przedmiotu:
Celem wykładu jest przedstawienie studentom najważniejszych idei, algorytmów i struktur danych wykorzystywanych w systemach komputerowych, głównie w sprzęcie, systemach operacyjnych i narzędziach systemowych.
**Uwaga**: Mimo, iż przedmiot pokrywa efekty kształcenia przedmiotów ASK i SO, to podejście do poruszanych tematów jest zasadniczo odmienne. Ten wykład skierowany jest głównie do studentów z zacięciem teoretycznym.
Zasady przyznawania punktów dla osób, które zaliczyły już przynajmniej jeden z powyższych przedmiotów:
1. Osoby, które zaliczyły ASK oraz SO, otrzymają za SyK 0 ECTS, a
2. Osoby, które zaliczyły ASK albo SO, otrzymają za SyK 4 ECTS.
Program wykładu opracowano wspólnie z **Krystianem Bacławskim**.
### Tematy wykładów
1. Sprzętowa implementacja operacji arytmetycznych: szybkie algorytmy dodawania (sumatory carry-lookahead i Ling'a), mnożenia (drzewa Wallace'a i kodowanie Booth'a) i dzielenia (non-restoring division, SRT division).
2. Niskopoziomowa reprezentacja programów (kod trójadresowy, graf przepływu sterowania), analiza przepływu danych (obliczenia stałopunktowe).
3. Architektura współczesnego procesora (przetwarzanie potokowe i *out-of-order*). Graf przepływu danych i algorytm Tomasulo.
4. Spekulatywne wykonywanie instrukcji, przewidywanie skoków (perceptron, TAGE), atak Spectre.
5. Instrumentacja kodu, profilowanie (graf wywołań funkcji) i optymalizacja kodu (algorytm
*local value numbering*).
6. Struktury pamięci podręcznych, algorytmy *cache-oblivious*.
8. Algorytmy szeregowania wątków i balansowania obciążenia procesorów (algorytm ULE, kolejka kalendarzowa).
9. Translacja adresów, wielopoziomowa i odwrócona tablica stron.
10. Pamięć wirtualna, algorytmy zastępowania stron (algorytm WSCLOCK, aging, Clock-Pro).
11. Algorytmy dynamicznego przydziału pamięci (buddy systems, boundary tags). Algorytmy odśmiecania (mark and sweep, algorytm kopiujący).
12. Struktury danych systemów plików (grupy bloków, i-node, B-drzewo, journaling). Planowanie operacji I/O (budget-fair queueing).
13. Przetwarzanie współbieżne. Implementacja środków synchronizacji (synchronizacja pamięci podręcznych, exponential backoff).
14. Kontrola przepływności w protokole TCP. Obliczanie sum kontrolnych i kodów korekcyjnych.
15. Sieci w układach scalonych: topologia i trasowanie pakietów.
