Буферизация команд 2 страница

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

Доступ к памяти с использованием чередования адресов

Рис 9.1

Рассмотрим более подробно реализацию архитектуры памяти с чередованием адресов: Разделим память на m банков В₀, В_1, ..., B_m-1 одинаковой емкости и установим связь между банком В, содержащим адрес i, и адресом d внутри банка B_k, соответствующим адресу i, следующим равенством:

l = d * m + k, d > 0, 0 < k < m—1;

Распределение адресов между m банками памяти называется m-кратным чередованием адресов памяти. Таким образом, память, состоящая из m банков с распределенными адресами, называется памятью с m-кратным чередованием адресов (m — обычно степень числа 2). Очевидно, что при обращении в ОП по адресу 5 в фиксаторы будет считано из банков содержимое по адресам 4, 5, 6 и 7, и при следующем обращении к соседнему адресу содержимое будет считано из фиксатора.

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

9.3 Кэш память

Кэш-память - это быстродействующая память, расположенная между ЦП и основной памятью (рис. 9.2). Вместе с основной памятью она образует иерархическую структуру, и ее действие эквивалентно быстрому доступу к основной памяти. В универсальных ЭВМ, основная память которых имеет емкость порядка 132 - 512 Мбайт, обычно используется кэш-память емкостью 64—512 Кбайт. То есть емкость кэш-памяти составляет порядка 1/1000—1/500 емкости основной памяти, а быстродействие в 5 - 10 раз выше быстродействия основной памяти.

Кэш - память

Рис 9.2

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

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

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

9.4. Ассоциативная память (безадресная память)

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

Схема ассоциативной памяти

Рис 9.3

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

Регистр маски в структуре ассоциативной памяти

Рис 9.4

Идей ассоциативной памяти были использованы в процессоре STARAN. Это матричный процессор, способный выполнять ассоциативный поиск с параллельным сравнением разрядов и последовательным сравнением слов и наоборот, т.е. с параллельным сравнением слов и последовательным сравнением разрядов по отношению к 256 процессорам, объединенных в единую матрицу.

10. АРХИТЕКТУРНЫЕ РЕШЕНИЯ

ВВОДА/ВЫВОДА ДАННЫХ

10.1 Проблемы организации и управления вводом/выводом

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

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

1) общее управление;

2) запуск операции ввода/вывода;

3) идентификация и обработка особых ситуаций;

4) завершение операций ввода/вывода;

5) синхронизация;

6) подключение новых устройств.

10.2 Основные архитектурные решения

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

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

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

10.3 Канальный ввод/вывод

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

Взаимодействие процессора и канала в канальной архитектуре

Рис 10.1

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

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

10.4 Архитектура с общей шиной

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

Архитектура с общей шиной

Рис 10.2

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

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

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

10.5 Архитектура ввода/вывода с общей памятью

Стремление универсально выполнять операции доступа, как к внешним, так и к внутренним устройствам привела в рамках архитектуры процессора пересылок к идее объединения адресного пространства не только внутри процессора и оперативной памяти, но и на уровне буферов устройств ввода/вывода - рис 10.3.

Архитектура ввода/вывода с общей памятью

Рис 10.3

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

11. ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА

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

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

11.1 Мультипрограммирование (многозадачность)

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

11.1.1 Однопроцессорная обработка

Схемы обработки потока разнородных задач на ЭВМ с одним процессором различаются в зависимости от характера потока задач и принятых решений по организации ввода/вывода:

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

Многозадачность в режиме квантования времени

Рис 11.1

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

Совмещение во времени работы процессора и канала для двух программ иллюстрировано на рис 11.2

Мультипрограммирование в канальной архитектуре

Рис 11.2

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

11.1.2 Многопроцессорная обработка

Наличие нескольких обрабатывающих устройств (АЛУ или процессоров) позволяет реализовать «настоящую» параллельную обработку заданий, при этом можно рассматривать несколько вариантов:

Вариант с раздельной оперативной памятью подразумевает фактически многомашинную систему, когда несколько ЭВМ (процессор + ОП) находятся под общим управлением диспетчера задач, распределяющего поток заданий - рис 11.3

Многомашинная система с диспетчером задач

Рис 11.3

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

Многопроцессорная система с общей памятью

Рис 11.4

11.2 Параллелизм независимых ветвей

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

Определение параллелизма ветвей на основе графа

вычислительного процесса задачи

Рис 11.5

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

1) нет связи по данным - результаты одного этапа не являются входом другого;

2) нет связей по уравнению - один этап не передает управление другому;

3) нет общих ячеек памяти по записи - этапы не производят запись по одному и тому же адресу памяти.

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

Она должна распределять параллельные ветви по процессорам в соответствии с графом вычислительного процесса задачи.

11.3 Параллелизм объектов

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

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

Параллелизм объектов - реализация «в ширину»

Рис 11.6

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

Параллелизм объектов - реализация «в глубину» - конвейер этапов

Рис 11.7

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

12. МАТРИЧНЫЕ СИСТЕМЫ

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

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

12.1 Однородные системы - параллелизм этапов задач

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

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

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

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

Однородная матричная система с перестраиваемой структурой

Рис 12.1

Идея однородных систем была предложена в начале 60-х годов Э.В. Евреиновым и Ю.Г. Косыревым в виде следующих трех принципов построения систем:

1) параллельность подзадач в алгоритмах (гипотеза параллельности - для сложной задачи можно предложить эффективный параллельный алгоритм решения);

2) переменность логической структуры;

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

12.2 Матрицы волнового фронта данных - параллелизм команд

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

Матричная система с волновым фронтом данных

Рис 12.2

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

12.3 Классические матричные системы - параллелизм объектов

Классические матричные системы реализую принцип - «одиночный поток команд - множественный поток данных». Процессорная матрица состоит из множества процессорных элементов (ПЭ) и одного устройства управления (УУ). УУ одновременно передает всем ПЭ одну и ту же команду, поэтому на всех ПЭ одновременно выполняется одна и та же операция, но с разными данными. Для передачи данных между ПЭ используется синхронная сеть связи. Схема классической матричной системы приведена на рис 12.3. Такая архитектура ориентирована, прежде всего, на задачи обработки матриц и обработки изображений.

Схема классического матричного процессора

Рис 12.3

Одной из первых реализаций такой матричной архитектуры была машина ILLIAC - IV, разработанная во второй половине 60-х годов в Иллинойском университете и изготовленная фирмой «Барроуз». Другой пример - разрядно модульный матричный процессор - MPP (Massively Parallel Processor), разработанный фирмой Goodyear по заказу NASA для обработки изображений, передаваемых из космоса.

ЛИТЕРАТУРА

1. Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект: Пер. с японск. - М.: Мир, 1993. - 400 с., ил.

2. Валиев К.А. и др. Развитие элементной базы высокопроизводительных ЭВМ // Информационные технологии и вычислительные системы № 1. - 1996.

3. Ларионов А.М. и др. Вычислительные комплексы, системы и сети / А.М. Ларионов, С.А. Майоров, Г.И. Новиков: Учебник для вузов. Л.: Энергоатомиздат. Ленингр. отд-ние, 1987. 288 с., ил.

4. Принципы работы системы IBM/370: Пер с англ. под ред. Л.Д. Райкова. - М.: Мир, 1978. - 576 с.

5. Пятибратов А.П. и др. Вычислительные системы, сети и телекоммуникации: Учебник. - 2-е изд., перераб. и доп. / А.П. Пятибратов, Л.П. Гудыко, А.А. Кириченко: Под ред. А.П. Пятибратова. - М.: Финансы и статистика, 2001. - 512 с., ил.

6. Смирнов А.Д. Архитектура вычислительных систем. - М.: Наука, 1990.

7. Столлингс В. Структурная организация и архитектура компьютерных систем, 5-ое изд.: Пер. с англ. – М.: Издательский дом "Вильямс", 2002.– 896 с.: ил.

Учебное издание

Ульянов Михаил Васильевич

Архитектуры процессоров

Учебное пособие

__________________________________________________________________

Подписано в печать 02.10.2002

Формат 60 х 80 1/16

Объем 4,25 п.л. Тираж 300 экз. Заказ № 128

Отпечатано в типографии Московской государственной академии

приборостроения и информатики

107846, Москва, ул. Стромынка, 20

Дата добавления: 2015-04-25