INF1070
		    Oppgaver uke 19 (9.-13.5.2005)


Oppgave 1

x86-prosessoren har en innebygget 64-bits teller som teller antall
klokkesykler som er gtt siden datamaskinen ble startet sist.

a. Hvorfor er denne telleren p? 64 bit og ikke bare p? 32 bit?

b. Skriv assemblerfunksjonen

   long long unsigned cycles (void)

   som returnerer sykeltelleren. Bruk instruksjonen rdtsc (?read time
   stamp?) som legger telleren i EDX (de ?verste 32 bit-ene) og i EAX
   (de nederste 32 bit-ene).

c. Skriv funksjonen i C. Bruk asm-konstruksjonen.


Oppgaved 2

En av de aller beste sorteringsm?tene heter quicksort og kan
implementeres slik:

void quicksort (int a[], int ia, int ib)
{
  int lim = ia, t, i;

  if (ia >= ib) return;

  for (i = ia+1;  i <= ib;  ++i) {
    if (a[i] <= a[ia]) {
      ++lim;  t = a[i];  a[i] = a[lim];  a[lim] = t;
    }
  }
  t = a[ia];  a[ia] = a[lim];  a[lim] = t;
  /* Invariant: ia<=i<lim: a[i]<=a[lim].
                lim<i<=ib: a[i]>a[lim]. */
  quicksort(a,ia,lim-1);  quicksort(a,lim+1,ib);
}

Den sorterer en vektor a fra indeks ia til indeks ib ved ? splitte den
i to deler: de som er mindre eller lik a[ia] ligger f?rst (opp til
indeks lim) og alle st?rre kommer etterp?. S? byttes a[ia] og a[lim]
og quicksort kalles rekursivt p? de to halvpartene av vektoren.

a. Oversett funksjonen quicksort til x86-kode.

  Hint: Instruksjonen pushal kan v?re nyttig ved rekursive kall. Les
  om denne instruksjonen (som kalles pushad i boken) i avsnitt 5.4.2.4
  i Irvine-boken.

  Hint: Instruksjonen xchgl kan v?re nyttig i denne oversettelsen. Les
  om instruksjonen i avsnitt 4.1.7 i Irvine-boken.

b. Ta utgangspunkt i C-funksjonen over og skriv l?kken i assemblerkode
  (for ? se om vi kan f? koden raskere). Bruk asm-konstruksjonen:

void quicksort (int a[], int ia, int ib)
{
  int lim = ia, t, i;

  if (ia >= ib) return;

  asm(...);

  /* Invariant: ia<=i<lim: a[i]<=a[lim].
                lim<i<=ib: a[i]>a[lim]. */
  quicksort(a,ia,lim-1);  quicksort(a,lim+1,ib);
}


Oppgave 3

Bruk funksjonen cycles fra oppgave 1 til ? avgj?re hvilken av de tre
implementasjonene av quicksort som er raskeste: C, assemblerkode eller
C/asm.