автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Параллельные устройства вычислительной техники класса "системы-на-кристалле"

На правах рукописи

¿Щ

СУВОРОВА ЕЛЕНААЛЕКСАНДРОВНА

Параллельные устройства вычислительной техники класса "системы-на-кристалле"

Специальность 05.13.05. Элементы и устройства вы числительной техники и систем управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2004

Диссертация выполнена в ГОУ В ПО «Санкт-Петербургский Государственный Университет Аэрокосмического приборостроения»

Научный руководитель:

д.т.н., доцент Шейнин Юрий Евгеньевич

Официальные оппоненты:

д.т.н., профессор Л ыпарь Юрий Иванович

к.т.н., доцент М ихайлуца Константин Тимофеевич

Ведущая организация

Московский институт электронной техники (Технический университет)

Защита состоится 17июня 2004г.в 16° 0 на заседании диссертационного совета Д212 229.18 при ГОУ ВПО «Санкт-Петербургский Государственный Политехнический университет», по адресу: 195251, г. Санкт-Петербург, ул. Политехническая, д. 29, 9 уч. корп., 325 а.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Автореферат разослан 14 мая 2004 г.

Ученый сектетарь

Диссертационного совета

/Шашихин В. Н./

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

Развитие новых технологий открывает новые перспективы перед разработчиками вычислительных устройств (ВУ). Активно развиваемым направлением создания ВУ являются системы-на-кристалле (СнК) (L. Hammond, К. Olukotun, T.N. Theis, В. Cordan, J. Udell, Берски Д.)- В результате быстрого развития интегральных технологий на одном кристалле становится возможным размещать параллельные вычислительные структуры (ПВС).

Параллельные вычислительные структуры являются перспективным направлением повышения производительности ВС. Отечественные и зарубежные научные школы в течение нескольких десятилетий исследовали проблемы, возникающие при проектировании структур ПВС и предложили пути их решения. Многие научные результаты в области параллельных структур, составившие основу построения и определившие облик современных высокопроизводительных средств вычислительной техники, были получены отечественными учеными: Б.А. Бабаяном, B.C. Бурцевым, В.М. Глушковым, Б.А. Головкиным, Э.В. Евреиновым, М.Б. Игнатьевым, А.В. Каляевым, В.В. Корнеевым, В.К. Левиным, И.В. Прангишвили, В.А. Торгашевым, Я.И. Хетагуровым, В.Г. Хорошевским, и др.

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

Целью диссертационной работы является разработка методов построения параллельных устройств вычислительной техники как систем-на-кристаллс -многомодульных систем на базе повторно

Методы выполнения исследования

Исследования осуществлялись на основе аппарата теории графов, теории вероятности, теории систем массового обслуживания и теории вычислительных систем. Для построения математических и имитационных моделей были использованы пакет Maple 7.0 и среда имитационного моделирования GPSS НЗ. Для реализации предложенной методики построения СнК были использованы язык VHDL, САПР Oread 9.1 и Foundation Express. Научная новизна

1. Предложена двухуровневая архитектура параллельных вычислительных устройств в исполнении «система-на-кристалле», включающая: 1) уровень синтезируемых параллельных структур из IP-узлов — функционально полных компонентов параллельных вычислительных структур. 2) уровень 1Р-узлов, синтезируемых из готовых IP-блоков традиционных типов (процессорные ядра, контроллеры, блоки памяти и др.).

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

3. Поставлена проблема и разработана методика выбора узлов для организации внешних связей в структуре параллельных вычислительных устройств — СнК.

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

5. Разработаны математические модели системы коммуникаций внутри IP-узла, на базе которых разработана методика синтеза системы связей между IP-блоками.

Практическая ценность

1. Разработаны методики построения ПСнК как многомодульных систем

на базе повторно используемых компонентов

2. Разработана методика спецификации на языках высокого уровня синтезируемых ПСнК с заданными характеристиками.

3. Разработана методика спецификации на языках высокого уровня синтезируемых повторно используемых №-узлов с заданными характеристиками для построения ПСнК.

4. Разработана методика спецификации на языках высокого уровня синтезируемых интерфейсных компонентов ^-блоков для адаптации к различным стандартам интерфейсов в структуре узла ПСнК

Апробация работы

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

Публикации. Результаты , полученные в диссертации, нашли отражение в 14 опубликованных научных работах по теме диссертации, в том числе 1 монография (в соавторстве), 7 программных продуктов, зарегистрированных в Госфонде алгоритмов и программ РФ.

Внедрение. Результаты диссертационной работы использованы в ОАО НИИ Системотехники (г. С.-Петербург), в ГУП НТЦ «Элвис» (г. Москва). Объем и структура работы

Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 152 страницы машинописного текста, 77 рисунков, 12 таблиц. Объем приложений 51 страниц. Перечень литературных источников содержит 82 наименований. КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В соответствии с современными тенденциями развития интегральных

технологий в ближайшем будущем на кристалле станет возможным размещать ПВС, содержащие сотни вычислительных узлов. Современная СнК должна обеспечивать параллельное выполнение множества процессов, высокую производительность и высокую надежность вычислений, должна быть легко масштабируема. Показано, что необходимость развития ПСнК по пути систем с распределенной структурой диктуется особенностями интегральной технологии. В результате масштабирования рисунков схем задержки сигнала в элементах уменьшаются быстрее, чем в линиях связи, что приводит к возникновению проблемы «длинных линий» для решения которой используются GALS архитектуры. Использование САПР позволяет переносить готовые модули, получившие название виртуальных компонентов (VC — Virtual component, IP — Intellectual Property) из ранее разработанных устройств в новые.

В построении ПСнК как масштабируемой распределенной вычислительной структуры, в методологии их проектирования, предложено использовать два уровня виртуальных компонентов - IP-узлы и IP-блоки. Основным функциональным компонентом ПСнК является вычислительный узел в целом - узел распределенной структуры параллельной ВС - 1Р-узел. IP-узлы могут быть не только параметрически настраиваемы, но и синтезируемы как компонуемые из виртуальных компонентов другого уровня - из IP-блоков — процессорных ядер, блоков памяти, контроллеров интерфейсов, и др., которые могут быть использованы для построения IP-узлов. При проектировании на базе IP-блоков разработчик получает возможность сконцентрироваться на характеристиках IP-узла, при проектировании системы на базе IP-узлов разработчик получает возможность сконцентрироваться на характеристиках системы в целом.

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

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

Во втором разделе рассмотрены особенности проектирования СнК на базе IP-узлов как готовых виртуальных компонентов. Граф связей, соответствующий топологии ПСнК, рассматривается на структурном уровне и уровне рисунка схемы.

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

Для предварительной оценки рисунка схемы (design schematic) кристалла широко используется модель Томпсона. Однако до этапа синтеза не возможно учесть ряд факторов, необходимых для корректного использования классической или трехмерной модели Томпсона. Для оценки длины линий связи и количества переходов линий связи из слоя в слой на этапе выбора графа связей узлов в ПСнК в работе предложена модель условных линий связи. Если для используемой технологии длина линий связи особенно критична, предложено использовать дополнительный параметр - максимальную длину условных линий связи. Для оценки сложности на уровне рисунка схемы предложено использовать следующий набор характеристик: количество слоев металлизации, необходимое для размещения рисунка схемы, суммарная длина условных линий связи, максимальная длина условных линий связи, суммарное количество переходов линий связи из слоя в слой.

В соответствии с определенной системой критериев и параметров разработана методика, позволяющую выбрать топологию связей вычислительных узлов ПСнК и рисунок схемы в соответствии с требованиями, предъявляемыми разработчиком:

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

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

3) Определение среднего диаметра графа связей для выбранных в соответствии с пунктом 2 топологий.

4) Выбор множества внешних узлов.

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

Таблица 1. Зависимость характеристик рисунков схем от методов их формирования_

1 рехмсрная решетка Тор Гиперкуб (2")

Без чередования (п С чередованием (2) Без чередования (1) С чередованием (2) Кластер 2^(1) Кластер 2' (2)

1. Суммарная длима линий связи Меньше на 10-12% Линейно зависит от числа ГР-узлов ОДИНАКОВА ОДИНАКОВА

2. Максимальная длина линий связи ОДИНАКОВА Растете ростом числа узлов Сравнима с размерами кристалла Фиксированная (2*Ь=соп!Л) Не зависит от числа узлов. Линейная зависимость от числа умов Больше раза

3. Количество переходов га слоя в слой Линейная зависимость от числа узлов Меньше в 2 раза Линейная зависимость от числа узлов 0(а') Больше в 2" раз 0(о-)

Таблица 2. Реализация рисунков схем с учетом ограничений технологии (числа слоев линий связи, числа переходов)_

Двумерная решетка (МхЫ) Трехмерная решетка (\1xNxL) Тор (МхЫ) Гиперкуб (2")

1. 1 слой для прокладки линий связи Без ограничений Реализуема при условиях: М=Ы=2 или М=Ь=2 или Ы=Ь=2 Реализуема при условиях: М=2 или К=2 Реализуема при п<4 (У=2'=8)

2. Линии связи прокладываются в активных слоях (3 слоя) без переходов из слоя в слой Без ограничений Реализуема при условиях: М=2 или N=2 или 1_=2 Без ограничений Реализуема при п<5 (У=2'=16)

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

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

Исследована проблема определения работоспособной конфигурации ПСнК в ходе ее самоинициализации. Методика самотестирования ПСнК должна

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

Разработан алгоритм распределенного самотестирования ПСнК, выполняющийся на этапе инициализации системы. Алгоритм выполняется в каждом из узлов. На этапе 0 выполняется самотестирование каждого узла и выработка сигнатуры. На этапе 1 узел определяет множество исправных связей с соседними узлами. На этапе 2 узел получает от соседних с ним узлов сигнатуры, которые были получены ими на этапе самотестирования. На базе сравнения собственной сигнатуры узла и сигнатур соседних узлов определяется условно правильная сигнатура на этапе 2. На этапе 3 (последующие этапы аналогичны ему) узел получает от соседних узлов условно правильные сигнатуры, определенные ими на предыдущем этапе, и определяет новую условно правильную сигнатуру. По завершении выполнения алгоритма узел определяет множество соседних узлов, чья сигнатура совпала с условно правильной, полученной им на последнем этапе. Их он считает исправными. В дальнейшем он взаимодействует только с ними. В результате формируется работоспособная конфигурация ПСнК, из которой исключены узлы, признанные неисправными:

Построена математическая модель алгоритма. Система характеризуется М - множеством сигнатур (v, - сигнатура с номером i из данного множества, V| -правильная сигнатура), вектором вероятностей Р - вероятность получения сигнатуры - функция вероятности принятия сигнатуры в качестве

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

и -1-1-

2 4 6

этап этап этап

—•— p1 =0,5 4h-p2=0,3

. p3=0,1 —*—p4=0,1

Рисунок 1 - Процесс схождения алгоритма

Теорема. Алгоритм является сходящимся, при условии, что является

монотонно возрастающей и Уу,еМ, Иру^ру. _ _

«ЗАВИСИМОСТЬ г| от

тогда и только тогда, когда Уу.еМ, У,^, РУ<РУ| ^ числа этапов (Рр=5^

0,8

Математическая модель позволяет также определить количество этапов алгоритма, необходимое

0,2

для того, чтобы узлы с заданной вероятностью определили сигнатуру, соответствующую работоспособному состоянию узла. Максимальное количество этапов равно диаметру графа связей +2 (самотестирование и проверка связей с соседними узлами). На рисунке 1 приведен пример, иллюстрирующий процесс схождения алгоритма в топологии типа двумерная решетка или тор при 0.3, 0.1,0.1] (здесь на 1 этапе PV|=0.5). К шестому этапу РУ] достигает 0.992.

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

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

В третьем разделе рассмотрена структура IP-узлов для построения ПСнК. Эффективность функционирования IP-узла сильно зависит от организации коммуникационной системы внутри него. Традиционные шины, организованные по схеме с тремя состояниями, вследствие особенностей технологии не подходят для СнК, где используются шины, организованные по схеме с мультиплексированием. Наряду с системой коммуникаций на базе шины в IP-узлах могут использоваться коммуникации на базе коммутаторов.

Исследованы сходства и отличия распространенных стандартов внутрикристальных систем коммуникаций: CoreFrame, VSIA, Marble, IPBus,

PIBus, FISHPBus, Wishbone, CoreConnect, OCP, Triscend Bus Architecture, Silicon

БаекИапе и АМВА.

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

Для оценки быстродействия коммуникационной системы используется время выполнения запроса - Тс. Оно складывается из времени ожидания предоставления канала коммуникационной системы - W и времени взаимодействия между ведущим и ведомым устройствами - (в общем случае системе может быть сопоставлена матрица времен обслуживания Ведущие устройства могут быть охарактеризованы временем между завершением выполнения заявки и генерацией следующей — Тт (в общем случае системе может быть сопоставлен вектор Тм). Для оценки эффективности используется загрузка каналов коммуникационной системы, вычисляемая на базе интенсивностей потоков заявок через ведущие устройства - и через каналы -X, (Л, если в системе 1 канал).

Пример стохастической сети, используемой для моделирования коммутатора, представлен на рисунке 2. Модель системы включает в себя обслуживающие приборы, соответствующие ведущим устройствам и каналам между ведущими и ведомыми устройствами. Описание модели выполнено в форме системы уравнений, из которых выводятся параметры системы. Например, для системы на базе общей шины, включающей в себя 3 ведущих устройства:

л = -

4-Г, + Г '

((4-Г +4-т 1 5 т ) Г У" 1 т

1 т

Т 1

т

(1 -Х-Т У +Х-Т (1 -Х-Т )' м гп Ш

4-Г'+Г '

Т -((4-Т +4- -«-Т 2)"

т «я V Т т '

Тс=\*/+Т..

Для системы на базе коммутатора включающей в себя 3 ведущих и 4 ведомых устройства:

, ({Ъ-Т + 60 Т +43 т я

X ----

ст 2

Т (32-Г +39-Г Г +36-7- )

5 /и_и 5_—)-Г V"

7т «

Г -3-Г

Г • ((8• Г +60-Г +4-т т 5

Г (32• Г + 39-Г -Г +36-Г2)

3. Д _/и д_V"

X т '

I-<1 -X -Т )г

Время ожидания в очереди к каналу 1-3: = --——т—

Время ожидания в очереди к каналу 4:

2 • (1 - Я -Г )' + 3(1-Л Т )г-(2 + Я -Т )

4 т т' т т' * т м'

И', =-$4

27а

6-Л

.Т^Ш-^-и^^+З-Т,).

Предложена методика теоретической оценки аппаратных затрат на реализацию коммуникационной системы на базе коммутатора в сопоставлении с шинными структурами. Аппаратные затраты на реализацию коммутатора могут быть оценены по следующей формуле: А2-Ы,{Щ А,+Ыт (1/3)А,,

Рисунок2-Моделькоммуникационной где " аппаратные затраты на

системы на базе коммутатора реализацию коммуникационной

системы на базе шины. Показана практическая приемлемость аппаратных затрат

на реализацию коммутатора в IP-узле. Например, при 5 ведущих, 6 ведомых устройствах они не превосходят 5% от аппаратных затрат на реализацию процессорного ядра LEON (SPARC V8.e). Примеры синтеза подтвердили теоретические расчеты по выведенной формуле (разница ¿0,4%).

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

В четвертом разделе предложены методики описания 1Р-узлов, IP-блоков и ПСнК в целом как виртуальных компонентов на основе языка VHDL.

Предложена методика параметризованного описания интерфейса IP-узла, позволяющая сделать его повторно используемым в ПСнК с различной топологией связей между узлами. Интерфейс IP-узла характеризуется количеством и разрядностью линий связи. Входной и выходной порты IP-узла описываются как массивы, количество элементов которых определяется этими параметрами. Компонент контроллера межузловых связей имеет блочную структуру. Для генерации нужного количества блоков используется конструкция for...generate.

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

Структурное описание ПСнК представлено на рисунке 3. Оно включает в себя описание конкретных экземпляров компонентов с определением парамет-

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

(type rangel is (2, 3, 4, 5); — множество внутренних узлов type rangeoutl i3 (1, 6); — множество внешних узлов)

MODULEs_in: FOR I in rangel'low to rangel'high GENERATE — секция

генерации множества внешних узлов

MODULEi_in: module_name

Generic map (num_lines=fs(I));

port map (

i_port(1) => net_find( 1,1,0 ), ijport(2) => net_find( 1,2,0 ),

end generate

MODULEs_out: FOR I in rangeoutl'low to rangeoutl'high GENERATE — секция

генерации множества внешних узлов

M0DUL2i_out: module_name

Generic_map(num_lines=fs (I));

port map (

i_port(1) => net_find( 1,1,0 ), i_port(2) => net_find( 1,2,0 ),

..) ;

Для генерации шаблона описания СнК разработана программа-генератор описания. В соответствии с особенностями стандартов внутри-

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

компоненте предлагается выделить постоянную и переменную- часть,

последняя по-разному реализуется в зависимости от конкретного стандарта. Набор компонентов, соответствующих переменным частям, включается в описание IP-блока с помощью секции IF... generate, что позволяет разработчику определять конкретный компонент, который будет включен в IP-блок.

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

ОПИСАНИЕ АРХИТЕКТУРЫ

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

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

В приложениях к работе приведены: программы теоретического расчета пара-метров коммуникационной системы на базе шины и на базе коммутатора; моде-ли коммуникационных систем на GPSS; примеры описания СнК, 1Р-узлов, IP-блоков на VHDL.

На защиту выносятся следующие научные положения:

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

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

3. Разработан децентрализованный алгоритм распределенного

самодиагностирования и формирования работоспособной конфигурации параллельной СнК с учетом особенностей технологии. Доказана сходимость алгоритма.

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

5. Разработан метод спецификации на языке высокого уровня и синтеза параллельных СнК с заданными структурными характеристиками из готовых IP-узлов. Разработан метод спецификации на языке высокого уровня и синтеза IP-узлов для параллельных СнК.

Основные положения диссертации опубликованы в следующих работах:

1. Суворова Е. А., Шейнин Ю. Е.. Проектирование цифровых систем на VHDL., СПб., БХВ-Петербург, 2003 г., 576 с.

2. Суворова Е. А., Шейнин Ю. Е., Язык VHDL для проектирования систем на СБИС. Учебное пособие. СПб., РИО ГУАП, 2001 г., 212 с.

3. Шейнин Ю. Е., Суворова Е. А. Архитектура вычислительного модуля для параллельных вычислительных систем на кристалле// Тез. докл. 5 международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электроника и энергетика». М., 1999. С. 699-700.

4. Шейнин Ю. Е, Суворова Е. А. Архитектура вычислительного модуля для параллельных систем на кристалле// Тез. докл. всероссийской научно-технической конференции 25 Гагаринские чтения М, 1999 г. С. 336.

5. Суворова Е. А. Влияние организации систем-на-кристалле на архитектуру параллельных ВС// Тез. докл. 3-ей научной сессии аспирантов, докторантов и соискателей, апрель 2000 г.: Сборник/ СПб., РИО ГУАП, 2000 г. С. 191.

6. Суворова Е. А. Формирование работоспособной конфигурации при инициализации параллельной вычислительной системы-на-кристалле// Сборник ГУАП/ РИО ГУАП, 2000 г. С. 232-240.

7. Суворова Е. А. Специфика архитектуры систем-на-кристалле// Тез. докл. всероссийской научно-технической конференции 26 Гагаринские чтения М., 2000 г. С. 256.

8. Суворова Е.А. Особенности организации параллельных систем на кристалле, включающих в себя 108 - 109 транзисторов// Тез. докл. 5 международной научно-технической конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» Таганрог, сентябрь 2000 г. С. 212-213.

9. Суворова Е. А. Топология связей вычислительных модулей в параллельных системах на кристалле// Тез. докл. 7 ежегодной международной научно-техническая конференции студентов и аспирантов. МЭИ 2001 г. С. 304.

Ю.Шейнин Ю. Е., Суворова Е. А. Организация межмодульных связей в параллельных вычислительных системах на кристалле// Тез. докл. 4 научная

сессии аспирантов ГУАП. Санкт-Петербург, 2001 г/СПб. РИО ГУАП, 2001 г. С. 247.

П.Шейнин Ю. Е., Суворова Е. А. Особенности организации модуля параллельной вычислительной системы на кристалле// Тез. докл. 5 научная сессии аспирантов ГУАП. Санкт-Петербург, 2002 г/СПб. РИО ГУАП, 2002 г. С. 432-435.

12.Шейнин Ю. Е., Суворова Е. А. Организация связей с внешними каналами в параллельной вычислительной системе-на-кристалле// Тез. докл. 6 научная сессии аспирантов ГУАП. Санкт-Петербург, 2003 г/СПб. РИО ГУАП, 2003 г. С. 309-310.

13."MCFUght" - SOC based chipset with SpaceWire Links for Aerospace Applications/ T. Solokhina, J. Petrichkovich, E. Suvorova, and others. International Space Wire Seminar 4 -5 November, 2003, pp 110-116.

14."MCFlight" - отечественное семейство СБИС с каналом SpaceWire для высокопроизводительных аэрокосмических систем обработки информации в реальном масштабе времени/ Т. В. Солохина, Я. Я. Петричкович, Е. А. Суворова, и дрУ/ Труды третьего расширенного семинара "Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях" 26-27 ноября 2003г. С' 121-127

15.Суворова Е. А. "Программа расчета количества шагов процесса определения работоспособной конфигурации параллельной системы-на-кристалле". / М: 50200300205,2003.

16.Суворова Е. А. "Пакет программ расчета характеристик коммуникационных систем на базе коммутатора и на базе шины." / М.: ВНТИЦ, 50200300182, 2003.

П.Суворова Е. А. "Пакет программ моделирования и синтеза блока

коммуникаций на базе шины АМВА АНВ для систем-на-кристалле." / М.: ВНТИЦ, 50200200640,2002.

18.Суворова Е. А. "Пакет программ моделирования и синтеза блока коммуникаций на базе коммутатора с интерфейсом АМВА АНВ для систем-на-кристалле." / М.: ВНТИЦ, 50200200623,2002.

19.Суворова Е. А. "Программа формирования множества внешних модулей для параллельных систем-на-кристалле." / М: ВНТИЦ, 50200300046,2003.

20.Суворова Е. А. "Программа генерации топологии связей между модулями параллельных систем-на-кристалле." / М.: ВНТИЦ, 50200300181,2003.

21.Суворова Е. А. "Программа моделирования процесса определения работоспособной конфигурации параллельной системы-на-кристалле." /М.: ВНТИЦ, 50200300179,2003.

Формат 60x84 1/16 Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ №%23 Отдел оперативной полиграфии ГОУ ВПО «ГУАП» 190000, Санкт-Петербург, ул. Б. Морская, 67

Р-97 75

Перечень сокращений

Содержание

Введение

1 Влияние развития интегральных технологий на организацию 9 параллельных систем-на-кристалле

1.1 Развитие интегральной технологии и ее влияние на архитектуру 9 вычислительных средств

1.1.1 Тенденции развития интегральных схем

1.1.2 Тенденции развития процесса литографии

1.1.3 Тенденции развития микропроцессорной логики и памяти

1.1.4 Тенденции совершенствования межэлементных соединений

1.1.5 Изменение параметров схем в результате масштабирования рисунков 14 схем

1.2 Системы-на-кристалле — электронная компонентная база нового 16 поколения

1.3 Параллельные системы-на-кристалле

1.3.1 Возможности и ограничения интегральной технологии для параллельных 18 систем-на-кристалле

1.3.2 Оценка возможностей построения параллельных систем-на-кристалле на 21 современных и перспективных интегральных технологиях

1.3.3 ПСнК как системы с распределенной архитектурой

1.3.4 Уровни виртуальных компонентов для параллельных СнК

1.4 Проблемы разработки и применения IP-узлов и IP-блоков для 25 параллельных систем-на-кристалле

1.4.1 Организация распределенной структуры ПСнК

1.4.2 Внутренняя организация вычислительных узлов ПСнК

1.4.3 Структура IP-узлов и IP-блоки для их построения

1.4.4 Проектирование ПСнК из виртуальных компонентов

1.5 Выводы по разделу

2 Структура параллельных систем-на-кристалле и IP-узлы для 29 ПСнК

2.1 Распределенная структура параллельных систем-на-кристалле

2.2 Характеристики коммуникационной системы параллельных систем- 30 на-кристалле с учетом технологии реализации

2.2.1 Характеристики систем связей ПВС с распределенной структурой

2.2.2 Характеристики систем связей для ПСнК на структурном уровне

2.2.3 Характеристики систем связей для ПСнК на уровне рисунка схемы

2.3 Анализ возможностей использования топологий ВС для построения 39 параллельных систем-на-кристалле

2.3.1 Определение возможности использования топологий на основе толщины 39 графа связей

2.3.2 Сравнение характеристик топологий и определение оптимальных условий их применения

2.4 Задача размещения множества внешних узлов в структуре параллельных систем-на-кристалле

2.4.1 Постановка задачи

2.4.2 Классический алгоритм нахождения р-мёдиан графа

2.4.3 Алгоритм формирования множества внешних узлов в структуре ПСнК

2.4.4 Размещение множества внешних узлов для топологий, рассмотренных в

параграфе 2.

2.5 Формирование работоспособной конфигурации при инициализации параллельных систем-на-кристалле

2.5.1 Алгоритмы тестирования ПВС

2.5.2 Формирование работоспособной конфигурации при инициализации

2.5.3 Математическая модель системы для оценки характеристик алгоритма формирования работоспособной конфигурации системы

2.5.4 Условия сходимости алгоритма формирования работоспособной конфигурации системы

2.5.5 Оценка характеристик алгоритма

2.5.6 Способы обмена информацией между узлами и их влияние на скорость схождения алгоритма

2.5 Выводы по разделу

3 Структура IP-узлов и IP-блоки для параллельных систем-накристалле

3.1 Организация IP-узла параллельных систем-на-кристалле

3.1.1 Структура IP-узла ПВСнК

3.1.2 Особенности коммуникационных систем для построения систем-накристалле

3.1.3 Описание коммуникационной системы

3.1.4 Стандарты внутрикристальных шин

3.1.5 Сходства и отличия стандартов внутрискристальных шин

3.2 Организация системы коммуникаций между блоками в IP-узле

3.2.1 Варианты организации системы коммуникаций между блоками на примере стандарта АМВА АНВ

3.2.2 Математическая модель системы коммуникаций на базе однонаправленных шин с мультиплексированием выходов на шину

3.2.3 Математическая модель системы коммуникаций на базе несимметричного коммутатора

3.2.4 Имитационные модели

3.2.5 Оценка аппаратных затрат на реализацию коммуникационной системы

IP-узла

3.3 Выводы по разделу

4 Методы синтеза параллельных систем-на-кристалле на основе языка VHDL

4.1 Особенности проектирования IP-узлов и IP-блоков

4.1.1 Требования к описаниям СнК в целом, IP-узлов и IP-блоков для СнК

4.1.2 Возможности языка VHDL для проектирования виртуальных 120 компонентов

4.2 Разработка и спецификация параллельных систем-на-кристалле с 124 использованием языка VHDL

4.2.1 Организация настраиваемого интерфейса IP-узлов

4.2.2 Организация структуры связей между IP-узлами

4.3 Организация внутренней структуры IP-узла

4.3.1 Возможность организации гибкого интерфейса IP-блока

4.3.2 Организация коммуникационной системы между блоками внутри IP-узла

4.3.3 Организация описания IP-узла с переменным количеством 146 дополнительных блоков

4.4 Методы разработки, спецификации и синтеза параллельных систем- 146 на-кристалле

4.4.1 Метод спецификации на языке высокого уровня и синтеза ПСнК из 146 готовых узлов

4.4.2 Метод спецификации на языке высокого уровня и синтеза IP-узлов для 147 параллельных СнК

4.5 Выводы по разделу 4 149 Заключение 151 Список литературы 153 Список публикаций по теме диссертации 158 Список зарегистрированного программного обеспечения 159 Приложения

П.1 Определение книжной толщины регулярной топологии на примере 160 тора

П.2 Определение параметров рисунков схем для топологий типа тор, трехмерная решетка, гиперкуб

П.З Влияние соотношения параметров решеток на средний диаметр

П.4 Таблицы характеристик рисунков схем

П.5 Определение среднего диаметра топологий

П.6 Программы теоретического расчета параметров системы на базе шины и на базе коммутатора

П.7 Модели на GPSS для определения параметров системы на базе шины 178 и на базе коммутатора в тех случаях, когда теоретический расчет не возможен

П.8 Описание блока связей узла на базе общей шины и на базе коммутатора на VHDL

П.9 Пример структурного описания параллельной системы-на- 194 кристалле

П.10 Пример расчета характеристик коммуникационной системы на базе шины и на базе коммутатора для процессора "Мультикор"

П.11 Акты о внедрении

Актуальность проблемы.

Развитие новых технологий открывает новые перспективы перед разработчиками вычислительных устройств (ВУ). Активно развиваемым направлением создания ВУ являются системы-на-кристалле (СнК) (L. Hammond, К. Olukotun, Т. N. Theis, В. Cordan, J. Udell, Берски Д.). В результате быстрого развития интегральных технологий на одном кристалле становится возможным размещать параллельные вычислительные структуры (ПВС).

Параллельные вычислительные структуры являются перспективным направлением повышения производительности ВС. Отечественные и зарубежные научные школы в течение нескольких десятилетий исследовали проблемы, возникающие при проектировании структур ПВС и предложили пути их решения. Многие научные результаты в области параллельных структур, составившие основу построения и определившие облик современных высокопроизводительных средств вычислительной техники, были получены отечественными учеными: Б.А. Бабаяном, В.С.Бурцевым, В.М. Глушковым, Б А. Головкиным, Э.В. Евреиновым, М.Б. Игнатьевым, А.В. Каляевым, В.В. Корнеевым, В.К. Левиным,

И.В. Прангишвили, В А. Торгашевым, Я.И. Хетагуровым, В.Г. Хорошевским, и др.

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

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

В данной работе рассмотрены аспекты построения систем-на-кристалле на базе повторно используемых компонентов. Предлагается использовать два уровня виртуальных компонентов - IP-узлы и IP-блоки. IP-узлы по сложности соответствуют вычислительным узлам (computer node), IP-блоки - процессорам, контроллерам, блокам памяти (из них строятся 1Р-узлы).

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

На базе этих характеристик определена методика выбора топологии связей для параллельной системы-на-кристалле в соответствии с предъявляемыми к ней требованиями и используемой технологией реализации.

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

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

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

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

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

Цель диссертационной работы.

Целью диссертационной работы является разработка методов построения параллельных систем-на-кристалле как многомодульных систем на базе повторно используемых компонентов.

Методы исследования.

Исследования осуществлялись на основе аппарата теории графов, теории вероятностей, теории систем массового обслуживания и теории вычислительных систем. Для построения математических .и имитационных моделей были использованы пакет Maple 7.0 и среда имитационного моделирования GPSS НЗ. Для реализации предложенной методики построения систем-на-кристалле был использован язык VHDL и САПР Oread 9.1 и Foundation Express 2.1i.

Научная новизна.

Научная новизна заключается в разработке методов проектирования систем-на-кристалле на базе повторно используемых компонентов. В результате проведенного исследования:

1. Предложена двухуровневая архитектура параллельных вычислительных устройств в исполнении «система-на-кристалле», включающая: 1) уровень синтезируемых параллельных структур из IP-узлов - функционально полных компонентов параллельных вычислительных структур. 2) уровень 1Р-узлов, синтезируемых из готовых IP-блоков традиционных типов (процессорные ядра, контроллеры, блоки памяти и др.)

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

3. Поставлена проблема и разработана методика выбора модулей для организации внешних связей в структуре параллельных вычислительных устройств -СнК.

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

5. Разработаны математические модели системы коммуникаций внутри 1Р-узла, на базе которых разработана методика синтеза системы связей между IP-блоками.

4.5 Выводы по разделу 4

1) Исследованы возможности языка VHDL для создания описания компонентов, которые могут быть адаптированы для использования в СнК с существенно различными характеристиками.

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

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

4) Предложенные методики реализованы в зарегистрированном программном обеспечении.

Заключение

В результате проделанной работы разработаны методики, позволяющие осуществить синтез параллельной системы-на-кристалле из IP-узлов и IP-узлов из IP-блоков.

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

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

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

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

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

На защиту выносятся следующие научные положения:

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

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

3. Разработан децентрализованный алгоритм распределенного самодиагностирования и формирования работоспособной конфигурации параллельной СнК с учетом особенностей технологии. Доказана сходимость алгоритма.

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

5. Разработан метод спецификации на языке высокого уровня и синтеза параллельных СнК с заданными структурными характеристиками из готовых IP-узлов. Разработан метод спецификации на языке высокого уровня и синтеза IP-узлов для параллельных СнК.

1. International technology roadmap for semiconductors. Edition 2002. // 194 p.

2. Theis T. N., Res J. The future of interconnection technology // IBM. Develop 44. 2000. No 3. P. 379-390.11

3. Рэнделл Айзек. Будущие технологии КМОП // Открытые системы. 2000. №10. С. 8-18.

4. Donnelly K. Serial Links. Next Generation Communication Buses // VP, Network Connection Division Rambus Inc. Gather Group Semiconductor Conference. 2001. Nov, Vol. 8. 15 p.

5. Bill Cordan. An Efficient Bus Architecture for System-on-Chip Design // 2001 IEEE Custom Integrated Circuits Conference. 2001. Jan. P. 29-35.7. http://comsci.yonsei.ac.kr/phd/yskim/over.html.

6. Open Core Protocol Reference Document Revision 002 // OCP-IP Association. 2001. 202 p.

7. Сложные устройства на одном кристалле становятся реальностью // ChipNews 1999. №2. Р. 22-25.

8. Entony Catalgo. Embedded DRAM gets pure-logic performance // EE TIMES 09.11.00.

9. Берски Д. Рост сложности ИС превращает цифровые схемы в однокристальные схемы // Электроника. 1993. №11-12. С. 12-15.

10. Lance Hammond and Kunle Olukotun. Considerations in the Design of Hydra: A Multiprocessor-on-a-Chip Microarchitecture // CSL-TR-98-749. 1998. February. 12 p.13. http://kasuga.csc.e.kysshu-u.ac.jpAppram/english/ppramwhat.html.

11. A Single chip Multiprocessor Integrated with Hight Density DRAM / Tadaaki Yamauchi, Lance Hammond, Kunle Olukotun // Computer Systems Laboratory, Stanford University. Report CSL-TR-97-731. 1997. 34 p.

12. Flynn M. S. Basis issues in microprocessor architecture // Journal of System Architecture 45. 1999. P. 939-948.

13. Vishal Anand. Design for flexibility // SNUG'99 Boston. 1999. 20 p.17. http://www.silicore.net.

14. Bill Cordan. EEdesign Exclusive Configurable Platform-Based SoC Design Techniques, part 1 // Computer Systems Laboratory, Stanford University. 2001. September 18. 8 p.

15. Sudhakar Yalamanchili. Introductory VHDL from simulation to synthesys // Prentice-hall. 2001.401 p.

16. Aldworth P. J. System-on-a-Chip Bus Architecture for embedded Applications // International Conference on Computer Design (ICCD'99). 1999. P. 297-298.

17. Cordan B. An Efficient Bus Architecture for System-on-a-Chip Design // Proceedings of IEEE Custom Integrated Circuits Conference. 1999. May. P. 623-626.

18. Winegarden S. Bus Architecture of a System on a Chip with User Configurable System Logic // IEEE Journal of Solid State Circuits. 2000. Vol. 35, No. 3. P. 425-433.

19. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. М.: Радио и связь, 1991. 248 с.

20. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.

21. Олифер В.Г., Олифер Н.А. Компьютерные сети: Принципы, технологии, протоколы // Учебное пособие, 2 изд. СПб.: Питер, 2003. 668 с.

22. Погребинский С. Б., Стрельников В. П. Проектирование и надежность микропроцессорных ЭВМ. М.: Радио и связь, 1998. 166 с.

23. Додонов А. Г., Кузнецова М. Г., Горбачик Е. С. Введение в теорию живучести вычислительных систем / Под ред. В. А. Гуляева. Киев: Наук. Думка, 1990. 184 с.

24. Новые подходы к исследованию высоконадежных бортовых вычислительных систем / Пер. с англ., сост. В.А. Гнет, Г.Ф. Лункин // Сб. статей. М.: ГосНИИАС, Научно-Информационный центр, 1991. 4 с.

25. Preparata F., Metze G., Chien R. On connection assignment problem of diagnosable systems // IEEE Trans. On Electronic Computers. 1967. Vol. EC-16, No 12. P. 848-854.

26. Дмитриев Ю. Самодиагностика систем из однотипных блоков. Вопросы теории и построения вычислительных систем // Выпуск 73. Новосибирск: ИМ СОАН СССР, 1978. С. 107-121.

27. Харари Ф. Теория графов. М.: Мир, 1973.300 с.

28. The Thickness of Graphs / A Survey, P. Mutzel, T. Odenthal, M. Scharobrodt // Proc. Symp. Frontiers of Massively Parallel Computation. 1998. Feb. P. 96-101.

29. Клейнрок Л. Коммутационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970. 256 с.

30. A Methodology for Useroriented Scalability Analysis / D. Royo, M. Valero-Garca, A. Gonzlez and C. Mar // IEEE Int'l Conf. on Application Specific Systems, Architectures, and Processors. 1997. P. 304-315.

31. Thompson C. D. Area-Time complexity for VLSI // Proc. ACM, Symp. Theory of Computing. 1979. P 81-88.

32. The recursive grid layout sceme for VLSI layout of hierarchical networks / Chi-Hsiang Yen, E. A. Varvarigos, B. Parhami // Proc. Merged Int'l Parallel Processig Symp. & Symp. Parallel and Distributed Processing. 1999. Apr. P.48-55.

33. Efficient VLSI layouts of hypercubic networks / С. H. Yeh, E.A. Varvarigos, B. Parhami // Proc. Symp. Fron-tiers of Massively Parallel Computation. 1999. Feb. P. 98105.

34. VLSI layout and packaging of butterfly networks / С. H. Yeh, B. Parhami, E.A. Varvarigos, H. Lee // Proc. ACM Symp. Parallel Algorithms and Architectures. 2000. P. 196-205.

35. The recursive grid layout scheme for VLSI layout of hierarchical networks / C. H.Yeh, B. Parhami, E.A. Varvarigos // Proc. Merged Int'l Parallel Processing Symp. & Symp. Parallel and Distributed Processing. 1999. Apr. P. 441-445.

36. Layout of the Batcher bitonic sorter. S. Even, S. Muthukrishnan, M.S. Paterson, S. Cenk Sahinalp // Proc. ACM Symp. Parallel Algorithms and Architectures. 1998. P. 172-181.

37. Chen G., Lau F. Layout of the Cube-connected Cycles without Long Wires // The Computer Journal. 2001. Vol. 44. P. 374-383.

38. Kruskal C. P., Snir M. A unified theory of interconnection network structure // Theoretical Computer Science. 1986. Vol. 48. P. 75-94.

39. Кристофидес H. Теория графов: Алгоритмический подход. М.: Мир, 1978. 432 с.

40. Суворова Е. А. "Программа расчета количества шагов процесса определения работоспособной конфигурации параллельной системы-на-кристалле". / М.: 50200300205, 2003.

41. Serlin О. Fault-Tolerant Systems in Commercial Applications // Computer. 1984. Aug, Vol. 17, No 8. P. 19-30.

42. Hakimi S. L. and Amin A. T. Characterization of Connection Assignment of Diagnosable Sistems // IEEE Trans. On Computers. 1974. January. 23 p.

43. Agrawal P. RAFT: A recursive algorithm for fault tolerance // International conference on parallel Processing. Proc. IEEE. 1985. P. 814-821.

44. Воробьев B.A., Лаходынова H.B. Реконфигурация отказоустойчивой процессорной матрицы на основе сигналов согласия // Российская академия наук, Сибирское отделение. Автометрия. 1997. № 6.

45. Kuhl J.G., Reddy S. М. Distributed Fault-Tolerance for Large Multiprocessor Systems // In Proceeding of the 7th Annual Symposium on Computer Architecture. IEEE. 1980. May. P. 23-30.

46. A Diagnosis Algorithm for Distributed Computing Systems with Dynamic Failure and Repair / S. H. Hosseini, J. G. Kuhl, S. M. Reddy // IEEE Transactions on Computers C-33 (3). 1984. March. P. 223-233.

47. Practical Applications and Implementation of Distributed System-Level Diagnostic Theory / R. P. Bianchini, Jr. K. Goodwin, D. S. Nydick // In Proceeding of the Twentieth International Symposium on Fault-Tolerant Computing. IEEE. 1990. June. P. 332-339.

48. Bianchini R., Buskens Jr. R. Implementation of On-Line Distributed System-Level Diagnosis Theory // IEEE. Transactions on computers. Spesial issue on Fault Tolerant Computing. 1992. May. 15 p.

49. Вентцель E. С. Теория вероятностей. M.: Наука, 1969. 574 с.

50. IP Creatioi^ntegration Bus protocols limit design reuse of IP / By Ed Smith, Director, Business Development, Sonics Inc // Mountain View, Calif. EE Times. 2000. December 14.

51. Arpaci M., A. John. Buffer management for Shares-Memory ATM Switches // Copeland. IEEE Communication Surveys. 2000. First Quarter. 27 p.

52. VSI. System Level Design. Model Taxonomy. Version 1.0 25 // Virtual Socket Interface Alliance™. 1998. October.

53. Bainbridge W.J. and Furber. S.B. Asynchronous Macrocell Interconnect Using. MARBLE // IEEE. Transactions on computers. 2000. lip.

54. IDT Peripheral Bus (IPBus ™ ) Intermodule Connection Technology Enables Broad Range Of System-Level Integration. // IEEE. Transactions on computers.2000. 4 p.

55. PI-Bus VHDL Toolkit. Version 3.1 // Centre for VLSI and Computer graphic. 1997. 132 P

56. FISHPBus foundation library // Mentor Craphics Corp. 1998. 22 p.

57. Usselmann R. OpenCores SoC Bus Review. Rev. 1.0 // Mentor Craphics Corp. 2001. January. 9 p.

58. Open Core Protocol Specification. Release 1.0 // OCP-IP Association. 2001. 156 p.

59. A Comparison of Five Different Multiprocessor SoC Bus Architectures / Kyeong K. Ryu, Eung Shin, Vinsent J. Mooney. // IEEE. Transactions on computers. 2001. 9 p.

60. AMBA Specification. Revision 2.0. //ARM Limited. 1999. 123 p.

61. Суворова E. А. "Пакет программ расчета характеристик коммуникационных систем на базе коммутатора и на базе шины." / М.: ВНТИЦ, 50200300182,2003.

62. Суворова Е. А. "Пакет программ моделирования и синтеза блока коммуникаций на базе шины AMBA АНВ для систем-на-кристалле." / М.: ВНТИЦ, 50200200640, 2002.

63. Суворова Е. А. "Пакет программ моделирования и синтеза блока коммуникаций на базе коммутатора с интерфейсом АМВА АНВ для систем-на-кристалле." / М.: ВНТИЦ, 50200200623,2002.

64. The SPARC Architecture Manual, Version 8 Revision// SAV080SI9308 SPARC International Inc. 1992. 640 p.

65. Суворова E.A., Шейнин Ю.Е. Проектирование цифровых систем на VHDL. СПб.: БХВ-Петербург, 2003. 576 с.

66. Symmetries and Sense of Direction in Labeled Graphs. / P. Flocchini, A. Roncato, N. Santoro // DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science. 1998. Vol. 87. P 34-40.

67. Folcchini P. Minimal Sense of Direction in Regular Networks // Information Processing Letters. 1997. Vol. 61, N 6. P 331-338.

68. On Edge Numbering of the n-Cube graphs / S. L. Bezrukov, N. Grunwald, K. Weber // Discrete Applied Mathematics. 1993. Vol. 46, No 2. P. 99-116.

69. Суворова E. А. "Программа формирования множества внешних модулей для параллельных систем-на-кристалле." / М.: ВНТИЦ, 50200300046, 2003.

70. Суворова Е. А. "Программа генерации топологии связей между модулями параллельных систем-на-кристалле." / М.: ВНТИЦ, 50200300181,2003.

71. Суворова Е. А. "Программа моделирования процесса определения работоспособной конфигурации параллельной системы-на-кристалле." / М.: ВНТИЦ, 50200300179,2003.

72. Шейнин Ю. Е., Суворова Е. А. Организация связей с внешними каналами в параллельной вычислительной системе-на-кристалле// Тез. докл. 6 научная сессии аспирантов ГУАП. Санкт-Петербург, 2003 г/СПб. РИО ГУАП, 2003 г., стр. 233234.

73. Суворова Е. А. Формирование работоспособной конфигурации при инициализации параллельной вычислительной системы-на-кристалле// Сборник ГУАП/ РИО ГУАП, 2000 г., стр. 343.

74. Вероятностные модели компьютерных архитектур/ Манита А. Д., Филин А. В., Малышем В. А // Фундаментальная и прикладная математика. T3.N1. 1997. Pp. 263-301

75. Майоров С. А., Новиков Г. И., Алиев Т. Н. Основы теории вычислительных систем: Уч. пос. для вузов. М.: Высш. шк, 1991. 345 с.

76. Шейнин Ю. Е., Суворова Е. А. Особенности организации модуля параллельной вычислительной системы на кристалле// Тез. докл. 5 научная сессии аспирантов ГУАП. Санкт-Петербург, 2002 г/СПб. РИО ГУАП, 2002 г., стр. 227-228

77. Основные положения диссертации опубликованы в следующих работах:

78. Суворова Е. А., Шейнин Ю. Е. Проектирование цифровых систем на VHDL., СПб., БХВ-Петербург, 2003 г., 576 с.

79. Суворова Е. А., Шейнин Ю. Е., Язык VHDL для проектирования систем на СБИС. Учебное пособие. СПб., РИО ГУАП, 2001 г., 212 с.

80. Шейнин Ю. Е, Суворова Е. А. Архитектура вычислительного модуля для параллельных систем на кристалле// Тез. докл. всероссийской научно-технической конференции 25 Гагаринские чтения М., 1999 г., стр 336

81. Суворова Е. А. Влияние организации систем-на-кристалле на архитектуру параллельных ВС// Тез. докл. 3-ей научной сессии аспирантов, докторантов и соискателей, апрель 2000 г.: Сборник/ СПб., РИО ГУАП, 2000 г., стр. 191

82. Суворова Е. А. Формирование работоспособной конфигурации при инициализации параллельной вычислительной системы-на-кристалле// Сборник ГУАП/ РИО ГУАП, 2000 г., стр. 232-240

83. Суворова Е. А. Специфика архитектуры систем-на-кристалле// Тез. докл. всероссийской научно-технической конференции 26 Гагаринские чтения М., 2000 г., стр. 256

84. Суворова Е. А. Топология связей вычислительных модулей в параллельных системах на кристалле// Тез. докл. 7 ежегодной международной научно-техническая конференции студентов и аспирантов. МЭИ 2001 г., стр. 304

85. Ю.Шейнин Ю. Е., Суворова Е. А. Организация межмодульных связей в параллельных вычислительных системах на кристалле// Тез. докл. 4 научная сессии аспирантов ГУАП. Санкт-Петербург, 2001 г/СПб. РИО ГУАП, 2001 г., стр. 247

86. П.Шейнин Ю. Е., Суворова Е. А. Особенности организации модуля параллельной вычислительной системы на кристалле// Тез. докл. 5 научная сессии аспирантов ГУАП. Санкт-Петербург, 2002 г/СПб. РИО ГУАП, 2002 г., стр. 432-435

87. Список зарегистрированного программного обеспечения

88. Суворова Е. А. "Программа расчета количества шагов процесса определения работоспособной конфигурации параллельной системы-на-кристалле". / М.: 50200300205,2003.

89. Суворова Е. А. "Пакет программ расчета характеристик коммуникационных систем на базе коммутатора и на базе шины." / М.: ВНТИЦ, 50200300182, 2003.

90. Суворова Е. А. "Пакет программ моделирования и синтеза блока коммуникаций на базе шины АМВА АНВ для систем-на-кристалле." / М.: ВНТИЦ, 50200200640,2002.

91. Суворова Е. А. "Пакет программ моделирования и синтеза блока коммуникаций на базе коммутатора с интерфейсом АМВА АНВ для систем-на-кристалле." / М.: ВНТИЦ, 50200200623,2002.

92. Суворова Е. А. "Программа формирования множества внешних модулей для параллельных систем-на-кристалле." / М.:' ВНТИЦ, 50200300046,2003.

93. Суворова Е. А. "Программа генерации топологии связей между модулями параллельных систем-на-кристалле." /М.: ВНТИЦ, 50200300181, 2003.

94. Суворова Е. А. "Программа моделирования процесса определения работоспособной конфигурации параллельной системы-на-кристалле." /М.: ВНТИЦ, 50200300179,2003