Введение к работе
1 * Актуальность работы. Среди архитектур параллельных вычислительных систем существенное место занимают многопроцессорные вычислительные системы (МВС) типа ОКМД (один поток команд - много потокси даккых). S таких системах N процессорных элементов (ПЭ) выполняют одну и ту же команду, но с различными операндами. При этом число используемых ПЭ в системах достигает нескольких тысяч единиц. Одной из главных проблем при проектировании МВС с общим управлением, как и в других параллельных системах, является проблема организации параллельных обменов данными между ПЭ. Поэтому актуальной является задача рационального выбора средств коммутации, реализованная в виде коммуникационной сети -ключевого элемента в таких системах. Для МВС типа ОКМД характерен перестановочный режим обмена, т. е. синхронный обмен в соответствии с заданным списком соединений, состоящим из множества пар "источник-приемник", когда все приемники различны. В этом случае отображение номеров входов сети в номера выходов рассматривается как некоторая перестановка из N чисел, где N- число входов сети. К числу общепринятых критериев при оценке производительности коммуникационной сети в перестановочном режиме относится ее комбинаторная мощность, т. е. доля бесконфликтно реализуемых перестановок от их общего числа. Под конфликтом или блокировкой понимается ситуация, которая по определению является недопустимой и состоит в том, что два различных сообщения претендуют на одну и ту же пинию связи в сети. Важным показателем является также способность сети реализовать перестановки регулярного вида, - т.е. такие; для которых правило отображения номеров входов в номера выходов известно. Вопросы реализации произвольных и регулярных перестановок рассматривались в работах В. Бенеша, Дж. Ленфанта, Д. Лори,-С. Оркута, Т. Шиманского, а также в работах других авторов. Подходы, лежащие в основе разработанных, методов имели ряд недостатков, таких как:
использование сложного, последовательного алгоритма управления коммуникационной сетью; '" ,:
необходимость разработки "индивидуального" алгоритма маршрутизации для возможности бесконфликтной реализации перестановок одного типа;
дополнительные'затраты на аппаратуру. """'
В диссертации предложен новый метод анализа- комбинаторных свойств наиболее распространенных типов статических и динамических коммуникационных сетей, применяемых в современных параллельных вычислительных системах, а именно
* Работа поддержана Российским фондом фундаментальных исследований, проект N94-01-01650
сети n-куб и ее распространенных модификаций, основанный на результатах из теории чисел.
Цель работы состоит в повышении эффективности работы коммуникационной сети посредством анализа условий возникновения блокировок на операциях информационного обмена перестановочного вида.
Методы исследования. Использовались методы комбинаторики, теории чисел, в частности, понятие конгруэнтности, теории цифровой обработки сигналов.
Научная новизна работы. Г. Разработан метод анализа коммуникационных структур определенного вида, позволяющий расширить их комбинаторные свойства.
2. С учетом архитектурных особенностей коммутационной сети типа n-куб и принятого
"классического" алгоритма маршрутизации с использованием понятий из теории чисел
сформулированы условия возникновения блокировки как для синхронного, так и для
предложенного в диссертации асинхронного режимов выполнения алгоритма
маршрутизации.
-
Показано, что асинхронная модификация общепринятого алгоритма маршрутизации значительно улучшает коммутационные свойства гиперкуба.
-
В результате исследования другой коммуникационной топологии, а именно, многопутевой Омега-сети (Пм), с использованием предложенного метода показано, что многопутевые модификации не только обладают отказоустойчивостью, но и обеспечивают существенно лучшие комбинаторные возможности, чем исходная однопутевая Омега-сеть.
Практическая ценность. Результаты работы позволяют повысить эффективность реализации наиболее часто встречающихся на практике видов параллельных обменов данными. Предложенный метод анализа распространяется также и на другие типовые коммуникационные сети, а именно: модифицированную Омега-сеть, тор и способствует рациональному выбору средств коммутации на этапе проектирования. Использование асинхронного режима выполнения алгоритма маршрутизации при реализации некоторых перестановок на сети типа n-куб может быть полезным в ряде задач с жестким требованием минимизации времени выполнения обменов.
Практическая реализация. Разработанный метод анализа блокировок использовался при разработке различных вычислительных моделей серии ПС-230О.
Аппробашш работы. Материалы диссертации обсуждались на международной конференции "Telecommunication Services for Developing Economies'*. ITC Specialist Seminar. Cracow. Poland. April 1991;
з международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях", 24-27 сентября, Алма-Ата, 1991; на V Совещании по распределенным вычислительным системам и сетям (CDS-92), 7-11 сентября 1992 г., Калининград;
на международной конференции "Third International Conference. РАСТ-95. St-Petersburg. Russia. September 1995.
Публикации. Основное содержание диссертационной работы изложено в 5 опубликованных научных работах.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав,
заключения, списка литературы из го наименований. Диссертация содержит
страниц текста, 33 рисунков, таблиц.