2004-gre-cs-practice-book.pdf/Q17 — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показано 13 промежуточных версий 1 участника) | |||
| Строка 8: | Строка 8: | ||
Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций. | Операция обычно занимает один цикл; однако операция занимает два цикла, если она дает результат, необходимый для выполнения непосредственно следующей операции в последовательности операций. | ||
| − | Рассмотрим выражение ''AB ABC | + | Рассмотрим выражение ''AB + ABC + BC'', где переменные ''A'', ''B'', ''C'' находятся в регистрах R0, R1, R2. |
Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение ''AB + ABC + BC''? | Если содержимое этих трех регистров не должно изменяться, то каково минимальное количество тактов требуется для последовательности операций, которая вычисляет значение ''AB + ABC + BC''? | ||
| Строка 20: | Строка 20: | ||
=== Объяснение === | === Объяснение === | ||
| − | |||
| − | + | {{cstest-source|2004-gre-cs-practice-book.pdf|18|17}} | |
| + | |||
| + | Пример решения: | ||
| + | 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 циклов. | ||
| − | + | Ну и граф вычислений вот такой: | |
<graph> | <graph> | ||
digraph G{ | digraph G{ | ||
A -> MUL_R3 | A -> MUL_R3 | ||
B -> MUL_R3 | B -> MUL_R3 | ||
| + | |||
| + | B -> MUL_R4 | ||
C -> MUL_R4 | C -> MUL_R4 | ||
| − | |||
| − | + | MUL_R3 -> MUL_R5 | |
C -> MUL_R5 | C -> MUL_R5 | ||
| − | + | ||
MUL_R3 -> SUM_R6 | MUL_R3 -> SUM_R6 | ||
| + | MUL_R4 -> SUM_R6 | ||
SUM_R6 -> SUM_R7 | SUM_R6 -> SUM_R7 | ||
| − | + | MUL_R5 -> SUM_R7 | |
} | } | ||
</graph> | </graph> | ||
| − | + | '''PS''' Вообще архитектура RISC под капотом это сложная штука, в которой происходит множество разных процессов. В данном примере речь идет о таком понятии как [https://en.wikipedia.org/wiki/Hazard_(computer_architecture) data hazards](В русскоязычном сегменте я не нашёл толковой информации). В нашем случае идет речь о случае [https://en.wikipedia.org/wiki/Hazard_(computer_architecture)#:~:text=A%20read%20after%20write%20(RAW)%20data%20hazard%20refers%20to%20a%20situation RAW(Read after write)]. Это случай, когда возникает проблема с чтением данных из регистра. Суть в том, что данные при выполнении какой-то операции не сразу записываются в регистр. Под капотом инструкции выполняются в несколько стадий, и когда одна инструкция лезет в данные, которые использовались в другой, ещё не завершенной инструкции, то может произойти конфликтная ситуация, data hazard. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
{{question-ok|[[Участник:StasFomin|StasFomin]] 06:07, 14 декабря 2024 (UTC)}} | {{question-ok|[[Участник:StasFomin|StasFomin]] 06:07, 14 декабря 2024 (UTC)}} | ||
[[Категория:Процессорная архитектура]] | [[Категория:Процессорная архитектура]] | ||
| − | |||
Текущая версия на 20:06, 23 декабря 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
Объяснение
Исходники — вопрос 17 на 18 странице книги «2004-gre-cs-practice-book.pdf»
Пример решения:
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 циклов.
Ну и граф вычислений вот такой:
PS Вообще архитектура RISC под капотом это сложная штука, в которой происходит множество разных процессов. В данном примере речь идет о таком понятии как data hazards(В русскоязычном сегменте я не нашёл толковой информации). В нашем случае идет речь о случае RAW(Read after write). Это случай, когда возникает проблема с чтением данных из регистра. Суть в том, что данные при выполнении какой-то операции не сразу записываются в регистр. Под капотом инструкции выполняются в несколько стадий, и когда одна инструкция лезет в данные, которые использовались в другой, ещё не завершенной инструкции, то может произойти конфликтная ситуация, data hazard.