4.5. НЕТРАДИЦИОННАЯ ОБРАБОТКА ДАННЫХ 4.5.1. ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА

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

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

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

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

Рассмотрим граф, описывающий последовательность процес­сов большой программы (рис. 4.8).

Из рис. 4.8 видно, что выполнение процесса Р$ не может на­чаться до завершения процессов и и, в свою очередь, вы­полнение процессов  не может начаться до завершения процесса Р\ .

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

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

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

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

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

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

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

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

ДЛЯ

 

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

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

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 stre­am), — конвейерная МГТС (рис. 4.12). Система имеет регулярную структуру в виде цепочки последовательно соединенных процес­соров, или специальных вычислительных блоков (СВБ), так что информация на выходе одного процессора является входной ин­формацией для следующего в конвейерной цепочке.

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

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

Структура МКМД (много потоков команд — много потоков данных), или MlMD(Multiple Instruction stream — Multiple Data stream) — представлена на рис. 4.13.

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

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

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

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

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

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

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

В отличие от ограниченного конвейерного функционирова­ния векторного процессора матричный процессор (синоним для большинства  может быть значительно более гиб­

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

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

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

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

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

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

♦ архитектура М1МБ обеспечивает большую гибкость — при наличии адекватной поддержки со стороны аппаратных средств и программного обеспечения         может работать как одно­

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

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

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

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

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

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

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

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

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

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

 

Г—Л ^ Г—л

Г Процессор 1 Г Процессор ] ( Процессор 1 ( Процессор ]

 

Подсистема ввода-вывода

Рис. 4.14. Типовая архитектура мультипроцессорной системы с общей памятью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Необходимость строго последовательно выполнять операции записи также является очень важным условием. Представим себе, что строго последовательное выполнение операций записи не со­блюдается. Тогда процессор Р1 может записать данные в ячейку, а затем в эту ячейку выполнит запись процессор Р2. Строго пос­ледовательное выполнение операций записи гарантирует два важ­ных следствия для этой последовательности операций записи. Во- первых, оно гарантирует, что каждый процессор в машине в не­который момент времени будет наблюдать запись, выполняемую процессором Р2. Если последовательность операций записи не соблюдается, то может возникнуть ситуация, когда какой-нибудь процессор будет наблюдать сначала операцию записи процессо­ра Р2, а затем — операцию записи процессора Р1 и будет хра­нить это записанное процессором Р1 значение неограниченно долго.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Команда наряду с кодом операции содержит поля, куда зано­сятся готовые операнды, и поле, содержащее адреса команд, в которые должен быть направлен в качестве операнда результат

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

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