Кохонен Т.
Ассоциативные запоминающие устройства
Перевод с английского канд. техн. наук С. П. Забродина
и канд. техн. наук А. В. Шалашова
под редакцией д-ра техн. наук В. И. Зуева
МОСКВА
«МИР»
1982
Кохонен Т. Ассоциативные запоминающие устройства. Перевод с английского. Москва. Мир, 1982.
В книге финского автора излагаются принципы создания и построения схе» ассоциативных запоминающих устройств. Основное внимание уделено возможностям использования таких ЗУ в системах с виртуальной, буферной и распределенной памятью в многопроцессорных вычислительных машинах. Автор известен советскому читателю по книге "Ассоциативная память" (М.: Мир, 1980).
Для инженеров, занимающихся разработкой цифровых вычислительных систем, а также студентов и аспирантов, изучающих вычислительную технику.
Редакция литературы по новой технике
© by Springer-Verlag Berlin Heidelberg 1980. All Rights Reserved. Authorized translation from English language edition published by Springer-Verlag Berlin — Heidelberg — New York
© Перевод на русский язык, «Мир», 1982
Содержание книги
Ассоциативные запоминающие устройства
Предисловие редактора перевода
Предисловие
Глава 1. Ассоциативная память, адресация по содержанию и ассоциативная выборка
1.1. Введение
1.2 Два подхода к реализации памяти с адресацией по содержанию
1.3. Ассоциации
1.4. Ассоциативная выборка: развитие основных понятий
Литература
Глава 2. Адресация по содержанию: программный подход
2.1. Основные принципы хеширования
2.2. Функции хеширования
2.3. Обработка коллизий
2.4. Структура и форматы таблиц хеширования
2.5. Анализ различных схем хеширования
2.6. Многоключевой поиск
2.7. Применение методов хеширования для поиска по соответствию
2.8. Организация памяти типа TRIE
2.9. Обзор литературы по методам хеширования и смежным вопросам
Литература
Глава 3. Логические принципы организации памяти с адресацией по содержанию (ПАС)
3.1. Возможности применения ассоциативных запоминающих устройств (АЗУ)
3.2. Логические основы операций сравнения
3.3. АЗУ параллельного действия
3.4. АЗУ с поиском, параллельным по словам и последовательным по разрядам
3.5. АЗУ, последовательные по словам и параллельные по разрядам
3.6. Методы побайтового поиска с адресацией по содержанию
3.7. Функциональная память
3.8. Методика формального описания микроопераций в АЗУ
3.9. Литература по АЗУ
Литература
Глава 4. Аппаратная реализация АЗУ
4.1. Электронные устройства ассоциативной памяти
4.2. Схемы для ассоциативной памяти параллельного типа
4.3. Схемы для последовательной ассоциативной памяти
4.4. Оптические АЗУ
Литература
Глава 5. Место ассоциативной памяти в вычислительной системе
5.1. АЗУ в системах с виртуальной памятью
5.2. Ассоциативная организация динамического распределения памяти
5.3. Ассоциативный буфер
5.4. Программируемая логика
Литература
Глава 6. Ассоциативные процессоры
6.1. Некоторые тенденции развития функций ассоциативной памяти
6.2. Память с распределенной логикой (ПРЛ)
6.3. Расширенная ассоциативная память (РАП)
6.4. Процессор ассоциаций (ПА)
6.5. Ассоциативные процессоры с операционными устройствами высокого уровня
6.6. Ассоциативные процессоры с последовательной обработкой разрядов
6.7. Обзор параллельных процессоров (ПП)
Литература
Предметный указатель
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
В последние годы в области вычислительной техники наметилась тенденция необычно быстрого увеличения производительности ЭВМ и систем. Существенную роль при этом играет совершенствование технических средств, в частности запоминающих устройств (ЗУ). Улучшаются не только технические характеристики таких устройств, но и ^расширяется набор выполняемых ими функций. Процесс увеличения производительности ЭВМ сопровождается передачей аппаратуре значительного числа функций, ранее выполнявшихся программными средствами.
В связи с бурным развитием полупроводниковой технологии, созданием схем с высокой степенью интеграции особенно важной становится задача ознакомления разработчиков с современным состоянием работ в области реализации ассоциативной обработки и хранения информации.
В настоящее время в литературе, в том числе отечественной, нет обобщающего труда, на основе которого специалистам можно было бы составить полное и достаточно четкое представление об основных системно-теоретических концепциях ассоциативной обработки и хранения информации. Книга проф. Кохонена в значительной мере восполняет указанный пробел, и нам представляется, что она будет с интересом принята специалистами. Следует отметить, что комплексный характер проблемы ассоциативной обработки и хранения информации, рассмотренный в предлагаемой книге, делает ее весьма полезной для разработчиков новых технических средств ЭВМ, а также для специалистов других областей (технической кибернетики, робототехники медицины, физики и др.).
Материал книги расположен в строгой логической последовательности, начиная с изложения основных теоретических положений, используемых в дальнейшем для выбора и обоснования технических решений, и кончая схемной реализацией устройств ассоциативной памяти на современной элементной базе. Необходимо отметить практическую ценность предлагаемого материала, ориентированного на удовлетворение запросов разработчиков средств вычислительной техники. Достаточно подробно рассмотрены сферы применения ассоциативной памяти в современных высокопроизводительных системах при реализации динамического распределения памяти, построении ассоциативных процессоров и др. Последняя глава интересна тем, что в ней представлены принципы построения ассоциативных процессоров, недостаточно освещенные в литературе, а также принципы построения систем РЕРЕ и STARAN.
При переводе и редактировании книги мы старались сохранить стиль автора и сделать все от нас зависящее, чтобы точнее передать основные идеи, рассматриваемые в книге.
Перевод книги выполнен А. В. Шалашовым (предисловие, гл. 1—3) и С. П. Забродиным (гл. 4—6).
В. И. Зуев
ПРЕДИСЛОВИЕ
Разработчики и пользователи ЭВМ давно придерживаются мнения, что в состав функций., выполняемых запоминающим устройством, следовало бы ввести средства адресации по содержанию. Подобные элементы «ассоциативной» памяти позволили бы существенно повысить производительность вычислительных систем за счет применения новых, более эффективных методов организации поиска данных. Однако, несмотря на то что основные принципы адресации по содержанию были разработаны более 20 лет назад, ассоциативные запоминающие устройства (АЗУ) до сих пор не получили широкого распространения. Как правило, они используются лишь в качестве буферных ЗУ небольшой емкости или входят в состав устройств управления центральных процессоров. Впрочем, в настоящее время положение, по-видимому, меняется благодаря развитию технологии производства ряда перспективных носителей информации, например полупроводниковых схем с высокой степенью интеграции, приборов с зарядовой связью, элементов памяти на цилиндрических магнитных доменах л т. д.
Переход на новую схемотехническую базу создает предпосылки для аппаратной реализации многих поисковых операций и построения АЗУ достаточно большой емкости, стоимость которых будет составлять лишь незначительную часть стоимости всей вычислительной системы. Внедрение таких запоминающих устройств, несомненно, окажет существенное воздействие на архитектуру и функционирование ЭВМ следующих поколений.
В этих условиях очень важно, чтобы пользователь ЭВМ мог своевременно знакомиться с новыми структурными и техническими принципами построения ассоциативной памяти. Между тем до последнего времени читателю было чрезвычайно сложно составить общее представление о тех разнообразных методах организации АЗУ и способах их схемной реализации, которые предлагались и постепенно устаревали по мере развития ассоциативных ЗУ. Методам адресации по содержанию было посвящено более тысячи статей, однако содержащийся в них материал до сих пор не был объединен в виде отдельной монографии. Отчасти это связано с тем, что в течение длительного времени информация о некоторых разработках редко публиковалась в открытой печати. Указанные обстоятельства и явились причиной появления настоящей книги, которая представляет собой попытку систематизировать результаты наиболее важных исследований, а также выявить их практическую ценность и проанализировать перспективы развития.
Материал представлен в книге в определенной логической последовательности. Вначале излагаются основные теоретические концепции, затем программные методы, которые, вероятно, заинтересуют всех, кто имеет дело с универсальными ЭВМ. Материал, посвященный логическим принципам и способам схемной реализации цепей АЗУ, предназначен главным образом для разработчиков вычислительной техники, в большей степени связанных с аппаратурой ЭВМ. Параллельные ассоциативные процессоры, архитектура которых представляет интерес лишь для отдельных специалистов, рассматриваются в последнюю очередь. Однако можно полагать, что со временем методы ассоциативной обработки будут применяться все более интенсивно, и круг пользователей, работающих с подобной техникой, значительно расширится.
Знакомясь с книгой, читатель отметит, что понятие адресации по содержанию трактуется в ней не столь узко, как это принято в литературе. Обычно термин «память с адресацией по содержанию» применяется лишь по отношению к соответствующим техническим средствам. Однако целый ряд чисто программных средств, в том числе такой способ быстрого поиска, как метод хеширования, может с равным правом именоваться адресацией по содержанию. Традиционно полагают, что реляционные и семантические структуры данных могут использоваться только при организации программных методов поиска. Между тем на аналогичных принципах может основываться и работа некоторых типов специализированной аппаратуры. В частности, уже созданы устройства, в которых аппаратно реализованы алгоритмы хеширования. Таким образом, происходит постепенное сближение программного и аппаратного подходов при построении ассоциативной памяти.
Именно поэтому было решено обсудить в книге совместно оба этих подхода, чтобы читатель имел возможность сравнить их и сделать более обоснованный выбор в пользу аппаратных или программных средств. Учитывая, что к последним можно отнести методы хеширования, они весьма подробно рассматриваются в гл. 2.
Основу книги составляют лекции, прочитанные автором в Технологическом университете г. Хельсинки, а также результаты исследований в области ассоциативной памяти, которые субсидировались Академией наук Финляндии. Мне хотелось бы выразить признательность за финансовую поддержку, оказанную мне этими учреждениями. Я хотел бы также поблагодарить лиц, содействовавших мне в работе над книгой: г-жу Пирио Тейти-нен, которая перепечатала рукопись и оказала помощь в подборе литературы; г-на Эркки Рейкала, занимавшегося сбором материалов по методам хеширования; г-жу Рауху Тапанайнен и г-на Эйкки Рийтинена, подготовивших иллюстрации; г-жу Майю-Лизу Хилкилья, напечатавшую предметный указатель и совместно с д-ром Эркки Оя откорректировавшую текст рукописи книги.
Теуво Кохонен
Скачать книгу "Ассоциативные запоминающие устройства". Москва, издательство Мир, 1982
|
