Архитектура вычислительных систем

Глава 1. Способы организации и типы ВС

8. Каковы области применения  однокристальных ВС?

 

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

Это могут быть:

• системы управления оборудованием (электроприводы, промышленные станки, робототехника, военная и космическая техника).
• устройства сбора и обработки первичной информации (системы сбора информации с датчиков, модули GPS для ввода географических координат, скорости и времени, диагностическое оборудование)
• аудио - , видео, бытовая техника

 

Задача

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

 

Решение:

1. Основное требование - малые физические размеры
2. Низкое энергопотребление
3. Выполнение интенсивных математических вычислений, характерных для алгоритмов цифровой обработки сигналов
4. Компактное программное обеспечение, возможно ПО будет записано («прошито») в микросхемы ПЗУ (или ППЗУ) на этапе производства и без возможности изменения.
5. Поддержка внешней flash памяти
6. Невысокая цена

 

Глава 2. Параллельная обработка информации.

8. Как была устроена коммутирующая  сеть ВС ILLIAC IV, в чем заключались  ее достоинства и недостатки?

 

ILLIAC IV – векторная суперЭВМ с матричной структурой. ILLIAC IV создана Иллинойским университетом и корпорацией Бэрроуз (Burroughs Corporation). Работы по созданию ILLIAC IV выполнялись под руководством Д. Л. Слотника и были начаты в 1966 г. в Иллинойском университете. Монтаж системы был закончен в мае 1972 г. в лаборатории фирмы Burroughs (Паоли, штат Панама), а установка для эксплуатации осуществлена в октябре 1972 г. в Научно-исследовательском центре НАСА им. Эймса (NASA’s Ames Research Center, штат Калифорния).

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

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

В квадранте 64 ПЭ образуют матрицу размером 8Х8. Реально действующая система ILLIAC-IV состоит, таким образом, из двух частей; центральной с устройством управления и 64 ПЭ, а также подсистемы ввода - вывода, включающей в себя универсальную ЭВМ В-6700, файловые диски и лазерную архивную память большой емкости. Каждый ПЭ состоит из собственно процессора и ОЗУ. Процессор оперирует с 64-разрядными числами и выполняет универсальный набор операций. Быстродействие процессора достаточно высокое: операция сложения 64-разрядных чисел выполняется за 240 нс, а умножения - за 400 нс. Таким образом, процессор выполняет в среднем 3 млн. операций в секунду, а следовательно производительность системы равна ЗХ64 200 млн. операций в секунду.

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

 Каждый процессор  кроме индексного регистра имеет  в своем составе пять программно-адресуемых  регистров: накапливающийся сумматор, регистр для операндов, регистр пересылок, используемый при передачах от одного ПЭ к другому, буферный регистр на одно слово и регистр управления состоянием ПЭ. Регистр управления имеет 8 разрядов. В зависимости от содержимого этого регистра ПЭ становится активным или пассивным, а также выполняет ряд пересылочных операций. Если вычисления не требуют полной разрядности, то процессор может быть разбит на два 32-разрядных подпроцессора или даже восемь 8-раэрядных. Это позволяет в случае необходимости обрабатывать векторные операнды из 64, 2Х64=128 и 8Х64=512 элементов.

 

Недостатки системы :

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

 

 

2. Не любая задача могла быть эффективно решена на данной системе. При построении параллельных алгоритмов необходимо было учитывать, что система ILLIAC IV управлялась одним потоком команд, т.е. структура системы позволяла одновременно выполнять одинаковые операции над 64 множествами данных, записанных в памяти различных ЭП. Следовательно, эффективные параллельные алгоритмы могли быть построены только для тех трудоемких задач, решение которых было связано с многократными вычислениями одной и той же функции для различных значений аргументов. Таких, например, как операции над матрицами, быстрое преобразование Фурье, линейное программирование, обработка сигналов, где как раз имеет место параллелизм данных или параллелизм независимых объектов.

 

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

 

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

 

 

 

Задачи

Задача 1.

МЗП клеточно-автоматная модель простейшего сумматора состоит из клеточного объекта - поля значений и двух правил: правило сложения и переноса и правило подъема. Клеточный объект в данном случае - это двумерный массив, элементами которого может быть 0 или 1. Строки клеточного объекта содержат двоичные представления чисел, которые сумматор должен сложить. Правила определяют, каким образом будут вычисляться новые значения ячеек клеточного массива. Каждое правило имеет правую и левую части. Правая часть означает условие применимости, а левая - новое значение после срабатывания правила.

 

Правило сложения и переноса:

 

x1      x0

01 -> 10

00      xx

 

(x в левой части означает, что  значение клетки на поле может  быть любым, x в правой части  означает, что правило не изменяет  значение клетки в соответствующей  позиции на поле)

 

Правило подъема:

 

0      1

1 --> 0

0      0

 

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

 

Исходные данные:

0000011

0000111

0001111

0000001

0000000

0000000

0000000

 

Решение:

 

Условные обозначения:

• Участок поля 2x3, обведенный жирной рамкой – участок, к которому на данном шаге применимо правило сложения и переноса
• Участок поля 1x3, закрашенный серым цветом – участок, к которому на данном шаге применимо правило подъема.

 

После шага 6 применимых правил больше нет – получили результат работы сумматора.

 

Задача 2.

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

 

Правило оконтуривания:

 

ijk       xxx

lmn -> xfx

opq      xxx

 

где в левой части правила указаны девять переменных, принимающих значения из сооветствующей клетки клеточного массива, а x - не изменяет значение клетки в соответствующей позиции на поле, а f вычисляется по формуле:

 

f = (m != i) или (m != j) или(m != k) или (m != l) или(m != m) или (m != n) или(m != o) или (m != p) или(m!= q)

 

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

 

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

 

00000000000000000000000000000000

00000000000000000000000000000000

00000000000001111000000000000000

00000000000001111000000000000000

00000000000001111000000000000000

00000000000001111000000000000000

00000000011111111111100000000000

00000000011111111111100000000000

00000000011111111111100000000000

00000000011111111111100000000000

00000000000001111000000000000000

00000000000001111000000000000000

00000000000001111000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

 

Решение:

Условные обозначения:

Ячейка клеточного поля, которая содержит 0 обозначена черным цветом.

Ячейка клеточного поля, которая содержит 1 обозначена белым цветом.

 

Тогда исходное состояние системы можно представить рисунком1:

 

Рис.1

 

Результат применения правила оконтуривания система представлен на рисунке2.

 

 

 

 

 

 

 

Рис2.

 

Глава 3. Конвейерная архитектура.

8. Какие существуют способы предсказания  ветвления и чем они отличаются?

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

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

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

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

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

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

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

Алгоритмы "динамического предсказания ветвлений" обычно задействуют одну из таблиц - для хранения истории предсказаний ветвлений (Branch History Table, BHT) или для хранения адресов инструкций (Branch Target Buffer, BTB). Либо используется сразу оба типа таблиц.

Примером динамического предсказания может служить двухуровневый адаптивный исторический алгоритм (англ. Bimodal branch prediction), использовавшийся процессорами архитектуры P6 (анализируется таблица истории переходов, содержащая младшие значимые биты адреса инструкции и соответствующую им вероятность условного перехода: «скорее всего, будет выполнен», «возможно, будет выполнен», «возможно, не будет выполнен», «скорее всего, не будет выполнен» и обновляемая после каждого перехода).

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

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

Задача

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

 

Исходные данные:

A=240 нс

B=80 нс

C=4

 D=50

 

Решение:

1.Вычисляем время исполнения на ВС с неконвейерной архитектурой. Так как программа линейная (не содержит переходов), оно равно произведению числа инструкций на время исполнения одной инструкции: T1 = A * D.