Краткий_Курс, страница 2

Потоковая архитектура (data-flow) вычислительных систем обеспечивает интерпретацию алгоритмов на графах, управляемых данными. Идеи потоковой обработки информации, организации вычислений, управляемых потоками данных можно рассмотреть на примере организации ввода и суммирования трех чисел. Традиционная схема вычислений может быть представлена так: ввод (а); ввод (в); ввод (с); s = a+b; s = s+c;

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

ввод (а) ввод (в) ввод (с)

а+в а+с в+с

(в+с)+а (а+с)+в (а+в)+с

Здесь, начальные вершины - ввод, затем каждое введенное данное размножается на три и они передаются на вершины, обеспечивающие суммирование. Теперь, любом порядке поступления данных отсутствуют задержки вычислений для получения результата. Data-flow программы записываются в терминах графов. В вершинах графа находятся команды, состоящие, например, из оператора, двух операндов (для двуместных операций), возможно, литеральных, или шаблонов для заранее неизвестных данных и ссылки, определяющей команду - наследника и позицию аргумента в ней для результата. Для фрагмента программы, вычисляющего оператор: a=(b+1)*(b-c), команды могут иметь вид:

L1:(+(<b>) “1” L3/1)

L2:(-(<b>) (<c>) L3/2)

L3:(*( ) ( ) <a>)

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

5.1. Классическая архитектура потоковой ВС.

Основными компонентами потоковой ВС являются:

- память команд (ПК),

- селекторная (арбитражная) сеть,

- множество исполнительных (функциональных) устройств (ФУ),

- распределительная сеть.

_______________

|--------------->| ФУ |-----------------|

| | ______________| |

| |

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

| ______________ |

|<---------------| ПК |-----------------|

|______________|

Память команд состоит из "ячеек" активной памяти, каждая из которых может содержать одну команду вида <метка>: <операция>,<операнд1>,..,<операндК>,<адр_рез1>,..,<адр. _рез.М>, где адреса результатов являются адресами ячеек памяти. С каждой командой связан подсчитывающий элемент, непрерывно ожидающий прибытие аргументов, который пересылает команду на выполнение при наличии полного комплекта аргументов. Активных характер памяти заключается в том, что ячейка, обладающая полным набором операндов, переходит в возбужденное состояние и передает в селекторную сеть информационный пакет, содержащий необходимую числовую и связующую информацию о команде.

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

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

Потоковая архитектура (data-flow), как одна из альтернатив фон-Нейманновской, обладает следующими характерными чертами:

- отсутствие памяти как пассивного устройства, хранящего потребляемую информацию,

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

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

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

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

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

4. Языки программирования для потоковых машин существуют, в основном, в виде графических языков машинного уровня. Языки типа SISAL, ориентируемые на описания потоковых алгоритмов, достаточно сложны для программистов.

6. Ассоциативная память

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

1924021

9448304

3336167

Для получения номера телефона второго абонента следует обратиться: load (2) и получить в регистре ответа R = 9448304. Такой вид памяти, при котором необходимая информация определяется номером строки памяти, называется адресной. Другой вид оперативной памяти – ассоциативной можно рассматривать также как двумерную таблицу, но у каждой строки которой есть дополнительное поле, поле ключа. Например:

Ключ Содержимое

Иванов 1924021

Петров 9448304

Сидоров 3336167

После обращение к ассоциативной памяти с запросом : load (Петров) для данного примера получим ответ: R = 9448304. Здесь задание координаты строки памяти производится не по адресу, а по ключу. Но при состоянии ассоциативной памяти:

Ключ Содержимое

1 1924021

2 9448304

3 3336167

можно получить номер телефона из второй строки запросом: load (2). Таким образом на ассоциативной памяти можно моделировать работу адресной. Ассоциативная память имеет очевидное преимущества перед адресной, однако, у нее есть большой недостаток - ее аппаратная реализация невозможна для памяти большого объема.

ВОПРОС !!!! Предложите схему реализации модели ассоциативной памяти при помощи адресной.

7. Адресация памяти

Адресация памяти производится с точностью до байта, длина адреса, его разрядность, определяет пространство памяти, которое может быть доступно ("видимо") в программе. Так 32 рр. виртуальный адрес охватывает пространство в 4 Гбай­та. Это виртуальное пространство - математическая память программы мо­жет не совпадать с реальным, физическим пространством памяти ЭВМ.

Адреса виртуального пространства памяти - виртуальные ад­реса, а адреса физического пространства - физические адреса.

Механизм виртуальной памяти позволяет:

- снять ограничения, связанные с объемом памяти, при раз­работки алгоритмов;

- предоставлять программисту область памяти в виде логи­чески непрерывного пространства;

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

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

Виртуальный адрес Физический адрес

а б - > с б

Аппаратно трансляция адресов производится при помощи таблицы страниц. Каждой страни­це виртуальной памяти соответствует строка в таблице страниц, объем которой соответствует числу страниц виртуальной памяти. В i строке таблицы хранится: N страницы (блока) физической па­мяти, которая соответствует данной виртуальной, статус доступа (чтение, запись), признак записи. Полный физический адрес получается добавлением к физи­ческому адресу, полученного из таблице страниц, смещения внутри страницы (б). Реальная структура таблицы страниц имеет более сложный вид.

8 Чередование адресов(расслоение) памяти (interleaved memory)

Расслоение памяти: память делится на М банков с автономным управлением так, что при последовательной выборки повторное обращение к одному банку произойдет через М обращений, поэтому возможно совмещение вре­мени выборки. Для банков одинаковой емкости:B1,B2,B3,..Bm-1 адрес i трансформируется в адрес d внутри банка Bb расчетом:

i=d * m + b, где d=>0, 0<=b<=m-1

При расслоении на четыре распределение адресов в банках будет:

Адреса в банках-b Банк 1 Банк 2 Банк 3 Банк 4

0 0 1 2 3 Распределение

1 4 5 6 7 адресов i

2 8 9 10 11

При конвейерном доступе при М-кратным расслоении и регулярной выборке доступ к памяти возможен в ин­тервале 1/М цикла памяти. Но возможны конфликты по доступу, если шаг регулярной выборки коррелируется с числом банков памяти.

9. Назначение и структура кэш-памяти.

Для ускорения доступа к оперативной памяти используется буферизация данных и объектного кода в памяти, скорость которой значительно выше основной. Если бы доступ к любым типам данных был случайным, то буферизация была бы бесполезным. Эффект от буферизации можно определить среднему времени выборки: t = t2*p+ t1*(1-p), где t1 - среднее время доступа к данным основной памяти, t2 - среднее время доступа к данным из буфера (t2<t1), p - вероятность наличия данного в буфере. Очевидно, среднее время зависит от вероятности р и изменяется от среднего времени доступа к основной памяти (при p=0) до среднего времени доступа непосредственно в буфер (при p=1). Кэш (cache, cache memory) память, как правило, на порядок более быстрая, чем основная, размещается в качестве буферной, между процессором и основной памятью и служит для временного хранения (в рамках своего объема) всех данных, потребляемых или генерирумых процессором. В много-уровневых кэшах элементами связки: "процессор - основная память" могут выступать сами кеши. Алгоритм кэширования состоит в следующем:

1. По каждому запросу процессора происходит поиск требуемого дан­ного в кэш памяти (места для записи генерируемого данного).

2. Если данное (место) есть в кэше - кэш попадание (cache hit), то оно передается в процессор (из процессора).

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

Традиционным кэшем является "процессорный" кэш или кэш первого уровня (первичный) или кэш (L1 Cache), имеющийся на любом микропроцессоре. Это буферная память объемом от 4 Кбайт до 16 Мбайт, в которой размещаются все данные, адресуемые процессором, и из которой данные поставляются процессору. Эта память значительно быстрее основной, но меньшего объема, поэтому механизм кэширования обеспечивает обновление кэша, обычно, сохраняя в нем только наиболее часто употребляемые дан­ные. Обмен между основной и кэш памятями производится квантами, объ­емами 4 - 128 байт - копируются "строки кэша" (cache line), содержа­щие адресуемое данное.

Обычно, программный код кешируется через особый, I кэш память, отделенной от кэша данных D-кэша. Выборка данных из кэша (hit time) прозводится, обычно, за один такт синхронизации (оценки 1 - 4 такта), потери при кеш промахе оцени­ваются в 8 - 32 такта синхронизации, доля промахов (miss rate) - 1% -20%. По определению, эффект кэширования основан на предположении о многократном использовании данных (Data reuse) из кэш памяти. Принято различать две формы многократного использования данных кэша:- временное использование (temporal reuse). - пространственное использование (spatial reuse). Временное использование означает, что некоторое данное, загружен­ные в кэш, может использоваться, по крайней мере, более двух раз. Пространственное использование кэша предполагает возможность ис­пользовать некоторый пространственный набор данных - строки кэша. Архитектура кэш памяти: полностью ассоциативная, частично ассоциативная и кэш память с прямым отображением.

10. Кэш память с прямым отображением.

Архитектура кэш-памяти с прямым отображением (direct-map­ped) характеризуется на­личием явной зависимости между адресами буферной и оперативной памяти, причем каждому адресу кэша соответствует адреса оперативной памяти, кратные размеру кэш памяти. Память кэша состоит их памяти данных и памяти тэгов. Пусть, длина строки кэша равна 32 байтам, размер кэша – 4 Кбайт, тогда кэш память для данных состоит из 128 строк. ОЗУ разделено на блоки, размером в 4Кбайт, каждый содержит 128 строк. В нулевой строке кэша может быть размещены 0 или 128, или .... строки ОЗУ, в первой – 1 или 129 или.. строки т и.д. Для каждой заполненной строки данных кэша известен тэг – номер блока ОЗУ, которому принадлежит строка. Тэги хранятся в специальной памяти - памяти тэгов, размер которой – 128 строк. Длина строки памяти тэгов зависит от размера ОЗУ. Если объем ОЗУ – 4 Гбайт, тогда полный адрес - 32 бита можно представить в виде полей: 20 рр – тэг (T), 7 рр – номер строки таблиц кэша (S), 5 рр – номер байта в строке (N). Поиск запрошенного байта (T-S-N) в кэше с прямым распределением производится так: