Категорична заборона на будь-яке недозволене автором використання і розмноження
2004
ЗМІСТ
TOC \o "1-2" \h \z HYPERLINK \l "_Toc65058646" Задача 01 PAGEREF _Toc65058646 \h 3
HYPERLINK \l "_Toc65058647" Задача 02 PAGEREF _Toc65058647 \h 3
HYPERLINK \l "_Toc65058648" Задача 03 PAGEREF _Toc65058648 \h 3
HYPERLINK \l "_Toc65058649" Задача 04 PAGEREF _Toc65058649 \h 4
HYPERLINK \l "_Toc65058650" Задача 05 PAGEREF _Toc65058650 \h 4
HYPERLINK \l "_Toc65058651" Задача 06 PAGEREF _Toc65058651 \h 5
HYPERLINK \l "_Toc65058652" Задача 07 PAGEREF _Toc65058652 \h 5
HYPERLINK \l "_Toc65058653" Задача 08 PAGEREF _Toc65058653 \h 6
HYPERLINK \l "_Toc65058654" Задача 09 PAGEREF _Toc65058654 \h 6
HYPERLINK \l "_Toc65058655" Задача 10 PAGEREF _Toc65058655 \h 7
HYPERLINK \l "_Toc65058656" Задача 11 PAGEREF _Toc65058656 \h 7
HYPERLINK \l "_Toc65058657" Задача 12 PAGEREF _Toc65058657 \h 7
HYPERLINK \l "_Toc65058658" Задача 13 PAGEREF _Toc65058658 \h 8
HYPERLINK \l "_Toc65058659" Задача 14 PAGEREF _Toc65058659 \h 8
HYPERLINK \l "_Toc65058660" Задача 15 PAGEREF _Toc65058660 \h 9
HYPERLINK \l "_Toc65058661" Задача 16 PAGEREF _Toc65058661 \h 9
HYPERLINK \l "_Toc65058662" Задача 17 PAGEREF _Toc65058662 \h 9
HYPERLINK \l "_Toc65058663" Задача 18 PAGEREF _Toc65058663 \h 10
HYPERLINK \l "_Toc65058664" Задача 19 PAGEREF _Toc65058664 \h 10
HYPERLINK \l "_Toc65058665" Задача 20 PAGEREF _Toc65058665 \h 10
HYPERLINK \l "_Toc65058666" Задача 21 PAGEREF _Toc65058666 \h 11
HYPERLINK \l "_Toc65058667" Задача 22 PAGEREF _Toc65058667 \h 11
HYPERLINK \l "_Toc65058668" Задача 23 PAGEREF _Toc65058668 \h 12
HYPERLINK \l "_Toc65058669" Задача 24 PAGEREF _Toc65058669 \h 12
HYPERLINK \l "_Toc65058670" Задача 25 PAGEREF _Toc65058670 \h 12
HYPERLINK \l "_Toc65058671" Задача 26 PAGEREF _Toc65058671 \h 13
HYPERLINK \l "_Toc65058672" Задача 27 PAGEREF _Toc65058672 \h 13
HYPERLINK \l "_Toc65058673" Задача 28 PAGEREF _Toc65058673 \h 14
Задача 01
Навести мовою асемблер DLX машини приклад циклічної програми та прокоментувати цю програму
Відповідь
;**************************************************************
;* *
;* Example DLX code without the use of loop unrolling and *
;* rescheduling. *
;* Assumtions: *
;* R1 initially holds the value 0 *
;* A is an integer array, stored beginning at address 0 *
;* B is an integer array, stored beginning at address 4000 *
;* *
;**************************************************************
Loop:
lw r2,0(r1) ;get next A value
lw r3,40(r1) ;get next B value
add r2,r2,r3 ;update A
sw 1000(r1),r2 ;store new A
addi r1,r1,#4 ;update counter
subi r4,r1,#4000 ;check to see if done
bnez r4,Loop ;repeat loop if not done
trap 0 ;end, return of control to monitor
Задача 02
Прокомпілювати while-цикл до RICS-коду за умови, що i, j, k зберігаються у регістрах $s3, $s4, $s5 відповідно, а базу масиву save зберігає $s5
Відповідь
Далі символом “доллар” починають позначення регістрів (MIPS асемблер). Первісний цикл мови Сі має вид:
while (save[i] == k) i = i + j;
Першим кроком завантажуємо до тимчасового регістра, а саме
Наступна інструкція має виконати тест циклу з виходом, якщо EMBED Equation.3 .
Ще одна інструкція має додати j до і:
Завершення чергової ітерації циклу, як правило спричинює його повторювання від початку. Тому наступною є інструкція
Задача 03
Навести приклад суперскалярної диспетчеризації програмного коду, наданого фрагментом :
Відповідь
Перші три інструкції скалярного коду мають залежність даних так само, як і останні дві. Припустимо, що операції load/store виконує другий конвеєр суперскалярної машини. Тоді диспетчеризований суперскалярний код, де скасовано зазначені залежності даних, набуде після автоматичної диспетчеризації наступного виду:
Потрібні часові витрати скоротилися з 5-ти до 4-х тактових інтервалів. Переставлено місцями дві інструкції додавання аби вичерпати небезпеку існуючі у скалярному коді залежності даних. При цьому лише на 4-му такті вдалося завантажити обидва конвеєри. Ідеальний (без врахування несумісності конвеєрів та залежностей даних) випадок забезпечив би часові витрати із значенням 0.5 такту на інструкцію при використанні двох конвеєрів. Ми отримали реальне значення 0.8 = 4/5 такти на одну інструкцію.
Задача 04
Навести приклад суперскалярної диспетчеризації програмного коду з розгортуванням циклів, якщо надано наступний фрагмент недиспетчеризованого скалярного коду процесора MIPS (класу DLX):
Тут символом “доллар” починають позначення регістрів. Літеру Т у своїй назві містять регістри тимчасового збереження локальних змінних фрагменту програми. Через $zero позначено регістр із номером нуль, який завжди містить нуль. Жирним шрифтом позначено регістри, зміна вмістимого яких обумовлює залежність поміж інструкціями за даними
Відповідь
Перші три інструкції скалярного коду мають залежність даних так само, як і останні дві. Припустимо, що операції load/store виконує другий конвеєр суперскалярної машини. Тоді диспетчеризований суперскалярний код, де скасовано зазначені залежності даних, набуде після автоматичної диспетчеризації з розгортуванням циклів наступного виду:
Зауважимо, що тут дванадцять з 14-ти інструкцій виконуються в суперскалярній моді і лише дві інструкції – в скалярній моді. Потрібні часові складають для цілого фрагменту 8 тактових інтервалів. Розгорнуто 4-и цикли. Без розгортання часові витрати наближаються до 20 тактових інтервалів. Платнею за прискорення є використання 4-х регістрів тимчасового зберігання замість одного, як у попередній задачі (регістр R3).
Задача 05
Користуючись поданими таблицею даними, показати, що не можна коректно оцінювати продуктивність комп’ютерної системи за допомогою арифметичного середнього нормалізованого часу виконання тестових програм
Відповідь
Виконаємо потрібні розрахунки і наповнемо таблицю, як це показано нижче.
Аналіз отриманих результатів
За усіма значеннями геометричних середніх обидві машини є рівноцінними. При нормалізації до А за арифметичним середнім кращою є машина А (менше значення). При нормалізації до В за арифметичним середнім кращою є машина В. При нормалізації розмірність часу зникає, що спотворює результати порівняння. Тут можлива будь-яка відповідь!
Висновок
Можна порівнювати лише характеристики, які не втрачають при обрахунку розмірність часу, в нашому випадку - це є арифметичні середні, а саме 500,5 сек та 55 сек. Зрозуміло, що кращою в останньому зазначеному сенсі є машина В (за умови, що до тесту залучено обидві програми).
Загалом, лише час виконання прикладної або тестової програми може репрезентувати продуктивність комп’ютерної системи.
Задача 06
Маємо дві реалізації тої самої ISA (instruction set architecture). Машина А має довжину тактового інтервалу 1 нс та CPI (clocks per instruction) 2,0 на деякій програмі. Машина В має довжину тактового інтервалу 2 нс та CPI=1,2 на тій самій програмі. Яка машина є швидшою та у скільки разів?
Відповідь
Зрозуміло, що обидві машини виконують ту ж саму кількість інструкцій, наприклад І. Спочатку визначимо кількість тактів, що використовує кожна машина на виконання програми. Маємо
CPU clock cycles A = I * 2,0;
CPU clock cycles B = I * 1,2.
Розрахуємо час виконання програми на кожній машині.
CPU time A = CPU clock cycles A * Clock cycle time A = I * 2,0 * 1 ns = 2* I ns.
CPU time B = CPU clock cycles B * Clock cycle time B = I * 1,2 * 2 ns = 2,4* I ns.
Ясно, що машина А є швидшою в
Execution time B / Execution time A = CPU performance A / CPU performance B =
(2,4 * I ns) / ( 2 * I ns) = 1,2.
Дійшли висновку, що А швидше від В в 1,2 рази.
Задача 07
Проектувальник компілятора намагається зробити вибір на користь одного з двох можливих варіантів компіляції деякого оператора мови програмування високого рівня. При цьому використовуються інструкції класів А, В, С, які розрізняються потрібною кількістю тактових інтервалів на виконання. Варіанти компіляції подано наступною таблицею:
При цьому проектувальник апаратури спроможний забезпечити наступну витрату тактових інтервалів у кожному класі інструкцій.
Який варіант є кращим та яке значення середнє СРІ забезпечує кожний варіант?
Відповідь
Варіант 1 виконує 2 + 1 + 2 = 5 інструкцій. Варіант 2 виконує 4 + 1 + 1 = 6 інструкцій. На перший погляд, варіант 1 є швидшим.
Розглянемо питання ретельніше. Визначимо кількість тактових інтервалів, витрачених обробкою кожного варіанту. Маємо
CPU clock cycles = EMBED Equation.3 .
Відповідно у першому та другому варіантах отримаємо, що
CPU clock cycles 1 = (2х1) + (1х2) + (2х3) = 10 cycles;
CPU clock cycles 2 = (4х1) + (1х2) + (1х3) = 09 cycles.
Виходить, що варіант 2 є скорішим. Тобто варіант 2 без втрати продуктивності можна виконувати на повільнішому CPU, хоча він і містить більше інструкцій.
Визначимо ще середнє значення кількості тактових інтервалів на виконання однієї інструкції в кожному варіанті коду.
CPI = CPU clock cycles / Instruction count
CPI 1= CPU clock cycles 1 / Instruction count 1 = 10 / 5 = 2;
CPI 2 = CPU clock cycles 2 / Instruction count 2 = 9 / 6 = 1,5.
Тобто, перевага виникає тоді, коли забезпечено менше середнє значення СРІ.
Задача 08
Визначити MIPS-рейтінг (Million Instruction Per Second) для оптимізованого та неоптимізованого варіантів коду. Припустити, що використовується оптимізуючий компілятор для машини з архітектурою load/store за наведеними нижче програмними статистиками:
Оптимізуючий компілятор скорочує в програмі (тобто оптимізує цю програму) 50% ALU-інструкцій, хоча неспроможний зменшити кількість інструкцій load, store, branch. Припустити також, що в машині реалізовано 2нс тактовий інтервал (500 MHz частота тактування) та для неоптимізованої програми досягнуто значення CPI=1,57
Відповідь
Відомо, що неоптимізоване значення
MIPS unoptimized = 500MHz / (1.57 * 106) = 318.5
Продуктивність неоптимізованого коду:
CPU TimeUnoptimized = IC Unoptimized * 1.57 * (2 * 10-9)
= 3.14 * 10-9 * IC unoptimized.
Для оптимізованого коду:
CPI optimized = [( 0.43 / 2) *1 + 0.21 * 2 + 0.12 * 2 + 0.24 * 2)] / (1- (0.43 / 2)) = 1.73.
Тут враховано, що половина АЛП інструкцій “викреслено” оптимізацією і що загальна кількість інструкцій впала. Тому,
MIPS optimized = 500 MHZ / 1.73 * 106 = 289.0.
Продуктивність оптимізованого коду є:
CPU Time Optimized = ( 0.785 * IC unoptimized ) * 1.73 * ( 2 * 10-9 )
= 2.72 * 10-9 * IC unoptimized
Висновок: оптимізований код в 3.14 / 2.72=1.15 рази швидший, проте його MIPS рейтинг менший, а саме 289 проти 318! Якість критерія MIPS є незадовільною!
Задача 09
Розглянемо машину з трьома класами інструкцій та значеннями СРІ, як то подано наступною таблицею:
Припустимо також, що ще однією таблицею подано результати компіляції деякої програми
Нехай машина має тактову частоту 500 Ми. Який компілятор подає більш швидкий код в термінах MIPS (Million Instruction Per Second)? Який час виконання має кожний код?
Відповідь
Перед усім визначимо час виконання кожного з двох прокомпільованих варіантів програм за допомогою наступних рівнянь:
Execution time = CPU clock cycles / Clock rate.
СPU clock cycles = EMBED Equation.3 .
Далі отримуємо, що
CPU clock cycles 1 = (05 * 1 + 1 * 2 + 1 * 3) * 10 9 = 10 * 10 9
CPU clock cycles 2 = (10 * 1 + 1 * 2 + 1 * 3) * 10 9 = 15 * 10 9
Тоді
Execution time 1 = 10 * 10 9 / 500 * 10 6 = 20 sec
Execution time 1 = 15 * 10 9 / 500 * 10 6 = 30 sec
Тобто, компілятор 1 генерує більш швидкий програмний код.
Зараз прорахуємо MIPS рейтинг.
MIPS = Instruction count / Execution time * 10 6
MIPS 1 = (05 + 1 + 1) * 10 9 / 20 * 10 6 = 350,
MIPS 2 = (10 + 1 + 1) * 10 9 / 30 * 10 6 = 400.
Виходить, що компілятор 2 має вищий MIPS рейтинг, проте генерує повільніший код!
Задача 10
Визначити середнє значення прискорення, що забезпечує конвеєрний варіант інформаційного тракту у порівнянні з неконвеєрним за умови, коли в неконвеєрній реалізації довжина одно тактового циклу складає 10 нс, а питома вага чотирициклових АЛП-інструкцій та умовних переходів і п'яти циклових операцій load/store дорівнює, відповідно, 40, 20 і 40 відсотків. Припустити, що складна конвеєрна реалізація збільшує довжину однотактового циклу на 10 відсотків.
Відповідь
Середній час виконання фрагменту програми складає:
10 нс * (( 40% + 20% ) * 4 + 40% * 5) = 44 нс.
Довжина циклу у конвеєрному варіанті:
10 нс + 1нс =11 нс.
Прискорення:
44 нс : 11нс = 4.
Задача 11
Визначити середнє значення прискорення , яке забезпечує конвеєрний (багато цикловий) варіант інформаційного тракту в порівнянні з прототипним (неконвеєрним, одно цикловим), за умови, що тракт утворено низкою послідовно з"єднаних вузлів із відповідною швидкодією 10 нс, 8 нс, 10 нс, 10 нс, 7 нс. При цьому складна конвеєрна реалізація вимагає збільшення тривалості опрацювання у кожному вузлі на 1 нс
Відповідь
Середній час на виконання однієї інструкції в неконвеєрному варіанті дорівнює:
10+8+10+10+7=45нс.
У конвеєрному варіанті довжина циклу становить:
10+1=11нс.
Інструкція в конвеєрі виконується за один цикл (без врахування початкової затримки), тому конвеєр забезпечує прискорення в
45:11=4.1 рази.
Задача 12
Проаналізувати вартість втрат ( в скільки разів зменшено швидкодію в порівнянні з ідеальним випадком) за рахунок існування структурної залежності типу load для конвеєрного варіанту скалярного DLX процесора. Припустити, що машина містить нойманівську головну пам’ять. Питома вага посилань на дані складає 40 відсотків у суміші інструкцій. CPI ідеальної машини дорівнює 1, а машина із структурною залежністю має прискорений в 1.05 рази цикл.
Відповідь
Середній час виконання інструкції:
Ідеальна машина не має пригальмувань конвеєра, тому для неї СРІ=1,
А середній час виконання інструкції становить
AverageInstructionTime=CPI*ClockCycleTimeIdeal.
Середній час виконання інструкції у машині із структурними залежностями є:
AverageInstructionTime=CPI*ClockCycleTime=
[(1+0.4*1)*СlockCycleTimeIdeal] : 1.05 = 1.3 * ClockCycleTimeIdeal.
Зрозуміло, що досягається (в ідеалі) прискорення в 1.3 рази.
Задача 13
Обгрунтувати доцільність диспетчеризації машинного коду компілятором з метою скасування залежності даних. При цьому розглянути результат компіляції наступної послідовності Сі-операторів:
a = b + c;
d = e * f;
за умови, що латентність завантаження дорівнює одиниці
Відповідь
Подамо диспетчеризований компілятором код:
LW Rb,b
LW Rc,c
LW Re,e ; swap instruction to avoid stall
ADD Ra,Rb,Rc
LW Rf,f
SW a,Ra ; store/load exchanged to avoid stall
SUB Rd,Re,Rf
SW d,Rd
Обидва защіплювання конвеєра
LW Rc, c з ADD Ra,Rb
та
LW Rf, f з SUB Rd,Re,Rf
скасовано.
Задача 14
Визначити, який процесор є швидшим у наступній ситуації. Існує альтернатива у виконанні інструкції умовного переходу:
- CPU A: код умови визначають окремою інструкцією порівняння, потім виконують ще одну інструкцію умовного переходу, яка тестує код умови;
- CPU B: порівняння виконується у складі єдиної інструкції умовного переходу.
В обидвох CPU інструкція умовного переходу виконується за два тактових імпульси, інші інструкції - за один тактовий імпульс. В CPU A питома вага інструкцій умовного переходу складає 20% та ще 20% від загальної кількості команд належать інструкціям порівняння, що забезпечують умовні переходи.
В CPU A робота інструкції умовного переходу є менш складною в порівнянні із роботою команди умовного переходу в CPU B. Тому в CPUA тактова частота збільшена в 1,25 рази в порівнянні з CPUB
Відповідь
Визначимо характеристику СРІ для процесора А:
CPIA=0.20*2+0.80*1=1.2.
Тоді продуктивність процесора А:
CPUtimeA=IC*1.2*ClockCycleTimeA.
Знайдемо
ClockCycleTimeB=1.25*ClockCycleTimeA
тому, що А має більше значення тактової частоти.
Порівняння не виконуються в процесорі В, саме тому 20%*80% або 25% інструкцій є тут умовні переходи, що виконуються за 2 такти, а решта інструкцій – за один такт. Тому
CPIB=0.25*2+0.75*1=1.25.
Процесор В не виконує порівнянь. Тому його програма має меншу кількість інструкцій, а саме:
ICB=0.8*ICA.
Зараз можна визначити продуктивність процесора В:
СPUtimeB = ICB*CPIB*ClockCycleTimeB
= 0.8*ICA*1.25*(1.25*ClockCycleTimeA)
= 1.25*ICA*ClockCycleTimeA.
За розглянутих умов процесор А з коротшим тактовим інтервалом є швидшим в порівнянні із процесором В з меншою довжиною програми.
Задача 15
Визначити MIPS-рейтинг (Million Instruction Per Second) для оптимізованого та неоптимізованого варіантів коду. Припустити, що використовується оптимізуючий компілятор для машини з архітектурою load/store за наведеними програмними статистиками:
Тип інструкції Питома вага Тактів на виконання
ALU ops 43% 1
Loads 21% 2
Stores 12% 2
Branches 24% 2
Оптимізуючий компілятор скорочує в програмі (тобто оптимізує цю програму) 50% ALU-інструкцій, хоча неспроможний зменшити кількість інструкцій load, store, branch. Припустити також, що в машині реалізовано 2нс тактовий інтервал (500 MHz частота тактування) та для неоптимізованої програми досягнуто значення CPI=1,57
Відповідь
Відомо, що неоптимізоване значення
MIPS unoptimized = 500MHz / (1.57 * 106) = 318.5
Продуктивність неоптимізованого коду:
CPU TimeUnoptimized = IC Unoptimized * 1.57 * (2 * 10-9)
= 3.14 * 10-9 * IC unoptimized.
Для оптимізованого коду:
CPI optimized = [( 0.43 / 2) *1 + 0.21 * 2 + 0.12 * 2 + 0.24 * 2)] / (1- (0.43 / 2)) = 1.73.
Тут враховано, що половина АЛП інструкцій “викреслено” оптимізацією і що загальна кількість інструкцій впала. Тому,
MIPS optimized = 500 MHZ / 1.73 * 106 = 289.0.
Продуктивність оптимізованого коду є:
CPU Time Optimized = ( 0.785 * IC unoptimized ) * 1.73 * ( 2 * 10-9 )
= 2.72 * 10-9 * IC unoptimized
Висновок: оптимізований код в 3.14 / 2.72=1.15 рази швидший, проте його MIPS рейтинг менший, а саме 289 проти 318! Якість критерію MIPS є незадовільною!
Задача 16
Визначити в скільки разів досягнуто середнє прискорення в машині з кешем в порівнянні з безкешовою машиною. Припустити, що кеш в 10 разів швидший від головної пам’яті. Нехай в 90% випадків CPU обмінюється інформацією з кешем.
Відповідь
Розрахунки є тривіальними. Їх можна виконати безпосередньо або за допомогою закону Амдаля. Досягається прискорення в 5,3 рази.
Задача 17
Дослідити прискорення, отримане за рахунок використання прискореного в 10 разів обладнання, за умови, що нове обладнання використовується тільки на 40% часового інтервалу опрацювання задачі
Відповідь
Використовуємо закон Амдаля. Тоді:
Частка покращення = 0.4;
Прискорення покращення = 10;
Прискорення загальне = 1 / [0.6 + ( 0.4 / 10 ) ] = 1.56.
Тобто, досягнуто прискорення не в 10, а лише в 1.56 рази.
Задача 18
Дослідити прискорення, отримане за рахунок застосування форсованого в 10 разів пристрою обчислення кореня квадратного для операндів з рухомою комою або ж, альтернативно, за рахунок дворазового прискорення виконання усіх операцій рухомої коми. При цьому має місце наступна статистика.
Питома вага часу виконання операції обчислення кореня у деякій неприскореній тестовій програмі складає 20%. А загалом операції з рухомою комою забирають також у неприскореному варіанті даної тестової програми 50% часу її виконання
Відповідь
Прискорене в 10 разів виконання лише операції обчислення кореня надає результат:
Прискорення тільки_корінь = 1/[(1-0.2)+0.2/10] = 1/0.82 = 1.22
Прискорення виконання програми за рахунок подвоєного прискорення усіх рухомих операцій надає результат:
Прискорення усі_рухомі_операції = 1/[(1-0.5) + 0.5/2.0] = 1/0.75 = 1.33
Останній результат є кращим. Висновок – система завжди має лишатися раціонально (розумно) збалансованою в сенсі швидкодії окремих її пристроїв.
Задача 19
Визначити прискорення, що отримає машина в ідеальному випадку, за умови 100-відсоткового влучення до кеша. Припустити, що машина має CPI=2, коли всі її звернення до пам’яті задовольняє кеш. В тестовій програмі всі вибирання даних є типу load/store і вибирання даних виконують 40% інструкцій програми. "Покарання" за невлучення до кешу складає 25 циклів(тактових імпульсів), а відсоток невлучень до кеша дорівнює двом
Відповідь
Перед усім визначимо продуктивність машини, що завжди влучає до кешу:
CPUexecutiontime= ( CPUclockcycles+Memorystallcycles)*Clockcycles
= ( IC*CPI+0)*Clockcycles
= IC*2.0*Clockcycl.
Зараз для машини з реальним кешем визначимо значення пригальмування при зверненні до головної пам’яті:
МемoryStallCycles= IC * MemoryReferencePerInstruction * MissRate * MissPenalty
= IC*(1+0.4)*0.02*25=IC*0.7
Тут множник (1+ 0.4) віддзеркалює одне вибирання кожною інструкцією себе та 0.4 вибирання даних. Загальна продуктивність в реальному випадку складає:
CPUexecutionTimeCache= (IC*2.0+IC*0.7) * ClockCycle
= 2.7 * IC * ClockCycle
Відношення продуктивностей є інверсним до відношення значень часу виконання. Тому
CPUexecutTimeCache/CPUexecutTime=(2.7*IC*ClockCycle)/(2.0*IC*ClockCycle) = 1.35
Задача 20
Припустимо, що розглядається вдосконалення машини через додавання апаратури виконання векторних операцій. Обчислення в векторному режимі виконуються на порядок (в 10 разів) скорше, ніж у нормальному скалярному режимі. Будемо називати питому вагу часу, коли машина знаходиться у векторному режимі (проти нормального, скалярного режиму) відсотком векторизації (percentage of vectorization).
Подати графік залежності прискорення обчислень (функція) в залежності від відсотка векторизації (аргумент).
Який відсоток векторизації забезпечує прискорення в 2 рази?
Який відсоток часу виконання треба залишатися у векторній моді, аби досягнути дворазового прискорення?
Який відсоток векторизації потрібен, аби досягнути половини максимального прискорення, яке є теоретично досяжним через уведення векторної моди?
Нехай визначений в деякий спосіб відсоток векторизації для певної програми дорівнює 70%. Група розробки апаратних засобів каже, що спроможна подвоїти швидкодію векторного обладнання, але із значними додатковими інженерними інвестиціями. Ви знаєте, що група розробки компіляторів спроможна збільшити питому вагу перебування програми у векторній моді і це треба розглядати як дійову альтернативу коштовному апаратному вдосконаленню. На скільки (суто програмно, в спосіб більш раціонального компілювання) треба підвищити питому вагу векторної моди протягом часу виконання неприскореної програми, аби досягнути того ж самого прискорення, як і при подвоєнні швидкодії векторної апаратури?
Без відповіді
Задача 21
Ваша компанія має деяку тестову програму (benchmark), яка обгрунтовано презентує ваш типову прикладну програму. Ваш вбудований процесор (embedded processor) з рейтінгом 120 MIPS (саме його ви плануєте використовувати) не містить вузла з рухомою комою, тому мусить емулювати кожну рухому операцію послідовністю цілих інструкцій. Сторонній виробник пропонує вам сумісний щодо вашого процесора копроцесор рухомої коми, аби підняти продуктивність. Копроцесор виконує рухомі операції апаратно, тобто без емуляції, тобто, швидше. Комбінація процесор/копроцесор подає рейтинг 80 MIPS на цьому тесті.
Треба застосовувати лише наступні символи під час подання відповідей на питання (1-5) цієї задачі:
I — кількість цілих інструкцій, що виконує тестова програма,
F— кількість рухомих інструкцій, що виконує тестова програма,
Y— кількість цілих інструкцій на емуляцію однієї рухомої операції,
W— час виконання тесту без копроцесора,
B— час виконання тесту з копроцесором.
Написати рівняння для MIPS рейтінга для кожної з конфігурацій (є копроцесор, нема копроцесора) із використанням лише поданих вище символів.
Для конфігурації без копроцесора виміряно, що F = 8 ??106, Y = 50, a W = 4 секунди. Знайти I.
Чому дорівнює B?
Визначити MFLOPS рейтинг для конфігурації з копроцесором?
Ваш колега по фірмі вирішив придбати копроцесор не дивлючись на те, що системі із копроцесором притаманна знижка MIPS рейтінгу у порівнянні з ізольованим процесором. Чи має ваш колега рацію? Відповідь треба довести (захистити).
Без відповіді
Задача 22
Однією з проблем, що виникає під час вимірювання MFLOPS рейтинга, є те, що не всі рухомі операції мають рівну часову складність, тобто, не усі вони мають той самий час виконання. Аби розв’язати зазначену проблему, вимірюють не прямий (натуральний) MFLOPS рейтинг, а його нормалізоване, зважене значення. Таблицею 1 подано, як автори так званого теста “Livermore Loops” (Livermore є містом, де розташовано центр військових ядерних досліджень США) кількістно визначають порівняльну складність операцій рухомої коми, аби нормалізувати ці операції. Іншими словами, натуральний (native) MFLOPS рейтинг є не тим самим, що нормалізований (normalized) MFLOPS рейтинг, на який посилаються у суперкомп’ютерній літературі. Останнє може стати несподіванкою для багатьох комп’ютерних інженерів.
Дослідимо ефект від вимірювання зваженого MFLOPS рейтинга. Нехай тестова програма SPEC CFP2000 171.swim виконується на машині Compaq AlphaServer ES40 за 287 секунд. Число операцій з рухомою комою, що складають цей тест, подано таблицею 2.
Чому дорівнює натуральний (не нормалізований) MFLOPS для 171.swim на Compaq AlphaServer ES40?
З використанням конверсійної таблиці 1 треба знайти нормалізований MFLOPS рейтинг.
Розробимо таку Сі програму, яка подає піковий (максимальний) MIPS рейтинг для машини. Викличемо цю програму на двох машинах, аби виміряти іхній піковий MIPS рейтинг. Потім викличемо SPEC CINT2000 176.gcc (знову таки на обидвох машинах). Як добре піковий MIPS прогнозує продуктивність для 176.gcc?
Таблиця 1. Реальні проти нормалізованих операцій рухомої коми
The number of normalized floating-point operations per real operation in a program used by the authors of the Livermore FORTRAN kernels, or “Livermore Loops,” to calculate MFLOPS. A kernel with one Add, one Divide, and one Sin would be credited with 13 normalized floating-point operations. Native MFLOPS won’t give the results reported for other machines on that benchmark.
Таблиця 2. Рухомі операції в тесті SPEC CFP2000 171.swim.
Без відповіді
Задача 23
Тест Dhrystone є широко розпосюдженим тестом вимірювання продуктивності комп’ютера на операціях фіксованої коми. Нехай комп’ютер А надав DA виконань тесту Dhrystone на секунду та при цьому ще показав продуктивність MIPSA (в мільонах операцій на секунду). Комп’ютер В надав DB виконань того ж тесту Dhrystone. В чому полягає софізм (хибність, що здається істиною) нижче запропонованої формули обчислення MIPS рейтінга комп’ютера В:
MIPSB = MIPSA ??(DB / DA )?
Без відповіді
Задача 24
Пропонуються три варіанти вдосконалення нової архітектури, кожний з яких забезпечує наступне прискорення деякої тестової програми (за умови його безперервної дії протягом усього часу виконання):
прискорення_1_варіант = 30,
прискорення_2_варіант = 20,
прискорення_3_варіант = 15.
Кожної миті можна реалізувати лише один з наведених варіантів (бо варіанти є несумісними в часі).
Якщо прискорення за варіантами1 та 2 можна використовувати протягом 25% часу виконання неприскореної тестової програми, тоді яку частку часу її виконання треба прискорити за варіантом 3, аби досягнути загального зменшення часу виконання в 10 разів?
Припустимо, що протягом 25%, 35% та 10% часу виконання неприскореної програми можна користуватися варіантами прискорення 1, 2 та 3 відповідно. Тоді, яку частину часу виконання програма залишиться не прискореною?
Припустимо, що для деякої тестової програми дозволена частка часу (від часу її неприскореного виконання) складає 15% для прискорення за варіантом 1 і 2 та 70% за варіантом 3. Ми намагаємося максимізувати продуктивність. Якщо можна застосувати лише один варіант покращення, тоді який саме з них потрібно вибрати? Якщо можна застосувати два варіанти покращення, тоді які саме з них потрібно вибрати?
Без відповіді
Задача 25
Виробники часто-густо пропонують комп’ютери, що мають ідентичну апаратуру та відрізняються лише частотою процесора. Наступні питання мають за мету прояснити вплив частоти на продуктивність.
З переліку-колекції комп’ютерів, поданих у звіті виконання тестів SPEC CFP2000 на www.spec.org/osg/cpu2000/results/, вибрати множину з трьох комп’ютерних моделей, що є ідентичними в тестових конфігураціях (both hardware and software) та розрізняються лише значенням тактової частоти. For each pair of models, compare the clock speedup to the SPECint_base2000 benchmark speedup. How closely does benchmark performance track clock speed? Is this consistent with the description of the SPEC benchmarks on pages 28–30?
Now the workload for the computers in part (a) is as follows: a user launches a word-processing program, opens the file of an existing fivepage text document, checks spelling, finds no errors, and finally prints the document to an inkjet printer. Suppose the execution time for this benchmark on the slowest clock rate model is 1 minute and 30 seconds, apportioned in this way: 5 seconds to load the word-processing program and the chosen document file from disk to memory, 5 seconds for the user to invoke spell checking, 1 second for spell checking to complete, 2 seconds for the user to absorb the information that there are no spelling errors, 5 seconds for the user to initiate the printing command, 2 seconds for the printing dialog box to appear, 2 seconds for the user to accept the default printing options and command that printing proceed, 8 seconds for the printer to start, and 1 minute to print the five pages. User think time—the time it takes for a human to respond after waiting for a computer reply in interactive use—improves significantly when the computer can respond to a command quickly because the user maintains better mental focus. Assume that for computer response times less than 2 seconds, any computer response time improvement is matched by double that amount of improvement in the human response time, bounded by a 0.5 second minimum human response time. What is the clock speedup and word-processing benchmark speedup for each pair of computer models? Discuss the importance of a faster processor for this workload.
Choose a desktop computer vendor that has a Web-based store and find the price for three systems that are configured identically except for processor clock rate. What is the relative price performance for each system if the workload execution time is determined only by processor clock speed ($ per MHz)? What is the relative price performance ($ per second) for each system if, during a workload execution time total of 100 seconds on the slowest system, the processor is busy 5% of the time and other system components and/or the user are busy the other 95% of the time?
Без відповіді
Задача 26
За допомогою моделі незалежних та уніфікованих запитів з боку процесорів визначити відсоток зайнятих обслуговування запитів з боку процесорів модулів глобальної пам’яті у великій системи, що складається з n процесорів та k модулів пам’яті. Рисунком подати генеральну топологію мультипроцесора на основі комутаційної мережі, що аналізується
Відповідь
Розглянемо випадок взаємно незалежних звертань від n процесорів до k модулів глобальної пам’яті у мультипроцесорній системі, топологію якої подано наступним рисунком.
Нехай на початку кожного циклу кожний процесор генерує незалежний запит на звернення до деякого модуля глобальної пам’яті. Тоді ймовірність звернення з боку будь-якого процесора до конкретного модуля пам’яті складе значення EMBED Equation.3 . Відповідно, імовірність того, що зазначений щойно процесор не буде звертатися до зазначеного модуля пам’яті, дорівнюватиме EMBED Equation.3 . Далі, імовірність того, що модуль пам’яті залишиться у даному циклі невибраним усіма n процесорами, визначиться як
EMBED Equation.3 .
При цьому зауважимо, що у випадку, коли до одного модуля пам’яті спрямовано декілька звертань з боку декількох процесорів, тоді лише одно звернення буде обслуговуватися, а решта залишатимуться в блокованому стані.
Зрозуміло, що значення p репрезентує частку модулів пам’яті, які лишаються вільними в поточному циклі. Коли кількість процесорів та кількість модулів пам’яті є дуже великою, тоді p прямує до значення
EMBED Equation.3 ,
EMBED Equation.3 .
Останнє дорівнює (1 – 1/e) = 0,63. Тобто, в середньому 63 відсотки модулів пам’яті лишаються зайнятими в великих системах. Якщо n = k = 8, тоді p набуває значення 0,66. Це не дуже відрізняється від щойно отриманого значення для великої системи. Тобто, отриманій результат на рівні 60-70 відсотків зайнятих обслуговуванням запитів процесорів модулів пам’яті лишається репрезентативним для мультипроцесорів з комутуючою мережею.
Задача 27
Спроектувати 4-вимірний гіперкуб на площину та показати можливість виконання на ньому SIMD-операцій
Відповідь
Подамо наступним рисунком топологію 4-вимірного гіперкубу та її проекцію на площину. Проекція гіперкуб-мультипроцесора на площину збігається за топологією до топології массивного мультипроцесора класу SIMD і тому може функціонувати у моді SIMD, коли керуюча система розповсюджує регулярні взірці синхронізуючих повідомлень на всі процесори пулу гіперкубу.
Додатково, гіперкуб-мультипроцесор може оперувати і у моді MIMD, коли повідомлення від керуючої системи розповсюджуються серед процесорів пулу з метою їхнього кооперування при розв’язуванні деякого завдання. Трафік зазначених повідомлень може бути сильно змінним та складатися з різних повідомлень аби забезпечити виконання поточної роботи з обробки прикладної програми.
Задача 28
Навести приклад реалізації критичної секції при зверненні до спільних змінних з боку різних задач мультипроцесора
Відповідь
Реалізацію так званої критичної секції програми мультипроцесора можна подати в наступний спосіб.
Розглянемо спільну змінну, що зберігається у глобальній пам’яті, SUM, яку опрацьовують обидві задачі TASK1 (Т1) та TASK2 (Т2). Нехай ці задачі виконують різні процесори . Нехай також кожна задача незалежно маніпулює із спільною змінною в наступний спосіб.
Задача зчитує поточне значення SUM, виконує операцію, що залежить від значення SUM та поновлює SUM у глобальній пам’яті. Можна уявити виникнення наступної помилки під час опрацювання звернення типу читання-модифікація-запис.
Припустимо, що обидва завдання зчитують поточне значення SUM, наприклад 17 і починають незалежну локальну обробку цієї змінної. Задача Т1 додає 5 і отримує результат 22, а задача Т2 віднімає 7 та отримує результат 10. При запису до глобальної пам’яті спочатку відпрацьовує Т2, потім Т1.Глобальна змінна SUM вміщуватиме хибне значення 22 в той час, як правдиве значення є 15 (= 17 + 5 – 7).
Аби гарантувати коректну роботу із спільною змінною треба застосувати ексклюзивний доступ кожної задачі до спільної змінної, наприклад, за допомогою також глобальної допоміжної змінної LOCK(BYTE) та допоміжної машинної інструкції test-and-set (TAS, TAS.B – при роботі із байтовою інформаційною одиницею LOCK(BYTE)). Змінна LOCK(BYTE) може містити лише два різні значення – нуль та одиницю. Нововпровадження зможе гарантувати, що лише одна задача в стані в той самий час модифікувати значення спільної змінної. Потрібно зауважити, що послідовність інструкцій кожної задачі, що маніпулює із спільною змінною, має назву критичної секції програми.
LOCK(BYTE) використовують в наступний спосіб. Вона дорівнює нулеві тоді, коли жодна задача не знаходиться у власній критичній секції. Коли будь-яка задача модифікувати SUM, тоді вона спочатку перевіряє значення LOCK та надає одиничного значення для LOCK не звертаючи уваги на її оригінальне значення. Якщо при цьому оригінальне значення було нульовим, тоді задача розпочинає обробку SUM, оскільки жодна інша задача не працює із цією змінною. Якщо ж оригінальне значення було 1, тоді наша задача отримує інформацію про то, що якась інша задача працює із змінною SUM і треба почекати кінця поточної обробки SUM, що виконує інша задача, яка, до речі, наприкінці власної роботи скине LOCK в значення нуль.
У зазначених вище фрагментах програм інструкцію BMI (branch if minus, перейти, якщо одиниця) використовують задля організації циклу очікування на звільнення спільної змінної від сторонньої обробки з боку іншого процесу. Скидання змінної LOCK (LOCKBYTE) наприкінці роботи критичної секції виконують інструкцією CLR.B.
End of Document
