Критерий существования целевой архитектуры

ЧАСТЬ II . МОДЕЛИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

РАЗДЕЛ 5. ВЫБОР ЦЕЛЕВОЙ АРХИТЕКТУРЫ

Отображение программы на ресурсы

Спецификация программы и ее представление целевой архитектурой. Во Введении и разделе 1 мы уже говорили о том, что масштабирование архитектуры может пониматься не только как наращивание вычислительных ресурсов, но и как их конфигурирование под конкретные приложения с целью повышения эффективности выполнения программ. Разумеется, здесь идет речь о сложных приложениях, состав которых априори известен, не изменяется в течение длительного времени функционирования системы и для выполнения которых необходимо эффективное использование дорогостоящих аппаратных платформ. Нужно сказать, что существуют различные взгляды на то, что считать компьютерной архитектурой. Так, в свое время Г. фон Блаау, один из разработчиков вычислительной системы IBM 360, определил архитектуру как функциональное проявление свойств системы с точки зрения пользователя. В этом курсе под архитектурой мы понимаем те аспекты компьютерной организации, которые видны программисту.

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

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

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

Спецификация Решетка процессоров ( )

Рис. 5.1. Отображение спецификации на целевую архитектуру

Рассмотрим некоторые примеры описаний архитектуры. Положим, семейство образовано признаками, являющимися способами организации потока команд и потока данных, а именно, , . Здесь и обозначают одиночный и множественный потоки команд, а – соответственно одиночный и множественный потоки данных. Тогда классификация архитектур вычислительных систем по Флинну может быть охарактеризована следующими наборами архитектурных признаков: , , , . В свою очередь, набор – частичное описание архитектур класса Multiple SIMD (MSIMD).

Сюда относят нейрокомпьютеры и некоторые векторные системы типа Cray Y-MP, состоящие из нескольких векторных процессоров, которые часто причисляют к SIMD-компьютерам. (Следует, правда, заметить, что ряд исследователей располагает векторно-конвейерные компьютеры, в частности, упомянутый Cray Y-MP, в другом классе – MIMD.) По аналогии можно описать и другие известные классификации. Так, по Фенгу описание архитектуры может быть задано парой признаков: числом разрядов машинного слова и числом одновременно обрабатываемых слов. Классификация Хендлера предполагает описание архитектуры тройкой признаков, обозначающих количество устройств управления, число арифметико-логических устройств в каждом из устройств управления и число групп элементарных логических схем в арифметико-логическом устройстве. Подобным же образом, на основе семейства архитектурных признаков и их наборов возможно представить классификации Шнайдера и Скилликорна.

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

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

а) б)

в)

Рис. 5.2. Спецификация (а) и различные способы ее представления (б, в)

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

– – вычисление соответственно на отдельном или том же вычислительном блоке, что и ;

– – вычисление каждого из значений на отдельном блоке; – повторное использование блока для вычисления ;

– – подсчет числа итераций на отдельном блоке; – подсчет итераций на блоке для вычислений и ; – вычисление индекса после вычисления , ; – отсутствие подсчета числа итераций.

Наборам ( ) и ( ) могут быть сопоставлены различные разбиения строк спецификации и , которые, в свою очередь, характеризуют различные способы вычисления – циклический (рис. 5.2, б) и конвейерный (рис. 5.2, в). Заметим, что при втором способе вычислений подсчет числа итераций отсутствует, а значения X на соседних стадиях вычислений с нулевой по четвертую могут различаться (поэтому на рис. 5.2, в показано пять различных дуг, обозначенных X). Далее, вышеприведенные наборы признаков описывают различные структуры – с повторным использованием вычислительных блоков (рис. 5.3, а) и конвейерную (рис. 5.3, б).

a) б)

Рис. 5.3. Реализация вычисления различными структурами

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

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

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

Локализация области поиска целевой архитектуры. Некоторое начальное разбиение спецификации может осуществляться разработчиком неформально, "вручную". При этом приходится рассматривать не один, а несколько вариантов разбиения. В общем случае количество вариантов разбиения не меньше числа сюръективных функций из на , т.е. , где . Здесь – число Стирлинга второго рода, умноженное на ! Практически число допустимых разбиений, конечно же, значительно меньше . Тем не менее с каждым из вариантов связывается свое семейство множеств архитектурных признаков. При этом в наборах , ..., одноименные компоненты ; ... ; в общем случае различны. Так, с вышерассмотренными разбиениями и спецификации , приведенной на рис. 5.2, а, могут ассоциироваться следующие семейства признаков: , . В этом случае описание должно представлять собой общую трансверсаль для семейств . Например, набор является общей трансверсалью семейств и , при этом ему может быть сопоставлено разбиение . В представляемой такими описанием и разбиением целевой архитектуре вычисления начального приближения , текущего значения и подсчет числа итераций выполняются на трех отдельных блоках, что отличает этот вариант от структуры на рис. 5.3, а. При этом вычисление производится итеративно на одном и том же арифметико-логическом устройстве, подобно тому, как это показано на рис. 5.3, а, с той лишь разницей, что арифметико-логическое устройство должно реализовывать функции сложения и деления.

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

Подробнее изложим суть этой идеи на следующем примере.

Рис. 5.4. Пример структуры многопроцессорной системы

Предположим, что многопроцессорная система, структура которой показана на рис. 5.4, предназначена для решения задач, допускающих крупноблочное распараллеливание на относительно независимые подзадачи по не идентичным вычислителям . Для коммутации данных используется системный интерфейс (СИ). Идея реализации распараллеливания задач по вычислителям заключается в следующем. Каждый из них работает по своей циклограмме, задаваемой препроцессором форматирования (ПФ). Таким образом, , где , "распознает" данные из общего потока к абонентам или от абонентов, предназначенные для обработки на вычислителе . По Флинну эту систему можно отнести к классу MIMD. В каждом из вычислителей, помимо препроцессора форматирования, имеются вычислительный модуль (ВМ), структура которого уже рассматривалась в п. 4.1 раздела 4 (см. рис. 4.5); блок памяти (БП) и, в случае децентрализованного управления обменом с системным интерфейсом, процессор обмена (ПОбм). От соответствующего препроцессора форматирования в блок обработки (БО) поступают данные в определенном формате. На рис. 5.4: БР – буферный регистр, ЛОП – локальная оперативная память, ПДП – блок прямого доступа к памяти. Таким образом, за каждым вычислителем закрепляется своя задача, обмен данными между вычислителями реализуется через системный интерфейс и общую память.

В архитектуре системы предусмотрены три типа препроцессорной обработки (см. рис. 5.4):

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

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

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

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

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

1) , где – разделение, – совместное использование и – биноминальное резервирование каналов данных (соответствующие группы вычислителей обозначим через Р, С и Б);

2) , где обозначает наличие, а – отсутствие буферизации;

3) , где – пословный обмен, а – обмен блоками слов с системным интерфейсом;

4) , где – обработка слова сразу после формирования, – обработка соответственно перед буферизацией и после считывания из буфера (блока памяти), – обработка до и после буферизации;

5) , где обозначают соответственно централизованное и децентрализованное управление.

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

1) ; 2) ; 3) .

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

Тогда подмножество разрешенных частичных описаний вычислителей представляется следующим образом:

Р ;

;

Знак соответствует любому из признаков , (группам Р, С, Б), а знак · соответствует признакам (группам С, Б).

В соответствии с описаниями на уровне наиболее значимых архитектурных признаков выделяются три группы вычислителей, в каждой из которых содержится 7 подклассов архитектур: Р1,...Р7; С2,..., С8; Б2,..., Б8. В каждом из подклассов реализуется свой тип циклограмм для обработки заданий, соответствующих функциям архитектуры. Для примера на рис. 5.5 показаны две разновидности циклограмм в архитектурах Р3, С3 и Б3, соответствует крайнему сроку завершения обработки, а – крайнему сроку завершения отдельных действий, длительность которых в общем случае является случайной величиной.

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

а)

б)

Рис. 5.5. Циклограммы заданий в архитектурах Р3, С3, Б3

Поэтому исследование пространства архитектурных решений требует специальных инструментальных средств. В начале 90-х годов прошлого столетия на кафедре вычислительной техники МЭИ была начата разработка системы GSSS (Generalized Structure Synthesis System). Со времени анонсирования одной из ее первых версий 1 система GSSS существенно развита и прошла апробацию в ряде проектов. Одна из возможностей этого инструментария – сравнительный анализ различных типов целевых архитектур на основе обобщения экспертных знаний. В качестве примера на рис. 5.6 показано расположение вариантов вычислителей с разделением каналов (группа Р) в пространстве ( ), где и представляют соответственно относительные затраты на реализацию аппаратной платформы и сложность программного кода в некоторых условных единицах. Так, относительная сложность кода изменяется от одной единицы до четырех, относительные затраты на аппаратуру не превышают 8 единиц, а крайний срок не больше 8 единиц времени.

а)

б)

Рис. 5.6. К анализу пространства архитектурных решений

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

На рис. 5.6, а это – вычислители подкласса Р3 в соответствующем диапазоне изменения крайнего срока завершения программы. На рис. 5.6, б не показано расположение вариантов архитектуры Р6, поскольку при той же производительности, что и для Р3, в соответствии с ее описанием необходимы дополнительные затраты на процессор обмена. Попытки добиться незначительного повышения производительности, обеспечиваемого архитектурой типа Р3 (см. рис. 5.6, а), требуют перехода в другие подклассы архитектур (Р1, Р2, Р4) и приводят к существенному росту аппаратурных затрат.

Другая практически ценная возможность системы GSSS, которая и позволяет упорядочить архитектурные признаки по значимости, это – определение долей относительных аппаратурных затрат на реализацию различных функций архитектуры. На рис. 5.7 показана диаграмма распределения затрат для архитектуры подкласса Р3 (см. рис. 5.6, а) в зависимости от крайнего срока и относительной сложности программного кода. На рис. 5.7 , – диапазоны изменения крайнего срока выполнения кода для двух разных значений его относительной сложности .

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

Рис. 5.7. Диаграмма распределения относительных затрат на реализацию функций архитектуры Р3

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

Весьма перспективным здесь может быть использование генетических алгоритмов, которые обладают рядом свойств, необходимых для решения задачи выбора архитектуры вычислительной системы. Чуть позже мы охарактеризуем эти полезные свойства, а сейчас на примере алгоритма Холланда SGA (simple genetic algorithm) опишем основные понятия и схему генетического алгоритма.

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

Схема алгоритма SGA включает следующие действия.

1.° Генерация случайным образом популяции.

2.° Вычисление функции выживаемости для каждой из строк популяции.

3.° Выполнение селекции – отбора строк популяции.

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

5.° Мутация с некоторой вероятностью символов, кодирующих решение, например, битов строки.

6.° Если критерий останова достигнут, то завершение работы, иначе переход к действию 2°.

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

Р4= ;

Р5= ;

Р6= .

Эти описания соответствуют группе вычислителей с разделением каналов данных (признак ). В архитектуре Р4 осуществляется обмен словами (признак ), а в архитектуре Р5 и Р6 – блоками слов (признак ). Выполним точечное скрещивание наборов Р4 и Р6 таким образом, что происходит обмен признаками обработки и . В результате генерируется новая популяция, включающая описания Р3= и Р7= . Положим, функция выживаемости – это относительные аппаратурные при заданных относительной сложности кода и крайнем сроке . Если , а , то существует вариант Р3, явно лучший варианта Р4 по аппаратурным затратам примерно при той же производительности (см. рис. 5.6, а). А вот решение Р7 (см. рис. 5.6, б) хуже решения Р5, поскольку требует дополнительного процессора для организации обмена данными (признак ), уступая варианту Р5 в производительности (на рис. 5.6, б относительные затраты на процессор обмена в Р7 не учтены). Поэтому в результате селекции архитектура Р7 не будет включена в новую популяцию. Предположим, что скрещивание наборов Р4 и Р6 было произведено таким образом, что произошел обмен признаками в позициях с третьей по пятую. Такое скрещивание не порождает новой популяции:

Р4= Þ Р6= ;

Р6= Þ Р4= .

Если происходит обмен парами, состоящими из четвертого и пятого признаков описаний Р4, Р6, то образуются следующие наборы:

и .

Первый из них будет хуже по значению функции выживаемости в сравнении с архитектурой Р3, поскольку признак означает введение дополнительного процессора обмена, хотя можно обойтись и без него, как это сделано в решении Р3 (признак ). Второй вариант вообще недопустим, поскольку нарушается третье правило синтеза описаний: комбинация признаков , и является запрещенной. Архитектура Р3 может быть получена из архитектуры Р4 в результате мутации признака ("гена") , приводящей к появлению признака в соответствующем описании Р3. С другой стороны, мутация признака в описании Р5= и замена его на признак не порождает нового решения. Дело в том, что архитектуры с описаниями Р5 и являются функционально эквивалентными: обработка слова сразу после формирования (признак ) при наличии буфера (признак ) – это то же самое, что обработка перед буферизацией (признак ). Однако сразу же заметим, что это не означает избыточности архитектурных признаков и : второе из вышеприведенных правил синтеза описаний допускает и отсутствие буферизации (признак ), при этом в описании обязательно должен присутствовать архитектурный признак . Такой комбинации соответствуют архитектуры подклассов С8 и Б8.

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

Теперь сформулируем основные свойства генетических алгоритмов, которые могут быть существенно полезны в синтезе архитектурных решений вычислительных систем. Первое полезное свойство: генетические алгоритмы при соответствующей настройке параметров хорошо адаптируются к целевым функциям. В отличие от алгоритмов имитации отжига (simulated annealing), скорость сходимости генетических алгоритмов практически не зависит от сложности ландшафта целевой функции. Алгоритмы имитации отжига основываются на понятии тепловой энергии, ассоциируемой с функцией качества решения. Задача комбинаторной оптимизации может быть рассмотрена как поиск состояния теплового равновесия и вычисления энергии системы. Сначала выбирается некоторое начальное приближение и устанавливается начальная температура. Генерируется новое решение, для которого вычисляется функция качества. Допускаются те переупорядочивания конфигурации, например, параметров системы, которые не увеличивают значения функции. В противном случае оценка допустимости конфигурации и выбор стартовой точки производятся с помощью вероятностного фактора Больцмана. Рассмотренные действия итеративно повторяются. Затем температура понижается. Если критерий останова не достигнут, то генерируется новое решение и т.д. Как правило, целевые функции, характеризующие качество архитектурного решения, имеют ряд локальных оптимумов и довольно сложный рельеф. Чтобы это проиллюстрировать, достаточно вновь обратиться к рис. 5.7, на котором показаны зависимости относительных аппаратурных затрат на реализацию различных функций архитектуры подкласса Р3. В алгоритмах имитации отжига, имеющих дело с подобными целевыми функциями, нужно медленно понижать температуру, чтобы алгоритм не был захвачен локальным оптимумом, из которого он не сможет выйти. При медленном понижении температуры возрастает число итераций и, соответственно, вычислительная сложность алгоритма. Второе полезное свойство: параметры генетического алгоритма, например, такие как размер популяции, значения вероятности скрещивания и мутации, могут быть настроены на задачах небольшой размерности. Затем они допускают перенос и на задачи большей размерности. Наконец, третье: допустимо изменять степень детализации описания архитектуры, в частности, число архитектурных признаков без значительных модификаций в самом генетическом алгоритме. Это возможно в том случае, когда вычисление функции выживаемости выполняется отдельно от операций генерации решений (селекции, скрещивания, мутации). Итак, генетические алгоритмы могут помочь в исследовании пространства и локализации области поиска архитектурных решений. Теперь сформулируем содержание основных этапов при выборе целевой архитектуры.

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

, , .

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

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

Этап 1. Нахождение частичного описания. Построение начальных фрагментаций и соответствующих последовательностей .

Этап 2. Поиск общей трансверсали признаков для последовательностей длины семейства .

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

На первом этапе поиск начальных фрагментаций спецификации может осуществляться не только "вручную", но и с помощью специальных алгоритмов, например, на основе метрического подхода. Примеры применения метрик приводятся в следующем подразделе данного раздела. Общая трансверсаль признаков для семейства не обязательно существует. Это означает, что на заданном семействе признаков не может быть реализована целевая архитектура с требуемыми свойствами. Тогда требуется возврат со второго этапа синтеза к первому и изменение вида последовательностей . Возможно, что придется при этом изменить и начальные фрагментации. В п. 5.2 исследуется критерий существования целевой архитектуры. Необходимость третьего этапа обусловлена тем, что семейство , соответствующее общей трансверсали, полученной на втором этапе, может содержать пересекающиеся подмножества. Кроме этого, возможно, что , т.е. некоторые объекты спецификации могут не попасть в подмножества семейства . Поэтому необходимо расширить подмножества до подмножеств семейства так, чтобы , а затем построить разбиение . Заметим, что во многих задачах проектирования дискретных систем приходится отыскивать разбиение множества, имея в качестве его "промежуточного" представления некоторое семейство не обязательно непересекающихся подмножеств, причем это семейство является покрытием исходного множества. Так, для вышерассмотренного примера с разбиением спецификации вычисления (см. рис. 5.2, а) "промежуточное" семейство подмножеств строк спецификации для вычислений , , может иметь следующий вид: ({1}, {2, 3, 4, 5, 6}, {2, 3, 5, 6}). Здесь неполнота знания о конечной реализации выражается в том, что подмножества строк, реализующих вычисления , , пересекаются. С другой стороны, из этого семейства могут быть получены уже упоминавшиеся разбиения ({1}, {4}, {2, 3, 5, 6}) и ({1}, {2, 3, 4, 5, 6}, Æ). Приемы отыскания окончательного вида разбиения рассматриваются в п. 5.3.

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

Критерий существования целевой архитектуры

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

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

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

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

;

Здесь · обозначает признак или признак . Наконец, третье правило синтеза описаний не соблюдается на следующих наборах:

;

где знак соответствует любому из признаков , , .

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

Рис. 5.8. Алгоритм поиска частичного описания архитектуры

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

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

Цель кластеризации по управлению – сгруппировать вместе операции в нити (потоки управления), как можно более длинные, чтобы уменьшить число передач управления между группами операций. О том, что условные ветвления замедляют работу программ и усложняют устройство процессоров, мы уже говорили в п. 4.1 раздела 4, когда речь шла о механизме предикации в архитектуре команд IA-64. Поскольку в реальных программах содержатся многочисленные операторы выбора, то было бы желательно минимизировать число передач управления между кластерами, соответствующими последовательным участкам программ. Пусть операция предшествует операции . Тогда формально метрика "близости" этих операций по управлению может быть введена так:

где – условная вероятность выполнения операции , т.е. вероятность того, что выполнится операция при условии, что выполнена операция .

Положим, отношение предшествования операций задано графом переходов (рис. 5.9, а).

Операция 2 соответствует условному ветвлению. Пусть переход от операции 2 к операции 3 осуществляется с вероятностью , а переход к операции 4 – с вероятностью . "Близость" операций 1 и 5 по управлению определяется значением метрики , а для операций 1 и 3 – . Поскольку переходы 1®2, 4®5 безусловны, то в один кластер попадают операции 1, 2, 4, 5, а в другой – операция 3.

а) б)

Рис. 5.9. К вычислению метрик "близости"

Совместимость операций может быть выражена следующей метрикой:

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

Минимизировать трафик обмена данными, что особенно важно в масштабируемых вычислительных системах, можно, используя метрику "близости" по данным:

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

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

, ,

, и т. д.

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

Поясним общую идею построения кластерных алгоритмов разбиения на следующем примере. Положим, с использованием метрики "близости" по данным необходимо выделить кластеры в 4-точечном конвейерном быстром преобразовании Фурье (БПФ) (рис. 5.10). Элемент БПФ выполняет четыре комплексных умножения (операции 1, 2, 7, 8) и восемь комплексных сложений (операции 3,...,6 и 9,...,12).

Сначала, на первой стадии разбиения метрика связности по данным вычисляется для всех 12 операций БПФ. Результаты представлены матрицей на рис. 5.11, а. Это матрица 12´12, симметричная относительно главной диагонали, состоящей из нулей.

Рис. 5.10. Элемент конвейерного БПФ с прореживанием по времени

	1	2	3	4	5	6	7	8	9	10	11	12
1	0	0	0,4	0	0,4	0	0	0	0	0	0	0
2	0	0	0	0,4	0	0,4	0	0	0	0	0	0
3	0,4	0	0	0	0,67	0	0	0	0,33	0,33	0	0
4	0	0,4	0	0	0	0,67	0,4	0	0	0	0	0
5	0,4	0	0,67	0	0	0	0	0	0	0	0,33	0,33
6	0	0,4	0	0,67	0	0	0	0,4	0	0	0	0
7	0	0	0	0,4	0	0	0	0	0,4	0,4	0	0
8	0	0	0	0	0	0,4	0	0	0	0	0,4	0,4
9	0	0	0,33	0	0	0	0,4	0	0	0,67	0	0
10	0	0	0,33	0	0	0	0,4	0	0,67	0	0	0
11	0	0	0	0	0,33	0	0	0,4	0	0	0	0,67
12	0	0	0	0	0,33	0	0	0,4	0	0	0,67	0

а)

	1	2	7	8	I	II	III	IV
1	0	0	0	0	0,33	0	0	0
2	0	0	0	0	0	0,33	0	0
7	0	0	0	0	0	0,33	0,33	0
8	0	0	0	0	0	0,33	0	0,33
I	0,33	0	0	0	0	0	0,25	0,25
II	0	0,33	0,33	0,33	0	0	0	0
III	0	0	0,33	0	0,25	0	0	0
IV	0	0	0	0,33	0,25	0	0	0

б)

	A	B	C	D		E	F		G	H
A	0	0	0,25	0,25	E	0	0,4	G	0	0,4
B	0	0	0,25	0,25	F	0,4	0	H	0,4	0
C	0,25	0,25	0	0
D	0,25	0,25	0	0

в) г) д)

Рис. 5.11. Матрицы значений метрики связности по данным

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

а)

б) в)

Рис. 5.12. Кластерные деревья

Так, для операций 1 и 3, 1 и 5 значение метрики равно . Однако операции 3, 5 связаны по данным сильнее, поскольку . Следовательно, именно они включаются в один кластер. На рис. 5.12, а он обозначен через I. Операция 1 в этот кластер не попадает. По аналогии формируются кластеры II, III и IV, куда входят пары операций 4, 6; 9, 10 и 11, 12 соответственно. Операции 2, 7 и 8 в эти кластеры не включаются, поскольку слабее связаны по данным, чем операции вышеуказанных пар. Итак, после первой стадии разбиения мы имеем восемь кластеров, одна половина которых состоит из одиночных операций (1, 2, 7, 8), другая образована парами операций (I, II, III, IV).

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

Значения метрики для всех восьми кластеров, полученных на второй стадии разбиения, приведены в матрице на рис. 5.11, б. Так, кластер I сильнее всего связан по данным с кластером 1. Поэтому они образуют новый кластер A (см. рис. 5.12, а). Аналогично могут быть сформированы и три остальных кластера B, C и D. Степень связности кластеров A, B, C, D представлена матрицей, показанной на рис. 5.11, в. При этом на третьей стадии разбиения возможно сформировать еще четыре более крупных группы операций E, F и G, H, которым соответствуют деревья, изображенные на рис. 5.12, б и в. Наконец, на последней, четвертой стадии кластеры E и F, а также кластеры G и H могут образовывать еще два кластера I и J соответственно (см. рис. 5.11, г, д и рис. 5.12, б, в). На этом завершается построение полных кластерных деревьев с корнями I, J.

Степень детализации кластера зависит от целевой архитектуры, а точнее, доступных вычислительных ресурсов. Положим, при вычислении БПФ, показанного на рис. 5.10, каждая из операций назначается на отдельный процессор. Доступность SMP-архитектуры с физически не распределенной общей памятью и не менее чем 12 процессорами позволяет реализовать это БПФ с минимальным обменом данными. При этом никакой кластеризации не нужно. Если в каждом вычислительном узле DSM-системы с локальной памятью имеется по два процессора, то на такой системе целесообразно реализовать восемь кластеров, полученных после первой стадии разбиения (см. рис. 5.12, а). При этом операции 3, 5; 4, 6; 9, 10 и 11, 12 назначаются на один узел. Если доступна вычислительная система, узлы которой содержат не менее трех процессоров, то на отдельные процессорные узлы имеет смысл назначать кластеры A, B, C и D, которые были выделены на второй стадии разбиения. Если же узел имеет, по крайней мере, 6 процессоров, то рассматриваемое вычисление БПФ может быть реализовано на двух узлах в соответствии с кластеризацией третьей стадии (см. рис. 5.11, в и рис. 5.12, б, в).

На практике, как правило, используются комбинации различных метрик либо отдельные метрики применяются в некоторой последовательности в зависимости от целей разбиения спецификации. При этом, однако нужно учитывать то, что метрики могут вступать в противоречия друг с другом. Возникает ситуация коллизии, когда на основе применения разных метрик одни и те же операции нужно причислять к разным кластерам. Так, например, операции и (см. рис. 5.9, б) наиболее близки по данным (для них, напомним, ). Однако при этом они являются несовместимыми, поскольку имеют различные типы, т.е. . Поэтому при практической реализации кластерного метода очень важен порядок использования тех или иных метрик "близости". Второй немаловажный момент – необходимость учета вида отношения предшествования операций. Например, формальное применение метрики совместимости к кластеризации операций БПФ (см. рис. 5.10) может привести к потере свойства конвейерности вычислений. В частности, если попытаться пары операции 1, 2 и 7, 8 назначить на один и тот же ресурс при условии, что каждая из них использует его монопольно, то никаких конвейерных вычислений реализовать уже будет нельзя. Ну и, наконец, аспект методологического характера. Метрики могут вводиться разными способами и не исключено, что при разных метриках лучшими будут оказываться различные разбиения одной и той же спецификации программы. В этом случае существует опасность подмены исходной задачи разбиения задачей выбора метрики.

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

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

Введем следующие обозначения:

Построим сеть с множеством вершин:

(5.1)

В (5.1) вершина соответствует множеству , а вершины и – элементу , .

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

(5.2)

На рис. 5.13 приведен пример сети с множествами вершин и дуг, определяемыми в соответствии с (5.1), (5.2), для последовательностей с и .

Рис. 5.13. Пример сети для поиска общей трансверсали архитектурных признаков

Таким образом, в сети любая вершина представляет множество в наборе длины , а пара вершин и соответствует архитектурному признаку , входящему в объединение множеств и .

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

Т е о р е м а 5.1. Пусть – последовательность -наборов, соответствующих функциям целевой архитектуры. Описание архитектуры существует тогда и только тогда, когда в сети (5.1), (5.2) существует нуль-единичный поток величины .

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

Далее, пусть существуют подстановки , где – перестановки , такие что – общая трансверсаль для последовательности , а значит, и для .

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

Число таких троек двудольных графов равно : , где , , . При этом , , , , . Далее, , , , . Наконец, , , , .

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

Если существуют подстановки , то существуют и паросочетания мощности в графах соответствующих троек . Между паросочетаниями в двудольном графе и нуль-единичными потоками в сети имеется взаимно однозначное соответствие. Значит, существуют нуль-единичные потоки величины в сетях троек

. Следовательно, существует и поток величины в сети .

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

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

1°. Для заданной последовательности семейств архитектурных признаков построить сеть вида (5.1), (5.2).

2°. Найти максимальный нуль-единичный поток в сети .

3°. Если величина потока равна числу множеств архитектурных признаков, то целевая архитектура для последовательности существует.

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

5°. Если величина потока меньше , то изменить последовательность и перейти к шагу 1°.

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

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

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

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

Т е о р е м а 5.2. При использовании метода Хопкрофта – Карпа сложность нахождения описания целевой архитектуры, реализующей спецификацию , имеет оценку .

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

Для графа с числом вершин и ребер сложность составляет .

Для графа сложность имеет порядок , поскольку число вершин равно , а число ребер .

Для графа так же, как для графа , имеет место оценка

При этом . Отсюда получаем порядок числа шагов алгоритма применительно к тройке :

Далее, .

Значит, . Отсюда получим оценку сложности для -й тройки: , а для троек сложность составляет . Теорема доказана.

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

1 GSSS // European C.A.D. Standartization Initiative Letter. 1994. №2. P. 2.

Дата добавления: 2021-07-19; просмотров: 190; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!