Иерархическая временная память (краткий обзор)

Иерархическая временная память (краткий обзор)

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

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

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

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

Обратите внимание

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

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

Рассмотрим основные элементы и принципы построения иерархической временной памяти.

Основные элементы и принципы построения иерархической временной памяти

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

Регион функционирующей сети представляет собой один уровень или одну из составляющих уровня иерархии, когда таких регионов на уровне несколько.

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

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

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

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

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

Важно

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

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

Иерархическая память и физиология

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

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

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

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

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

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

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

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

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

Совет

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

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

Алгоритмы обучения иерархической временной памяти

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

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

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

Затем регион определяет, каким образом они образуют последовательности во времени.

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

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

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

Обратите внимание

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

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

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

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

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

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

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

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

Важно

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

искусственные нейронные сети иерархическая временная память

Как устроена оперативная память – Компьютерная техника

Страница создана: 2010-09-09, обновлена: 2017-10-27

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

Адресация данных

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

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

Схематически память компьютера можно представить в виде массива слов.

Обычно длина машинного слова компьютеров составляет от 16 до 64 бит. Если длина слова равна 32 битам, в одном слове может храниться 32-разрядное число в дополнительном коде или четыре символа ASCII, занимающих 8 бит каждый. Восемь идущих подряд битов являются байтом. Для представления машинной команды требуется одно или несколько слов.

Байтовая адресация

Отдельные биты, как правило, не адресуются и чаще всего адреса назначаются байтам памяти. Память, в которой каждый байт имеет отдельный адрес, называется памятью с байтовой адресацией. Последовательные байты имеют адреса 0.1, 2 и так далее Таким образом, при использовании слов длиной 32 бита последовательные слова имеют адреса 1.4, 8, …, и каждое слово состоит из 4 байт.

Прямой и обратный порядок байтов

Существует два способа адресации байтов в словах:

• в прямом порядке. Прямым порядком байтов (little-endian) называется система адресации, при которой байты адресуются справа налево, так что наименьший адрес имеет самый младший байт слова (расположенный с правого края);
• в обратном порядке. Обратным порядком байтов (big-endian) называется система адресации, при которой байты адресуются слева направо, так что самый старший байт слова (расположенный с левого края) имеет наименьший адрес.

В ПЭВМ на основе 80 x 86 используется прямой порядок, а в ПЭВМ на основе Motorola 68000 – обратный. В обеих этих системах адреса байтов 0.4, 8 и так далее, применяются в качестве адресов последовательных слов памяти в операциях чтения и записи слов.

Расположение слов в памяти

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

По практическим причинам, связанным с манипулированием Двоично-кодированными адресами, количество байтов в слове обычно является степенью двойки. Поэтому, если длина слова равна 16 бит (2 байтам), выровненные слова начинаются по байтовым адресам 0.

2, 4, …, а если она равна 64 бит (23, то есть 8 байтам), то выровненные слова начинаются по байтовым адресам 0.8, 16, …

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

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

Адресное пространство

Для доступа к памяти необходимы имена или адреса, определяющие расположение данных в памяти. В качестве адресов традиционно используются числа из диапазона от 0 до 2k- 1 со значением к, достаточным для адресации всей памяти компьютера. Все 2k адресов составляют адресное пространство компьютера. Следовательно, память состоит из 2kадресуемых элементов.

Например, использование 24-разрядных (как в процессоре 80286) адресов позволяет адресовать 224 (16 777 216) элементов памяти. Обычно это количество адресуемых элементов обозначается как 16 Мбайт (1 Мбайт=220=1 048 576 байт, адресное пространство 8086 и 80186). Поскольку у процессоров 80386.

80486 Pentium и их аналогов 32-разрядные адреса, им соответствует адресное пространство в 232 байт, или 4 Гбайт.

Совет

Адресное пространство ЭВМ графически может быть изображено прямоугольником, одна из сторон которого представляет разрядность адресуемой ячейки (слова) процессора, а другая сторона – весь диапазон доступных адресов для этого же процессора. Диапазон доступных адресов процессора определяется разрядностью шины адреса системной шины. При этом минимальный номер ячейки памяти (адрес) будет равен 0, а максимальный определяется из формулы M=2n – 1.

Для шестнадцатиразрядной шины это будет 65 535 (64 К).

Иерархическая организация памяти

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

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

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

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

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

Доля попаданий (hit rаtе) – доля обращений к данным, найденным на более высоком уровне. Доля промахов (miss rate) – это доля обращений к данным, которые не найдены на более высоком уровне.

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

Потери на промах (miss реnаltу) есть время для замещения блока в более высоком уровне на блок из более низкого уровня плюс время для пересылки этого блока в требуемое устройство (обычно в процессор).

Потери на промах далее включают в себя два компонента:

• время доступа (access time) – время обращения к первому слову блока при промахе;
• время пересылки (transfer time) – дополнительное время для пересылки оставшихся слов блока. Время доступа связано с задержкой памяти более низкого уровня, а время пересылки – с полосой пропускания канала между устройствами памяти двух смежных уровней.

Кэш-память

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

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

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

Обратите внимание

В дальнейшем она была разделена на два уровня – встроенная в процессор (on-die) и внешняя (on-motherboard).

Иерархия оперативной памяти

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

Эффективность той или иной системы кэш памяти зависит от стратегии управления памятью.

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

Отображение памяти на кэш

Существует три основных способа размещения блоков (строк) основной памяти в кэше:

• кэш память с прямым отображением (direct-mapped cache);
• полностью ассоциативная кэш память (fully associative cache).
• частично ассоциативная (или множественно ассоциативная, partial associative, set-associative cache) кэш память;

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

(Адрес блока кэш памяти)=(Адрес блока основной памяти) mod (Число блоков в кэш памяти).

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

Полностью ассоциативная память

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

Частично-ассоциативный кэш

Является наиболее распространенным в данный момент среди процессорных архитектур. Характеризуется тем или иным количеством n «каналов» (степенью ассоциативности, «п-way») и может отображать содержимое данной строки памяти на каждую из n своих строк. Этот вариант является разумным компромиссом между полностью ассоциативным и кэшем «прямого отображения».

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

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

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

При замещении просто нечего выбирать – на попадание проверяется только один блок и только этот блок может быть замещен.

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

• случайная (Random) – блоки-кандидаты выбираются случайно (равномерное распределение). В некоторых системах используют псевдослучайный алгоритм замещения;
• замещается тот блок, который не использовался дольше всех (LRU – Least-Recently Used). В этом случае чтобы уменьшить вероятность удаления информации, которая скоро может потребоваться, все обращения к блокам фиксируются.

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

Алгоритмы обмена с кэш памятью (свопинга)

включают следующие разновидности:

• алгоритм сквозной записи (Write Through) или сквозного накопления (Store Through);
• алгоритм простого свопинга (Simple Swapping) или обратной записи (Write Back);
• алгоритм свопинга с флагами (Flag Swapping) или обратной записи в конфликтных ситуациях с флагами (CUX);
• алгоритм регистрового свопинга с флагами (FRS).

Алгоритм сквозной записи

Самый простой алгоритм свопинга.

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

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

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

Алгоритм простого свопинга

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

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

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

Алгоритм свопинга с флагами

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

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

Алгоритм регистрового свопинга с флагами

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

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

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

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

Иерархическая организация памяти

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

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

Важно

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

Обычно рассматривается взаимодействие внутри иерархии памяти между двумя соседними уровнями.

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

При обращении к каждому уровню иерархии возможны два исхода. Либо искомый блок находится на запрашиваемом уровне (попадание – hit) либо он отсутствует (промах – miss) и приходится обращаться к следующему уровню иерархии, обладающему меньшей скоростью выборки.

Эффективность механизма хранения данных можно описать долей попаданий (hit rate). Механизм организации каждого уровня иерархии должен обеспечивать возможность размещения любого блока из более низкого уровня иерархии.

Отсюда – необходим некий ассоциативный механизм отображения блока из нижележащего уровня иерархии на вышележащий.

Иерархия памяти в ЭВМ показана на рис. 17. Емкость памяти растет сверху вниз на рисунке, стоимость хранения байта (слова) и скорость выборки байта (слова) растет снизу вверх.

Самый верхний уровень иерархии – регистровая память. Емкость регистровой памяти обычно не превышает нескольких десятков (иногда сотен) байт или слов.

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

Совет

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

Массовая оперативная память имеет объем от нескольких десятков килобайт до нескольких сотен мегабайт.

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

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

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

Он просматривает обращения центрального процессора к основной памяти и определяет хранятся ли требуемые данные в кэше (cache hit) и,следовательно, могут быть прочитаны из него, или нет (cache miss), и следовательно, придется производить обращение к более медленной основной памяти. Скорость доступа к ячейке кэш-памяти может составлять от 3 до 7 тактов процессора. Кэш-память в свою очередь сама может быть реализована по иерархическому принципу, т.е. может быть разделена на несколько уровней:

· кэш первого уровня, объемом несколько килобайт со временем доступа 2-3 такта, встроенный непосредственно в процессор;

· кэш второго уровня со временем доступа 3-5 тактов и объемом несколько десятков килобайт, расположенный на одной плате с центральным процессором;

· кэш третьего уровня со временем доступа 5-7 тактов и объемом несколько сотен килобайт на системной плате и так далее.

Ниже в этом разделе мы вернемся обсуждению кэш-памяти и рассмотрим ее функционирование подробнее.

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

Обратите внимание

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

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

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

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

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

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

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

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

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

Кэш-память

Как уже говорилось выше, назначение кэш-памяти – временное хранение данных и команд, часто используемых процессором. Основной структурной единицей кэш-памяти является так называемая строка кэша (cache line). Длина строки кэша составляет обычно 32, 64, 128 или 256 байт.

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

Важно

Следовательно, объем непосредственно адресуемой оперативной памяти составляет 210 байт. Пусть имеется кэш-память из восьми строк, каждая строка из восьми байт. Организация кэш-памяти показана на рис 18. С каждой строкой кэша связано поле тэга.

Тэг (tag – пометка, отметка) – признак, используемый при поиске требуемых данных.

Существуют три основных способа организации кэш-памяти: 1) кэш с прямым отображением; 2) полностью ассоциативный кэш; 3) наборно ассоциативный кэш.

В случае кэша с прямым отображением адрес, формируемый процессором, имеет вид, показаный на рис 18 а). Адрес состоит из трех частей. Младшие биты адреса определяют конкретный байт в строке кэша. Их количество k определяется длиной строки кэша L

k = log2L.

Средние биты адреса определяют одну из строк кэша. Количество n средних битов определяется количеством M строк кэша

n = log2M.

тэг

а)

тэг

б)

тэг

в)

Рис 18. Кэш-память. а) с прямым отображением; б) полностью ассоциативная; в) наборно-ассоциативная.

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

Достоинство кэша с прямым отображением – очевидная простота реализации. Недостаток состоит в том, что несколько адресов с одинаковыми младшими k + n битами могут претендовать на одну и ту же ячейку кэша.

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

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

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

Как следствие, ассоциативная кэш память не может иметь большого количества строк.

Третий вид кэш-памяти – наборно-ассоциативная (см. рис 18 в)) – это смешанная конструкция, сочетающая в себе простоту памяти с прямым отображением и эффективность ассоциативного кэша.

Совет

Строки кэша объединяются в наборы по 2, 4, 8 и т.д. штук. Средние биты определяют не строку, а набор. Конкретная строка в наборе выбирается с помощью ассоциативного сравнения для всех строк, входящих в набор.

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

Для этого не­обходимо решить, какую из строк кэша сле­дует удалить для разме­щения вновь поступивших данных. Для выбора строки, подлежащей замещению, чаще всего используется так называемый алгоритм LRU (от Least Recently Used – дольше всего неиспользуемый).

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

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

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

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

Первый, самый простой, носит название сквозная запись (write through). При этом способе данные одновременно записываются в кэш-память и в опера­тивную память. Естественно, выигрыша в ско­рости при записи не происходит.

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

Обратите внимание

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

Существенно уменьшить потери производительности позволяет другой способ записи, который называется буферизированной сквозной записью (buffered write through).

Процессор передает запи­сываемые данные контроллеру кэша и на этом операция записи для процессора считается законченной.

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

Третий способ организации называется обратной записью (write back). При этом способе нагрузка на тракты обмена данными между процессором и памятью максимально снижается. Процессор произ­водит запись только в кэш-память.

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

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

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

Применение модели иерархической временной памяти в распознавании изображений

УДК 004.931

ПРИМЕНЕНИЕ МОДЕЛИ ИЕРАРХИЧЕСКОЙ ВРЕМЕННОЙ ПАМЯТИ В РАСПОЗНАВАНИИ ИЗОБРАЖЕНИЙ

Ю.А. Болотова, В.Г. Спицын, А.Э. Фомин*

Томский политехнический университет, *Московский физико-технический институт E-mail: julya21@hotbox.ru; arseniy-fe@mail.ru

На основе модели иерархической временн?й памяти Дж. Хокинса и Дж. Дилипа разработана система для решения задачи распознавания образов. Описана структура системыi, алгоритм ее обучения ирабоы. Представленыi результатыi тестирования системы,I на примере распознавания стилизованных цифр.

Ключевые слова:

Модель иерархической временной памяти, распознавание образов, временная и иерархическая составляющая в процессе видения, эволюционны1й алгоритм. Key words:

Важно

Hierarchical temporal memory model, pattern recognition, time and hierarchical components in vision, evolutionary algorithm.

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

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

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

Чем выше уровень иерархии, тем с более абстрактной информацией он работает.

Следовательно, в системе распознавания образов сложные объекты должны быть иерархически связаны с более простыми их составляющими [1—4].

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

Структура сети

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

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

1 приведен пример сети, состоящей из 3-х уровней.

Рис. 1. Схема передачи информации между уровнями

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

Структура узла

Совет

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

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

трицы смежности Т (рис. 3, а) и цепи Маркова, состоящей из 5 пространственных центров. В результате выделились 2 временные группы: g1 и ^2 (рис. 3, б).

Рис. 2. Структура узла. Пример узла первого уровня: с—с5 -пространственные центры; д1, д2 – временные группы

Пространственное объединение

Пространственное объединение необходимо для фильтрации и компрессии входных данных и их первичного обобщения.

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

#факты | Иерархия компьютерной памяти

Сегодня мы поговорим о том месте, которое занимает в вашем цифровом устройстве каждый вид памяти. Та память, которую мы сегодня рассмотрим, именуется компьютерной, хотя и применяется не только в ПК, но и в других цифровых устройствах.

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

Обратите внимание

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

О системе памяти новой игровой консоли Xbox One мы недавно рассказывали довольно подробно. И хотя перед нами игровая консоль, ее память в полной мере компьютерная.

Какой бывает компьютерная память и в каких устройствах она используется?

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

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

К примеру, большинство типов оперативной памяти относятся к энергозависимой категории.

Наиболее известные представители энергонезависимой категории это ПЗУ (постоянная память) и флеш-память, получившая в последнее время немалое распространение. В частности, карты памяти CompactFlash и SmartMedia.

Прежде всего просто перечислим основные виды компьютерной памяти и только потом начнем их рассматривать:

• Оперативная память. Оперативное запоминающее устройство. ОЗУ, RAM
• Постоянная память. Постоянное запоминающее устройство. ПЗУ, ROM
• Кеш-память, Cache
• Динамическая оперативная память. Dynamic RAM, DRAM
• Статическая оперативная память. Static RAM, SRAM
• Флеш-память, Flash memory
• Память типа Memory Sticks в виде карт памяти для цифровых фотоаппаратов
• Виртуальная память, Virtual memory
• Видеопамять, Video memory
• Базовая система ввода-вывода, БСВВ, BIOS

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

• Сотовых телефонах
• Смартфонах
• Планшетах
• Игровых консолях
• Автомобильных радиоприемниках
• Цифровых медиаплеерах
• Телевизорах

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

Иерархическая пирамида компьютерной памяти

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

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

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

Важно

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

Вершиной пирамиды является регистр процессора.

За ним следует кеш-память первого (L1) и второго уровня (L2) Оперативная память делится на: физическую и виртуальную И кеш, и оперативная память являются временными хранилищами информации Далее идут постоянные хранилища информации: ПЗУ/BIOS; съемные диски; удаленные накопители (в локальной сети); жесткий диск Подножие пирамиды образуют устройства ввода, к которым относятся:

клавиатура; мышь; подключаемые медиаустройства; сканер/камера/микрофон/видео; удаленные источники; другие источники

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

Роль оперативной памяти в общем «оркестре» компонентов компьютера

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

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

Давайте рассмотрим типичный сценарий работы любого компьютера.

Вы включили компьютер. Он, в свою очередь, загрузил данные из постоянной памяти (ROM) и начал самотестирование при включении (power-on self-test, POST). Компьютер проверяет сам себя и определяет, исправен ли он и готов ли к новому трудовому сеансу.

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

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

Компьютер загружает из ПЗУ базовую систему ввода-вывода, более известную по английской аббревиатуре BIOS. В этом «биосе» содержится базовая информация о накопителях, порядке загрузки, безопасности, автоматическом распознавании устройств (Plug and Play) и некоторые иные сведения.

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

Совет

Важные компоненты операционной системы обычно находятся в оперативной памяти компьютера на протяжении всего времени работы с ним.

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

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

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

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

Что происходит, когда вы сохраняете файл и закрываете приложение? Файл записывается на жесткий диск, а приложение «выталкивается» из оперативной памяти.

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

Если измененный файл не был сохранен перед удалением из временного хранилища, все изменения будут потеряны.

Обратите внимание

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

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

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

Продолжение следует

По материалам computer.howstuffworks.com