Если в лесу тикает счетчик, кто-нибудь его видит?
наши требования гласят, что каждое изменение числа должно быть видно на экране
частота обновления экрана sh вашего экрана, вероятно, составляет 60 Гц , а может быть и выше 144 Гц. Изменение видео-ОЗУ быстрее, чем это, оставит некоторые подсчеты непрочитанными при аппаратном сканировании l oop по кадровому буферу 1 , никогда не отправляется на физический экран и никогда не превращается в образец фотонов видимого света что высокоскоростная камера может записывать.
Сноска 1: Или виртуальный эквивалент, если текстовый режим VGA эмулируется каким-либо образом поверх аппаратного обеспечения, которое умеет рисовать только пиксели. На вопрос Поддерживает ли современное видеооборудование P C текстовый режим VGA в HW или B IOS эмулирует его (в режиме управления системой)? в качестве продолжения.
Если мы не принимаем этот предел в 1 приращение на 16,66 ... мс (60 Гц), нам нужно решить, на что мы хотим узкое место, в сравнении с тем, что мы можем обойти.
Конечно, нам нужно выполнить фактическую работу по вычислению цифр ASCII, а не просто увеличивать двоичный счетчик и иногда форматировать его в строку в таймере или вертикальное гашение прерывание (один раз на экран refre sh) , Это не удовлетворяло бы духу назначения.
Или что, если мы вычисляем цифры ASCII исключительно в регистрах и сохраняем только mov в таймере или прерывании vblank? Это будет производить асинхронную выборку быстродействующего счетчика из его приращений, чтобы вы могли визуально увидеть, как меняются все младшие разряды. (Это довольно четкое минимальное требование).
Пропускать магазины из фактического l oop все еще не похоже на то, что оно соответствует духу задания. Я думаю, что наш l oop должен, если он работает сам по себе, без какой-либо сложной аппаратной настройки, действительно получать все данные вплоть до видеопамяти. Это кажется спорным. Это то, что делает оригинальный код.
ЦП может быть настроен на комбинирование записи с MTRR . Некоторые настольные ПК имели опцию B IOS, чтобы установить AGP GART как U C (UnCacheable) против W C (называя это "USW C = Uncacheable Speculartive Combining"). Эта статья о настройке B IOS содержит раздел . Похоже, что современная прошивка оставляет VGA-память U C, позволяя ОС / графическим драйверам настраивать MTRR / PAT.
К сожалению, создание VGA-памяти W C работает тоже хорошо и магазины никогда не выходят из буфера объединения записи ядра ЦП . (LFB, так как это процессор Intel.) Мы можем вручную sh после каждого хранилища иметь барьер памяти, такой как mfence или clflushopt с адресом строки кэша. Но затем мы вернулись к тому, с чего начали, потому что в операционной системе iGPU / прошивке Kaby Lake от OP, кажется, что очистка хранилища W C стоит примерно столько же, сколько и обычное хранилище U C.
Конечно, мы должны делать грипп sh, когда весь счетчик синхронизирован c, после обновления всех цифр, если перенос рифлен далеко. Если бы мы хранили каждый di git по отдельности, это могло бы ускорить нас на 11.111%, если бы у меня была правильная математика против памяти U C. Или, если мы делали хранилища мечей из 2 цифр одновременно, на 1,0101%, потому что нам нужен только дополнительный магазин каждые 100 отсчетов, а не каждые 10.
Я думаю, что мы можем уловить дух задания, все еще позволяя аппаратное обеспечение оптимизирует наши магазины с помощью кадрового буфера W C и сброса при прерывании по таймеру или vblank.
Это означает, что мы увеличиваем счетчик очень быстро (почти 1 счет на ядро тактовый цикл с тщательной реализацией). И мы сэмплируем , чтобы противостоять этому, просто используя барьер памяти или инструкцию сериализации в обработчике прерываний, который запускается непосредственно перед тем, как видеооборудование начинает новый проход в верхнем левом углу экрана, сканируя новый кадр. На самом деле iret сериализуется, поэтому простое возвращение из пустого обработчика прерываний сделает эту работу. Удерживание клавиши на клавиатуре может даже сделать обновления счетчика видимыми на экране (где они не были иначе), если вы использовали MTRR для создания видеопамяти W C, но не запрограммировали прерывание по таймеру или вертикальное гашение для периодически запускать.
Использование clflush или mfence с внешнего уровня l oop не будет работать хорошо; это было бы синхронно с приращениями и, следовательно, оставляло бы младшие цифры всегда равными нулю. Это сделало бы тот факт, что мы только иногда грипп sh явно в l oop, вместо того, чтобы оставить сброс как нечто, что происходит из-за прерываний, которые являются частью нормальной работы системы. (Или, по крайней мере, так было бы, если бы этот загрузчик не был буквально единственным запущенным. Например, если бы он работал под DOS, вы бы прерывали таймер каждые несколько мс.)
Если мы настаиваем на сбросе к видео RAM каждый отсчет (либо оставив его U C, либо вручную с явным сбросом W C + в l oop), единственная оптимизация, которая будет иметь значение, - это уменьшение количества магазинов до видео RAM. т.е. не обновляя цифры, которые не меняются. Оригинальный код хранит каждый di git каждый раз, поэтому исправление, которое должно привести к ускорению почти в 10 раз.
Даже просто сохранение в не кэшируемый DRAM или выполнение транзакции P CIe намного медленнее чем что-либо, что вы могли бы оптимизировать внутри l oop, даже с помощью машины с самоизменяющимся кодом. И если сохранение в текстовом кадровом буфере VGA вызывает прерывание режима управления системой (SMI) для эмуляции текстового режима путем обновления кадрового буфера реального пикселя, стоимость сохранения кадра является астрономической по сравнению со всем, что вы могли бы сделать в l * 1295. *. Вполне может быть так, как работает прошивка для наших интегрированных графических процессоров Skylake / Kaby Lake: Поддерживает ли современное видеооборудование P C текстовый режим VGA в HW или B IOS эмулирует его (в режиме управления системой)?
Разрешение аппаратному обеспечению объединять записи в наших магазинах с VRAM, таким образом, важно для того, чтобы сделать эту проблему оптимизации интересной, помимо одного алгоритма c твик.
Для этого запрограммируйте MTRR для кадрового буфера VGA. https://wiki.osdev.org/MTRR документирует фактические MSR, которые вы можете использовать с инструкцией wrmsr . Я думаю, что каждая MSR имеет битовое поле из 8 регионов. Нужно выбрать IA32_MTRR_FIX16K_A0000, в MSR[259] - 8 областей по 16 КБ каждая (всего 128 КБ) , которые включают в себя блок линейного адреса B8000, который содержит память текстового режима VGA. Рисунок 11-8 в Intel SDM vol 3 описывает структуру.
Предполагается W C видеопамять (или для обновления кэш-памяти WB)
Есть много вещей, которые нужно улучшить , но две важные вещи:
Микроархитектура: Самоизменяющийся код конвейерного ядерного оружия , иначе машина очищается, с count[] существо в той же строке кэша 64B, что и ваша основная l oop ( ~ 50x производительность без других изменений.) Без изменения этого трудно увидеть какие-либо выгоды от любой другой микрооптимизации.
Алгоритмы c: Не распространяйте вслепую, переносите весь путь вверх через каждый ди git каждый раз : 90% приращений вообще не переносятся, 99% несут только 1 место, эт c. Вложенные циклы для обработки младших цифр могут работать очень эффективно, просто увеличивая их собственный счетчик di git и имея внешний l oop, сбрасывающий его в '0', нет необходимости явно распространять эти переносы с adc. Хранение этих цифр ASCII в регистрах также избавляет от необходимости загружать / сохранять их в counts[], просто в чистые хранилища в видеопамять, например mov [di-4], eax.
С очень эффективными внутренними циклами для низких цифр, производительность верхние 6 или 7 цифр становятся почти неактуальными. Эта часть выполняется один раз с шагом 10 кб или 1 кб, поэтому ее стоимость амортизируется. ( ~ 19x ускорение для агрессивно оптимизированных внутренних циклов по сравнению с микрооптимизированная версия вашего оригинала l oop, которая экономит некоторые мопы и позволяет избежать некоторых узких мест без изменения алгоритма.)
Другие микрооптимизации вашего оригинала (после исправления SM C машина сбрасывает) дает коэффициент ускорения в ~ 1,5 раза: обычная ветвь переноса обычно не берется, сохраняются некоторые мопы, избегаются некоторые ложные зависимости частичного регистра из lodsb и записывается 16-битный частичный регистр.
С оптимизированными четырьмя уровнями внутренних циклов, которые я переписал с нуля, моя версия примерно в 29 раз быстрее на Skylake / Kaby Lake, чем не-SM C -установленная версия оригинальной , или ~ 1500 раз быстрее, чем настоящий оригинал. Конечно, есть середина, где вы adc несете распространение, но заблаговременно, когда CF == 0; Я не пытался реализовать это.
Протестировано в 32-битном режиме, но тот же код, собранный для 16-битного режима, должен выполняться точно так же, включая киоски SM C в вашем оригинале. (Предполагая, что хранилища W C не запускают SMI до тех пор, пока он не будет очищен, и что буфер W C сохраняет локальные хранилища внутри ядра, так что ~ 1 хранилище / тактовые импульсы возможны, как с памятью WB.)
SKL и KBL имеют одинаковую тактовую частоту, одинаковую микроархитектуру, поэтому результаты моих тестов должны быть воспроизводимы для вас. Я собрал ваш код в 16-битном режиме, чтобы увидеть выравнивание: похоже, ваш l oop будет иметь несколько байтов count[] в той же строке 64-байтового кэша, что и конец l oop, следовательно, SM C конвейерное ядро за итерацию для большинства цифр.
Я адаптировал ваш исходный код, чтобы можно было запускать тот же l oop в 32-битном режиме под Linux, делая можно использовать perf для профилирования со счетчиками производительности HW. Первым шагом в оптимизации чего-либо является получение базового измерения. Поскольку вы упоминаете некоторые микрооптимизации по микроархитектурным причинам, мы хотим, чтобы счетчики производительности не просто составляли общее время. Мы не можем легко получить это в загрузчике на голом металле. Возможно, в гостевой виртуальной машине, но тогда вы будете хранить данные на виртуальном VGA-устройстве, а не на реальном оборудовании, поэтому это, вероятно, не отличается от использования обычных или NT-хранилищ в обычной памяти WB в пользовательском пространстве под Linux.
perf stat -I1000 показывать счетчики для объема работы, выполняемой каждую секунду, - это удобный способ сравнить скорость для твиков, которые не меняют алгоритм или количество ветвей. Посмотрите на количество ответвлений за 1 секунду, чтобы увидеть относительную скорость l oop, или разделите ее на циклы.
Я использовал movnti, чтобы попытаться смоделировать хранилище для W C видео RAM ( спекулятивное объединение с записью без кэширования вместо обычного WB = кэширование с обратной записью). Я думаю, что нормальные хранилища для областей памяти W C ведут себя как movnt хранилища. movnt хранилища, которые не завершают строку кэша, могут продолжать обновлять тот же LFB, сочетающий запись, без фактического сброса в память. Так что это похоже на обычное хранилище для памяти WB, которое может попадать в кэш L1d.
SMI-перехват хранилищ кадрового буфера (если вообще выполняется) выполняется аппаратными средствами вне ядра ЦП, возможно, системным агентом, поэтому не срабатывает, пока ядро не сбрасывается. Или, если нет ловушки SMI, то, вероятно, это просто идет на DRAM в наших системах iGPU. Или по шине P CIe для доступа к видеопамяти на отдельной карте.
Версии, рассчитанные под ядро GNU / Linux 5.5.10 на i7-6700k на несколько простаивающих система с тактовой частотой ~ 4,2 ГГц
DRAM и кэш-память практически не задействованы, и система была достаточно простаившей, чтобы ничто не занимало циклы на другом логическом ядре физического ядра, поэтому в коде был весь ЦП для себя самого время спама хранится в буфере объединения записей.
- Исходная версия, портированная для запуска в 32-битном пользовательском пространстве: Godbolt - не полностью по времени, но
perf stat -I1000 для печати статистики в секунду показывает, что она работает примерно в 52 раза медленнее, чем с align 64 до counter:. Ядерный конвейер может включать в себя очищающие буферы W C, что также означало бы обращение к DRAM. - Первоначальная версия, в которой было предотвращено использование ядерных конвейеров SM C: ~ 85,7 секунды, ~ 358 миллиардов тактов ядра для 10 ^ 10 отсчетов. 2,66 IP C
- Микрооптимизированная версия этого: Godbolt - ~ 55,3 секунды, ~ 231 млрд тактовых циклов для 10 ^ 10 отсчетов. 4,56 IP C (но с более простыми инструкциями, не lodsb)
- Новые внутренние циклы, пустой заполнитель, внешний l oop: Godbolt - ~ 2,93 секунды , ~ 12,25 миллиарда тактовых импульсов ядра. 2.73 IP C
Оптимизированная версия достигает почти 3 магазинов за 4 такта. (Подсчет младших 2 цифр от 00..99 занимает 100 магазинов, как он это делает. Я не рассчитывал эти окончательные версии с clflushopt.)
Если вы исправили некоторые киоски и остановил ваш l oop с CF == 0, это привело бы к узким местам при задержке сохранения / перезагрузки (пересылки в хранилище) к младшему элементу массива count. Вы определенно хотите, чтобы они были в регистрах, чтобы они могли быть доступны только для магазина, а не для загрузки / adc / store.
TODO: прокомментируйте и поговорите о микрооптимизациях, которые я применил для этой версии:
- Почему G CC не использует частичные регистры? / Как именно работают частичные регистры на Haswell / Skylake? Написание AL, похоже, ложно зависит от RAX, а AH несовместимо - также
lodsb отстой. lodsd / q все в порядке. Используйте movzx для выполнения узких загрузок вместо слияния с младшим байтом. К счастью, inc / dec в adc l oop в семействе Sandybridge - это нормально, не вызывая частичных флагов , как , как в семействе P6 . Особенно в Skylake, который вообще не выполняет слияние флагов, а просто читает части CF и / или SPAZO флагов отдельно, если это необходимо. (Следствие: cmovbe и cmova - это 2 мопа для чтения 2 целочисленных входов и CF + ZF; другие cmov - только 1 моп.) - Вы можете использовать 32-битные регистры в 16-битном режиме вам не нужно переключать режимы. Ассемблер просто использует префикс размера операнда. Запись 32-битного регистра не зависит от старого значения, но 16 или 8 делает. Я использовал это, чтобы разорвать цепочки зависимостей, которые в противном случае были бы перенесены на l oop, , позволяя процессору использовать параллелизм на уровне команд (ILP) на протяжении l oop итераций / http://www.lighterra.com/papers/modernmicroprocessors/.
- Haswell / Skylake приняли пропускную способность ветвления 1 / такт, но могут запускать не взятые и взятые в одном и том же цикле. Выкладывайте ветки, чтобы отдавать предпочтение не взятым на быстрый путь (в общем, хорошая идея).
- Какая микроархитектура Intel представила особый случай AD C reg, 0 single-uop? -
adc al,0 - это, к сожалению, 2 мопа на Skylake, в отличие от adc eax,0 или adc bl,0. Сумасшедший, верно? В основном это ошибка производительности ЦП или пропущенная оптимизация ЦП разработчиками оборудования, когда специальные коды операций для меньших кодировок декодируют хуже. 32-байтовая выровненная подпрограмма не соответствует кэш мопов - последняя ошибка Intel J CC делает проверку idq.mite_uops perf достойной внимания. Когда-то Skylake был довольно устойчив к выравниванию кода, но теперь это ужасно для кода с высокой пропускной способностью.
Perf не полностью падает с обрыва, но существенный фактор возможен из-за узких мест переднего плана из-за необходимости использовать устаревшее декодирование для некоторых 32-байтовых блоков машинного кода, которые заканчиваются jcc на 32-байтовой границе. Я не потратил много сил на эту оптимизацию для этого кода, но быстрые версии, по мнению счетчиков перфокарт, позволяют избежать этой проблемы.
Моя версия с вложенными циклами, тестируется на GNU / Linux
Это только внутренний цикл; внешний l oop просто повторяет это 10 ^ 10 / 10k раз без фактической работы external-l oop. Мы оставляем внутренние 4 цикла только один раз на 10 тыс. Приращений, поэтому притворство в том, что эта часть занимает нулевое время, особенно не меняет результат.
Один и тот же паттерн из 2-х вложенных уровней зацикливания на регистр может повторяться несколько раз, или просто сделать цепочку из adc, как вы делали.
;; nasm -felf32 decimal-counter.asm
;; ld -N -melf_i386 -o decimal-counter decimal-counter.o
;; writeable text segment like a bootloader
;; runs in 32-bit mode with prefixes for 16-bit operand-size
;;
;; taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,resource_stalls.any:u,rs_events.empty_cycles:u,machine_clears.count:u -I1000 ./decimal-counter
%use smartalign
alignmode p6, 64
;org 7c00h
;pos equ vram + 2*(2*80-2) ;address on screen
pos equ vram + 2*(2*80-4) ;address on screen
; In GDB, use
; p ((char*)&vram) + 2*(2*80-4)-36
;init
;cli
;mov ax,3
;int 10h
;mov ax,0b800h
;mov es,ax
;jmp 0:start
; pick your poison, or let stores stay in the CPU, not reaching VRAM
%macro FLUSH 1
; clflushopt %1 ; all the way to DRAM
; mfence ; for mov to WB: just drain store buffer. For WC or movnt, IDK how guaranteed it is to hit DRAM
; lock xor byte [esp], 0 ; faster version of mfence (at least on Skylake)
%endmacro
;%define movnti mov ; for experiments
global _start
align 512
_start:
; push cs
; pop ds
; mov ebp, counter+9 ; save address in a register
; mov edi,pos
mov edi, pos - 10*4
mov eax, '0_0_'
mov ecx, 10
rep stosw ; memset the digits in VRAM
mov ebp, 10000000000 / 10000 ; outer loop iterations
mov edi, pos-4
; mov ah, 4Eh ; VGA attribute byte
; mov eax, '____'
align 32
.outer:
mov edx, '0_0_' ; thousands (low), hundreds (high) digits
.thousands:
.hundreds:
movnti [edi-4], edx
; don't want to flush yet; only after low digits are updated
add edx, 1<<16
mov eax, '0_0_' ; tens (low=AX), ones (high) digits
.tens:
.ones: ; do{
movnti [edi], eax ; store low 2 digits
FLUSH [edi]
lea ecx, [eax + (1<<16)] ; off the critical path of the EAX dep chain
movnti [edi], ecx
FLUSH [edi]
add eax, 2<<16 ; unroll by 2
cmp eax, '9_'<<16
jle .ones ; }while(ones<='9')
; mov byte [edi+2], '9' ; peel the last 2 iterations?
add eax, ('1_0_') - ('0_0_' + (10<<16)) ; increment the more-significant digit (AL), resetting less-significant digit back to '0'
cmp al, '9'
jle .tens
cmp edx, '9_9_'
jle .hundreds
add edx, ('1_0_') - ('0_0_' + (10<<16)) ; increment the more-significant digit (DL), resetting less-significant digit back to '0'
cmp dl, '9'
jle .thousands
;; TODO: increment the high 6 digits, propagating carry. Possibly clflushopt here only?
; pause
dec ebp
jnz .outer
; jmp $
mov eax, 1
int 0x80
;section .data ; avoids machine clears
; in original 16-bit code: counter starts at 00000037 30<rept>, ends at 00000040 (inclusive), in same cache line as the loop
align 64
counter:
times 10 db '0'
;section .text
times 510-($-$$) db 0
dw 0aa55h
section .bss
vram: resw 80*25
Я проверял, что это работает для младших цифр , одноступенчатых в GDB и использования display ((char*)&vram) + 2*(2*80-4)-36 или чего-то подобного для отображения содержимого этой части BSS в виде строки на каждом шаге.
Использование хранилищ dword означает что когда они размещаются, нам не нужен отдельный магазин для обновления десятков. Он просто должен обновить младший байт того же регистра и позволить первой итерации внутреннего l oop сделать это хранилище.
Во время переключения с 0099 на 0100 содержимое памяти временно 0199. Но если вы не используете SSE для хранения 16 байтов одновременно, вы не сможете избежать одной или другой проблемы. Другим вариантом было бы как-то договориться о 0000 до 0100, но это могло бы потратить магазин на меч десятков / единиц в сотнях l oop.