игра брюс 2048
Главная / Аппаратное обеспечение / Архитектура параллельных вычислительных систем / Тест 6

Архитектура параллельных вычислительных систем - тест 6

Упражнение 1:
Номер 1
Составьте взвешенный информационный граф счета линейного (непрерываемого) участка программы, содержащего условия. Сложение производится за 2 такта, умножение - за 4 такта,  деление - за 5 тактов. Логические операции, включая команду if-then-else, выполняются за 2 такта. Операция считывания из ОП производится не менее чем за 50 тактов. A:if a-b>0 then(c×d):f else c+e×f;
B:=if(a>b∨c>b) then A×a else c+d

Ответ:

 (1) files 

 (2) files 

 (3) files 


Номер 2
Составьте взвешенный информационный граф счета линейного (непрерываемого) участка программы, содержащего условия. Сложение производится за 2 такта, умножение - за 4 такта,  деление - за 5 тактов. Логические операции, включая команду if-then-else, выполняются за 2 такта. Операция считывания из ОП производится не менее чем за 50 тактов. A:=x×if a>b then(c+d):f else c+(a×f);
B:=ifA>0 then a×b:f else A×(c+f)

Ответ:

 (1) files 

 (2) files 

 (3) files 


Номер 3
Составьте взвешенный информационный граф счета линейного (непрерываемого) участка программы, содержащего условия. Сложение производится за 2 такта, умножение - за 4 такта,  деление - за 5 тактов. Логические операции, включая команду if-then-else, выполняются за 2 такта. Операция считывания из ОП производится не менее чем за 50 тактов. A:if a>0then ifb>c thena↑2else d×a×b else (d-e)×f
B:=if a×b>0 then A×x else 0

Ответ:

 (1) files 

 (2) files 

 (3) files 


Упражнение 2:
Номер 1
Для задачи 
A:if a-b>0 then(c×d):f else c+e×f;
B:=if(a>b∨c>b) then A×a else c+d
представьте программы линейных участков в безадресной форме. Составьте план использования неограниченного числа быстрых регистров (СОЗУ) для хранения промежуточных результатов счета. Сколько регистров потребуется?

Ответ:

 (1) if ab-0> then cd×f:else cef×+3nA; if ab>cd>∨ then Aa×else cd+3nB→​ if r1 0> then r2f:else c r3+3nA; if r4r5∨ then r6 then r7 3nB→​ if r8 then r9 else r10 3nA; if r11 then r6 else r7 3nB Требуется 11 быстрых регистров 

 (2) if ab- 0> then cd×f: else cef×+ ЗnA; if ab> cd>∨ then Aa× else cd+ЗnВ →​ if r1 0>then r2 f: else c r3+Зnr4; if r5 r6∨ then r7 else r8 ЗnВ →​ if r9 then r10 else r11 Зnr4; if r12 then r7 else r8 ЗnВ. Требуется 12 быстрых регистров 

 (3) if ab- 0> then cd×f: else cef×+ ЗnА; if ab>cd>∨ then Aa× else cd+ЗnВ →​ if r1 0>then r2 f: else c r3+Зnr4; if r5 r6∨ then r7 else r8 Зnr9 →​ if r10 then r11 else r12 Зnr4; if r13 then r7 else r8 ЗnВ. Требуется 13 быстрых регистров 


Номер 2
Для задачи 
A:x×if a>b then(c+d):f else c+(a×f);
B:=ifA>0 then a×b:f else A×(c+f)
представьте программы линейных участков в безадресной форме. Составьте план использования неограниченного числа быстрых регистров (СОЗУ) для хранения промежуточных результатов счета. Сколько регистров потребуется?

Ответ:

 (1) x if ab> then cd+ f: else caf×+× ЗnА; if A0>then ab× f: else Acf+× ЗnВ →​ x if r1 then r2 f: else cr3+× ЗnА; if r4 then r5 f: else Ar6×ЗnВ →​ x if r1 then r7 else r8× Зnr9; if r4 then r10 else r11 ЗпВ →​ xr12×ЗnА; ЗпВ. Требуется 12 быстрых регистров 

 (2) x if ab>then cd+ f: else caf×+× ЗnА; if A0> then ab× f: else Acf+× ЗnВ →​ x if r1 then r2 f: else cr3+× ЗnА; if r4 then r5 f: else Ar6× ЗnВ →​ x if r1 then r7 else r8×ЗnА; if r4 then r9 else r10 ЗnВ →​ xr11× ЗnА; ЗnВ. Требуется 11 быстрых регистров 

 (3) x if ab> then cd+ f: else caf×+× ЗnА; if A0> then ab× f: else Acf+× ЗnВ →​ x if r1 then r2 f: else cr3+× Зnr4; if r5 then r6 f: else Ar7× Зnr8 →​ x if r1 then r9 else r10× Зnr4; if r5 then r11 else r12 Зnr8 →​ xr13×ЗnА; ЗnВ Требуется 13 быстрых регистров 


Номер 3
Для задачи 
A:if a>0then ifb>c thena↑2else d×a×b else (d-e)×f
B:=if a×b>0 then A×x else 0
представьте программы линейных участков в безадресной форме. Составьте план использования неограниченного числа быстрых регистров (СОЗУ) для хранения промежуточных результатов счета. Сколько регистров потребуется?

Ответ:

 (1) if a0 then if bc> then a↑2 else dab×× else de- f× ЗnА; if ab×0> then Ax×else 0 →​ if r1 then if r2 then r3 else dr4× else r5 f× ЗnА; if r6 0>then r7 else 0 ЗnВ →​ if r1 then if r2 then r3 else r8 else r9 ЗnА; if r10 then r7 else 0 ЗпВ →​ if r1 then r11 else r9 ЗnА; ЗnВ. Требуется 11 быстрых регистров 

 (2) if a0 then if bc> then a­2 else dab××else de- f×ЗnА; if ab×0> then Ax×else 0 →​ if r1 then if r2 then r3 else dr4×else r5 f×Зnr6; if r7 0>then r8 else 0 ЗnВ →​ if r1 then if r2 then r3 else r9 else r10 Зnr6; if r11 then r8 else 0 ЗпВ →​ if r1 then r12 else r10 ЗnА; ЗпВ. Требуется 12 быстрых регистров 

 (3) if a0 then if bc> then a↑2 else dab×× else de- f× ЗnА; if ab×0> then Ax×else 0 →​ if r1 then if r2 then r3 else dr4× else r5 f×ЗnА; if r6 0>then r7 else 0 ЗnВ →​ if r1 then if r2 then r3 else r8 else r2 ЗnА; if r9 then r7 else 0 ЗnВ →​ if r1 then r10 else r9 ЗnА; ЗnВ. Требуется 10 быстрых регистров 


Упражнение 3:
Номер 1
Переведите выражение арифметического оператора в ПОЛИЗ и, используя неограниченное количество регистров для хранения промежуточных результатов, составьте программу счета в трехадресной системе команд. X := (a+ b)× (a: c – d)

Ответ:

 (1)
1+abr1
2:acr2
3-r2dr3
4×r1r3X
 

 (2)
1:acr1
2-r1dr2
3+abr3
4×R2r3X
 

 (3)
1+abr1
2:acr2
3×r1r2r3
4-r3dX
 


Номер 2
Переведите выражение арифметического оператора в ПОЛИЗ и, используя неограниченное количество регистров для хранения промежуточных результатов, составьте программу счета в трехадресной системе команд.X := (a+ b)× (c:d)

Ответ:

 (1)
1+abr1
2:cdr2
3×r1r3X
 

 (2)
1:cdr1
2+abr2
3×r1r3X
 

 (3)
1+abr1
2×r1cr2
3:r2dX
 


Номер 3
Переведите выражение арифметического оператора в ПОЛИЗ и, используя неограниченное количество регистров для хранения промежуточных результатов, составьте программу счета в трехадресной системе команд.X := a× (b+ c)+ d2

Ответ:

 (1)
1+bcr1
2×ddr2
3×ar1r3
4+r3r2X
 

 (2)
1×ddr1
2+bcr2
3×ar2r3
4+r3r1X
 

 (3)
1×ddr1
2+bcr2
3+r1r2r3
4×ar3X
 


Упражнение 6:
Номер 1
Ответьте на вопросы обоснования методов компоновки "длинных" командных слов (широкой команды - по другой терминологии) в архитектурах ВС, управляемых в каждом такте. Почему компоновку командных слов целесообразно производить на этапе трансляции?

Ответ:

 (1) статический режим компоновки командных слов сокращает объем и функции оборудования 

 (2) однажды сформированный программный код не меняется на всем протяжении жизненного цикла программы. Поэтому его целесообразно оптимизировать на этапе трансляции 

 (3) распределенный между процессорами вычислительный ресурс не разделяется между программами. Порядок его использования одной программой остается неизменным. Поэтому целесообразно оптимизировать этот порядок на этапе трансляции 

 (4) динамическое распределение вычислительного ресурса никогда не достигает той степени оптимизации, что единственно возможна при статическом распределении 

 (5) задача оптимального распределения вычислительного ресурса - задача высокой сложности. Поэтому она может решаться только в статическом режиме 


Номер 2
Ответьте на вопросы обоснования методов компоновки "длинных" командных слов (широкой команды - по другой терминологии) в архитектурах ВС, управляемых в каждом такте. Каково соотношение между элементами статики и динамики в алгоритме составления оптимального потактового расписания  для многофункционального АЛУ?

Ответ:

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

 (2) компоновка "длинных" командных слов производится в статическом режиме, как и вся трансляция. Однако в основе составления расписания лежит диспетчер динамического распараллеливания 

 (3) сочетание элементов статики и динамики приводит к значительному снижению трудоемкости алгоритма планирования 

 (4) малый выигрыш от применения процедур оптимизации (минимизации времени выполнения программы) позволяет сосредоточить усилия на построении "быстрых" динамических компоновщиков, используемых на последнем этапе статической трансляции 


Номер 3
Ответьте на вопросы обоснования методов компоновки "длинных" командных слов (широкой команды - по другой терминологии) в архитектурах ВС, управляемых в каждом такте.  Проведите обоснование выполнения компоновки "длинных" командных слов внутри непрерываемых участков программы

Ответ:

 (1) глобальную компоновку всей программы целесообразно разбить на элементарные шаги, результаты выполнения которых остаются неизменными, т.к. "логика" вносит значительный элемент неопределенности 

 (2) в современном суперскаллере альтернативное выполнение частных работ в составе арифметических операторов, благодаря операциям if-then-else и памяти предикатов, оказывается погруженным в линейные (непрерываемые) участки программы. Условные и процедурные переходы в таком случае в большей степени характеризуют структуру программы и требуют других уровней и средств оптимизации 

 (3) компоновка "длинных" командных слов в составе линейного участка программы требует столь специфических средств распараллеливания, что выдвигается в отдельную трудно решаемую проблему 

 (4) задача глобальной оптимизации программ столь сложна, что требует разбиения на частные задачи по принципу "разделяй и властвуй" 




Главная / Аппаратное обеспечение / Архитектура параллельных вычислительных систем / Тест 6