авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ Сборник трудов ...»

-- [ Страница 2 ] --

Взаимодействие модулей асинхронных схем Несмотря на отсутствие общей синхронизации, в асинхронных схемах должна быть обеспечена локальная синхронизация выполнения операций и передачи данных между непо средственно связанными модулями. Данная задача решается посредством процедуры асин Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ хронных коммуникаций. Наиболее распространенный вариант процедуры — обмен с под тверждениями (квитированием), описанный в [2].

Процедура асинхронных коммуникаций — неотъемлемая составляющая диаграмм вза имодействующих модулей [2, 3], которые являются основным способом высокоуровневого описания асинхронных схем. Эта модель позволяет наглядно представить асинхронную схе му, разбивая ее на простые модули (регистры, мультиплексоры, арбитры и т.д.), между кото рыми передаются потоки данных, и тем самым справиться со сложностью восприятия децен трализованности и параллелизма. Сами модули описываются на уровне поведения, без дета лизации внутренней организации, а основное внимание уделяется их взаимодействию.

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

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

Диаграммы взаимодействующих модулей используются для структурного описания асинхронных схем, на уровне модулей и на RTL-уровне, при этом RTL-описания асинхрон ных схем по форме могут отличаться от RTL-описаний синхронных схем. Формальную мо дель взаимодействующих модулей разработал C.H. van Berkel [3], а возможность автоматиче ского синтеза подобных описаний в схемы на КМОП-логике математически доказал A. Martin в [4].

Взаимодействующие процессы Формальный язык взаимодействующих последовательных процессов (communicating sequential processes) был разработан Чарльзом Хоаром. Этот язык ориентирован на описание параллелизма компонентов системы, допускает операции присваивания, последовательной и параллельной композиции, выбора и блокирующего ввода—вывода через порты. Реализации этого языка, ориентированные на синтез асинхронных схем, включают в себя CHP, Tangram и Balsa. Описания могут быть синтезированы в нечувствительную к задержкам на вентилях схему из взаимодействующих модулей, при этом каждому оператору сопоставляется один модуль (цикла, присваивания, модули последовательной и параллельной композиции, модуль условного исполнения и т.д.). Такой подход носит название компиляции, управляемой син таксисом [2]. Альтернативный подход разработал A. Martin [4], используя промежуточную нотацию правил вывода, он описал процедуру синтеза описаний на CHP в КМОП-схемы.

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

Правила вывода Правило вывода представляет собой пару «условие—присваивание», где условие — буле ва функция от сигналов схемы, а присваивание определяет положительный или отрицательный перепад одного из сигналов, который инициируется, когда условие истинно. При этом подразу мевается, что перепад осуществляется в течение некоторого времени, что соответствует поведе нию реальных логических и запоминающих элементов. Два дополняющих правила вывода (определяющих условия фронта и спада перепада одного и того же сигнала) задают поведение асинхронного вентиля (с памятью или без). Например, логический элемент «И» задают правила i1 i2 o ;

i1 i2 o, элемент «ИЛИ» — правила i1 i2 o ;

i1 i2 o, а C-элемент Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Маллера, изменяющий значения на своем выходе, только когда значения на входах совпада ют – i1 i2 o ;

i1 i2 o.

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

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

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

а) б) Рис. 1. Два варианта реализации булевой функции На рис. 1, а показана оптимизированная реализация функции f ( x z ) ( y z ). Если входные сигналы схемы находятся в состоянии x = 1, y = 0, z = 1 (на выходе схемы будет Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ единица) и задержка у нижнего вентиля меньше, чем у верхнего, то после отрицательного перепада на z выход схемы на короткое время перейдет в нуль. В асинхронных схемах это недопустимо. Поэтому используется неполная оптимизация (см. рис. 1, б). Подробно этапы синтеза конечных автоматов рассмотрены в [1].

Графы изменения сигналов Граф изменения сигналов (Signal Transition Graph, STG) — модель схемы, описывающая ее поведение в виде взаимосвязей между событиями изменения сигналов. STG используются с той же целью, что и асинхронные автоматы: для создания асинхронных вентильных схем без гонок, но для устройств, работающих в режиме ввода—вывода (схем Маллера), где вход ные сигналы должны оставаться стабильными до тех пор, пока не изменится значение хотя бы одного выходного. Такое ограничение гораздо лучше подходит для построения схем с квитированием.

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

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

Оценка производительности и графы зависимостей Нечувствительные к задержкам схемы проектируются так, чтобы функционировать корректно в широком диапазоне изменений задержек на вентилях. На практике нас интересу ет производительность схемы как относительно других вариантов реализации той же функ циональности, так и в абсолютных временных величинах. Оценка производительности слож ных устройств должна начинаться с уровня архитектуры. Но задача решается и на более низ ком уровне: она разбивается на задачи оценки производительности более простых структур, таких как асинхронный конвейер, представляющий собой последовательность из асинхрон ных защелок и функциональных блоков, аналогичных комбинационным схемам, или коль цо — конвейер, в котором последняя ступень соединена с первой. В своей диссертации [6] Ted Williams предложил метод оценки таких структур на основе графов зависимостей. Такой граф аналогичен STG, но в нем полностью отсутствуют неопределенности и каждый переход помечен в дополнение к изменению сигнала задержкой перехода (временем от выполнения условия перехода до реализации результата перехода). Графы позволяют определить локаль ные параметры конвейеров и колец, такие как задержки на этапах и локальный период — временной интервал между приемом последовательных порций данных.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ На рис. 2 показан участок асинхронного конвейера с соответствующим ему графом за висимостей. Для определения локального периода в этом графе необходимо найти длинней ший (в отношении суммы задержек на всех переходах) простой цикл.

а) б) Рис. 2. Участок асинхронного конвейера (а) и граф зависимостей (б) Так, в данном случае локальный период i-й ступени конвейера находится как Pi td (0 1) tc td (0 1) tc ti tc ti tc 20 нс.

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

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

В России проблемой асинхронной схемотехники и асинхронной коммуникации з а нимался В.И. Варшавский. Он разработал множество схемотехнических решений и про токолов обмена, внес большой вклад в теорию коллективного поведения автоматов и о с новал научную школу асинхроники. В настоящее время его ученики, такие как А. Таубин, М. Карповский, А. Яковлев, А. Кондратьев и М. Кишиневский работают за рубежом. Об исследованиях и публикациях по данной тематике в современной России, к сожалению, практически неизвестно.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ ЛИТЕРАТУРА 1. Mаyers С. Asynchronous circuit design. NY: John Wiley & Sons, 2001. 404 с.

2. Sparso J. Principles of asynchronous circuit design — a systems perspective. Dordrecht:

Kluwer Academic Publishers, 2001. 337 р.

3. Van Berkel C.H. Handshake circuits: an intermediary between communicating processes and VLSI. Eindhoven: Technische universiteit Eindhoven, 1992. 253 р.

4. Martin A. Programming in VLSI: from communicating processes to delay-insensitive circuits.

Pasadena: California Institute of technology, 1989. 66 р.

5. Martin A. The limitations of delay-insensitivity in asynchronous circuits. Pasadena: California Institute of technology, 1990. 16 р.

6. Williams T. Self-timed rings and their application to division. Palo Alto: Stanford University, 1991. 144 р.

УДК 004.414. ПОДХОД К СОЗДАНИЮ МОДЕЛЕЙ КОММУТАТОРОВ КОМПЬЮТЕРНЫХ СЕТЕЙ Л. А. Муравьева-Витковская, Д. О. Сафин Для коммутаторов компьютерных сетей, реализующих механизмы клас сификации и управления трафиком, предлагается подход к созданию моделей, позволяющих оценить их структурно-функциональные пара метры при заданном качестве обслуживания. Получены аналитические зависимости для определения емкости буферной памяти коммутатора при приоритетном управлении трафиком.

Ключевые слова: компьютерная сеть, коммутатор, качество обслуживания, структурно-функциональные параметры, трафик, пакет, кадр, приоритетное управление, модель.

Введение Специфичность компьютерных сетей обусловлена следующими факторами: многообра зием сетевых технологий и архитектур;

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

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

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

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

В настоящее время из-за интенсивного роста числа пользователей и различных приложений все большее распространение получают мультисервисные сети, в которых существуют десятки разновидностей трафика [1], вызванных внедрением новых информационных технологий, Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ использованием различных приложений: Интернет, IP-телефонии (VoIP), видеоконференц связи, планирования ресурсов предприятия (ERP), управления взаимоотношениями с заказ чиками (CRM) и др. Таким образом, одной из характерных особенностей современных телекоммуникационных сетей (ТКС) является неоднородность трафика [1, 2].

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

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

Алгоритмы обработки очередей составляют одну из основ механизмов обеспечения га рантированного качества обслуживания (Quality of Service — QoS) в сетевых элементах.

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

Для предотвращения потерь кадров при кратковременном многократном превышении среднего значения интенсивности трафика (например, для сети LAN часто встречаются зна чения коэффициента пульсации трафика в диапазоне 50—100 [3]) единственным средством служит буфер соответствующего объема.

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

Модель коммутатора должна адекватно воспроизводить задержки коммутации, потери пакетов, управление интерфейсами, приоритеты трафика и другие эффекты, связанные с пе редачей информации, присущие моделируемому коммутатору [3].

Процесс создания модели коммутатора состоит из четырех этапов:

— построение тестовой сети;

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

— определение значений параметров разработанного алгоритма модели;

— проверка адекватности и уточнение модели.

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

Число компьютеров должно соответствовать числу портов исследуемого коммутатора.

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

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

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

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

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

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

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

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

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

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

отслеживание и управление состоянием сетевых интерфейсов в процессе испы тания (контроль механизмов управления потоком);

синхронизация времени на ЭВМ, участ вующих в испытании;

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

Рассмотрим приемы определения параметров на примере модели коммутатора, реали зующего приоритетное управление трафиком. В качестве модели коммутатора рассматрива ется одноканальная система массового обслуживания (СМО) с накопителем неограниченной Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ емкости, в которую поступают K типов заявок, образующих простейшие потоки с интенсив ностью, …,.

Заявка в СМО соответствует кадру в коммутаторе;

интенсивность потока заявок — ин тенсивности потока кадров;

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

дисциплина обслуживания заявок – схеме приоритетной обработки кадров в коммутаторе.

Будем полагать, что длительность обслуживания заявки типа k распределена по произ вольному закону с плотностью вероятности b(). Заявки выбираются на обслуживание в соот ветствии с дисциплиной обслуживания со смешанными приоритетами (ДО СП), задаваемой с помощью матрицы приоритетов (МП) вида Q=[qij] (i, j = 1,…, K), где qij=0 означает, что заявка типа i не имеет приоритета по отношению к заявке типа j (дисциплина обслуживания без прио ритета, БП), qij=1 — относительный приоритет, ОП, и qij=2 — абсолютный приоритет, АП [2].

Для описанной модели в [2] получены преобразования Лапласа плотностей распределе ний временных характеристик функционирования системы (времени ожидания и пребывания заявок в СМО) и соответствующие начальные моменты. Очевидно, что число заявок, нахо дящихся в СМО, прямо пропорционально зависит от времени их пребывания. В [5] определе на эта связь и методом введения дополнительного события получено выражение для произ водящей функции числа заявок типа k = 1,…, K, одновременно находящихся в СМО M k (Z ) U k (k k Z ).

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

Пусть pk(l) — вероятность того, что длина кадра типа k равна l байтам. Положим, что l k l r p k (l ) (r 1, 2,...);

L* ( Z ) Z p k (l ) (0 Z 1;

k 1,..., K ).

(r ) l k l 0 l Определим статистику числа единиц длины кадра типа k в буферной памяти. Если в бу ферной памяти коммутатора находится Mk кадров типа k, то число единиц длины кадра типа k равно Mk Gk Lki, i тогда производящая функция числа единиц длины кадра типа k равна Gk (Z ) M k ( Lk (Z )), * * а первый и второй начальный моменты числа единиц длины кадра типа k равны соответ ственно:

G k mk l k (1) (1) (1) (2) 2 G k m k l k m k (l (2) l k ).

(2) (2) (1) (1) (1) k Используя выражение (2), можно определить средний объем внутренней буферной памяти коммутатора, необходимый для хранения кадров типа k. Для более точной оценки размера бу ферной памяти определим объем буферной памяти, необходимый для хранения кадров типа k при заданном значении вероятности переполнения памяти *. Определим вероятность q k (g ) k того, что в буфере находится g единиц длины кадров типа k следующим образом:

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ g* 1 d G k ( z) q k(g).

g g!

dz z Тогда вероятность того, что число единиц длины кадров типа k в буферной памяти Gk * превышает некоторое число Gk, имеет вид:

qk (g) * P(Gk Gk ) (k 1,, K ).

g Gk * Объем внутренней буферной памяти коммутатора определяется путем решения нера * венства P(Gk Gk ) * относительно Gk.

* k Так как для определения вероятностей необходимо производить многократное диффе ренцирование производящей функции, что является трудоемкой задачей, при оценочных рас четах объема буферной памяти можно воспользоваться неравенством Чебышева.

Проведенные исследования показали, что объем буферной памяти существенно зависит от типа распределения длины кадра. Так, например, при переходе от детерминированного распределения к экспоненциальному объем буфера кадров увеличивается в 1,5—2 раза, а при переходе от детерминированного к гиперэкспоненциальному распределению — в 3—5 раз.

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

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

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

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

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

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Заключение На основе предложенной модели коммутатора можно решать задачи, связанные с опре делением структурных и функциональных параметров, обеспечивающих заданное качество функционирования проектируемой компьютерной сети при различной нагрузке. Сочетание использования аналитических и имитационных моделей на различных этапах проектирова ния позволяет повысить достоверность полученных результатов.

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

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

ЛИТЕРАТУРА 1. Гольдштейн Б.С., Пинчук А.В., Суховицкий А.Л. IP-телефония. М.: Радио и связь, 2001.

2. Якубович Д. Оптимизация сетевого трафика // Сети и системы связи. 2001. № 10.

С. 92—97.

3. Вишневский В.М. Теоретические основы проектирования компьютерных сетей.

Техносфера, 2003.

4. Алиев Т.И. Характеристики дисциплины обслуживания заявок со смешанными приоритетами // Изв. вузов СССР. Приборостроение. 1981. № 11. С. 36—40.

5. Муравьева-Витковская Л.А. Определение структурно-функциональных параметров коммутатора телекоммуникационной сети при приоритетной обработке кадров // Современные технологии. СПб: СПбГУ ИТМО, 2003. С. 27—33.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ УДК 004. МЕТОДЫ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ RISC-ПРОЦЕССОРОВ М. А. Басов Представлен последовательный обзор существующих на сегодня базо вых методов, позволяющих повысить производительность процессоров класса RISC. Предлагается методика на базе модели абстрактной про граммы для тестирования некоторых методов и получения количествен ных характеристик.

Ключевые слова: производительность, RISC-процессор, абстрактная программа, модельный эксперимент.

Введение Рынок сегодняшних микропроцессоров и микроконтроллеров обильно представлен вы числителями, принадлежащими классу RISC, из наиболее известных можно выделить MIPS32/64, AVR8/16/32, PIC8/16/32, ARM32. Кроме того, развитие получает направление проектирования VLIW-компьютеров, родственных по идеологии RISC-компьютерам [1, 2].

Микроархитектура некоторых представителей компьютеров CISC-класса, например линейки процессоров x86, содержат внутреннее RISC-ядро [3].

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

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

Анализ проблем и обзор методов В первую очередь необходимо определить единицы измерения производительности процессора. Зачастую применяется единица MIPS (число миллионов инструкций, выполняе мых в секунду), где в качестве временного промежутка принимается секунда. Однако едини цей измерения событий в синхронных схемах является такт кварцевого генератора. Таким образом, поскольку частота работы каждого конкретного процессора может разниться — для более точного представления целесообразно использовать единицу, опирающуюся на так ты — IPC (количество инструкций, выполненных за такт) или обратную ей величину CPI (ко личество тактов на инструкцию). В дальнейшем будем ориентироваться на единицу CPI.

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

— «идеальное» значение CPI метода, — потери из-за технических конфликтов (конфликты по данным, конфликты по управлению и структурные конфликты).

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ «Идеальное» значение CPI определяется используемым методом, способствующим уве личению количества исполняемых команд за единицу времени. Можно выделить как мини мум два таких метода — это конвейеризация и увеличение количества функциональных бло ков. Конвейеризация позволяет достичь «идеального» значения CPI, равного единице, за счет разбиения вычислительного процесса на несколько независимых шагов, называемых ступе нями конвейера. Увеличение количества функциональных блоков в совокупности с конвейе ризацией позволяет еще больше увеличивать количество одновременно исполняемых ин струкций, соответственно CPI может принимать значения, меньшие единицы.

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

Конфликты по данным обусловлены последовательной природой программ. Здесь име ются в виду программы с последовательной организацией команд, где подразумевается и их последовательное исполнение. Так, результат вычисления одной команды может зависеть от результата предыдущей, что показано на примере 5-ступенчатого конвейера на рис. 1. Видно, что команда вычитания (sub) требует результат предыдущей команды загрузки из памяти (load). Самый простой метод разрешения данного конфликта заключается в останове вычис лительного конвейера при обнаружении зависимости по данным до полного его устранения.

Так, если запись результатов исполнения происходит на ступени WB, а считывание исходных данных новой команды на ступени ID — потеря в производительности при этом составляет холостых такта (CPI = 3). Как правило, нет необходимости полностью останавливать конвейер при зависимостях такого рода, достаточно проанализировать — на какой ступени результат требуется новой команде и на какой ступени получается результат предыдущей команды.

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

Рис. 1. Конфликт в вычислительном конвейере Наличие ветвлений в программе также способно уменьшить загрузку конвейера (кон фликт по управлению), ведь принятие решения о переходе по условию требует прохождения командой перехода соответствующей вычислительной ступени. Для уменьшения простоя возможно использовать метод, позволяющий предсказать адрес перехода и выполнять эти команды по предположению (спекулятивное исполнение). Общей отрицательной чертой всех спекулятивных методов является факт, что правильно предсказать переход в 100 % случаев не представляется возможным, следовательно, накладные расходы заключаются в требовании восстановления состояния процессора в предшествующее переходу при ошибке. Одним из способов, не имеющих подобного недостатка, является статическая гипотеза задержанного Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ перехода. При этом команда в так называемом слоте задержки оказывается неотделимой от команды условного перехода и выполняется всегда — заполнение слота определяется статически, на этапе компиляции. Такой подход имеет и некоторые недостатки, такие как проблема реализации механизма точных исключений (вытекает из неотделимости слота задержки от команды перехода), невысокий процент полезного заполнения, а также ни з кая эффективность применения в микроархитектурах с длинным конвейером (более ступеней). В качестве альтернативы — существуют и статические спекулятивные методы, например, априорное высказывание «все переходы состоятся», но как правило, при ис пользовании спекулятивной схемы опираются на так называемые динамические методы, основанные на наборе статистики во время исполнения. Так, наиболее известными и в то же время эффективными являются методы на базе одно- или двубитового счетчика. Каж дый отсчет является состоянием, которым и определяется предсказание. Несмотря на свою привлекательность однобитовая схема не учитывает некоторых типичных для лю бой программы конструкций, как ветвление в цикле или цикл в цикле, снижая эффектив ность предсказаний. Количественные характеристики данных схем приведены ниже. Для микроархитектурных решений, содержащих несколько функциональных блоков, эффек тивным может быть решение, позволяющее отказаться от обычных процедур ветвления (предикатное исполнение). За счет большого количества исполнительных блоков стан о вится возможным выполнять несколько ветвей алгоритма одновременно с дальнейшей записью результатов только истинной ветви. Таким образом, не снижается уровень па раллелизма на уровне инструкций и не возникает остановов, связанных с возможными ошибками предсказания.

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

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

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Модельный эксперимент Для оценки тех или иных методов и решений требуются их количественные характери стики, получаемые, как правило, с использованием модельного эксперимента. Обычно это задача решается в рамках конкретной компьютерной архитектуры, т.е. в качестве централь ной выступает потактовая модель вычислителя, на которой можно запустить тестовую про грамму. Создание такой модели требует достаточно больших усилий, к тому же иногда тре буется оценить лишь общие тенденции влияния того или иного метода безотносительно к конкретной архитектуре. Так, в качестве альтернативы можно предложить модель абстракт ной программы, не привязанной к конкретной вычислительной архитектуре.

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

В качестве шаблонов, присущих реальным программам, были выделены следующие:

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

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

При моделировании использовались следующие основные параметры: длина про граммы — 100 000 инструкций, длина линейного участка — 10 инструкций (примерно исполняемых команд на одну инструкцию перехода), общее количество исполняемых и н струкций для каждого случая — 1 000 000. На рис. 2—4 представлены результаты экспе римента.

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Процент кэш-промахов, % Рис. 2. Зависимость интенсивности кэш-промахов от размеров блока для кэшей разных размеров Процент кэш-промахов, % Рис. 3. Зависимость интенсивности кэш-промахов от степени ассоциативности для кэшей разных размеров Количество состоявшихся переходов, % Рис. 4. Зависимость интенсивности ошибок предсказания от количества состоявшихся при моделировании переходов для разных схем предсказания Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Заключение Рассматриваемая тематика весьма обширна, но, к сожалению, формат статьи не позво ляет раскрыть всех проблем, влияющих на производительность вычислителей, поэтому был проведен краткий, но последовательный анализ ключевых проблем, присущих всем совре менным вычислителям, а также обзор методов их решения. Количественные результаты, по лученные с помощью предложенной методики абстрактной программы, в целом показывают ее адекватность и пригодность для дальнейших исследований. В качестве направлений даль нейших исследований можно рассматривать более полное изучение проблем планирования ресурсов в суперскалярных и VLIW-архитектурах и совершенствование существующих мето дов программно-аппаратной оптимизации.

ЛИТЕРАТУРА 6. Ким А.К., Волконский В.Ю., Груздов Ф.А., Михайлов М.С., Парахин Ю.Н., Сахин Ю.Х., Семенихин С.В., Слесарев М.В., Фельдман В.М. Микропроцессороные вычислительные комплексы с архитектурой «Эльбрус» и их программное обеспечение [Электронный ресурс]: http://www.mcst.ru/doc/volk_090610.doc.

7. Klaiber A. The Technology Behind Crusoe® Processors [Электронный ресурс]:

http://www.enlight.ru/docs/cpu/crusoe/crusoetechwp.pdf.

8. Patterson D. A., Hennessy J. L. Computer Organization and Design. The software/hardware interface. San Francisco: Morgan Kaufmann Publishers, 2007.

9. Patterson D. A., Hennessy J. L. Computer Architecture: A Quantitative Approach. San Francisco: Morgan Kaufmann Publishers, 2007.

УДК 004. КЛОНИРОВАНИЕ КОМПЬЮТЕРОВ В ЛОКАЛЬНОЙ СЕТИ С ИСПОЛЬЗОВАНИЕМ СВОБОДНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ Н. В. Касаткин, А. О. Сергеев Администрирование большого количества современных компьютеров невозможно без использования метода клонирования. В государствен ных учреждениях применение коммерческих систем клонирования нецелесообразно и функционально неоправданно. Предложен и описан метод улучшения существующей открытой технологии клонирования, позволяющий интегрировать систему в локальную сеть без внесения изменений в существующие службы.

Ключевые слова: локальные сети, обработка данных, передача данных, сетевые технологии, клонирова ние, свободное программное обеспечение.

Введение Администрирование большого числа современных компьютеров, объединенных в ло кальную сеть, сопряжено с большими трудозатратами со стороны системных администрато ров. Помимо первоначальной установки операционной системы необходимо регулярно об новлять набор программного обеспечения на всех компьютерах или их части. Производители операционных систем (ОС) и программного обеспечения (ПО) предлагают разнообразные Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ методы и программы по автоматизации установки и обновления своих продуктов. Но часто эти подходы оказываются неэффективными, особенно когда на компьютерах установлено больше одной ОС или используется широкий ассортимент разнообразного прикладного ПО.

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

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

В государственных учреждениях, а особенно в образовательных, целесообразно исполь зование свободного программного обеспечения (СПО) для выполнения тех же функций. Та кие преимущества СПО, как наличие исходных текстов и сообщество разработчиков, позво ляют использовать данный вид ПО в образовательном процессе, например в работах студен тов на практических и лабораторных занятиях. В общую стоимость владения такой системой входят только затраты на работу системного администратора. Благодаря свободному типу лицензии (GNU GPL) [2] и наличию исходных текстов можно улучшать программу и моди фицировать ее под конкретные требования [3].

Рассмотрим решение задачи интеграции системы клонирования в локальную сеть без внесения изменений в существующие службы на примере внедрения подобной системы в ло кальную сеть СПбГУ ИТМО.

Интеграция системы клонирования в локальную сеть Для решения данной задачи были выбраны сервер сетевой загрузки DRBL и комплекс программ клонирования Clonezilla от Free Software Labs, NCHC (лаборатории свободных про грамм тайваньского национального центра высокопроизводительных вычислений) [4].

Выбранную систему клонирования необходимо было интегрировать в локальную сеть факультета ИТиП ИТМО. Развертывание системы клонирования затрагивало часть сети, со стоящую из центрального сервера (сервер R), двух вспомогательных серверов (серверы D и V) и 10 компьютерных классов, выделенных в подсети класса C. На серверах установлены опера ционные системы Linux Centos и Linux Ubuntu Server, на рядовых компьютерах в классах установлена операционная система Windows XP и набор прикладного ПО. Общее число кло нируемых компьютеров составляло 181.


Сервер R предоставляет несколько служб, в частности DHCP (Dynamic Host Configuration Protocol) [5], которая задействована в системе клонирования. Компьютер V представляет со бой хранилище резервных копий и сервер виртуальных машин, одна из которых — эталон ный компьютер для клонирования, на котором происходит обновление ПО. Сервер D являет ся непосредственно сервером клонирования.

Выбранная система клонирования опирается на протокол сетевой загрузки PXE (Preboot eXecution Environment, Intel) [6], используемый практически в любой компьютерной сети.

Протокол PXE является надстройкой над протоколом DHCP и использует те же порты и ме тоды передачи информации. Современные DHCP-серверы могут функционировать и как PXE-серверы при соответствующей настройке. Сервер сетевой загрузки DRBL может высту пать как сервер PXE и соответственно DHCP (рис. 1).

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Параметры обычно включают в себя адрес сервера загрузки и имя файла загрузки. Когда кли ент их получает, он переходит к стадии загрузки указанного файла в память и передает ему управление (шаг 3 на рис. 1).

Рис. 1. Сетевая загрузка с использованием PXE-сервера В локальной сети факультета ИТиП уже существовал функционирующий DHCP-сервер, конфигурацию которого изменять было нельзя, было решено отказаться от идущего в ком плекте с DRBL PXE-сервера и использовать proxy DHCP-службу (PXE redirection service) [6].

Сетевая загрузка с использованием proxy DHCP-сервера происходит следующим обра зом: в сеть с существующим сервером DHCP добавляется proxy DHCP-сервер, принимающий дейтаграммы по протоколу UDP на тот же порт, что и DHCP-сервер (рис. 2).

Рис. 2. Сетевая загрузка с использованием proxy DHCP-сервера Оба сервера, получив расширенный запрос от PXE-клиента (шаг 1 на рис. 2), отвечают ему, но только своим набором параметров. DHCP-сервер отвечает набором DHCP-параметров Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ (шаг 2а на рис. 2), а proxy DHCP-сервер — набором PXE-параметров (шаг 2б на рис. 2). Кли енту для загрузки необходимы оба ответа, так как в них содержится вся необходимая инфор мация. После их получения клиент переходит к стадии загрузки указанного файла в память и передает ему управление (шаг 3 на рис. 2).

В качестве proxy DHCP-сервера был выбран сервер Dnsmasq [7], являющийся свобод ным ПО и выполняющий помимо прочего функцию сервера TFTP (Trivial File Transfer Protocol) [8]. В итоге функциональная часть системы клонирования осталась неизменной, а изменился только процесс сетевой загрузки с сервера DRBL (сервер D).

После установки необходимого ПО на эталонный компьютер производится его подго товка к снятию образа, в случае с операционной системой Windows — это сброс идентифика торов безопасности, добавление драйверов, программирование процедур на выполнение по сле клонирования. Затем виртуальная машина эталонного компьютера выключается и загру жается по сети с использованием протокола PXE. Посылается широковещательный PXE запрос, на который DHCP-сервер R отвечает набором DHCP-параметров (IP-адрес компьюте ра) в специальным образом настроенную ОС Linux [9]. Запускается процесс создания точной копии жесткого диска (так называемого эталонного «образа») — копирование, сжатие, пере дача по сети и сохранение на сервере D (рис. 3).

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

Заключение Интегрирование системы клонирования в локальную сеть СПбГУ ИТМО без внесения изменений в существующие службы производилось путем подбора и замены составных частей свободной системы с открытым исходным кодом DRBL и Clonezilla, была удалена функция PXE сервера, вместо которой добавлена функция proxy DHCP-сервера. При внедрении системы клони рования были учтены следующие особенности архитектуры локальной сети СПбГУ ИТМО:

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ ЛИТЕРАТУРА 1. Медведев Ю.Г. Технологии клонирования компьютеров. СПб: BHV-Санкт-Петербург, 2006. 304 с.

2. Лицензия GPL [Электронный ресурс]: http://www.gnu.org/licenses/gpl.html.

3. Немет Э., Снайдер Г., Хейн Т. Руководство администратора Linux. СПб: Вильямс, 2007.

1072 с.

4. Сайт разработчиков DRBL [Электронный ресурс]: http://drbl.sourceforge.net/.

5. Техническая спецификация протокола DHCP [Электронный ресурс]: http://www.ietf.org /rfc/rfc2131.txt.

6. Техническая спецификация протокола [Электронный ресурс]:

PXE http://download.intel.com/design/archives/wfm/downloads/pxespec.pdf.

7. Dnsmasq Сервер Dnsmasq [Электронный ресурс]: http://www.thekelleys.org.uk/ dnsmasq/doc.html.

8. Техническая спецификация протокола TFTP [Электронный ресурс]: http://www.ietf.org/ rfc/rfc2347.txt.

9. Боттс Т., Доусон Т., Перди Г.Н. Linux руководство администратора сети. М.: Кудиц Пресс, 2006. 368 с.

УДК 519. СОВРЕМЕННЫЕ СИСТЕМЫ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ Г. К. Асафьев Проведен сравнительный анализ следующих средств имитационного моделирования: AnyLogic, Arena, Ptolemy II и GPSS World. Системы сравнивались по следующим критериям: гибкость при моделировании, простота в применении, скорость работы.

Ключевые слова: имитационное моделирование, AnyLogic, Arena, Ptolemy II, GPSS World.

Введение Имитационное моделирование (ИМ) — один из самых распространенных методов ис следования операций и теории управления. Об этом свидетельствует включение дисциплин по ИМ в программы высших учебных заведений, а также проведение многочисленных кон ференций по ИМ: Winter Simulation Conference в США, ИММОД в России и др.

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

— проектирование и анализ производственных систем;

— оценка различных систем вооружений;

— определение требований к оборудованию и протоколам сетей связи;

— модернизация различных процессов в деловой сфере;

— определение политики в системах управлениями запасами;

— анализ финансовых и экономических систем.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ В настоящее время различают следующие виды ИМ: агентное моделирование, систем ная динамика и дискретно-событийное моделирование [2]. Наиболее эффективным при ис следовании вычислительных систем и сетей передачи данных является дискретно событийное моделирование [3].

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

Возможности пакетов имитационного моделирования При выборе средств ИМ следует учитывать все возможности [3], предоставляемые ими.

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

— Возможность определять и изменять атрибуты объектов и глобальных переменных, а также применять как те, так и другие в логике модели.

— Возможность использовать математические выражения и функции (логарифмы, возведение в степень).

— Возможность создавать новые моделирующие конструкции, собственные библиотеки моделирующих конструкций.

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

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

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

— Хорошие средства отладки.

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


Ниже рассматриваются популярные системы ИМ: Arena компании Rockwell Automation, AnyLogic компании XJ Technologies, разработка института Беркли — Ptolemy II и GPSS World фирмы Minuteman Software.

Пакет имитационного моделирования Rockwell Arena Система Arena компании Rockwell Automation является лидером на рынке программ ИМ. Этот продукт используют крупнейшие компании, включая General Motors, UPS, IBM, Nike, Xerox, Lufthansa, Ford Motor Company и др. Основные области применения данного па кета: производство (моделирование конвейерного производства, определение узких мест…), логистика и складское хозяйство (оптимизация использования складских площадей), воору жение и безопасность, медицина (моделирование потока пациентов, распределение персона ла…) и др.

В Arena применяются процессор и язык ИМ SIMAN. Пользователю предоставляется удобный графический интерфейс с набором шаблонов моделирующих конструкций. Для со здания модели конструкции сначала «перетаскивают» в окно модели с помощью мыши, а затем соединяют, чтобы обозначить движение заявок в моделируемой системе. Затем моде лирующие конструкции детализируются с помощью диалоговых окон или встроенных таблиц. Arena поддерживает иерархическое моделирование.

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Каждая заявка в Arena обладает набором стандартных атрибутов, но помимо стандарт ных заявкам можно присвоить собственные атрибуты с помощью конструкции Assign. После присвоения атрибута его можно использовать в логике модели для принятия решения (например, в конструкции ветвления Decide) или присваивать ему новое значение (например, с помощью Assign).

Arena поддерживает язык Visual Basic for Applications (VBA) компании Microsoft. С его помощью можно связать модель с продуктами фирмы Microsoft (например, экспорт результа тов в Excel).

Arena обеспечивает вывод на экран двумерной и трехмерной (Arena 3DPlayer) анимации процесса моделирования. Для представления результатов доступны различные гистограммы и графики.

Число потоков случайных чисел в пакете Arena не ограничено. Более того, пользователь имеет доступ к 12 стандартным теоретическим распределениям вероятностей, а также к эм пирическим распределениям.

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

Rockwell Arena работает только под операционными системами семейства Windows.

Пакет имитационного моделирования AnyLogic AnyLogic — программное обеспечение для ИМ сложных систем и процессов, разрабо танное российской компанией XJ Technologies. Многие крупные компании, такие как Билайн, Газпром, General Motors, Mitsubishi, McDonalds, остановили свой выбор на AnyLogic.

AnyLogic основан на Java и базируется на платформе Eclipse – современном стандарте для бизнес-приложений, благодаря которой AnyLogic работает на всех распространенных операционных системах (Windows, Mac, Linux и т.д.).

Графическая среда AnyLogic построена по тому же принципу, что и в Rockwell Arena.

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

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

Заявки имеют стандартный тип Entity, однако есть возможность присваивать заявкам соб ственные типы (Java-классы) с нестандартным набором атрибутов.

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

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

Ptolemy II Ptolemy II является проектом университета Беркли. Ptolemy II представляет собой набор пакетов Java, предназначенных для создания моделей, моделирования и проектирования си Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ стем реального времени и встраиваемых систем. Благодаря технологии Java Ptolemy может работать на всех распространенных операционных системах.

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

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

Ptolemy II распространяется бесплатно.

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

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

Компания Wolverine Software, поддерживающая другую систему, основанную на GPSS — GPSS/H — в 1989 г. выпустила продукт Proof Animation, позволяющий создавать анимацию к моделям GPSS World. Proof Animation представляет собой семейство программ ных продуктов, дополняющих анимацией процесс моделирования дискретных событий.

В Proof Animation используются два входных потока ASCII-кодов. Первый из них создает статическое изображение объекта, в котором происходит движение динамических элементов — заявок (аэропорт, госпиталь, банк и т. д.), а второй отображает временную последовательность заявок рождающихся, движущихся, уничтожаемых и т.п. Оба потока представляют собой ASCII-тексты свободного формата, создаваемые достаточно просто раз личными способами. Первый тип файлов обычно создается в среде Proof Animation, тогда как второй может генерироваться другими средствами моделирования (например, в GPSS World), но по стандартам Proof Animation.

Ниже приведена сводная таблица основных характеристик рассмотренных систем ИМ.

Сравнительный анализ средств имитационного моделирования Характеристика AnyLogic GPSS World Arena Ptolemy II задаются задаются можно задать с помощью с помощью только тип заявки Атрибуты заявок с помощью Java конструкции оператора ASSIGN Assign дополнение имеющихся только создание Создание новых конструкций язык PLUS из стандартных пользовательских моделирующих конструкций собственными модулей пакета библиотек функциями (Java) Построение моделей да нет да да с помощью пикто грамм Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Продолжение таблицы пошаговое пошаговое пошаговое пошаговое Возможности моделирование, моделирование моделирование моделирование отладки пауза, откат Возможности да да да нет создания (с помощью Proof) интерфейса Число вероятностных 29 25 12 распределений Иерархическое да нет да да моделирование совместная совместная совместная, 2D-анимация 2D-анимация раздельная библиотека GR (В версии и раздельная Анимация (Proof 5 и Proof 3D) (простейшие Professional 3D-анимация 3D объекты) 3D-анимация) (Arena 3DPlayer) Выводы В данной статье были рассмотрены четыре программных продукта, которые конкури руют на рынке систем ИМ. Во многом благодаря средствам визуализации ИМ обретает все большую популярность. Визуализация значительно облегчает восприятие модели. С ростом сложности моделей вычислительных систем крайне важным фактором становится скорость их работы на персональных компьютерах с ограниченной производительностью.

GPSS World является проверенной временем системой ИМ. Язык GPSS используется специалистами в области моделирования уже более 40 лет. Однако сама система обладает ря дом недостатков. В первую очередь — это отсутствие возможности интерактивного создания моделей. Средства визуализации сильно замедляют работу системы даже на очень мощных персональных компьютерах. Скорость прогона модели несмотря на отсутствие интерактив ного интерфейса сравнима со скоростью AnyLogic (при испытаниях на модели системы мас сового обслуживания М/М/1 на предельной скорости). Отсутствие поддержки иерархическо го моделирования делает модели на GPSS громоздкими и тяжелыми для восприятия.

Ptolemy II является бесплатным пакетом ИМ. В нем присутствуют возможности интер активного создания модели и иерархического моделирования. К недостаткам системы можно отнести низкую скорость работы (по скорости работы Ptolemy II значительно уступает GPSS World и AnyLogic) и слабые возможности визуализации процесса моделирования.

Из рассматриваемых в данной статье систем ИМ лидерами на рынке являются Rockwell Arena и AnyLogic. Они же предоставляют пользователю удобный, интуитивный пользова тельский интерфейс с возможностью интерактивного создания модели, а также встроенные средства визуализации процесса моделирования. Обе системы позиционируются как универ сальные средства моделирования, однако в Arena сделан уклон на моделирование бизнес процессов. AnyLogic предоставляет дополнительную гибкость в процессе построения модели за счет программирования на Java. Более того, AnyLogic работает быстрее, чем Arena (при испытаниях на модели системы массового обслуживания М/М/1 на предельной скорости AnyLogic показал производительность в 20 раз выше Arena).

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ ЛИТЕРАТУРА 1. Лоу А.М., Кельтон В.Д. Имитационное моделирование. СПб: Питер, 2004. 847 с.

2. Строгалев В.П., Толкачева И.О. Имитационное моделирование. М.: МГТУ им. Баумана, 2008. 379 с.

3. Алиев Т.И. Основы моделирования дискретных систем. СПб: СПбГУ ИТМО, 2009. 363 с.

УДК 004. ОТКАЗОУСТОЙЧИВЫЙ АЛГОРИТМ МАРШРУТИЗАЦИИ ДЛЯ СЕТЕЙ НА КРИСТАЛЛЕ А. С. Румянцев Рост уровня интеграции и увеличение количества гетерогенных компо нентов в системах на кристалле (СнК) и сетей на кристалле (СтнК) при водит к необходимости внедрения реконфигурируемых алгоритмов для обеспечения отказоустойчивости. Особенно остро данная задача стоит для СтнК, так как в большинстве существующих реализаций СтнК ис пользуются различные детерминированные алгоритмы маршрутизации.

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

Ключевые слова: сеть на кристалле, маршрутизация, отказоустойчивость.

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

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

— Ресурсы (отдельные подсистемы СтнК) подключены к сети посредством адаптеров.

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

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

— Большинство маршрутизаторов могут независимо друг от друга передавать данные.

Значительное уменьшение размеров интегральных схем в последнее время позволяет зна чительно увеличить емкость интегральных схем (в транзисторах, помещающихся на схеме) и снизить энергопотребление. Однако данная тенденция создает новые проблемы при создании Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ интегральных схем. В связи с резко сокращающимися размерами элементов становится все труднее контролировать различные физические параметры в производственном процессе. Ре зультатом этого становится значительное увеличение ошибок и сбоев в производимых инте гральных схемах: перекрестные помехи начинают мешать передаче сигнала, производственные ошибки могут приводить к образованию нерабочих сегментов схем и т.д. Кроме того, увеличи вается количество схем, которые выходят из строя в период эксплуатации.

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

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

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

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

Рассматриваемая типовая архитектура СтнК В представленной работе делается попытка объединить детерминированный алгоритм маршрутизации (маршрутизации по адресу назначения — XY-маршрутизация) с набором пра вил локальной маршрутизации, при возникновении отказов, для обеспечения отказоустойчи вой маршрутизации. Данный алгоритм призван достичь минимальных ресурсов, необходи мых для реализации, сравнимых с алгоритмами детерминированной маршрутизации, и огра ниченного использования пропускной способности СтнК, т.е. уменьшение количества или сведения на нет широковещательных запросов. Применение данных ограничений позволяет использовать полученный алгоритм отказоустойчивой маршрутизации в СтнК.

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

Сборник трудов молодых ученых и сотрудников кафедры ВТ КОМПЬЮТЕРНЫЕ СИСТЕМЫ Каждый маршрутизатор будет иметь 5 сетевых адаптеров: 4 — для связи с другими маршрутизаторами и 1 — для связи с подсоединяемым к СтнК ресурсом, а кроме того, обла дает уникальным адресом в данной сети формата i, j.

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

Рис. 1. Связь сетевых адаптеров в предлагаемой СтнК Физический уровень отвечает за передачу информации на битовом уровне между двумя соседними адаптерами. Канальный уровень ответствен за установление соединения между соседними адаптерами и надежную передачу. В предлагаемой архитектуре на канальном уровне реализован простой протокол установления соединения, основанный на возможностях физического уровня. В этом протоколе, если маршрутизатор хочет передать данные соседне му маршрутизатору, он просто выставляет на шину «data_out» данные и устанавливает сигнал «ctrl_tx». Когда принимающий маршрутизатор примет данные с шины «data_in», он устанав ливает сигнал «ctrl_act_rx». На этом передача заканчивается.

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

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

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



Pages:     | 1 || 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.