Имя материала: Информационные системы и технологии в экономике

Автор: Т.П. Барановская

4.5. нетрадиционная обработка данных

 

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

 

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

Для распараллеливания необходимо соответствующим образом организовать вычисления. Сюда входит следующее:

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

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

Рассмотрим описывающий последовательность процес-

сов большой программы (рис. 4.8).

Из рис. 4.8 видно, что выполнение процесса Р$ не может на-

чаться до завершения процессов и и, в свою очередь, вы-

полнение процессов         не может начаться до завершения

процесса Р .

В данном случае для выполнения программы достаточно трех процессоров.

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

При автоматическом обнаружении параллельных вычислений мы различаем в последовательной программе возможность явной и скрытой параллельной обработки. Хотя в обоих случаях требуется анализ программы, различие между этими видами об"-работки состоит в том, что скрытая параллельная обработка требует некоторой процедуры преобразования последовательной программы, чтобы сделать возможным ее параллельное выполнение. При анализе программы строится граф потока данных. Чтобы обнаружить явную параллельность процессов, анализируются множества входных (считываемых) переменных R (Read) и выходных (записываемых) переменных W(Write) каждого процесса. Два процесса i, j (ioj) могут выполняться параллельно при следующих условиях:

 

RiCWj =0;

 

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

 

4.5.2.   КОНВЕЙЕРНАЯ ОБРАБОТКА

 

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

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

применяет эти ресурсы заранее предусмотренным способом. Хо-

рошим примером конвейерной организации является сборочный

транспортер на производстве, на котором изделие последователь-

но проходит все стадии вплоть до готового продукта. Преиму-

щество этого способа состоит в том, что         изделие на своем

пути использует одни и те же ресурсы, и как только некоторый

ресурс освобождается данным изделием, он сразу же может быть

использован следующим изделием, не ожидая, пока предыдущее

изделие достигнет конца сборочной линии. Если транспортер не-

сет аналогичные, но не тождественные изделия, то это последо-

вательный конвейер; если же все изделия одинаковы, то это век-

торный конвейер.

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

Ускорение обработки в данном устройстве измеряется отношением времени Ts, необходимого для последовательного выполнения L заданий (т.е. выполнения L циклов на одной обрабатывающей ступени), ко времени Тр выполнения той же обработки на конвейере. Обозначим через /, время обработки на г-й ступени, а через /у — соответствующее время для самой медленной ступени (рис. 4.9,6). Тогда, если L заданий (команд) проходят через конвейер с п ступенями, эффективность конвейера определяется выражением

 

L5>

J п

р Х'<+(і-1)?/

и

 

-    ■> nL

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

Типичное использование векторного конвейера — это процесс, вырабатывающий по двум исходным векторам А и В результирующий вектор С для арифметической операции С <— А +В. В этом случае на конвейер поступает множество одинаковых команд.

 

4.5.3. КЛАССИФИКАЦИЯ АРХИТЕКТУР ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

 

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

Удачной признана классификация Флина, которая строится по признаку одинарности или множественности потоков команд и данных [21].

Структура     (один поток команд — один поток данных),

или SISD (Single Instruction stream — Single Data stream), — однопроцессорная ЭВМ (рис. 4.10).

Структура ОКМД (один поток команд, много потоков данных), или SIMD (Single Instruction stream, Multiple Data stream), — матричная многопроцессорная система. МПС содержит некоторое число одинаковых и сравнительно простых быстродействующих процессоров, соединенных друг с другом и с памятью данных таким образом, что образуется сетка (матрица), в узлах которой размещаются процессоры (рис. 4.11). Здесь возникает сложная задача распараллеливания алгоритмов решаемых задач для обеспечения загрузки процессоров. В ряде случаев эти вопросы лучше решаются в конвейерной системе.

Структура МКОД (много потоков команд — один поток данных), или MISD (Multiple Instruction stream — Single Data stream), — конвейерная МГТС (рис. 4.12). Система имеет регулярную структуру в виде цепочки последовательно соединенных процессоров, или специальных вычислительных блоков (СВБ), так что информация на выходе одного процессора является входной информацией для следующего в конвейерной цепочке.

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

Структура МКМД (много потоков команд — много потоков

данных), или            (Multiple Instruction stream — Multiple Data

stream) — представлена на рис.

Существует несколько типов МКМД. К ним относятся: мультипроцессорные системы, системы с мультиобработкой, машинные системы, компьютерные сети.

 

4.5.4. ТИПЫ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМ

 

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

Можно выделить четыре типа архитектуры систем параллельной обработки.

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

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

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

В отличие от ограниченного конвейерного функционирова-

ния векторного процессора матричный процессор (синоним для

большинства           может быть значительно более гиб-

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

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

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

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

4. Многопроцессорные машины с SIMD-процессорами. Многие современные суперЭВМ представляют собой многопроцессорные системы, в которых в качестве процессоров используются векторные процессоры, или процессоры типа SIMD. Такие машины относятся к машинам класса MSIMD.

Многопроцессорные системы за годы развития вычислительной техники прошли ряд этапов. Исторически первым стало освоение технологии SIMD. Однако в настоящее время наметился устойчивый интерес к архитектурам MIMD. Этот интерес главным образом определяется двумя факторами:

• архитектура MIMD обеспечивает большую гибкость — при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения         может работать как одно-

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

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

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

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

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

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

Многопроцессорные системы с общей памятью. К этой группе относятся машины с общей (разделяемой) основной памятью, объединяющие до нескольких десятков (обычно менее 32) процессоров. Сравнительно небольшое количество процессоров в таких машинах позволяет иметь одну централизованную общую память и объединить процессоры и память с помощью одной шины. При наличии у процессоров кэш-памяти достаточного объема высокопроизводительная шина и общая память могут удовлетворить обращения к памяти, поступающие от нескольких процессоров. Поскольку при этом имеется единственная память с одним и тем же временем доступа, эти машины иногда называются UMA (Uniform Memory Access). Такой способ организации со сравнительно небольшой разделяемой памятью в настоящее время является наиболее популярным. Архитектура подобной системы представлена на рис. 4.14.

Требования, предъявляемые современными процессорами к

быстродействию памяти, можно существенно снизить путем при-

менения больших многоуровневых кэш-модулей. При этом не-

сколько процессоров смогут разделять доступ к одной и той же

памяти. Начиная с 1980 г. эта идея, подкрепленная широким рас-

пространением микропроцессоров, стимулировала многих раз-

работчиков на создание небольших мультипроцессоров, в кото-

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

соединенную с ними с помощью разделяемой шины. Из-за мало-

го размера процессоров и заметного сокращения требуемой по-

лосы пропускания шины, достигнутого за счет возможности реа-

лизации достаточно большой кэш-памяти, такие машины стали

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

шению "стоимость / производительность". В первых разработ

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

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

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

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

протоколы на основе справочника (directory based). В этом случае информация о состоянии блока физической памяти содержится только в одном месте — справочнике (физически справочник может быть распределен по узлам системы);

протоколы наблюдения (snooping). При этом каждый кэш-мо-

дуль, который содержит копию данных некоторого блока физи-

ческой памяти, имеет также соответствующую копию служебной

информации о его состоянии.   система запи-

сей отсутствует. Обычно кэш-модули   на общей

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

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

Неформально проблема когерентности кэш-памяти состоит в

необходимости       что любое считывание элемента

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

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

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

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

Необходимость строго последовательно выполнять операции

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

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

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

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

ледовательное выполнение операций записи гарантирует два важ-

ных следствия для этой последовательности операций записи. Во-

первых, оно гарантирует, что каждый процессор в машине в не-

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

процессором Р2. Если последовательность операций записи не

соблюдается, то может возникнуть ситуация, когда какой-нибудь

процессор будет наблюдать сначала операцию записи процессо-

ра Р2, а затем —     записи процессора Р1 и будет хра-

нить это записанное процессором Р1 значение неограниченно

долго.

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

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

ров, которые удается поддерживать на           разделяемой шине

и общей памяти.

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

Обычно устройства ввода-вывода, так же как и память, рас-

пределяются по узлам, и в действительности узлы могут состоять

из небольшого числа        процессоров, соединенных между со-

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

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

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

Машины с архитектурой, подобной Cray T3D, называют процессорами (машинами) с массовым параллелизмом (МРР — Massively Parallel Processor). К машинам с массовым параллелизмом предъявляются взаимно исключающие требования. Чем больше объем устройства, тем большее число процессоров можно расположить в нем, тем длиннее каналы передачи управления и данных, а значит, меньше тактовая частота. Происшедшее возрастание нормы массивности для больших машин до 512 и даже 64000 байт процессоров обусловлено не увеличением размеров машины, а повышением степени интеграции схем, позволившей за последние годы резко поднять плотность размещения элементов в устройствах. Топология сети обмена между процессорами в такого рода системах может быть различной.

Для построения крупномасштабных систем может служить

протокол на основе справочника, который отслеживает состоя-

ние кэш-памяти. Такой подход предполагает, что логически еди-

ный справочник хранит состояние каждого блока памяти, кото-

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

информация о том, в какой кэш-памяти имеются копии данного

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

реализациях этого направления справочник размещается рядом с

кэш-памятью. Имеются также протоколы, в которых часть ин-

формации размещается в самой кэш-памяти. Положительной сто-

хранения всей информации в едином справочнике являет-

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

информация сосредоточена в одном месте. К недостаткам такого

рода справочников относится их размер, который пропорцио-

нален общему объему памяти, а не размеру кэш-памяти. Это не

создает проблемы для машин, состоящих, например, из несколь-

ких сотен процессоров, поскольку связанные с реализацией тако-

го справочника накладные расходы можно считать приемлемы-

ми. Но для машин  размера необходима методика, по-

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

 

4.5.5.  КОНЦЕПЦИЯ  ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ С УПРАВЛЕНИЕМ ПОТОКОМ ДАННЫХ

 

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

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

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

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

Потоковая программа размещается в массиве ячеек команд (рис. 4.16).

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

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 |