Компютърни архитектури — Ръководство за лабораторни упражнения

Цветан Таслаков, Милен Ангелов. Компютърни архитектури — Ръководство за лабораторни упражнения. ТУ-Варна, 2010.

Упражнение 1 — Производителност на компютъра. Методи за определянето й.

Цел на упражнението

Да се разучат основните методи за определяне и оценка на производителността на компютъра — методи на измерването и методи на моделирането. Анализът да обхване предимствата, недостатъците и типичните грешки на всеки метод.

Теория

Производителността на компютъра представлява сложна нелинейна функция от множество параметри: тактова честота, брой тактове за команда, логически възможности на системата команди, структура на процесора, обем и организация на паметта, пропускателна способност на входно/изходните канали, характеристики на операционната система. Индексите на производителността биват количествени и качествени; по-нататък се разглеждат само количествено измеримите.

Разграничават се клиентска (потребителска) и системна производителност. Клиентската е достигната за отделна задача с пълен приоритет; системната — при едновременно решаване на съвкупност от задачи. Производителността се измерва в MFLOPS (10⁶), GFLOPS (10⁹) или TFLOPS (10¹²) за операции с плаваща запетая.

Методите за оценка се делят на методи на измерването (прилагат се когато компютърът е в наличност) и методи на моделирането (прилагат се при проектиране или при липса на достъп). В реалния свят двата подхода взаимно се допълват.

Методи на измерването:

Елементарни времена — производителността в MIPS въз основа на времето за изпълнение на основна операция. Измерва пиковата производителност; не отчита програмното осигуряване.
Командни смеси — средно претеглено време за изпълнение на команди с тегловни коефициенти (напр. командна смес на Гибсън: k = 0,33 за събиране с фиксирана запетая, k = 0,175 за безусловни преходи).
Образцови програми — типична програма, изпълнявана „на хартия”; отчита и апаратното, и програмното осигуряване.
Измервателни програми — реална програма с директно измерване на времето чрез системния таймер. Грешката произтича от дискретния характер на таймера; намалява се чрез обработка на големи масиви и многократно повтаряне на изчисленията.
Синтетични програми (benchmarks) — специално съставени за изпитване на конкретни способности; Whetstone, Dhrystone, LINPACK (основа на Top500), Livermore Fortran Kernels, SPEC.

Методи на моделирането:

Аналитично моделиране — детерминирани (машини на Тюринг, мрежи на Петри) и вероятностни (теория на опашките, марковски процеси) модели. Дават бърза оценка с грешка ~10%. Пример — модел на Марини: P = 1/(0.7·t_add + 0.3·t_mult + km·tm) [MIPS].
Имитационно моделиране — програмно описание на системата; три етапа: концептуален модел, разработка на имитационен модел, моделиране с компютър. Грешка 2–3%; изисква значителни изчислителни ресурси. Инструменти: GPSS, SIMSCRIPT или универсални езици (C, C++).

Апробация на модела: Моделът се счита за достатъчно точен, ако индексите му се отличават от реалните с по-малко от допустимата максимална грешка. Процесът по повторна корекция до постигане на необходимата точност се нарича калибровка.

Моделни изследвания

Разучаване на различни benchmark програми за определяне на производителността на компютри, предоставени от ръководителя на упражнението. С тяхна помощ — оценка на производителността на изследвания компютър. Анализ на факторите, влияещи върху грешката за всеки конкретен тест, и начините за нейното намаляване.

Упражнение 2 — Определяне влиянието на командите за преход върху ефективността на конвейер за команди

Цел на упражнението

Да се изследва производителността на процесор с реализиран конвейерен принцип за изпълнение на командите. Анализът да се проведе с помощта на аналитичен модел.

Теория

Изпълнението на командите включва няколко етапа. В двустепенен конвейер: извличане (IF) и изпълнение (EX). Докато втората степен изпълнява текущата команда, първата може да извлича следващата — техника, известна като предварително извличане на команди. При еднакви продължителности на двете степени теоретично се очаква двойно увеличение на скоростта, но на практика то не се постига по две причини:

Времето за изпълнение на командата, като правило, е по-голямо от времето за извличане.
При команди за преход е неизвестна следващата команда до завършване на текущата, което налага изчистване на конвейера.

Загубата от командите за преход може да се намали чрез прогнозиране: избира се командата, непосредствено следваща след командата за преход. Ако преходът не се е осъществил — загуба няма; ако се е осъществил — командата се отхвърля. Неритмичната работа на конвейера при преходи се нарича поява на мехурчета (pipeline bubbles). С увеличаване броя на степените проблемът се усложнява.

Основни подходи за преодоляване на влиянието на преходите:

предварителен избор на адреса на разклонение;
използване на няколко потока команди;
прогнозирано разклонение (апаратно);
отложено разклонение (програмно).

Аналитичен модел: Нека L е броят на степените, n — общият брой команди, p — вероятността за поява на команда за преход (~20% по Amdahl), g — вероятността за успешно взето разклонение (~60%). Общият брой тактове за изпълнение на програмата:

S_total = n·(1-p) + n·p·g + n·p·(1-g)·L

Ефективността при условие n >> L:

E = 1 / [1 - p + p·g + p·(1-g)·L]

Действителната производителност: S = L · E.

Моделни изследвания

С помощта на програма LAB2 да се проведат изследвания с две различни стойности на L и три различни стойности на g. Да се анализира зависимостта на ефективността от p, g и L.

Упражнение 3 — Анализ на конвейер за изпълнение на командите

Цел на упражнението

Да се изследва производителността на двустепенен конвейер за команди с помощта на имитационен модел.

Теория

Техниката „предварително извличане” не води до съществено увеличение на производителността поради неравните времена на двете степени. За преодоляване — в първото стъпало (IF-устройство, Instruction Fetch Unit) се изпълняват повече действия: извличане, декодиране, определяне адреса на операнда. Така двете степени имат приблизително еднакви времена. Между тях стои фиксатор (регистров файл / FIFO буфер), позволяващ относително независима работа.

Ресурсите в модела са три: памет, IF устройство и EU (Execution Unit). Командите се разделят на две групи:

Първа група (вероятност p): аритметични и логически команди, преходи. Трите подгрупи: безусловни преходи (5% — изчистват конвейера), условни преходи (15%, с вероятност 50% изчистват конвейера), изчислителни и логически (не предизвикват извънредни събития).
Втора група (вероятност 1-p): команди четене/запис от/в паметта; изпълнение: извличане от паметта, определяне на ефективния адрес, обръщение към паметта.

Събитията в модела: E1 (начало на извличане), E2 (край на извличане след t1), E3 (край на изпълнение след t2), E4 (край на обръщение към паметта след t3). Всяка команда е транзакт с два атрибута: група и текущо събитие.

Ограничения на модела: не се моделират зависимости между командите; опашката към EU е неограничена.

Моделни изследвания

С програма LAB3 да се определи влиянието на t1, t2 и t3 върху производителността и средното време за изпълнение на команди при изменение на p (0,1 до 0,9). Режими: а) t1=t2=t3=t; б) t1=t3=t, t2>t. За всеки режим — с и без отчитане на командите за преход.

Упражнение 4 — Изследване работата на многостъпален конвейер

Цел на упражнението

Да се изследва производителността на реален многостъпален конвейер — как се влияе тя при увеличаване броя на степените и при среща с команди за преход.

Теория

Многостъпалният конвейер реализира повече етапи от обработката на командата (извличане, декодиране, определяне адреса на операнда, изпълнение, обратен запис), но нелинейно увеличение на производителността поради:

Допълнителни загуби от прехвърляне на данни между фиксаторите при всяко стъпало. Пример: при разбиване от 2 на 4 степени с 20 ns overhead за фиксатор и 80 ns логика, новият такт е 60 ns вместо очакваните 50 ns — само 1,67 пъти ускорение вместо 2.
Стремителен ръст на управляващата логика при увеличен брой степени.
Увеличено отрицателно влияние на командите за преход при по-дълъг конвейер.

Изследваният процесор е IDT-C6 — x86-съвместим CISC процесор с вътрешна RISC архитектура и 6-степенен конвейер: извличане → транслация → опашка → декодиране → адрес → изпълнение → обратен запис. Степента „транслация” преобразува сложните x86 инструкции в 33-битови RISC инструкции вътрешно. Няма суперскаларна архитектура, нняма хардуерно предвиждане на преходи — удобен за моделиране.

Концептуалният модел разглежда 7 ресурса: кеш за инструкции, блок за транслация, блок за декодиране, блок за адрес, блок за изпълнение, блок за обратен запис, кеш за данни. Предполага се, че обръщенията към кеш паметта винаги са успешни. Командите са в две групи, аналогично на упражнение 3.

Моделни изследвания

С програма LAB4 в два режима:

Демо режим: Наблюдение на работата на конвейера; идентификация на командите (J=безусловен преход, C=условен преход, M=памет, R=останали). Анализ на максималния брой команди в опашката.
Режим моделиране: Влияние на времето за изпълнение на командата (етап 5), влияние на командите за преход при дълъг конвейер; сравнение с резултатите от упражнение 3.

Упражнение 5 — Анализ на производителността на операционен конвейер

Цел на упражнението

Да се изследва промяната на производителността на конвейера в зависимост от дължината на обработвания вектор, броя степени в конвейера и броя паралелно работещи конвейери в векторния процесор.

Теория

Конвейерният принцип може да се приложи не само при обработката на команди, но и при обработката на данни — операционен (аритметичен) конвейер във векторния процесор. Векторът е набор от скаларни данни от еднакъв тип. Ако A, B, C са вектори с n елемента, скаларната сума A+B се изразява с единствена векторна команда C=A+B.

Единичен конвейер. Времето за обработка на n елемента:

t(n) = t_init + (L + n - 1)·tc

където tc е тактът на конвейера, L — брой степени, t_init — времето за инициализация. Увеличението на производителността спрямо скаларно аритметично-логическо устройство без конвейер:

S ≈ L·n / (σ + L + n - 1)

при σ = t_init/tc. С нарастване на n, S се стреми към пределната стойност L. Ефективността:

E = S / L = n / (σ + L + n - 1)

Минималната дължина на вектора за ефективна обработка при желана ефективност E₀:

n_min = E₀·(σ + L - 1) / (1 - E₀)

Макроконвейер (съставни команди). Когато векторният процесор поддържа съставни команди (напр. F(a+b)·d с два последователни конвейера — събиране и умножение), двата конвейера се свързват последователно — единият подава изхода директно на следващия, без запис в паметта. Ускорението спрямо последователното изпълнение с k паралелни конвейера:

S_macro ≈ k·(L + σ + n - 1) / (σ + k·(L + n - 1))

При еднакви σ и L за всеки конвейер.

Моделни изследвания

С програма LAB5:

Единичен конвейер: Определяне на зависимостта n(L) при фиксирана ефективност E ∈ (0,6…0,8).
Макроконвейер: Минимална и максимална стойност на S; влияние на параметъра σ при две различни стойности.

Упражнение 6 — Компютри с SMP и MPP архитектури

Цел на упражнението

Да се изследват двата основни типа паралелни архитектури — с обща и с разпределена памет — и да се анализира зависимостта на производителността им от различни фактори.

Теория

В зависимост от отношението на процесорите към паметта се различават два класа паралелни компютри:

SMP (Symmetrical Multiple Processors / Shared Memory Processors) — силно свързани системи с обща памет. Всички процесори имат пряк достъп до общата памет чрез комуникационна мрежа. Опростено системно и приложно програмиране; лесна синхронизация. Основен недостатък: при добавяне на нови процесори трафикът към паметта нараства до насищане — лоша мащабируемост. Решения: кеш памет за всеки процесор (с проблем за кохерентност) и подходящо разпределение на данните по модулите памет.

MPP (Massively Parallel Processing) — слабо свързани системи с разпределена памет. От стотици до хиляди процесори, всеки с локална памет. Без обща памет — конфликтите при достъп до паметта се разрешават. Комуникацията между процесорите се реализира чрез обмен на съобщения (PVM — Parallel Virtual Machine, MPI — Message-Passing Interface). Добра мащабируемост, но необходима разработка на нови паралелни алгоритми.

NUMA (Non Uniform Memory Access) — хибрид: всеки възел е SMP компютър, а достъпът до паметта на отдалечени възли е значително по-бавен (200–700% разлика спрямо локален достъп). Архитектурата ccNUMA (cache coherent NUMA) решава проблема с кохерентността на кеш паметите чрез специализирани протоколи.

Модел с обща памет (Cvetanovic): Ускорението при N процесора:

S(N) = D_c(N)·BW(N) / [D_c(N) + (t_s/t)·BW(N)/D_m(N)]

където D_c(N) е декомпозиционната функция на изчисленията, D_m(N) — на комуникациите, BW(N) — ширина на лентата на пропускане. При crossbar мрежа без конфликти BW(N) = N; при единична шина BW(N) = 1.

Модел с разпределена памет (хиперкуб): Двоичен хиперкуб с размерност a: N = 2^a процесора, всеки свързан с a съседа. Параметър на глобалност G (0 ≤ G ≤ 1): при G = 0 данните са изцяло локални; при G = 1 — максимален комуникационен трафик. Средно разстояние на съобщенията: D = G·a/(1+G). Ускорението:

S(N) = N·W_c / [W_c + N·W_s·D]

Моделни изследвания

С програма LAB6 за модел с обща памет: изследване на граничните случаи (crossbar без конфликти, crossbar с конфликти, шинна архитектура) при различни D_c, D_m и BW. За модел с разпределена памет: зависимост S(N) при груб паралелизъм (W_c = 0,9) и фин паралелизъм (W_c = 0,1) при различни стойности на G.

Упражнение 7 — Определяне на производителността на MPP компютри при решаване на един клас задачи

Цел на упражнението

Да се определи влиянието на решаваната задача върху производителността на паралелна система без обща памет, при комуникация чрез обмен на съобщения.

Теория

Изчислителният процес протича в редуващи се фази: паралелна работа (процесорите работят автономно) и последователна работа (обмен на информация между процесорите и централния компютър).

Времето за решаване при P процесора: T(P) = T_a(P) + W(P), където T_a(P) е времето за аритметични и логически операции, W(P) — времето за комуникация и синхронизация. Ускорението:

S(P) = T(1) / [T_a(P) + W(P)]

При равномерно разпределение на товара и независими задачи T_a(P) ≈ T(1)/P. При неравномерно натоварване се въвежда коефициент c (c = 1 при равномерно, c > 1 при неравномерно):

S(P) ≈ P / (c + W(P)·P/T(1))

Метод на декомпозиция за матрични операции: Матрицата A(n,n) се разделя на P хоризонтални слоя от по n/P реда, всеки съхранен в локалната памет на съответния процесор. Критичен размер: минималното n, при което S > 1.

Формули за t_comm(P) (при последователно предаване): събиране матрици — 1,5n²(P-1)·t_e; умножение матрици — 2n²(P-1)·t_e; транспониране — n²(P-1)·t_e; обратна матрица — 3n²(P-1)·t_e, където t_e = 2,4 μs (T805/30 транспютър).

Моделни изследвания

С програма LAB7: за всяка от четирите матрични операции да се определи критичният размер n при конкретен брой процесори; зависимостта S(n) при P = const; зависимостта S(P) при n = const.

Упражнение 8 — Определяне на основните параметри на някои статични комуникационни мрежи

Цел на упражнението

Да се изследват основните параметри на статичните комуникационни мрежи и да се определи как зависят те от броя на процесорите.

Теория

Комуникационната мрежа е ключов фактор за общата производителност на паралелния компютър. Тя е N×N многополюсник с входове (предаватели) и изходи (приемници). Описва се като граф, чиито върхове са комуникационните елементи, а дъгите — линиите за връзка.

Статичните комуникационни мрежи осигуряват непосредствена връзка само между строго определени компоненти. Работят с комутация на пакети; намират основно приложение при изграждане на клъстери.

Основни параметри:

N — брой компютри в мрежата.
D — диаметър: максималното минимално разстояние между произволна двойка върхове.
P (средно разстояние) — средно разстояние от всеки връх до всички останали.
T — средна плътност на трафика: брой съобщения за единица време на линия за връзка = (N·P) / (общ брой линии).

Примери за статични мрежи: линия (конвейер), кръг, двумерна решетка, тор, двоично дърво, хиперкуб, хипердърво. Характеристики като наличие на алтернативни пътища (отказоустойчивост) и еднотипност на всички възли (мащабируемост) са допълнителни критерии.

Моделни изследвания

С програма LAB8: пресмятане на D, P и T за различни топологии и различен брой процесори N, използвайки алгоритъм на Форд или Дейкстра. Наредяне на топологиите по D, P и T. Препоръка за оптималната топология.

Упражнение 9 — Анализиране на производителността на някои динамични комуникационни мрежи

Цел на упражнението

Да се изследва производителността на cross-bar мрежа (матричен превключвател) и delta мрежа.

Теория

Динамичните комуникационни мрежи позволяват реконфигурация на активните комуникационни елементи. Осигуряват директна връзка между произволни компоненти; изграждат се от няколко стъпала с по-прости елементи. Параметри: сегментиране (разделяне на независими подмрежи) и ширина на лентата на пропускане.

Cross-bar мрежа (N×M матричен превключвател): пълна мрежа, при която конфликти се получават само когато две заявки се отнасят към един и същи модул памет. При вероятност p за заявка от всеки процесор, очакваната ширина на лентата:

B(N,M) ≈ M·[1 - (1 - 1/M)^(N·p)]

Вероятността за приемане на заявка:

P_a(N,M) = B(N,M) / (p·N)

При реални условия отхвърлените заявки се повтарят (динамична вероятност p’ > p). Средният брой изгубени цикли: L = (1 - p_d) / p_d.

Delta мрежа (a^k × b^k; изградена от модули a×b в k стъпала): анализира се рекурсивно — изходната вероятност на едно стъпало е входна за следващото. Широчината на лентата не може да се изрази в явен вид и сравнението с cross-bar се прави графично.

Моделни изследвания

С програма LAB9: cross-bar при N=M (квадратна, N = 2,4,8,16,32,64) и при N≠M (правоъгълна); delta мрежа при различен брой стъпала и при N=M, N>M, N<M. Сравнение на B и L за двата типа мрежи при изменение на p от 0,1 до 1,0.

Упражнение 10 — Изследване влиянието на кеш паметта върху времето за достъп до данните

Цел на упражнението

Да се изследва увеличението на скоростта на достъп при наличие на кеш памет спрямо система само с основна памет, и да се определи от какви фактори зависи то.

Теория

Кеш паметта работи въз основа на локалността на обръщенията — универсално свойство на програмите. Два типа локалност:

Локалност по време: веднъж достъпена позиция вероятно ще бъде достъпена отново (цикли, стекови променливи, горещи данни).
Локалност по пространство: при достъп до дадена позиция вероятно ще бъдат достъпени и съседните (потоци от инструкции, масиви, матрици).

Аналитичен модел: Нека p е вероятността търсеният обект да е в кеш паметта, t_c — времето за достъп до кеш, t_m — времето за достъп до основна памет. Средното ефективно латентно за достъп:

τ = p·t_c + (1-p)·t_m

Увеличението на скоростта на достъп спрямо система само с основна памет:

S = t_m / τ = a / [p + (1-p)·a]

където a = t_m / t_c показва колко пъти е по-бърза кеш паметта. Ефективността на кеш паметта: E = S/a.

Параметърът p е критичен за проектанта. Не може да бъде 1 (невъзможно 100% попадение) нито 0 (винаги има повторно използване). В реалността p не е константа — изменя се динамично в зависимост от програмата и структурата на кеш паметта.

Моделни изследвания

С програма LAB10: изследване на S и E при различни стойности на p и a. Анализ: при какви стойности на p е рационално използването на кеш памет; влияние на коефициента a върху ефективността.

Упражнение 11 — Изследване влиянието на конфликтите при обръщение към паметта върху ефективността й

Цел на упражнението

Да се анализира влиянието на конфликтите при обръщение към разслоена памет (interleaved memory) върху ефективността на системата памет-процесор.

Теория

При хоризонталната организация целта е увеличаване на броя достъпи за единица време чрез разслояване на паметта на M модула. Последователните адреси са в различни, но последователни модули. При обръщение към вече зает модул процесорът трябва да изчака — конфликт.

Нека компютърът съдържа N процесора и M модула памет. Пълният цикъл на паметта заема h такта. Всеки процесор в начало на такт се обръща към паметта с вероятност p при равновероятен избор на модул. Ефективността:

E = 1 / (1 + φ·p·h·(d+1))

при φ = N/M. Ограничения на модела: не отчита зависимостта на p от предисторията; предполага равновероятни обръщения (реалните системи имат последователни обръщения); не отчита опашката при множество процесори към един модул.

Независимо от ограниченията, формулата показва в явен вид полезната информация за взаимната връзка между N, M и h.

Моделни изследвания

С програма LAB11: Как зависи E от h? Как зависи E от броя модули M и броя процесори N при случаите M>N, M=N, M<N? Кога ефективността е максимална?

Упражнение 12 — Анализ на производителността на дисковата памет

Цел на упражнението

Да се изследва влиянието на параметрите на дисковата памет върху общата производителност и да се определят граничните стойности на всеки параметър.

Теория

Пътят на входно/изходните операции при твърдите дискове включва: драйвер на диска (управлява устройство-специфичните взаимодействия, може да пренарежда заявките), HBA (Host Bus Adapter) (свързва с шината), контролер на диска (управлява механизма, реализира ECC, кеширане, планиране) и дисков механизъм (въртящи се плочи и глави с позициониращ механизъм).

Предложеният имитационен модел симулира работата на един или повече дискове, присъединени към обща SCSI шина. Параметри на диска: размер на сектора, сектори на пътечка, пътечки на цилиндър, брой цилиндри, Cylinder Skew, Track Skew, RPM, Bus Grab Time, Bus Speed, Cache Size. Параметри на модела: брой дискове, брой заявки, максимално време между заявки, максимален размер на заявка.

Основни допускания на модела:

Времето за търсене се моделира с функция от разстоянието: SeekTime(dis) ≈ a·√dis + b·dis.
Без зониране; без агресивно предварително позициониране.
Всички цилиндри се използват за данни (логически = физически адреси).
Времето за обработка на заявката от контролера е постоянно ~1 μs.
Кеш редът е равен на сектора; без сегментиране на кеша.
Заместващ алгоритъм: FIFO; реализира се read-ahead до запълване на кеша.
Всички записи се записват в кеш (immediate write-behind).

Моделни изследвания

С програма LAB12: Влияние на броя дискове (1, 2, 3, 4) върху средното латентно за достъп и броя прехвърлени сектори — с и без промяна на времето между заявките. Влияние на RPM (скоростта на въртене) — кой параметър е най-чувствителен. Влияние на ширината на лентата на шината.