Локалност референци

У информатици‎, локалност референци (такође позната као принцип локалитета) је појава који описује исту вредност, или одговарајуће локације за складиштење којима се често приступа, односно којима ће се приступити у блиској будућности. Постоје две основне врсте референтних локалитета. Временска локалност, односи се на употребу одређених (истих) података, и/или средстава, у релативно малом временском интервалу. Просторна локалност, односи се на коришћење података у релативно блиским меморијским локацијама. Секвенцијални локалитет, као специјални случај просторног локалитета, настаје када су подаци тако распоређени да им се приступа у линеарном времену, као што је приступ члановима једнодимензионалног низа.

Локалитет је само један од типова предвиђања који се јављају у рачунарским системима. Системи који испољавају јаку локалност референци, кандидати су за оптимизацију перформанси кроз компоненте као што су кеш и многе друге.

Локалност референци

Локалност референци, такође позната као принцип локалности, открива, помоћу анализе локација података реферисаних у скорашњем временском периоду, да изабрана локација може бити релативно предвидљива. Важни специјални случајеви локалности су временска, просторна, еквидистанцијална и локалност гранања.

Временска локалност: Ако је у једном тренутку одређени део меморије референциран, онда је велика вероватноћа да ће тај исти део меморије бити референциран у блиској будућности. Можемо рећи да постоји временска близина измећу два референцирања истог дела меморије. У овом случају, намеће се, да је потребно чувати копије података у посебним меморијама за складиштење којима се приступа брже. Такође познато је да је временска локалност веома посебан случај просторне локалности, односно могућа наредна локалност је управо садашња локалност.

Просторна локалност: Ако је у одређено време референцирана одређена локација у меморији, онда је велика вероватноћа да ће у блиској будућности бити референциране управо оне локације које се налазе у близини тренутне. За побоњшање перформанси овим случајем потребно је одредити величину подручја око тренутно референциране локације и тај блок припремити за бржи приступ.

Локалност гранања: Ако постоји само неколико могућих алтернатива за будући део путање у просторно-временској координати простора. То је случај ако петља инструкција има једноставну структуру, или ако је могући исход малог система условних инструкција гранања ограничен на мали избор могућности. Локалитет гранања обично није просторни локалитет, јер неколико могућности може да се налази далеко једна од друге

Локалитет једнаког одстојања: Он је између просторног локалитета и локалитета гранања. Замисслите петњу приступа локацији по шаблону једнаког одстојања, односно пут у просторно-временске координате простора је испрекидана линија. У овом случају, проста линеарна функција може предвидети којој локацији ће се приступити у блиској будућности.

Да би имали корист од веома честих појављивања временских и просторних врста локалитета, већина система за складиштење информација је хијерархијски организована, види испод. Локалитет једнаког одстојања је обично подржан од стране различитих нетривијалних допунских инструкција процесора. У случају локалитета гране, савремени процесори имају софистициране предикторе грана, а на основу овог предвиђања управљач меморије процесора покушава да прикупи и обради податке могућих алтернатива.

Разлози за локалитет

Постоји неколико разлога за локалитет. Ови разлози су или циљеви за постићи или разлози за прихватити, у зависности од аспекта. Испод су приказани разлози, од наопштијег случаја, до специјалних случајева:

Предвидљивост: Заправо локалитет је само један тип предвидљивог понашања у рачунарским системима. Срећом, многи од практичних проблема су тако децидирани да програм за њихово решавање може да буде предвидљив, ако је добро написан

Структура програма: Локалност се дешава често, због начина на који су рачунарски програми створени, за решавање децидираних проблема. Генерално, слични подаци се чувају у оближњим локацијама у складишту. Један заједнички образац у рачунарству подразумева обраду неколико ставки, једну по једну. То значи да ако је много обрађивања завршено, одређеним ставкама ће бити приступљено више пута, што доводи до временске локалности референце. Штавише, прелазак на слдећу ставку подразумева да ће следећа ставка бити прочитана, па имамо просторну локалност референце.

Линеарне структуре података: Локалитет се често дешава зато што садржи петље које имају тенденцију да упуте на низове или друге структуре података помоћу индекса. Секвенцијални локалитет, посебан случај просторног локалитета, јавља се када су релевантни елементи података организовани и приступа им се линеарно. На пример, једноставан пролазак елемената у једнодимензионалном низу, од базне адресе до највишег елемента ће искористити секвенцијални локалитет низа у меморији. Општији локалитет једнаког одстојања се јавља када је линеарни прелазак преко дужег подручја суседних структура података које имају идентичну структури и величину. И поред тога, нису целе структуре приступне, него само међусобно одговарајући исти елементи структура. Ово је случај када је матрица представљена као секвенцијална матрица редова и услов је да се приступи једној колони матрице.

Општа употреба локаности

Ако се већину времена значајан део укупних референци скупља у кластере, и ако се облик овог система кластера може добро предвидети, онда се може користити за оптимизацију брзине. Постоји неколико начина да се добију бенефиције од кластера. Уобичајене технике за оптимизацију су:

Повећање локалности референци

Ово се обично постиже софтверски.

Искоришћавање локалности референце

Ово се обично постиже хардверски. Временски и просторни локалитети се могу капитализовати по хијерархијским хардверским складиштима. Локалност једнаког одстојања може се користити на одговарајући начин од стране специјализованих инструкција процесора, ова могућност није само одговорност хардвера, него и софтвера такође, било да је њена структура погодна за израду бинарног програма који узима специјализоване инструкције у обзир. Локалитет гране је сложенија могућност, стога је потребно више напора око развоја, али постоји много већа резерва за будуће истраживање у овој врсти локалитета, него у било којој од преосталих.

Коришћење просторног и временског локалитета

Хијерархијска меморија

Хијерархијска меморија је хардверска оптимизација која користи просторни и временски локалитет и можђе се користити у више нивоа хијерархије меморије. Страничење очигледно има корист од просторног и временског локалитета. Кеш је једноставан пример експлоатације временског локалитета, јер посебно дизајниран, брз, а мали меморијски простор, углавном коришћен да би чуцао недавно референциране податке и податке близу њих, што може довести до потенцијалног повећања перформанси.

Подаци у кешу морају обавезно да одговарају подацима који су просторно близу у главној меморији, међутим елементи података су деведени у кеш , једну по једну кеш линију. Ово имплицира да је просторни локалитет поново важан: ако је један елемент рефернциран, неколико суседних елемената ће се такође довести у кеш. Коначно, временски локалитет игра улогу на најнижем нивоу, јер се резултати који су референцирани налазе веома близу један другом те се могу чувати у регистрима машине. Програмски језици као што је C омогућавају програмеру да предложи да се одређене променљиве чувају у регистрима.

Локалитет података је типична меморијска референтна карактеристика уобичајених програма(мада постоје многи неуобичајени шаблони). То чини распоред хијерархијске меморије профитабилним. У рачунарима, меморија је подељена хијерархијски да би се убрзао приступ подацима. Низи нивои меморијске хијерархије теже да буду спорији, али већи. Дакле, програм ће постићи боље рерформансе ако користи меморију кеширану на вишем нивоу хијерархије, и ако избегава довођење података у виши ниво хијерархије који ће свргниту податке који ће се користити у ближој будућности. Ово је идеално, и понеда се не може постићи.

Типична меморијска хијерархија(времена приступа и кеш величине су приближне типичним вредностима од 2013 за потребе дискусије; стварне вредности и стварни бројеви нивоа у хијерархији могу варирати)

Процесорски регистар (8-256 регистара)– тренутни приступ, и то брзином најбржег језгра процесора
L1 CPU кеш (32 KiB to 512 KiB) – брз приступ, брзином меморијске магистрале.
L2 CPU кеш (128 KiB to 24 MiB) – нешто спорији приступ, брзином меморијске магистрале између два језгра
L3 CPU кеш (2 MiB to 32 MiB) – још спорији приступ, брзином меморијске магистрале између још више језгара процесора.
Главна, физичка меморија (РАМ) (256 MiB to 64 GiB) – спор приступ, брзина која је ограничена просторном удаљености и општим хардверским интерфејсом између процесора и меморијских модула на матичној плочи.
Диск (виртуелна меморија) (1 GiB to 256 TiB) – веома спора,
Удаљена меморија (са других рачунара или интернета) (практично бесконачна) – брзина варира од веома спорих до невероватно спорих

Множење матрица

Заједнички пример је множење матрица:

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Када се ради о великим матрицама, овај алгоритам има тенденцију да превише дуплира подаке. Како је потребно помножити сваки члан реда једне матрице са сваким чланом колоне друге долази до вишеструком приступу истим подацима, као и вишеструком добијању истих резултата.

Може се приметити да од ј зависи колона ове матрице C и B и она треба да се врти у унутрашњој петљи(то ће поправити итераторе редова, i и k док се ј креће преко сваке колоне у реду). Ово неће променити математички резултат али се побољшава ефикасност. Преласком ј и к петљи временска захтевност за веће матрице драматично расте. (У овом случају, 'велики' значи, отприлике, више од 100.000 елемената у свакој матрици, или довољно елемената тако да матрице не могу да стану у L1 и L2 кеш.)

Временска захтевност може бити побољшана у претходном примеру, користећи технику која се зове блокирање. Већа матрица се може поделити на равномерно велике суб-матрице, тако да се мањи блокови множе неколико пута док су у меморији.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      for (i = ii; i < ii + BLOCK_SIZE && i < SIZE; i++)
        for (k = kk; k < kk + BLOCK_SIZE && k < SIZE; k++)
          for (j = jj; j < jj + BLOCK_SIZE && j < SIZE; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

Временска сложеност решења изнад је боље јер блок може да се користи неколико пута пре него што пређете на наредни, тако да мање губимо кад он оде у доње нивое хијерархије . Просторни локалитет је побољшан, јер елементи са суседне меморијске адресе имају тенденцију да се повуку заједно кроз меморијску хијерархију.

Погледај још

Референце

Литература

P.J. Denning, The Locality Principle, Communications of the ACM, Volume 48, Issue 7, (2005), Pages 19–24
P.J. Denning, S.C. Schwartz, Properties of the working-set model, Communications of the ACM, Volume 15, Issue 3 (March 1972), Pages 191-198