Принцип локальности в компьютерах

Обновлено: 07.07.2024

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

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

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

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

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

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

Маскирование прерываний.

Прерывание – это инициируемый определенным образом процесс, временно переключающий микропроцессор на выполнение другой программы с последующим возобновлением выполнения прерванной программы. Внешние прерывания делятся на:1)маскируемые — прерывания, которые можно запрещать установкой соответствующих битов в регистре маскирования прерываний(IF (Interrupt Flag) – флаг прерывания. Предназначен для так называемого маскирования (запрещения) аппаратных прерываний, то есть прерываний по входу INTR. На обработку прерываний остальных типов флаг IF влияния не оказывает. Если IF=1, микропроцессор обрабатывает внешние прерывания, если IF = 0, микропроцессор игнорирует сигналы на входе INTR).2)немаскируемые — обрабатываются всегда, независимо от запретов на другие прерывания.

Билет №18

1.Методы совмещения операций.

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

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

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

2.Системные и локальные шины.

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

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

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

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

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

Главная задача компьютерной системы – выполнять программы. Программы вместе с данными, к которым они имеют доступ , в процессе выполнения должны (по крайней мере частично) находиться в оперативной памяти . Операционной системе приходится решать задачу распределения памяти между пользовательскими процессами и компонентами ОС. Эта деятельность называется управлением памятью. Таким образом, память ( storage , memory ) является важнейшим ресурсом, требующим тщательного управления. В недавнем прошлом память была самым дорогим ресурсом.

Часть ОС, которая отвечает за управление памятью , называется менеджером памяти.

Физическая организация памяти компьютера

Запоминающие устройства компьютера разделяют, как минимум, на два уровня: основную (главную, оперативную , физическую ) и вторичную (внешнюю) память.

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

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

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

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

Локальность

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

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

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

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

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

Логическая память

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

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

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


Рис. 8.2. Расположение сегментов процессов в памяти компьютера

Некоторые сегменты , описывающие адресное пространство процесса, показаны на рис. 8.2. Более подробная информация о типах сегментов имеется в лекции 10.

Большинство современных ОС поддерживают сегментную организацию памяти. В некоторых архитектурах (Intel, например) сегментация поддерживается оборудованием.

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

Связывание адресов

Итак логические и физические адресные пространства ни по организации, ни по размеру не соответствуют друг другу. Максимальный размер логического адресного пространства обычно определяется разрядностью процессора (например, 2 32 ) и в современных системах значительно превышает размер физического адресного пространства . Следовательно, процессор и ОС должны быть способны отобразить ссылки в коде программы в реальные физические адреса, соответствующие текущему расположению программы в основной памяти . Такое отображение адресов называют трансляцией (привязкой) адреса или связыванием адресов (см. рис. 8.3).

Связывание логического адреса, порожденного оператором программы, с физическим должно быть осуществлено до начала выполнения оператора или в момент его выполнения. Таким образом, привязка инструкций и данных к памяти в принципе может быть сделана на следующих шагах [Silberschatz, 2002].

Что такое локальность и почему ее нет в квантовом мире?

Предположим, зайдя на любимый научный портал, вы обратили внимание на статью с таким заголовком: «Физики обнаружили экстремальное нарушение локального реализма в квантовых гиперграфовых состояниях». Любопытство побуждает разобраться с тем, что же все-таки такое обнаружили физики, но дальше первых четырех слов заголовка продвинуться не так-то просто. Мы решили помочь со следующей парой терминов. На наши вопросы о локальном реализме и квантовой нелокальности ответил Александр Львовский, сотрудник РКЦ и профессор Университета Калгари.

Что такое локальность и принцип локальности в физике?

Эйнштейн ввёл такое понятие — физическая реальность. Это когда результат эксперимента (или вероятности возможных результатов) можно предсказать до проведения эксперимента. Например, мы точно знаем, что если подпрыгнем, то с вероятностью 100% приземлимся обратно, а не останемся парить в воздухе. Нам не нужно специально подпрыгивать, чтобы проверить это, и, соответственно, этот факт относится к категории физической реальности.

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

А что значит нарушение локальности? Как что-то может быть нелокальным, например, в нашем «большом» мире? Чем это плохо, например, в классической механике?

Нарушение локальности — это когда действия, скажем, Алисы на Венере мгновенно и без всякого взаимодействия меняют физическую реальность у Боба на Марсе (к примеру, теперь Боб, подпрыгнув, зависнет в воздухе). Такие вещи неприятны не только потому что они, казалось бы, нарушают теорию относительности, в соответствии с которой никакая информация не может передаваться мгновенно. Хуже то, что они нарушают здравый смысл, самые основания нашего представления о мире — что нельзя изменить состояние объекта, не взаимодействуя с ним.

На что похожи квантовые нарушения локальности?

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

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


Может ли быть так, что мы чего-то не учитываем и частицы обо всем «договорились» в момент рождения?

Собственно, такой вывод Эйнштейн, Подольский и Розен сделали. Они сказали, что получается, что квантовая теория либо внутренне противоречива, либо противоречит основополагающему принципу локальности! Физики высказали надежду, что может быть, когда-нибудь, в будущем, удастся создать теорию, которая сможет объяснить экспериментальные результаты так же хорошо, как квантовая механика. При этом она будет объяснять корреляцию, которую я описал выше, именно таким образом — что частицы с момента рождения несут в себе какие-то скрытые, нам пока неизвестные, скоррелированные друг с другом параметры, которые и определят результат измерений.

Неравенства Белла, они связаны с локальностью и нелокальностью, с локальным реализмом? Если да, то как?

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

Ситуация изменилась в 1964 году, когда Джон Белл придумал эксперимент, в котором любая альтернативная теория, если только она соблюдает принцип локальности, предсказывает иной результат, нежели квантовая теория. И как только это произошло, проблема вернулась в лоно физики: появилась возможность решить вопрос в ту или иную сторону посредством эксперимента. Открытие Белла было не менее великим, чем открытие Эйнштейна. Подумайте только: его эксперимент позволяет проверить гипотезу, про которую почти ничего не известно, кроме того, что она подчиняется принципу локальности.


Наблюдали ли нарушения локальности экспериментально? Есть ли принципиальные различия между разными экспериментами?

Эксперименты по схеме Белла появились практически сразу после его открытия и продолжаются до сих пор, постоянно совершенствуясь. Все эти эксперименты свидетельствовали в пользу нарушения локальности. То есть существуют корреляции, которые невозможно объяснить с помощью скрытых локальных параметров. Цель усовершенствования экспериментов — устранение «дыр». Например, одна из таких «дыр», которую до недавнего времени не удавалось победить, была потерей доли частиц по дороге к Алисе и Бобу и при детектировании. Если частицы теряются, то можно, играя роль адвоката дьявола, говорить, что природа создаёт эти потери избирательно, и что они искажают статистику результатов и создают лишь иллюзию нелокальности. Эксперимент, в котором все «дыры» были устранены, появился лишь несколько месяцев назад. Это значительное достижение в современной физике.

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

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

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

Есть какие-то примеры нелокальных теорий?

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

В каких еще физических теориях действует принцип локальности? Локальна ли электродинамика Максвелла?

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

Нужно ли как-то справляться с квантовой нелокальностью? Как это нам поможет?

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

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

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

СОДЕРЖАНИЕ

Типы населенных пунктов

Существует несколько различных типов справочной местности:

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

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

    Актуальность

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

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

    Общее использование

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

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

    Использование пространственной и временной местности

    Иерархическая память

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

    Элементы данных в кэше не обязательно соответствуют элементам данных, которые пространственно близки в основной памяти; однако элементы данных помещаются в кэш по одной строке кэша за раз. Это означает, что пространственная локальность снова важна: если имеется ссылка на один элемент, несколько соседних элементов также будут помещены в кэш. Наконец, временная локальность играет роль на самом низком уровне, поскольку результаты, на которые ссылаются очень близко друг к другу, могут храниться в машинных регистрах . Некоторые языки программирования (например, C ) позволяют программисту предлагать хранить определенные переменные в регистрах.

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

    Типичная иерархия памяти (время доступа и размеры кэша являются приблизительными значениями, используемыми с 2013 года для целей обсуждения; фактические значения и фактическое количество уровней в иерархии различаются):

    • Регистры процессора (8–256 регистров) - немедленный доступ со скоростью внутреннего ядра процессора
    • Кеши ЦП L1 (от 32 КБ до 512 КБ ) - быстрый доступ со скоростью внутренней шины памяти, принадлежащей исключительно каждому ядру
    • Кеши ЦП L2 (от 128 КБ до 24 МБ ) - немного более медленный доступ, со скоростью шины памяти, разделяемой между двойниками ядер
    • Кеши ЦП L3 (от 2 МБ до 32 МБ ) - еще более медленный доступ, при этом скорость шины памяти распределяется между еще большим количеством ядер одного процессора
    • Основная физическая память ( RAM ) (от 256 МБ до 64 ГБ ) - медленный доступ, скорость которого ограничена пространственными расстояниями и общими аппаратными интерфейсами между процессором и модулями памяти на материнской плате.
    • Диск ( виртуальная память , файловая система ) (от 1 ГБ до 256 ТБ ) - очень медленный из-за более узкого (по разрядности), физически гораздо более длинного канала данных между основной платой компьютера и дисковыми устройствами, а также из-за требуется посторонний программный протокол поверх медленного аппаратного интерфейса
    • Удаленная память (другие компьютеры или облако) (практически без ограничений) - скорость варьируется от очень медленной до очень медленной.

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

    Умножение матриц

    При изменении порядка цикла для j и k ускорение умножения больших матриц становится значительным, по крайней мере, для языков, в которых непрерывные элементы массива помещаются в последнее измерение. Это не изменит математический результат, но повысит эффективность. В этом случае «большой» означает, приблизительно, более 100 000 элементов в каждой матрице или достаточное количество адресуемой памяти, так что матрицы не помещаются в кэш-память L1 и L2.

    Причина этого ускорения заключается в том, что в первом случае операции чтения A[i][k] находятся в кеше (поскольку k индекс является непрерывным последним измерением), но B[k][j] нет, поэтому существует штраф за промахи в кеше B[k][j] . C[i][j] не имеет значения, потому что его можно поднять из внутреннего цикла - переменная цикла есть k .

    Во втором случае операции чтения и записи C[i][j] находятся в кеше, чтение B[k][j] - в кеше, а чтение A[i][k] может быть выведено из внутреннего цикла.

    Таким образом, во втором примере нет штрафа за промахи в кэше во внутреннем цикле, в то время как в первом примере штраф за кеширование.

    На процессоре 2014 года второй вариант примерно в пять раз быстрее первого, если он написан на C и скомпилирован с помощью gcc -O3 . (Тщательное изучение дизассемблированного кода показывает, что в первом случае GCC использует инструкции SIMD, а во втором - нет, но потери кэша намного хуже, чем усиление SIMD.)

    Временная локальность также может быть улучшена в приведенном выше примере с помощью техники, называемой блокировкой . Большую матрицу можно разделить на подматрицы равного размера, чтобы на меньшие блоки можно было ссылаться (умножаться) несколько раз, пока они находятся в памяти. Обратите внимание, что этот пример работает для квадратных матриц размеров SIZE x SIZE, но его можно легко расширить для произвольных матриц, заменив SIZE_I, SIZE_J и SIZE_K там, где это необходимо.

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


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

    • Ключевые слова / keywords:
    • На пути к экзафлопсу
    • On the way to exaflops
    • Суперкомпьютеры
    • конкурентные вычисления
    • concurrent computing
    • Платформы
    • распределенная память

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

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

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

    Рис.1. Ресурс параллелизма и использование данных
    Рис.1. Ресурс параллелизма и использование данных

    Ресурс параллелизма в современных суперкомпьютерах растет невероятными темпами — первое значение в 1 MFLOPS было получено в 1966 году на компьютере CDC-6600, содержащем единственный процессор, и до настоящего времени именно увеличение степени параллелизма определяло рост производительности. Все специалисты сходятся во мнении, что на экзафлопсных суперкомпьютерах одновременно будут работать сотни миллионов и миллиарды параллельных процессов и нитей, а если это так, то как обеспечить эффективность их взаимодействия при выполнении приложения?

    Эффективное использование данных уже давно стало серьезной проблемой, и еще в середине 90-х годов она удостоилась даже специального термина — «стена памяти» [1]. Задержка при обращении процессора к оперативной памяти для большинства современных систем лежит в диапазоне 150–300 тактов, и пока нет доступных технологий, которые могли бы это значение принципиально уменьшить. Основным решением на сегодня является использование иерархии памяти, однако тут же возникает вопрос: как обеспечить работу с данными в программах и алгоритмах, адекватную введенной иерархии?

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

    Универсальный характер применимости локальности сначала удивляет, но вместе с этим он легко объясняется многими естественными принципами. Простой физический принцип «чем ближе расположены — тем быстрее взаимодействие» находит отражение почти во всех элементах архитектуры вычислительных систем. Более того, необходимость учета локальности возникает и из-за постоянного поиска компромисса между разумной стоимостью и разумными характеристиками компонентов суперкомпьютеров. Хорошо бы тогда и для всей оперативной памяти иметь латентность, как у кэш-памяти первого уровня, но пока это технологически сложно и чрезмерно дорого, а отсюда и возникает иерархия памяти, отражающая локальность. Хорошо бы в суперкомпьютерах для быстрой связи каждого узла с любым другим иметь топологию коммуникационной сети «полный граф», но это технологически сложно и дорого, а отсюда компромиссы в виде более простых решений: решетка, кольцо, толстое дерево, N-мерный тор, Dragonfly и другие — где взаимодействие с непосредственными соседями всегда происходит быстрее. Следует отметить и тот факт, что локальность свойственна и нашему стилю написания программ, и используемым структурам данных, многим технологиям программирования и используемым конструкциям языков высокого уровня.

    Локальность всюду

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

    Иерархия памяти — очень важное понятие, прямо связанное с эффективностью. Для любой современной вычислительной платформы легко написать два варианта программы, реализующих один и тот же алгоритм, но отличающихся друг от друга на порядок по времени работы, причем без использования избыточных операций и каких-либо специальных задержек. Интересно и то, что сама идея иерархии памяти появилась давно. Например, уже в компьютере ILLIAC-IV (1967 год) каждый процессорный элемент имел 6 регистров и 2048 слов оперативной памяти. Кроме того, для всей системы были предусмотрены два диска по 1 Гбит каждый и барабан для долговременного хранения данных объемом 10 12 бит с однократной записью — иерархия памяти в четыре уровня была уже тогда.

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

    Еще большее значение имеет локальность данных в системах с распределенной памятью. Во время работы параллельной программы происходит обмен данными между процессами, на скорость которого влияют и латентность, и пропускная способность, и другие характеристики коммуникационной сети. Чем меньше обменов, тем меньше задержек и выше эффективность программ. Как распределить данные по памяти вычислительных узлов, чтобы минимизировать обмен в процессе выполнения программы? Это исключительно серьезная математическая задача [2], которая далеко не всегда имеет простое решение, однако эта задача принципиально важна для разработки масштабируемых приложений для экзафлопсных суперкомпьютеров, и именно поэтому проектирование алгоритмов без интенсивного обмена данными (communication free algorithms) является одним из приоритетных направлений исследований для всего суперкомпьютерного сообщества.

    Заметим, что понимание важности описания локальности расположения данных для создания масштабируемых и переносимых приложений привело к появлению отдельного класса технологий параллельного программирования, опирающихся на модель PGAS (Partitioned Global Address Space). Яркими представителями этого класса являются языки UPC, Coarray Fortran, Fortress, Chapel и X10.

    Смежный, но очень важный для систем с распределенной памятью вопрос — топология коммуникационной сети и ее учет параллельными приложениями. Главная проблема заключается в том, чтобы обеспечить хорошее соответствие между локальностью взаимодействия параллельных процессов в приложении и близостью вычислительных узлов. Интересные данные были приведены на конференции ISC 2013 об опыте использования суперкомпьютера Blue Waters в Центре суперкомпьютерных приложений — если из 4116 узлов, выделяемых приложению, всего 1 узел (0,02% от общего числа) выбивается из связного пула узлов и выделяется где-то в другой области коммуникационной сети, то падение эффективности работы приложения на такой конфигурации может достигать 30% и более. Подобные примеры накладывают жесткие требования не только на качество работы планировщиков заданий, которые обязательно должны учитывать локальность при выделении ресурсов приложениям. Здесь важно понимать и четко описывать структуру взаимодействия параллельных процессов внутри самих приложений, но эта информация доступна далеко не всегда. Если в приложении, например, явным образом используется понятие MPI-топологии, то задача упрощается, но в общем случае она очень непроста.

    Весьма интересно то, как идеи локальности отражаются в технологиях программирования. В технологии OpenMP предусмотрены два класса переменных: локальные (private) и глобальные (shared). Если нить использует свои локальные переменные, то все происходит без каких-либо задержек и проблем. Но если необходим доступ к глобальной переменной, то начинаются вопросы. Где физически расположить глобальную переменную, чтобы доступ к ней из любой нити был бы одинаково быстрым? Как обеспечить синхронизацию доступа для сохранения корректности данных? Сразу возникает необходимость синхронизации и использования механизмов критической секции или семафоров, и, как следствие, неизбежно падает эффективность.

    Другой пример «нелокальности» — коллективные операции в MPI, вовлекающие, как правило, все параллельные процессы приложения. На практике отсутствие локальности в организации параллелизма всегда оборачивается проблемами с эффективностью и масштабируемостью приложений, поэтому использование таких операций стараются минимизировать. Для алгоритмов, в которых не требуется барьерная синхронизация, ввели даже специальное название: synchronization free algorithms, подчеркивая практическую важность этого свойства.

    Локальность на практике

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

    Мощным средством, дающим хорошее представление о свойствах локальности реальных приложений, является построение профиля работы приложения с памятью [3] — последовательности чисел (адресов) в памяти, расположенных в том порядке, в котором к ним происходят обращения при выполнении программы. Как часто этим пользуются на практике? Вряд ли можно назвать это распространенным явлением. На рис. 2 показаны четыре профиля, отвечающие различным приложениям. По вертикали отложены виртуальные адреса данных, к которым происходит обращение, а по горизонтали — порядковый номер обращения: чем правее расположено обращение, тем позже оно произошло. Ясно, что программа, профиль которой изображен на рис. 2, а, обладает крайне плохой как пространственной, так и временнóй локальностью, что станет причиной заведомо низкой эффективности. Профиль на рис. 2, б показывает чуть лучшие свойства, но до высоких показателей еще далеко, а программы, чьи профили изображены на рис. 2, в и 2, г, явно обладают хорошими свойствами локальности.

    Рис. 2. Профили работы с памятью реальных программ
    Рис. 2. Профили работы с памятью реальных программ

    Еще одним мощным средством исследования реальных свойств программ является анализ данных мониторинга системного уровня, описывающих характеристики программно-аппаратной среды суперкомпьютеров во время исполнения приложений. В основе подхода Job Digest [4], развиваемого в НИВЦ МГУ, лежит анализ данных от аппаратных датчиков: реальная загрузка процессоров, реальная производительность, особенности использования коммуникационной сети, интенсивность операций ввода-вывода, появление свопинга и т. д. Эти и другие параметры дают содержательную информацию о многих свойствах параллельных приложений. В том числе и о свойствах локальности. На рис. 3 показаны два графика,иллюстрирующих ситуацию с промахами в кэш-память второго уровня для двух разных приложений. Ясно, что у первого приложения локальность использования данных не составляет проблем, однако у второго на локальность явно нужно обратить внимание.

    Рис. 3. Job Digest: иллюстрация кэш-промахов для отражения локальности использования данных в приложениях
    Рис. 3. Job Digest: иллюстрация кэш-промахов для отражения локальности использования данных в приложениях

    Свойство локальности отлично согласуется с возможностями технологий для разумного построения суперкомпьютеров экзафлопсной производительности, а сама идея локальности естественна и отражает окружающий мир, поэтому неудивительно, что нерегулярные приложения проигрывают приложениям с хорошими свойствами локальности. Более того, суперкомпьютеры будущего будут учитывать свойства локальности, что подтверждается даже соображениями энергопотребления — жизненно важного для экзафлопсных систем. Энергозатраты на выполнение одной арифметической операции составляют 100 пДж (1 пДж = 10 -12 Дж), в то время как энергозатраты на перемещение данных в пределах узла — 4800 пДж, что ставит жесткое требование к минимизации перемещений данных и снова указывает на актуальность свойства локальности.

    Читайте также: