ioann44 / super-comps-course-work Goto Github PK

2nd task variant

Possible output

Реализован традиционный алгоритм перемножения матриц. Реализован алгоритм перемножения матриц с транспонированием, что обеспечивает более эффективное использование памяти за счёт кеширования. Как видно, транспонирование имеет смысл и действительно ускоряет получение результата.

Реализован алгоритм блочного перемножения. Оптимальным вариантом оказалось разбиение на блоки размером корня квадратного, тем не менее выигрыш на матрицах произвольного размера всё равно очень мал.

Запуск на различных типах данных обеспечивается с помощью шаблонов.

В целях дальнейшего ускорения реализован алгоритм Штрассена, имеющий лучшую асимптотику добавлено распараллеливание традиционного алгоритма.

Подсистема памяти современных ЭВМ называется многоуровневой из-за того, что она состоит из нескольких уровней, каждый из которых имеет различные характеристики, скорость доступа и емкость. Эти уровни организованы иерархически, обеспечивая оптимизацию доступа к данным в соответствии с требованиями производительности и стоимости.

Уровни памяти, которые я знаю, включают в себя:

• Регистры процессора
• Кэш-память (причём из 3 уровней)
• Оперативная память (RAM)
• Внешняя память (например, жесткие диски, SSD)

Принципы построения и основные характеристики каждого уровня:

• Регистры процессора: Быстрая доступная память, непосредственно связанная с процессором. Обычно имеют небольшой объем и используются для хранения данных, к которым нужен быстрый доступ.

- Размер регистров общего назначения обычно 64 бита в современных процессорах.
- Скорость доступа к регистрам процессора очень высокая, обычно составляет всего один цикл процессора или даже менее.

• Кэш-память: Память более высокого уровня, расположенная между регистрами и оперативной памятью. Она имеет более высокую скорость доступа по сравнению с оперативной памятью и используется для временного хранения данных, которые часто запрашиваются процессором.

Уровни кэша на процессоре обычно классифицируются как L1, L2 и L3. Размеры и скорость доступа к данным для каждого уровня могут различаться в зависимости от конкретной архитектуры процессора.

L1 Cache:
- Размер: Обычно от нескольких десятков килобайт до нескольких сотен килобайт.
- Скорость доступа: Очень высокая, обычно в пределах нескольких циклов процессора.
L2 Cache:
- Размер: Обычно от нескольких сотен килобайт до нескольких мегабайт.
- Скорость доступа: Скорость доступа к L2 кэшу обычно немного медленнее, чем к L1 кэшу, но все равно очень быстрая, обычно в пределах нескольких циклов процессора.
L3 Cache:
- Размер: Обычно от нескольких мегабайт до десятков мегабайт или даже сотен мегабайт, в зависимости от конкретной архитектуры процессора.
- Скорость доступа: Скорость доступа к L3 кэшу может быть чуть медленнее, чем к L1 и L2 кэшам, но по-прежнему очень быстрая, обычно в пределах десятков циклов процессора.

• Оперативная память (RAM): Основная память компьютера, используемая для хранения данных и программ во время их выполнения. Насколько знаю, один int считывается за 100 наносекунд.
• Внешняя память: Хранилище данных на постоянной основе, такое как жесткие диски или SSD.

Ассоциативность кэша означает, как данные из оперативной памяти соотносятся с ячейками кэша. Полностью ассоциативный кэш позволяет любым данным из оперативной памяти быть размещенными в любой доступной ячейке кэша, в то время как прямой (или прямоассоциативный) кэш имеет фиксированный набор мест, куда конкретные блоки из оперативной памяти могут быть помещены.

Проблема когерентности кэшей возникает, когда два или более кэша содержат копии одних и тех же данных и один из них изменяется. Это может привести к несогласованности данных между кэшами, что может привести к ошибкам в программном обеспечении. Способы обеспечения когерентности кэшей включают использование протоколов когерентности кэша, таких как MESI (Modified, Exclusive, Shared, Invalid), которые контролируют доступ к данным и управляют их обновлением и инвалидацией между кэшами. Преимущества включают повышение производительности за счет снижения нагрузки на память, но есть и недостатки, такие как увеличение сложности системы и возможное снижение производительности из-за накладных расходов на управление когерентностью.