11.4 Egyszerű instrumentáció: ciklusszámlálás és időmérés

11.4.1 Motiváció: a helyes eredmény mellé mérési szerződés kell

Egy assembly rutin már helyesen számol, de szeretnénk tudni, érdemes-e tovább optimalizálni. A teljes program futásideje önmagában kevés: tartalmazhat fájlkezelést, memóriakezelést, formázott kiírást és inicializálást is. Ezek könnyen elfedik a vizsgált rutin költségét.

Az instrumentáció (instrumentation) olyan kiegészítő kód beillesztése, amely megfigyelhetővé teszi a program működését. Ebben az alfejezetben két időbélyeget veszünk egy C-ből hívott assembly rutin ismételt végrehajtása körül. A módszer előfeltétele a helyes eredmény és a szabályos memóriaelérés; ezek vizsgálatát az előző hibakeresési esettanulmány tárgyalta.

Profil: I. rész, A64 ISA, ARMv8-A, AArch64 Linux, little-endian, LP64 adatmodell. Az assembly példában minden utasítás és regiszter ehhez a profilhoz tartozik; a direktívák az AArch64 célú GNU assembler direktívái, nem processzorutasítások.

A bemutatott programot itt nem futtatjuk. A számszerű ellenőrzőösszeg levezetett érték; futási időt a hallgató laborja szolgáltat.

11.4.2 Mit mér a két időbélyeg?

A libc clock_gettime függvénye a kiválasztott óra állapotát egy struct timespec objektumba írja. Ennek két mezője:

• tv_sec: egész másodperc;
• tv_nsec: a másodpercen belüli nanomásodperc, értéke sikeres hívás után 0 és 999999999 közötti.

A libc-felület nem feltétlenül jelent minden híváskor kernelbe lépést. Natív Linuxon például vDSO-alapú gyors út is lehetséges; a konkrét végrehajtási út libc-, kernel- és emulációfüggő. A mérési szerződésünket ezért az API-ra, nem egy feltételezett belső implementációra építjük.

Időtartamhoz CLOCK_MONOTONIC órát használunk. Ez nem a naptári időt adja, és a rendszeróra ugrásszerű átállítása nem okoz benne megfelelő ugrást. Nem azonos azonban a folyamat által ténylegesen felhasznált CPU-idővel: az ütemezés miatti várakozás is növelheti a mért időt.

Levezetés. Ha a kezdő időbélyeg $(s_0,n_0)$, a záró pedig $(s_1,n_1)$, akkor:

$$T_{\mathrm{ns}}=(s_1-s_0)\cdot 10^9+(n_1-n_0).$$

Itt $s_0,s_1$ másodpercben, $n_0,n_1$ nanomásodpercben értendő, az eredmény pedig nanomásodperc. A kivonást előjeles, megfelelő szélességű típussal végezzük: másodperchatár átlépésekor $n_1-n_0$ negatív lehet, miközben a teljes időtartam pozitív.

A nanomásodperces reprezentáció nem garantál nanomásodperces felbontást vagy pontosságot.

11.4.2.1 Mi maradjon a mérési blokkon kívül?

Az adat-előkészítés, allokáció, kiírás és eredményellenőrzés ne kerüljön a két időbélyeg közé. A mérési intervallum itt szándékosan tartalmazza:

• az assembly rutin hívását és visszatérését;
• a rutin munkáját;
• a C-oldali ismétlőciklust és ellenőrzőösszeg-képzést;
• az időbélyegzés intervallumba eső járulékos költségét.

Ez tehát hívási költséggel együtt értett rutinmérés, nem egyetlen utasítás késleltetésének mérése.

Egy rövid rutint sokszor hívunk két időbélyeg között. Ha az ismétlésszám $R$, akkor a számított átlagos költség $T_{\mathrm{ns}}/R$, mértékegysége ns/hívás. Az ismétlés csökkenti az időbélyegzés egy hívásra jutó hatását, de nem távolítja el a ciklus és a függvényhívás költségét.

11.4.3 Időmérés és ciklusszámlálás nem ugyanaz

Három különböző mennyiséget kell elválasztani:

1. Algoritmikus iterációszám: például hány tömbelemet dolgozunk fel.
2. Dinamikus utasításszám: hány ISA-utasítás hajtódik végre.
3. Processzorciklusok száma: egy meghatározott hardveres számláló által számolt ciklusok.

Ezek között nincs általános, állandó szorzótényező. Egy utasítás több ciklust igényelhet, miközben egy processzor bizonyos feltételek mellett több utasítás munkáját is átfedheti.

Az A64 környezetben elérhető CNTVCT_EL0 időzítőszámláló sem általános CPU-ciklusszámláló. A teljesítményfigyelő egység ciklusszámlálójának, például az A64 PMCCNTR_EL0 regiszterének alkalmazásszintű olvashatósága pedig rendszerkonfigurációtól függ. Ezekre itt nem építünk.

QEMU alatt különösen hibás lenne a mért másodperceket egy elképzelt target-órajel frekvenciájával megszorozni, majd az eredményt AArch64 ciklusszámnak nevezni.

11.4.4 Kidolgozott példa: tömbösszegzés időméréssel

Munkakönyvtár: ~/arm-labor/a64/a043/ — az alfejezet minden laborfájlja ide kerül, és minden parancs innen futtatandó (a könyvtárrendet a Labor-alapkörnyezet alfejezet írja le).

mkdir -p ~/arm-labor/a64/a043
cd ~/arm-labor/a64/a043

Az assembly függvény előjel nélküli, 32 bites elemek összegét adja vissza előjel nélküli, 64 bites értékként. Általánosan az összeadás modulo $2^{64}$ értendő; a labor adatai mellett nincs túlcsordulás.

Az AAPCS64 szerint az A64 X0 kapja a tömbmutatót, az A64 X1 az elemszámot, a visszatérési érték pedig az A64 X0 regiszterbe kerül.

A lab-sum.S fájl:

// A64 ISA, ARMv8-A, little-endian; GNU as direktívák.
.arch armv8-a
.text
.p2align 2
.global lab_sum_u32
.type lab_sum_u32, %function

lab_sum_u32:
    mov     X2, XZR
    cbz     X1, .Llab_done

.Llab_loop:
    ldr     W3, [X0], #4
    add     X2, X2, X3
    subs    X1, X1, #1
    b.ne    .Llab_loop

.Llab_done:
    mov     X0, X2
    ret     X30

.size lab_sum_u32, .-lab_sum_u32
.section .note.GNU-stack,"",%progbits

Az A64 W3 regiszterbe írás nullázza az A64 X3 felső 32 bitjét, ezért az előjel nélküli elem helyesen kerül a 64 bites összegbe. A függvény csak hívó által mentendő munkaregisztereket módosít, és nem hív másik függvényt.

A kódolási korlátok ebben a mintában:

• Az A64 ldr utóindexelt alakjában az eltolás előjeles, 9 bites bájtérték: −256…255. A #4 belefér.
• Az A64 subs immediate alakja 12 bites előjel nélküli konstanst fogad, opcionális 12 bites balra tolással. A #1 közvetlenül kódolható.
• Az A64 cbz és b.ne elágazása előjeles, 19 bites, 4 bájttal skálázott PC-relatív eltolást használ. A közeli címkék elérhetők.

Pozitív $n$ elemszámra a függvény dinamikus utasításszáma levezethető: két kezdőutasítás, elemenként négy ciklusutasítás, végül két záróutasítás, vagyis $4n+4$. Ez utasításszám, nem processzorciklusszám.

A lab-time.c fájl:

#define _POSIX_C_SOURCE 200809L
#include <inttypes.h>
#include <math.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* C-oldal: AArch64 Linux, LP64, little-endian. */
extern uint64_t lab_sum_u32(const uint32_t *p, size_t n);

enum { N = 4096, REPEATS = 2000, SAMPLES = 9 };

static void lab_stamp(struct timespec *t)
{
    if (clock_gettime(CLOCK_MONOTONIC, t) != 0) {
        perror("clock_gettime");
        exit(2);
    }
}

static int64_t lab_elapsed_ns(const struct timespec *a,
                             const struct timespec *b)
{
    return ((int64_t)b->tv_sec - (int64_t)a->tv_sec)
               * INT64_C(1000000000)
           + (int64_t)b->tv_nsec - (int64_t)a->tv_nsec;
}

int main(void)
{
    static uint32_t data[N];
    int64_t elapsed[SAMPLES];
    uint64_t totals[SAMPLES];

    for (size_t i = 0; i < N; ++i)
        data[i] = (uint32_t)(i + 1);

    const uint64_t expected = (uint64_t)N * (N + 1) / 2;

    /* Bemelegítés és első helyességellenőrzés: mérésen kívül. */
    if (lab_sum_u32(data, N) != expected) {
        fputs("warmup checksum error\n", stderr);
        return 1;
    }

    for (unsigned s = 0; s < SAMPLES; ++s) {
        struct timespec start, end;
        uint64_t total = 0;

        lab_stamp(&start);
        for (unsigned r = 0; r < REPEATS; ++r)
            total += lab_sum_u32(data, N);
        lab_stamp(&end);

        elapsed[s] = lab_elapsed_ns(&start, &end);
        totals[s] = total;
    }

    /* Ellenőrzés, statisztika és minden normál kiírás: mérésen kívül. */
    int64_t minimum = elapsed[0];
    double mean = 0.0;

    for (unsigned s = 0; s < SAMPLES; ++s) {
        if (totals[s] != expected * REPEATS || elapsed[s] <= 0) {
            fputs("invalid sample or checksum\n", stderr);
            return 1;
        }
        if (elapsed[s] < minimum)
            minimum = elapsed[s];
        mean += (double)elapsed[s];
    }
    mean /= SAMPLES;

    double squared_deviations = 0.0;
    for (unsigned s = 0; s < SAMPLES; ++s) {
        double d = (double)elapsed[s] - mean;
        squared_deviations += d * d;
        printf("sample[%u]_ns=%" PRId64 "\n", s, elapsed[s]);
    }

    double sd = sqrt(squared_deviations / (SAMPLES - 1));
    printf("checksum=%" PRIu64 "\n", totals[SAMPLES - 1]);
    printf("min_ns=%" PRId64 " mean_ns=%.1f sd_ns=%.1f\n",
           minimum, mean, sd);
    printf("ns_per_call=%.3f\n", mean / REPEATS);
    return 0;
}

A külön fordított assembly függvényhez nem adunk pure vagy const attribútumot, és nem használunk LTO-t. A C-fordító nem ismeri a függvény törzsét; a visszatérési értékeket felhasználjuk és ellenőrizzük. Így nincs szükség arra, hogy az egész adattömböt volatile minősítésűvé tegyük — az megváltoztatná a vizsgált programot.

A bemelegítés csökkentheti az első kódfordítás és adatérintés hatását, de nem garantál meghatározott cache-állapotot.

11.4.4.1 Fordítás és futtatás

Az alábbi lépések targetje qemu-user, AArch64 Linux; a parancsokat az Ubuntu x86_64 hoston adjuk ki. A statikus linkeléshez szükséges a cross libc és libm fejlesztői állománya, amelyet a megfelelő cross fejlesztői csomagok, például a libc6-dev-arm64-cross biztosítanak.

# Target: qemu-user / AArch64 Linux. Assembly -> objektum.
aarch64-linux-gnu-gcc -march=armv8-a -g \
    -c lab-sum.S -o lab-sum.o

# Target: qemu-user / AArch64 Linux. C -> objektum.
aarch64-linux-gnu-gcc -std=c11 -O2 -g -Wall -Wextra \
    -march=armv8-a -fno-lto \
    -c lab-time.c -o lab-time.o

# Target: qemu-user / AArch64 Linux. Statikus linkelés.
aarch64-linux-gnu-gcc -static -fno-lto \
    lab-time.o lab-sum.o -lm -o lab-time

# Target: qemu-user / AArch64 Linux. Futtatás.
qemu-aarch64 ./lab-time
printf 'exit=%d\n' "$?"

Várt, levezetett ellenőrzési feltételek:

Konkrét futási időt nem jósolunk. A mean_ns egy teljes, 2000 hívásból álló mérési blokk átlaga, az ns_per_call pedig az ebből számított hívásonkénti költség.

11.4.5 Ismétlés, szóródás és QEMU-korlát

A kilenc időminta átlaga mellett a program minimumot és mintaszórást (sample standard deviation) is közöl. A variancia (variance) és a szórás nem ugyanaz:

$$s^2=\frac{\sum_{i=1}^{m}(T_i-\overline{T})^2}{m-1}, \qquad s=\sqrt{s^2}.$$

Itt $m>1$ a mintaszám, $T_i$ és $\overline{T}$ nanomásodpercben értendő; $s^2$ egysége ns², $s$ egysége ns. A nagy szórás instabil mérési környezetre vagy változó végrehajtási költségre utalhat. A minták nem feltétlenül függetlenek, ezért ez egyszerű leíró statisztika, nem automatikus megbízhatósági bizonyíték. A minimum sem tekintendő a rutin „igazi” hardveridejének.

Érdemes a teljes folyamatot is többször elindítani:

# Target: qemu-user / AArch64 Linux.
# Három külön folyamat; mindegyik várt kilépési állapota 0.
for run in 1 2 3; do
    qemu-aarch64 ./lab-time || break
done

QEMU user-mode alatt az A64 utasításokat a gazdagépen futó emulátor hajtja végre, jellemzően dinamikus bináris fordítással. A mért időre hat a host processzora, terhelése, ütemezése és a QEMU fordítási működése. A target memóriaelérések nem egy konkrét AArch64 processzor cache-hierarchiájának hardverhű modelljén futnak.

Ezért a QEMU-eredmény:

• alkalmas a mérési program és az eredményellenőrzés gyakorlására;
• azonos környezetben adhat relatív, illusztratív összehasonlítást;
• nem szolgáltat garantált, hardverhű abszolút késleltetést vagy ciklusszámot;
• még az implementációk fizikai hardveren várható sebességi sorrendjét sem garantálja.

11.4.6 Tipikus hibák és ellenpróbák

A második futás gyorsabb. Hipotézis: első adatérintés, QEMU-fordítás vagy környezeti terhelés befolyásolta az elsőt. Gyűjtsük össze az összes mintát, majd egyetlen változtatással növeljük a mérésen kívüli bemelegítést. Ezután ismételjük meg a teljes futtatást.

A mérés kiírással együtt szokatlanul lassú. Ellenőrizzük, nem került-e formázott I/O a két időbélyeg közé. Helyezzük át a kiírást, mást ne változtassunk, majd mérjünk újra.

A futás túl rövid vagy az eredmény gyanús. Vizsgáljuk meg a generált kódot:

# Target: qemu-userre készült AArch64 objektumok statikus vizsgálata.
aarch64-linux-gnu-objdump -dr lab-time.o
aarch64-linux-gnu-objdump -dr lab-sum.o

Ellenőrizzük a rutin hívását, a körülötte lévő ismétlést és az időbélyegzés helyét. Az objektumban a külső hívások célját relokációs bejegyzések is azonosíthatják. GDB-vel ellenőrizhető a paraméter és az eredmény, de a megállításokat tartalmazó futás időadatait el kell dobni.

Nagy, megmagyarázhatatlan ingadozás. Gyűjtsünk több teljes futást, ellenőrizzük a host terhelését, majd növeljük csak az ismétlésszámot. Ha a relatív ingadozás nem csökken, ne fedjük el pusztán több tizedesjegy kiírásával.

11.4.7 Feladatok

1. (magyarázó, alapszint — cél: megértés-ellenőrzés) Miért hibás csak az időbélyegek tv_nsec mezőit kivonni? Miért nem target-ciklusszám a QEMU alatt kapott idő és egy feltételezett 2 GHz-es frekvencia szorzata?

2. (implementációs, középszint — cél: rutinépítés) Egészítsd ki a programot ns/elem mutatóval. Add meg a nevezőt, és fogalmazd meg pontosan, milyen járulékos költségeket tartalmaz az eredmény.

3. (mérési/hibakeresési, középszint — cél: rutinépítés) Változtasd a REPEATS értékét 1000-re, 2000-re, majd 4000-re. Minden változathoz végezz három teljes futtatást. Őrizd meg az időmintákat és az ellenőrzőösszeget. Mit vizsgálnál, ha a teljes mérési idő nem közelítőleg arányosan változna?

11.4.8 Megoldások

1. megoldás — Segítség. Gondolj arra, mi történik tv_nsec-kel, ha a mérés átlép egy másodperchatárt — lehet-e a vég tv_nsec-je kisebb, mint a kezdeté, miközben az eltelt idő pozitív?

1. megoldás — Teljes megoldás. Másodperchatár átlépésekor a nanomásodpercmező kisebb értékre vált. A teljes különbséghez a másodpercmező különbsége is kell. A QEMU-idő a hoston végrehajtott emuláció eltelt ideje; nincs hozzá igazolt target-ciklus/futási másodperc megfeleltetés.

2. megoldás — Segítség. Egy mérési blokk REPEATS hívást végez, mindegyik N elemet dolgoz fel — hány elemfeldolgozás történt összesen egy blokkban?

2. megoldás — Teljes megoldás. A nevező REPEATS * N, de a számítást célszerű lebegőpontos típussal végezni: mean / ((double)REPEATS * N). Az eredmény tartalmazza a hívások, a C-ciklus és az időbélyegzés járulékos költségét is. Nem egy izolált betöltés késleltetése.

3. megoldás — Segítség. Ha a fix (REPEATS-független) mérési rezsiköltség elhanyagolható, a teljes idő és a REPEATS között közel lineáris kapcsolatot vársz — mikor térne el ettől a minta?

3. megoldás — Teljes megoldás. A várt ellenőrzőösszegek rendre 8390656000, 16781312000 és 33562624000. Közel arányos időnövekedés és nagyjából állandó ns/hívás azt jelzi, hogy a fix mérési költség nem dominál. Eltéréskor először a szóródást és a host terhelését vizsgáljuk, majd az objdump segítségével ellenőrizzük a ciklust. A linearitás önmagában nem igazolja a hardverhű időzítést.

11.4.9 Rövid összefoglaló

A használható időméréshez pontosan meg kell határozni, mi kerül a két időbélyeg közé. A példában az adat-előkészítés, ellenőrzés és kiírás kívül marad, a függvényhívás és az ismétlőciklus költsége viszont beleszámít. A CLOCK_MONOTONIC eltelt időt szolgáltat; a nanomásodperces ábrázolás nem jelent ugyanekkora pontosságot. Több mintát és szóródási mutatót közlünk, nem egyetlen kedvező eredményt. QEMU alatt ezek emulációs időadatok, nem target-ciklusszámok. Erre a munkafolyamatra épít a lebegőpontos és NEON-fejezet, majd a teljesítmény-tudatos mérés.

• Instrumentáció: megfigyelést lehetővé tevő kódkiegészítés.
• Mérési intervallum: a két időbélyeg közötti végrehajtási szakasz.
• Mintaszórás: az időminták szóródását az eredeti mértékegységben jellemző mutató.

11.4.10 Források és ellenőrzési hiányok

A linkek és a dokumentumverziók közös állapota az Olvasói útmutató forrásállapot-táblájában van; itt csak az alfejezet saját megállapításai szerepelnek.

• Linux man-pages: clock_gettime — libc-felület, óratípusok, hibajelzés és időábrázolás. Tartalmilag ellenőrizve: a Linux man-pages projekt 6.19-es kiadása.
• QEMU User Mode Emulation — user-mode futtatási modell és használat. Tartalmilag ellenőrizve, de verzió-megjegyzéssel: a master ág dokumentációja (közös verziókorlát); a hivatalos szöveg nem állít semmit a cache-hierarchia vagy a memóriasávszélesség modellezéséről, ezért a fejezet QEMU-korlátra vonatkozó állításai a TCG ismert, funkcionális (nem cikluspontos) tervezéséből következnek, nem egy explicit QEMU-dokumentált korlátból.
• GNU assembler kézikönyv — AArch64 szintaxis és assembler-direktívák. Tartalmilag ellenőrizve: a jelenlegi kiadás binutils 2.47.
• GNU GDB kézikönyv — a mérési kód működésének hibakeresési ellenőrzése. Tartalmilag ellenőrizve, de verzió-megjegyzéssel: a „current” fejlesztői pillanatkép (közös verziókorlát).

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: tényleges laborfuttatás nem történt. A helyi Ubuntu-csomagverziókat, a statikus cross könyvtárak rendelkezésre állását és a clock_gettime konkrét QEMU/libc végrehajtási útját a laborban kell ellenőrizni. A forráskódhoz nem tartozik előzetesen validált időadat.