Разбор задачи 7: TLB и служебные обращения к памяти
Условие
В аппаратуре 4-уровневая организация таблиц страниц. Размер страницы 512 байт. TLB на 3 записи. Обращения за инструкциями игнорировать. Каково минимальное и максимальное число лишних, служебных обращений в память, не связанных непосредственно с обращениями к ячейкам массивов?
extern double *a;
extern double *b;
register int i;
register double sum = 0.0;
for (i = 0; i < 70; i++)
{
sum += a[i] * b[i];
}
Шаг 0. Предположения
Ответ нужно пояснить, поэтому сначала выпишите предположения. Без них «правильного» числа нет.
iиsumв регистрах (register) — к памяти не обращаются.aиb— глобальные переменные-указатели в памяти. Без оптимизации компилятор читает их на каждой итерации (каждоеa[i]— это*(a + i)).- Промах TLB стоит 4 обращения к памяти (по одному на уровень). Попадание — 0.
- TLB вначале пуст (или содержит чужие трансляции), замещение — LRU.
- Массивы не пересекаются.
sizeof(double)= 8. - Служебные обращения = обращения к таблицам страниц + чтения указателей
aиb(они не к ячейкам массивов).
Шаг 1. Обращения одной итерации
| № | Обращение | Страница |
|---|---|---|
| 1 | прочитать указатель a |
Pa |
| 2 | прочитать a[i] |
одна из страниц массива a |
| 3 | прочитать указатель b |
Pb (может совпадать с Pa) |
| 4 | прочитать b[i] |
одна из страниц массива b |
За 70 итераций — 280 обращений: 140 к массивам и 140 к указателям.
Шаг 2. Сколько страниц
70 × 8 = 560 байт > 512, поэтому массив занимает минимум 2 страницы.
- Минимум: 2 страницы (массив начинается с начала страницы).
- Максимум: 3 страницы (начинается со смещения 504: 504 + 560 = 1064 > 1024).
Шаг 3. Минимум
Указатели a и b — на одной странице P (рядом объявлены). Массивы по 2 страницы.
На итерации нужны 3 разные страницы: P, текущая страница a, текущая страница b. TLB на 3 записи держит их все. Промахи бывают только при первом обращении к странице:
| Страница | Промахов |
|---|---|
| P (указатели) | 1 |
a: стр. 0, стр. 1 |
2 |
b: стр. 0, стр. 1 |
2 |
| итого | 5 |
Проверим LRU при переходе a на новую страницу (итерация 64): TLB = {P, A0, B0}, нужна A1 → вытесняется наименее недавно использованная. Порядок обращений P, A0, P, B0, поэтому LRU — A0. Её и вытесняем. Хорошо: B0 и P остаются.
Минимум = 5 × 4 + 140 = 20 + 140 = 160
Шаг 4. Максимум
Указатели a и b — на разных страницах Pa ≠ Pb. Массивы по 3 страницы.
На итерации нужны 4 разные страницы: Pa, A, Pb, B. Обращения идут по кругу: Pa → A → Pb → B → Pa → …
При циклическом обходе N+1 страниц через N записей LRU каждый раз вытесняет ту страницу, которая понадобится следующей. Поэтому промахивается каждое из 280 обращений.
Максимум = 280 × 4 + 140 = 1120 + 140 = 1260
Нужны ли для максимума смещения 504?
Для «каждое обращение — промах» достаточно 4 разных страниц на итерацию, то есть Pa ≠ Pb. Число страниц массивов при этом уже не влияет: промах и так на каждом обращении. Но в объяснении стоит упомянуть, что массивы могут занимать по 3 страницы — это показывает, что вы проверили и этот фактор.
Симулятор
Минимум: указатели «на одной странице», смещения 0 и 0. Максимум: «на разных страницах», смещения 504 и 504. Сравните с «в регистрах».
Альтернативные трактовки
Преподаватель примет и другой ответ, если предположения названы явно.
| Трактовка | Минимум | Максимум |
|---|---|---|
| Стандартная: указатели читаются каждую итерацию, TLB вначале пуст | 160 | 1260 |
| Только обращения к таблицам страниц (чтения указателей не считать «служебными») | 20 | 1120 |
| Указатели в регистрах (компилятор вынес чтения из цикла) | 4 × 4 = 16 (по 2 страницы на массив) | 6 × 4 = 24 (по 3 страницы) |
| TLB уже содержит страницу указателей и первые страницы массивов | 2 × 4 + 140 = 148 | 1260 |
Как записать ответ
- Выпишите обращения одной итерации:
a,a[i],b,b[i];iиsumв регистрах. - Массив 560 байт: 2–3 страницы по 512.
- Минимум: указатели на одной странице, массивы выровнены → 3 страницы на итерацию помещаются в TLB → 5 промахов × 4 = 20, плюс 140 чтений указателей = 160.
- Максимум: указатели на разных страницах → 4 страницы на итерацию при 3 записях TLB → при LRU промах на каждом из 280 обращений: 280 × 4 = 1120, плюс 140 = 1260.
- Оговорите: если не считать чтения указателей — 20 и 1120; если указатели в регистрах — максимум 24.
Практика решено 0 из 9
Шаг 1. Сколько обращений к памяти за одну итерацию делает тело цикла sum += a[i] * b[i];,
если i и sum — регистровые, а a и b — глобальные (extern) указатели? Чтение инструкций не считаем. (число)
Сколько из этих обращений за все 70 итераций не относятся к ячейкам массивов? (число)
Шаг 2. Массив из 70 double занимает 560 байт. Минимальное число страниц по 512 байт, которые он может занимать? (число)
А максимальное число страниц для того же массива? (число)
Шаг 3, минимум. Указатели a и b лежат на одной странице, каждый массив — на 2 страницах (выровнен),
TLB вначале пуст. Сколько промахов TLB за весь цикл? (число)
Сколько служебных обращений в минимальном случае (промахи × 4 уровня + чтения указателей)? (число)
Шаг 4, максимум. Указатели a и b на разных страницах, массивы по 3 страницы.
Сколько разных страниц нужно на одной итерации? (число)
При 4 разных страницах на итерацию (порядок a, a[i], b, b[i], снова a, …) и TLB на 3 записи с LRU
сколько служебных обращений за весь цикл? (число)
Компилятор с оптимизацией прочитал a и b в регистры один раз до цикла. Каким станет максимум?
Войдите, чтобы отмечать пройденные уроки.