2004-gre-cs-practice-book.pdf/Q17 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q17-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q17-4c9f66 == | == Вопрос: Q17-4c9f66 == | ||
| − | + | Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ADD Rs1, Rs2, Rd Add Rs1 to Rs2 and put the sum in Rd | |
| − | + | MUL Rs1, Rs2, Rd Multiply Rs1 by Rs2 and put the product in Rd | |
| − | + | ||
| − | + | Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Рассмотрим выражение ''AB ABC BC + +'', где переменные ''A'', ''B'', ''C'' находятся в регистрах R0, R1, R2. | |
| − | + | ||
| − | + | ||
| + | Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение ''AB + ABC + BC''? | ||
| + | |||
| + | === Ответы === | ||
| + | * 5 | ||
| + | * Правильный ответ: 6 | ||
| + | * 7 | ||
| + | * 8 | ||
| + | * 9 | ||
=== Объяснение === | === Объяснение === | ||
| − | < | + | Вообще странно, что менее выгодно, когда результат операции сразу доступен. Надо это вкурить. |
| − | {{cstest-source|2004-gre-cs-practice-book.pdf| | + | Граф наверно такой, в регистры влезаем |
| + | <graph> | ||
| + | digraph G{ | ||
| + | A -> MUL_R3 | ||
| + | B -> MUL_R3 | ||
| + | C -> MUL_R4 | ||
| + | MUL_R3 -> MUL_R4 | ||
| + | |||
| + | B -> MUL_R5 | ||
| + | C -> MUL_R5 | ||
| + | |||
| + | MUL_R5 -> SUM_R6 | ||
| + | MUL_R3 -> SUM_R6 | ||
| + | |||
| + | SUM_R6 -> SUM_R7 | ||
| + | MUL_R4 -> SUM_R7 | ||
| + | } | ||
| + | </graph> | ||
| + | |||
| + | При другом графе наверно не влезем. | ||
| + | |||
| + | Последовательность | ||
| + | A × B → R3 // 1 такт | ||
| + | R3 × C → R4 // 2 такта | ||
| + | |||
| + | B × C → R5 // 1 такт | ||
| + | R5 + R3 → R6 // 1 такт | ||
| + | R6 + R4 → R7 // 1 такт | ||
| + | |||
| + | {{cstest-source|2004-gre-cs-practice-book.pdf|18|17}} | ||
| + | |||
| + | |||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 06:07, 14 декабря 2024 (UTC)}} | |
| − | + | [[Категория:Процессорная архитектура]] | |
| + | [[Категория:Разобраться]] | ||
Текущая версия на 06:07, 14 декабря 2024
Вопрос: Q17-4c9f66
Некоторая конвейерная RISC-машина имеет 8 регистров общего назначения R0, R1, …, R7 и поддерживает следующие операции
ADD Rs1, Rs2, Rd Add Rs1 to Rs2 and put the sum in Rd MUL Rs1, Rs2, Rd Multiply Rs1 by Rs2 and put the product in Rd
Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций.
Рассмотрим выражение AB ABC BC + +, где переменные A, B, C находятся в регистрах R0, R1, R2.
Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение AB + ABC + BC?
Ответы
- 5
- Правильный ответ: 6
- 7
- 8
- 9
Объяснение
Вообще странно, что менее выгодно, когда результат операции сразу доступен. Надо это вкурить. Граф наверно такой, в регистры влезаем
При другом графе наверно не влезем.
Последовательность
A × B → R3 // 1 такт R3 × C → R4 // 2 такта B × C → R5 // 1 такт R5 + R3 → R6 // 1 такт R6 + R4 → R7 // 1 такт
Исходники — вопрос 17 на 18 странице книги «2004-gre-cs-practice-book.pdf»