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

Содержание к диссертации

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

Содержание 3

Введение 6

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

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

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

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

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

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

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

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

3. Параллельные системы-на-кристалле 18

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

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

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

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

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

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

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

7. Структура ІР-узлов и IP-блоки для их построения 26

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

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

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

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

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

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

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

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

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

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

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

условий их применения

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

14. Постановка задачи 53

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

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

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

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

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

19. Формирование работоспособной конфигурации при инициализации 64 ПСнК

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

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

22. Оценка характеристик алгоритма 74

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

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

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

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

24. Структура ІР-узла ПВСнК 81

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

26. Описание коммуникационной системы 83

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

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

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

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

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

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

32. Имитационные модели 105

33. Оценка аппаратных затрат на реализацию коммуникационной системы 114 ІР-узла

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

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

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

34. Требования к описаниям СнК в целом, ІР-узлов и ІР-блоков для СнК 120

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

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

36. Организация настраиваемого интерфейса ІР-узлов 124

37. Организация структуры связей между ІР-узлами 128

4.3 Организация внутренней структуры ІР-узла 136
43.1 Возможность организации гибкого интерфейса ІР-блока 136

2. Организация коммуникационной системы между блоками внутри ІР-узла 139

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

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

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

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

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

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

тора

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

трехмерная решетка, гиперкуб

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

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

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

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

шины и на базе коммутатора

П.7 Модели на GPSS для определения параметров системы на базе шины 178

и на базе коммутатора в тех случаях, когда теоретический расчет не

возможен

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

коммутатора на VHDL

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

кристалле

П.10 Пример расчета характеристик коммуникационной системы на базе 197

шины и на базе коммутатора для процессора "Мультикор"

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

Введение к работе

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

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

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

М.Б. Игнатьевым, А.В. Каляевым, В.В. Корнеевым, В.К. Левиным,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эволюция вычислительных структур существенно зависит от развития производственных технологий. Можно выделить следующие основные направления развития технологий: увеличение степени интеграции, увеличение размеров кристаллов и количества слоев металлизации, увеличение количества выводов микросхем, увеличение быстродействия элементов и скорости распространения сигнала в линиях связи, снижение потребляемой и рассеиваемой мощности, [1]. В соответствии с этим происходит увеличение количества функциональной логики и объема памяти на кристалле. Улучшение характеристик схем по этим направлениям происходит с различной скоростью, которая определяется особенностями совершенствования процесса литографии.

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

От используемой технологии литографии зависят геометрические размеры и форма объектов, составляющих рисунок схемы, а также материалы, используемые для создания рисунка схемы. Литографию принято характеризовать размером полушага - проектной нормой. Этот размер определяет минимально воспроизводимый размер объекта и, минимальное расстояние между объектами (размер раздельно воспроизводимых параллельных отверстий в маске). В 2000 г. размер полушага составлял 0,18 мкм, а к 2010 г. прогнозируется снижение этого параметра до 0,045 мкм, более чем в 3.5 раза. [1, 3]. В настоящее время сосуществует несколько технологий литографии. Наиболее широко используется оптическая литография (проектные нормы до 0,13 мкм). Для достижения меньших проектных норм используются экстремальная ультрафиолетовая литография, рентгеновская литография, литография с использованием электронной и ионной проекции. Для этих технологий существует не только предельно возможный минимальный размер объекта, но и предельно допустимый максимальный размер объекта. При реализации объектов большего размера резко возрастает время изготовления и снижается качество.

Современные технологии позволяют создавать 6-8 слоев металлизации. К 2010 году прогнозируется увеличение числа слоев до 10-12. Различные слои могут создаваться по различной технологии, [1,2].

Современные транзисторы в 20 раз быстрее ив 100 раз меньше, чем 2 десятилетия назад. Исследование Тауера [4] показало, что темпы роста производительности наиболее часто используемых в настоящее время транзисторов (комплиментарные полевые транзисторы КМОП) по мере уменьшения их размеров

вскоре снизятся. Пути поддержания темпов роста производительности он рекомендует искать в транзисторах новых типов, в низкотемпературном режиме работы и повышении степени интеграции функций. Нынешние темпы повышения производительности можно сохранить еще в течение 10 - 15 лет, но только посредством поиска новых материалов и структур транзисторов, качественного изменения литографии. Однако закон Мура, согласно которому число элементов наиболее сложной из существующих интегральных микросхем каждый год удваивается, продолжает действовать до сих пор, и предсказывается, что его действие сохранится в ближайшее десятилетие, [3]. Мур указал, что удвоение числа элементов в интегральных схемах будет происходить за счет трех факторов: на 50% - за счет увеличения разрешающей способности литографии; на 25% - за счет увеличения размера кристалла благодаря улучшению производственных процессов и литографии; на 25% - за счет разного рода инноваций, в частности появления новых методов формирования элементов на кристалле (из которых подавляющее число составляют транзисторы). Вследствие такого быстрого роста степени интеграции на первый план выходит проблема масштабирования рисунков схем, [3].

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

Вследствие уменьшения размеров транзисторов, увеличения плотности их упаковки, увеличения геометрических размеров кристаллов и увеличения количества слоев металлизации на кристалле становится возможным размещать все больше функциональной логики и блоки памяти большего объема. В таблице 1.1 приведены данные прогноза развития технологии до 2014 года, [1].

Таблица 1.1 - Прогноз развития технологии микропроцессорной логики и памяти

Прогнозируется, что к 2014 году площадь кристалла станет почти в 2 раза больше, чем в 1999 г. Количество транзисторов, размещаемых на кристалле за этот период времени возрастет в 180 раз и превысит 4 миллиарда. Линейные размеры вентилей уменьшатся в 7 раз, размер ячеек DRAM уменьшится более, чем в 80 раз. Если в 1999 г. плотность размещения ячеек DRAM составляла 0.27 Гбит/см , то в 2014 г. прогнозируется 24.5Гбит/см². Таким образом в 2014 г., на той же площади поверхности кристалла станет возможным размещать память DRAM, объем которой будет в 90 раз больше, чем в 1999 г.. В 2014 году прогнозируется возможность размещать на кристалле с площадью поверхности 400 мм , 32Гб памяти DRAM. Плотность размещения транзисторов SRAM за период с 1999 по 2014 год возрастет более, чем в 100 раз. Плотность размещения транзисторов комбинационной логики за этот же период времени возрастет только в 10 раз. Эта тенденция иллюстрируется

млн./см2

рисунком 1.1.

комбинационная логика SRAM

Однако, не по
всем направлениям
развития технологии
прогнозируется
столь быстрый рост
показателей. За

период времени с 1999 г. по 2014 г.

прогнозируется, что

количество микросхем количество

общее

выводов

Рисунок 1.1 — Прогноз роста плотности размещения транзисторов

(плотность размещения транзисторов указана по осу ординат) на

кристалле для комбинационной логики и памяти

информационных выводов возрастет только в 2 раза. К 2014 году количество информационных выводов достигнет 1400. Разрыв в развитии этих тенденций иллюстрируется рисунком 1.2, [5]. Количество слоев металлизации так же растет не быстро.

Количество транзисторов на кристалле (млн,) количество внешних выводов

<$ ^

*Г

95,2

-23,8,

^

»47,6,.

Рисунок 1.2 — Тенденции роста количества внешних выводов кристалла по сравнению с числом транзисторов на кристалле

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

Можно выделить три типа линий связи: локальные, средние и глобальные, [1].

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

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

Глобальные линии - линии между функциональными блоками. Эти линии располагаются в верхних слоях металлизации. Их длина, как правило, лежит в интервале от 4 мм до полу периметра кристалла, [1]. В настоящее время для расположения этих линий отводится два слоя металлизации. В ближайшее десятилетие прогнозируется рост числа слоев до четырех — пяти.

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

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

Таблица 1.2 —Тенденции развития межэлементных соединений в комбинационных схемах

В таблице 1.3 приведены данные для памяти DRAM

Таблица 1.3 — Тенденции развития межэлементных соединений в DRAM

В таблице 1.4 приведены данные для СнК.

Таблица 1.4 — Тенденции развития межэлементных соединений в SoC

Как можно видеть из этих таблиц, характеристики межсоединений СнК близи к

характеристикам межсоединений микропроцессорной логики.

Шаг глобальных, средних и локальных линий связи за период времени с 1999 г по 2014 год уменьшается более, чем в 5 раз. Шаг локальных линий связи в 1,25 раза меньше шага средних линий связи и в 2 раза меньше шага глобальных линий связи. Эта тенденция иллюстрируется рисунком 1.3. Как можно видеть из этого графика, снижение накладных расходов на реализацию глобальных линий более ощутимо, чем для средних и локальных линий связи. Это позволяет более широко использовать их при проектировании.

Количество слоев металлизации, отводимое для линий связи растет медленно. В 2003 г. возможно использование до 7 слоев металлизации, то к 2014 году прогнозируется рост числа слоев до 10. Однако, для широкого класса схем, даже увеличение количества слоев металлизации на один позволяет существенно сократить длину межсоединений, количество переходов линий связи из слоя в слой и

оптимизировать распределение рассеиваемой мощности на кристалле.

Рассмотрим, как

изменяется время

распространения

сигнала в линиях связей

различных типов.

Разница между

Рисунок 1.3 —Тенденции изменения шага (минимальной толщины) локальных, средних и глобальных линий связи

«локальной» частотой и

частотой, с которой

сигналы

распространяются по

кристаллу, со временем

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

Тенденции изменения частоты для локальных и глобальных сигналов внутри

кристалла и на линиях кристалл - плата представлены на рисунке 1.4.

Если в 2000 г. локальная и глобальная тактовые частоты практически совпадали, то, согласно прогнозу, к 2014 году разница между локальной и глобальной тактовой частотой вырастет в 3,75 раза, см. рисунок 1.5. Глобальная тактовая частота практически совпадает с тактовой частотой на линиях кристалл - плата, если используются мультиплексированные линии и в два раза выше частоты на линиях кристалл - плата, если используются линии без мультиплексирования.

1.1.5 Изменение параметров схем в результате масштабирования Вследствие быстрого развития технологии очень важной становится проблема изменения параметров схем при масштабировании. Можно выделить следующие основные причины масштабирования, [1]; увеличение геометрических размеров

^

АР <& Г.О г^

rS>" cS^ гч# rS>^V

с>

Частота

-локальный сигнал тактирования

-глобальный сигнал тактирования

- кристалл - плата (мультиплексированные линии)

кристалл - плата

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

линии)

Соотношение частоты

локального и глобального

^

тактового сигналов

Рисунок. 1.5—Тенденции изменения

соотношения частоты на локальных и

глобальных линиях связи

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

связей и в вентилях Относительная задержка сигнала в линиях связи 100

Рисунок 1.4 — Тенденции изменения частоты

сигналов на локальных и глобальных линиях связи

внутри кристалла и на линиях кристалл - плата

Задержка в
вентилях

- Задержка в локальных линиях связи

Задержка в
глобальных линиях
связи с

повторителями

Задержка в

глобальных линиях связи без повторителей

проектная норма, мкм

Рисунок 1.6 — Тенденции изменения задержек в элементах и линиях связи с изменением проектной нормы

при переходе к

меньшим проектным

нормам,

иллюстрирующаяся

рисунком 1.6. При

изменении

проектной нормы от

0,25 мкм до 0,035

мкм относительные

задержки в вентилях

уменьшаются почти

в 10 раз,

относительные

задержки в

локальных линиях

связей уменьшаются,

но не так быстро, только в два раза. Относительные задержки сигнала в глобальных линиях связи с использованием специального оборудования возрастают в 2 раза, без использования специального оборудования возрастают в 50 раз.

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

Тенденции развития технологии

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

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

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

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

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

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

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

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

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

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

Описание виртуальных компонентов может выполняться с использованием графических редакторов принципиальных схем или с использованием языков описания аппаратуры. В этом случае виртуальный компонент считается описанным на уровне Soft, верхнем уровне описания. На базе описания компонента на уровне Soft может быть сгенерирован частично оптимизированный список связей, ориентированный на элементную базу конкретной фирмы-производителя - описание на уровне Firm. Если в организации элемента на уровне Soft была заложена возможность настроек, то на уровне Firm она сохраняется. На базе описания на уровне Firm может быть создан полностью оптимизированный список связей, ориентированный на конкретную реализацию кристалла СБИС - описание на уровне Hard, нижнем уровне описания. Настройки компонентов на этом уровне невозможны. [8].

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

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

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

Типы компонентов, которые могут быть интегрированы в рамках одного кристалла

Логика % SRAM Rash E-DRAM CMOSRF FPGA MB/IS FRAM

В настоящее время в рамках
одной СнК могут быть

интегрированы компоненты,

принадлежащие к большинству
современных технологий, [1]. На
рисунке 1.7, [1], представлены типы
компонентов, которые могут быть
интегрированы в СнК. Однако, это
приводит к усложнению

химич. сенсої: технологического процесса,

Электро-биол.

электро-опти. добавлению масок, [1].

В таблице 1.5. приведены
технологические возможности

гисунок і. / —і ипы компонентов, которые могут быть интегрированы в рамках одного кристалла " *

Таблица 1.5 —Технологические возможности ведущих фирм

Продолжение таблицы 1.5

Как можно видеть из этой таблицы большинство компаний производителей позволяют интегрировать в рамках одного кристалла процессорную логику, память типа SRAM и DRAM. Это позволяет строить в рамках одного кристалла системы, включающие в себя и функциональную логику и память. Как можно видеть из этой таблицы, размер ячейки DRAM по-прежнему в среднем на порядок меньше, чем размер ячейки SRAM, [10]. Однако память типа SRAM обладает большим быстродействием и ее проще интегрировать на кристалле с процессорной логикой.

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

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

200 процессоров

2-4 процессора

1-2 процессора

Количество вычислительных узлов на кристалле

Рисунок 1.8- Тенденция увеличения количества вычислительных узлов на кристалле

Ядро современного RISC процессора может быть реализовано с использованием 100 - 500 тысяч вентилей, ядро SISC процессора класса Pentium Pro для своей реализации требует не более чем на порядок больше вентилей, [11]. С учетом приведенных выше оценок роста сложности кристаллов в ближайшем будущем на одном кристалле можно будет размещать сотни процессорных модулей.

В настоящее время существуют ПСнК, в которых объединены 4-16 процессор} d. Например, Hydra объединяет на одном кристалле 4 однотипных микропроцессора, подобных R10000 процессору, [12]. В рамках проекта PPRAM 256-4 на кристалле так же объединяется 4 однотипных процессорных модуля. Каждый процессорный модуль содержит 256 Мб памяти. Взаимодействие между процессорными модулями в рамках кристалла осуществляется по PPRAM link -однонаправленным последовательным каналам, выполненным на базе стандарта SCI

(IEEE 1596-1992), [13]. FPGA фирмы Xilinx уже могут включать до 4 RISC процессоров с архитектурой PowerPC.

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

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

Организация СнК как системы с распределенной архитектурой диктуется особенностями технологии. Как было рассмотрено в параграфе 1.1, с уменьшением проектной нормы задержки в линиях связи будут возрастать по отношению к задержкам внутри блоков. Если система разрабатывается как единый блок, это приведет к увеличению длительности такта. Так, например, при использовании технологии 0,1 мкм сделать блок, занимающий такую же площадь на кристалле, как при использовании технологии 0,35, то его тактовая частота будет на порядок ниже, [15]. Если система строится на базе модулей, размер одного модуля будет существенно меньше размера кристалла в целом. Это позволит сделать линии межсоединений внутри модуля короче, следовательно, каждый из модулей СнК сможет функционировать с более высокой тактовой частотой.

В настоящее время существует ряд мультипроцессорных СнК (т. н. CMP - Chip Multiprocessors), которые включают в себя до четырех процессорных модулей, работающих с одной общей памятью, [14]. Такие системы трудно масштабировать, поскольку память в них быстро становится узким местом. Существуют так же системы, состоящие из нескольких процессорных блоков и нескольких блоков памяти. Недостатком таких систем становится относительная удаленность памяти от процессорной логики, в результате чего возрастает время доступа к памяти, что ведет к снижению производительности системы.

Используемые в современных СМР симметричные мультипроцессорные структуры не могут обеспечить достаточную производительность для большого числа процессоров. Проблема масштабируемости параллельных вычислительных структур в традиционном исполнении решается в рамках перехода от симметричных мультипроцессоров с общей памятью к системам с распределенной архитектурой -системам классов DSM или МРР, [Culler]. И в системах класса DSM (Distributed Shared Memory, системы с логически общей, физически - распределенной, памятью), и в системах класса МРР (Message-Passing Multiprocessors, системы с явным обменом сообщениями), параллельная система компонуется из вычислительных модулей (processing modules), включающих процессор (или несколько процессоров), локальную память и коммуникационные блоки для обмена сообщениями между модулями (в МРР - явного, в DSM - аппаратно реализуемого). В распределенной структуре параллельной ВС такие вычислительные модули часто называют также «узлами» (nodes).

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

Такая организация ПСнК так же хорошо согласуется с концепцией повторно используемых компонентов.

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

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

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

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

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

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

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

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

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

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

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

При проектировании на базе ІР-блоков разработчик получает возможность сконцентрироваться на характеристиках IP-узла, при проектировании системы на базе

ІР-узлов разработчик получает возможность сконцентрироваться на характеристиках вычислительной структуры в целом.

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

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

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

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

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

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

конфигурацию. Методы самотестирования должны учитывать распределенность структуры ПСнК и ее масштабируемость.

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

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

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

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

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

Для построения ІР-узла могут быть использованы повторно используемые блоки процессора, памяти, контроллера межузловых связей, блоки специального назначения. Эффективность функционирования ІР-узлов зависит не только от выбора блоков, но и от эффективности функционирования системы коммуникаций между ними. Построение ІР-узла как компонента СнК диктует необходимость перехода от традиционных методов построения межсоединений в ВС к новым методам, адекватным СнК. Существующие в настоящее время стандарты внутрикристальных шин определяются так, как если бы между компонентами осуществлялось соединение типа «точка-точка». В результате физическая реализация этих стандартов может иметь не только структуру шины, но и коммутатора, или соединения могут прокладываться, например, между каждой парой компонентов, между которыми существует информационное взаимодействие, [17, 18].

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

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

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

Метод описания компонентов в графической форме имеет следующие недостатки. В этом случае происходит привязка описания виртуального компонента к конкретной элементной базе. Это может сделать перенос компонента на другую элементную базу практически не возможным или приводящим к нерациональным решениям, [19]. Описание компонента в графическом виде практически не возможно сделать параметризуемым. Решить эти проблемы можно за счет использования языков описания аппаратуры, таких как Verilog, AHDL, VHDL и др. Структура и функционирование виртуального компонента могут быть специфицированы с использованием конструкций языка без явной привязки к конкретной элементной реализации. Языки описания аппаратуры позволяют выполнять гибкое, параметрическое описание схемы, [19]. Изменение значений параметров позволяет влиять на внутреннюю организацию и функционирование виртуального компонента. Это позволяет ускорить процесс проектирования. Языки типа Verilog предназначены в основном для описания принципиальных схем. VHDL позволяет описывать не только принципиальные, но и функциональные схемы на структурном и поведенческом уровне. Он так же предоставляет более широкие возможности по параметризации описаний, [69]. В связи с этим в данной работе для описания аппаратуры используется VHDL.

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

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

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

1) Рассмотрены тенденции развития производственных технологий, существенные для построения СнК. Определено влияние развития интегральных

технологий, неравномерного по различным направлениям, на характеристики схемотехнической реализации вычислительных устройств в кристаллах СБИС.

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

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

4. Рассмотрено влияние средств автоматизированного проектирования на построение СнК, возможности языков описания аппаратуры высокого уровня для создания повторно используемых виртуальных компонентов.

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

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

   методы размещения подмножества модулей, имеющих внешние каналы связи системы-на-кристалле;

   методы самотестирования и формирования работоспособной конфигурации ПСнК;

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

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

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

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

   Как было рассмотрено в разделе 1, ПСнК должна иметь распределенную структуру и строиться на базе совокупности вычислительных узлов. Система коммуникаций может быть организована на базе шин, коммутаторов или непосредственных связей между узлами. Как отмечалось в разделе 1, реализация шин сталкивается с технологическими проблемами. Системы на базе шин трудно масштабировать. В [20, 21, 22] были рассмотрены варианты построения мультипроцессорных систем на базе шинных архитектур Global Bus I Architecture (GBIA), Global Bus II Architecture (GBIIA), Bi-FIFO Bus Architecture (BFBA). Было показано, что производительность систем на базе этих стандартов ограничивается пропускной способностью шин. Кроме того, с ростом количества узлов длина шин возрастает, что также приводит к увеличению времени передачи данных. Поэтому коммуникационная система ПСнК должна быть организована или на базе коммутаторов или на базе непосредственных связей между ІР-узлами. В данной работе будут рассмотрены коммуникационные системы на базе непосредственных связей между узлами. В данном разделе определен набор характеристик, существенных для ПСнК, разработана методика оценки топологий с точки зрения их применимости для СнК.

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

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

   Таким образом, характеристики топологий ПСнК можно разделить на две группы: характеристики топологии на структурном уровне и характеристики топологии на уровне рисунка схемы.

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

   систем-на-кристалле с учетом технологии реализации

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

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

   Анализ структурных свойств системы на графе неизбежно приобретает топологический характер, который предполагает использование ряда характеристик, определяющих количественную меру топологии объекта. Использование этих характеристик позволяет уже на ранних стадиях проектирования оценивать качество структуры системы с позиции общесистемного подхода. В настоящее время различными авторами предложено несколько вариантов наборов характеристик систем. В соответствии с классификацией Г. Т. Артамонова, В. Д. Тюрина [23], В. В. Корнеева [24], В. Г. Олифера и Н. А. Олифера [25] можно выделить следующие основные классы топологических характеристик:

   1. характеристики, позволяющие оценить сложность системы;

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

   3. характеристики, позволяющие оценить возможности масштабирования системы;

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

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

   Сложность сети растет с ростом числа узлов и ребер. Разнообразие узлов по валентности усложняет сеть за счет уменьшения унификации в оборудовании узлов, [23]. В соответствии с этим для оценки сложности могут быть использованы, следующие параметры: количество вершин графа - V, количество ребер графа - Q, валентность (степень) вершин графа - В. Если вершины графа имеют различную валентность, то количество типов вершин по валентности, [24].

   На уровне структуры сети среднее время передачи сообщения может быть оценено с использованием среднего диаметра сети. Средний диаметр (обозначим его D_s) - средняя длина пути между вершинами (под которым понимается математическое ожидание расстояния между вершинами при равновероятном выборе пар вершин). Минимизация среднего диаметра графа межмодульных связей ведет к

   сокращению числа транзитных передач и, следовательно, к увеличению эффективности функционирования системы, [24].

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

   Для обеспечения отказоустойчивости системы в целом необходимо, чтобы принципы надежности системы были заложены на всех ее уровнях, [27]. Классические критерии надежности как среднее время наработки на отказ, вероятность отказа, интенсивность отказов, пригодны только для систем с относительно простой структурой. Для вычислительных устройств становится более актуальной отказоустойчивость, под которой понимается способность системы скрывать от пользователя отказ отдельных элементов, [25]. ПСнК относятся к классу избыточных систем, в которых в любой момент времени все исправные модули активны и применяются для решения задач. Избыточность в этих системах представляется в неявном виде. При отказе вычислительного узла осуществляется реконфигурация системы для исключения отказавшего узла. При этом происходит снижение производительности. Критерий выхода из строя такой системы можно связать с определенным уровнем производительности системы, можно также определить минимально допустимое число работоспособных узлов, [26]. СнК являются неремонтопригодными. Для того, чтобы каждый узел мог определить множество связанных с ним работоспособных узлов в начале функционирования системы должна выполняться специальная процедура. Алгоритм такой процедуры предложен в параграфе 2.4.

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

   Показатели сложности на структурном уровне

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

   Для СнК важной характеристикой сложности становится минимальное количество слоев металлизации, необходимое для размещения структуры связей на кристалле. Определение этой характеристики предполагается на базе «книжной» толщины графа связей. Использование классической толщины является слишком строгим условием. Толщины графа связей - наименьшее числа планарных подграфов, объединение которых образует исходный граф, [31]. При таком определении предполагается, что каждая вершина исходного графа входит в один или несколько

   подграфов и каждое ребро исходного графа входит в один из планарных подграфов. Каждый из подграфов может быть размещен в одном слое металлизации. Современные технологии предполагают возможность перехода линий связи из слоя в слой. В соответствии с развитием технологий был определен ряд модификаций понятия толщины графа. В частности было определено понятие 4-толщины (4-Thickness) и книжной толщины (book-thickness). 4-толщина равна минимальному количеству подграфов, валентность вершин которых не превосходит 4, на которое можно разбить исходный граф. Появление этого понятия связано с тем, что при проектировании рисунков печатных плат и СнК рисунки узлов системы внедряются в двумерную решетку, в которой каждый узел имеет четыре непосредственных соседа. При определении книжной толщины граф разбивается на «страницы» - планарные подграфы. Часть ребер исходного графа может не принадлежать страницам, а переходит от страницы к странице по «корешку» книги. Количество страниц определяет книжную толщину графа. Для оценки характеристик графа с точки зрения возможности его применения для СнК используется именно книжная толщина, но предполагается, что ребро может переходить от одного планарного графа к другому не только по «корешку», но в любом месте рисунка. Это наиболее точно отражает особенности технологии, [32].

   Показатели времени передачи сообщений

   Оценим задержку передачи сообщения в сети. Пусть средний диаметр сети равен D_s. Это означает, что при передаче сообщения оно проходит транзитом в среднем через D_s ребер и (D_s-1) вершин графа связей. Обозначим среднее время передачи сообщения между модулями - Т_г, среднее время пребывания сообщения в очереди на обработку - Т₀. Тогда среднее время передачи сообщения по сети определяется следующим образом, [33]:

   T_s=(D_s-l)-T₀ + D_s'T_r; (2.1)

   Таким образом, на структурном уровне среднее время передачи сообщения по сети прямо пропорционально среднему диаметру сети.

   Вычислительные узлы обмениваются информацией не только между собой, но и с устройствами, находящимися за пределами кристалла. Как было отмечено в первом разделе, число внешних выводов СБИС растет существенно медленнее, чем сложность СБИС, число элементов на кристалле. Вследствие этого, не все узлы СнК могут иметь связи с внешним миром. Будем называть множество узлов, которые имеют связи с внешним миром множеством внешних узлов. Размещение множества внешних узлов определяет среднее время доступа к информации за пределами кристалла, [77]. Обозначим среднее расстояние от узла системы до внешнего узла D_v. Тогда по аналогии с T_s среднее время доступа к информации за пределами кристалла можно оценить следующим образом:

   T_V=((D_V-1) T₀+D_sT_r) + (Ть+Td); (2.2)

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

   Масштабируемость

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

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

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

   Существует общий подход для определения критерия масштабируемости на базе некоторой выбранной характеристики, [34]. Пусть выбрана характеристика F(p). Тогда можно определить функцию, определяющую рост этой характеристики в зависимости от роста параметра p. (1+т) определяет, во сколько раз вырос параметр

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

   _{Н{щр) =} ^ГЬА (2.4)

   Эта функция позволяет определить во сколько раз выросла характеристика
   F(p),'eanH параметр р вырос в (т+1) раз. ,. ,*

   Обозначим функции масштабирования: количества ребер графа от количества вершин - H_q(m,V); валентности от количества вершин - Hb(m,V), среднего диаметра от количества вершин - Hd(m,V), среднего расстояния до внешних узлов от количества вершин - H_v(m,V). Функция масштабирования количества ребер от количества вершин определяется следующим образом:

   _Щ(т,у₎₌Ши^Ш ₍₂.₅₎

   Q(V)*m Определенная таким образом функция позволяет определить, во сколько раз вырастет количество ребер, если количество вершин увеличится в т+1 раз. Для остальных функций определение может выглядеть аналогично.

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

   Модели, используемые для оценки характеристик рисунков схем

   Для представления рисунка схемы в целом широко используется модель Томпсона, [35]. В соответствии с этой моделью граф связей внедряется в двумерную решетку. Рисунки вычислительных модулей представляются квадратами со стороной h. Линии связи могут прокладываться горизонтально и вертикально вдоль линий решетки. Различные линии могут пересекаться под прямым углом, но не могут перекрываться. Точки изменения направления линий не могут совпадать. Считается, что линии связи между узлами имеют единичную толщину. Площадь, занимаемая схемой в целом, определяется как площадь прямоугольника минимального размера, на котором можно разместить все вычислительные узлы и линии связи. Если для линий связи отводится два слоя металлизации, то в одном из них располагаются фрагменты линий, расположенные вертикально, а в другом - фрагменты линий, расположенные горизонтально. Каждый изгиб линии связи соответствует ее переходу из слоя в слой. Поскольку в ряде случаев может быть сгенерирован рисунок схемы, количество переходов линий связи в котором будет меньше, модель Томпсона позволяет оценить верхнюю количества переходов.

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

   остаются промежутки для прокладывания необходимого количества линий связи, [35].

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

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

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

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

   Обозначим длину условной линии связи L_u. Узлы могут располагаться в соседних ячейках решетки по вертикали или горизонтали. В этом случае длина условной линии связи между модулями равна линейному размеру модуля h (L_u=h). Узлы могут располагаться не рядом, но в одном столбце или в одной строке решетки. В этом случае L_u=(k+1)' h, где к - количество узлов, находящихся между связываемыми. Узлы могут располагаться в разных столбцах и в разных строках. В этом случае L_u=(k+l+m+l)- h, где к — количество узлов, находящихся между связываемыми в строке, m - количество узлов, находящихся между связываемыми в столбце.

   Обозначим количество переходов одной условной линии связи из слоя в слой — N_u. Рассмотрим те же варианты, что и при определении условной длины линий связи. Будем считать, что если узлы расположены в соседних ячейках решетки по горизонтали или вертикали, линия связи между ними целиком расположена в одном слое металлизации. Для такой связи N„=0. Когда узлы расположены в одном столбце

   или в одной строке, но не рядом, их центры также могут быть соединены вертикальной или горизонтальной линией. Однако, если какие-либо из модулей, расположенных между рассматриваемыми, также связаны, то линии связи в этом случае перекроются, что не допустимо. Рассмотрим, как этого можно избежать на примере узлов, расположенных в одной строке. Будем считать, что линия связи состоит из трех участков. Первый и третий (имеют пренебрежимо малую длину) — расположены вертикально, позволяют сместить линию связи относительно центров узлов вверх или вниз. Второй участок горизонтальный. Таким образом, на линии связи будет два перехода из слоя в слой - N_u=2. Эта оценка может быть несколько завышенной по сравнению с реальной ситуацией, поскольку в синтезированном рисунке геометрические места соединяемых портов различных модулей могут находиться не на одной линии, связи в этом случае перекрываться не будут. Аналогично линия связи между модулями, находящимися в разных столбцах и строках максимально может состоять из четырех отрезков. Первый (пренебрежимо короткий) предназначен для отведения линии в сторону от центра узла, второй и третий предназначены для приближения линий к нужному узлу, четвертый, как и первый предназначен для приведения линии к центру узла. Таким образом, линия связи насчитывает три перехода из слоя в слой - N„=3. Эта оценка так же несколько завышена. Таким образом, предлагаемая модель позволяет получить оценку верхней границы количества переходов линий связи из слоя в слой.

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

   Сложность

   Для определения сложности реализации конкретного рисунка схемы на кристалле существенны следующие численные характеристики, [1]:

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

   6. геометрические размеры кристалла, необходимые для размещения рисунка схемы,

   7. количество переходов линий связи из слоя в слой.

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

   M »

   где L_u. - условная длина линии с номером і.

   Если для выбранной технологии длина линий связи является критичной, необходимо использовать дополнительный параметр - максимальная условная длина линии связи - L_m. Этот параметр может быть определен следующим образом:

   L =max (2.7)

   /ими, ^v '

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

   N =У> (2.8)

   i-i

   где N_u. - количество переходов линии связи с номером і

   Масштабируемость рисунков схем

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

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

   Варианты построения рисунков схемы

   Между рисунками схемы могут существовать следующие различия. Рисунки вычислительных узлов могут по-разному располагаться в кристалле. Рисунок одного узла, соответствующего RISC процессору в настоящее время занимает в среднем 2-3 слоя металлизации. При доступных в настоящее время 5-6 слоях металлизации возможно 2 способа расположения рисунков вычислительных модулей, [1,2].

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

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

   При использовании первого способа количество необходимых слоев металлизации определяется как количество слоев металлизации, занимаемое одним модулем + 1 (или 2 в зависимости от используемой технологии для размещения линий связи). В настоящее время это составляет 3 - 4 слоя. При втором способе используется как минимум 5-6 слоев.

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

   В настоящее время существует ряд подходов к организации рисунков схем, позволяющих минимизировать длину линий связи и количество переходов линий связи из слоя в слой. Для топологий, графы связей которых можно представить в виде множества подграфов, имеющих структуру, аналогичную исходному графу, но меньшую размерность используется подход кластеризации, [36, 37, 38, 39]. Исходный граф разбивается на подграфы, которые в свою очередь разбиваются на подграфы до тех пор, пока на очередном этапе полученные подграфы не окажутся планарными. Для них генерируются рисунки схемы. Далее эти рисунки объединяются в соответствии с подграфами, находящимися на уровень выше, генерируются более крупные рисунки и так продолжается до тех пор, пока не будет получен рисунок для схемы в целом. Этот подход используется для таких топологий как гиперкуб, топология типа «бабочка», звезда.

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

   Методика определения возможности использования топологии для построения СнК

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

   1. Определение толщины графа связей для рассматриваемых топологий. Позволяет определить возможность использования топологий для выбранной технологии.

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

   3) Определение характеристик скорости передачи сообщения (среднего
   диаметра графа связей) для выбранных в соответствии с пунктом 2 топологий.
   Оценка возможности масштабирования топологии. Выбирается топология с
   наименьшим значением среднего диаметра.

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

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

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

   В соответствии с рассмотренными выше особенностями технологии под толщиной в дальнейшем рассмотрении будем понимать «книжную толщину». Для планарных графов книжная толщина равна 1, [32].

   Двумерная решетка планарна, следовательно имеет толщину, равную 1.

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

   Для тора книжная толщина совпадает с классической толщиной. В соответствии с этим доказательство теоремы совпадает с доказательством соответствующей теоремы для классической толщины, предложенный вариант доказательства приводится в прил. П1. D

   Теорема 2. Трехмерная решетка имеет толщину, не превосходящую 2.

   Доказательство. Пусть решетка состоит из L плоскостей, каждая из которых включает в себя M*N вершин. Если любые два из параметров М, N, L равны 2, решетка планарна. Это доказывается графически на рисунке 2.1.

   Рассмотрим случай, когда М>2, N>2, L>2. Можно представить граф в виде набора из L подграфов - плоскостей, включающих в себя M*N вершин. Пусть

   подграфы пронумерованы от
   1 до L. Докажем, что никакой
   граф, образованный тремя
   подграфами с номерами I и
   1+1 и 1+2 нельзя разместить в
   одной плоскости при М>2 и
   N>2. Эти три подграфа
   образуют граф со

   следующими параметрами:
   MxNxLl, где Ы=3.

   (2.9)

   2.1,2

   2.L.2

   2,2,2

   2.L.2

   1.L.1 Рисунок. 2.1

   1.L.1

   1.L.2

   1.L.2

   Планарность трехмерной решетки при

   M=N=2

   Количество вершин в таком графе Gj: V_x = М N 3
   Количество ребер:
   Q = 3(M-l)-N + 3(N-\)-M + 2N-M = SM-N-3M-3N (2.10)

   Максимальное количество ребер, которое можно разместить в одной плоскости:
   О =6M-N-A (2.11)

   Q_l-Q_m=2M-N-3M-3N + 4 (2.12)

   При М>2 и N>2 разность (2.12) всегда положительна, следовательно, необходимое условие планарности не выполняется и толщина такого графа всегда больше 1.

   Однако, поскольку связывающие ребра имеют только подграфы, номера которых отличаются на единицу, то в одной плоскости может быть размещено множество подграфов, для каждой пары подграфов которого выполняется следующее условие: их номера различаются больше, чем на единицу. Следовательно, минимальное количество таким образом сформированных множеств, на которое можно разбить исходный граф, определяет толщину графа. Это минимальное число равно 2: все подграфы с нечетными номерами можно разместить в одной плоскости, а с четными - в другой. Таким образом, толщина трехмерной решетки при М>2, N>2 и L>2 равна 2. о

   Теорема 3. Толщина гиперкуба не превосходит 2.

   Доказательство. Пусть

   101 гиперкуб включает в себя V=2ⁿ

   вершин. При п=2, (рисунок 2.2, а), и

   при п=3, (рисунок 2.2, б), граф

   планарен.

   Рисунок 2.2 - Планарность гиперкуба при п<4

   _tr*^oc ЕЙСКАЯ

   41 ^го<:1^л-^{л,=ствен}ная

   „библиотека

   Определим книжную толщину графа при п>3. Все грани гиперкуба являются 4-циклами. Количество ребер гиперкуба можно определить по следующей формуле, [31]:

   Q = n-- = n-2ⁿ-^x (2.13)

   =2^-4 = 2^-4 = 4-2^-4 (2.14)

   Из этих выражений видно, что при п>3 необходимое условие планарности не выполняется, следовательно, в этом случае толщина графа будет больше 1. По определению структура связей гиперкуба имеет следующий вид: каждой вершине присваивается двоичный номер; вершины, количество единиц в двоичных номерах которых отличается на 1, связываются ребрами. Таким образом, вершина с четным номером оказывается связанной только с вершинами с нечетными номерами, а вершина с нечетным номером связана только с вершинами с четными номерами. Следовательно, если все множество вершин разбить на подмножество вершин с четными номерами и подмножество вершин с нечетными номерами, то внутри каждого из этих подмножеств связей между вершинами не будет. Таким образом, каждое из этих подмножеств образует планарный подграф исходного графа. Следовательно, толщина гиперкуба при п>3 равна 2.

   Таким образом, толщина гиперкуба при п<4 равна 1, а при п>3 равна 2.

   Существует ряд топологий, подобных гиперкубу, так же находящих широкое применение для построения параллельных вычислительных систем. Они получили название bidelta сети. Все эти сети являются многоуровневыми и могут быть преобразованы друг в друга перестановкой модулей в рамках каждого уровня. Например, к таким топологиям относятся cube connection cycle, топология типа «бабочка», омега-сети, SW banyan сети. Результат, полученный для гиперкуба, может быть обобщен и для них.

   Теорема 4. Толщина bidelta сети не превосходит 2.

   Доказательство. Для всех bidelta сетей характерно следующее. Узлы в них разбиты на последовательность уровней, узлы находящиеся на одном уровне связаны только с узлами на предыдущем и на последующем уровнях. Можно пронумеровать уровни и разделить их на множество уровней с четными и нечетными номерами. Каждое из этих множеств будет образовывать планарный подграф. Таким образом, толщина (книжная) bidelta сети не превосходит 2.

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

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

   Толщина топологии «бабочка» так же не превосходит 2. Действительно все множество вершин графа можно разбить на уровни вершины каждого из которых связаны только с вершинами уровней с номерами на 1 больше и на 1 меньше, чем у рассматриваемого. Таким образом, все множество уровней можно разбить на два множества: множество уровней с четными и нечетными номерами. В соответствии с этим толщина графа не превосходит 2.

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

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

   Исследование характеристик топологий на уровне рисунков схем

   Топологии характеризуются теми же параметрами, что и в параграфе 2.3.1.

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

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

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

   Рассмотрим варианты размещения в кристалле остальных исследуемых топологий для случая, когда их толщина (книжная) равна 2.

   Трехмерная решетка. Рассмотрим варианты расположения на кристалле трехмерной решетки MxNxL. Эту структуру можно рассмотреть как совокупность двумерных матриц размера MxN. В дальнейшем будем называть их уровнями решетки. Если на кристалле для размещения рисунков узлов отводится одна группа слоев металлизации, уровни решетки могут быть размещены в нем так, как показано на рисунке 2.3 а. Обозначим такой способ формирования рисунка - способ 1. Вывод формул для определения характеристик приведен в приложении П2

   Рассмотрим, как повлияет на характеристики рисунка применение метода чередования узлов- способ 2. Элементы уровней решетки 1 и 2 (рисунок 2.3,6 1 -окрашены белым, 2 -серым) можно чередовать, например, по горизонтали. Это иллюстрируется рисунком 2.4. Если рисунок одного узла занимает три слоя металлизации, то один из них может использоваться для прокладки вертикальных

   _u—J

   _{GO і}

   _\чА

   а)

   б)

   _ft-

   Рисунок 2.3 - Варианты расположения модулей

   трехмерной решетки а) в одной группе слоев

   металлизации, б) в двух группах слоев

   _{ІгпПгтГи}

   Рисунок 2.4 - Размещение узлов решетки с чепе ттппяттием

   линий связи между узлами, второй - для прокладки горизонтальных линий связи между узлами, принадлежащими первому уровню, и третий - для прокладки линий связи, принадлежащих второму уровню. Такой рисунок схемы может быть использован, если в соответствии с технологией не может быть выделено дополнительных слоев металлизации для прокладки линий связи. (Книжная толщина графа связей равна 2) Если L>2, то рисунки пар уровней могут располагаться относительно друг друга так, как это было рассмотрено на рисунке 2.3,6. Модули уровней решетки, окрашенных серым, чередуются с модулями неокрашенных уровней решетки. Вывод формул для оценки характеристик такого рисунка приведен в приложении П2. В соответствии с результатами (приложение П2) при N>l/2((3-M+2)/M) использование этого способа позволяет сократить суммарную длину условных линий связи, если для прокладки линий связи могут быть использованы активные слои, 2 способ позволяет сократить количество переходов линий связи из слоя в слой в два раза по сравнению с первым способом

   Тор. Рассмотрим варианты расположения на кристалле тора на базе двумерной решетки MxN. Если для расположения рисунков узлов отводится одна группа слоев металлизации, они могут быть расположены в ней в форме двумерной матрицы -обозначим это способ 1. Это иллюстрируется рисунком 2.5. Вывод формул для расчета характеристик рисунка представлен в прил. П2.

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

   Для устранения этого можно воспользоваться методом чередования. Обозначим этот способ формирования рисунка схемы - способ 2. Матрицу MxN можно разделить на 4 примерно равные части, так как это показано на рисунке 2.5 пунктиром.

   Рисунок 2.5 - Вариант расположения рисунка

   схемы, соответствующей тору, иллюстрация его

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

   

   Устройства вычислительной техники для цифровой обработки сигналов, аппроксимированных цепями Маркова, в системе остаточных классовИванова, Надежда Николаевна

   Контроллерные сложно-функциональные блоки и их применение в составе СБИС класса "система-на-кристалле"Родионов, Андрей Андреевич

   

   Модели, методы и алгоритмы кодирования изображений в устройствах систем на кристаллеФахми, Шакиб Субхиевич

   

   Исследование методов и разработка устройств обработки информации в системах на кристаллеЗинкевич Алексей Владимирович

   

   Повышение помехоустойчивости аналого-цифровых систем на кристалле средствами адаптивной коррекции сложных функциональных блоковСибагатуллин, Артур Гиниятович

   

   Средства и методы повышения производительности и снижения энергопотребления систем на кристалле, реализуемых на базе программируемых логических интегральных схемШалтырев Владимир Алексеевич

   

   Методы и средства проектирования аналого-цифровых базовых матричных кристаллов и микроэлектронных устройств на их основе Полевиков Валерий Викторович

   Проектирование устройства микропрограммного управления на основе базового матричного кристаллаКамалов, Абиджан Алаханович

   Теоретический анализ и экспериментальное исследование искажений импульсных сигналов в многопроводных межсоединениях элементов и устройств вычислительной техникиЗаболоцкий Александр Михайлович

   

   Система контроля и анализа технических свойств интегральных элементов и устройств вычислительной техники по многоуровневой модели информативных параметровНомоконова, Наталья Николаевна