Els protocols de coherència de caché basats en tokens són capa¸cos de capturar
simultàniament els principals avantatges dels dos esquemes que tradicionalment
s’han utilitzat per a assegurar coherència: baixa latència en les fallides
de caché (com en els protocols basats en snooping) i no dependència de xarxes
d’interconnexió totalment ordenades (com en els protocols basats en directori).
Els protocols basats en tokens poden unir eixes característiques gràcies en gran
part a la utilització de peticions desordenades. Desafortunadament, les peticions
desordenades introduïxen un problema nou ja que, en cas de competir
per un mateix bloc de memòria, poden generar carreres de protocol, la qual
cosa impedix la resolució de les fallides de caché. Per eliminar les carreres de
protocol i poder assegurar que totes les peticions són finalment completades
(assegurant així la resolució de totes les fallides de caché), els protocols basats
en tokens requerixen la utilització d’un mecanisme de prevenció d’inanició.

Els problemes més significatius dels protocols de coherència basats en tokens
són causats principalment pel mecanisme de prevenció d’inanició. Encara
que fins ara s’han proposat diverses alternatives per a implementar aquests
mecanismes, continuen presentant problemes seriosos: primer, són massa ineficients;
segon, consumixen uns recursos d’emmagatzemament a cada node
que creixen proporcionalment amb la grandària del sistema; i tercer, requerixen
la utilització de missatges broadcast. Tots aquests problemes comprometen
l’escalabilitat dels protocols basats en tokens perquè, conforme creix
la grandària del sistema, el rendiment del protocol empitjora, la quantitat de
recursos d’emmagatzemament requerits a cada node creix significativament i
la xarxa d’interconnexió es congestiona cada vegada més a causa dels missatges
broadcast. Malgrat això, aquests no són els únics problemes seriosos que
comprometen l’escalabilitat del protocol, ja que aquesta també es veu afectada
per la utilització d’invalidacions no silencioses (non-silent invalidations).

Mentres seguisca la tendència d’augmentar el nombre de nodes en els sistemes
multiprocessadors de memòria compartida, es continuarà requerint la
utilització de protocols de coherència de caché que siguen eficients i escalables.
Tenint en compte això, les contribucions aportades per aquesta tesi tenen com
a objectiu la millora del rendiment i l’escalabilitat dels protocols de coherència
basats en tokens. Per a aconseguir-ho, aquesta tesi aborda tant els aspectes
més negatius dels mecanismes de prevenció d’inanició com els de les invalidacions
no silencioses. La contribució més destacada és l’observació que certs
algoritmes d’acarrerament poden evitar de forma natural que els protocols que
no estan basats en xarxes totalment ordenades ni en directoris generen carreres
de protocol. Així, mitjan¸cant la utilització de técniques d’acarrerament
basades en camins ordenats, podem crear fàcilment un mecanisme de prevenció
d’inanició eficient i flexible. A més, aquests algoritmes d’acarrerament
ens permeten desenvolupar tècniques que milloren l’escalabilitat del protocol i
reduir tant els recursos d’emmagatzemament requerits pel mecanisme de prevenció
d’inanició com el trànsit de xarxa generat pels missatges broadcast.
Addicionalment, aquestes tècniques es poden utilitzar també per a millorar
les invalidacions no silencioses.