2004-gre-cs-practice-book.pdf/Q17 — различия между версиями
Urmat A (обсуждение | вклад) |
Urmat A (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{reserve-task|[[Участник:Urmat A|Urmat A]] 14:14, 21 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Urmat A|Urmat A]] 14:14, 21 декабря 2024 (UTC)}} | ||
| + | |||
== Вопрос: Q17-4c9f66 == | == Вопрос: Q17-4c9f66 == | ||
| Строка 9: | Строка 10: | ||
Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций. | Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций. | ||
| − | Рассмотрим выражение ''AB ABC | + | Рассмотрим выражение ''AB + ABC + BC'', где переменные ''A'', ''B'', ''C'' находятся в регистрах R0, R1, R2. |
Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение ''AB + ABC + BC''? | Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение ''AB + ABC + BC''? | ||
| Строка 21: | Строка 22: | ||
=== Объяснение === | === Объяснение === | ||
| + | |||
| + | {{cstest-source|2004-gre-cs-practice-book.pdf|18|17}} | ||
| + | |||
Вообще странно, что менее выгодно, когда результат операции сразу доступен. Надо это вкурить. | Вообще странно, что менее выгодно, когда результат операции сразу доступен. Надо это вкурить. | ||
| Строка 54: | Строка 58: | ||
R6 + R4 → R7 // 1 такт | R6 + R4 → R7 // 1 такт | ||
| − | + | ===================== | |
| − | + | Ваш вариант должен работать по-другому, потому что "...однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций...". | |
| + | A × B → R3 // 2 такта, т.к результат используется непосредственно в следующей операции | ||
| + | R3 × C → R4 // 1 такт, т.к содержимое R4 не используется в следующей операции | ||
| + | |||
| + | B × C → '''R5''' // 2 такта, т.к результат используется непосредственно в следующей операции | ||
| + | '''R5''' + R3 → '''R6''' // 2 такта, т.к результат используется непосредственно в следующей операции | ||
| + | '''R6''' + R4 → R7 // 1 такт | ||
| + | Итого 8 циклов. | ||
| + | Я бы предложил следующее: | ||
| + | MUL R0, R1, R3 → 1 цикл | ||
| + | MUL R1, R2, R4 → 1 цикл | ||
| + | MUL R3, R2, R5 → 1 цикл | ||
| + | ADD R3, R4, R6 → 2 цикла, т.к результат используется непосредственно в следующей операции | ||
| + | ADD R5, R6, R7 → 1 цикл | ||
| + | Итого 6 циклов. | ||
{{question-ok|[[Участник:StasFomin|StasFomin]] 06:07, 14 декабря 2024 (UTC)}} | {{question-ok|[[Участник:StasFomin|StasFomin]] 06:07, 14 декабря 2024 (UTC)}} | ||
Версия 14:24, 21 декабря 2024
Задача зарезервирована: Urmat A 14:14, 21 декабря 2024 (UTC)
Вопрос: 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
Объяснение
Исходники — вопрос 17 на 18 странице книги «2004-gre-cs-practice-book.pdf»
Вообще странно, что менее выгодно, когда результат операции сразу доступен. Надо это вкурить.
Кто-то может это обьяснить? Это на практике так?
Граф наверно такой, в регистры влезаем
При другом графе наверно не влезем.
Последовательность
A × B → R3 // 1 такт R3 × C → R4 // 2 такта B × C → R5 // 1 такт R5 + R3 → R6 // 1 такт R6 + R4 → R7 // 1 такт
=========
Ваш вариант должен работать по-другому, потому что "...однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций...".
A × B → R3 // 2 такта, т.к результат используется непосредственно в следующей операции R3 × C → R4 // 1 такт, т.к содержимое R4 не используется в следующей операции B × C → R5 // 2 такта, т.к результат используется непосредственно в следующей операции R5 + R3 → R6 // 2 такта, т.к результат используется непосредственно в следующей операции R6 + R4 → R7 // 1 такт
Итого 8 циклов.
Я бы предложил следующее:
MUL R0, R1, R3 → 1 цикл MUL R1, R2, R4 → 1 цикл MUL R3, R2, R5 → 1 цикл ADD R3, R4, R6 → 2 цикла, т.к результат используется непосредственно в следующей операции ADD R5, R6, R7 → 1 цикл
Итого 6 циклов.