asembler

Przedmiot jest przeznaczony dla studentów zainteresowanych szczegółowym poznaniem architektury wewnętrznej współczesnego komputera. Głównym celem wykładu jest nauczenie studentów tworzenia bardzo wydajnego kodu i odpowiedniego projektowania budowy wewnętrznej struktur danych, co ma kluczowe znacznie w realistycznej grafice komputerowej, cyfrowym przetwarzaniu sygnałów (m.in. modelowanie przestrzenne dźwięku) i programowaniu systemowym. Zostaną też poruszone zagadnienia związane z pisaniem sterowników dla systemu Windows/Linux.

wymagane przygotowanie
  • umiejętność programowania w języku C/C++
materiały elektroniczne

powrót na początek strony

Terminarz

  • wykład: poniedziałek 19:00-20:30 s.119 (P.Wyderski)
  • laboratorium:
    wtorek 18-20 s.108 (P.Rzechonek)
    czwartek 8-10 s.108 (P.Witkowski)

powrót na początek strony

Laboratorium

zasady zaliczenia przedmiotu
ogólnie:
W semestrze będzie opublikowanych (na tej stronie) kilkanaście prostych zadań do zaprogramowania lub przygotowania w formie pisemnej (referat, rozwiązanie zadania teoretycznego). Za każde poprawnie zrobione zadanie i oddane w terminie można będzie dostać 10 punktów.
terminy:
Zadania będą ogłaszane w tygodniu poprzedzającym termin ich realizacji. Zadania należy oddawać w wyznaczonym terminie. Spóźnienia nie będą tolerowane, za wyjątkiem uzasadnionych sytuacji: choroba potwierdzona zwolnieniem lekarskim, wezwanie do Sądu, itp.
prezentacje:
Programy należy prezentować osobiście w czasie pracowni (proszę nie wysyłać programów pocztą elektroniczną, ani nie przekazywać ich poprzez kolegów i koleżanki). W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi zadania: metoda rozwiązania, zastosowane konstrukcje językowe, itp.
oceny:
Aby zaliczyć laboratorium na ocenę dostateczną trzeba do końca semestru zdobyć 50% z wszystkich możliwych do uzyskania punktów; na ocenę bardzo dobra trzba będzie zgromadzić 90% punktów; oceny pośrednie pozostją w liniowej zależności od przedstawionych wymagań granicznych.
listy zadań
  1. 6.03.2007: referat o DMA (10 punktów)
    Opisz działanie mechanizmu DMA na przykładzie:
    1. Ultra-DMA
    2. ISA
    3. PCI
    4. PCI-Express
    5. AGP
    Wersja referatu jest przydzielona zgodnie z numerem indeksu: przystawanie modulo 5.
    Uwaga: referat należy przygotować w postaci papierowej (pisemnej lub drukowanej).
  2. 13.03.2007: zadanie o zmiennoprzecinkowej postaci liczb (10 punktów)
    Opisz format zapisu binarnego liczb typu float i double w języku C, które są kodowane zgodnie ze standardem IEEE-754. Następnie wykaż, że jeśli w liczbie zmiennoprzecinkowej x typu float zanegujemy wszystkie bity, to otrzymamy liczbę x’, która jest w przybliżeniu równa -4/x. Wylicz, jaka jest dokładność otrzymanego wyniku.
    Uwaga: rozwiązanie zadania należy przygotować w postaci papierowej (pisemnej lub drukowanej).
  3. 20.03.2007: proste procedury w asemblerze (10 punktów)
    Wybierz sobie do 3 zadań i zaprogramuj je w asemblerze.
    1. (1 punkt) Napisz procedurę, która wyznaczy wartość bezwzględną z liczby.
          int abs (int x);
    2. (1 punkt) Napisz procedurę, która wyznaczy znak liczby (-1 gdy liczba jest ujemna, +1 gdy jest dodatnia i 0 gdy jest zerem).
          int sgn (int x);
    3. (2 punkty) Napisz procedurę, która wykona operację bitową na dostarczonych do niej argumentach. Kod operacji (1 to AND, 2 XOR i 3 OR) na być jednym z argumentów.
          int bitcalc (int op1, int op2, int kod);
    4. (1 punkt) Napisz procedurę, która wyznaczy maksimum spośród dwóch liczb.
          int max2 (int op1, int op2);
    5. (2 punkty) Napisz procedurę, która wyznaczy medianę spośród trzech liczb.
          int med3 (int op1, int op2, int op3);
    6. (3 punkty) Napisz procedurę, która wyznaczy minimum spośród czterech liczb.
          int min4 (int op1, int op2, int op3, int op4); Do obliczeń wykorzystaj procedurę obliczającą minimum z dwóch liczb (wywołanie innej procedury).
          int min2 (int op1, int op2);
    7. (3 punkty) Napisz procedurę, która wyznaczy numer najmłodszego zgaszonego bitu w słowie.
          int ind0 (int w);
    8. (3 punkty) Napisz procedurę, która policzy liczbę szystkich zapalonych bitów w słowie.
          int cnt1 (int w);
    9. (4 punkty) Napisz procedurę, która sprawdzi w stałej liczbie kroków, czy podana liczba jest potęgą 2 (0 gdy nie jest albo 1 gdy jest potęgą 2).
          int pow2 (int x);
    10. (3 punkty) Napisz procedurę, która posumuje wszystkie liczny naturalne ≤n (dodawanie w pętli).
          int sum (int n);
    11. (4 punkty) Napisz iteracyjną procedurę, która obliczy n-tą liczbę Fibonacciego (F0=0, F1=1, Fn=Fn-1+Fn-2 dla n≥2).
          int fibit (int n);
    12. (5 punktów) Napisz rekurencyjną procedurę, która obliczy n-tą liczbę Fibonacciego (F0=0, F1=1, Fn=Fn-1+Fn-2 dla n≥2).
          int fibrec (int n);
    Uwaga 1: procedury w asemblerze skompiluj używając kompilatora nasm; programy testujące napisz w języku C i skompiluj kompilatorem gcc; powstałe moduły zlinkuj na końcu przy pomocy gcc.
    Uwaga 2: nie wolno używać operacji znajdujących pierwszy zapalony bit BSF i BSR.
  4. 27.03.2007: operacje na długich liczbach naturalnych (10 punktów)
    Napisz w asemblerze bibliotekę do operacji arytmetycznych na długich liczbach naturalnych. Nie ma to być arytmetyka o ustalonej precyzji, tylko o precyzji zmiennej - w każdej operacji należy podać długość operandów n, czyli liczbę 32-bitowych słów z których zbudowany jest każdy operand. Biblioteka ta ma realizować następujące operacje:
    1. (0 punktów) zerowanie liczby (jak przypisanie =0)
          void assign0 (int n, int *dst); // dst = 0
      funkcja nie zwraca żadnej wartości;
    2. (1 punkt) kopiowanie liczby (jak operator podstawienia =)
          void assign (int n, int *dst, int *src); // dst = src
      funkcja nie zwraca żadnej wartości;
    3. (1 punkt) porównanie liczby z 0 (tak jak ==0)
          int comp0 (int n, int *op); // op == 0
      wynikiem jest wartość 0 gdy operand jest zerem albo 1 gdy operand nie jest zerem;
    4. (1 punkt) porównanie dwóch liczb (jak operatory porównań <, <=, >, >=, == i !=)
          int comp (int n, int *op1, int *op2); // op1 ? op2
      wynikiem jest wartość -1 gdy op1>op2, +1 gdy op1<op2 albo 0 gdy operandy są równe (na podstawie powyższej funkcji napisz kolekcję sześciu operatorów porównujących lt, lteq, gt, gteq, eq i neq);
    5. (2 punkty) przesunięcia bitowe o jedną pozycję (tak jak <<1 i >>1)
          void rshift (int n, int *op); // op <<= 1
          void lshift (int n, int *op); // op >>= 1
      wynik jest umieszczany bezpośrednio w operandzie (rshift jest równoważne z pomnożeniem przez 2 a lshift z podzieleniem przez 2);
    6. (2 punkty) dodawanie i odejmowanie (tak jak += i -=)
          void add (int n, int *op, int *oper); // op += oper
          void sub (int n, int *op, int *oper); // op -= oper
      wynik jest umieszczany bezpośrednio w pierwszym operandzie;
    7. (3 punkty) czytanie i pisanie liczb w postaci szestanstkowej (operacje na tablicach znakowych)
          void read (int n, int *op, char *in); // czytanie
          void write (int n, int *op, char *out); // pisanie
      napisy w konwencji C (ze znakiem o kodzie 0 na końcu).
    Na podstawie zdefiniowanych operacji na długich liczbach zaprogramuj wysokopoziomowo mnożenie długich liczb po rosyjsku. Wykorzystaj te operacje do obliczenia 100! na liczbach 1024-bitowych.
  5. 3.04.2007: operacje na liczbach zespolonych (10 punktów)
    Załóżmy, że typ liczb zespolonych w postaci algebraicznej jest zdefiniowany następująco: 
        typedef struct
    {
        double re;
        double im;
    } complex;
    Zaprogramuj poniższe zadania w asemblerze i sprawdź ich działanie w programie testowym w języku C.
    1. (1 punkt) Napisz funkcję sprawdzającą równość dwóch liczb zespolonych.
          bool eq (complex a, complex b);
    2. (2 punkty) Napisz procedury konwersji pomiędzy dwiema reprezentacjami liczb zespolonych: algebraiczną z = Re(z) + i*Im(z) i trygonometryczną z = |z| * (cos(arg(z)) + i*sin(arg(z))). Zapoznaj się z opisem instrukcji FPATAN i FSINCOS i użyj ich w swoim rozwiązaniu.
          void alg2try (complex z, double *arg, double *r);
          void try2alg (double arg, double r, complex *z);
    3. (3 punkty) Napisz funkcje wykonujące operacje dodawania, odejmowania, mnożenia i dzielenia dwóch liczb zespolonych w postaci algebraicznej.
          void add (complex a, complex b, complex *result);
          void sub (complex a, complex b, complex *result);
          void mul (complex a, complex b, complex *result);
          void div (complex a, complex b, complex *result); // b != 0
    4. (4 punkty) Napisz funkcję obliczającą wartość wielomianu W(x) w zadanym punkcie x wykorzystując schemat Hornera: W(x) = w0 + x*(w1 + x*(...(wn-1 + x*wn)...)). Napisz osobną wersję procedury dla liczb rzeczywistych i osobną dla liczb zespolonych.
          void horner_real (int n, double *w, double x, double *result);
          void horner_comp (int n, complex *w, complex x, complex *result);
  6. 17.04.2007: kalkulator ONP (10 punktów)
    Ciąg instrukcji assgns zdefiniowany jest następująco:
    • assgns to ciąg instrukcji przypisania zakończonych znakiem średnika ;
          assgns := assgn assgns | assgn ;
          assgn := variable = exprs
    • exprs to wyrażenie zapisane w postaci ONP
          exprs := atom exprs | atom
          atom := variable | number | operator
          operator := + | - | * | / | ^ | Sin | Cos | Arctan | Log | Exp
          variable to mała litera alfabetu łacińskiego a...z
          number to liczba typu double bez znaku zapisywana w notacji z kropką dziesiętną
    Zaprogramuj w asemblerze prosty kalkulator ONP ze zmiennymi:
            int calcONP (char *assgns, double *symtbl);
    Zadaniem kalkulatora jest obliczenie wartości ciągu wyrażeń i zapamiętaniu wyników w tablicy ze zmiennymi. Wyrażenie ONP assgns jest przekazywane do procedury jako znaków, w którym wszystkie symbole są pooddzielane spacjami (co najmniej jedną). Do procedury przekazywana jest też tablica zmiennych symtbl (26 komórek, gdzie pierwsza komórka odpowiada zmiennej a, a ostatnia zmiennej z); zadaniem procedury jest zmiana wartości tych zmiennych na podstawie wyrażenia ONP. Funkcja calcONP zwraca wartość int, która ma informować o poprawności wyrażenia ONP przekazanego do procedury (0 gdy całe wyrażenie było poprawne, albo wartość p>0 gdy wykryto pierwszy błąd na pozycji p).
  7. 24.04.2007: procedury systemowe (10 punktów)
    Poniższe zadania zaprogramuj całkowicie w asemblerze (funkcja main powinna uruchamiać tylko jedną procedurę). Programy kompiluj i uruchamiaj pod kontrolą systemu Linux. Wykorzystaj funkcje systemowe dostępne za pomocą przerwania int 0x80.
    1. (1 punkt) Napisz funkcję, która wypisze na standardowym wyjściu numer identyfikacyjny procesu (pobranie pid - funkcja nr 20, wypisanie komunikatu na ekranie - funkcja nr 4).
    2. (2 punkty) Napisz funkcję, która wydrukuje na standardowym wyjściu tabelę kodów znaków ASCII od 32 do 126.
    3. (4 punkty) Napisz funkcję, która wypisze bieżącą datę i czas po polsku (miesiąc i dzień tygodnia wypisz słownie).
    4. (3 punkty) Napisz funkcję, która wczyta liczbę dziesiętną (32-bitowa liczba całkowita ze znakiem) i wypisze ją w postaci binarnej.
    Opis funkcji systemowych oraz ich wykorzystanie w programowaniu w asemblerze pod Linuxem możesz znaleźć w internecie.
  8. 8.05.2007: test cache'a (10 punktów)
    Napisz program do badania wydajności dostępu do pamięci operacyjnej z wykorzystaniem pamięci podręcznej. Program powinien wielokrotnie przenosić dane pomiędzy dużymi blokami pamięci. Zwiększaj stopniowo (w postępie geometrycznym) rozmiary bloków redukując jednocześnie liczbę iteracji - zacznij od bloków o rozmiarze 4KB z 16384 powtórzeniami a zakończąc na 16MB z 4 powtórzeniami. Wykonaj pomiary czasu każdej fazy i wpisz je do tabeli. Przenoszenie danych wykonaj na dwa sposoby:
    • liniowo (kopiuj po kolei od pierwszego do ostatniego słowa);
    • pseudolosowo (pozycje słów do zamiany wyznaczaj na podstawie opracowanego schematu gwarantującego duży rozrzut adresów).
    Zrób wykres wydajności czasowej na podstawie otrzymanych danych i wyciągnij wnioski. Czy potrafisz na podstawie tych wyników prawidłowo określić rozmiar pamięci cache?
  9. 15.05.2007: modyfikacje plików graficznych PPM (10 punktów)
    W każdym z poniższych zadań funkcję główną należy napisać w asemblerze, zaś plikowe operacje wejścia/wyjścia w języku C. Proszę stosować instrukcje MMX wszędzie tam, gdzie jest to uzasadnione.
    1. (3 punkty) Dany jest obraz P (plik w formacie PPM). Napisz funkcję
          void brighten (struct pixmap *P, unsigned char d, bool switch); która zwiększy jasność obrazu P o wartość d, czyli doda d do każdej z trzech składowych każdego pixela obrazu. Wartość boolowska switch informuje, czy należy wykorzystać tryb nasyceniowy.
    2. (3 punkty) Dane są obrazy P, Q oraz maska bitowa M (pliki w formacie PPM) o jednakowych wymiarach. Napisz funkcję
          void doMask (struct pixmap *P, struct pixmap *Q, struct pixmap *M); nakładającą maskę M na obraz Q i umieszczającą tak powstałą figurę geometryczną w obrazie P. Bardziej formalnie: niech p, q, m będą pikselami obrazów P, Q, M o tych samych współrzędnych; należy zaprogramować operację p := (!m and p) or (m and q) dla wszystkich pikseli.
    3. (4 punkty) Dane są obrazy P i Q (pliki w formacie PPM) o jednakowych wymiarach. Należy zaprogramować animację efektu przejścia obrazu P w Q (alpha-blending). Program, którego wynikiem będzie ciąg kolejnych klatek animacji należy napisać w języku C, natomiast procedurę obliczającą następną klatkę w asemblerze. Bardziej formalnie: niech p, q będą pikselami obrazów P, Q o tych samych współrzędnych; dla parametru w z przedziału [0,1] pikselem klatki K(w) będzie w*p+(1-w)*q; program powinien produkować ciąg plików K(1.0), K(0.9),... K(0.1), K(0.0) (albo ze skokiem co 0.05).
    Specyfikacja formatu PPM: http://netpbm.sourceforge.net/doc/ppm.html (proszę zignorować punkt 10 tej specyfikacji i przyjąć, że piksele zapamiętane są w formacie RGB).
    Przykładowa przeglądarka i konwerter grafiki PPM: http://www.filetrial.com/download/abc-filetrial.exe.
  10. 22.05.2007: instrukcje SIMD oraz arytmetyzacja (10 punktów)
    Instrukcje SIMD pozwalają na równoległe wykonywanie operacji arytmetyczo-logicznych na wektorach z danymi. Zaprogramuj w asemblerze funkcje realizujące następujące zadania:
    1. (2 punkty) wyznaczanie minimum/maksimum spośród 16-bitowych danych zapisanych w tablicy o rozmiarze będącym wielokrotnością 8;
    2. (3 punkty) przekształcenie 32-bitowych danych zapisanych w tablicy o rozmiarze będącym wielokrotnością 4 w sumy prefiksowe (w i-tej komórce ma się znaleźć suma wszystkich wyrazów od pierwszego do i-tego).
    Arytmetyzacja polega na tym, aby obliczać pewne proste funkcje bez używania instrukcji skoków. Dokonaj arytmetyzacji i zaprogramuj w asemblerze następujące funkcje, których argumentami są liczby całkowite:
    1. (3 punkty) wartość bezwzględna abs(x) i znak liczby sgn(x);
    2. (2 punkty) minimum min(x,y) i maksimum max(x,y).
  11. 29.05.2007: metoda Newtona-Raphsona (10 punktów)
    Wybierz i zaprogramuj w asemblerze jedno z zadań:
    1. (5 punktów) odwrotność liczby typu float z dokładnością do 8 bitów;
    2. (10 punktów) pierwiastek z liczby typu double z dokładnością do 16 bitów;
    Do zaprogramowania tych funkcji wykorzystaj metodę Newtona-Raphsona, o której była mowa przy okazji zadania 2.
  12. 5.06.2007: operacje SSE na łańcuchach znakowych (10 punktów)
    Zaprogramuj w asemblerze każde z poniższych zadań z wykorzystaniem operacji SSE2:
    1. (2 punkty) funkcja znajdująca adres padanego znaku w łańcuchu znakowym
      char * sse2strchr (const char *cs, int c);
    2. (4 punkty) funkcja porównująca dwa łańcuchy znakowe
      int sse2strcmp (const char *cs, const char *ct);
    3. (4 punkty) funkcja kopiująca łańcuch znakowy
      char * sse2strcpy(char *s, const char *ct);
    Następnie porównaj czasy działania zaprogramowanych przez ciebie funkcji z czasami działania analogicznych funkcji z biblioteki standardowej w języku C.
  13. 19.06.2007: obiekty synchronizujące (10 punktów)
    Zaprogramuj każde z poniższych zadań, wykorzystując wstawki asemblerowe gcc w funkcjach:
    1. (5 punktów) Zaimplementuj prosty spin-lock (semafor binarny z aktywnym czekaniem) bez żadnych gwarancji kolejności przydziału sekcji krytycznej i zastosuj go do rozwiązania problemu producentów i konsumentów (po 3 wątki każdego rodzaju). Producenci i konsumenci współdzielą listę liczb całkowitych typu int.
      Wskazówka: instukcja XCHG.
    2. (5 punktów) Zaimplementuj spin-lock przydzielający dostęp do sekcji krytycznej w porządku FIFO i użyj go do rozwiązania poprzedniego zadania.
      Wskazówka: instukcje CMPXCHG i XADD.
    Potrzebne do rozwiązania obu zadań wątki utwórz korzystając z API twojego systemu operacyjnego lub bibliotek ACE lub boost::thread.
ranking

powrót na początek strony

Ogłoszenia

6.03.2007
Rozwiązanie zadania będzie tak samo oceniane jak zadanie programistyczne!
27.02.2007
Przygotowanie referatu będzie tak samo oceniane jak zadanie programistyczne!

powrót na początek strony