Свойства коллективов мв.

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

Параллельный алгоритм.

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

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

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

Лекция 2

Параллельные алгоритмы

Параллельный алгоритм – алгоритм сложной задачи. Использует КМВ. Качество параллельного алгоритма определяется методикой распараллеливания, то есть расчленения ли агентирования сложных задач.

Существует два подхода при распараллеливании задач – локальная и глобальная (крупноблочная)

1)Локально распараллеливание требует расчленения на слишком простые части, элементарные операции, и, как показали исследования не приводят к параллельным алгоритмам, эффективно реализуемых КМВ

2)Глобальное распараллеливание позволяет осуществлять разбиение задачи на крупные блоки, т.е. подзадачи, между которыми существуют слабые связи. Говоря иначе, в алгоритме построенных на основе крупноблочного распараллеливания операция обмена между подзадачами составляют незначительную часть по сравнению с общим числом операций в каждой подзадаче. Такие подзадачи называются ветвями параллельного алгоритма. Все ветви идентичны, это следует из принципа конструктивной однородности КМВ. Каждая ветвь реализуется своей МВ. Распараллеливание по циклам является одним из подходов к крупноблочному распараллеливанию сложной задачи. При этом подходе процесс решения задачи представляется в виде параллельных ветвей, полученных расщеплением цикла на части, число которых в пределе равно числу повторений цикла. На входах и выходах из цикла, параллельный процесс сводится к последовательному процессу вычисления, доля которого, в общем времени незначительна. Говоря иначе, процесс вычислений можно представить в виде периодического повторяющейся кучности параллельных ветвей, перемежающихся узлами – последовательными процессами. На переходе от кучностей к узлам и от узлов к кучностям происходит синхронизация вычислений, обмен информацией между ветвями и управление.

Схемы обмена

Схемы обмена между ветвями параллельного алгоритма при применении крупноблочного распараллеливания сводится к трём типам:

1)трансляционный обмен

2)конвейерно-параллельный обмен

3)диффиринцированный обмен

При трансляционном обмене осуществляется передача одной и той же информации из каждой ветви к другим ветвям. Оно выполняется за два такта: 1)осуществляется передача информации из нечётных ветвей в четыре 2)из чётных в нечётные.

При дифф обмене производится передача информации от данной ветви, к одной из других ветвей. 1,2,3 обмены характерны для многих сложных задач.

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

Опыт распараллеливания сложной задачи показывает, что 1 2 и 4 обмены составляют 90% всех обменов. Относительная простота организации обменов по рассмотренным схемам позволяет создавать простые регулярные структуры системы связи между МВ.

КМВ формально описывается четвёркой:

<C,S,P,A> - где С – множество МВ, S – множество схем объектных взаимодействий, P – множество фаз работы, А – алгоритм функционирования модели.

Р состоит из четырёх фаз: P={Р1,Р2,Р3,Р4}. Р1 связана с конструированием задания. В течении Р2 выполняется обмен информацией между МВ. В течении Р3 осуществляется параллельно выполнение ветвей сложной задачи. Фаза Р4 служит для реализации функции управления модели. Тогда и только тогда условие эффективности модели является неравенством:

t1<<t3

t2<<t3

t4<<t3

где ti – длительность фазы, причём t1<t2<t3<t4. (??????)

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

СОД.

Все виды СОД можно классифицировать следующим образом:

ВК – вычислительный комплекс, ММВК – много машинный ВК, МПВК – многопроцессорный ВК. ВС – Вычислительная система, СТО – системы телеобработки.

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

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

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

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

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

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

Технические средства СОД

Основу СОД составляют ТС, т.е. оборудование, предназначенное для ввода, хранения, конвертирования и вывода данных. Состав ТС определяется структурой или конфигурацией СОД, т.е. тем, из каких частей , элементов состоит система, и каким образом эти части связанны между собой. Математическая форма представления структуры – граф, вершины которого соответствуют элементам системы, а рёбра или дуги – связям между ними. Инженерная форма представления структуры – это схема. Схема и граф тождественные по содержанию и различны по форме. В схеме для изображения элементов используются различные геометрические фигуры, а для изображения связей – линии многих типов, за счет этого схема приобретает большую по сравнению с графом наглядность. Основные элементы структуры СОД это устройства, процессоры, ЗУ, устройства ввода вывода, устройства сопряжения с объектами СОД. Устройства связываются с помощью интерфейсов, включающих в себя совокупность линий или каналов передачи данных.

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

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

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

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

Лекция 3