Древовидные сети подвержены влиянию переменных задержек, которые имеют место при добавлении узлов к поддереву, когда данные у всех узлов одного поддерева должны быть переданы на другое.
Производительность конвейера ограничивается производительностью самого медленного его участка. Кроме этого в конвейере имеют место затраты времени на посылку сообщений из одного каскада в другой.
Для того, чтобы преодолеть ограничения, присущие традиционным сетям связи, разработаны высокопоточные сети. Для параллельной обработки информации предложены три варианта построения высокопоточных сетей: сеть «бабочка»; сеть с перекрестным обменом и гиперкуб.
Рисунок 17.5 - Виды топологии параллельных ММПС
Сеть «бабочка», разработанная в конце 60-х годов Рабинером и Гоулдом, повышает скорость вычислений при реализации БПФ, которое требует выполнения 4N2 умножений и 4N2 сложений комплексных чисел (на этой сети необходимо повторить алгоритм N/2log2 N раз).
Сеть перекрестного обмена предложена в конце 60-х годов Пизом и Стоуном и представляет собой альтернативный вариант топологии связной сети по отношению к варианту «бабочка» для выполнения БПФ, которое реализуется за log2 N шагов.
Гиперкуб или бинарный N-куб представляет собой теоретическую концепцию, обосновывающую возможность наращивания структуры за пределами трех измерений (см. рис. 17.6).
Рисунок 17.6 - Топология ММПС “гиперкуб”
N-размерный куб содержит 2N узлов (узловых процессоров). Концепция гиперкуба удобна для описания универсальных матричных ЭВМ, так как многие другие сетевые топологии могут быть отображены на гиперкуб путем отбрасывания некоторых связей.
Сетки (решетки) представляют собой одномерные, двумерные матрицы или матрицы большей размерности. На их основе реализуются систолические или волновые матрицы, в которых каждая ячейка соединена со своими ближайшими «соседями» во всех измерениях.
Цилиндры и тороиды являются разновидностью решеток, в которых число используемых измерений и топология поверхности выбираются таким образом, чтобы они соответствовали реализуемому прикладному алгоритму.
17.2 Функционирование мультимикропроцессорных систем. Взаимодействие функциональных модулей
При выполнении заданий совместно несколькими МПМ необходимо обеспечить их взаимодействие между собой, с общей памятью и с периферийными устройствами. Эти связи могут быть запланированными или незапланированными, т. е. возникающими как реакция системы на отказ одного из МПМ или на сигнал при обслуживании памяти, устройств ввода-вывода. Связи в ММПС обеспечиваются аппаратно-программными средствами. Известны три основных метода организации взаимодействия МПМ в ММПС: ведущий — ведомый, раздельного выполнения заданий в МПМ и симметричной работы всех МПМ. Применяются также их комбинации. Метод ведущий — ведомый позволяет реализовывать супервизорные программы только в одном МПМ (ведущем), который выбирается оператором или автоматически. Ведущий модуль может быть как универсальным микропроцессорным, так и специально разработанным супервизорным. В отличие от специально разработанного супервизорного универсальный модуль можно использовать и для расчетов по прикладным программам, когда супервизорные программы не выполняются. Супервизорные программы
ведущего модуля можно записать как программы повторных входимостей, а так как доступ к системным программам имеет только один МПМ, то в системе не возникают конфликты или блокировки.
В ММПС по методу ведущий — ведомый возможны отказы при сбоях в ведущем МПМ. Это происходит, если МПМ не является специализированным и оператор может заново запустить систему, используя при этом в качестве ведущего другой модуль. Ведущий МПМ должен обеспечивать выполнение супервизорных программ достаточно быстро, чтобы с опережением удовлетворять выдвигаемым требованиям. Если это условие не обеспечивается, то эффективность применения системы может оказаться низкой. Время простоя, накапливающееся в ведомых МПМ, делает рассматриваемую организацию наиболее пригодной для систем специального назначения, где допускаются простои. Она эффективна для неоднородных систем, которые содержат МПМ с существенно различающейся мощностью.
В методе раздельного выполнения заданий в МПМ супервизорные программы осуществляются каждым МПМ, для чего предусматривается их повторная входимость или повторная загрузка копий в каждый МПМ. При отказе одного из МПМ система с раздельным выполнением заданий в МПМ в целом не
теряет работоспособности. Однако восстановление и повторный запуск программ, которые выполнялись отказавшим модулем, сопряжены с большими трудностями. Эффективность системы мала, если загрузка МПМ в системе неравномерна. В тех случаях, когда применяется сочетание описанных организаций, число конфликтов, вызванных блокировкой системных программ, невелико, так как каждый МПМ имеет собственный набор необходимых программных модулей. Метод симметричной работы всех МПМ используется для повышения эффективности системы. Симметричная работа наиболее естественна для ММПС. Общесистемное управление в системе симметричной
работы всех МПМ непрерывно перераспределяется между МПМ. МПМ, который обеспечивает в данный момент управление системой и выполнение функции планирования, называется исполнительным. Для предотвращения конфликтных ситуаций в любой момент времени исполнительным является только один МПМ. Каждый МПМ выполняет супервизорные программы, связанные с решаемой задачей, и функции, необходимые для выполнения новой задачи, если текущая работа прервана или завершена. Лучшая балансировка загрузки и повышение эффективности системы достигается за счет выполнения неспецифических функций: прерывания для ввода-вывода, использования наименее загруженных в данный момент времени МПМ. Несмотря на то, что в общесистемном управлении только один МПМ является исполнительным, другие МПМ могут выполнять те же супервизорные программы, которые должны обладать повторной входимостью или иметь подпрограммы для каждого запуска.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.