Список использованных источников

АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОБРАЗОВАТЕЛЬНАЯ

ОРГАНИЗАЦИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

ЦЕНТРОСОЮЗА РОССИЙСКОЙ ФЕДЕРАЦИИ

«РОССИЙСКИЙ УНИВЕРСИТЕТ КООПЕРАЦИИ»

КРАСНОДАРСКИЙ КООПЕРАТИВНЫЙ ИНСТИТУТ (ФИЛИАЛ)

Факультет: Среднего профессионального образования

Кафедра: Бухгалтерского учета и информационных технологий

Специальность: 09.02.04 Информационные системы (по отраслям)

Курс 2 Форма обучения

КУРСОВАЯ РАБОТА

Краснодар 2017

АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ОБРАЗОВАТЕЛЬНАЯ

ОРГАНИЗАЦИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

ЦЕНТРОСОЮЗА РОССИЙСКОЙ ФЕДЕРАЦИИ

«РОССИЙСКИЙ УНИВЕРСИТЕТ КООПЕРАЦИИ»

КРАСНОДАРСКИЙ КООПЕРАТИВНЫЙ ИНСТИТУТ (ФИЛИАЛ)

Факультет: среднего профессионального образования

Кафедра: Бухгалтерского учета и информационных технологий

Специальность: 09.02.04 Информационные системы (по отраслям)

УТВЕРЖДАЮ

Заведующий кафедрой

__________к.э.н. Н.В. Ходаринова

ЗАДАНИЕ

ПО КУРСОВОЙ РАБОТЕ

                         Березовского Кирилла Александровича

1 Тема работы: «Оптимизация доступа к кэш-памяти»

2 Срок сдачи законченной работы на кафедру «____» _____ 2017 г.

3 Содержание пояснительной записки (перечень подлежащих разработке вопросов):

1.Кэш память

2. Кэш-процессора

3. производители чипов

4. увеличение объема памяти

5. Оптимизация кода: память

Календарный план выполнения курсовой работы

на тему: «Оптимизация доступа к кэш-памяти»

обучающийся Березовский Кирилл Александрович

факультет среднего профессионального образования

курса 2 формы обучения очной

Обучающийся Березовский К.А. ____________       

Руководитель Богачев А.Ю. ____________

СОДЕРЖАНИЕ

Введение………………………………………………………….………..5

1 Кэш-память……………………………………………………………..7

2Кэш-процессора………………………………………………………...9

3Оптимизация кода: память……………………………………………15

4 Производители чипов…………………………………………………22

5Увеличение объема памяти……………………………………………23

Заключение……………………………………………………..................26

Список использованных источников…………………………………..27

Введение

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

Кэш память является одним из важнейших элементов компьютера. Именно из нее процессор берет программы и исходные данные для обработки, в нее он записывает полученные результаты. Название «оперативная» эта память получила потому, что она работает очень быстро, так что процессору практически не приходится ждать при чтении данных из памяти или записи в память. Однако содержащиеся в ней данные сохраняются только пока компьютер включен или до нажатия кнопки сброса (reset). При выключении компьютера содержимое оперативной памяти стирается. Поэтому перед выключением или нажатием кнопки сброса все данные, подвергнутые во время работы изменениям, необходимо сохранить на запоминающем устройстве. При новом включении питания сохраненная информация вновь может быть загружена в память.

Часто для оперативной памяти используют обозначение RAM (RandomAccessMemory, то есть память с произвольным доступом). Это означает, что обращение к данным, хранящимся в оперативной памяти, не зависит от порядка их расположения в памяти. Когда говорят о памяти компьютера, обычно подразумевают оперативную память, прежде всего микросхемы памяти или модули, в которых хранятся активные программы и данные, используемые процессором.

Кэш-память

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

Кэш-память напрямую влияет на скорость вычислений и помогает процессору работать с более равномерной загрузкой. Представьте себе массив информации, используемой в вашем офисе. Небольшие объемы информации, необходимой в первую очередь, скажем список телефонов подразделений, висят на стене над вашим столом. Точно так же вы храните под рукой информацию по текущим проектам. Реже используемые справочники, к примеру, городская телефонная книга, лежат на полке, рядом с рабочим столом. Литература, к которой вы обращаетесь совсем редко, занимает полки книжного шкафа.

Компьютеры хранят данные в аналогичной иерархии. Когда приложение начинает работать, данные и команды переносятся с медленного жесткого диска в оперативную память произвольного доступа (DynamicRandomAccessMemory — DRAM), откуда процессор может быстро их получить. Оперативная память выполняет роль кэша для жесткого диска.

Кэш-память построена на триггерах, которые, в свою очередь, состоят из транзисторов. Группа транзисторов занимает гораздо больше места, нежели те же самые конденсаторы, из которых состоит оперативная память. Это тянет за собой множество трудностей в производстве, а также ограничения в объёмах. Именно поэтому кэш память является очень дорогой памятью, при этом обладая ничтожными объёмами. Но из такой структуры, вытекает главное преимущество такой памяти – скорость. Так как триггеры не нуждаются в регенерации, а время задержки вентиля, на которых они собраны, невелико, то время переключения триггера из одного состояния в другое происходит очень быстро. Это и позволяет кэш-памяти работать на таких же частотах, что и современные процессоры.

Также, немаловажным фактором является размещение кэш-памяти. Размещена она, на самом кристалле процессора, что значительно уменьшает время доступа к ней. Ранее, кэш память некоторых уровней, размещалась за пределами кристалла процессора, на специальной микросхеме SRAM где-то на просторах материнской платы. Сейчас же, практически у всех процессоров, кэш-память размещена на кристалле процессора.

Кэш микропроцессора

Кэш микропроцессора—кэш(сверхоперативная память), используемый микропроцессором компьютера для уменьшения среднего времени доступа компьютерной памяти. Является одним из верхних уровней иерархии памяти. Кэш использует небольшую, очень быструю память (обычно типаSRAM), которая хранит копии часто используемых данных из основной памяти. Если большая часть запросов в память будет обрабатываться кэшем, средняя задержка обращения к памяти будет приближаться к задержкам работы кэша.

Когда процессору нужно обратиться в память для чтения или записи данных, он сначала проверяет, доступна ли их копия в кэше. В случае успеха проверки процессор производит операцию используя кэш, что значительно быстрее использования более медленной основной памяти. Подробнее о задержках памяти см.ЛатентностьSDRAM: tCAS, tRCD, tRP, tRAS.

Данные между кэшем и памятью передаются блоками фиксированного размера, также называемые линиями КЭШа(англ.cacheline) или блоками кэша.

Большинство современных микропроцессоров для компьютеров и серверов имеют как минимум три независимых кэша:кэш инструкцийдля ускорения загрузкимашинного кода, кэш данныхдля ускорения чтения и записи данных ибуфер ассоциативной трансляции(TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных. Кэш данных часто реализуется в виде многоуровневого кэша (L1, L2, L3).

Увеличение размера кэш-памяти может положительно влиять на производительность почти всех приложений, хотя в некоторых случаях эффект незначителен. Работа кэш-памяти обычно прозрачна для программиста, однако для её эффективного использования в некоторых случаях применяются специальные алгоритмические приёмы, изменяющие порядок обхода данных в ОЗУ или повышающие их локальность (например, при блочном умножении матриц)

Оптимизация кода: память

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

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

Иерархия памяти работает, потому что хорошо написанные программы имеют тенденцию обращаться к хранилищу на каком-то конкретном уровне более часто, чем к хранилищу на более низком уровне. Так что хранилище на более низком уровне может быть медленнее, больше и дешевле. В итоге мы получаем большой объём памяти, который имеет стоимость хранилища в самом низу иерархии, но доставляет данные программе со скоростью быстрого хранилища в самом верху иерархии.

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

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

На написание этой статьи меня вдохновила шестая глава из книги ComputerSystems: A Programmer'sPerspective. В другой статье из этой серии, «Оптимизация кода: процессор», мы также боремся за такты процессора.

Память тоже имеет значение

Рассмотрим две функции, которые суммируют элементы матрицы. Они практически одинаковы, только первая функция обходит элементы матрицы построчно, а вторая — по столбцам.

int matrixsum1(int size, int M[][size])

{

int sum = 0;

for (inti = 0; i< size; i++) {

for (int j = 0; j < size; j++) {

sum += M[i][j]; // обходим построчно

}

}

return sum;

}

int matrixsum2(int size, int M[][size])

{

int sum = 0;

for (inti = 0; i< size; i++) {

for (int j = 0; j < size; j++) {

sum += M[j][i]; // обходим по столбцам

   }

}

returnsum;

}
Обе функции выполняют одно и то же количество инструкций процессора. Но на машине с Core i7 Haswell первая функция выполняется в 25 раз быстрее для больших матриц. Этот пример хорошо демонстрирует, что память тоже имеет значение. Если вы будете оценивать эффективность программ только в терминах количества выполняемых инструкций, вы можете писать очень медленные программы.

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

Иерархия памяти

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

На вершине иерархии находятся регистры процессора. Доступ к ним занимает 0 тактов, но их всего несколько штук. Далее идёт несколько килобайт кэш-памяти первого уровня, доступ к которой занимает примерно 4 такта. Потом идёт пара сотен килобайт более медленной кэш-памяти второго уровня. Потом несколько мегабайт кэш-памяти третьего уровня. Она гораздо медленней, но всё равно быстрее оперативной памяти. Далее расположена относительно медленная оперативная память.

Оперативную память можно рассматривать как кэш для локального диска. Диски это рабочие лошадки среди устройств хранения. Они большие, медленные и стоят дёшево. Компьютер загружает файлы с диска в оперативную память, когда собирается над ними работать. Разрыв во времени доступа между оперативной памятью и диском колоссальный. Диск медленнее оперативной памяти в десятки тысяч раз, и медленнее кэша первого уровня в миллионы раз. Выгоднее обратиться несколько тысяч раз к оперативной памяти, чем один раз к диску. На это знание опираются такие структуры данных, как B-деревья, которые стараются разместить больше информации в оперативной памяти, пытаясь избежать обращения к диску любой ценой.

Локальный диск сам может рассматриваться как кэш для данных, расположенных на удалённых серверах. Когда вы посещаете веб-сайт, ваш браузер сохраняет изображения с веб-страницы на диске, чтобы при повторном посещении их не нужно было качать. Существуют и более низкие иерархии памяти. Крупные дата центры, типа Google, сохраняют большие объёмы данных на ленточных носителях, которые хранятся где-то на складах, и когда понадобятся, должны быть присоединены вручную или роботом.

Таблица 1 - Современная система имеет примерно такие характеристики

Быстрая память стоит очень дорого, а медленная очень дёшево. Это великая идея архитекторов систем совместить большие размеры медленной и дешёвой памяти с маленькими размерами быстрой и дорогой. Таким образом система может работать на скорости быстрой памяти и иметь стоимость медленной. Давайте разберёмся как это удаётся.

Допустим, ваш компьютер имеет 8 ГБ оперативной памяти и диск размером 1000 ГБ. Но подумайте, что вы не работаете со всеми данными на диске в один момент. Вы загружаете операционную систему, открываете веб-браузер, текстовый редактор, пару-тройку других приложений и работаете с ними несколько часов. Все эти приложения помещаются в оперативной памяти, поэтому вашей системе не нужно обращаться к диску. Потом, конечно, вы закрываете одно приложение и открываете другое, которое приходится загрузить с диска в оперативную память. Но это занимает пару секунд, после чего вы несколько часов работаете с этим приложением, не обращаясь к диску. Вы не особо замечаете медленный диск, потому что в один момент вы работаете только с небольшимбъёмом данных, которые кэшируются в оперативной памяти. Вам нет смысла тратить огромные деньги на установку 1024 ГБ оперативной памяти, в которую можно было бы загрузить содержимое всего диска. Если бы вы это сделали, вы бы почти не заметили никакой разницы в работе, это было бы «деньги на ветер».

Так же дело обстоит и с маленькими кэшами процессора. Допустим вам нужно выполнить вычисления над массивом, который содержит 1000 элементов типа int. Такой массив занимает 4 КБ и полностью помещается в кэше первого уровня размером 32 КБ. Система понимает, что вы начали работу с определённым куском оперативной памяти. Она копирует этот кусок в кэш, и процессор быстро выполняет действия над этим массивом, наслаждаясь скоростью кэша. Потом изменённый массив из кэша копируется назад в оперативную память. Увеличение скорости оперативной памяти до скорости кэша не дало бы ощутимого прироста в производительности, но увеличило бы стоимость системы в сотни и тысячи раз. Но всё это верно только если программы имеют хорошую локальность.

Локальность

Локальность — основная концепция этой статьи. Как правило, программы с хорошей локальностью выполняются быстрее, чем программы с плохой локальностью. Локальность бывает двух типов. Когда мы обращаемся к одному и тому же месту в памяти много раз, это временнáя локальность. Когда мы обращаемся к данным, а потом обращаемся к другим данным, которые расположены в памяти рядом с первоначальными, это пространственная локальность.

Рассмотрим, программу, которая суммирует элементы массива:

intsum(intsize, int A[])

{

inti, sum = 0;

for (i = 0; i< size; i++)

sum += A[i];

return sum;

}

В этой программе обращение к переменным sum и i происходит на каждой итерации цикла. Они имеют хорошую временную локальность и будут расположены в быстрых регистрах процессора. Элементы массива A имеют плохую временную локальность, потому что к каждому элементу мы обращаемся только по разу. Но зато они имеют хорошую пространственную локальность — тронув один элемент, мы затем трогаем элементы рядом с ним. Все данные в этой программе имеют или хорошую временную локальность или хорошую пространственную локальность, поэтому мы говорим что программа в общем имеет хорошую локальность.

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

Перемещение данных между уровнями иерархии осуществляется блоками определённого размера. К примеру, процессор Core i7 Haswell перемещает данные между своими кэшами блоками размером в 64 байта. Рассмотрим конкретный пример. Мы выполняем программу на машине с вышеупомянутым процессором. У нас есть массив v, содержащий 8-байтовые элементы типа long. И мы последовательно обходим элементы этого массива в цикле. Когда мы читаем v[0], его нет в кэше, процессор считывает его из оперативной памяти в кэш блоком размером 64 байта. То есть в кэш отправляются элементы v[0]–v[7]. Далее мы обходим элементы v[1], v[2], ..., v[7]. Все они будут в кэше и доступ к ним мы получим быстро. Потом мы читаем элемент v[8], которого в кэше нет. Процессор копирует элементы v[8]–v[15] в кэш. Мы быстро обходим эти элементы, но не находим в кэше элемента v[16]. И так далее.

Поэтому если вы читаете какие-то байты из памяти, а потом читаете байты рядом с ними, они наверняка будут в кэше. В этом выгода от пространственной локальности. Нужно стремиться на каждом этапе вычисления работать с данными, которые расположены в памяти рядом.

Желательно обходить массив последовательно, читая его элементы один за другим. Если нужно обойти элементы матрицы, то лучше обходить матрицу построчно, а не по столбцам. Это даёт хорошую пространственную локальность. Теперь вы можете понять, почему функция matrixsum2работала медленнее функции matrixsum1. Двумерный массив расположен в памяти построчно: сначала расположена первая строка, сразу за ней идёт вторая и так далее. Первая функция читала элементы матрицы построчно и двигалась по памяти последовательно, будто обходила один большой одномерный массив. Эта функция в основном читала данные из кэша. Вторая функция переходила от строки к строке, читая по одному элементу. Она как бы прыгала по памяти слева-направо, потом возвращалась в начало и опять начинала прыгать слева-направо. В конце каждой итерации она забивала кэш последними строками, так что в начале следующей итерации первых строк кэше не находила. Эта функция в основном читала данные из оперативной памяти.

Дружелюбный к кэшу код

Как программисты вы должны стараться писать код, который, как говорят, дружелюбный к кэшу (cache-friendly). Как правило, основной объём вычислений производится лишь в нескольких местах программы. Обычно это несколько ключевых функций и циклов. Если есть вложенные циклы, то внимание нужно сосредоточить на самом внутреннем из циклов, потому что код там выполняется чаще всего. Эти места программы и нужно оптимизировать, стараясь улучшить их локальность.

Вычисления над матрицами очень важны в приложениях анализа сигналов и научных вычислениях. Если перед программистами встанет задача написать функцию перемножения матриц, то 99.9% из них напишут её примерно так:

void matrixmult1(intsize, double A[][size], double B[][size], double C[][size])

{

doublesum;

for (inti = 0; i< size; i++)

for (int j = 0; j < size; j++) {

sum = 0.0;

for (int k = 0; k < size; k++)

sum += A[i][k]*B[k][j];

       C[i][j] = sum;

}

}

Этом код дословно повторяет математическое определение перемножения матриц. Мы обходим все элементы окончательной матрицы построчно, вычисляя каждый из них один за другим. В коде есть одна неэффективность, это выражение B[k][j] в самом внутреннем цикле. Мы обходим матрицу B по стобцам. Казалось бы, ничего с этим не поделаешь и придётся смириться. Но выход есть. Можно переписать то же вычисление по другому:

void matrixmult2(int size, double A[][size], double B[][size], double C[][size])

{

double r;

for (inti = 0; i< size; i++)

for (int k = 0; k < size; k++) {

       r = A[i][k];

for (int j = 0; j < size; j++)

C[i][j] += r*B[k][j];

   }

}
Теперь функция выглядит очень странно. Но она делает абсолютно то же самое. Только мы не вычисляем каждый элемент окончательной матрицы за раз, мы как бы вычисляем элементы частично на каждой итерации. Но ключевое свойство этого кода в том, что во внутреннем цикле мы обходим обе матрицы построчно. На машине с Core i7 Haswell вторая функция работает в 12 раз быстрее для больших матриц. Нужно быть действительно мудрым программистом, чтобы организовать код таким образом.

Блокинг

Существует техника, которая называется блокинг. Допустим вам надо выполнить вычисление над большим объёмом данных, которые все не помещаются в кэше высокого уровня. Вы разбиваете эти данные на блоки меньшего размера, каждый из которых помещается в кэше. Выполняете вычисления над этими блоками по отдельности и потом объёдиняете результат.

Можно продемонстрировать это на примере. Допустим у вас есть ориентированный граф, представленный в виде матрицы смежности. Это такая квадратная матрица из нулей и единиц, так что если элемент матрицы с индексом (i, j) равен единице, то существует грань от вершины графа i к вершине j. Вы хотите превратить этот ориентированный граф внеориентированный. То есть, если есть грань (i, j), то должна появиться противоположная грань (j, i). Обратите внимание, что если представить матрицу визуально, то элементы (i, j) и (j, i) являются симметричными относительно диагонали. Эту трансформацию нетрудно осуществить в коде:

void convert1(int size, int G[][size])

{

for (inti = 0; i< size; i++)

for (int j = 0; j < size; j++)

G[i][j] = G[i][j] | G[j][i];

}

Блокинг появляется естественным образом. Представьте перед собой большую квадратную матрицу. Теперь иссеките эту матрицу горизонтальными и вертикальными линиями, чтобы разбить её, скажем, на 16 равных блока (четыре строки и четыре столбца). Выберите два любых симметричных блока. Обратите внимание, что все элементы в одном блоке имеют свои симметричные элементы в другом блоке. Это наводит на мысль, что ту же операцию можно совершать над этими блоками поочерёдно. В этом случае на каждом этапе мы будем работать только с двумя блоками. Если блоки сделать достаточно маленького размера, то они поместятся в кэше высокого уровня. Выразимэтуидеювкоде:

void convert2(int size, int G[][size])

{

intblock_size = size / 12; // разбить на 12*12 блоков

                              // представим, что делится без остатка

for (int ii = 0; ii < size; ii += block_size) {

for (intjj = 0; jj< size; jj += block_size) {

inti_start = ii; // индекс i для блока принимает значения [ii, ii + block_size)

inti_end = ii + block_size;

intj_start = jj; // индекс j дляблокапринимаетзначения [jj, jj + block_size)

intj_end = jj + block_size;

       // обходимблок

for (inti = i_start; i<i_end; i++)

for (int j = j_start; j <j_end; j++)

               G[i][j] = G[i][j] | G[j][i];

   }

}

}

Нужно заметить, что блокинг не улучшает производительность на системах с мощными процессорами, которые хорошо делают предвыборку. На системах, которые не делают предвыборки, блокинг может сильно увеличить производительность.

На машине с процессором Core i7 Haswell вторая функция не выполняется быстрее. На машине с более простым процессором Pentium 2117U вторая функция выполняется в 2 раза быстрее. На машинах, которые не выполняют предвыборку, производительность улучшилась бы ещё сильнее.

Какие алгоритмы быстрее

Все знают из курсов по алгоритмам, что нужно выбирать хорошие алгоритмы с наименьшей сложностью и избегать плохих алгоритмов с высокой сложностью. Но эти сложности оценивают выполнение алгоритма на теоретической машине, созданной нашей мыслью. На реальных машинах теоретически плохой алгоритм может выполнятся быстрее теоретически хорошего. Вспомните, что получить данные из оперативной памяти занимает 200 тактов, а из кэша первого уровня 4 такта — это в 50 раз быстрее. Если хороший алгоритм часто трогает память, а плохой алгоритм размещает свои данные в кэше, хороший алгоритм может выполняться медленнее плохого. Также хороший алгоритм может выполняться на процессоре хуже, чем плохой. К примеру, хороший алгоритм вносит зависимость данных и не может загрузить конвеер процессора. А плохой алгоритм лишён этой проблемы и на каждом такте отправляет в конвеер новую инструкцию. Иными словами, сложность алгоритма это ещё не всё. Как алгоритм будем выполняться на конкретной машине с конкретными данными имеет значение.

Представим, что вам нужно реализовать очередь целых чисел, и новые элементы могут добавляться в любую позицию очереди. Вы выбираете между двумя реализациями: массив и связный список. Чтобы добавить элемент в середину массива, нужно сдвинуть вправо половину массива, что занимает линейное время. Чтобы добавить элемент в середину списка, нужно дойти по списку до середины, что также занимает линейное время. Вы думаете, что раз сложности у них одинаковые, то лучше выбрать список. Тем более у списка есть одно хорошее свойство. Список может расти без ограничения, а массив придётся расширять, когда он заполнится.

Допустим, очередь длиной 1000 элементов мы реализовали обоими способами. И нам нужно вставить элемент в середину очереди. Элементы списка хаотично разбросаны по памяти, поэтому чтобы обойти 500 элементов, нам понадобится 500*200=100'000 тактов. Массив расположен в памяти последовательно, что позволит нам наслаждаться скоростью кэша первого уровня. Используя несколько оптимизаций, мы можем двигать элементы массива, тратя 1-4 такта на элемент. Мы сдвинем половину массива максимум за 500*4=2000 тактов. То есть быстрее в 50 раз.

Если в предыдущем примере все добавления были бы в начало очереди, реализация со связным списком была бы более эффективной. Если какая-то доля добавлений была бы куда-то в середину очереди, реализация в виде массива могла бы стать лучшим выбором. Мы бы тратили такты на одних операциях и экономили такты на других. И в итоге могли бы остаться в выигрыше.Система памяти организована в виде иерархии устройств хранения с маленькими и быстрыми устройствами вверху иерархии и большими и медленными устройствами внизу. Программы с хорошей локальностью работают с данными из кэшей процессора. Программы с плохой локальностью работают с данными из относительно медленной оперативной памяти.

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

В частности, рекомендуются следующие техники:

· Сконцентрируйте ваше внимание на внутренних циклах. Именно там происходит наибольший объём вычислений и обращений к памяти.

· Постарайтесь максимизировать пространственную локальность, читая объекты из памяти последовательно, в том порядке, в котором они в ней расположены.

· Постарайтесь максимизировать временную локальность, используя объекты данных как можно чаще после того, как они были прочитаны из памяти.

Заключение

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

В настоящее время разработано много видов оперативной памяти: высокоскоростной и более медленной, дорогой и подешевле. Какую память следует устанавливать на компьютер, должен решать сам пользователь, в зависимости от того, какие возможности ему нужны. Но следует помнить, что быстроразвивающаяся компьютерная отрасль, в том числе программное обеспечение, предъявляют все большие требования к компьютерам, в том числе и к оперативной памяти.

Итак, подведём итоги сравнения оперативной памяти:

· cамая быстродействующая на сегодняшний момент ОП, а также самая дорогостоящая - Rambus, её частота работы эквивалентна 800 MHz;

· в связи с дороговизной память типа SRAM используется, в основном только как КЭШ L1 и L2.

Список использованных источников

1. Скотт Мюллер «Модернизация и ремонт ПК», 11-е издание, издательский дом «Вильямс», М 2000г. 503-504,504-508,512-513,513-514,520-521,547-548

2. https://habrahabr.ru/post/312078/ - Оптимизация кода: память

3. https://ru.wikipedia.org/wiki/%D0%9A%D1%8D%D1%88_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D1%80%D0%B0 - Кэш микропроцессора