Раздел 32 · Системное программирование: Zig, ассемблер, Verilog
Симулятор кэша: cachelab на Zig
открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти
Симулятор кэша: cachelab на Zig
В прошлом уроке ты разобрал адрес на тег, индекс набора и смещение, проиграл несколько адресов на кэше прямого отображения и на двухпутевом, и написал функцию разбора адреса по параметрам S, E и B. Сегодня из этой функции вырастает целая лабораторная: программа
csim, которая читает трассу обращений к памяти в формате valgrind, проигрывает её на кэше с любыми параметрами и отвечает тремя числами: попадания, промахи, вытеснения. Мы сверим её с трассами, посчитанными руками, снимем свои трассы с обычной Zig-программы, превратим домашние задачи книги про CMYK и буфер экрана в программы, которые сами считают свои промахи, и поставим кэш между процессором Y86 и его памятью, чтобы такты наконец стали зависеть от того, куда программа ходит за данными.
Цели урока
- Читать трассу обращений в формате valgrind lackey и понимать, чем строка
Mотличается от парыLиS. - Собрать
csimиз трёх файлов: разбор трассы, ядро кэша с LRU и политиками записи, интерфейс командной строки как в лабораторной. - Сверять симулятор с трассами, посчитанными руками, и объяснять каждый исход через набор и тег.
- Снимать трассу с любой Zig-программы без valgrind, через обёртки над массивом, и понимать, чего в такой трассе нет.
- Превратить задачи книги 6.36 до 6.43 в программы и получить доли промахов, совпадающие с бумажным расчётом.
- Поставить кэш между процессором Y86 и памятью, увидеть, как такты получают штраф за промах, и посчитать CPI с кэшем и без.
Что такое cachelab
В курсе CS:APP есть лабораторная, которую делают все: cachelab. Первая её часть это симулятор кэша. На вход программа получает файл с трассой обращений к памяти, который снимает valgrind с любой настоящей программы, и параметры кэша: s, E, b. На выходе три числа. Эталонная реализация называется csim-ref, и твоя задача в лабораторной сойтись с ней на всех трассах до последнего вытеснения.
Мы сделаем ту же лабораторную на Zig, только без готового эталона: эталоном будет ручной подсчёт. И это правильный порядок. Симулятор, который не сходится с бумагой на семи строках, не стоит запускать на семи миллионах.
Ключевая мысль, на которой держится весь симулятор: данных в нём нет. Чтобы ответить, попало обращение или нет, кэшу нужен только тег в строке и бит валидности. Что лежало по адресу, ему безразлично. Поэтому строка кэша в симуляторе это три поля, а не шестьдесят четыре байта, и симулятор кэша на восемь тысяч строк занимает пару сотен килобайт.
Формат трассы: четыре буквы
Трасса обращений
в cachelab записана в формате инструмента lackey из состава valgrind. Так выглядят четыре строки настоящей трассы, снятой на Linux x86-64 командой valgrind --tool=lackey --trace-mem=yes ./prog (на macOS valgrind нет, поэтому форму покажу, а свои трассы мы снимем иначе):
I 0400d7d4,8
L 7ff000398,8
S 7ff000390,8
M 0421c7f0,4Буква это вид обращения, дальше шестнадцатеричный адрес, запятая и размер в байтах. I это выборка инструкции, L чтение данных (load), S запись (store), M изменение (modify), то есть чтение и сразу запись по тому же адресу: так выглядит x += 1. Перед I пробела нет, перед остальными есть. По этому пробелу cachelab отличает выборки инструкций от обращений к данным, а симулятор кэша данных строки I пропускает.
Размер обращения симулятор тоже не читает. В лабораторной принято, что обращение не пересекает границу блока, и все наши трассы так и устроены: массивы выровнены, а элементы не длиннее блока.
Разбор трассы ты написал в уроке про локальность, вот он ещё раз, без тестов, чтобы каталог csim собирался целиком. Тесты из того урока остаются в файле как были.
//! Трасса обращений к памяти в формате valgrind lackey.
//!
//! Каждая строка это одно обращение:
//!
//! I 0400d7d4,8 выборка инструкции, кэш данных её не видит
//! L 7ff000398,8 загрузка (load)
//! S 7ff000390,8 сохранение (store)
//! M 0421c7f0,4 модификация (modify): загрузка и сразу сохранение
//!
//! Адрес шестнадцатеричный, размер десятичный. Перед L, S и M lackey ставит
//! пробел, перед I нет; парсер принимает оба варианта и игнорирует пробелы.
//! Пустые строки и строки, начинающиеся с `#`, пропускаются: так удобно
//! подписывать эталонные трассы прямо в файле.
const std = @import("std");
/// Вид обращения. Значение это буква, которой оно записано в трассе.
pub const Kind = enum(u8) {
instruction = 'I',
load = 'L',
store = 'S',
modify = 'M',
pub fn letter(kind: Kind) u8 {
return @intFromEnum(kind);
}
/// Обращения к данным: всё, кроме выборки инструкций.
pub fn isData(kind: Kind) bool {
return kind != .instruction;
}
};
/// Одна строка трассы.
pub const Entry = struct {
kind: Kind,
addr: u64,
size: u32,
pub fn load(addr: u64, size: u32) Entry {
return .{ .kind = .load, .addr = addr, .size = size };
}
pub fn store(addr: u64, size: u32) Entry {
return .{ .kind = .store, .addr = addr, .size = size };
}
pub fn modify(addr: u64, size: u32) Entry {
return .{ .kind = .modify, .addr = addr, .size = size };
}
};
pub const ParseError = error{
BadKind,
BadAddress,
BadSize,
MissingComma,
};
/// Разбирает одну строку. Пустая строка и комментарий дают `null`.
pub fn parseLine(line: []const u8) ParseError!?Entry {
const trimmed = std.mem.trim(u8, line, " \t\r");
if (trimmed.len == 0 or trimmed[0] == '#') return null;
const kind = std.enums.fromInt(Kind, trimmed[0]) orelse return error.BadKind;
const rest = std.mem.trimStart(u8, trimmed[1..], " \t");
const comma = std.mem.indexOfScalar(u8, rest, ',') orelse return error.MissingComma;
const addr = std.fmt.parseInt(u64, rest[0..comma], 16) catch return error.BadAddress;
const size_text = std.mem.trim(u8, rest[comma + 1 ..], " \t");
const size = std.fmt.parseInt(u32, size_text, 10) catch return error.BadSize;
return .{ .kind = kind, .addr = addr, .size = size };
}
/// Построчный обход текста трассы. Помнит номер строки, чтобы ошибку можно
/// было показать пользователю с указанием места.
pub const Iterator = struct {
lines: std.mem.SplitIterator(u8, .scalar),
/// Номер последней прочитанной строки, с единицы.
line_no: usize = 0,
pub fn init(text: []const u8) Iterator {
return .{ .lines = std.mem.splitScalar(u8, text, '\n') };
}
/// Следующее обращение или `null` в конце текста.
pub fn next(it: *Iterator) ParseError!?Entry {
while (it.lines.next()) |line| {
it.line_no += 1;
if (try parseLine(line)) |entry| return entry;
}
return null;
}
};
/// Разбирает трассу целиком. Выборки инструкций остаются в результате:
/// решать, что с ними делать, будет тот, кто трассу проигрывает.
pub fn parse(gpa: std.mem.Allocator, text: []const u8) ![]Entry {
var entries: std.ArrayList(Entry) = .empty;
errdefer entries.deinit(gpa);
var it: Iterator = .init(text);
while (try it.next()) |entry| try entries.append(gpa, entry);
return entries.toOwnedSlice(gpa);
}
/// Печатает одно обращение так, как это делает lackey.
pub fn writeEntry(w: *std.Io.Writer, entry: Entry) std.Io.Writer.Error!void {
// Перед выборкой инструкции пробела нет, перед обращением к данным есть.
if (entry.kind != .instruction) try w.writeByte(' ');
try w.print("{c} {x},{d}\n", .{ entry.kind.letter(), entry.addr, entry.size });
}
/// Печатает трассу целиком.
pub fn write(w: *std.Io.Writer, entries: []const Entry) std.Io.Writer.Error!void {
for (entries) |entry| try writeEntry(w, entry);
}
/// Трасса в виде строки, для тестов и файлов.
pub fn format(gpa: std.mem.Allocator, entries: []const Entry) ![]u8 {
var out: std.Io.Writer.Allocating = .init(gpa);
defer out.deinit();
try write(&out.writer, entries);
return out.toOwnedSlice();
}На две вещи здесь посмотри второй раз. Первая: Kind это enum со значениями-буквами, поэтому разбор буквы и печать буквы это одно и то же преобразование в обе стороны, и std.enums.fromInt отсеивает всё, что не I, L, S и M. Вторая: строки, начинающиеся с #, парсер пропускает. Через минуту это станет соглашением: первая строка каждой эталонной трассы будет хранить ответ.
Ядро: наборы, LRU и три счётчика
Ядро кэша из прошлого урока тоже приведу целиком, без тестов. Оно чуть шире того, что нужно cachelab: помимо hits, misses и evictions оно считает обращения к памяти и умеет две политики записи. В самой лабораторной есть только write-back с выделением строки, и это политика по умолчанию.
//! Симулятор кэша с параметрами (s, E, b): S = 2^s наборов, E строк в наборе,
//! B = 2^b байт в блоке. Замещение LRU, счётчики как в cachelab.
//!
//! Кэш хранит только теги и служебные биты, данных в нём нет: для подсчёта
//! попаданий и промахов содержимое блоков не нужно. Размер обращения тоже не
//! учитывается: как и cachelab, считаем, что обращение не пересекает границу
//! блока. Все трассы в этом пакете так и устроены.
//!
//! Политика записи выбирается при создании:
//! .write_back запись остаётся в кэше (бит dirty), в память блок уходит
//! при вытеснении; промах записи выделяет строку (write-allocate);
//! .write_through запись сразу идёт в память, промах записи строку не
//! выделяет (no-write-allocate).
//! Счётчики `mem_reads` и `mem_writes` показывают, сколько раз кэш ходил в память.
const std = @import("std");
const trace = @import("trace.zig");
pub const Params = struct {
/// Бит индекса набора: наборов 2^s.
s: u6,
/// Строк в наборе (ассоциативность).
e: u32,
/// Бит смещения в блоке: блок 2^b байт.
b: u6,
pub fn numSets(p: Params) u64 {
return @as(u64, 1) << p.s;
}
pub fn blockBytes(p: Params) u64 {
return @as(u64, 1) << p.b;
}
/// Ёмкость C = S * E * B байт.
pub fn capacityBytes(p: Params) u64 {
return p.numSets() * p.e * p.blockBytes();
}
};
/// Адрес, разобранный на три поля: тег, индекс набора, смещение в блоке.
pub const Parts = struct {
tag: u64,
set: u64,
offset: u64,
};
/// Старшие биты адреса это тег, средние s бит выбирают набор, младшие b бит
/// это смещение внутри блока.
pub fn split(p: Params, addr: u64) Parts {
const set_mask = p.numSets() - 1;
const offset_mask = p.blockBytes() - 1;
return .{
.tag = addr >> @intCast(@as(u7, p.s) + p.b),
.set = (addr >> p.b) & set_mask,
.offset = addr & offset_mask,
};
}
pub const Outcome = enum {
hit,
miss,
/// Промах, ради которого пришлось вытеснить занятую строку.
evict,
pub fn name(o: Outcome) []const u8 {
return switch (o) {
.hit => "hit",
.miss => "miss",
.evict => "miss eviction",
};
}
};
pub const WritePolicy = enum { write_back, write_through };
pub const Stats = struct {
hits: u64 = 0,
misses: u64 = 0,
evictions: u64 = 0,
/// Блоков прочитано из памяти (каждый промах с выделением строки).
mem_reads: u64 = 0,
/// Записей в память: блоков при write-back, слов при write-through.
mem_writes: u64 = 0,
pub fn accesses(st: Stats) u64 {
return st.hits + st.misses;
}
pub fn missRate(st: Stats) f64 {
if (st.accesses() == 0) return 0;
return @as(f64, @floatFromInt(st.misses)) / @as(f64, @floatFromInt(st.accesses()));
}
};
pub const Line = struct {
valid: bool = false,
dirty: bool = false,
tag: u64 = 0,
/// Показание часов кэша при последнем обращении, для LRU.
last_used: u64 = 0,
};
/// Результат обращения из трассы: у `M` их два, загрузка и сохранение.
pub const Applied = struct {
first: Outcome,
second: ?Outcome = null,
};
pub const Cache = struct {
params: Params,
policy: WritePolicy,
/// Все строки подряд: набор i занимает lines[i*E .. (i+1)*E].
lines: []Line,
/// Часы: растут на единицу с каждым обращением.
clock: u64 = 0,
stats: Stats = .{},
pub fn init(gpa: std.mem.Allocator, params: Params, policy: WritePolicy) !Cache {
const lines = try gpa.alloc(Line, params.numSets() * params.e);
@memset(lines, .{});
return .{ .params = params, .policy = policy, .lines = lines };
}
pub fn deinit(c: *Cache, gpa: std.mem.Allocator) void {
gpa.free(c.lines);
c.* = undefined;
}
/// Строки одного набора.
pub fn set(c: *Cache, index: u64) []Line {
const start = index * c.params.e;
return c.lines[start .. start + c.params.e];
}
/// Чтение по адресу.
pub fn access(c: *Cache, addr: u64) Outcome {
return c.read(addr);
}
pub fn read(c: *Cache, addr: u64) Outcome {
const parts = split(c.params, addr);
if (c.lookup(parts)) |line| return c.hit(line);
return c.fill(parts, false);
}
pub fn write(c: *Cache, addr: u64) Outcome {
const parts = split(c.params, addr);
if (c.lookup(parts)) |line| {
const outcome = c.hit(line);
switch (c.policy) {
.write_back => line.dirty = true,
.write_through => c.stats.mem_writes += 1,
}
return outcome;
}
switch (c.policy) {
// Write-allocate: блок читается в кэш и меняется там.
.write_back => return c.fill(parts, true),
// No-write-allocate: слово уходит прямо в память, кэш не трогаем.
.write_through => {
c.clock += 1;
c.stats.misses += 1;
c.stats.mem_writes += 1;
return .miss;
},
}
}
/// Обращение из трассы: `L` это чтение, `S` запись, `M` чтение и запись
/// по одному адресу подряд. Выборка инструкции (`I`) кэш не трогает.
pub fn apply(c: *Cache, entry: trace.Entry) ?Applied {
return switch (entry.kind) {
.instruction => null,
.load => .{ .first = c.read(entry.addr) },
.store => .{ .first = c.write(entry.addr) },
.modify => .{ .first = c.read(entry.addr), .second = c.write(entry.addr) },
};
}
/// Проигрывает трассу целиком.
pub fn run(c: *Cache, entries: []const trace.Entry) void {
for (entries) |entry| _ = c.apply(entry);
}
/// Сбрасывает грязные строки в память. Нужен, чтобы при write-back
/// в `mem_writes` попали и те блоки, которые никто не успел вытеснить.
pub fn flush(c: *Cache) void {
for (c.lines) |*line| {
if (line.valid and line.dirty) c.stats.mem_writes += 1;
line.dirty = false;
}
}
fn lookup(c: *Cache, parts: Parts) ?*Line {
for (c.set(parts.set)) |*line| {
if (line.valid and line.tag == parts.tag) return line;
}
return null;
}
fn hit(c: *Cache, line: *Line) Outcome {
c.clock += 1;
line.last_used = c.clock;
c.stats.hits += 1;
return .hit;
}
/// Промах: занять свободную строку или вытеснить ту, к которой дольше
/// всех не обращались.
fn fill(c: *Cache, parts: Parts, dirty: bool) Outcome {
c.clock += 1;
c.stats.misses += 1;
c.stats.mem_reads += 1;
const line = c.victim(parts.set);
const evicted = line.valid;
if (evicted) {
c.stats.evictions += 1;
if (line.dirty) c.stats.mem_writes += 1;
}
line.* = .{ .valid = true, .dirty = dirty, .tag = parts.tag, .last_used = c.clock };
return if (evicted) .evict else .miss;
}
fn victim(c: *Cache, set_index: u64) *Line {
const lines = c.set(set_index);
var oldest = &lines[0];
for (lines) |*line| {
if (!line.valid) return line;
if (line.last_used < oldest.last_used) oldest = line;
}
return oldest;
}
};
/// Проигрывает трассу на свежем кэше и возвращает счётчики. Грязные строки
/// в конце сбрасываются, чтобы `mem_writes` при write-back был полным.
pub fn simulate(gpa: std.mem.Allocator, params: Params, policy: WritePolicy, entries: []const trace.Entry) !Stats {
var c = try Cache.init(gpa, params, policy);
defer c.deinit(gpa);
c.run(entries);
c.flush();
return c.stats;
}Пройдёмся по тому, что важно именно для симулятора.
Все строки лежат в одном срезе. Набор с номером i это отрезок lines[i*E .. (i+1)*E]. Никаких вложенных массивов и никакого отдельного выделения на набор: один alloc, один free, один @memset, чтобы каждая строка начала жизнь невалидной.
LRU это часы. У кэша есть счётчик clock, он растёт на единицу при каждом обращении, и его значение записывается в last_used строки, которую только что трогали. Жертва
при промахе это строка с наименьшим last_used, а если в наборе есть невалидная строка, она берётся раньше любой валидной. Заметь, что hit тоже обновляет last_used. Убери эту строку, и вытесняться начнёт та, что пришла первой, то есть FIFO. На маленьких трассах разница не видна, на LRU-тесте из прошлого урока видна сразу.
Вытеснение это тоже промах. Исход .evict увеличивает и misses, и evictions, поэтому в ответе лабораторной misses никогда не меньше evictions. Разница между ними это холодные промахи: блоки, которые попали в пустую строку.
M это два обращения. Функция apply разворачивает modify в read и сразу write по тому же адресу. Первое из них может промахнуться, второе попасть не может: блок только что приехал в набор, и вытеснить его между двумя половинами обращения некому. Так что M даёт либо «попадание, попадание», либо «промах, попадание», и в счётчиках hits оно всегда оставляет хотя бы единицу. В csim -v это выглядит как M 20,1 miss hit, и именно на этой строке чаще всего ошибаются те, кто считает трассу руками.
Политики записи. С write-back
запись помечает строку грязной, а в память блок уезжает при вытеснении или при финальном flush. Со сквозной записью каждая запись сразу уходит в память, а промах записи строку не выделяет. На три счётчика лабораторной политика влияет только в одном месте: промах записи при write_through не занимает строку и потому не вытесняет ничего. Мы к этому вернёмся в домашке.
csim: интерфейс лабораторной
Осталось обернуть ядро в программу с тем же интерфейсом, что у csim-ref:
csim [-v] -s <s> -E <E> -b <b> -t <trace> [-w back|through]//! Программа `csim`, симулятор кэша по трассе, с тем же интерфейсом, что
//! у cachelab:
//!
//! csim [-v] -s <s> -E <E> -b <b> -t <trace> [-w back|through]
//!
//! Печатает `hits:N misses:N evictions:N`. С `-v` перед итогом идёт каждая
//! строка трассы с результатом. Ключ `-w` выбирает политику записи и
//! добавляет строку с числом обращений к памяти.
const std = @import("std");
const cache = @import("cache.zig");
const trace = @import("trace.zig");
const max_trace_bytes = 256 << 20;
const Options = struct {
params: cache.Params,
trace_path: []const u8,
verbose: bool = false,
policy: ?cache.WritePolicy = null,
};
pub fn main(init: std.process.Init) !void {
var debug_allocator: std.heap.DebugAllocator(.{}) = .init;
defer _ = debug_allocator.deinit();
const gpa = debug_allocator.allocator();
const args = try init.minimal.args.toSlice(init.arena.allocator());
var out_buf: [4096]u8 = undefined;
var stdout = std.Io.File.stdout().writerStreaming(init.io, &out_buf);
const out = &stdout.interface;
defer out.flush() catch {};
var err_buf: [512]u8 = undefined;
var stderr = std.Io.File.stderr().writerStreaming(init.io, &err_buf);
const err = &stderr.interface;
defer err.flush() catch {};
const options = parseArgs(args) catch |e| {
try err.print("{t}\n", .{e});
try usage(err);
return e;
};
const text = std.Io.Dir.cwd().readFileAlloc(init.io, options.trace_path, gpa, .limited(max_trace_bytes)) catch |e| {
try err.print("не читается {s}: {t}\n", .{ options.trace_path, e });
return e;
};
defer gpa.free(text);
var sim = try cache.Cache.init(gpa, options.params, options.policy orelse .write_back);
defer sim.deinit(gpa);
var it: trace.Iterator = .init(text);
while (true) {
const entry = it.next() catch |e| {
try err.print("{s}:{d}: {t}\n", .{ options.trace_path, it.line_no, e });
return e;
} orelse break;
const applied = sim.apply(entry) orelse continue;
if (options.verbose) try printVerbose(out, entry, applied);
}
sim.flush();
try out.print("hits:{d} misses:{d} evictions:{d}\n", .{ sim.stats.hits, sim.stats.misses, sim.stats.evictions });
if (options.policy != null) {
try out.print("mem_reads:{d} mem_writes:{d}\n", .{ sim.stats.mem_reads, sim.stats.mem_writes });
}
}
fn printVerbose(out: *std.Io.Writer, entry: trace.Entry, applied: cache.Applied) !void {
try out.print("{c} {x},{d} {s}", .{ entry.kind.letter(), entry.addr, entry.size, applied.first.name() });
if (applied.second) |second| try out.print(" {s}", .{second.name()});
try out.writeAll("\n");
}
fn usage(w: *std.Io.Writer) !void {
try w.writeAll("csim [-v] -s <s> -E <E> -b <b> -t <trace> [-w back|through]\n");
}
fn parseArgs(args: []const []const u8) !Options {
var s: ?u6 = null;
var e: ?u32 = null;
var b: ?u6 = null;
var trace_path: ?[]const u8 = null;
var verbose = false;
var policy: ?cache.WritePolicy = null;
var i: usize = 1;
while (i < args.len) : (i += 1) {
const key = args[i];
if (std.mem.eql(u8, key, "-v")) {
verbose = true;
continue;
}
i += 1;
if (i == args.len) return error.MissingValue;
const value = args[i];
if (std.mem.eql(u8, key, "-s")) {
s = try std.fmt.parseInt(u6, value, 10);
} else if (std.mem.eql(u8, key, "-E")) {
e = try std.fmt.parseInt(u32, value, 10);
} else if (std.mem.eql(u8, key, "-b")) {
b = try std.fmt.parseInt(u6, value, 10);
} else if (std.mem.eql(u8, key, "-t")) {
trace_path = value;
} else if (std.mem.eql(u8, key, "-w")) {
policy = if (std.mem.eql(u8, value, "back"))
.write_back
else if (std.mem.eql(u8, value, "through"))
.write_through
else
return error.UnknownPolicy;
} else {
return error.UnknownOption;
}
}
if (e != null and e.? == 0) return error.ZeroLines;
return .{
.params = .{
.s = s orelse return error.MissingSetBits,
.e = e orelse return error.MissingLines,
.b = b orelse return error.MissingBlockBits,
},
.trace_path = trace_path orelse return error.MissingTrace,
.verbose = verbose,
.policy = policy,
};
}Программа читает файл целиком, гонит по нему trace.Iterator, кормит каждую строку в sim.apply и печатает то, что лабораторная ждёт увидеть в первой строке вывода. Ключ -v включает подробный режим: каждая строка трассы и её исход. Ключ -w наш, в лабораторной его нет: он выбирает политику записи и добавляет строку с числом походов в память.
Ошибки разбора трассы печатаются с номером строки, потому что Iterator считает строки, включая пустые: traces/x.trace:17: BadAddress находится глазами за секунду. Ошибки аргументов печатают подсказку и возвращают ненулевой код, как и положено программе, которую будут запускать из скриптов.
Сборка и запуск в каталоге, где лежат trace.zig, cache.zig и main.zig:
$ zig build-exe main.zig -O ReleaseFast --name csim
$ ./csim -s 4 -E 1 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:3Четыре, пять, три. Те же три числа даёт csim-ref на этой трассе. Осталось убедиться, что они правильные, а не совпали случайно.
Сверка с эталонными трассами
Трасса yi.trace из лабораторной это семь строк, и её нарочно считают руками. Вот она, вместе с нашим соглашением о первой строке: комментарий хранит параметры и ответ, парсер его пропускает, а тест шага по нему сверяет симулятор.
# csim -s 4 -E 1 -b 4: hits:4 misses:5 evictions:3
L 10,1
M 20,1
L 22,1
S 18,1
L 110,1
L 210,1
M 12,1Кэш -s 4 -E 1 -b 4: шестнадцать наборов по одной строке, блок шестнадцать байт, всего 256 байт. Индекс набора это биты с четвёртого по седьмой, тег это всё с восьмого бита и выше. Считаем.
| строка | набор | тег | что в наборе | исход |
|---|---|---|---|---|
L 10,1 | 1 | 0 | пусто | промах |
M 20,1 | 2 | 0 | пусто, затем тег 0 | промах, попадание |
L 22,1 | 2 | 0 | тег 0 | попадание |
S 18,1 | 1 | 0 | тег 0 | попадание |
L 110,1 | 1 | 1 | тег 0 | промах, вытеснение |
L 210,1 | 1 | 2 | тег 1 | промах, вытеснение |
M 12,1 | 1 | 0 | тег 2, затем тег 0 | промах, вытеснение, попадание |
Попаданий четыре: второе обращение из первого M, L 22, S 18 и второе обращение из последнего M. Промахов пять, из них два холодных и три с вытеснением. Три адреса, 0x10, 0x110 и 0x210, различаются только тегом и по очереди выбивают друг друга из набора 1: это промах по конфликту, тот самый, который лечится ассоциативностью. Проверим: две строки в наборе.
$ ./csim -v -s 4 -E 1 -b 4 -t traces/yi.trace
L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3
$ ./csim -s 4 -E 2 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:2Подробный вывод совпал с таблицей строка в строку. Двухпутевой кэш убрал одно вытеснение: 0x10 и 0x110 теперь уживаются в наборе 1, и вытесняет только третий претендент, 0x210. Промахов при этом по-прежнему пять, потому что 0x10 после двух вытеснений всё равно приходится грузить заново.
Вторая ручная трасса из лабораторной, dave.trace, на кэше из четырёх наборов:
# csim -s 2 -E 1 -b 4: hits:2 misses:3 evictions:1
L 10,4
S 18,4
L 20,4
S 28,4
S 50,4$ ./csim -v -s 2 -E 1 -b 4 -t traces/dave.trace
L 10,4 miss
S 18,4 hit
L 20,4 miss
S 28,4 hit
S 50,4 miss eviction
hits:2 misses:3 evictions:1Адрес 0x50 при четырёх наборах попадает в набор 1, тот же, что 0x10: тег другой, строка одна, вытеснение. Посчитай сам, в какой набор попал бы 0x50 при восьми наборах, и что случилось бы с последней строкой.
Дальше проще щёлкать, чем считать. В виджете лежит та же yi.trace и ещё пять трасс: обход массива подряд, матрица 4×4 по строкам и по столбцам, умножение матриц ijk и jki. Кнопка «шаг» проигрывает одно обращение, справа видно содержимое наборов и возраст каждой строки в очереди LRU, а галочка «подробно» печатает то же самое, что csim -v.
Поставь E=2 на yi.trace и посмотри, какое из трёх вытеснений исчезло. Потом переключись на «матрица 4×4 по столбцам» и найди параметры, при которых столбцовый обход промахивается не чаще строчного.
Свой генератор трасс
Valgrind на macOS нет, а трассы нужны, и не на семь строк. В уроке про локальность мы решили это обёрткой: массив, каждое обращение к которому по-настоящему читает или пишет элемент и заодно записывает адрес и размер в Tracer. Файл gen.zig, без тестов:
//! Генератор трасс из Zig-программы.
//!
//! Идея: обращения к массиву идут не напрямую, а через обёртку `Traced(T)`,
//! которая выполняет чтение или запись по-настоящему и заодно записывает
//! адрес и размер обращения в `Tracer`. Получается та же трасса, что снял бы
//! valgrind, только без инструкций и без обращений к локальным переменным,
//! которые компилятор всё равно держит в регистрах.
//!
//! Адреса в трассе виртуальные: у каждого массива свой `base`, который
//! задаёт программа. Так трасса не зависит от того, куда аллокатор положил
//! данные, и число промахов воспроизводится байт в байт.
const std = @import("std");
const cache = @import("cache.zig");
const trace = @import("trace.zig");
pub const Tracer = struct {
gpa: std.mem.Allocator,
entries: std.ArrayList(trace.Entry) = .empty,
/// Сколько обращений не удалось записать из-за нехватки памяти.
dropped: usize = 0,
/// Если задан, каждое обращение сразу проигрывается на этом кэше и в
/// список не попадает: трассу умножения матриц 128 на 128 (шесть
/// миллионов строк) незачем держать в памяти.
sink: ?*cache.Cache = null,
pub fn init(gpa: std.mem.Allocator) Tracer {
return .{ .gpa = gpa };
}
pub fn deinit(t: *Tracer) void {
t.entries.deinit(t.gpa);
t.* = undefined;
}
/// Обёртки над массивами возвращают значения, а не ошибки, поэтому
/// нехватка памяти здесь только считается; `slice` её потом покажет.
pub fn record(t: *Tracer, kind: trace.Kind, addr: u64, size: u32) void {
const entry: trace.Entry = .{ .kind = kind, .addr = addr, .size = size };
if (t.sink) |c| {
_ = c.apply(entry);
return;
}
t.entries.append(t.gpa, entry) catch {
t.dropped += 1;
};
}
pub fn slice(t: *const Tracer) error{OutOfMemory}![]const trace.Entry {
if (t.dropped > 0) return error.OutOfMemory;
return t.entries.items;
}
pub fn count(t: *const Tracer, kind: trace.Kind) usize {
var n: usize = 0;
for (t.entries.items) |entry| {
if (entry.kind == kind) n += 1;
}
return n;
}
pub fn write(t: *const Tracer, w: *std.Io.Writer) !void {
try trace.write(w, try t.slice());
}
};
/// Массив элементов T, каждое обращение к которому попадает в трассу.
pub fn Traced(comptime T: type) type {
return struct {
const Self = @This();
items: []T,
/// Виртуальный адрес нулевого элемента в трассе.
base: u64,
tracer: *Tracer,
pub fn init(tracer: *Tracer, base: u64, items: []T) Self {
return .{ .items = items, .base = base, .tracer = tracer };
}
pub fn addrOf(self: Self, index: usize) u64 {
return self.base + index * @sizeOf(T);
}
pub fn get(self: Self, index: usize) T {
self.tracer.record(.load, self.addrOf(index), @sizeOf(T));
return self.items[index];
}
pub fn set(self: Self, index: usize, value: T) void {
self.tracer.record(.store, self.addrOf(index), @sizeOf(T));
self.items[index] = value;
}
/// `x[i] += v`: одно обращение вида M, как его видит lackey.
pub fn add(self: Self, index: usize, value: T) void {
self.tracer.record(.modify, self.addrOf(index), @sizeOf(T));
self.items[index] += value;
}
/// Чтение одного поля структуры: адрес и размер только у этого поля.
pub fn getField(self: Self, index: usize, comptime field: []const u8) @FieldType(T, field) {
const addr = self.addrOf(index) + @offsetOf(T, field);
self.tracer.record(.load, addr, @sizeOf(@FieldType(T, field)));
return @field(self.items[index], field);
}
pub fn setField(self: Self, index: usize, comptime field: []const u8, value: @FieldType(T, field)) void {
const addr = self.addrOf(index) + @offsetOf(T, field);
self.tracer.record(.store, addr, @sizeOf(@FieldType(T, field)));
@field(self.items[index], field) = value;
}
};
}
/// Матрица rows на cols поверх трассируемого массива, построчно (row-major),
/// как двумерный массив в C: элемент (i, j) лежит по индексу i*cols + j.
pub fn Matrix(comptime T: type) type {
return struct {
const Self = @This();
data: Traced(T),
rows: usize,
cols: usize,
pub fn init(tracer: *Tracer, base: u64, items: []T, rows: usize, cols: usize) Self {
std.debug.assert(items.len == rows * cols);
return .{ .data = .init(tracer, base, items), .rows = rows, .cols = cols };
}
pub fn index(self: Self, i: usize, j: usize) usize {
return i * self.cols + j;
}
pub fn get(self: Self, i: usize, j: usize) T {
return self.data.get(self.index(i, j));
}
pub fn set(self: Self, i: usize, j: usize, value: T) void {
self.data.set(self.index(i, j), value);
}
pub fn add(self: Self, i: usize, j: usize, value: T) void {
self.data.add(self.index(i, j), value);
}
/// Прямой доступ без трассы: заполнить матрицу перед прогоном или
/// проверить результат после.
pub fn at(self: Self, i: usize, j: usize) *T {
return &self.data.items[self.index(i, j)];
}
};
}
/// Сумма по строкам: внутренний цикл идёт вдоль строки, шаг между
/// соседними обращениями равен размеру элемента.
pub fn sumRows(m: Matrix(i32)) i64 {
var sum: i64 = 0;
var i: usize = 0;
while (i < m.rows) : (i += 1) {
var j: usize = 0;
while (j < m.cols) : (j += 1) sum += m.get(i, j);
}
return sum;
}
/// Сумма по столбцам: те же обращения, но шаг между соседними равен
/// длине строки, и пространственная локальность пропадает.
pub fn sumCols(m: Matrix(i32)) i64 {
var sum: i64 = 0;
var j: usize = 0;
while (j < m.cols) : (j += 1) {
var i: usize = 0;
while (i < m.rows) : (i += 1) sum += m.get(i, j);
}
return sum;
}
/// Обход массива с шагом: `count` чтений с индексами 0, stride, 2*stride ...
pub fn strideWalk(x: Traced(i64), stride: usize, count: usize) i64 {
var sum: i64 = 0;
var k: usize = 0;
while (k < count) : (k += 1) sum += x.get(k * stride);
return sum;
}
/// Сколько разных блоков по 2^b байт затронула трасса: мера пространственной
/// локальности. Чем меньше блоков на то же число обращений, тем она выше.
pub fn distinctBlocks(gpa: std.mem.Allocator, entries: []const trace.Entry, b: u6) !usize {
var seen: std.AutoHashMapUnmanaged(u64, void) = .empty;
defer seen.deinit(gpa);
for (entries) |entry| {
if (!entry.kind.isData()) continue;
try seen.put(gpa, entry.addr >> b, {});
}
return seen.count();
}Трасса получается не совсем такой, как у valgrind: в ней нет выборок инструкций и нет обращений к локальным переменным, которые компилятор всё равно держит в регистрах. Зато адреса в ней виртуальные, base задаёт программа, и число промахов воспроизводится байт в байт на любой машине. Для задач про кэш это ровно то, что нужно: книга тоже считает обращения к массиву, а не к стеку.
Поле sink решает вторую проблему: трассу умножения матриц 128 на 128 незачем держать в памяти, шесть миллионов строк можно сразу скармливать симулятору. В генераторе ниже sink не пригодится: там нужен файл на диске.
Генератор это обычная программа, которая запускает несколько функций на трассируемых массивах, проигрывает каждую трассу на симуляторе и пишет файл с нашей шапкой:
//! Генератор эталонных трасс: обычная Zig-программа ходит по массиву через
//! обёртки из gen.zig, обращения ложатся в трассу, трасса уходит в файл.
//! Первая строка файла это комментарий с ответом симулятора на тех же
//! параметрах, по нему тесты потом сверяют csim.
//!
//! zig run tracegen.zig -- traces
const std = @import("std");
const book = @import("book.zig");
const cache = @import("cache.zig");
const gen = @import("gen.zig");
const matmul = @import("matmul.zig");
const trace = @import("trace.zig");
const base: u64 = 0x10000;
/// Скалярное произведение двух строк x[2][128]: задача книги 6.36.
fn dotRows(gpa: std.mem.Allocator, tracer: *gen.Tracer) !void {
const items = try gpa.alloc(i32, 2 * 128);
defer gpa.free(items);
@memset(items, 1);
_ = book.dotRows(.init(tracer, base, items, 2, 128));
}
/// Умножение матриц 8 на 8 в порядке ijk, три матрицы подряд в памяти.
fn matmulIjk(gpa: std.mem.Allocator, tracer: *gen.Tracer) !void {
const n = 8;
const items = try gpa.alloc(f64, 3 * n * n);
defer gpa.free(items);
@memset(items, 1.0);
const stride = n * n * @sizeOf(f64);
const a: matmul.Mat = .init(tracer, base, items[0 .. n * n], n, n);
const b: matmul.Mat = .init(tracer, base + stride, items[n * n .. 2 * n * n], n, n);
const c: matmul.Mat = .init(tracer, base + 2 * stride, items[2 * n * n ..], n, n);
matmul.multiply(.ijk, a, b, c);
}
/// Квадрат CMYK 16 на 16, закрашенный по столбцам: задача книги 6.38.
fn cmykColumns(gpa: std.mem.Allocator, tracer: *gen.Tracer) !void {
const items = try gpa.alloc(book.PointColor, 16 * 16);
defer gpa.free(items);
@memset(items, std.mem.zeroes(book.PointColor));
book.paintByColumns(.init(tracer, base, items, 16, 16));
}
/// Тот же квадрат по строкам: задача 6.39.
fn cmykRows(gpa: std.mem.Allocator, tracer: *gen.Tracer) !void {
const items = try gpa.alloc(book.PointColor, 16 * 16);
defer gpa.free(items);
@memset(items, std.mem.zeroes(book.PointColor));
book.paintByRows(.init(tracer, base, items, 16, 16));
}
const Spec = struct {
name: []const u8,
params: cache.Params,
run: *const fn (std.mem.Allocator, *gen.Tracer) anyerror!void,
};
const specs = [_]Spec{
.{ .name = "dot_rows", .params = .{ .s = 5, .e = 1, .b = 4 }, .run = dotRows },
.{ .name = "matmul_ijk", .params = .{ .s = 5, .e = 1, .b = 5 }, .run = matmulIjk },
.{ .name = "cmyk_columns", .params = .{ .s = 5, .e = 1, .b = 5 }, .run = cmykColumns },
.{ .name = "cmyk_rows", .params = .{ .s = 5, .e = 1, .b = 5 }, .run = cmykRows },
};
pub fn main(init: std.process.Init) !void {
var debug_allocator: std.heap.DebugAllocator(.{}) = .init;
defer _ = debug_allocator.deinit();
const gpa = debug_allocator.allocator();
const args = try init.minimal.args.toSlice(init.arena.allocator());
const dir_path = if (args.len > 1) args[1] else "traces";
var dir = try std.Io.Dir.cwd().openDir(init.io, dir_path, .{});
defer dir.close(init.io);
var buf: [4096]u8 = undefined;
var stdout = std.Io.File.stdout().writer(init.io, &buf);
const out = &stdout.interface;
for (specs) |spec| {
var tracer: gen.Tracer = .init(gpa);
defer tracer.deinit();
try spec.run(gpa, &tracer);
const entries = try tracer.slice();
const stats = try cache.simulate(gpa, spec.params, .write_back, entries);
const name = try std.fmt.allocPrint(gpa, "{s}.trace", .{spec.name});
defer gpa.free(name);
var file = try dir.createFile(init.io, name, .{});
defer file.close(init.io);
var file_buf: [4096]u8 = undefined;
var writer = file.writer(init.io, &file_buf);
const w = &writer.interface;
try w.print("# csim -s {d} -E {d} -b {d}: hits:{d} misses:{d} evictions:{d}\n", .{
spec.params.s, spec.params.e, spec.params.b, stats.hits, stats.misses, stats.evictions,
});
try trace.write(w, entries);
try w.flush();
try out.print("{s}: {d} обращений, hits:{d} misses:{d} evictions:{d}\n", .{
name, entries.len, stats.hits, stats.misses, stats.evictions,
});
}
try out.flush();
}Функции book.dotRows и book.paintByColumns мы напишем в следующем разделе, а matmul.multiply ты напишешь в следующем уроке; для генератора важен только их тип: функция от трассируемой матрицы. Запуск:
$ zig run tracegen.zig -- traces
dot_rows.trace: 256 обращений, hits:0 misses:256 evictions:224
matmul_ijk.trace: 1088 обращений, hits:1000 misses:152 evictions:120
cmyk_columns.trace: 1024 обращений, hits:768 misses:256 evictions:224
cmyk_rows.trace: 1024 обращений, hits:960 misses:64 evictions:32Так выглядит начало matmul_ijk.trace: чтения A идут по строке с шагом 8 байт, чтения B по столбцу с шагом 64, и после восьми пар одно M в C:
# csim -s 5 -E 1 -b 5: hits:1000 misses:152 evictions:120
L 10000,8
L 10200,8
L 10008,8
L 10240,8
L 10010,8
L 10280,8
L 10018,8
L 102c0,8
L 10020,8
L 10300,8
L 10028,8
L 10340,8
L 10030,8
L 10380,8
L 10038,8
L 103c0,8
M 10400,8
L 10000,8
L 10208,8Файл с шапкой проходит через csim как любая другая трасса, шапка это комментарий:
$ ./csim -s 5 -E 1 -b 5 -t traces/matmul_ijk.trace
hits:1000 misses:152 evictions:120
$ ./csim -v -s 5 -E 1 -b 5 -t traces/matmul_ijk.trace | tail -3
L 103f8,8 hit
M 105f8,8 miss eviction hit
hits:1000 misses:152 evictions:120Шапка и вывод сходятся, но это сверка симулятора с самим собой, и ценность у неё одна: если завтра кто-то сломает LRU, трасса это заметит. Настоящая сверка это ручной подсчёт, и он у нас есть для yi.trace и dave.trace. Для сгенерированных трасс роль бумаги играет книга: задачи, у которых ответ известен заранее.
Задачи книги как программы
В конце главы про кэш у книги есть серия домашних задач, 6.36 до 6.43, и все они устроены одинаково: дан массив, дан цикл, даны параметры кэша, посчитай долю промахов. Считать их на бумаге полезно один раз. Второй раз полезнее написать программу, которая ходит по массиву ровно так, как написано в условии, и отдать подсчёт симулятору. Расхождение с бумагой в любую сторону это находка: либо ошибка в расчёте, либо в симуляторе.
//! Домашние задания книги про промахи как трассы. Каждая программа
//! построена так же, как в условии: тот же массив, тот же порядок циклов,
//! те же обращения, а параметры кэша заданы рядом. Промахи считает
//! симулятор, а не карандаш, и в тестах шага 37 их можно сверить с тем, что
//! получилось на бумаге.
const std = @import("std");
const cache = @import("cache.zig");
const gen = @import("gen.zig");
/// Массив начинается с адреса, выровненного на размер кэша, как в условиях.
pub const base: u64 = 0x10000;
/// Скалярное произведение двух строк x[2][128] из int: x[0][i] * x[1][i].
/// Строки лежат на расстоянии 512 байт друг от друга.
pub fn dotRows(x: gen.Matrix(i32)) i64 {
var sum: i64 = 0;
var i: usize = 0;
while (i < x.cols) : (i += 1) sum += @as(i64, x.get(0, i)) * x.get(1, i);
return sum;
}
/// Сумма квадратами 2 на 2: четыре соседних элемента за одну итерацию,
/// внешний цикл по столбцам.
pub fn sumSquares(m: gen.Matrix(i32)) i64 {
var sum: i64 = 0;
var j: usize = 0;
while (j < m.cols) : (j += 2) {
var i: usize = 0;
while (i < m.rows) : (i += 2) {
sum += m.get(i, j) + m.get(i + 1, j) + m.get(i, j + 1) + m.get(i + 1, j + 1);
}
}
return sum;
}
/// Точка в цветовой модели CMYK: int плюс три байта, с выравниванием
/// восемь байт, как у той же структуры в C.
pub const PointColor = extern struct { c: i32, m: u8, y: u8, k: u8 };
/// Закрашивание квадрата 16 на 16 по столбцам: внешний цикл по i, но
/// обращение к square[j][i].
pub fn paintByColumns(square: gen.Matrix(PointColor)) void {
var i: usize = 0;
while (i < 16) : (i += 1) {
var j: usize = 0;
while (j < 16) : (j += 1) paintPoint(square, j, i);
}
}
/// То же по строкам: square[i][j].
pub fn paintByRows(square: gen.Matrix(PointColor)) void {
var i: usize = 0;
while (i < 16) : (i += 1) {
var j: usize = 0;
while (j < 16) : (j += 1) paintPoint(square, i, j);
}
}
/// Два прохода по строкам: сначала только жёлтый, потом остальные три поля.
pub fn paintTwoPasses(square: gen.Matrix(PointColor)) void {
var i: usize = 0;
while (i < 16) : (i += 1) {
var j: usize = 0;
while (j < 16) : (j += 1) square.data.setField(square.index(i, j), "y", 1);
}
i = 0;
while (i < 16) : (i += 1) {
var j: usize = 0;
while (j < 16) : (j += 1) {
const idx = square.index(i, j);
square.data.setField(idx, "c", 0);
square.data.setField(idx, "m", 0);
square.data.setField(idx, "k", 0);
}
}
}
fn paintPoint(square: gen.Matrix(PointColor), i: usize, j: usize) void {
const idx = square.index(i, j);
square.data.setField(idx, "c", 0);
square.data.setField(idx, "m", 0);
square.data.setField(idx, "y", 1);
square.data.setField(idx, "k", 0);
}
/// Пиксель экранного буфера 640 на 480: четыре байта.
pub const Pixel = extern struct { r: u8, g: u8, b: u8, a: u8 };
/// Очистка буфера по столбцам, поле за полем.
pub fn clearByFields(buffer: gen.Matrix(Pixel)) void {
var j: usize = 0;
while (j < buffer.cols) : (j += 1) {
var i: usize = 0;
while (i < buffer.rows) : (i += 1) {
const idx = buffer.index(i, j);
buffer.data.setField(idx, "r", 0);
buffer.data.setField(idx, "g", 0);
buffer.data.setField(idx, "b", 0);
buffer.data.setField(idx, "a", 0);
}
}
}
/// Очистка тем же буфером, но как массивом байтов: указатель char.
pub fn clearByBytes(bytes: gen.Traced(u8)) void {
var i: usize = 0;
while (i < bytes.items.len) : (i += 1) bytes.set(i, 0);
}
/// Очистка как массивом int: по четыре байта за раз.
pub fn clearByWords(words: gen.Traced(i32)) void {
var i: usize = 0;
while (i < words.items.len) : (i += 1) words.set(i, 0);
}
pub const Program = enum {
dot_rows,
sum_rows,
sum_cols,
sum_squares,
paint_by_columns,
paint_by_rows,
paint_two_passes,
clear_by_fields,
clear_by_bytes,
clear_by_words,
};
/// Запускает программу на её собственном массиве и проигрывает трассу на
/// кэше `params`. Размер квадратной матрицы для сумм задаёт `n`.
pub fn run(gpa: std.mem.Allocator, program: Program, params: cache.Params, n: usize) !cache.Stats {
var sim = try cache.Cache.init(gpa, params, .write_back);
defer sim.deinit(gpa);
var tracer: gen.Tracer = .init(gpa);
defer tracer.deinit();
tracer.sink = ∼
switch (program) {
.dot_rows => {
const items = try gpa.alloc(i32, 2 * 128);
defer gpa.free(items);
@memset(items, 1);
_ = dotRows(.init(&tracer, base, items, 2, 128));
},
.sum_rows, .sum_cols, .sum_squares => {
const items = try gpa.alloc(i32, n * n);
defer gpa.free(items);
@memset(items, 1);
const m: gen.Matrix(i32) = .init(&tracer, base, items, n, n);
_ = switch (program) {
.sum_rows => gen.sumRows(m),
.sum_cols => gen.sumCols(m),
else => sumSquares(m),
};
},
.paint_by_columns, .paint_by_rows, .paint_two_passes => {
const items = try gpa.alloc(PointColor, 16 * 16);
defer gpa.free(items);
@memset(items, std.mem.zeroes(PointColor));
const square: gen.Matrix(PointColor) = .init(&tracer, base, items, 16, 16);
switch (program) {
.paint_by_columns => paintByColumns(square),
.paint_by_rows => paintByRows(square),
else => paintTwoPasses(square),
}
},
.clear_by_fields => {
const items = try gpa.alloc(Pixel, 480 * 640);
defer gpa.free(items);
clearByFields(.init(&tracer, base, items, 480, 640));
},
.clear_by_bytes => {
const items = try gpa.alloc(u8, 480 * 640 * 4);
defer gpa.free(items);
clearByBytes(.init(&tracer, base, items));
},
.clear_by_words => {
const items = try gpa.alloc(i32, 480 * 640);
defer gpa.free(items);
clearByWords(.init(&tracer, base, items));
},
}
sim.flush();
return sim.stats;
}
/// Параметры кэшей из условий.
pub const dot_direct_512: cache.Params = .{ .s = 5, .e = 1, .b = 4 };
pub const dot_direct_1024: cache.Params = .{ .s = 6, .e = 1, .b = 4 };
pub const dot_two_way_512: cache.Params = .{ .s = 4, .e = 2, .b = 4 };
/// 4 КБ прямого отображения, блок 16 байт: для сумм 64 на 64 и 60 на 60.
pub const sum_params: cache.Params = .{ .s = 8, .e = 1, .b = 4 };
/// 1 КБ прямого отображения, блок 32 байта: для квадрата CMYK.
pub const cmyk_params: cache.Params = .{ .s = 5, .e = 1, .b = 5 };
/// 64 КБ прямого отображения, блок 4 байта: для экранного буфера.
pub const screen_params: cache.Params = .{ .s = 14, .e = 1, .b = 2 };
test "структуры книги занимают столько же, сколько в C" {
try std.testing.expectEqual(@as(usize, 8), @sizeOf(PointColor));
try std.testing.expectEqual(@as(usize, 4), @sizeOf(Pixel));
}Каждая функция повторяет условие буквально. PointColor это extern struct, чтобы поля лежали как в C: int и три char, восемь байт с выравниванием. Пиксель экрана это четыре байта. Массивы начинаются с адреса 0x10000, кратного любому размеру кэша из условий, как и требуют задачи. Параметры кэшей выписаны рядом константами: 512 байт прямого отображения с блоком 16 для скалярного произведения, 4 КБ для сумм, 1 КБ с блоком 32 для квадрата CMYK, 64 КБ с блоком 4 байта для экрана.
Программа, которая гонит их все и печатает таблицу:
//! Прогон домашних программ книги через симулятор: таблица промахов.
const std = @import("std");
const book = @import("book.zig");
const cache = @import("cache.zig");
const Row = struct { name: []const u8, program: book.Program, params: cache.Params, n: usize };
const rows = [_]Row{
.{ .name = "dot_rows 512 direct", .program = .dot_rows, .params = book.dot_direct_512, .n = 0 },
.{ .name = "dot_rows 1024 direct", .program = .dot_rows, .params = book.dot_direct_1024, .n = 0 },
.{ .name = "dot_rows 512 2-way", .program = .dot_rows, .params = book.dot_two_way_512, .n = 0 },
.{ .name = "sum_rows 64", .program = .sum_rows, .params = book.sum_params, .n = 64 },
.{ .name = "sum_cols 64", .program = .sum_cols, .params = book.sum_params, .n = 64 },
.{ .name = "sum_squares 64", .program = .sum_squares, .params = book.sum_params, .n = 64 },
.{ .name = "sum_rows 60", .program = .sum_rows, .params = book.sum_params, .n = 60 },
.{ .name = "sum_cols 60", .program = .sum_cols, .params = book.sum_params, .n = 60 },
.{ .name = "sum_squares 60", .program = .sum_squares, .params = book.sum_params, .n = 60 },
.{ .name = "paint_by_columns", .program = .paint_by_columns, .params = book.cmyk_params, .n = 0 },
.{ .name = "paint_by_rows", .program = .paint_by_rows, .params = book.cmyk_params, .n = 0 },
.{ .name = "paint_two_passes", .program = .paint_two_passes, .params = book.cmyk_params, .n = 0 },
.{ .name = "clear_by_fields", .program = .clear_by_fields, .params = book.screen_params, .n = 0 },
.{ .name = "clear_by_bytes", .program = .clear_by_bytes, .params = book.screen_params, .n = 0 },
.{ .name = "clear_by_words", .program = .clear_by_words, .params = book.screen_params, .n = 0 },
};
pub fn main(init: std.process.Init) !void {
var debug_allocator: std.heap.DebugAllocator(.{}) = .init;
defer _ = debug_allocator.deinit();
const gpa = debug_allocator.allocator();
var buf: [4096]u8 = undefined;
var stdout = std.Io.File.stdout().writer(init.io, &buf);
const out = &stdout.interface;
try out.print("{s:<22} {s:>9} {s:>8} {s:>10} {s:>7}\n", .{ "program", "accesses", "misses", "evictions", "rate" });
for (rows) |row| {
const st = try book.run(gpa, row.program, row.params, row.n);
try out.print("{s:<22} {d:>9} {d:>8} {d:>10} {d:>6.2}%\n", .{ row.name, st.accesses(), st.misses, st.evictions, st.missRate() * 100 });
}
try out.flush();
}Вывод, приведённый к таблице (все числа сняты этим прогоном, машина роли не играет: трасса виртуальная):
| программа | кэш | обращений | промахов | вытеснений | доля |
|---|---|---|---|---|---|
dot_rows | 512 Б, прямой, блок 16 | 256 | 256 | 224 | 100 % |
dot_rows | 1024 Б, прямой, блок 16 | 256 | 64 | 0 | 25 % |
dot_rows | 512 Б, 2-way, блок 16 | 256 | 64 | 32 | 25 % |
sum_rows, 64 на 64 | 4 КБ, прямой, блок 16 | 4096 | 1024 | 768 | 25 % |
sum_cols, 64 на 64 | 4 КБ, прямой, блок 16 | 4096 | 4096 | 3840 | 100 % |
sum_squares, 64 на 64 | 4 КБ, прямой, блок 16 | 4096 | 2048 | 1792 | 50 % |
sum_rows, 60 на 60 | 4 КБ, прямой, блок 16 | 3600 | 900 | 644 | 25 % |
sum_cols, 60 на 60 | 4 КБ, прямой, блок 16 | 3600 | 900 | 644 | 25 % |
sum_squares, 60 на 60 | 4 КБ, прямой, блок 16 | 3600 | 900 | 644 | 25 % |
paint_by_columns | 1 КБ, прямой, блок 32 | 1024 | 256 | 224 | 25 % |
paint_by_rows | 1 КБ, прямой, блок 32 | 1024 | 64 | 32 | 6.25 % |
paint_two_passes | 1 КБ, прямой, блок 32 | 1024 | 128 | 96 | 12.5 % |
clear_by_fields | 64 КБ, прямой, блок 4 | 1 228 800 | 307 200 | 290 816 | 25 % |
clear_by_bytes | 64 КБ, прямой, блок 4 | 1 228 800 | 307 200 | 290 816 | 25 % |
clear_by_words | 64 КБ, прямой, блок 4 | 307 200 | 307 200 | 290 816 | 100 % |
Теперь разберём, почему числа такие. Каждая строка это одна задача книги, переформулированная своими словами.
Скалярное произведение двух строк (6.36). Массив x[2][128] из int: строка занимает 512 байт, и вторая строка начинается ровно через 512 байт после первой. На кэше в 512 байт прямого отображения x[0][i] и x[1][i] попадают в один набор с разными тегами, и каждое обращение вытесняет предыдущее: 100 процентов промахов, из них 224 с вытеснением и 32 холодных, по числу наборов. Удвоенный кэш разводит строки по разным наборам: промах на первом слове каждого блока из четырёх int, дальше три попадания, 25 процентов. Двухпутевой кэш того же размера даёт те же 25 процентов, потому что обе строки теперь живут в наборе вместе. И последнее, что спрашивает задача: помог бы в первом случае более широкий блок? Нет. Конфликт создают не размеры блоков, а расстояние в 512 байт, кратное размеру кэша; сколько ни расширяй блок, x[0][i] и x[1][i] останутся в одном наборе.
Три суммы (6.37). Функции sum_rows, sum_cols и sum_squares обходят один и тот же массив int тремя порядками. При 64 на 64 строка занимает 256 байт, шестнадцать строк заполняют кэш целиком, и семнадцатая ложится поверх первой. Обход по строкам это классические 25 процентов: блок 16 байт, четыре int, промах на первом. Обход по столбцам промахивается всегда: шаг 256 байт, каждое обращение в новый блок, а через шестнадцать шагов набор уже занят другой строкой. Обход квадратами 2 на 2 читает два соседних элемента из двух соседних строк: два промаха на четыре обращения, 50 процентов. Дальше самое интересное: при 60 на 60 все три дают 25 процентов. Строка теперь 240 байт, и это не кратно 256, поэтому соседние строки ложатся в разные наборы, обход по столбцам перестаёт конфликтовать, и промахи остаются только холодные. Одна и та же программа, один и тот же кэш, а разницу между 100 и 25 процентами дают четыре лишних элемента в размере массива.
Квадрат CMYK (6.38 до 6.40). Точка это восемь байт, в блоке из 32 байт четыре точки, весь квадрат 2 КБ при кэше в 1 КБ. Закрашивание по столбцам (square[j][i] при внешнем цикле по i) пишет четыре поля точки, потом прыгает на 128 байт вниз: первое поле промах, три остальных попадание, а к тому времени, как цикл вернётся к соседней точке в том же блоке, блок уже вытеснен точкой с тем же индексом восемью строками ниже. 256 промахов на 1024 записи, 25 процентов. По строкам блок из четырёх точек грузится один раз и обслуживает шестнадцать записей: 64 промаха, 6.25 процента. Два прохода по строкам, сначала одно поле, потом три, грузят каждый блок дважды: 128 промахов, 12.5 процента. Заметь, что число записей во всех трёх одинаково; меняется только порядок.
Буфер экрана (6.41 до 6.43). Пиксель это четыре байта, блок тоже четыре байта, значит, пространственной локальности внутри блока нет вовсе: блок это один пиксель. Очистка по полям пишет четыре байта одного пикселя четырьмя записями: промах и три попадания, 25 процентов. Очистка как массива char делает то же самое, только без структуры: та же доля. Очистка как массива int пишет каждый пиксель одной записью, и каждая запись промах: 100 процентов. Но посмотри на столбец промахов: во всех трёх строках их 307 200, по числу пикселей. Доля промахов у третьей версии вчетверо хуже при том же числе походов в память, и по времени она не медленнее, а быстрее: записей вчетверо меньше. Доля промахов это не время. Это первый звонок к тому, что будет в следующем уроке.
Всё это проверяет тест шага tests/step_39.zig: пятнадцать строк таблицы выписаны в нём как ожидания, и симулятор обязан их выдать. Там же сверка каждой трассы из traces/ с её шапкой (тест открывает каталог, читает первую строку и сравнивает три счётчика), проверка того, что M даёт два исхода и второй всегда попадание, что выборки I кэш данных не видит, и что dot_rows.trace с matmul_ijk.trace воспроизводятся из программы байт в байт. Запуск: zig build test -Dstep=39 из корня проекта, потому что тесты открывают traces/ относительно рабочего каталога.
Шаг проекта: кэш перед памятью Y86
В уроке про симулятор Y86 память отвечала на любое обращение мгновенно, и такт был равен инструкции. В уроке про PIPE CPI получил штрафы за риски конвейера, но память по-прежнему была бесплатной. Сегодня это заканчивается: машина пишет трассу обращений в формате lackey, между процессором и памятью встаёт кэш, и каждый промах стоит тактов.
Шаг состоит из трёх новых файлов в src/sim/ и правок в main.zig. Ядро cpu.zig не меняется вовсе: перехватчик встаёт снаружи шести этапов.
memtrace.zig: трасса в формате lackey
//! Трасса обращений к памяти в формате valgrind lackey, том самом, который
//! читает симулятор кэша из cachelab.
//!
//! I 000,10 выборка инструкции: адрес и длина в байтах
//! L 018,8 чтение слова данных
//! S 1f8,8 запись слова данных
//!
//! Адрес шестнадцатеричный без префикса, как у lackey. У строк данных
//! ведущий пробел, у выборки инструкции его нет: так cachelab отличает
//! обращения за инструкциями от обращений за данными. Симулятор кэша смотрит
//! только на вид обращения и адрес, длину он не читает: в cachelab принято,
//! что обращение не пересекает границу блока.
//!
//! Записывать трассу можно двумя способами, и оба включаются полем:
//! `writer` пишет строки по мере исполнения, `gpa` копит обращения списком.
//! Счётчики ведутся всегда.
const std = @import("std");
const Allocator = std.mem.Allocator;
const Writer = std.Io.Writer;
pub const Kind = enum {
instr,
load,
store,
/// Буква обращения в трассе.
pub fn letter(self: Kind) u8 {
return switch (self) {
.instr => 'I',
.load => 'L',
.store => 'S',
};
}
};
pub const Access = struct {
kind: Kind,
addr: u64,
len: u8,
};
pub const Counts = struct {
instr: usize = 0,
load: usize = 0,
store: usize = 0,
pub fn data(self: Counts) usize {
return self.load + self.store;
}
pub fn total(self: Counts) usize {
return self.instr + self.data();
}
};
pub const Error = Writer.Error || Allocator.Error;
pub const Recorder = struct {
counts: Counts = .{},
/// Куда писать строки трассы. null означает, что трасса не пишется.
writer: ?*Writer = null,
/// Аллокатор списка обращений. null означает, что список не копится.
gpa: ?Allocator = null,
accesses: std.ArrayList(Access) = .empty,
pub fn deinit(self: *Recorder) void {
if (self.gpa) |gpa| self.accesses.deinit(gpa);
self.* = undefined;
}
pub fn record(self: *Recorder, access: Access) Error!void {
switch (access.kind) {
.instr => self.counts.instr += 1,
.load => self.counts.load += 1,
.store => self.counts.store += 1,
}
if (self.writer) |w| try write(w, access);
if (self.gpa) |gpa| try self.accesses.append(gpa, access);
}
};
/// Одна строка трассы.
pub fn write(w: *Writer, access: Access) Writer.Error!void {
const lead: []const u8 = if (access.kind == .instr) "" else " ";
try w.print("{s}{c} {x:0>3},{d}\n", .{ lead, access.kind.letter(), access.addr, access.len });
}
/// Разбор одной строки трассы. Ведущие пробелы и перевод строки разрешены,
/// всё остальное нет: строку, которую нельзя разобрать, лучше заметить.
pub fn parse(line: []const u8) ?Access {
const text = std.mem.trim(u8, line, " \r\n");
if (text.len < 3 or text[1] != ' ') return null;
const kind: Kind = switch (text[0]) {
'I' => .instr,
'L' => .load,
'S' => .store,
else => return null,
};
const comma = std.mem.indexOfScalar(u8, text, ',') orelse return null;
const addr = std.fmt.parseInt(u64, text[2..comma], 16) catch return null;
const len = std.fmt.parseInt(u8, text[comma + 1 ..], 10) catch return null;
return .{ .kind = kind, .addr = addr, .len = len };
}
const testing = std.testing;
test "строки трассы печатаются как у lackey" {
var out: Writer.Allocating = .init(testing.allocator);
defer out.deinit();
try write(&out.writer, .{ .kind = .instr, .addr = 0x00a, .len = 9 });
try write(&out.writer, .{ .kind = .load, .addr = 0x18, .len = 8 });
try write(&out.writer, .{ .kind = .store, .addr = 0x1f8, .len = 8 });
try testing.expectEqualStrings("I 00a,9\n L 018,8\n S 1f8,8\n", out.written());
}
test "разбор возвращает то, что было напечатано" {
const access: Access = .{ .kind = .store, .addr = 0x1f0, .len = 8 };
var out: Writer.Allocating = .init(testing.allocator);
defer out.deinit();
try write(&out.writer, access);
try testing.expectEqual(access, parse(out.written()).?);
try testing.expectEqual(@as(?Access, null), parse("M 000,8"));
try testing.expectEqual(@as(?Access, null), parse("I 000"));
try testing.expectEqual(@as(?Access, null), parse(""));
}
test "записывающий считает и копит" {
var out: Writer.Allocating = .init(testing.allocator);
defer out.deinit();
var rec: Recorder = .{ .writer = &out.writer, .gpa = testing.allocator };
defer rec.deinit();
try rec.record(.{ .kind = .instr, .addr = 0, .len = 10 });
try rec.record(.{ .kind = .load, .addr = 0x18, .len = 8 });
try rec.record(.{ .kind = .load, .addr = 0x20, .len = 8 });
try rec.record(.{ .kind = .store, .addr = 0x1f8, .len = 8 });
try testing.expectEqual(@as(usize, 1), rec.counts.instr);
try testing.expectEqual(@as(usize, 2), rec.counts.load);
try testing.expectEqual(@as(usize, 1), rec.counts.store);
try testing.expectEqual(@as(usize, 4), rec.counts.total());
try testing.expectEqual(@as(usize, 4), rec.accesses.items.len);
try testing.expectEqual(@as(usize, 4), std.mem.count(u8, out.written(), "\n"));
}Строки печатаются так же, как у lackey, с одним отличием: адрес добит нулями до трёх цифр, потому что память машины умещается в 4 КБ и так трасса читается глазами. Симулятору кэша ведущие нули безразличны. Вида M в этой трассе нет: у Y86-64 нет инструкции, которая читает и пишет одно слово, pushq и popq ходят по разным адресам.
Recorder ведёт счётчики всегда, а трассу пишет только если ему дали writer, и копит список только если дали gpa. Так машина в тестах не тратит память на трассу, которая никому не нужна.
cache.zig: тот же алгоритм, что в csim
//! Кэш (s, E, b) с вытеснением по давности: тот же алгоритм, что в cachelab.
//!
//! Адрес режется на три поля. Младшие b бит это смещение внутри блока,
//! следующие s бит выбирают набор, всё, что старше, это тег:
//!
//! | тег | индекс набора (s бит) | смещение (b бит) |
//!
//! В наборе E строк, у каждой бит valid, тег и отметка времени последнего
//! обращения. Обращение попадает, если в наборе есть валидная строка с тем же
//! тегом. Иначе промах: строка кладётся в пустое место, а если пустого нет,
//! вытесняется та, к которой дольше всех не обращались.
//!
//! Размер обращения кэш не смотрит, как и cachelab: считается, что обращение
//! не пересекает границу блока. Запись ведёт себя как чтение: блок при промахе
//! подтягивается (write-allocate), а что уходит в память и когда, здесь не
//! моделируется.
const std = @import("std");
const memtrace = @import("memtrace.zig");
const Allocator = std.mem.Allocator;
pub const Params = struct {
/// Бит индекса: наборов 2^s.
s: u6,
/// Строк в наборе.
e: u32,
/// Бит смещения: блок 2^b байт.
b: u6,
pub fn sets(self: Params) usize {
return @as(usize, 1) << self.s;
}
pub fn blockBytes(self: Params) usize {
return @as(usize, 1) << self.b;
}
/// Сколько байт данных помещается в кэш.
pub fn capacity(self: Params) usize {
return self.sets() * self.e * self.blockBytes();
}
pub fn tagOf(self: Params, addr: u64) u64 {
const shift: u6 = @intCast(@as(u32, self.s) + self.b);
return addr >> shift;
}
pub fn setOf(self: Params, addr: u64) usize {
return @intCast((addr >> self.b) & (self.sets() - 1));
}
pub fn offsetOf(self: Params, addr: u64) u64 {
return addr & (self.blockBytes() - 1);
}
/// Разбор записи вида `s=4,E=1,b=4`. Порядок полей любой, все три обязательны.
pub fn parse(text: []const u8) ?Params {
var s: ?u6 = null;
var e: ?u32 = null;
var b: ?u6 = null;
var fields = std.mem.splitScalar(u8, text, ',');
while (fields.next()) |field| {
const eq = std.mem.indexOfScalar(u8, field, '=') orelse return null;
const name = field[0..eq];
const digits = field[eq + 1 ..];
if (std.mem.eql(u8, name, "s")) {
s = std.fmt.parseInt(u6, digits, 10) catch return null;
} else if (std.mem.eql(u8, name, "E")) {
e = std.fmt.parseInt(u32, digits, 10) catch return null;
} else if (std.mem.eql(u8, name, "b")) {
b = std.fmt.parseInt(u6, digits, 10) catch return null;
} else return null;
}
const params: Params = .{ .s = s orelse return null, .e = e orelse return null, .b = b orelse return null };
if (params.e == 0 or @as(u32, params.s) + params.b >= 64) return null;
return params;
}
pub fn format(self: Params, w: *std.Io.Writer) std.Io.Writer.Error!void {
try w.print("s={d},E={d},b={d}", .{ self.s, self.e, self.b });
}
};
/// Чем кончилось обращение. `evict` это тоже промах, но с вытеснением.
pub const Outcome = enum { hit, miss, evict };
pub const Stats = struct {
hits: usize = 0,
misses: usize = 0,
evictions: usize = 0,
pub fn count(self: *Stats, outcome: Outcome) void {
switch (outcome) {
.hit => self.hits += 1,
.miss => self.misses += 1,
.evict => {
self.misses += 1;
self.evictions += 1;
},
}
}
pub fn add(self: *Stats, other: Stats) void {
self.hits += other.hits;
self.misses += other.misses;
self.evictions += other.evictions;
}
pub fn accesses(self: Stats) usize {
return self.hits + self.misses;
}
};
pub const Line = struct {
valid: bool = false,
tag: u64 = 0,
/// Показание часов кэша при последнем обращении: чем меньше, тем давнее.
last_used: u64 = 0,
};
pub const Cache = struct {
params: Params,
/// Все строки подряд: набор i занимает срез [i * E, (i + 1) * E).
lines: []Line,
stats: Stats = .{},
/// Часы кэша: тикают на каждом обращении, по ним ищется самая давняя строка.
clock: u64 = 0,
gpa: Allocator,
pub fn init(gpa: Allocator, params: Params) Allocator.Error!Cache {
const lines = try gpa.alloc(Line, params.sets() * params.e);
@memset(lines, .{});
return .{ .params = params, .lines = lines, .gpa = gpa };
}
pub fn deinit(self: *Cache) void {
self.gpa.free(self.lines);
self.* = undefined;
}
fn set(self: *Cache, index: usize) []Line {
const e = self.params.e;
return self.lines[index * e .. (index + 1) * e];
}
pub fn access(self: *Cache, addr: u64) Outcome {
self.clock += 1;
const tag = self.params.tagOf(addr);
const lines = self.set(self.params.setOf(addr));
// Сначала ищем попадание и по дороге запоминаем пустую строку
// и самую давнюю на случай промаха.
var empty: ?*Line = null;
var oldest: *Line = &lines[0];
for (lines) |*line| {
if (line.valid and line.tag == tag) {
line.last_used = self.clock;
self.stats.count(.hit);
return .hit;
}
if (!line.valid and empty == null) empty = line;
if (line.last_used < oldest.last_used) oldest = line;
}
const outcome: Outcome = if (empty != null) .miss else .evict;
const target = empty orelse oldest;
target.* = .{ .valid = true, .tag = tag, .last_used = self.clock };
self.stats.count(outcome);
return outcome;
}
};
/// Общий кэш на всё или два раздельных: для инструкций и для данных.
pub const Organization = enum { unified, split };
pub const Hierarchy = struct {
/// Общий кэш, а при раздельной организации кэш инструкций.
instr: Cache,
data: ?Cache,
pub fn init(gpa: Allocator, params: Params, org: Organization) Allocator.Error!Hierarchy {
var instr = try Cache.init(gpa, params);
errdefer instr.deinit();
const data: ?Cache = switch (org) {
.unified => null,
.split => try Cache.init(gpa, params),
};
return .{ .instr = instr, .data = data };
}
pub fn deinit(self: *Hierarchy) void {
self.instr.deinit();
if (self.data) |*data| data.deinit();
self.* = undefined;
}
pub fn organization(self: *const Hierarchy) Organization {
return if (self.data == null) .unified else .split;
}
pub fn access(self: *Hierarchy, addr: u64, kind: memtrace.Kind) Outcome {
if (kind == .instr) return self.instr.access(addr);
if (self.data) |*data| return data.access(addr);
return self.instr.access(addr);
}
/// Счётчики обоих кэшей вместе.
pub fn stats(self: *const Hierarchy) Stats {
var total = self.instr.stats;
if (self.data) |data| total.add(data.stats);
return total;
}
};
const testing = std.testing;
test "адрес режется на тег, индекс и смещение" {
const p: Params = .{ .s = 4, .e = 1, .b = 4 };
try testing.expectEqual(@as(usize, 16), p.sets());
try testing.expectEqual(@as(usize, 16), p.blockBytes());
try testing.expectEqual(@as(usize, 256), p.capacity());
// 0x1f8 = 0b1_1111_1000: смещение 8, набор 15, тег 1.
try testing.expectEqual(@as(u64, 8), p.offsetOf(0x1f8));
try testing.expectEqual(@as(usize, 15), p.setOf(0x1f8));
try testing.expectEqual(@as(u64, 1), p.tagOf(0x1f8));
}
test "разбор параметров" {
try testing.expectEqual(Params{ .s = 4, .e = 1, .b = 4 }, Params.parse("s=4,E=1,b=4").?);
try testing.expectEqual(Params{ .s = 0, .e = 2, .b = 5 }, Params.parse("b=5,E=2,s=0").?);
try testing.expectEqual(@as(?Params, null), Params.parse("s=4,b=4"));
try testing.expectEqual(@as(?Params, null), Params.parse("s=4,E=0,b=4"));
try testing.expectEqual(@as(?Params, null), Params.parse("s=x,E=1,b=4"));
}
test "прямое отображение: два адреса в одном наборе выталкивают друг друга" {
var c: Cache = try .init(testing.allocator, .{ .s = 1, .e = 1, .b = 4 });
defer c.deinit();
try testing.expectEqual(Outcome.miss, c.access(0x00));
try testing.expectEqual(Outcome.hit, c.access(0x0f));
// 0x20 попадает в тот же набор 0, но с другим тегом.
try testing.expectEqual(Outcome.evict, c.access(0x20));
try testing.expectEqual(Outcome.evict, c.access(0x00));
// Другой набор конфликта не создаёт.
try testing.expectEqual(Outcome.miss, c.access(0x10));
try testing.expectEqual(@as(usize, 1), c.stats.hits);
try testing.expectEqual(@as(usize, 4), c.stats.misses);
try testing.expectEqual(@as(usize, 2), c.stats.evictions);
}
test "вытесняется самая давняя строка, а не самая старая по загрузке" {
var c: Cache = try .init(testing.allocator, .{ .s = 0, .e = 2, .b = 4 });
defer c.deinit();
try testing.expectEqual(Outcome.miss, c.access(0x00));
try testing.expectEqual(Outcome.miss, c.access(0x10));
// Обращение к 0x00 делает давней строку 0x10.
try testing.expectEqual(Outcome.hit, c.access(0x00));
try testing.expectEqual(Outcome.evict, c.access(0x20));
try testing.expectEqual(Outcome.hit, c.access(0x00));
try testing.expectEqual(Outcome.evict, c.access(0x10));
}
test "раздельные кэши не мешают друг другу" {
var h: Hierarchy = try .init(testing.allocator, .{ .s = 0, .e = 1, .b = 4 }, .split);
defer h.deinit();
try testing.expectEqual(Outcome.miss, h.access(0x000, .instr));
try testing.expectEqual(Outcome.miss, h.access(0x100, .load));
// Единственная строка кэша инструкций осталась при своих.
try testing.expectEqual(Outcome.hit, h.access(0x008, .instr));
try testing.expectEqual(Outcome.hit, h.access(0x108, .store));
try testing.expectEqual(@as(usize, 2), h.stats().hits);
try testing.expectEqual(@as(usize, 2), h.stats().misses);
var u: Hierarchy = try .init(testing.allocator, .{ .s = 0, .e = 1, .b = 4 }, .unified);
defer u.deinit();
try testing.expectEqual(Outcome.miss, u.access(0x000, .instr));
try testing.expectEqual(Outcome.evict, u.access(0x100, .load));
try testing.expectEqual(Outcome.evict, u.access(0x008, .instr));
}Это ядро csim без политик записи: запись ведёт себя как чтение, блок при промахе подтягивается, а что и когда уходит в память, здесь не моделируется. Зато есть то, чего в csim нет: Hierarchy, общий кэш или два раздельных, для инструкций и для данных. Настоящие L1 почти всегда раздельные, и через минуту станет видно, почему это не бесплатно.
Функция Params.parse разбирает запись вида s=4,E=1,b=4 с командной строки, а format печатает её обратно, чтобы сводка называла кэш теми же словами, что и пользователь.
machine.zig: перехватчик между этапами
//! Процессор, кэш и память вместе.
//!
//! `cpu.step` исполняет инструкцию за шесть этапов, но не знает, чего стоит
//! каждое обращение к памяти. Здесь те же шесть этапов, только между выборкой
//! и декодированием, а потом между этапом памяти и записью обратно, стоит
//! перехватчик: он записывает обращение в трассу и прогоняет его через кэш.
//!
//! Модель времени у симулятора уровня инструкций одна: такт равен инструкции.
//! Кэш добавляет к этому штраф за каждый промах:
//!
//! такты = инструкции + промахи × штраф
//!
//! Программа, регистры и память от кэша не зависят: трасса версии 1 остаётся
//! той же байт в байт, меняется только строка тактов и счётчики.
const std = @import("std");
const cache = @import("cache.zig");
const cpu = @import("cpu.zig");
const isa = @import("../isa.zig");
const memtrace = @import("memtrace.zig");
const state = @import("state.zig");
const Allocator = std.mem.Allocator;
const State = state.State;
const Writer = std.Io.Writer;
pub const Config = struct {
/// Параметры кэша. null означает, что кэша нет: память отвечает за такт.
cache: ?cache.Params = null,
organization: cache.Organization = .unified,
/// Сколько тактов стоит один промах.
miss_penalty: u32 = 0,
/// Предохранитель от программы, которая не доходит до останова.
max_steps: usize = 100_000,
};
pub const Report = struct {
instructions: usize,
stat: isa.Stat,
/// true, если такты кончились раньше, чем машина остановилась.
hit_limit: bool,
accesses: memtrace.Counts,
/// Счётчики кэша. null, если кэша не было.
cache: ?cache.Stats,
miss_penalty: u32,
/// Такты со штрафом за промахи. Без кэша это число инструкций.
pub fn cycles(self: Report) usize {
const misses = if (self.cache) |c| c.misses else 0;
return self.instructions + misses * self.miss_penalty;
}
pub fn cpi(self: Report) f64 {
if (self.instructions == 0) return 0;
return @as(f64, @floatFromInt(self.cycles())) / @as(f64, @floatFromInt(self.instructions));
}
/// Сводка для человека: сколько чего было и во что обошлось.
pub fn print(self: Report, w: *Writer, config: Config) Writer.Error!void {
try w.print("инструкций {d}, обращений к памяти: выборок {d}, чтений {d}, записей {d}\n", .{
self.instructions,
self.accesses.instr,
self.accesses.load,
self.accesses.store,
});
const stats = self.cache orelse {
try w.print("кэша нет: тактов {d}, CPI {d:.2}\n", .{ self.instructions, 1.0 });
return;
};
const kind: []const u8 = switch (config.organization) {
.unified => "общий",
.split => "раздельный для инструкций и данных",
};
try w.print("кэш {f} ({s}): попаданий {d}, промахов {d}, вытеснений {d}\n", .{
config.cache.?,
kind,
stats.hits,
stats.misses,
stats.evictions,
});
try w.print("тактов без кэша {d} (CPI {d:.2}), со штрафом {d} за промах {d} (CPI {d:.2})\n", .{
self.instructions,
1.0,
self.miss_penalty,
self.cycles(),
self.cpi(),
});
}
};
pub const Machine = struct {
st: State,
config: Config,
/// Трасса обращений: счётчики всегда, запись и список по желанию
/// вызывающего, который выставляет `recorder.writer` и `recorder.gpa`.
recorder: memtrace.Recorder = .{},
caches: ?cache.Hierarchy,
instructions: usize = 0,
pub fn init(gpa: Allocator, config: Config) Allocator.Error!Machine {
const caches: ?cache.Hierarchy = if (config.cache) |params|
try cache.Hierarchy.init(gpa, params, config.organization)
else
null;
return .{ .st = .init(), .config = config, .caches = caches };
}
pub fn deinit(self: *Machine) void {
if (self.caches) |*caches| caches.deinit();
self.recorder.deinit();
self.* = undefined;
}
/// Обращение к памяти проходит через трассу и через кэш.
fn touch(self: *Machine, kind: memtrace.Kind, addr: u64, len: u8) memtrace.Error!void {
try self.recorder.record(.{ .kind = kind, .addr = addr, .len = len });
if (self.caches) |*caches| _ = caches.access(addr, kind);
}
/// Один такт: те же шесть этапов, что в `cpu.step`, с перехватчиком
/// после выборки и после этапа памяти.
pub fn step(self: *Machine) memtrace.Error!cpu.Retired {
const st = &self.st;
const pc = st.pc;
var s: cpu.Signals = .{};
cpu.fetch(st, &s);
// Выборка состоялась, только если байтов хватило: тогда известна
// и длина инструкции. Иначе это ADR, и в трассу писать нечего.
if (s.val_p > pc) try self.touch(.instr, pc, @intCast(s.val_p - pc));
cpu.decode(st, &s);
cpu.execute(st, &s);
cpu.memory(st, &s);
if (s.mem_read) try self.touch(.load, s.mem_addr, 8);
if (s.mem_write) try self.touch(.store, s.mem_addr, 8);
cpu.writeback(st, &s);
cpu.pcUpdate(st, &s);
st.stat = s.stat;
self.instructions += 1;
return .{ .pc = pc, .icode = s.icode, .ifun = s.ifun, .stat = s.stat };
}
/// Загружает образ и крутит такты до останова или до предохранителя.
pub fn run(self: *Machine, image: []const u8) memtrace.Error!Report {
self.st = .init();
self.st.load(image);
while (self.st.stat == .aok and self.instructions < self.config.max_steps) {
_ = try self.step();
}
return self.report();
}
pub fn report(self: *const Machine) Report {
return .{
.instructions = self.instructions,
.stat = self.st.stat,
.hit_limit = self.st.stat == .aok,
.accesses = self.recorder.counts,
.cache = if (self.caches) |caches| caches.stats() else null,
.miss_penalty = self.config.miss_penalty,
};
}
};
/// Трасса обращений программы текстом: удобно тестам и виджетам.
pub fn memtraceOf(gpa: Allocator, image: []const u8, config: Config) Allocator.Error![]u8 {
var out: Writer.Allocating = .init(gpa);
errdefer out.deinit();
var m: Machine = try .init(gpa, config);
defer m.deinit();
m.recorder.writer = &out.writer;
_ = m.run(image) catch return error.OutOfMemory;
return out.toOwnedSlice();
}
const testing = std.testing;
// irmovq $2, %rax; irmovq $0x100, %rbx; rmmovq %rax, (%rbx); mrmovq (%rbx), %rcx; halt
const store_load = [_]u8{
0x30, 0xf0, 0x02, 0x00, 0, 0, 0, 0, 0, 0,
0x30, 0xf3, 0x00, 0x01, 0, 0, 0, 0, 0, 0,
0x40, 0x03, 0x00, 0x00, 0, 0, 0, 0, 0, 0,
0x50, 0x13, 0x00, 0x00, 0, 0, 0, 0, 0, 0,
0x00,
};
test "трасса обращений: выборки, запись и чтение" {
const text = try memtraceOf(testing.allocator, &store_load, .{});
defer testing.allocator.free(text);
try testing.expectEqualStrings(
\\I 000,10
\\I 00a,10
\\I 014,10
\\ S 100,8
\\I 01e,10
\\ L 100,8
\\I 028,1
\\
, text);
}
test "без кэша такт равен инструкции, с кэшем промахи дорожают" {
var plain: Machine = try .init(testing.allocator, .{});
defer plain.deinit();
const r0 = try plain.run(&store_load);
try testing.expectEqual(@as(usize, 5), r0.instructions);
try testing.expectEqual(@as(usize, 5), r0.cycles());
try testing.expectEqual(@as(?cache.Stats, null), r0.cache);
try testing.expectEqual(isa.Stat.hlt, r0.stat);
// Прямое отображение, блок 16 байт. Три попадания: вторая инструкция
// лежит в блоке первой, четвёртая в блоке третьей, а слово 0x100 после
// записи читается из кэша. Запись при этом выталкивает блок 0x000 из
// набора 0, это единственное вытеснение.
var cached: Machine = try .init(testing.allocator, .{
.cache = .{ .s = 4, .e = 1, .b = 4 },
.miss_penalty = 10,
});
defer cached.deinit();
const r1 = try cached.run(&store_load);
try testing.expectEqual(@as(usize, 5), r1.instructions);
try testing.expectEqual(@as(usize, 3), r1.cache.?.hits);
try testing.expectEqual(@as(usize, 4), r1.cache.?.misses);
try testing.expectEqual(@as(usize, 1), r1.cache.?.evictions);
try testing.expectEqual(@as(usize, 45), r1.cycles());
try testing.expectEqual(@as(u64, 2), cached.st.get(.rcx));
}Главное здесь функция step. Это те же шесть этапов, что в cpu.step, вызванные по очереди, но между выборкой и декодированием, а потом между этапом памяти и записью, стоит touch: обращение записывается в трассу и прогоняется через кэш. Выборка попадает в трассу только если удалась: если байтов не хватило, это исключение ADR, и длины инструкции не существует. Длина обращения к данным всегда восемь: в Y86-64 память читается и пишется только словами.
Модель времени одна строка:
такты = инструкции + промахи × штрафТакт равен инструкции, как и было, а каждый промах добавляет miss_penalty тактов. Это грубая модель: настоящий процессор перекрывает промахи другой работой, а промах записи часто стоит меньше промаха чтения. Но она уже показывает главное: одна и та же программа с одним и тем же числом инструкций стоит разное число тактов, смотря помещается ли она в кэш. Тест в конце файла делает это на пяти инструкциях: 5 тактов без кэша и 45 с кэшем на 16 наборов и штрафом 10.
Изменённые места
В root.zig три новых экспорта, чтобы тесты и main.zig видели модули по имени:
pub const memtrace = @import("sim/memtrace.zig");
pub const cache = @import("sim/cache.zig");
pub const machine = @import("sim/machine.zig");В build.zig в список шагов добавляется "39", а тесту шага подключается образец трассы как анонимный модуль: это данные теста, а не часть машины, поэтому файл лежит в tests/expected/, а не в src/:
const steps = [_][]const u8{ "20", "21", "22", "23", "24", "25", "26", "27", "29", "30", "39" };
// внутри цикла по шагам, после addTest:
tests.root_module.addAnonymousImport("sum.memtrace", .{
.root_source_file = b.path("tests/expected/sum.memtrace"),
});В main.zig подкоманда sim получает четыре ключа: --cache s=4,E=1,b=4, --split, --miss-penalty N и --memtrace file. Разбор ключей, загрузка образа из любого из трёх форматов и второй прогон через машину с кэшем выглядят так:
/// Ключи `sim`. Путь к программе идёт без ключа, остальное парами.
const SimOptions = struct {
path: ?[]const u8 = null,
config: MachineConfig = .{},
memtrace_path: ?[]const u8 = null,
/// Нужна ли машина с перехватчиком, или хватит обычной трассы.
fn wantsReport(self: SimOptions) bool {
return self.config.cache != null or self.memtrace_path != null;
}
};
fn parseSimOptions(cli: Cli, args: []const []const u8) !SimOptions {
var opts: SimOptions = .{};
var i: usize = 2;
while (i < args.len) : (i += 1) {
const arg = args[i];
if (!std.mem.startsWith(u8, arg, "--")) {
opts.path = arg;
continue;
}
if (std.mem.eql(u8, arg, "--split")) {
opts.config.organization = .split;
continue;
}
i += 1;
if (i == args.len) {
try cli.err.print("у ключа {s} нет значения\n", .{arg});
return error.BadUsage;
}
const value = args[i];
if (std.mem.eql(u8, arg, "--cache")) {
opts.config.cache = cache.Params.parse(value) orelse {
try cli.err.print("не разобрать кэш {s}, нужно s=4,E=1,b=4\n", .{value});
return error.BadUsage;
};
} else if (std.mem.eql(u8, arg, "--miss-penalty")) {
opts.config.miss_penalty = std.fmt.parseInt(u32, value, 10) catch {
try cli.err.print("штраф за промах это число тактов, а не {s}\n", .{value});
return error.BadUsage;
};
} else if (std.mem.eql(u8, arg, "--memtrace")) {
opts.memtrace_path = value;
} else {
try cli.err.print("неизвестный ключ: {s}\n", .{arg});
return error.BadUsage;
}
}
if (opts.path == null) {
try usage(cli.err);
return error.BadUsage;
}
return opts;
}
fn simulateCommand(cli: Cli, args: []const []const u8) !void {
const opts = try parseSimOptions(cli, args);
const path = opts.path.?;
const image = try loadImage(cli, path);
defer cli.gpa.free(image);
try runImage(cli, image);
if (opts.wantsReport()) try reportCommand(cli, image, opts);
}
/// Образ памяти из любого из трёх форматов: исходник собирается на месте.
fn loadImage(cli: Cli, path: []const u8) ![]u8 {
if (std.mem.endsWith(u8, path, ".ys")) {
var result = try assembleFile(cli, path);
defer result.deinit(cli.gpa);
return cli.gpa.dupe(u8, result.image);
}
const text = try readSource(cli, path);
defer cli.gpa.free(text);
return if (std.mem.endsWith(u8, path, ".hex"))
assembler.loadHex(cli.gpa, text)
else
assembler.loadYo(cli.gpa, text);
}
/// Второй прогон той же программы, уже через машину с кэшем и трассой
/// обращений. Программа детерминирована и крошечная, поэтому прогнать её
/// дважды проще, чем учить `trace.write` кэшу.
fn reportCommand(cli: Cli, image: []const u8, opts: SimOptions) !void {
var m: Machine = try .init(cli.gpa, opts.config);
defer m.deinit();
var file: ?std.Io.File = null;
defer if (file) |f| f.close(cli.io);
var file_buf: [4096]u8 = undefined;
var file_writer: std.Io.File.Writer = undefined;
if (opts.memtrace_path) |mt_path| {
file = try std.Io.Dir.cwd().createFile(cli.io, mt_path, .{});
file_writer = file.?.writerStreaming(cli.io, &file_buf);
m.recorder.writer = &file_writer.interface;
}
const report = try m.run(image);
if (file != null) try file_writer.interface.flush();
try report.print(cli.out, opts.config);
}Прогонов два, и это осознанно: сначала обычная трасса версии 1, та же байт в байт, что печаталась до кэша, потом та же программа ещё раз через Machine со сводкой. Программа детерминирована и крошечная, прогнать её дважды проще, чем учить trace.write кэшу. А главное, так сохраняется контракт из уроков про симулятор и конвейер Y86: кэш не имеет права менять трассу.
Прогон: sum.ys с кэшем и без
Трасса обращений программы sum.ys, той самой, чей листинг напечатан в книге целиком. Она снята командой zig build run -- sim programs/expected/sum.yo --memtrace sum.memtrace и лежит в tests/expected/sum.memtrace:
I 000,10
I 00a,9
S 1f8,8
I 038,10
I 042,10
I 04c,9
S 1f0,8
I 056,10
I 060,10
I 06a,2
I 06c,2
I 06e,9
I 087,9
I 077,10
L 018,8
I 081,2
I 083,2
I 085,2
I 087,9
I 077,10
L 020,8
I 081,2
I 083,2
I 085,2
I 087,9
I 077,10
L 028,8
I 081,2
I 083,2
I 085,2
I 087,9
I 077,10
L 030,8
I 081,2
I 083,2
I 085,2
I 087,9
I 090,1
L 1f0,8
I 055,1
L 1f8,8
I 013,1Тридцать четыре выборки, шесть чтений, две записи. Первая строка без пробела в начале, обращения к данным с пробелом: ровно то, что понимает csim. Первые три строки это irmovq stack, %rsp, call main и запись адреса возврата 0x013 на стек по адресу 0x1f8. Дальше четыре витка цикла, в каждом одно чтение из массива по адресам 0x018, 0x020, 0x028, 0x030, и два ret, которые читают адреса возврата обратно.
Теперь та же программа с кэшем. Четыре прогона, от просторного кэша к тесному:
$ zig build run -- sim programs/expected/sum.yo --cache s=8,E=1,b=4 --miss-penalty 10
...
инструкций 34, обращений к памяти: выборок 34, чтений 6, записей 2
кэш s=8,E=1,b=4 (общий): попаданий 31, промахов 11, вытеснений 0
тактов без кэша 34 (CPI 1.00), со штрафом 10 за промах 144 (CPI 4.24)
$ zig build run -- sim programs/expected/sum.yo --cache s=4,E=1,b=4 --miss-penalty 10
...
кэш s=4,E=1,b=4 (общий): попаданий 31, промахов 11, вытеснений 0
тактов без кэша 34 (CPI 1.00), со штрафом 10 за промах 144 (CPI 4.24)
$ zig build run -- sim programs/expected/sum.yo --cache s=4,E=1,b=4 --split --miss-penalty 10
...
кэш s=4,E=1,b=4 (раздельный для инструкций и данных): попаданий 29, промахов 13, вытеснений 0
тактов без кэша 34 (CPI 1.00), со штрафом 10 за промах 164 (CPI 4.82)
$ zig build run -- sim programs/expected/sum.yo --cache s=1,E=1,b=4 --miss-penalty 10
...
кэш s=1,E=1,b=4 (общий): попаданий 21, промахов 21, вытеснений 19
тактов без кэша 34 (CPI 1.00), со штрафом 10 за промах 244 (CPI 7.18)Читаем. Кэш на 256 наборов вмещает всю память машины, вытеснять нечего, и одиннадцать промахов это ровно число разных блоков по 16 байт, которые трасса трогает: посчитай их по трассе выше, блоков кода девять, с 0x000 по 0x09f без 0x020, плюс блок 0x1f0 со стеком, плюс блоки 0x010, 0x020 и 0x030 с массивом, из которых два делятся с кодом. Это холодные промахи, и меньше их не будет ни при каком кэше: блок, который ещё ни разу не приезжал, промахнётся при любом размере кэша. Шестнадцать наборов дают то же самое: программа лежит в первых 160 байтах, стек в последних шестнадцати, и они не пересекаются по индексу.
Раздельные кэши при тех же параметрах каждого дали на два промаха больше. Это не ошибка: блоки 0x010 и 0x030 содержат и код, и данные, в общем кэше они грузятся один раз, в раздельных дважды. Разделение не бесплатно: оно меняет, кто с кем делит наборы, а выигрыш это или проигрыш, решает программа.
И наконец два набора по 16 байт: программа не помещается, блоки выбивают друг друга по кругу, к одиннадцати холодным промахам добавляются десять по конфликту, и CPI вырастает до 7.18. Число инструкций во всех четырёх прогонах одно: кэш меняет цену такта, а не работу.
Тесты шага
//! Шаг 39: память машины пишет трассу обращений, между процессором и
//! памятью встаёт кэш.
//!
//! Проверяется три вещи. Первая: трасса совпадает с образцом байт в байт,
//! и её форма та же, что у valgrind lackey, так что её понимает симулятор
//! кэша из лабораторной. Вторая: счётчики кэша сходятся с независимым
//! подсчётом по самой трассе, а не с числом, которое напечатал тот же код,
//! что мы проверяем. Третья: штраф за промах виден в тактах и в CPI.
const std = @import("std");
const y86 = @import("y86");
const testing = std.testing;
const cache = y86.cache;
const machine = y86.machine;
const memtrace = y86.memtrace;
/// Образец трассы `sum.ys`, снятый вместе с уроком.
const expected_sum = @embedFile("sum.memtrace");
/// Собирает программу по имени и возвращает её образ памяти.
fn imageOf(name: []const u8) ![]u8 {
const program = y86.programs.get(name).?;
var result = try y86.assembler.assemble(testing.allocator, program.source, null);
defer result.deinit(testing.allocator);
return testing.allocator.dupe(u8, result.image);
}
test "трасса sum совпадает с образцом" {
const image = try imageOf("sum.ys");
defer testing.allocator.free(image);
const text = try machine.memtraceOf(testing.allocator, image, .{});
defer testing.allocator.free(text);
try testing.expectEqualStrings(expected_sum, text);
}
test "форма трассы та же, что у lackey" {
// Первая строка это выборка первой инструкции по адресу 0, без пробела
// в начале. У обращений к данным пробел есть: по нему их и различают.
try testing.expect(std.mem.startsWith(u8, expected_sum, "I 000,"));
try testing.expect(std.mem.indexOf(u8, expected_sum, "\n S ") != null);
try testing.expect(std.mem.indexOf(u8, expected_sum, "\n L ") != null);
var lines = std.mem.tokenizeScalar(u8, expected_sum, '\n');
var count: usize = 0;
while (lines.next()) |line| {
// Каждая строка обязана разбираться обратно в обращение.
const access = memtrace.parse(line) orelse {
std.debug.print("строка трассы не разобралась: {s}\n", .{line});
return error.TestUnexpectedResult;
};
try testing.expect(access.len == 8 or access.kind == .instr);
count += 1;
}
try testing.expect(count > 10);
}
/// Сколько разных блоков по `1 << b` байт трогает трасса. Это нижняя граница
/// числа промахов: каждый блок хотя бы раз приезжает в кэш холодным.
fn distinctBlocks(text: []const u8, b: u6) !usize {
var seen: std.AutoHashMapUnmanaged(u64, void) = .empty;
defer seen.deinit(testing.allocator);
var lines = std.mem.tokenizeScalar(u8, text, '\n');
while (lines.next()) |line| {
const access = memtrace.parse(line).?;
// Обращение может пересечь границу блока, поэтому считаем оба конца.
try seen.put(testing.allocator, access.addr >> b, {});
try seen.put(testing.allocator, (access.addr + access.len - 1) >> b, {});
}
return seen.count();
}
test "просторный кэш промахивается ровно на холодных блоках" {
const image = try imageOf("sum.ys");
defer testing.allocator.free(image);
// 256 наборов по 16 байт это 4 КБ: вся память машины помещается,
// вытеснять нечего, значит остаются только холодные промахи.
const params: cache.Params = .{ .s = 8, .e = 1, .b = 4 };
var m: machine.Machine = try .init(testing.allocator, .{ .cache = params, .miss_penalty = 10 });
defer m.deinit();
const report = try m.run(image);
const text = try machine.memtraceOf(testing.allocator, image, .{});
defer testing.allocator.free(text);
const cold = try distinctBlocks(text, 4);
const stats = report.cache.?;
try testing.expectEqual(cold, stats.misses);
try testing.expectEqual(@as(usize, 0), stats.evictions);
try testing.expectEqual(report.accesses.total(), stats.accesses());
}
test "тесный кэш добавляет промахи по конфликту" {
const image = try imageOf("sum.ys");
defer testing.allocator.free(image);
const text = try machine.memtraceOf(testing.allocator, image, .{});
defer testing.allocator.free(text);
const cold = try distinctBlocks(text, 4);
// Два набора по 16 байт: программа не помещается, и блоки начинают
// выбивать друг друга. Холодные промахи никуда не делись, к ним
// добавились промахи по конфликту.
const params: cache.Params = .{ .s = 1, .e = 1, .b = 4 };
var m: machine.Machine = try .init(testing.allocator, .{ .cache = params });
defer m.deinit();
const report = try m.run(image);
const stats = report.cache.?;
try testing.expect(stats.misses > cold);
try testing.expect(stats.evictions > 0);
try testing.expectEqual(report.accesses.total(), stats.accesses());
}
test "штраф за промах виден в тактах и в CPI" {
const image = try imageOf("sum.ys");
defer testing.allocator.free(image);
// Без кэша память отвечает за такт, и такт равен инструкции.
var plain: machine.Machine = try .init(testing.allocator, .{});
defer plain.deinit();
const without = try plain.run(image);
try testing.expectEqual(without.instructions, without.cycles());
try testing.expectEqual(@as(f64, 1.0), without.cpi());
const params: cache.Params = .{ .s = 1, .e = 1, .b = 4 };
var slow: machine.Machine = try .init(testing.allocator, .{
.cache = params,
.miss_penalty = 10,
});
defer slow.deinit();
const with = try slow.run(image);
// Число инструкций от кэша не зависит: кэш меняет цену такта, а не работу.
try testing.expectEqual(without.instructions, with.instructions);
const misses = with.cache.?.misses;
try testing.expectEqual(with.instructions + misses * 10, with.cycles());
try testing.expect(with.cpi() > 1.0);
}
test "раздельные кэши команд и данных считают те же обращения" {
const image = try imageOf("sum.ys");
defer testing.allocator.free(image);
const params: cache.Params = .{ .s = 4, .e = 1, .b = 4 };
var unified: machine.Machine = try .init(testing.allocator, .{ .cache = params });
defer unified.deinit();
const one = try unified.run(image);
var split: machine.Machine = try .init(testing.allocator, .{
.cache = params,
.organization = .split,
});
defer split.deinit();
const two = try split.run(image);
try testing.expectEqual(one.accesses.total(), two.accesses.total());
try testing.expectEqual(one.accesses.data(), two.accesses.data());
// Обе организации учитывают каждое обращение: разделение меняет, кто
// с кем делит наборы, а не сколько раз машина сходила в память.
try testing.expectEqual(one.accesses.total(), one.cache.?.accesses());
try testing.expectEqual(two.accesses.total(), two.cache.?.accesses());
// Разделение при тех же параметрах каждого кэша это не бесплатный
// выигрыш: инструкции теряют наборы, которые раньше делили с данными,
// и промахов может стать больше. Что выгоднее, решает программа.
try testing.expect(two.cache.?.misses > 0);
}Посмотри, как устроена сверка счётчиков: не с числом, которое напечатал тот же код, а с независимым подсчётом разных блоков по самой трассе. Просторный кэш обязан промахнуться ровно на холодных блоках, тесный обязан промахнуться больше, а сумма попаданий и промахов обязана равняться числу обращений в любой организации. Прогон zig build test -Dstep=39 в our-y86 зелёный, как и zig build test целиком.
Практика
Задача это ядро симулятора без парсера и без печати: структура Cache с параметрами (s, e, b), срезом строк и часами. В заготовке уже есть setIndex, tagOf и setLines из прошлой задачи, а три метода надо написать: init выделяет строки под все наборы и помечает их невалидными, deinit возвращает срез аллокатору, access(addr) делает одно обращение и возвращает .hit, .miss или .evict, обновляя last_used и счётчики.
Скрытые тесты гонят:
- пример из книги с адресами 0, 1, 7, 8, 0 на кэше из четырёх наборов с блоком в два байта;
- конфликтные промахи в прямом отображении и их исчезновение в двухпутевом кэше;
- LRU против FIFO: строка, которую трогали при попадании, не должна вытесняться первой;
- занятие свободной строки раньше вытеснения;
- трассу
yi.trace, гдеMразвёрнут в два вызоваaccessна стороне теста; - 48-битные адреса, у которых старшие биты обязаны попасть в тег;
- кэш на восемь тысяч строк под
std.testing.allocator, который проваливает тест при утечке.
Упражнения
Итоги
- Симулятор кэша не хранит данных: строка это бит валидности, тег и отметка времени. Этого достаточно, чтобы ответить на единственный вопрос, попал адрес или нет.
- Трасса в формате lackey это буква, адрес и размер.
Iкэш данных пропускает,LиSэто одно обращение,Mэто два: чтение и запись по одному адресу, и второе из них всегда попадание. - LRU это часы:
clockрастёт на каждом обращении,last_usedобновляется и при попадании, и при загрузке. Без обновления при попадании получается FIFO. - Вытеснение это тоже промах. Разница между
missesиevictionsэто холодные промахи, а число разных блоков в трассе это нижняя граница промахов при любом кэше. csimсходится с ручным подсчётом наyi.traceиdave.trace; сгенерированные трассы носят ответ в первой строке, и тест шага сверяет по нему симулятор.- Свои трассы снимаются без valgrind: обёртка над массивом записывает адрес и размер каждого обращения, адреса виртуальные, число промахов воспроизводится байт в байт.
- Задачи книги 6.36 до 6.43 как программы дают ровно бумажные доли: 100, 25 и 25 процентов у скалярного произведения, 25, 100 и 50 у трёх сумм при 64 на 64 и по 25 при 60 на 60, 25, 6.25 и 12.5 у квадрата CMYK, 25, 25 и 100 у буфера экрана.
- Доля промахов это не время: три очистки экрана дают одно и то же число промахов, а версия со 100 процентами быстрее всех, потому что записей вчетверо меньше.
- В Y86 кэш встал между процессором и памятью снаружи шести этапов: перехватчик после выборки и после этапа памяти. Трасса версии 1 не изменилась ни на байт.
- Такты равны инструкциям плюс промахи на штраф. На
sum.ysпри штрафе 10 CPI растёт с 1.00 до 4.24 на просторном кэше и до 7.18 на кэше из двух наборов; число инструкций при этом одно. - Раздельные кэши команд и данных при тех же параметрах каждого дали на два промаха больше: блоки, где код лежит рядом с данными, грузятся дважды.
Дальше
У тебя есть симулятор, которому можно скормить любую трассу, и генератор, который снимет трассу с любого цикла. В следующем уроке мы этим воспользуемся по-настоящему: возьмём умножение матриц и переберём все шесть порядков вложенности циклов, ijk, jik, jki, kji, kij, ikj. Посчитаем промахи на итерацию у каждого и увидим, что они распадаются на три класса, а разница между лучшим и худшим измеряется в разы. Потом вернём локальность на больших матрицах блочным разбиением, напишем транспонирование с минимумом промахов, вторую часть cachelab, и поговорим о том, как раскладывать структуры в памяти, чтобы кэш работал на тебя: массив структур против структуры массивов, линия кэша и ложное разделение между потоками. Симулятор из сегодняшнего урока будет считать каждую версию.
домашка