Ассоциативная кэш память. Экспериментальное определение характеристик кэш-памяти

· кэш с прямым отображением (размещением);

· полностью ассоциативный кэш;

· множественный ассоциативный кэш или частично-ассоциативный.

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

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

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

Отображение секторов ОП в кэш-памяти.

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

Иерархическая модель кэш-памяти

Как правило, кэш-память имеет многоуровневую архитектуру. Например, в компьютере с 32 Кбайт внутренней (в ядре ЦП) и 1 Мбайт внешней (в корпусе ЦП или на системной плате) кэш-памяти первая будет считаться кэш-памятью 1-го уровня (L1), а вторая - кэш-памятью 2-го уровня (L2). В современных серверных системах количество уровней кэш-памяти может доходить до четырех, хотя наиболее часто используется двух- или трехуровневая схема.

В некоторых процессорных архитектурах кэш-память 1-го уровня разделена на кэш команд (InstructionCache, I-cache) и кэш данных (DataCache, D-cache), причем необязательно одинаковых размеров. С точки зрения схемотехники проще и дешевле проектировать раздельные I-cache и D-cache: выборку команд проводит I-box, а выборку данных - Е-box и F-box, хотя в обоих случаях задействуются А-box и С-box. Все эти блоки велики, и обеспечить им одновременный и быстрый доступ к одному кэшу проблематично. Кроме того, это неизбежно потребовало бы увеличения количества портов доступа, что также усложняет задачу проектирования.

Так как I-cache и D-cache должны обеспечивать очень низкие задержки при доступе (это справедливо для любого кэша L1), приходится жертвовать их объемом - обычно он составляет от 16 до 32 Кбайт. Ведь чем меньше размер кэша, тем легче добиться низких задержек при доступе.

Кэш-память 2-го уровня, как правило, унифицирована, т. е. может содержать как команды, так и данные. Если она встроена в ядро ЦП, то говорят о S-cache (SecondaryCache, вторичный кэш), в противном случае - о B-cache (BackupCache, резервный кэш). В современных серверных ЦП объем S-cache составляет от одного до нескольких мегабайт, aB-cache - до 64 Мбайт. Если дизайн ЦП предусматривает наличие встроенной кэш-памяти 3-го уровня, то ее именуют T-cache (TernaryCache, третичный кэш). Как правило, каждый последующий уровень кэш-памяти медленнее, но больше предыдущего по объему. Если в системе присутствует B-cache (как последний уровень модели кэш-памяти), то он может контролироваться как ЦП, так и набором системной логики.

Если в момент выполнения некоторой команды в регистрах не окажется данных для нее, то они будут затребованы из ближайшего уровня кэш-памяти, т. е. из D-cache. В случае их отсутствия в D-Cache запрос направляется в S-cache и т. д. В худшем случае данные будут доставлены непосредственно из памяти. Впрочем, возможен и еще более печальный вариант, когда подсистема управления виртуальной памятью операционной системы (ОС) успевает вытеснить их в файл подкачки на жесткий диск. В случае доставки из оперативной памяти потери времени на получение нужных данных могут составлять от десятков до сотен тактов ЦП, а в случае нахождения данных на жестком диске речь уже может идти о миллионах тактов.

Ассоциативность кэш-памяти

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

Выбор места может проводиться по различным алгоритмам, среди которых чаще всего используются принципы замещения LRU (LeastRecentlyUsed, замещается запись, запрошенная в последний раз наиболее давно) и LFU (LeastFrequentlyUsed, запись, наименее часто запрашиваемая), хотя существуют и модификации этих принципов. Например, полностью ассоциативная кэшпамять (fullyassociative), в которой информация, находящаяся по произвольному адресу в оперативной памяти, может быть размещена в произвольной строке. Другой вариант - прямое отображение (directmapping), при котором информация, которая находится по произвольному адресу в оперативной памяти, может быть размещена только в одном месте кэш-памяти. Естественно, этот вариант обеспечивает наибольшее быстродействие, так как при проверке наличия информации контроллеру придется "заглянуть" лишь в одну строку кэша, но и наименее эффективен, поскольку при записи контроллер не будет выбирать "оптимальное" место. При одинаковом объеме кэша схема с полной ассоциативностью будет наименее быстрой, но наиболее эффективной.

Полностью ассоциативный кэш встречается на практике, но, как правило, у него очень небольшой объем. Например, в ЦП Cyrix 6x86 использовалось 256 байт такого кэша для команд перед унифицированным 16-или 64-Кбайт кэшем L1. Часто полноассоциативную схему применяют при проектировании TLB (о них будет рассказано ниже), кэшей адресов переходов, буферов чтения-записи и т. д. Как правило, уровни ассоциативности I-cache и D-cache довольно низки (до четырех каналов) - их увеличение нецелесообразно, поскольку приводит к увеличению задержек доступа и в итоге негативно отражается на производительности. В качестве некоторой компенсации увеличивают ассоциативность S-cache (обычно до 16 каналов), так как задержки при доступе к этому кэшу неважны. Например, согласно результатам исследований часто используемых целочисленных задач, у IntelPentiumIII 16 Кбайт четырехканального D-cache было достаточно для покрытия около 93% запросов, а 16-Кбайт четырехканального I-cache - 99% запросов.

Размер строки и тега кэш-памяти

Немаловажная характеристика кэш-памяти - размер строки. Как правило, на одну строку полагается одна запись адреса (так называемый тег), которая указывает, какому адресу в оперативной памяти соответствует данная линия. Очевидно, что нумерация отдельных байтов нецелесообразна, поскольку в этом случае объем служебной информации в кэше в несколько раз превысит объем самих данных. Поэтому один тег обычно полагается на одну строку, размер которой обычно 32 или 64 байта (реально существующий максимум 1024 байта), и эквивалентен четырем (иногда восьми) разрядностям системной шины данных. Кроме того, каждая строка кэш-памяти сопровождается некоторой информацией для обеспечения отказоустойчивости: одним или несколькими битами контроля четности (parity) или восемью и более байтами обнаружения и коррекции ошибок (ЕСС, ErrorCheckingandCorrecting), хотя в массовых решениях часто не используют ни того, ни другого.

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

Stag=log2(Smem*A/Scache),

где Stag - размер одного тега кэш-памяти, в битах; Smem - максимальный кэшируемый объем оперативной памяти, в байтах; Scache - объем кэш-памяти, в байтах; А - ассоциативность кэш-памяти, в каналах.

Отсюда следует, что для системы с 1-Гбайт оперативной памятью и 1-Мбайт кэш-памятью с двухканальной ассоциативностью потребуется 11 бит для каждого тега. Примечательно, что собственно размер строки кэш-памяти никак не влияет на размер тега, но обратно пропорционально влияет на количество тегов. Следует понимать, что размер строки кэш-памяти не имеет смысла делать меньше разрядности системной шины данных, но многократное увеличение размера приведет к чрезмерному засорению кэш-памяти ненужной информацией и излишней нагрузке на системную шину и шину памяти. Кроме того, максимально кэшируемый объем кэш-памяти не обязан соответствовать максимально возможному устанавливаемому объему оперативной памяти в системе. Если возникнет ситуация, когда оперативной памяти окажется больше, чем может быть кэшировано, то в кэш-памяти будет присутствовать информация только из нижнего сегмента оперативной памяти. Именно такой была ситуация с платформой Socket7/Super7. Наборы микросхем для этой платформы позволяли использовать большие объемы оперативной памяти (от 256 Мбайт до 1 Гбайт), в то время как кэшируемый объем часто был ограничен первыми 64 Мбайт (речь идет о B-cache, находящемся на системной плате) по причине использования дешевых 8-бит микросхем теговой SRAM (2 бита из которых резервировалось под указатели действительности и измененности строки). Это приводило к ощутимому падению производительности.

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

3.3.1 Ассоциативность

Можно было бы реализовать кэш-память, в которой каждая кэш-строка может хранить копию любой ячейки памяти. Это называется полностью ассоциативной кэш-памятью (fully associative cache ). Чтобы получить доступ к кэш-строке, ядро процессора должно было бы сравнить теги всех до единой кэш-строк с тегом запрашиваемого адреса. Тег должен будет хранить весь адрес, который не будет указываться смещение в кэш-строке (это означает, что значение S, показанное на рисунке в разделе 3.2, будет равно нулю).

Есть кэш-память, которая реализована подобным образом, но взглянуть на размеры кэш-памяти L2, используемой в настоящее время, то видно, что это непрактично. Учтите, что 4 Мб кэш-памяти с кэш-строками размером в 64Б должна иметь 65 536 записей. Чтобы получить адекватную производительность, логические схемы кэш-памяти должны быть в состоянии в течение нескольких циклов выбрать из всех этих записей ту, которая соответствует заданному тегу. Затраты на реализацию такой схемы будут огромными.

Рис.3.5: Схематическое изображение полностью ассоциативной кэш-памяти

Для каждой кэш-строки требуется, чтобы компаратор выполнил сравнение тега большого размера (заметьте, S равно нулю). Буква, стоящая рядом с каждым соединением, обозначает ширину соединения в битах. Если ничего не указано, то ширина соединения равна одному биту. Каждый компаратор должен сравнивать два значения, ширина каждого из которых равна Т бит. Затем, исходя из результата, должно выбираться и стать доступным содержимое соответствующей кэш-строки. Для этого потребуется объединить столько наборов линий данных О, сколько есть сегментов кэш-памяти (cache buckets). Число транзисторов, необходимых для реализации одного компаратора будет большим в частности из-за того, что компаратор должен работать очень быстро. Итеративный компаратор использовать нельзя. Единственный способ сэкономить на количестве компараторов, это снизить их число с помощью итеративного сравнения тегов. Это не подходит по той же самой причине, по которой не подходят итеративные компараторы: на это потребуется слишком много времени.

Полностью ассоциативная кэш-память практична для кэш-памяти малого размера (например, кэш-память TLB в некоторых процессорах Intel является полностью ассоциативной), но эта кэш-память должна быть небольшой - действительно небольшой. Речь идет максимум о нескольких десятках записей.

Для кэш-памяти L1i, L1d и кэш-памяти более высокого уровня необходим другой подход. Все, что можно сделать, это ограничить поиск. В самом крайнем случае каждый тег отображается точно в одну кэш-запись. Расчет прост: для кэш-памяти 4MB/64B с 65 536 записями мы можем напрямую обращаться к каждому элементу и использовать для этого с 6-го по 21-й биты адреса (16 битов). Младшие 6 битов являются индексом кэш-строки.

Рис.3.6: Схематическое изображение кэш-памяти с прямым отображением

Как видно из рисунка 3.6 реализация такой кэш-памяти с прямым отображением (direct-mapped cache ) может быть быстрой и простой. Для нее требуется только один компаратор, один мультиплексор (на этой схеме приведены два, поскольку тег и данные разделены, но это не является строгим конструктивным требованием) и некоторая логическая схема для выбора контента, содержащего действительно допустимые кэш-строки. Компаратор сложный из-за требований, касающихся скорости, но теперь он только один; в результате можно потратить больше усилий, чтобы сделать его более быстрым. Реальная сложность такого подхода заключена в мультиплексорах. Количество транзисторов в простом мультиплексоре растет по закону O(log N), где N является количеством кэш-строк. Это приемлемо, но может получиться медленный мультиплексор, и в этом случае скорость можно увеличить, если потратиться на транзисторы в мультиплексорах и для увеличения скорости распараллелить часть работы. Общее количество транзисторов будет расти медленное в сравнении с ростом размера кэш-памяти, что делает это решение очень привлекательным. Но у такого подхода есть недостаток: он работает только в случае, если адреса, используемые в программе, равномерно распределены относительно битов, используемых для прямого отображения. Если это не так, и это обычно бывает, некоторые кэш-записи используются активно и, поэтому, неоднократно высвобождаются, в то время как другие практически вообще не используются, либо остаются пустыми.

Рис.3.7: Схематическое изображение кэш-памяти с множественной ассоциативностью

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

Результатом является кэш-память, которая достаточно устойчива к промахам из-за неудачного или преднамеренного выбора адресов с одними и теми же номерами наборов в одно и то же время, а размер кэш-памяти не ограничен количеством компараторов, которые могут работать параллельно. Если кэш-память увеличивается (смотрите рисунок), то увеличивается только количество столбцов, а не количество строк. Число строк увеличивается только в том случае, если повышается ассоциативность кэш-памяти. Сегодня процессоры для кэш-памяти L2 используют уровни ассоциативности до 16 и выше. Для кэш-памяти L1 обычно используется уровень, равный 8.

Таблица 3.1: Влияние размера кэш-памяти, ассоциативности и размера кэш-строки

Если у нас кэш-память 4MB/64B и 8-канальная ассоциативность, то в кэш-памяти у нас будет 8192 наборов и для адресации кэш-наборов потребуется только 13 битов тега. Чтобы определить, какая из записей (если таковая имеется) содержит в кэш-наборе адресуемую кэш-строку, потребуется сравнить 8 тегов. Это можно сделать за очень короткое время. Как видно из практики, в этом смысл есть.

В таблице 3.1 показано количество промахов кэш-памяти L2 для некоторой программы (в данном случае — для компилятора gcc, который, по мнению разработчиков ядра Linux, является наиболее важным бенчмарком) при изменении размера кэш-памяти, размера кэш-строки, а также значения множественной ассоциативности. В разделе 7.2 мы познакомимся с инструментальным средством, предназначенным для моделирования кэш-памяти, которое необходимо для этого теста.

Просто, если это еще не очевидно, взаимосвязь всех этих значений в том, что размер кэш-памяти равен

размер кэш-строки х ассоциативность х количество множеств

Отображение адресов в кэш-память вычисляется как

O = log2 от размера кэш-строки

S = log2 от числа наборов

согласно рисунку в разделе 3.2.

Рис.3.8: Размер кэш-памяти и уровень ассоциативности (CL=32)

Рис. 3.8 делает данные таблицы более понятными. На рисунке приведены данные для кэш-строки фиксированного размера, равного 32 байта. Если посмотреть на цифры для заданного размера кэш-памяти, то видно, что ассоциативность действительно может существенно помочь сократить число промахов кэш-памяти. Для кэш-памяти размером 8 МБ при переходе от прямого отображения на кэш-память с 2-канальной ассоциативностью экономится почти 44% кэш-памяти. В случае, если используется кэш-память со множественной ассоциативностью, то процессор может хранить в кэш-памяти рабочий набор большего размера, чем в случае кэш-памяти с прямым отображением.

В литературе иногда можно прочитать, что введение ассоциативности имеет тот же самый эффект, как удвоение размера кэш-памяти. Это, как это видно для случая перехода от кэш-памяти размером 4 МБ к кэш-памяти размером 8 МБ, верно в некоторых крайних случаях. Но это, конечно, не верно при последующем увеличении ассоциативности. Как видно из данных, последующее увеличение ассоциативности дает существенно меньший выигрыш. Нам, однако, не следует абсолютно не учитывать этот факт. В программе нашего примера пик использования памяти равен 5,6 MB. Так что при размере кэш-памяти в 8 Мб, что те же самые кэш-наборы будут использоваться многократно (более, чем дважды). С увеличением рабочего набора экономия может увеличиться, поскольку, как мы видим, при меньших размерах кэш-памяти преимущество от использования ассоциативности будет больше.

В целом, увеличение ассоциативность кэш-памяти выше 8, как кажется, дает слабый эффект при одном потоке рабочей нагрузки. С появлением многоядерных процессоров, которые используют общую кэш-память L2, ситуация меняется. Теперь у вас в основном есть две программы, которые обращаются к одной и той же кэш-памяти, в результате чего на практике эффект от использования ассоциативности должен увеличиться вдвое (или в четыре раза для четырехядерных процессоров). Таким образом, можно ожидать, что с увеличением числа ядер, ассоциативность общей кэш-памяти должна расти. Как это станет делать невозможным (16-канальную ассоциативность реализовывать уже трудно) разработчики процессоров начнут использовать общую кэш-память уровня L3 и далее, в то время как кэш-память уровня L2 будет, потенциально, совместно использоваться некоторым подмножеством ядер.

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

Как уже упоминалось выше, размер рабочего набора в его пиковом значении равен 5,6 Мб. Это значение не позволяет нам рассчитать размер памяти, который бы принес максимальную выгоду, но позволяет оценить этот размер. Проблема в том, что вся память используется не непрерывно и, следовательно, у нас есть конфликты даже при наличии 16M кэш-памяти и рабочего набора, размер которого равен 5,6M (вспомните преимущество 2-канальной ассоциативной кэш-памяти размером в 16 МБ над версией с прямым отображением). Но можно с уверенностью сказать, что при такой нагрузке преимущество кэш-памяти размером в 32 МБ будет несущественным. Однако кто сказал, что рабочий набор должен оставаться неизменным? С течением времени рабочие нагрузки растут и то же самое должно касаться размера кэш-памяти. Когда покупаются машины и принимается решение, за какой размер кэш-памяти требуется заплатить, стоит измерить размер рабочего набора. Почему это важно, можно увидеть на рис. 3.10.

Рис.3.9: Размещение памяти, используемой при тестировании

Запускается два типа тестов. В первом тесте элементы обрабатываются последовательно. В тестовой программе используется указатель n , но элементы массива связаны друг с другом, так что они обходятся в том порядке, в котором они находятся в памяти. Этот вариант показан в нижней части рис.3.9. Есть одна обратная ссылка, идущая от последнего элемента. Во втором тесте (верхняя часть рисунка) элементы массива обходятся в произвольном порядке. В обоих случаях элементы массива образуют циклический односвязный список.

Уровни КЭШ.

Микропроцессор, как правило, имеет несколько уровней КЭШ -а (processor cache memory, кеш ). Первый (L1 & L1i (кэш дляинструкций )), второй (L2 ) и третий (L3 ) (на серверных решениях бывает и больше).

Чем ниже по рангу кэш, тем медленней скорость его работы.

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

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

Кэш бывает разделяемый (на каждое ядро) и общий (объединённый).

Бесспорно, общий кэш работает быстрее . Так как в разделённом кэше , если одному ядру требуется информация, которая до этого была просчитана другим ядром и находится в его КЭШе , то ей придётся проходить по гораздо более медленной оперативной памяти. Иногда быстрее посчитать снова, что процессор и делает. А в случае с общим кэшем , мог бы простовзять данные из общего КЭШа .

К примеру, процессорIntel C2D q9550 состоит из двух Intel C2D E8400 .

Четыре ядра будут медленнее не только из-за использования общих ресурсов шины. Кэш L2 теперь не общий и ему приходится искать обходные пути, если к примеру ядру 1 понадобилась информация обработанная ядром 3 . Этоувеличивает время обработки информации, следовательно уменьшает быстродействие.

Кэш -память называется полностью ассоциативной , если каждая строка ОЗУ может располагаться в любом месте кэш -памяти.

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

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

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

1. LRU - замещается строка, к которой дольше всего не было обращений;

2. FIFO - замещается самая давняя по пребыванию в кэш-памяти строка;

3. Random - замещение проходит случайным образом.

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

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

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

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

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

11. Микропроцессор (МП). Определение. Выполняемые функции. Основные параметры. Типы МП в зависимости от набора системы команд (CISC, RISC, VLIW).

Микропроцессор - программно-управляемое универсальное устройство для цифровой обработки дискретной и (или) аналоговой информации и управления процессом этой обработки, построенное на одной или неск. больших интегральных схемах (БИС)

Функции МП.

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

Таким образом, основные функции любого процессора следующие:

1) выборка (чтение) выполняемых команд;

2) ввод (чтение) данных из памяти или устройства ввода/вывода;

3) вывод (запись) данных в память или в устройства ввода/вывода;

4) обработка данных (операндов), в том числе арифметические операции над ними;

5) адресация памяти, то есть задание адреса памяти, с которым будет производиться обмен;

6) обработка прерываний и режима прямого доступа.

Параметры

Основные характеристики микропроцессора

Микропроцессоры отличаются друг от друга двумя главными характеристиками: типом (моделью) и тактовой частотой. Одинаковые модели микропроцессоров могут иметь разную тактовую частоту - чем выше тактовая частота, тем выше производительность и цена микропроцессора. Тактовая частота указывает, сколько элементарных операций (тактов) микропроцессор выполняет в одну секунду. Тактовая частота измеряется в мегагерцах (МГц). Следует заметить, что разные модели микропроцессоров выполняют одни и те же операции за разное число тактов. Чем выше модель микропроцессора, тем меньше тактов требуется для выполнения одних и тех же операций.

Рассмотрим характеристики процессоров более подробно.

1. Тип микpопpоцессоpа.

Тип установленного в компьютеpе микpопpоцессоpа является главным фактоpом, опpеделяющим облик ПК. Именно от него зависят вычислительные возможности компьютеpа. В зависимости от типа используемого микpопpоцессоpа и опpеделенных им аpхитектуpных особенностей компьютеpа pазличают пять классов ПК:

Компьютеры класса XT;

Компьютеры класса AT;

Компьютеpы класса 386;

Компьютеpы класса 486;

Компьютеpы класса Pentium.

2. Тактовая частота микpопpоцессоpа - указывает, сколько элементарных операций (тактов) микропроцессор выполняет за одну секунду.

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

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

3. Быстродействие микропроцессора - это число элементарных операций, выполняемых микропроцессором в единицу времени (операции/секунда).

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

Разрядность МП обозначается m/n/k/ и включает: m - разрядность внутренних регистров, определяет принадлежность к тому или иному классу процессоров; n - разрядность шины данных, определяет скорость передачи информации; k - разрядность шины адреса, определяет размер адресного пространства. Например, МП i8088 характеризуется значениями m/n/k=16/8/20.

5. Архитектура микропроцессора. (Типы Микропроцессоров)

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

В соответствии с архитектурными особенностями, определяющими свойства системы команд, различают:

Микропроцессоры типа CISC с полным набором системы команд (наиболее большой набор команд, универсальные МП, заменяют системы целиком);

Микропроцессоры типа RISC с усеченным набором системы команд (должен выполнять быстро количество операций (всего 120 команд) Например: управление периферийными уст-вами);

Микропроцессоры типа VLIW со сверхбольшим командным словом ((very long instruction) – архитектуры для расчет статистических параметров. Их задача – огромные расчёты);

Микропроцессоры типа MISC с минимальным набором системы команд и весьма высоким быстродействием и др.

12. Серверные микропроцессоры. Требования к характеристикам. Отличительные особенности.

Серверные МП – быстрое выполнение операций. Быстрое выполнение задач. Адресовать большое кол-во ОП, должен выполнять любые задачи.

Например, XEON, AMD Optiron, эти процессоры не экономят электроэнергию. У них нет хорошего графического ядра.
Характеристики:
-частота
-чипсет
-многопроцессорная система

Архитектура кэш-памяти.

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

Кэш-память с прямым отображением.

В кэш-памяти прямого отображения адрес памяти, по которому происходит обра-щение, однозначно определяет строку кэша, в которой может находиться требуе-мый блок. Принцип работы такого кэша поясним на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт - типичный кэш системной платы для Pentium. Структуру кэш-памяти в такой системе иллюстрирует рис. 1. Кэшируемая основная память условно разбивается на страницы (в данном случае по 256 Кбайт), размер которых совпадает с размером кэш-памяти (256 Кбайт). Кэш--память (и, условно - страницы основной памяти) делится на строки (256 Кбайт/ 32 байт - 8 К строк). Архитектура прямого отображения подразумевает, что каж-дая строка кэша может отображать из любой страницы кэшируемой памяти толь-ко соответствующую ей строку. Поскольку объем основной памяти много больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса, которую называют смещением внутри страницы (0 - множество, 1-множество, 2-ьножество … N-множество 32-х байтных блоков). Одна строка в определен-ный момент может содержать копию только одного из этих блоков. Номер строки является адресом строки в кэш-памяти, а тег несет ин-формацию о том, какой именно блок занимает данную строку (тег это старшая часть адреса, выставленного процессором при обращении в память или, иначе говоря, номер страницы). Память тегов должна иметь количество ячеек, равное количеству строк кэша, а ее разрядность должна быть достаточной, чтобы вместить старшие биты адреса кэшируемой памяти, не попавшие на шину адреса кэш-памяти. Кроме адресной части тега, с каждой строкой кэша связаны биты признаков действительности и модифицированности данных. В начале каждого обращения к оперативной памяти контроллер кэш-памяти, первым делом, счи-тывает ячейку памяти тэгов с адресом строки, определяемым разрядами А17-А5, сравнивает содержимое этой строки памяти тэгов с разрядами А25-А18 адреса памяти, выставленного процессором, и анализирует признак действительности.

Рис. 1. Кэш с прямым отображением.

Этот анализ выполняется в специальном цикле слежения, который иногда называют циклом запроса. Если в результате анализа выясняется, что требуемого блока нет в кэше, генерируется (или продолжается) цикл обращения к основной памяти (кэш-промах). В случае попадания запрос обслуживается кэш--памятью. В случае промаха после считывания из основной памяти приемником ин-формации новые данные помещаются в строку кэша (если она чистая), а в ее тег помещаются старшие биты адреса и устанавливается признак действительности данных. Независимо от объема затребованных данных в кэш из основной памя-ти строка переписывается вся целиком (поскольку признак действительности относится ко всем ее байтам). Если контроллер кэша реализует упреждающее считывание, то в последующие свободные циклы шины обновляется также следующая строка (если она была чистой). Чтение «про запас» позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки. Такой кэш имеет самую простую аппаратную реализацию и применяется во вторич-ном кэше большинства системных плат. Однако ему присущ серьезный недоста-ток. Если в процессе выполнения программы процессор поочередно будет обращаться по одному и тому же адресу строки, но разными или циклически изменяющимися номерами тэгов, то постоянно будут фиксироваться кэш-промахи и кэш-память вместо ускорения будет вносить замедление в обмен с памятью. Переклю-чение страниц в многозадачных операционных системах (ОС) также снижает количество кэш-попаданий, что отражается на производительности системы. Увеличение размера кэша при сохранении архитектуры прямого отображения даст не очень существенный эф-фект, поскольку разные задачи будут претендовать на одни и те же строки кэша. Не увеличивая объема кэша, .можно повысить эффективность кэширования изме-нением его структуры, о чем пойдет речь ниже.

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

Рис. 2. Секторированный кэш прямого отображения

Наборно-ассоциативный (частично-ассоциативный) кэш.

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

Рис. 3. Четырехканальный наборно-ассоциативный кэш

Канди-датом на замещение обычно выбирается строка, к которой дольше всего не обраща-лись (алгоритм LRU - Least Recently Used). При относительно большом количе-стве каналов (строк в наборе) прибегают к некоторому упрощению - алгоритм Pseudo-LRU для четырех строк позволяет при-нимать решения, используя всего 3 бита.

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

Ассоциативный кэш.

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

Рис. 4. Полностью ассоциативная кэш-память.

Адреса кэшированного блока, за вычетом битов, определяющих положение (смещение) данных в строке, хранятся в памяти тегов. В такой архитектуре (рис. 4) для определения наличия затребованных данных в кэш-памяти требуется сравнение со старшей частью ад-реса тегов всех строк памяти тэгов, а не одной или нескольких, как при прямом отображении или наборно-ассоциативной архитектуре. Последовательный пере-бор ячеек памяти тегов отпадает. (на это требуется слишком много времени), поэтому остается параллельное сравнение тэгов всех ячеек, а это является сложной аппаратной за-дачей, которая приемлемо решаема только для небольших объемов первичного кэша (процессор М2 Cyrix).

За счет чего же мы наблюдаем постоянный рост производительности однопоточных программ? В данный момент мы находимся на той ступени развития микропроцессорных технологий, когда прирост скорости работы однопоточных приложений зависит только от памяти. Количество ядер растет, но частота зафиксировалась в пределах 4 ГГц и не дает прироста производительности.

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

Как же определить характеристики кэша автоматический? (естественно cpuinfo распарсить не считается, хотя-бы потому-что в конечном итоге мы бы хотели получить алгоритм, который можно без труда реализовать в других ОС. Удобно, не правда ли?) Именно этим мы сейчас и займемся.

Немного теории

Кэш с прямым отображением (direct mapping cache)

Ассоциативный кэш (fully associative cache)

Множественно-ассоциативный кэш

LRU - вытеснение самой «долго не использованной» строки, кэш памяти.

Идея

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

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

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

Ассоциативный кэш

Как только размер данных превышает размер кэш-памяти,
полностью ассоциативный кэш «промахивается» при каждом обращении к памяти.

Прямой кэш

Рассмотрим разные размеры строк. - показывает максимальное количество промахов, которое потратит процессор для доступа к элементам массива при следующем проходе по строке.

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

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

Если-же говорить о памяти - то самая быстрая это кэш, следом идет оперативная, самая медленная это swap, про него мы в дальнейшем говорить не будем. В свою очередь у разных уровней кэша (как правило сегодня процессоры имеют 2-3 уровня кэша) разная скорость отклика памяти: чем больше уровень, тем меньше скорость отклика. И поэтому, если строка помещается в первый уровень кэша, (который кстати полностью ассоциативный) время отклика будет меньше, чем у строки значительно превышающей размеры кэша первого уровня. По-этому на графике времени отклика памяти от размеров строки будет несколько плато - плато* отклика памяти, и плато вызванные различными уровнями кэша.

*Плато функции - { i:x, f(xi) - f(xi+1) < eps: eps → 0 }

Приступим к реализации

Быстро написан код, обычный проход по строкам разной длины, меньше 10мб, выполняющийся многократно. (Будем приводить небольшие куски программы, несущие смысловую нагрузку).

For (i = 0; i < 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }

Смотрим на график - и видим одну большую ступеньку. Но ведь в теории получается все, просто замечательно. Стало быть нужно понять: из за чего это происходит? И как это исправить?

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

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

Длина рандомизованного массива должна быть сопоставимой с длиной основной строки, чтобы избавиться от большой гранулярности обращений, так же длина массива не должна быть степенью двойки, из-за этого происходили «наложения» - следствием чего могут - быть выбросы. Лучше всего задать гранулярность константно, в том числе, если гранулярность простое число, то можно избежать эффектов наложений. А длина рандомиованого массива - функция от длинны строки.
for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ random[x] + m ]; } } }

После чего мы удивили столь долгожданную «картинку», о которой говорили в начале.

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

Листинг файла size.с Linux

#include #include #include #include #define T char #define MAX_S 0x1000000 #define L 101 volatile T A; int m_rand; int main (){ static struct timespec t1, t2; memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &t2); printf ("%g\n",1000000000. * (((t2.tv_sec + t2.tv_nsec * 1.e-9) - (t1.tv_sec + t1.tv_nsec * 1.e-9)))/(double)(L*M*j)); if (k >

Листинг файла size.с Windows

#include #include #include #include #include #include using namespace std; #define T char #define MAX_S 0x1000000 #define L 101 volatile T A; int m_rand; int main (){ LARGE_INTEGER freq; LARGE_INTEGER time1; LARGE_INTEGER time2; QueryPerformanceFrequency(&freq); memset ((void*)A, 0, sizeof (A)); srand(time(NULL)); int v, M; register int i, j, k, m, x; for (k = 1024; k < MAX_S;) { M = k / L; printf("%g\t", (k+M*4)/(1024.*1024)); for (i = 0; i < M; i++) m_rand[i] = L * i; for (i = 0; i < M/4; i++) { j = rand() % M; x = rand() % M; m = m_rand[j]; m_rand[j] = m_rand[i]; m_rand[i] = m; } if (k < 100*1024) j = 1024; else if (k < 300*1024) j = 128; else j = 32; QueryPerformanceCounter(&time1); for (i = 0; i < j; i++) { for (m = 0; m < L; m++) { for (x = 0; x < M; x++){ v = A[ m_rand[x] + m ]; } } } QueryPerformanceCounter(&time2); time2.QuadPart -= time1.QuadPart; double span = (double) time2.QuadPart / freq.QuadPart; printf ("%g\n",1000000000. * span/(double)(L*M*j)); if (k > 100*1024) k += k/16; else k += 4*1024; } return 0; }

В общем- то думаю все понятно, но хотелось бы оговорить несколько моментов.

Массив A объявлен как volatile - эта директива гарантирует нам что к массиву A всегда будут обращения, то-есть их не «вырежут» ни оптимизатор, ни компилятор. Так-же стоит оговорить то что вся вычислительная нагрузка выполняется до замера времени, что позволяет нам, уменьшить фоновое влияние.

Файл переведен в ассемблер на Ubuntu 12.04 и компилятором gcc 4.6 - циклы сохраняются.

Обработка данных

Находим все точки, в которых вторая производная больше нуля (с некоторой погрешностью потому-что вторая производная, помимо того что считается численно, - сильно зашумлена). Задаем функцию зависимости знака второй производной функции от размера кэша. Функция принимает значение 1 в точках, где знак второй производной больше нуля, и ноль, если знак второй производной меньше или равен нулю.

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

Листинг файла data_pr.с
#include #include #include double round (double x) { int mul = 100; if (x > 0) return floor(x * mul + .5) / mul; else return ceil(x * mul - .5) / mul; } float size, time, der_1, der_2; int main(){ size = 0; time = 0; der_1 = 0; der_2 = 0; int i, z = 110; for (i = 1; i < 110; i++) scanf("%g%g", &size[i], &time[i]); for (i = 1; i < z; i++) der_1[i] = (time[i]-time)/(size[i]-size); for (i = 1; i < z; i++) if ((time[i]-time)/(size[i]-size) > 2) der_2[i] = 1; else der_2[i] = 0; //comb for (i = 0; i < z; i++) if (der_2[i] == der_2 && der_2 != der_2[i]) der_2 = der_2[i]; for (i = 0; i < z-4; i++) if (der_2[i] == der_2 && der_2[i] != der_2 && der_2[i] != der_2) { der_2 = der_2[i]; der_2 = der_2[i]; } for (i = 0; i < z-4; i++) if (der_2[i] == der_2 && der_2[i] != der_2 && der_2[i] != der_2 && der_2[i] != der_2) { der_2 = der_2[i]; der_2 = der_2[i]; der_2 = der_2[i]; } // int k = 1; for (i = 0; i < z-4; i++){ if (der_2[i] == 1) printf("L%d = %g\tMb\n", k++, size[i]); while (der_2[i] == 1) i++; } return 0; }

Тесты

• 
  Intel Pentium CPU P6100 @2.00GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt

  L1 = 0.05 Mb
  L2 = 0.2 Mb
  L3 = 2.7 Mb

• Не буду приводить все хорошие тесты, давайте лучше поговорим о «Граблях»

Давайте поговорим о «граблях»

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

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

Хотелось бы услышать ваши предложения, по поводу решения этой проблемы.

Список литературы

• Макаров А.В. Архитектура ЭВМ и Низкоуровневое программирование.
• Ulrich Drepper What every programmer should know about memory