Контролни въпроси и задачи — отговори
Цветан Таслаков, Милен Ангелов. Компютърни архитектури — Ръководство за лабораторни упражнения. ТУ-Варна, 2010.
Упражнение 1 — Производителност на компютъра
Въпрос 1
Приведете примери, че производителността зависи действително от гледната точка за оценка.
Производителността не е единствена обективна величина — тя е функция от това какво измерваме и за кой потребител. Едно и също устройство може да има висока производителност по един показател и ниска по друг. Например суперкомпютър с пикова производителност от 10 TFLOPS може да постигне едва 30–40% ефективност при решаване на реални задачи, защото значителна част от времето се губи в комуникации между процесорите. Обратно, персонален компютър с по-скромна пикова производителност може да е по-ефективен при текстообработка, тъй като задачата не изисква масивен паралелизъм. Преносимите компютри се оценяват предимно по консумация на енергия (производителност на ват), а не по пикова скорост. Система за обработка на транзакции се оценява по брой завършени транзакции за секунда (TPS), а не по FLOPS. Накратко: производителността е многомерна величина и различните потребители акцентират върху различни индекси.
Въпрос 2
Какви са различията между производителността, ориентирана към потребителя и към системата?
Клиентската (потребителска) производителност се измерва за отделна задача, на която е предоставен приоритетен достъп до всички необходими ресурси. Тя изразява колко бързо конкретна програма завършва изпълнението си при оптимални условия. Именно нея потребителят „усеща” при интерактивна работа.
Системната производителност се постига при едновременно решаване на съвкупност от задачи, конкуриращи се за ресурсите. Тя отразява пропускателната способност на системата — колко задания завършват за единица време. Системата може да е оптимизирана за максимален throughput, дори за сметка на по-голямо латентно за всяка отделна задача.
Разликата е особено важна при многопотребителски системи: максималният throughput не съвпада задължително с минималното латентно за индивидуалния потребител. Операционната система балансира между двата показателя чрез планировчика.
Въпрос 3
Какво следва да се разбира под понятието „модел на компютъра”?
Моделът на компютъра е определено количество организирана информация за изчислителната система, построена с цел нейното изучаване. В зависимост от формата на представяне моделите биват аналитични (математически уравнения, описващи поведението на системата) и имитационни (програма, симулираща функционирането на системата). И в двата случая моделът е абстракция — опростена версия на реалността, акцентираща върху онези аспекти, които са съществени за поставената цел. Неизбежно е всеки модел да носи определени ограничения и грешки, произтичащи от опростяванията. Качеството на модела се измерва с точността (степента, до която предсказва реалното поведение) и приложимостта (обхвата от условия, за които е валиден).
Въпрос 4
Какво представлява пропускателната способност на компютъра и как се определя?
Пропускателната способност (throughput) изразява количеството извършена работа за единица време. В зависимост от контекста тя може да означава: брой изпълнени задания за единица време (при система за пакетна обработка), брой завършени транзакции за секунда (при OLTP системи), или брой битове/байтове, предавани за единица време (при комуникационни системи). Определя се чрез измервателни програми, benchmark тестове или изчисление от аналитичен модел. Важно е да се разграничава от латентното (времето за изпълнение на отделна заявка) — системи с висок throughput не са задължително с ниско латентно, и обратно.
Въпрос 5
От какво зависи достоверността на един модел?
Достоверността на модела зависи от: точността на концептуалния модел (дали са уловени всички съществени причинно-следствени връзки), правилността на транслацията от концептуален към имитационен/аналитичен модел (липса на програмни грешки), точността на зададените параметри (грешни входни данни дават грешни резултати дори при коректен модел) и степента на разпространяване на опростяванията. Проверката на достоверността се извършва чрез калибровка — сравнение с резултати от реалната система (ако е налична) и повторение на процеса на корекция до постигане на допустимата грешка. Грешките биват: от формулировката на модела, от решението и от задаването на параметрите.
Въпрос 6
Какво е аналитичен модел? Защо той представлява интерес при оценка на производителността?
Аналитичен модел е модел с математическо представяне на системата — система от уравнения или неравенства, описваща ключовите параметри и тяхните зависимости. Биват детерминирани (машини на Тюринг, мрежи на Петри, графични модели) и вероятностни (теория на опашките, марковски процеси). Интересът им произтича от: бързата оценка (резултатите се получават за часове или минути без нужда от мощни компютри); ясната причинно-следствена картина (може да се покаже кой компонент с колко процента влияе върху производителността — нещо трудно постижимо с имитационен модел); приложимостта в процес на проектиране, когато реалната система не съществува. Основен недостатък е по-голямата грешка (~10%) спрямо имитационните модели.
Въпрос 7
Какви са предимствата и недостатъците на детерминираните и вероятностните модели?
Детерминираните модели са полезни при извеждане на формули за първо приближение и оценка на порядъка на величините. Те са прости за разработка и интерпретация. Недостатъкът им е, че заменят всеки случаен параметър с неговото средно значение, което не отразява реалната вариабилност на работното натоварване — при силно нестационарни процеси (например burst трафик) това води до значителни грешки.
Вероятностните модели по-естествено отразяват аспектите на изменчивото натоварване. Те могат да моделират разпределения на времената за обслужване и вероятности за различни типове заявки. Недостатъкът е, че някои аспекти (като корелирани заявки или реда на пристигане) са трудни за представяне; при сложни системи решаването на модела изисква значителни математически усилия.
Въпрос 8
Какво представлява имитационният модел?
Имитационният модел е програма, описваща изследваната система на алгоритмичен език. Включва описание на: елементите на системата, структурата (съвкупността от връзки между елементите) и функциите на системата. Провеждат се симулационни експерименти — изпълнение на програмата с различни набори входни данни — и се събира статистика за поведението. Системното (моделното) времe е дискретно — изменя се само при настъпване на определени събития. Инструменти: специализирани симулационни езици (GPSS, SIMSCRIPT) или универсални езици (C, C++, FORTRAN). Имитационните модели постигат грешка 2–3%, но са значително по-сложни за разработка, верификация и изпълнение.
Въпрос 9
Моделът на Марини към коя група методи за оценка на производителността може да се отнесе?
Моделът на Марини е аналитичен детерминиран модел. Той дава производителността на процесора чрез формулата P = 1/(0.7·t_add + 0.3·t_mult + km·tm) [MIPS] — детерминирана математическа зависимост без вероятностни елементи. Моделът предполага фиксирани стойности на параметрите (tgadd, tmult, km, tm) и не отчита разпределение на заявките или случайности в изпълнението. Той е прост за приложение (изисква само данни от производителя на процесора) и дава бърза, макар и приближена оценка на порядъка на производителността.
Въпрос 10
Какви грешки съпътстват всяка измервателна програма? Какви са подходите за тяхното намаляване?
Основната грешка произтича от дискретния характер на системния таймер: той се актуализира периодично (интервалът варира за различните компютри), а обръщенията към него в началото и края на измерването попадат в произволни моменти спрямо тактовите импулси. Ако тестовата програма трае по-малко от един период на таймера, грешката може да е сравнима с реалното ниво на изпълнение. Допълнителна грешка идва от операционната система (планиране, прекъсвания) и от кеш ефектите (студен кеш при първо изпълнение).
Два подхода за намаляване: (а) тестовата програма обработва големи структури от данни — така времето за изпълнение е многократно по-голямо от периода на таймера и грешката е пропорционално малка; (б) изчисленията се повтарят многократно в цикъл с предварително известен брой итерации — общото измерено времe се дели на броя итерации, с което грешката е допълнително намалена.
Въпрос 11
Ако тактовата честота на процесора е 750 MHz и той дава четири резултата на такт, колко е неговата пикова производителност?
Тактовата честота е 750 MHz, което означава 750 × 10⁶ такта в секунда. При четири резултата на такт:
Pp = 750 × 10⁶ такта/с × 4 резултата/такт = 3 000 × 10⁶ MIPS = 3 GIPS
Ако резултатите са операции с плаваща запетая: 3 GFLOPS.
Важно: тази пикова производителност никога не се постига на практика — тя предполага непрекъсната работа на всички функционални устройства без никакви зависимости, закъснения или пропуски в конвейера.
Въпрос 12
Опишете методика, чрез която могат да се определят тегловните коефициенти на всяка команда.
За определяне на тегловните коефициенти се анализира честотата на изпълнение на всяка команда при изпълнение на представителен набор от реални програми (достатъчно широк клас задачи за целевото приложение). Методиката включва:
- Избор на представителен набор от програми — benchmarks, подходящи за целевото приложение (научно-технически, комерсиални, игри и т.н.).
- Инструментиране на програмите (например с профайлер) за брояне на изпълнените команди от всеки тип.
- Изпълнение на програмите и събиране на статистика.
- Нормализиране: тегловният коефициент kᵢ = (брой изпълнения на команда тип i) / (общ брой изпълнени команди).
- Верификация: проверка дали Σkᵢ = 1.
Важно: тегловните коефициенти са специфични за приложния домейн. Командната смес на Гибсън е съставена за научно-технически задачи (k = 0,33 за събиране, k = 0,04 за умножение с плаваща запетая, k = 0,175 за условни преходи). Използването й за различен тип задачи може да доведе до значителни грешки.
Въпрос 13
Каква е разликата между моделното и физическото времe в имитационните модели?
Физическото (астрономическо) времe е реалното времe, в което функционира моделираната система — изразява се в секунди, микросекунди и т.н. Моделното (системното) времe е абстрактна времева ос в имитационния модел — то се изменя дискретно, само при настъпване на определени събития (изпълнение на команда, завършване на операция, пристигане на заявка). Между две последователни събития системното времe стои неподвижно. Отношението между двете е мащабен коефициент, установяван при разработката на модела. Например, ако едно събитие в реалната система отнема 10 ns, а в модела то се обработва за 1 μs реално времe на компютъра, мащабният коефициент е 100. Дискретният характер на системното времe прави имитационното моделиране значително по-ефективно от аналогово или непрекъснато моделиране.
Упражнение 2 — Определяне влиянието на командите за преход върху ефективността на конвейер за команди
Въпрос 1
Обяснете същността на компенсационните методи за намаляване отрицателното влияние на разклонението:
а) На апаратно ниво:
Предварителен избор на адреса на разклонение — специализирана апаратура изчислява целевия адрес на прехода по-рано в конвейера, с което се намалява броят на изчистените стъпала при взет преход.
Използване на няколко потока команди (multiple instruction streams) — конвейерът поддържа паралелно два потока: един за пътя „преходът не се взема” и един за пътя „преходът се взема”. При разрешаване кой е правилният поток грешният се изхвърля. Удвоява се необходимата буферна памет.
Прогнозирано разклонение (branch prediction) — на базата на история (Branch History Table, BTB — Branch Target Buffer) се прогнозира дали преходът ще се вземе и какъв ще е целевият адрес. При правилна прогноза — нулева загуба; при грешна — изчистване. Динамичните предиктори (2-битови броячи с насищане, двустепенна адаптивна история) постигат точност 90–95%.
б) На програмно ниво:
Отложено разклонение (delayed branch) — компилаторът поставя „безвредна” команда непосредствено след командата за преход. Тази команда се изпълнява преди преходът да влезе в сила (в т.нар. branch delay slot). Ако компилаторът не намери подходяща команда, вмъква NOP. Предимство: нулева хардуерна цена; недостатък: изисква специфично знание на компилатора за архитектурата.
Въпрос 2
Освен при изпълнение на команди за преход, при какви други условия може да се наруши ритмичната работа на конвейера?
Мехурчета в конвейера (pipeline hazards) се появяват при три типа зависимости:
Структурни опасности (structural hazards) — два или повече конвейерни стъпала изискват едновременно един и същ хардуерен ресурс (напр. една обща памет за команди и данни). Решение: разделена кеш памет (Harvard архитектура) или многоцикловост.
Зависимости по данни (data hazards) — стъпало изисква резултат, все още непроизведен от предишно стъпало (напр. RAW — Read After Write: команда B чете регистър, в който команда A записва резултат, но A не е завършила записа). Решения: преотправяне (forwarding/bypassing) на резултата директно по специален път, и преподреждане на командите от компилатора.
Управляващи опасности (control hazards) — команди за преход (разгледани подробно в теорията на упражнението).
При наличие на многостъпален конвейер и суперскаларна архитектура сложността на управлението на зависимостите нараства значително.
Упражнение 3 — Анализ на конвейер за изпълнение на командите
Въпрос 1
Какви функции изпълнява IFU и EU?
IFU (Instruction Fetch Unit) е първото стъпало на двустепенния конвейер. Извлича командата от паметта (или кеш паметта), декодира я и определя действителния адрес на операнда. Натрупва достатъчно информация за изпълнение в следващата стъпало. Буферира извлечените команди в FIFO регистров файл, позволявайки относително независима работа спрямо изпълнителното устройство.
EU (Execution Unit) е второто стъпало. Изпълнява декодираната команда: аритметично-логически операции, обръщения към паметта за четене/запис. Резервира паметта при команди за достъп и освобождава я при завършване. При изпълнение на команда за (условен) преход оценява условието и при взет преход обявява съдържанието на конвейера за невалидно.
Въпрос 2
На какво се дължи зависимостта между командите в конвейера?
Зависимостта между командите (pipeline hazards) произтича от факта, че конвейерните стъпала не са напълно независими — те споделят ресурси и резултати. Конкретно: команда B може да изисква като вход резултата на команда A, преди A да е завършила (RAW зависимост по данни). Или двете команди могат едновременно да изискват достъп до паметта (структурен хазард). В разгледания модел се приема (опростяващо), че зависимости между командите не съществуват — реалните конвейери разполагат с хардуер за обнаружаване и управление на зависимостите.
Въпрос 3
Какви други ограничения на модела, освен посочените, можете да посочите?
Освен неотчитането на зависимостите между командите и безкрайната опашка към EU, моделът не отчита: реалното разпределение на командите (равновероятно за всяка група, което не съответства на реалните програми), влиянието на пропуски в кеш паметта (cache misses) — в модела паметта е с единствено латентно, ефектите от TLB (Translation Lookaside Buffer) пропуски, влиянието на прекъсванията и изключенията, и специфики на конкретните инструкционни набори.
Въпрос 4
От какво зависи вероятността p за появяване на команди от първата група?
Вероятността p (вероятността за команди, различни от достъп до памет) зависи от: типа на приложната програма (научни изчисления — висок p; бази данни с интензивен достъп до памет — нисък p), инструкционния набор (RISC архитектурите имат по-голям дял load/store спрямо CISC при еднакъв код на високо ниво), степента на оптимизация от компилатора (добрите компилатори минимизират излишните достъпи до памет чрез register allocation), и размера на обработваните структури от данни.
Упражнение 4 — Изследване работата на многостъпален конвейер
Въпрос 1
Какво налага въвеждането на степента „транслация” в конвейера?
Степента „транслация” е въведена в IDT-C6 за адресиране на фундаментален проблем при CISC архитектурите: x86 инструкциите имат неравномерна дължина и сложност. Едни инструкции се изпълняват за един такт, а сложни инструкции с индиректна адресация или с множество микроопрерации — за много тактове. Вместо да изпълнява сложните x86 инструкции директно (което изисква сложна управляваща логика), процесорът ги преобразува в прости 33-битови RISC инструкции на вградено ниво. Ядрото на процесора работи с RISC инструкции — регулярни, с еднакво форматирани, лесно конвейеризируеми. Така от гледна точка на програмиста архитектурата е x86 (CISC), а изпълнителното ядро е RISC. Степента „транслация” е именно интерфейсът между двата свята.
Въпрос 2
От какво зависи времето за изпълнение на командата в етап 5?
Времето за изпълнение в изпълнителното стъпало (etap 5 на конвейера на IDT-C6) зависи от: типа на RISC инструкцията (аритметична с фиксирана запетая е по-бърза от с плаваща, деление е по-бавно от събиране), дали операндите са готови или трябва да се изчакват (data hazards), сложността на аритметично-логическото устройство (кога именно се формира carry при събиране с голяма разрядност), и в системи с доза OOO (out-of-order) изпълнение — от наличността на функционалното устройство. В IDT-C6 конкретно: командите за достъп до данни (тип M) изискват достъп до кеша за данни, което добавя допълнително латентно.
Упражнение 5 — Анализ на производителността на операционен конвейер
Въпрос 1
С увеличаване на L разликата между tc, определено от (5.4), и действителното tc расте. Защо?
При разбиване на аритметичната операция на повече стъпала всяко стъпало изпълнява по-малка функция — логиката е по-проста. Теоретично тактът на конвейера tc = t_операция / L. На практика обаче всяко стъпало изисква фиксирано overhead от регистровото буфериране между стъпалата (латчове), логиката за управление и синхронизацията. Тъй като това overhead е постоянна добавка (независима от L), нейният относителен дял нараства с увеличаване L — оттук разликата между теоретичното и действителното tc нараства. При достатъчно голямо L overhead доминира и по-нататъшното разбиване вече не намалява такта.
Въпрос 2
Колко начина за увеличаване на производителността при обработка на вектори познавате? Кои са те?
- Увеличаване на дължината L на конвейера — с нарастване на L пределната производителност S → L нараства, но нараства и σ (времето за инициализация).
- Увеличаване на броя паралелно работещи конвейери k — при k идентични конвейера производителността нараства почти k пъти за дълги вектори.
- Използване на съставни команди (макроконвейер) — свързване на два или повече конвейера последователно без запис в паметта между тях; операциите се конвейеризират като едно цяло.
- Увеличаване на n (дължината на вектора) — при S → L само при n >> (σ + L); по-дългите вектори по-пълно амортизират инициализационното забавяне.
- Намаляване на σ (времето за инициализация) — оптимизиране на пренасянето на данни от паметта към конвейера; векторни регистри намаляват необходимостта от достъп до основната памет.
Въпрос 3
Можете ли да начертаете структурната схема на векторния процесор и да обясните предназначението на отделните функционални блокове?
Векторният процесор включва: векторни регистри (файл от висококапацитетни регистри, съхраняващи вектори — напр. 8 × 64 елемента); операционни конвейери за различни аритметични операции (събиране, умножение, деление, логически операции — всеки е дълбоко конвейеризиран); управляваща логика за декодиране на векторните команди, управление на достъпа до конвейерите и синхронизация; памет с широка шина за паралелно зареждане на векторите; скаларен процесор за управляващи изчисления (цикли, индекси, адреси). Предимството на векторните регистри е намаляване на трафика между паметта и конвейерите — веднъж заредени, векторите се обработват без допълнителни достъпи до паметта.
Въпрос 4
На колко нива може да се осигури конвейерна обработка във векторния процесор?
На три нива: (1) конвейер за команди — векторните инструкции се извличат, декодират и изпълняват в конвейер; (2) операционен (аритметичен) конвейер — аритметичните операции (напр. сумиране на два вектора) се реализират чрез многостъпален конвейер, при което всеки елемент от двата вектора минава последователно през степените; (3) макроконвейер — два или повече операционни конвейера са свързани последователно за изпълнение на съставни команди, при което изходните данни на единия конвейер служат директно за вход на следващия без междинен запис в паметта.
Въпрос 5
Може ли да се реализира векторна обработка, ако в процесора не е реализирана конвейерна обработка?
Да — теоретично е възможно, но практически неефективно. Векторна обработка означава прилагане на една операция към множество двойки операнди. Без конвейер всяка двойка ще се обработва последователно с пълно latency за всяка операция — производителността ще е идентична с тази на скаларен процесор. Ефектът от векторизацията (намалените overhead от декодиране на команди) ще е налице, но основното предимство — конвейерното припокриване на обработката на последователни елементи — ще отсъства. В реалните реализации векторните процесори задължително използват дълбоко конвейеризирани аритметични устройства.
Въпрос 6
Какви препоръки бихте дали на програмиста за максимална производителност при векторна обработка?
- Работете с дълги вектори — производителността S → L само при n >> (σ + L); кратките вектори не амортизират инициализационното забавяне.
- Избягвайте условни разклонения вътре в цикли — те нарушават непрекъснатостта на обработката.
- Осигурявайте единичен stride (стъпка 1 между елементите) при достъп до вектори — при непоследователен достъп се получават конфликти в разслоената памет.
- Използвайте съставни команди (макроконвейер) когато са налични — те елиминират ненужни записи/четения от паметта между последователни операции.
- Разпределете данните по векторните регистри максимално — достъпът до регистровия файл е много по-бърз от основната памет.
- Избягвайте зависимости между последователни векторни операции, когато е възможно — те налагат изчакване за завършване на предишната операция.
Въпрос 7
Какви са предимствата и недостатъците при използване на съставни команди?
Предимства: Елиминиране на междинния запис в паметта между операциите (значително намаляване на трафика към паметта); по-добро амортизиране на инициализационното забавяне (σ се плаща веднъж за цялата съставна операция); по-ниска честота на декодиране на команди.
Недостатъци: Необходима е специализирана хардуерна поддръжка (последователно свързани конвейери — „макроконвейер”) — по-сложен хардуер; намалена гъвкавост (съставните команди не могат да изпълняват произволни комбинации от операции, а само предварително дефинирани); размерът на двата изходни вектора трябва да съвпадат; компилаторът трябва да разпознава подходящи шаблони в кода.
Въпрос 8
Каква е разликата между съставните команди и дългите команди, използвани в VLIW процесорите?
Съставните команди обединяват конкретни аритметични операции (напр. умножение + събиране) в единична векторна инструкция, изпълнявана от фиксирана верига от конвейери. Семантиката и хардуерната поддръжка са предварително зафиксирани в архитектурата.
VLIW (Very Long Instruction Word) командите са пакети от независими прости операции, кодирани заедно в широка инструкция (64–512 бита). Компилаторът е отговорен за намирането на независими операции и тяхното опаковане. Всяка „слот” в VLIW инструкцията управлява отделно функционално устройство. VLIW не изисква специализирани конвейерни вериги — той просто паралелизира изпълнението на множество независими операции.
Ключовата разлика: съставните команди са специфични векторни операции с фиксирана семантика; VLIW е общ механизъм за изразен паралелизъм на ниво инструкции, управляван изцяло от компилатора.
Упражнение 6 — Компютри с SMP и MPP архитектури
Въпрос 1
Кои са причините за появяването и развитието на паралелните компютри?
Три основни движещи сили: (1) ограничения на скалярната архитектура — тактовата честота достига физически предели (консумация, топлоотдаване, разпространение на сигнала); (2) ненаситен апетит за изчислителна мощ — задачи от симулации на климата, ядрени реакции, биоинформатика, AI, изискват производителности, невъзможни за единичен процесор; (3) икономическа ефективност — обединяването на евтини стандартни процесори в клъстер е многократно по-изгодно от разработката на един свръхскъп специализиран процесор.
Въпрос 2
От какво зависи производителността на паралелните компютри?
От фактори, свързани с решаваната задача: преобладаващ тип аритметика (плаваща/фиксирана запетая), размер на задачата, вътрешен паралелизъм (grain size), метод за декомпозиция и разпределение между ресурсите. И от архитектурни фактори: брой и мощност на процесорите, организация на паметта (обща/разпределена), структура и пропускателна способност на комуникационната мрежа, топология на свързване, и ефективност на операционната система при управление на ресурсите.
Въпрос 3
Какви други свързвания между процесорите познавате освен хиперкуб?
Линия (конвейер), кръг, решетка (2D grid), тор (torus — кръгово замкната решетка), двоично дърво, хипердърво, crossbar (пълна мрежа), delta мрежа (многостъпална), butterfly мрежа, fat tree, mesh с директни връзки. Хиперкубът (k-битов хиперкуб: N = 2^k процесора, всеки свързан с k съседи) е сред най-широко изследваните поради добрите му свойства: диаметър log₂N, множество алтернативни пътища, лесно адресиране.
Въпрос 4
Кои са предимствата (недостатъците) на компютрите с разпределена памет?
Предимства: Елиминиране на конфликтите при достъп до обща памет; много добра мащабируемост — добавянето на нови процесори не деградира производителността на съществуващите; потенциал за масов паралелизъм (стотици до хиляди процесори).
Недостатъци: Комуникацията между процесорите е значително по-бавна от достъпа до локална памет; програмирането е значително по-сложно (MPI, PVM); значителна инвестиция в разработката на нови паралелни алгоритми; времето за предаване на съобщения може да се окаже доминиращо при задачи с висока степен на взаимодействие (фин паралелизъм); балансирането на натоварването е нетривиална задача.
Въпрос 5
Каква характеристика на компютъра се отчита с t_s/t?
Отношението t_s/t = t_comm / t_arithm изразява относителното латентно на комуникацията — колко пъти е по-бавна операцията за достъп до глобалната памет (или предаването на съобщение) в сравнение с изпълнението на аритметична/логическа операция. Ако t_s/t ≪ 1, комуникациите са бързи и паралелната система е ефективна дори при честа комуникация. Ако t_s/t ≫ 1, всяка комуникация е скъпа и системата е ефективна само при задачи с груб паралелизъм (малък брой дълги комуникационни паузи). Именно това съотношение определя границата между SMP-подходящи и MPP-подходящи задачи.
Упражнение 7 — Определяне на производителността на MPP компютри
Въпрос 1
Защо е необходимо да се осигури равномерно натоварване на процесорите?
При неравномерно разпределение на работата частта от процесорите, получили по-малко работа, завършват по-рано и после чакат останалите — времето на системата се определя от най-натоварения процесор. Ако един от P процесори обработва двойно повече данни, всички P-1 останали чакат след края на своята работа, а реалното ускорение е значително под теоретичното. Коефициентът c > 1 в модела отчита именно тази неефективност. При максимален дисбаланс ускорението клони към 1 — паралелизмът не дава никакъв ефект. Равномерното натоварване (c = 1) е предпоставка за постигане на теоретично ускорение близко до P.
Въпрос 2
Как бихте определили T(1), ако няма възможност да се използват тестови програми?
При липса на тестови програми T(1) може да се оцени: (а) аналитично — от сложността на алгоритъма (брой операции) и известните времена за изпълнение на основни операции за конкретния процесор; (б) от публикувани benchmark резултати за процесора, мащабирани спрямо размера на задачата; (в) от имитационен модел на процесора; (г) от теоретични оценки от алгоритмичния анализ — например матрично умножение на n×n матрици изисква ~2n³ операции, а при известна производителност на процесора T(1) ≈ 2n³ / P_processor.
Въпрос 3
Какво се отчита с параметъра c?
Параметърът c (коефициент на дисбаланс) отчита неравномерното натоварване на процесорите. Когато броят на редовете n се дели точно на броя на процесорите P, всеки получава n/P реда — натоварването е равномерно и c = 1. Когато P не се дели точно в n, един или няколко процесора получават повече редове от останалите. В крайния случай процесорът с най-много работа забавя цялата система. Стойността c > 1 се изчислява като отношение на максималния брой редове при един процесор към идеалния брой n/P. Минималната стойност c = 1 се постига при n кратно на P.
Упражнение 8 — Основни параметри на статичните комуникационни мрежи
Въпрос 1
Какво представлява в най-общия случай една комуникационна мрежа? Къде е мястото й?
Комуникационната мрежа е N×N многополюсник (N входа свързани с предавателите, N изхода — с приемниците), изграден от комуникационни елементи и линии за връзка. В архитектурата на паралелния компютър комуникационната мрежа е прослойката между процесорите (и/или процесорите и модулите на паметта), осигуряваща физическите пътища за предаване на данни. Нейните характеристики (диаметър, ширина на лентата, латентно) са ключов ограничаващ фактор за ефективността на цялата система.
Въпрос 2
Какви комуникационни мрежи познавате?
Статични — непроменяема топология: линия, кръг, решетка, тор, хиперкуб, дърво, хипердърво, кръг с хорди. Динамични — реконфигурируема топология: crossbar (матричен превключвател), delta мрежа, butterfly мрежа, fat tree, Omega мрежа, Clos мрежа. Статичните са подходящи за клъстери; динамичните — за тясно свързани многопроцесорни системи.
Въпрос 3
Какви са характеристиките на всяка комуникационна мрежа?
Брой компютри N; диаметър D (максимално минимално разстояние между двойка върхове); средно разстояние P; средна плътност на трафика T; наличие на алтернативни пътища (отказоустойчивост); еднотипност на всички върхове (мащабируемост — дали степента на всеки връх е постоянна и независима от N); ширина на лентата на пропускане; латентно при предаване; цена на реализация.
Въпрос 4
По какъв начин се определя пътят между предавателя и приемника?
При статичните мрежи — с алгоритъм за намиране на най-кратките пътища в граф: алгоритъм на Форд (Bellman-Ford) за графи с отрицателни тегла или алгоритъм на Дейкстра за графи с неотрицателни тегла (типично за комуникационните мрежи). Алгоритъмът определя минималния брой дъги (хопове) между всяка двойка върхове — оттам се изчисляват D, P и T. При динамични мрежи пътят се определя динамично от управляващата логика на комутиращите елементи въз основа на адреса на получателя (напр. бит-стрийп маршрутизиране при delta мрежи).
Въпрос 5
С какви параметри се оценяват статичните мрежи?
Диаметър D, средно разстояние P, средна плътност на трафика T, наличие на алтернативни пътища, еднотипност на всички възли (постоянна степен, независима от N). Допълнително: мащабируемост (лесно добавяне на нови възли), цена на реализация (брой линии за връзка), максимална широчина на лентата.
Упражнение 9 — Производителност на динамичните комуникационни мрежи
Въпрос 1
Колко основни вида комуникационни мрежи познавате? Какви са техните предимства?
Два основни вида: статични и динамични. Предимства на статичните: просто управление; ниска цена (всеки процесор е комутиращ елемент); подходящи за клъстери; добра мащабируемост при мрежи с постоянна степен. Предимства на динамичните: осигуряват директна връзка между произволни двойки компоненти; висока ширина на лентата; поддържат едновременно множество независими комуникации; подходящи за тясно свързани многопроцесорни системи (SMP, NUMA).
Въпрос 2
С какви параметри се оценяват динамичните мрежи?
Сегментиране (способност за разделяне на независими подмрежи с пълни комуникационни способности — важно за защита на данните и отказоустойчивост); ширина на лентата на пропускане B(N,M) — очакван брой заявки, приети за единица время; среден брой изгубени цикли L на заявка; вероятност за приемане P_a; латентно при предаване (брой стъпала × латентно на едно стъпало); цена (брой превключвателни елементи: crossbar изисква N×M елемента; delta мрежата — k×b×a^(k-1) елемента).
Въпрос 3
Какви други динамични мрежи познавате освен разгледаните?
Butterfly мрежа (подобна на delta, с различна топология на стъпалата), Omega мрежа (permutation network от k стъпала, всяко от N/2 превключватели 2×2), Benes мрежа (rearrangeable non-blocking), Clos мрежа (three-stage: оптимизирана за blocking probability), fat tree (йерархично дърво с увеличаваща се ширина нагоре — използвана в InfiniBand клъстери). Crossbar е специален случай: пълна non-blocking мрежа, осигуряваща едновременно всички N! пермутации.
Упражнение 10 — Влияние на кеш паметта върху времето за достъп
Въпрос 1
Какво е мястото на кеш паметта в общата структура на паметта в компютъра?
Кеш паметта заема междинно ниво в йерархията на паметта — между регистровата памет (вградена в процесора) и основната (оперативна) памет. В съвременните компютри има 2–3 нива кеш памет: L1 (в чипа, 8–128 KB, 1–4 ns), L2 (в чипа или извън него, 0,5–8 MB, 5–12 ns) и L3 (в чипа, 3–32 MB, 14–30 ns). Смисълът й е да компенсира огромната разлика в скоростта между процесора (тактова честота 1–5 GHz) и DRAM паметта (латентно 50–100 ns) чрез съхранение на актуално използваните данни в близка бърза SRAM памет.
Въпрос 2
Какво представлява локалността на обръщение по времe? Дайте примери.
Локалност по времe означава, че веднъж достъпена позиция от паметта е вероятно да бъде достъпена отново скоро. Примери: (1) цикли — след влизане в цикъл всички команди се извикват многократно; (2) извиквания на подпрограми — при рекурсивна функция тялото й се достъпва многократно; (3) горещи данни — брояч на итерации, натрупваща се сума, елемент на матрица, обработван в два вложени цикъла; (4) стекови променливи — при дълбока рекурсия горната на стека данни се достъпва постоянно.
Въпрос 3
Какво представлява локалността на обръщение по пространство? Дайте примери.
Локалност по пространство означава, че при достъп до дадена позиция, съседните позиции вероятно ще бъдат достъпени скоро. Примери: (1) последователно изпълнение на команди — в отсъствие на преходи следващата команда е на съседен адрес; (2) обхождане на масив: for(i=0; i<n; i++) A[i] — всяка итерация достъпва следващия елемент; (3) ред-по-ред обработка на матрица в C (row-major layout) — последователните елементи са в паметта в съседни адреси; (4) символни низове — обработката на текст от начало до край.
Въпрос 4
Какви структури на кеш паметта познавате?
По метода на асоциативност: директно съответствие (direct-mapped) — всеки блок от RAM съответства на точно един фрейм в кеша; бързо търсене, склонно към конфликти. Пълна асоциативност — блокът може да отиде в произволен фрейм; максимална гъвкавост, бавно търсене. n-кратна асоциативност (set-associative) — компромис: кешът е разделен на групи от n фрейма; блокът може да отиде в произволен фрейм в определена група. По стратегия за замяна: LRU, LFU (Least Frequently Used), FIFO, случайна замяна. По стратегия за запис: write-through, write-back. По организация: включваща (inclusive) или изключваща (exclusive).
Въпрос 5
Какво се разбира под понятието „ефективност” на използването на кеш паметта? Какво означава E=0 и E=1?
Ефективността E = S/a, където S е увеличението на скоростта на достъп, а a = t_m/t_c. Тя показва каква дял от теоретично максималното ускорение реално се постига. При E = 1: системата достига максималното си ускорение — всички достъпи са само до кеш паметта (p = 1, нулев пропуск). При E = 0: кеш паметта не дава никакъв ефект — системата работи като без кеш (p = 0, всички достъпи са до основната памет). В реалността E варира между 0 и 1 в зависимост от p и a.
Въпрос 6
Защо вероятността за намиране на информация в кеш паметта не може да бъде нито 0 нито 1?
Не може да е 0, защото дори при напълно случайни достъпи и малка кеш памет все ще съществуват повторни обръщения — например загрузката на командите от основния цикъл на програмата. Локалността по времe гарантира поне минимален hit rate. Не може да е 1, защото обемът на кеш паметта е многократно по-малък от обема на основната памет — не е физически възможно всички нужни данни да са в кеша едновременно. При изпълнение на нова програма (студен кеш) или при достъп до различни части от голям масив, cache miss е неизбежен. В реалността p е динамична величина, зависеща от конкретната програма и структурата на кеш паметта.
Въпрос 7
В реалният свят, от какво зависи вероятността p за намиране на търсената информация в кеш паметта?
От: размера на кеш паметта (по-голям кеш → по-висок p); размера на кешовия блок (по-голям блок → по-добро използване на локалността по пространство, до определен предел); метода на асоциативност (по-висока асоциативност → по-малко конфликти); стратегията за замяна (LRU е по-ефективна от FIFO или случайна); приложната програма (научни изчисления с регулярен достъп → висок p; бази данни с произволен достъп → по-нисък p); размера на работното множество (ако работното множество не се побира в кеша → p пада рязко); и организацията на данните (правилното наредба в паметта — row-major за C — подобрява използването на пространствената локалност).
Упражнение 11 — Конфликти при обръщение към разслоена памет
Въпрос 1
Каква е разликата между хоризонталната и вертикалната организация на паметта?
Вертикалната (йерархична) организация цели намаляване на времето за достъп до информацията чрез използване на по-бърза, но по-малка памет за най-актуалните данни. Тя включва множество нива (регистри → кеш → RAM → диск), а всяко ниво е по-бавно, по-евтино и с по-голям обем. Механизмът, управляващ движението на данни между нивата, е виртуалната памет и кеш мениджмънтът.
Хоризонталната организация цели увеличаване на броя на достъпите за единица времe без непременно намаляване на латентното за отделния достъп. Реализира се чрез разслояване: паметта се дели на N модула, като последователните адреси са в последователни модули — така N едновременни независими заявки могат да се обслужат паралелно.
Въпрос 2
Колко подхода за хоризонтална организация на паметта познавате?
Два основни: (1) Пакетна обработка — при всяко обръщение се четат N последователни думи едновременно, поставени в буфери; при следващото обръщение данните се взимат от буферите. (2) Конвейерна обработка — фиксаторите на адресите позволяват независим достъп до всеки модул с различен адрес; управляващ контролер обработва заявките по конвейерен принцип. И двата метода постигат N-кратно ускорение за последователни адреси.
Въпрос 3
Какви са недостатъците на разслоената памет?
При непоследователен достъп (програми с много преходи, разпръснати структури от данни) ефективността пада значително. При интервал q между адресите: средното времe ≈ qt/N при q ≤ N и t при q > N. Конфликтите при едновременни заявки към един и същ модул водят до принудително изчакване. Освен това за правилна работа се изисква правилно разпределение на данните по модулите (скосено разпределение, простo-числова организация), което усложнява програмирането и компилатора.
Въпрос 4
Кога възникват конфликти при обръщенията към разслоена памет?
Конфликт възниква когато процесор (или конвейерно стъпало) отправя заявка към модул памет, чиято предходна операция все още не е завършила (цикълът на паметта h такта не е изтекъл). Вероятността за конфликт нараства с: увеличаване на броя процесори N (повече потенциални конкурентни заявки), увеличаване на вероятността p за заявка на такт, намаляване на броя модули M спрямо N, и по-голям цикъл на паметта h. При непоследователен достъп с малък интервал q, множество заявки попадат в един и същ модул, което e основен източник на конфликти.
Въпрос 5
Използва ли се хоризонтална организация на паметта в еднопроцесорните системи? Кога и защо?
Да — при векторни процесори и при процесори с операционен конвейер. Едностепенната обработка на единична команда не изисква многомодулна памет, но при векторна обработка (суммиране на два вектора, умножение на матрици) процесорът може да подава непрекъснат поток заявки към паметта с един на такт. Разслоената памет осигурява честотата на доставки, необходима за поддържане на операционния конвейер зает. Ако паметта е с единичен модул, латентното на достъп h = 4–8 такта би означавало, че конвейерът стои празен по-голямата част от времето.
Въпрос 6
Синтезирайте схема, формираща адреси за разслоена памет.
При N = 2^k модула и адрес с битова ширина (m+k): младшите k бита от адреса определят номера на модула (адресите се разпределят по модули кръгово). Старшите m бита определят адреса вътре в модула. Схемата работи така: от (m+k)-битовия адрес A: номер на модул = A mod N = A[k-1:0] (долните k бита); адрес в модула = A >> k = A[m+k-1:k] (горните m бита). Тази схема гарантира, че последователните адреси A, A+1, A+2, … попадат в модули 0, 1, 2, …, N-1, 0, 1, … — равномерно и без конфликти при последователен достъп.
Упражнение 12 — Анализ на производителността на дисковата памет
Въпрос 1
От какво зависи обслужването на една заявка, отправена към диска?
Обслужването на заявка зависи от три компонента: (1) Времe за достъп (seek time) — позициониране на главата към търсената пътечка; зависи от разстоянието (брой пътечки, пресичани по пътя) и механичните характеристики на задвижващия механизъм. (2) Времe за изчакване (rotational latency) — изчакване докато търсеният сектор се завърти под главата; в средния случай равно на половин оборот (~4 ms при 7200 RPM). (3) Времe за предаване (transfer time) — физическо предаване на данните; пропорционално на броя байтове и обратно пропорционално на скоростта на въртене и плътността на записа. В допълнение: времe за обработка на заявката от контролера (~1 μs) и евентуален overhead от шинния трансфер.
Въпрос 2
Какво представлява времето за изчакване? От какво зависи то?
Времето за изчакване (rotational latency) е времето, необходимо за завъртане на диска от текущата позиция на главата до позицията на търсения сектор. Зависи от: скоростта на въртене (RPM) — по-висока скорост → по-малко латентно; текущата позиция на диска в момента на завършване на seek — случайна величина, равномерно разпределена от 0 до един пълен оборот (средната стойност е половин оборот). При 7200 RPM: период = 60/7200 = 8,33 ms; средно латентно = 4,17 ms. При 15000 RPM: период = 4 ms; средно латентно = 2 ms. В най-лошия случай латентното е равно на пълен оборот.
Въпрос 3
Как се дефинира „пропускателната способност” на един диск?
Пропускателната способност (throughput) на диска се определя като количеството данни, предавани успешно между диска и компютъра за единица времe. При суперкомпютри се измерва в MB/s при последователни трансфери на големи блокове. При транзакционни системи — в брой I/O операции за секунда (IOPS). Максималната (пикова) пропускателна способност се достига при непрекъснат последователен достъп без seek. Ефективната пропускателна способност при произволен достъп е значително по-ниска и зависи от средното seek time и rotational latency.
Въпрос 4
Какво е характерно за обработката на транзакции от входно-изходната подсистема?
Транзакционните системи (банки, резервационни системи, бази данни) се характеризират с: голям брой кратки заявки с произволен достъп; малки обеми данни на заявка; умерено латентно (потребителят очаква отговор в десетки ms); висока производителност (хиляди до десетки хиляди IOPS). Времето за обслужване е доминирано от seek и rotational latency — времето за предаване е малко. Входно-изходната подсистема трябва да поддържа многобройни паралелни заявки (queue depth), кеш за данни и интелигентно планиране на заявките (напр. elevator алгоритъм).
Въпрос 5
Защо времето за обработката на транзакции не се влияе съществено от намаляване на времето за предаване?
При транзакционни системи типичният размер на заявката е малък (от 512 байта до няколко KB). Времето за предаване на такъв блок е пренебрежимо малко (при 200 MB/s шина — под 0,05 ms) в сравнение с seek time (~5–10 ms) и rotational latency (~4 ms). Дори удвояването на скоростта на шината не би намалило общото времe за обслужване с повече от 1–2%. Напротив, подобрения в механичните характеристики на диска (по-висока RPM за намаляване на latency, или по-малък среден seek distance чрез кеширане) имат значителен ефект.
Въпрос 6
Защо при предаване на данни за научни изследвания всяко усъвършенстване в технологията на дисковете е ефективно?
При суперкомпютри и научни приложения данните са организирани в огромни последователни блокове (симулационни матрици, резултати от измервания). При последователен достъп seek time и rotational latency се плащат само веднъж за целия блок, а времето за предаване е доминиращо. При 1 GB блок и 200 MB/s шина: T_transfer = 5 s; T_seek ≈ 8 ms; T_rot ≈ 4 ms — т.е. >99% от времето е за предаване. Следователно, всяко технологично усъвършенстване, увеличаващо скоростта на предаване (по-висока плътност на записа, по-широка шина) директно намалява общото времe пропорционално.
Въпрос 7
Какво представляват дисковите матрици с излишък? Какви са техните предимства и недостатъци?
Дисковите матрици (RAID) обединяват множество физически дискове в единна логическа единица. Излишъкът (redundancy) се реализира чрез дублиране (RAID 1) или чрез контролни суми (XOR четност при RAID 3/4/5, двойна четност при RAID 6).
Предимства: Увеличена пропускателна способност чрез паралелен достъп (RAID 0, 5); отказоустойчивост — при отказ на един (или два при RAID 6) диска данните се възстановяват; горещо подмяна без спиране на работата (при апаратен RAID с hot spare); скалируемост.
Недостатъци: MTTF на матрицата е по-нисък от MTTF на единичен диск (повече дискове = повече потенциални откази); при RAID 5/6 записите са по-бавни поради необходимостта от четене + изчисляване на четността + запис; при апаратна реализация — значителна цена за контролера; при RAID 0 — нулева защита срещу загуба на данни.