Поиск :
Личный кабинет :
Электронный каталог: Prihozhy, A. A. - Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algori...
Prihozhy, A. A. - Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algori...
Статья
Автор: Prihozhy, A. A.
Системный анализ и прикладная информатика: Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algori...
Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей в графе
б.г.
ISBN отсутствует
Автор: Prihozhy, A. A.
Системный анализ и прикладная информатика: Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algori...
Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей в графе
б.г.
ISBN отсутствует
На полку
Статья
Prihozhy, A. A.
Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algorithms = Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей в графе / A. A. Prihozhy // Системный анализ и прикладная информатика / гл. ред. Сергей Васильевич Харитончик; учредитель Белорусский национальный технический университет (Минск). – 2019. – №4. – P. 10-18. – Режим доступа : https://rep.bntu.by/handle/data/62315. – На англ. яз.
Caches are intermediate level between fast CPU and slow main memory. It aims to store copies of frequently used data and to reduce the access time to the main memory. Caches are capable of exploiting temporal and spatial localities during program execution. When the processor accesses memory, the cache behavior depends on if the data is in cache: a cache hit occurs if it is, and, a cache miss occurs, otherwise. In the last case, the cache may have to evict other data. The misses produce processor stalls and slow down the computations. The replacement policy chooses a data to evict, trying to predict the future accesses to memory. The hit and miss rate depends on the cache type: direct mapped, set associative and fully associative cache. The least recently used replacement policy serves the sets. The miss rate strongly depends on the executed algorithm. The all pairs shortest paths algorithms solve many practical problems, and it is important to know what algorithm and what cache type match best. This paper presents a technique of simulating the direct mapped, k-way associative and fully associative cache during the algorithm execution, to measure the frequency of read data to cache and write data to memory operations. We have measured the frequencies versus the cache size, the data block size, the amount of processed data, the type of cache, and the type of algorithm. After comparing the basic and blocked Floyd-Warshall algorithms, we conclude that the blocked algorithm well localizes data accesses within one block, but it does not localize data dependencies among blocks. The direct mapped cache significantly loses the associative cache; we can improve its performance by appropriate mapping virtual addresses to physical locations.
Кэш является промежуточным уровнем между быстрым процессором и медленной основной памятью. Он предназначен для хранения копий часто используемых данных и сокращения времени доступа к основной памяти. Кэш способен использовать временную и пространственную локальность данных во время выполнения программы. Когда процессор обращается к памяти, поведение кэш зависит от того, находятся ли данные в нем: попадание в кэш происходит, если данные там, в противном случае, имеет место промах кэш. В последнем случае кэш может потребоваться удалить другие данные. Промахи приводят к остановке процессора и замедляют вычисления. Стратегия замены выбирает данные для удаления, пытаясь предсказать будущие обращения к памяти. Частота попаданий и промахов зависит от типа кэш: прямого сопоставления, множественно-ассоциативный и полностью ассоциативный кэш. Стратегия удаления наименее недавно использованных данных обслуживает множества слотов. Уровень промахов сильно зависит от выполняемого алгоритма. Алгоритмы поиска кратчайших путей между всеми парами вершин графа решают многие практические задачи, и важно знать, какой алгоритм и какой тип кэш лучше подходят друг другу. В этой статье представлен метод моделирования кэш прямого отображения, k-канального ассоциативного и полностью ассоциативного кэш во время выполнения алгоритма, для измерения частоты чтения данных в кэш и записи данных в память. Мы измерили частоты в зависимости от размера кэш, размера блока данных, объема обработанных данных, типа кэш и типа алгоритма. После сравнения основного и блочного алгоритмов Флойда-Уоршелла, мы пришли к выводу, что блочный алгоритм хорошо локализует доступ к данным внутри одного блока, но не локализует зависимости данных между блоками. Кэш прямого отображения значительно уступает ассоциативным кэш; мы можем улучшить его производительность путем соответствующего отображения виртуальных адресов на физические адреса памяти.
004.254
общий = БД Техника
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = КЭШ-ПАМЯТЬ
общий = ИЕРАРХИЧЕСКИЕ СИСТЕМЫ (систем. анализ; кибернет.)
общий = АЛГОРИТМЫ ПОИСКА ДАННЫХ
общий = ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
общий = АССОЦИАТИВНАЯ ПАМЯТЬ
Prihozhy, A. A.
Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algorithms = Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей в графе / A. A. Prihozhy // Системный анализ и прикладная информатика / гл. ред. Сергей Васильевич Харитончик; учредитель Белорусский национальный технический университет (Минск). – 2019. – №4. – P. 10-18. – Режим доступа : https://rep.bntu.by/handle/data/62315. – На англ. яз.
Caches are intermediate level between fast CPU and slow main memory. It aims to store copies of frequently used data and to reduce the access time to the main memory. Caches are capable of exploiting temporal and spatial localities during program execution. When the processor accesses memory, the cache behavior depends on if the data is in cache: a cache hit occurs if it is, and, a cache miss occurs, otherwise. In the last case, the cache may have to evict other data. The misses produce processor stalls and slow down the computations. The replacement policy chooses a data to evict, trying to predict the future accesses to memory. The hit and miss rate depends on the cache type: direct mapped, set associative and fully associative cache. The least recently used replacement policy serves the sets. The miss rate strongly depends on the executed algorithm. The all pairs shortest paths algorithms solve many practical problems, and it is important to know what algorithm and what cache type match best. This paper presents a technique of simulating the direct mapped, k-way associative and fully associative cache during the algorithm execution, to measure the frequency of read data to cache and write data to memory operations. We have measured the frequencies versus the cache size, the data block size, the amount of processed data, the type of cache, and the type of algorithm. After comparing the basic and blocked Floyd-Warshall algorithms, we conclude that the blocked algorithm well localizes data accesses within one block, but it does not localize data dependencies among blocks. The direct mapped cache significantly loses the associative cache; we can improve its performance by appropriate mapping virtual addresses to physical locations.
Кэш является промежуточным уровнем между быстрым процессором и медленной основной памятью. Он предназначен для хранения копий часто используемых данных и сокращения времени доступа к основной памяти. Кэш способен использовать временную и пространственную локальность данных во время выполнения программы. Когда процессор обращается к памяти, поведение кэш зависит от того, находятся ли данные в нем: попадание в кэш происходит, если данные там, в противном случае, имеет место промах кэш. В последнем случае кэш может потребоваться удалить другие данные. Промахи приводят к остановке процессора и замедляют вычисления. Стратегия замены выбирает данные для удаления, пытаясь предсказать будущие обращения к памяти. Частота попаданий и промахов зависит от типа кэш: прямого сопоставления, множественно-ассоциативный и полностью ассоциативный кэш. Стратегия удаления наименее недавно использованных данных обслуживает множества слотов. Уровень промахов сильно зависит от выполняемого алгоритма. Алгоритмы поиска кратчайших путей между всеми парами вершин графа решают многие практические задачи, и важно знать, какой алгоритм и какой тип кэш лучше подходят друг другу. В этой статье представлен метод моделирования кэш прямого отображения, k-канального ассоциативного и полностью ассоциативного кэш во время выполнения алгоритма, для измерения частоты чтения данных в кэш и записи данных в память. Мы измерили частоты в зависимости от размера кэш, размера блока данных, объема обработанных данных, типа кэш и типа алгоритма. После сравнения основного и блочного алгоритмов Флойда-Уоршелла, мы пришли к выводу, что блочный алгоритм хорошо локализует доступ к данным внутри одного блока, но не локализует зависимости данных между блоками. Кэш прямого отображения значительно уступает ассоциативным кэш; мы можем улучшить его производительность путем соответствующего отображения виртуальных адресов на физические адреса памяти.
004.254
общий = БД Техника
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = КЭШ-ПАМЯТЬ
общий = ИЕРАРХИЧЕСКИЕ СИСТЕМЫ (систем. анализ; кибернет.)
общий = АЛГОРИТМЫ ПОИСКА ДАННЫХ
общий = ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ
общий = АССОЦИАТИВНАЯ ПАМЯТЬ
