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

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

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


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ УДК 004:51:621.3:537.8

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ББК 32.97

Российская академия наук Т78

Московский физико-технический институт

(государственный университет)

Российский фонд фундаментальных исследований

Труды 52-й научной конференции МФТИ «Со Федеральная целевая программа Т78 временные проблемы фундаментальных и при «Научные и научно-педагогические кадры инновационной России»

кладных наук». Часть I. Радиотехника и кибернетика.

на 2009–2013 годы Том 1. — М.: МФТИ, 2009. — 182 с.

Фонд содействия развитию малых форм предприятий ISBN 978-5-7417-0323- в научно-технической сфере ТРУДЫ В сборник включены результаты фундаментальных и приклад 52-й НАУЧНОЙ КОНФЕРЕНЦИИ МФТИ ных исследований студентов, аспирантов, преподавателей и научных сотрудников МФТИ, а также ряда научных и учебных организаций.

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

Часть I Радиотехника и кибернетика В октябре 2009 года Московский физико-технический институт (государ ственный университет) стал победителем конкурсного отбора программ раз вития университетов России, в отношении которых устанавливается кате Том 1 гория «национальный исследовательский университет».

УДК 004:51:621.3:537. ББК 32. ISBN 978-5-7417-0323- c ГОУ ВПО «Московский физико-технический Москва–Долгопрудный, институт (государственный университет)», Секция радиотехники и защиты Программный комитет информации Кудрявцев Н.Н., чл.-корр. РАН, ректор института — председатель Кондранин Т.В., профессор, первый проректор — зам. председателя Стрыгин Л.В., доцент — учёный секретарь конференции Алфимов М.В., академик, директор Центра фотохимии РАН Андреев А.Ф., академик РАН, директор ИФП РАН Беляев С.Т., академик РАН, зав. кафедрой МФТИ Велихов Е.П., академик РАН, президент РНЦ «Курчатовский институт» УДК 519. Гуляев Ю.В., академик РАН, директор ИРЭ РАН Дмитриев В.Г., чл.-корр. РАН, зав. кафедрой МФТИ С.М. Владимиров Иванников В.П., академик РАН, директор ИСП РАН Коротеев А.С., академик РАН, директор Центра им.



М.В. Келдыша vlsergey@gmail.com Кузнецов Н.А., академик РАН, зав. кафедрой МФТИ Московский физико-технический институт Макаров В.Л., академик-секретарь Отделения ОН РАН, дир. ЦЭМИ РАН (государственный университет) Петров А.А., академик РАН, заведующий отделом ВЦ РАН Фортов В.Е., академик-секретарь Отделения ЭММПУ РАН Использование итеративного Патон Б.Е., академик, президент НАН Украины Шпак А.П., академик, первый вице-президент НАН Украины декодирования в сетевом кодировании Черепин В.Т., чл.-корр. НАН Украины, директор ФТЦ НАНУ Жданок С.А., академик-секретарь Отделения ФТН НАН Беларуси Гаричев С.Н., д.т.н., декан ФРТК Передача сообщений в сетевом кодировании при использовании Трунин М.Р., д.ф.-м.н., декан ФОПФ обычных блоковых кодов, рассчитанных на передачу кодовых слов (а Негодяев С.С., к.т.н., декан ФАКИ не подпространств), с одной стороны, даёт возможность использовать Грознов И.Н., доцент, декан ФМБФ Тодуа П.А., профессор, декан ФФКЭ весь опыт и наработки по блоковым кодам. Однако как было показа Вышинский В.В., профессор, декан ФАЛТ но в работе Jingyu Kang и др. [1], линейные комбинации сообщений и Шананин А.А., профессор, декан ФУПМ последующее восстановление негативно сказываются на вероятности Леонов А.Г., профессор, декан ФПФЭ Кривцов В.Е., доцент, декан ФИВТ восстановления сообщений: если на вход декодера поступают сообще Ковальчук М.В., чл.-корр. РАН, декан ФНБИК ния A и AB, то при одинаковой вероятности ошибки в блоке для по Деревнина А.Ю., д.т.н., декан ФИБС ступивших сообщений после декодирования вероятность ошибки для Кобзев А.И., профессор, декан ФГН сообщения B будет большей. В качестве решения представленной за Кваченко А.В., к.т.н., зав. кафедрой Алехин А.П., профессор, зав. кафедрой дачи авторы предложили, во-первых, осуществлять одновременное Белоусов Ю.М., профессор, зав. кафедрой декодирование сообщений итеративным способом, обмениваясь при Бугаев А.С., академик РАН, зав. кафедрой этом информацией об апостериорных вероятностях декодирования Габидулин Э.М., профессор, зав. кафедрой битов, во-вторых, разбить сообщения на два блока, каждый из кото Гладун А.Д., профессор, зав. кафедрой Иванов А.П., профессор, зав. кафедрой рых пойдёт по своему пути. Тем самым авторы добились уравнивания Лукин Д.С., профессор, зав. кафедрой вероятностей декодирования сообщений A и B за счёт модификации Петров И.Б., профессор, зав. кафедрой декодера и модификации протокола.

Половинкин Е.С., профессор, зав. кафедрой В работе предлагается использование способа передачи информа Сон Э.Е., чл.-корр. РАН, зав. кафедрой Тельнова А.А., доцент, зав. кафедрой ции, когда вместо одновременного декодирования двух и более сооб Трухан Э.М., профессор, зав. кафедрой щений, каждое из которых состоит из нескольких пакетов, использу Холодов А.С., чл.-корр. РАН, зав. кафедрой ется единственное сообщение из нескольких частей. При этом пред Энтов Р.М., академик, зав. кафедрой лагается способ передачи данных, который легко обобщается как на Секция радиотехники и защиты информации 5 6 52-я научная конференция МФТИ ФРТК- сообщение. Можно показать, что при отсутствии ошибок передачи произвольное количество частей сообщения (путей в сети), так и на расширенная матрица Рж и вектор x дают нулевой синдром ошибки.





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

LDPC-кода размером 96 на 48. Считалось, что работают два при Рассмотрим модель сети бабочка. Под a и b будем понимать две ёмника, первых из которых принимает сообщения a и b, второй — a части одного кодового слова mLDP C-кода. По стандартному способу и a b. При этом каждое сообщение закодировано с использованием декодирования исходного сообщения в приёмниках восстанавливает амплитудной модуляции с a = 1, на канал передачи действует адди ся каждая из его частей, после чего декодируется код и исправляют тивный белый гауссов шум с дисперсией. Оба приёмника пытаются ся ошибки передачи. Обозначим принятые сообщения через m1 и m2.

исправить ошибки в кодовом слове m как первым, так и вторым Тогда без ограничения общности для левого приёмника:

способом. Измеряется вероятность ошибки в блоке в зависимости от a = m1, величины энергии на информационный бит:

b = m1 m2.

После этого сообщение m восстанавливается простой конкатенацией m = a ||b.

Предлагается новый способ декодирования, когда операция вос становления исходных частей сообщения включается в алгоритм де кодирования m из принятых сообщений m1 и m2 с помощью итера тивного декодирования. Пусть H — проверочная матрица выбранного LDPC-кода.

Построим сообщение x как конкатенацию нулей и принятых сооб щений:

x = 0–0||m1 ||m Первая часть вектора (нули) по размеру совпадает с размером ис ходного сообщения m. Таким образом, размерность вектора x будет равна удвоенной размерности исходного вектора m. Будем использо вать следующую проверочную матрицу:

Рис. 1. Вероятность ошибки в блоке в зависимости от величины H 0 энергии на информационный бит для стандартного и улучшенного Il 0 Il H=.

алгоритма Il Il 0 Il На диаграмме показано 6 графиков, 3 из которых совпадают.

Здесь l — длина принятых сообщений m1 и m2, Il — единичная матри- Красным отмечены вероятность ошибки в блоке для обычного алго ца размера l = n/2, где n — длина исходного кодового слова m, а так- ритма декодирования, жёлтым — для улучшенного алгоритма с рас же ширина исходной матрицы H;

0 — нулевые матрицы. Данную про- ширенной проверочной матрицей. В качестве легенды указываются верочную матрицу используем для итеративного «декодирования» со- сообщения, которые пришли на вход декодера. Графики для a,a b и общения x, а именно для восстановления первых 2lбит. Итеративный ab,b совпадают для обоих алгоритмов, что косвенно свидетельствует алгоритм используем в том виде, как он описан в книге Маккея [2], о точности моделирования. Совпадение графиков для a, b показыва причём будем считать, что первые 2lбит сообщения x имеют априор- ет, что для случая, когда на вход декодера пришли сами сообщения, ные вероятности 50% (то есть стёрты). После окончания декодирова ния первые 2lбит сообщения будем использовать как восстановленное Секция радиотехники и защиты информации 7 8 52-я научная конференция МФТИ ФРТК- а не их линейные комбинации, использование нового алгоритма не Любую IT-инфраструктуру необходимо защищать, в первую оче даёт преимуществ, однако он и не хуже обычного алгоритма. редь от несанкционированного доступа. Традиционные средства за Данный способ удобно расширить на случай случайного сетевого щиты информации от НСД в системах виртуализации не эффектив кодирования, а также случай, когда количество блоков больше двух ны, поскольку в структуре программной среды появляются два до (рис. 1). полнительных уровня — гипервизор и виртуальные устройства. Та кие изменения кардинально меняют подход к построению системы Литература защиты. Например, если злоумышленник получит доступ к среде вир туализации, то любая виртуальная машина, а следовательно, и вся 1. King Jyngli, Zhou Bo, Ding Zhi, Lin Shu. LDPC coding schemes обрабатываемая ею информация, может быть полностью скомпроме for error control in a multicast network // In Proceedings of IEEE тирована. Традиционные средства защиты, даже если они начинают International Symposium on Information Theory, July 6-11. — Toronto:

работать сразу после включения виртуальной машишы, не смогут за 2008. — P. 822–826.

щитить обрабатываемую в гостевой ОС информацию, поскольку к 2. MacKayd David J.C. Information theory, inference and learning ней есть доступ с более низкого уровня. Поэтому система защиты в algorithms. — Cambridge: Cambridge University Press, 2003. — 628 p. — среде виртуализации должна функционировать на всех уровнях за ISBN 0-521-64298-1.

щищаемой среды.

С точки зрения гипервизора и управляющей ОС виртуальная ма шина, на которой может быть запущена гостевая ОС, представля УДК 004.9 ет собой набор файлов. Пользователь виртуальной инфраструктуры может иметь право на чтение и модификацию этих файлов. Осуще С.В. Лапшин ствить эти права можно из ОС управления виртуальной инфраструк турой. Поэтому, для обеспечения защиты от НСД разграничения до sv.lapshin@gmail.com ступа только в гостевых ОС не достаточно. Подсистема разграниче Московский физико-технический институт ния доступа должна также функционировать в ОС управления.

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

ки, повысить эффективность и управляемость IT-инфраструктуры. В то же время он должен иметь доступ к контролируемой среде.

Виртуализация платформ является хорошим для этого решением и Поскольку вычислительная среда меняется во времени, контроль це за последние годы получила широкое распространение. Продукта- лостности программной среды «снаружи» затруднен, и компоненту ми виртуализации стало намного проще пользоваться, они стали бо- безопасности необходимо иметь возможность «влезть» в эту среду, лее надежными и функциональными. Примерами являются VMware исследовать ее, и сравнивать полученные параметры среды с эталон Infrastructure, Citrix XenServer, KVM и т. д. ными. Под параметрами среды в данном случае подразумеваются не Секция радиотехники и защиты информации 9 10 52-я научная конференция МФТИ ФРТК- только параметры гостевой операционной системы, но также настрой- УДК 004.056. ки самой виртуальной машины, например, набор её оборудования.

В.А. Обернихин Исходя из этих рассуждений, в системах виртуализации компо нент безопасности должен находиться на уровне между гипервизо- obernikhin@mail.ru ром и виртуальными машинами. Также необходимо обеспечивать це Московский физико-технический институт лостность самого компонента безопасности. Это может быть реали (государственный университет) зовано только двумя способами — из гипервизора и аппаратно. По Восстановление работоспособности сетевых скольку вмешиваться в работу гипервизора некорректно и это мо жет привести к существенному падению производительности систе кластеров виртуальных серверов после мы, то контроль целостности компонента безопасности необходимо вирусных атак осуществлять аппаратно.

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

ратный модуль доверенной загрузки.

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

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

процентов. Этот факт давно был подмечен различными исследовате лями, в частности, уже в течение нескольких лет программное обес Литература печение проекта Берклиевского университета Seti@home [1] начинает 1. Конявский В.А. Управление защитой информации на базе СЗИ использовать время CPU только когда оно используется не полно НСД «Аккорд». — М.: Радио и связь, 1999. — 325 с. стью другими пользовательскими программами.

2. Yanick de Jong. Xen hypervisor security in VM isolation. — Специализированное программное обеспечение даёт возможность Amsterdam: Universiteit van Amsterdam, 2009. — 30 c. запускать множество (десятки и даже сотни) виртуальных серверов 3. Лапшин С.В., Счастный Д.Ю. Виртуализация: в поисках точ- на базе одного физического. С точки зрения пользователя каждый ки опоры // Материалы XIV международной конференции «Ком- виртуальный сервер представляет из себя полнофункциональный фи плексная защита информации». — 2009. — С. 147. зический сервер.

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

Безопасность виртуальных серверов. С точки зрения инфор мационной безопасности возникают дополнительные вопросы обеспе чения безопасности между виртуальными сервервами, а также без Секция радиотехники и защиты информации 11 12 52-я научная конференция МФТИ ФРТК- опасность самого физического сервера. Изоляция виртуальных сер- чики, позволяющие обеспечивать адекватную реакцию на попытки веров друг от друга и от основного физического сервера обеспечи- заражения приложения-аудитора.

вается самим ПО виртуализации, однако механизмы интеграции го- Известные способы использования совокупности аппаратных мо стевых систем с хостом а также уязвимости ПО делают возможным дулей TPM, TXT и VT-x ограничивались обеспечением доверенной нарушение данной изоляции ( [2]). загрузки основного физического сервера и виртуальных серверов.

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

безопасности.

Литература Для любой компьютерной системы необходимым механизмом по строения изолированной программной среды [3, с. 30] является обес- 1. Исследовательский проект Берклиевского университета печение доверенной загрузки операционной системы [3, c.57]. В свою Seti@home URL: http://setiathome.berkeley.edu/ .

очередь для доверенной загрузки операционной системы необходимы 2. Бюллетень по информационной безопасности средства контроля целостности загружаемых исполняемых файлов. VMware Security Advisory VMSA-2009-0006 URL: http://Наиболее распространенным аппаратным средством контро- http://www.vmware.com/security/advisories/VMSA-2009-0006.html .

ля целостности загружаемых модулей является Trusted Platform 3. Щербаков А.Ю. Методы и модели проектирования средств обес Module [4], интегрированный во множество выпускаемых на се- печения безопасности в распределённых компьютерных системах на годняшний день материнских плат компьютеров и переносных основе создания изолированной программной среды. Диссертация на устройств. Дополненный Trusted Execution Technology [5] данный ап- соискание ученой степени доктора технических наук. — М.: 1997.

паратный комплекс позволяет обеспечить доверенную загрузку ос- 4. Trusted Computing Group URL: http://новного «физического» сервера и виртуальных серверов [6]. http://trustedcomputinggroup.org/developers/ .

Стоит отметить, что на сегодняшний день известны атаки, поз- 5. Trusted Execution Technology URL: http://воляющие сразу же после доверенной загрузки получить полный до- http://www.intel.com/technology/security/ .

ступ к системе [7]. 6. Bernhard Jansen, HariGovind V.Ramasamy, Matthias Schunter.

Восстановление сетевых кластеров виртуальных серверов Flexible Integrity Protection and Verication Architecture for после вирусных атак. Применение совокупностей технологий ап- Virtual Machine Monitors» (IBM Research) // 2nd Workshop паратной поддержки виртуализации (VT-x), TPM и TXT позволяет on Advances in Trusted Computing. — 2006. URL: http://не только контролировать целостность исполняемых модулей систе- http://www.trl.ibm.com/projects/watc/XenSecurityServicesPaper.pdf .

мы в момент загрузки, но и использовать тот же механизм на уже 7. Wojtczuk R., Rutkowska. J. Attacking Intel R Trusted Execution зараженной системе. В качестве обычного приложения, контролиру- Technology // Black Hat Briengs. — USA, DC: 2009. URL: http://емого TPM и TXT, может быть запущено приложение — «аудитор», invisiblethingslab.com/press/itl-press-2009-01.pdf.

для обследования текущего состояния системы. Поскольку TPM и TXT обеспечивают дополнительную изоляцию страниц памяти для приложений, приложение — «аудитор» может осуществлять деятель ность по сбору информации и проверке текущего состояния системы даже в уже зараженной среде. При несанкционированном доступе к страницам памяти приложения-аудитора будут срабатывать обработ Секция радиотехники и защиты информации 13 14 52-я научная конференция МФТИ ФРТК- УДК 519.72 Наборы параметров 1, 2 обеспечивают большую криптостойкость, но меньшую помехозащищенность по сравнению с набором 3. Помехо А.А. Сенюта, А.С. Кшевецкий защищенность рассматривается как требуемый уровень сигнал/шум, необходимый для обеспечения значения ошибки на бит, равной 102.

anton.seny@gmail.com Разница в помехозащищенности между 1-м и 3-м наборами составля Московский физико-технический институт ет 2 дБ. Это является малым значением для канала связи с высоким (государственный университет) уровнем сигнал/шум ( 20 дБ). Значение криптостойкости набора Оптимизация параметров интегрированной является критичным на сегодняшний день.

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

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

ну характеристику, но при этом будут ухудшаться другие. Например, — криптосистема ГПТ [2];

повышая криптостойкость, ухудшается помехозащищенность. Таким — добавление столбцевого скремблера [3];

образом, важной является задача определения параметров криптоси- — на приводимых ранговых кодах [4];

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

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

— вид криптосистемы;

Выбрана модуляция QAM-16, характерная для радиоканала с ор — длины открытого и шифро-блоков;

тогональным частотным уплотнением. Передаваемый сигнал пред — скорость шифрования;

ставляется в виде матрицы из QAM-символов на частотно-временной — криптостойкость;

диаграмме. Строки соответствуют подчастотам, столбцы — дискре — модуляция, виды перемежения;

там времени. Тогда широкополосный шум — стирание столбцов, а — гауссов шум;

узкополосный шум — строк. Вероятность появления помехи задается — широкополосный и узкополосный шумы. как стирание одной строки или одного столбца. Для модели канала была выбрана вероятность появления помехи, равной 103.

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

является зависимость вероятности ошибки на бит от величины гаус- В работе [1] произведён сравнительный анализ разных видов пере сова шума. межений для ранговых кодов. Показано, что при равной вероятности Результаты. В выполненной работе выделено 3 набора парамет- помех двух видов, нужно применять перемежение, при котором каж ров интегрированной криптосистемы (рис. 1). Из 3-х представленных дый QAM-символ на частотно-временной диаграмме содержит биты наборов первый является наиболее оптимальным. разных кодовых слов рангового кода. Такой вариант перемежения Секция радиотехники и защиты информации 15 16 52-я научная конференция МФТИ ФРТК- взят в качестве оптимального для интегрированной криптосистемы УДК 004. в условиях рассматриваемых помех.

С.И. Смирнов 3. Заключение. В работе предложены оптимальные параметры для интегрированной криптосистемы с защитой от несанкциониро- imshodan@gmail.com ванного доступа и помех в канале исходя из требований на крипто Московский физико-технический институт стойкость. Проведено сравнение помехозащищенности для несколь (государственный университет) ких уровней криптостойкости.

Исследование линейных регистров сдвига специального вида В [1, 2] введено понятие управляемого регистра сдвига (УРС).

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

Отличие ЛУРС от классического состоит в возможном наличии инверторов между элементами задержки.

Рис. 1. Наборы оптимальных параметров интегрированной Рассмотрим, какие же преимущества даёт исследуемая структура.

криптосистемы Во-первых, при криптоанализе системы, построенной на ЛУРС, существенно увеличивается количество переборов для решения зада Литература чи полным перебором — с 2n до 22n.

Во-вторых, криптоанализ принципиально затруднён. Действи 1. Kshevetskiy A., Senyuta A. Performance Evaluation of Rank Codes тельно, рассмотрим зависимость между элементами выходной по in Channels with AWGN and Criss-Cross Errors // Proc. of the XII следовательности { xn } классического ЛРС. Она имеет вид international symposium on problems of redundancy in information n xn = i=0 i xi, где x0 — первый элемент, с которого началось наблю and control systems. — Saint-Petersburg, Russia, 26-30 May, 2009. — дение выходной последовательности ЛРС криптоаналитиком. Для P. 130–136.

2. Gabidulin E.M., Paramonov A.V., Tretjakov O.V. Rank errors and вскрытия ЛРС, то есть для нахождения всех i, достаточно прона блюдать последовательность длиной 2n и решить систему линейных rank erasures correction // Proc. Fourth Int. Colloquium on Coding уравнений. Наличие инверторов усложняет картину. Зависимость бу Theory. — Dilijan, Armenia, 30 September. — 7 October, Yerevan, дет иметь следующий вид: xm = n1 i xmn+i i j i.

1992. — P. 11–19. i=0 j= 3. Ourivski Alexei, Gabidulin E.M. Column Scrambler for the GPT Такое выражение показывает, что получаемая в случае ЛРС спе Cryptosystem // Discrete Applied Mathematics. — 2003. — N. 128(1). — циального вида система уравнений для криптоанализа нелинейна.

P. 207–221.

4. Kshevetskiy A., Gabidulin E. High-weight errors in reducible rank codes // Proc. of the 8th International Symposium on Communication Theory & Applications. — 2005. — P. 71–76.

Секция радиотехники и защиты информации 17 18 52-я научная конференция МФТИ ФРТК- к стандартному и наоборот. Сложность перехода называется тран Литература зитивной сложностью. Низкой транзитивной сложностью обладают оптимальные нормальные базисы. При оптимальном выборе базисов 1. Орлов В.А. Об одном представлении конечных автоматов // сложность перехода будет сравнима с O(n), если используется опти Тезисы докладов XV международной конференции «Проблемы тео мальный базис первого типа, или с O(pn logp n) — в случае базисов ретической кибернетики». Казань: Отечество, 2008.

второго и третьего типа.

2. Орлов В.А. Об одном способе реализации конечных автоматов Оценим сложность операции умножения в стандартном базисе:

// Вестник МГУПИ. — 2009. — № 21. — С. 77–80.

s Mg (n) M2 (n) + kn, где — M2 (n) = O(n log2 n log2 log2 n) — сложность операции умноже ния многочленов степени n 1 над полем GF (2);

с высокой вероят УДК 519.725. ностью k = 3, в худшем случае k = 5.

И.Ю. Сысоев Оценим сложность операции умножения в оптимальном нормаль ном базисе. Для выполнения умножения выполняется переход к стан Igor.Sisoev@gmail.com дартному базису со схемной сложностью 2n 2, затем производится Московский физико-технический институт умножение в стандартном базисе и осуществляется переход обратно (государственный университет) к нормальному базису со сложностью n 1.

Одновременное использование Оценка сложности в оптимальном нормальном базисе 1-го типа:

стандартного и нормального базисов M2 (n) + 7n 8.

M O1 (GF (2n )) s при реализации алгоритмов кодирования В оптимальном нормальном базисе 2-го или 3-го типа и декодирования рангового кода 3n M O2 (GF (2n )) s 3M2 (n) + log2 n + O(n).

На сегодняшний момент ранговые коды являются перспективны- Оценим сложность операции инвертирования в стандартном базисе:

ми для использования в системах, использующих идею сетевого ко (n 1)K2 (n) + (2 (n 1) + I(GF (2n )) дирования. Актуальной задачей является эффективная реализация алгоритма рангового кода.

+ 2 (n 1) + 1 + o(1))M O (GF (2n )), При реализации криптографических алгоритмов самыми ресурсо затратными являются операции возведения в степень (в том числе, где K2 (n) — оценка сложности возведения в степень 2, K2 (n) = O(n).

операция инвертирования) и умножения. Чаще всего вычисление в Заметим, что указанная оценка сложности инвертирования в случае конечных полях выполняется либо только в нормальном, либо толь- стандартного базиса справедлива и для операции деления.

ко в стандартном базисе. Умножение эффективнее производить в Сложность операции инвертирования в оптимальном нормальном стандартном (линейная сложность), а возведение в степень — в нор- базисе:

I O (GF (2n )) (2 (n 1) + мальном базисе (циклический сдвиг координат). Существует метод, позволяющий использовать оба этих преимущества. В таком мето + 2 (n 1) + 1 + o(1))M O (GF (2n )), де операции умножения и возведения в степень используются в наи где 2 (n) = log2 (n 1), а 2 (n) — число единиц в двоичной запи более подходящем для операции базисе. Дополнительную вычисли си числа n. Стоит указать, что возведение в степень 2 выполняется тельную нагрузку в этом случае даёт переход от нормального базиса практически без затрат.

Секция радиотехники и защиты информации 19 20 52-я научная конференция МФТИ ФРТК- Для сравнения скорости алгоритмов оценим асимптотическую Сложность операции возведения в произвольную степень d n:

разность сложностей реализации:

M O (GF (2n )) log2 d O( ).

Lstd Lopt O(n2 n log n).

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

базисе, а возведения в степень — в нормальном базисе. Для простей Литература шего случая с кодовым расстоянием d = 3, потребуются две операции умножения для вычисления синдрома s, две операции деления и одна 1. Габидулин Э.М., Афанасьев В.Б. Кодирование в радиоэлектро операция возведения в квадрат для определения вектора ошибки. нике. — М.: Радио и связь, 1986. — 176 c.

Оценим сложность алгоритма в случае стандартного базиса: 2. Болотов А.А., Гашков С.Б. О быстром умножении в нормаль ных базисах конечных полей // Дискретная математика. — 2001. — Lstd = 3(M (n) + 3n) + T.13, № 3. — С. 3–31.

3. Сагалович Ю.Л. Введение в алгебраические коды. — М.:

+2((n 1)O(n) + (2 (n 1) + МФТИ, 2007. — 260 с.

+ 2 (n 1) + 1 + o(1))M (n)) + O(n) = = 2((n 1)O(n) + (2 (n 1) + 2 (n 1) + УДК 004.492. +2 + o(1))M (n)) + M (n) + 9n + O(n), Если производить операцию возведения в степень только в нормаль- А.Д. Чорняк ном базисе, а умножение многочленов — в стандартном, то получаем a.chornyak@gmail.com оценку сложности алгоритма:

Московский инженерно-физический институт (Национальный Lopt = 3(M (n) + 7n 8) + исследовательский ядерный университет) Автоматизированное выделение и методы + 2(2 (n 1) + 2 (n 1) + 1 + оценки сигнатур разрушающих + o(1))(M (n) + 7n 8) + 1 · 0 = программных воздействий = 2(2 (n 1) + 2 (n 1) + 2 + + o(1))(M (n) + 7n 8) + В настоящей статье предлагается следующий подход к автомати + (M (n) + 7n 8), зации процесса выделения сигнатур.

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

ствия (РПВ), после чего осуществляется сравнение контрольных сумм файловой системы до и после заражения. Элементы множества Секция радиотехники и защиты информации 21 22 52-я научная конференция МФТИ ФРТК- R можно получить не только исполнением самого РПВ, но и запус- си в конец, изменение даты или атрибутов у файла, строки типа ком его потомков. Чем больше множество R, тем меньше вероятность « [Ee] [Ll] [Ff]», « [Ss]cript», « [Jj]ava», и т. д.

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

лять собой «чистую систему» (C). Чем оно больше, тем меньше ве- Суть его состоит в следующем. Проверке подлежит некоторая ги роятность ошибок типа «false positive». потеза H, с которой связаны некоторые утверждения А1, А2 и т. д.

По сути, задача выявления сигнатур сводится к нахождению по- Тогда, проверив одно из них (A), мы можем пересчитать вероятность следовательности, присутствующей во всех файлах, зараженных дан- гипотезы H с учётом истинности или ложности этого утверждения.

ной моделью РПВ, и не встречающихся ни в одном файле «чистой В рамках данной работы в качестве гипотезы H будет выступать системы». То есть необходимо найти новое множество потенциальных предположение о том, что файл, содержащий данную сигнатуру, бу сигнатур (SP ) представляющее собой вычитание множества C из мно- дет являться инфицированным, либо самим РПВ. В качестве утвер жества R. При этом нет никакой необходимости в дизассемблирова- ждений (A) предлагается использовать эвристические признаки, при нии файлов, что даёт существенный выигрыш в производительности. сутствующие в оцениваемой сигнатуре.

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

сти не встречаются в «чистой системе», ещё не гарантирует отсут P1 (H/A1 A2...As ), P2 (H/A1 A2...As ),..., Pi (H/A1 A2...As ), ствия ложных срабатываний. Это связано с тем, что невозможно составить полное множество «чистой системы» C, так как оно бу где s количество эвристических признаков в сигнатуре. Из вычис дет стремиться к бесконечности. Данная задача разрешима только ленных вероятностей берется максимальная, так как она обеспечит для узких областей применения, где набор возможного программного наименьшую вероятность ложного срабатывания.

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

под качественной сигнатурой понимается последовательность, обес печивающая минимальное количество ложных срабатываний. P t P P + t, Качественная сигнатура должна содержать как можно больше эв- n n ристических признаков, характерных для моделей РПВ. Чем каче где t n = — точность оценки, — среднеквадратическое откло ственнее будет сигнатура, тем меньше вероятность ложных срабаты ваний. Исходя из этого, предлагается создать множество эвристиче- нение, n — объём выборки, P — выборочное среднее, t — аргумент функции Лапласа, при котором (t) =.

ских признаков (E), каждому из которых поставить в соответствие некоторый «вес» (Pi, i = 1, k, где k — число эвристических призна- Среднеквадратическое отклонение рассчитывается как ков), который будет соответствовать вероятности ложного срабатыва ния в случае наличия данного признака в сигнатуре. Соответственно n 1 (Pi P ).

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

n В качестве характерных для РПВ признаков можно использовать i= следующие: определение местоположения, то есть определение теку В данном случае выборка будет включать в себя совокупность всех щего IP, открытие файла на запись или смещения указателя запи весов Pi, i = 1, k, а также все вариации их произведений.

Секция радиотехники и защиты информации Секция инфокоммуникационных Вместо множества эвристических признаков в описанном выше методе можно также использовать частотные признаки. Для этого систем и сетей рассчитывается распределение значений байт по частоте их исполь зования в базе данных известных сигнатур (или вирусов), которое принимается как эталонное. «Веса» ставятся в соответствие каждо му значению байт, отражая частоту появления последнего в базе сиг натур. Чем больше частота, тем больше «вес». Далее производится поиск значений байт из эталонного распределения во множестве по УДК 519. тенциальных сигнатур SP. Если в одной последовательности множе ства SP содержатся несколько байт, значения которых совпадает со В.А. Абдрашитов значениями из эталонного распределения, то «веса» суммируются.

snooker@rt.mipt.ru Следовательно, из множества SP выбирается сигнатура с минималь ным значением P. Московский физико-технический институт Если вероятность ложного срабатывания у всех полученных сиг- (государственный университет) натур достаточно велика, то для исключения ошибки типа «false Оценка эффективности систем управления positive» предлагается совместно использовать пару потенциальных сигнатур. При этом общая вероятность ложного срабатывания будет работой персонала для операторов связи равна произведению вероятностей каждой сигнатуры. Однако недо статком данного подхода является увеличение времени сканирования В настоящее время активно разрабатываются и внедряются так вдвое.

называемые системы управления работой персонала (СУРП, англ.

Эффективность применения описанного метода обусловлена сле Workforce Management System) — программное обеспечение, которое дующими факторами:

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

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

раторов.

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

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

выполнении задачи, координация транспортных средств осуществля Литература ются в центре управления. Расписание составляется с учётом сво бодных рабочих часов инженеров, их физического расположения, 1. Cohen F. Computer viruses // Computers & Security. — 1987. — профессиональных навыков, имеющегося в наличии оборудования, N. 6. — P. 22–35.

временных ограничений и связанности задач. Далее может произво 2. Christodorescu M., Jha S. Static analysis of executables to detect диться так называемая оптимизация — модификация расписания для malicious patterns // SSYM’03: Proc. of the 12th conference on USENIX улучшения его параметров, повышения эффективности, например:

Security Symposium. — Berkeley, CA, USA: USENIX Association. — уменьшение промежутков в расписании, сокращение дальности пере 2003. — P. 12.

мещения инженеров путём назначения им задач в близко расположен 3. Касперски К., Рокко Е. Искусство дизассемблирования. — ных локациях, равномерная загрузка задачами разных инженеров.

СПб.: БХВ-Петербург, 2008. — 891 с.

Секция инфокоммуникационных систем и сетей 25 26 52-я научная конференция МФТИ ФРТК- 2. Guido B., Roberto G., Di Tria P. [et al.]. Workforce management Эффективное планирование и управление инженерными работа ми представляет собой нетривиальную задачу и требует значитель- (WFM) issues // IEEE Network Operations and Management ного количества времени и персонала. Специфика этих процессов до- Symposium. — 1998. — V. 2. — P. 473–482.

3. Azarmi N., Smith R. Intelligent scheduling and planning пускает их автоматизацию. Современные СУРП могут взять на себя функции составления и оптимизации расписания по различным пара- systems for telecommunications resource management // BT Technology метрам, составления поручений для инженеров и обработки отчёты Journal. — 2007. — V. 25, N. 3. — P. 241–248.

4. Pinker E.J., Larsont R.C. Models of Flexible Workforces о задачах, прокладывания маршрутов для водителей и прогнозирова ния спроса на инженерные ресурсы. Это позволит избежать ошибок, in Stochastic Service Environments, the One-Job Case. — Boston:

допускаемых диспетчером-человеком, увеличить производительность Massachusetts Institute of Technology, Operations Research Center, и снизить операционные расходы, принося этим дополнительную при- 1995. — 53 с.

5. Карманов В.Г. Математическое программирование. — М.: Физ быль компании. Поэтому представляет интерес величина прироста эффективности при применении СУРП по сравнению с ручным вы- матлит, 2004. — 264 с.

полнением перечисленных функций.

В работе представлена математическая модель СУРП, в рамках которой проведена формализация входных и управляемых парамет УДК 004. ров, выбраны критерии эффективности расписания и в упрощённом виде сформулирована математическая задача составления оптималь А.В. Васильев1, М.Н. Антоненко ного расписания задач и распределения работников по задачам. В бо лее общих предположениях выведены выражения, связывающие со- zolenenok@gmail.com, a.antonenko@fcs.coe.nagoya-u.ac.jp вокупные выходные параметры расписания со средними показателя- Московский физико-технический институт ми по выполнению отдельных задач и характеристиками трудовых (государственный университет) ресурсов компании. Также выведены формулы для некоторых клю- Институт автоматизации проектирования РАН чевых показателей эффективности основной деятельности операто Модели и методы оценки количественных ра связи в зависимости от используемой функциональности системы управления работой персонала.

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

ка и наличие связи с реестром оборудования дают прирост пропуск- Цель работы — показать состоятельность и применимость методов ной способности на 2.1, 0.8, 2.3 и 0.7 процентов соответственно. интеллектуального анализа данных (Data Mining) к задачам оценки количественных характеристик работ в рамках проектов.

Литература В работе решаются две задачи: из множества предоставленных 1. Melik R. The Rise of the Project Workforce. — Hoboken: John данных выделить наиболее важные — те, которые оказывают наи Wiley & Sons, 2007. — 344 с. большее влияние на конечный результат;

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

Секция инфокоммуникационных систем и сетей 27 28 52-я научная конференция МФТИ ФРТК- полученные на тестовых модельных данных, показали достаточную Для обнаружения этих «скрытых» знаний применяется алгоритм, точность, чтобы считать средства Data mining пригодными для ана включающий:

лиза проектов на основе накопленных данных, полученных с выпол 1) обработку пропущенных значений — таблицы данных часто со ненных проектов.

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

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

3) нормализацию — преобразование числовых атрибутов таким образом, чтобы значения атрибутов лежали в одном и том же диапа зоне;

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

5) решение задачи регрессии;

Рис. 6) тестирование регрессионной модели.

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

После того как модель построена и выбраны атрибуты, по кото рым предлагается делать оценку, данные разбиваются на два мно жества. На одном множестве производится «обучение»;

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

Рис. Для решения задачи были сняты метрики — среднеквадратичное отклонение, абсолютная погрешность. Если считать, что отклонения имеют нормальное распределение, то получится график, представ Литература ленный на рис. 2. Видим, что достоверность предсказания составля 1. Барсегян А.А., Куприянов М.С., Степаненко В.В. [и др.]. Тех ет порядка 80 процентов, что по мировой практике является очень нологии анализа данных: Data Mining, Visual Mining, Text Mining, приемлемым результатом.

OLAP. — СПб.: БХВ-Петербург, 2008. — 384 с.

Таким образом, по результатам выполнения работы средства Data 2. Хардман Р., МакЛафлин М. Oracle PL/SQL для профессиона Mining показали перспективность и состоятельность применения к лов. — М.: Лори, 2007. — 418 с.

задачам оценки количественных характеристик работ. Результаты, Секция инфокоммуникационных систем и сетей 29 30 52-я научная конференция МФТИ ФРТК- УДК 519.816 результаты предыдущего шага (рейтинги, полученные разными мето дами) в качестве входных данных (оценок по критериям).

А.В. Евдокимов1, А.Е. Харичкин1,2 Одним из наиболее удачных оказался следующий вариант итера ционного многометодного алгоритма. На первом шаге алгоритма каж alexey.evdokimov@gmail.com, akharitchkin@gmail.com дым методом из k классических методов решается исходная задача, Московский физико-технический институт состоящая из оценок альтернатив по критериям c и весов критериев (государственный университет) w:

ООО «НетКрэкер» k (cn,wn ) (sk ).

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

задач многокритериального принятия решений, в частности, задач На i-м шаге решается задача линейного упорядочения альтернатив (альтернативных решений). За дачи подобного рода называются ранжированием, а их решение обыч- k m,i1,wi1 ) (sm,i,wi );

i 1, (sn n k k но сводится к получению какого-либо рейтинга для каждой из аль тернатив (с последующей сортировкой альтернатив по рейтингу).

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

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

k j ных вычислений корректируется лицом, принимающим окончатель 1 + cos Si,Si ное решение [1, 2].

=C j Однако первые из указанных методов не исключают «запрограм- wi i w i1 ;

Ck,i =, мированных» ошибок из-за неполноты и/или неточности компьютер k ных моделей, вторые требуют привлечения дорогостоящих экспер- где Si — вектор рейтингов альтернатив, полученных k-м методом на тов, и даже «золотая середина» — человеко-машинные процедуры — i-м шаге [3].

имеют ограничения как по точности результата, так и по стоимости С помощью данного и подобных алгоритмов решались несколько процесса принятия решений. различных (по сути, объёму входных данных, требованиям к резуль Цель данной работы — избежать использования мнений экспер- тату) задач: задача выбора оптимальной схемы подключения (3 аль тов (которых затруднительно привлечь во многих реальных ситуа- тернативы, 4 критерия), задача отбора студентов в учебный центр циях), но при этом повысить степень доверия к результатам автома- ( 60 альтернатив и 6–7 критериев). Оказалось, что приведённый тического ранжирования. Эта цель достигается путём согласования выше алгоритм достаточно быстро сходится (не более 6 итераций да рейтингов, получаемых разными классическими методами (которые же на самой объёмной задаче при предъявлении завышенных требо по сути эвристические и поэтому не имеют никакой меры качества, ваний к точности). Само понятие «сходимости» определяется неодно позволяющая их сравнивать друг с другом), а также путём построе- значно;

в данной работе остановка итераций производилась на основе ния итерационного процесса, где каждый следующий шаг использует анализа либо норм отклонений векторов результатов в пространстве Секция инфокоммуникационных систем и сетей 31 32 52-я научная конференция МФТИ ФРТК- УДК 519. решений, либо последовательностей, отсортированных по рангу аль тернатив.

А.А. Кутафин1,2, Д.А. Некрылов1, В итоге результаты, полученные комбинированием различных ме тодов (трёх-четырёх из семи имевшихся в наличии), отличались лишь akutafin@gmail.com, mrdan@frtk.ru единичными различиями в последовательности из 60 альтернатив. Московский физико-технический институт Столь же небольшим оказалось отличие от эталонного решения, ко- (государственный университет) торое было составлено на основе мнений экспертов. Таким образом, ООО «НетКрэкер»

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

модернизации телекоммуникационной сети Литература с учётом технических и экономических 1. Ларичев О.И. Теория и методы принятия решений. — М.: Логос, критериев 2000. — 296 с.

2. Любченко В.В. Переключение методов в интерактивной проце Возможности экстенсивного пути развития сотовой связи стандар дуре принятия решений // Труды Одесского политехнического уни та GSM/EDGE близки к исчерпанию. Идет процесс перехода к новым верситета. — 2002. — Вып. 2(18). — С. 2–3.

технологическим решениям, которые лучше соответствуют возраста 3. Jaap S. Interactive multiple objective programming ющим требованиям пользователей к качеству и составу предлагае methods. — Springer, 1981. — P. 114–122. — http://мых услуг. По некоторым оценкам потребуется обеспечить для до publishing.eur.nl/ir/repub/asset/10709/HFDSTK.5.PDF.

машнего пользователя скорость доступа в среднем около 28 Мбит/с.

В современных сетях передачи данных пропускная способность со ставляет всего лишь от 50 Кбит/с до 1,5 Мбит/с на уровне абонент ского доступа.

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

В нашей постановке задачи дано исходное дерево, которое пред ставляет собой контроллер базовых станций (BSC — Base Station Controller) и обслуживаемые им базовые станции (BTS — Base Transceiver Station). Будем считать, что был проведён предваритель ный анализ текущей пропускной способности соединений и найдены участки, на которых она недостаточна для передачи возросших объ ёмов трафика.

При решении задачи принимались в рассмотрение следующие кри терии:

— стоимость модернизации, или «Cost», — остаточная пропускная способность, или «Bandwidth», — максимальное расстояние между узлами сети, или «Length».

Секция инфокоммуникационных систем и сетей 33 34 52-я научная конференция МФТИ ФРТК- Также были наложены ограничения на максимальную глубину де- Рассмотренный подход имеет большие перспективы для исполь рева и сгенерированы запреты на связь двух конкретных BTS (в ре- зования в реальной сети. Он позволяет избежать лишних затрат на альной жизни аналог — стоящее между ними здание). Требуется най- обновление оборудования сети, более рационально использовать те ти все варианты построения дерева с учётом ограничений и отобрать кущие ресурсы. Это особенно актуально в условиях повсеместного наилучшие. перехода к новым технологиям, например, от GSM к 3G, который Для решения поставленной задачи была использована теория важ- требует больших вложений.

ности критериев, в частности, метод количественных оценок, так как Литература многокритериальный подход в сравнении с однокритериальным име ет ряд преимуществ: 1. Подиновский В.В., Потапов М.А. Теоретические основы и си — не рассматривается взвешенная сумма, или линейная свёртка, стемы поддержки принятия многокритериальных решений. Инфор поэтому критерии с малыми весами тоже имеют существенное значе- мационные технологии в науке, образовании, телекоммуникации и ние, бизнесе // Приложение к журналу «Открытые конференции». — — возможность одновременного учёта и анализа критериев разно- 2007. — С. 87–89.

го рода (экономических и технических), 2. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, тех — результатом анализа является небольшое число недоминируе- нологии, протоколы: учебник для вузов. — 3-е изд. — СПб.: Питер, мых вариантов, из которых оператором выбирается наилучший на 2007. — 958 с.

основе дополнительных соображений или предпочтений.

В качестве тестовой модели был выбран участок реальной сети, состоящий из одного BSC и 33 BTS.

УДК 004. В результате решения получено 7 вариантов с использованием многокритериального анализа и 1 вариант с использованием простой Н.А. Подольская линейной свёртки. Этот вариант минимизирует стоимость, но осталь ные два критерия имеют нелучшие значения. Для передачи голоса nap@math.msu.su такое решение является подходящим, хотя сеть будет испытывать Московский физико-технический институт большие перегрузки при увеличении потоков трафика. (государственный университет) Варианты с большей стоимостью, но и большей пропускной спо- Московский государственный университет им. М.В. Ломоносова собностью будут предпочтительнее во многих других случаях, напри- ЗАО «Интел А/О»

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

Варианты с высоким значением критерия «Length» были отсеяны и методах её решения однокритериальной оптимизацией из-за малого веса параметра, но, как показывают результаты, они менее дорогие и могут оказаться Симуляция компьютерных сетей используется при решении раз наиболее предпочтительными для передачи данных.

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

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

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

Секция инфокоммуникационных систем и сетей 35 36 52-я научная конференция МФТИ ФРТК- Описанное усовершенствование ns-2 позволило провести оценку или 2) переиспользование реализации этого протокола в операцион алгоритмов выбора скорости передачи. Коды алгоритмов были встро ной системе. Недостатком первого метода является его недостовер ены в исходные тексты ns-2, и проведены измерения производитель ность, то есть возможное отличие от реализации протокола в реаль ности сетевого соединения для каждого из алгоритмов (рис. 1).

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

Примером программной симуляции сетевых соединений может служить симулятор ns-2 [1]. В нем симулируются временные харак теристики движения данных в сети. В ns-2 программно реализова ны все протоколы сетевого стека TCP/IP с точки зрения времени и продолжительности посылки фреймов. Данный симулятор может использоваться для оценки производительности сети или оценки ал горитма управления трафиком.


Автор доклада использовал ns-2 для оценки алгоритма выбора скорости передачи в сетевых соединениях, работающих по протоко лу 802.11 (WiFi) в закрытых помещениях. Выбор скорости передачи WiFi фрейма имеет большое влияние на производительность переда чи: при более низкой скорости передачи возрастает надежность, но удлиняется время передачи, при более высокой — сокращается вре Рис. 1. Графики производительность сетевого соединения при постоян мя перелачи фрейма, но уменьшается надежность передачи, то есть ных скоростях передачи и при использовании различных алгоритмов возрастает вероятность необходимости перепосылки фрейма, что вы выбора скорости передачи в зависимости от расстояния между WiFi зывает дополнительные траты времени.

станциями Для решения данной задачи возникла необходимость заново ре ализовать в ns-2 физический уровень стека сетевых протоколов, по- Переиспользование в симуляторе реализации сетевых протоко скольку алгоритм выбора скоростей актуален в условиях затухания лов, имеющихся в операционной системе (ОС), часто требует про радиосигнала, а в ns-2 симулируется свободная от помех среда пере- граммной реализации недостающей функциональности. Так, напри дачи. мер, при решении задачи оценки алгоритма, управляющего сетевым Задача симуляции затухания радиосигнала в закрытых помещени- трафиком, требуется включить этот алгоритм в функционирование ях была решена автором доклада совместно в Ф.Н. Шерстюком [2]. стека сетевых протоколов ОС. Данное достигается инсталляцей в Результатом решения явились симулированные значения уровня шу- операционной системе специального сетевого драйвера, например, ма радиоэфира. TUN/TAP [3].

Результаты решения задачи затухания радиосигнала были встрое- Под руководством автора доклада студентами механико-матема ны в исходные тексты симулятора ns-2: по ним определялось отноше- тического факультета МГУ М.С. Хроповым и А.Д. Ямпольским в ние уровня сигнала к уровню шума (Signal-to-Noise Ratio, или SNR) рамках выполнения курсовой работы решалась задача симуляции в данный момент времени. Заметим, что в ns-2 уровень сигнала за- беспроводной сети, состоящей из двух станций, связывающихся по висит от расстояния до передающей станции. Исходя из эксперимен- протоколу 802.11. Протокол 802.11 симулировался программно, этот тальных данных вероятности появления ошибок в процессе передачи код коммуницировал с драйвером TUN/TAP, инсталлированным в фрейма при данном SNR, вычислялась вероятность ошибки в приня- операционной системе, и посылка фреймов имитировала посылку их том фрейме. При наличии ошибки прием фрейма не подтверждался, WiFi станцией, то есть фреймы посылались с задержками, соответ и передающая станция вынуждена была передавать фрейм повторно. ствующими стандарту 802.11. Радиопомехи также симулировались Секция инфокоммуникационных систем и сетей 37 38 52-я научная конференция МФТИ ФРТК- поведение на реальной сети. Эффективность работы алгоритма на с использованием результатов работы [2]. Симулятор использовался прямую зависела от состояния радиоэфира, а для его отлаживания для оценки алгоритма, управляющего посылкой данных через сеть.

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

Решение задач симуляции компьютерных сетей предполагает ком Это привело к задаче моделирования Wi-Fi соединения на отдельно бинирование двух описанных выше методов: программной симуляции взятом компьютере.

сетевых протоколов и переиспользование сетевых протоколов, реали На данный момент существует несколько различных стандартов зованных в операционной системе. Выбор конкретного решения опре беспроводной связи. Наиболее распространены IEEE 802.11b/g, так деляется исходя из требований, предъявляемых к решению, а также же известные под общим названием Wi-Fi. Варианты беспроводного из имеющихся ресурсов.

стандарта IEEE 802.11 различаются между собой не только частота Литература ми вещания, но и поведением, которое призвано получить максималь но возможную скорость при любых условиях среды. Wi-Fi основан на 1. The Network Simulator. — ns-2. URL: http://типичном для большинства современных протоколов связи принци http://www.isi.edu/nsnam/ns/ . Документация и исходные тексты симу пе «данные–подтверждение»: после каждой отправленной части ин лятора ns-2.

формации станция связи ожидает реакции принимающей стороны.

2. Подольская Н.А., Шерстюк Ф.Н. Задача симуляции затуха В случае, если ответ не приходит, заглушен другим сигналом или же ния радиосигнала: решение и приложения // Фундамент. и при пакет поврежден, предполагается, что в эфире наличествует ещё как кл. матем. — 2007. — T 13, № 1. — С. 179–187. URL: http://минимум одна станция беспроводной связи, оперирующая на той же mech.math.msu. su/ f pm/ps/k07/k071/k07110. pdf.

частоте — обе ждут случайный, увеличивающийся с каждой неуда 3. Virtual Point-to-Point (TUN) and Ethernet (TAP) devices;

http://чей отрывок времени перед повторной отправкой. Таким образом, vtun.sourceforge.net/tun/. Документация и исходные тексты драйвера даже в заполненных Wi-Fi сигналами офисных комплексах удаётся TUN/TAP.

создать достаточно пространства для вещания каждой станции. Для случая посторонних шумов, не связанных напрямую с беспроводным обменом информацией, стандарт имеет настраиваемые скорости пе УДК 004.7 редачи данных — путём увеличения времени на передачу каждого пакета станция увеличивает шансы восстановления данных при при М.С. Хропов, А.Д. Ямпольский еме.

Для моделирования беспроводного соединения использовался agat-mt@mail.ru, corvus57@gmail.com драйвер Tun/Tap — широко известное виртуальное сетевое устрой Московский государственный университет им. М.В. Ломоносова ство, работающее с TCP/IP и Ethernet-фреймами на уровне операци О решении задачи симуляции сетевого онной системы. Конкретно использовался его Win32-аналог, являю щийся частью проекта Open-VPN. Это позволило программно симу соединения, работающего по стандарту лировать любое поведения пакета в предполагаемой среде, не исполь 802.11 зуя никаких иных средств, кроме компьютера, на котором запущена программа симуляции. С помощью Tun/Tap создаётся виртуальная сетевая карта, которую Windows способен адекватно распознавать.

Задача симуляции беспроводного сетевого соединения возникла Используя специальную C/C++ библиотеку, можно подключать к перед авторами доклада при решении задачи разработки алгоритма, этой карте драйвер, реализованный пользователем. Взаимодействие управляющего распределением потока данных в сети. Разработанный с TCP/IP протоколом реализуется с помощью системы событий — авторами алгоритм требовал тестирования и оценки производитель драйвер получает все пакеты, посланные на виртуальную карту, и ности сети, получаемой при использовании данного алгоритма. Одна ко в силу специфики алгоритма недостаточно было исследовать его Секция инфокоммуникационных систем и сетей 39 40 52-я научная конференция МФТИ ФРТК- может в свою очередь посылать другие пакеты назад на уровень при- Результат решения данной задачи был успешно применен для ложения, симулируя входящий трафик (рис. 1). оценки качества работы алгоритма распределения трафика в беспро водных сетях и его тестирования.

Литература 1. Podolskaya N.A., Sherstyuk F.N. The problem of Wi-Fi radio fading simulation: Solution and applications // Journal of Mathematical Sciences. — 2008. — V. 152, N. 4. — P. 571–577.

Рис. 1. Стеки протоколов TCP/IP с сете вой картой Wi-Fi и с драйвером Tun/Tap Для решения поставленной задачи был написан код драйвера для Tun/Tap, моделирующий поведение беспроводного соединения. Были реализованы очередь сообщений, вычисление задержки отправления пакета, возможность потери пакетов, имитирующая помехи, а также настраиваемые условия моделируемой среды. Для вычисления веро ятности повреждения данных в зависимости от помех в среде пере дачи информации были использованы теоретические и эксперимен тальные результаты статьи [1]. Сами помехи задавались функцией, зависящей от общего уровня шума, проводимости симулируемой сре ды распространения волн и проектируемого количества других Wi-Fi сетей, вещающих на той же частоте, что в сущности охватывает весь спектр возможных источников помех.

Преимущества такого подхода заключаются в следующем: тести рование алгоритмов стало возможно даже на одной машине без сете вой карты Wi-Fi;

любую собираемую по трафику статистику можно отслеживать в процессе работы соединения;

на моделируемую кар ту по определению не посылаются пакеты от сторонних приложений;

отладка алгоритмов значительно упрощается благодаря возможности доступа к трафику на любом уровне TCP/IP стека.

42 52-я научная конференция МФТИ ФРТК- Секция высокопроизводительных битовой последовательности и т. д., четыре транзитных канала пере дачи данных — для передачи данных с внешних входов ПЭ на его вычислительных систем внешние выходы с программируемой задержкой, равной 0, 1, 2, такта сигнала синхронизации, входной и выходной коммутаторы — для подключения внешних входов и выходов ПЭ к входам и выходам внутренних исполнительных устройств (рис. 1).

УДК 004.272. Д.С. Артамонов dmitry.artamonov@idm.ru Московский государственный институт электронной техники (технический университет) ООО «ИДМ»

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

Таким образом, необходима разработка методов повышения эф фективности вычислений (удельной производительности — произво дительности на единицу площади аппаратуры, отношения производи тельность/потребление) на однородных вычислительных средах по трём направлениям:

1). Разработка архитектуры процессорного элемента и его функ циональности. Разрабатываемый процессорный элемент однородной Рис. 1. Структурная схема процессорного элемента вычислительной среды представляет собой совокупность независи мых устройств, которые предназначены для обработки, хранения и Многофункциональное устройство, в основе функционирования передачи данных [5]. Процессорный элемент включает в себя арифме которого лежат принципы конвейерной последовательно-параллель тико-логическое устройство (АЛУ) — для обработки данных по ариф ной обработки данных, обеспечивает эффективную с точки зрения метическим и логическим операциям, многофункциональное устрой затрачиваемых аппаратных ресурсов и времени вычислений обработ ство (МФУ) — для обработки данных по составным алгоритмам — ку данных различных форматов (8-, 16-, 32-, 64-бит).

умножении, умножение в полях Галуа, деление, поиск совпадений в Секция высокопроизводительных вычислительных систем 43 44 52-я научная конференция МФТИ ФРТК- тельной системы относительно варьируемого диапазона классов об 2). Оптимизация затрат аппаратных ресурсов матрицы вычис рабатываемых алгоритмов.

лительной системы. Вычислительная ячейка однородной вычисли тельной среды может выполнять прямую или альтернативную функ Литература цию из существующего набора функций в зависимости от сигнала 1. Евреинов Э.В. Однородные вычислительные системы, структу условия. Введение поддержки альтернативных вычислений позволя ет снизить аппаратные издержки относительно обрабатываемых ал- ры и среды. — М.: Радио и связь, 1981. — 208 c.

2. Богачев М.П. Архитектура вычислительной системы с однород горитмов, включающих ветвления, в 2 раза (рис. 2). В масштабах мат рицы процессорных элементов такой выигрыш в аппаратных ресур- ной структурой. — Львов: ФМИ АН УССР, 1981. — С. 15–21.

3. Варшавский В.И., Мораховский В.Б. [и др.]. Однородные струк сах позволяет значительно повысить удельную производительность всей системы в целом. туры. — М.: Энергия, 1973. — 150 c.

4. Шмойлов В.И., Русин Б.П., Кузьо М.Н. Ячейка пульсирующих информационных решёток. — Львов: Меркатор, 2001. — 34 с.

5. Процессор однородной вычислительной среды: пат. 2180969, Российская Федерация: МПК7 G06F15/00, G06F15/163/ Бачери ков Г.И., Геворкян В.И., Крохин В.М., Татур В.Ю.;

заявка № 2000126004/09, заявл. 18.10.2000, опубл. 27.03.2002.

УДК 004.4’ В.А. Битнер wilek@mail.ru Московский физико-технический институт (государственный университет) ЗАО «Московский центр SPARC-технологий»

Система интерпретации промежуточного Рис. 2. Аппаратура для реализации алгоритма типа выбор на стандарт ной ячейке (а) и на ячейке, поддерживающей технологию альтерна представления программы тивных вычислений (б) (активные ячейки и связи выделены жирным, неактивные — пунктиром) в оптимизирующем компиляторе 3). Динамическая частичная реконфигурируемость аппаратуры вычислительной системы. Необходимо обеспечить возможность до- Начальным этапом трансляции в оптимизирующем компилято ступа для реконфигурирования к любому индивидуальному ПЭ в ре, созданном и развиваемом для архитектуры «Эльбрус» [1], яв любой момент времени. Такая возможность может быть организова- ляется преобразование исходного кода программы в промежуточное на посредством введения адресации ячеек матрицы вычислительного представление, предназначенное для удобства генерации кода и/или процессора по осям X и Y, а также введения индивидуального управ- проведения различных оптимизаций [2]. Промежуточное представле ляющего сигнала, определяющего режим каждого отдельного ПЭ. ние исходной программы можно интерпретировать как программный Поддержка динамической частичной реконфигурируемости аппа ратуры вычислительной матрицы обуславливает гибкость вычисли Секция высокопроизводительных вычислительных систем 45 46 52-я научная конференция МФТИ ФРТК- зации не приводит к явному её обнаружению, то есть проявляется код, который приводится к машинному коду и исполняется (оно ос только на этапе исполнения программы.

новано на Ассемблере целевой архитектуры, но при этом не является программой на языке Ассемблера).

Литература Принято различать два типа представления исходной программы:

1. Волконский В.Ю. Оптимизирующие компиляторы для архи высокоуровневый, максимально абстрагированный от особенностей конкретной вычислительной архитектуры и предназначенный глав- тектуры с явным параллелизмом команд и аппаратной поддержкой ным образом для межпроцедурных оптимизаций, и низкоуровневый, двоичной совместимости // Информационные технологии и вычисли приближённый к архитектуре некоторой конкретной вычислитель- тельные системы. — 2004. — № 3. — С. 4–26.

2. Ахо А.В., Сети Р., Ульман Д.Д. Компиляторы: принципы, тех ной системы и предназначенный для оптимизаций внутри процеду ры [3]. Данная работа посвящена разработке системы интерпретации нологии и инструменты. — М.: Вильямс. — 2003. — 768 с.

3. Дроздов А.Ю., Степаненков А.М. Методы комбинирования ал промежуточного представления низкоуровневого типа посредством трансляции промежуточного кода в рабочую программную среду, ко- горитмов анализа и оптимизаций в современных оптимизирующих торая обладает необходимыми свойствами надежности, доступности, компиляторах // Компьютеры в учебном процессе. — 2004. — № 11. — удобства использования. Техническая реализация трансляции строит- С. 3–12.

4. Galazin A.B. [et al.]. A Software Instruction Prefetching Method ся на моделировании элементов промежуточного представления Си кодом, выполняемым с сохранением функциональной эквивалентно- in Architectures with Static Scheduling // Programming and Computer сти. Моделируются не только элементы промежуточного представле- Software. — 2008. — V. 34, N. 23. — P. 49–53.

ния, но и аппаратная поддержка исполнения программы на процессо ре с архитектурой «Эльбрус», например, моделирование асинхронной предподкачки массивов данных [4] или процесса использования стека УДК 004. данных. Результатом трансляции промежуточного представления яв А.Ю. Богданов ляется программный код на языке Си, исполняемый на архитектуре x86 и в точности повторяющий функциональность промежуточного bmstupower@gmail.com кода исходной программы.

Московский государственный технический университет Особое внимание в работе уделяется моделированию архитектур им. Н.Э. Баумана ных особенностей, при котором достигаются наиболее простые и эф ЗАО «Московский центр SPARC-технологий»

фективные решения: реальный регистр моделируется как переменная типа int, реальный стек — как массив элементов типа char, вызов Комплексная отладка контроллера процедуры — как инициализация «станка» — указатель типа void — периферийных интерфейсов и вызов по косвенности с использованием средств языка Си и так далее. Общий принцип моделирования основывается на замене всех непереносимых объектов архитектуры «Эльбрус» эквивалентными (в В настоящее время компания ЗАО «МЦСТ» разрабатывает кон смысле функциональности) и операбельными объектами архитекту- троллер периферийных интерфейсов (КПИ). Он предназначается ры x86. для использования в высокопроизводительных системах на кристал В процессе разработки оптимизирующего компилятора архитек- ле с архитектурой «Эльбрус» и поддерживает интерфейсы Ethernet, туры «Эльбрус» система интерпретации промежуточного представ- Sata, IDE, PCI, PCI-Express, USB2.0, AC97, GPIO, IEEE1284, RS232, ления программы актуальна как необходимая основа для создания IOAPIC, PIC, I2C, SPI и IOlink.

нового эффективного отладочного средства. Такое отладочное сред- На первых этапах разработки отладка КПИ проводилась исклю ство будет использоваться для верификации оптимизаций в оптими- чительно программными средствами, реализующими исполнение на зирующем компиляторе, особенно в случаях, когда ошибка в оптими- бора тестов программным модулем, представляющим собой RTL-код Секция высокопроизводительных вычислительных систем 47 48 52-я научная конференция МФТИ ФРТК- на языке Verilog. Такой подход имел существенные недостатки, основ ными из которых были:

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

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

Через шину PCI инструментальная машина посылает запросы к КПИ в виде PCI фрагментов IOLink пакетов запросов и считывает Рис. 1. Функциональная схема макета с тестирующим устройством ответы на ранее поступившие запросы из тестирующего устройства.

Через шину IOLink тестирующее устройство посылает запросы к КПИ и получает ответы на них, которые сохраняются во внешней памяти.

Внешняя память служит для хранения запросов и ответов на них, поступающих в режиме DMA.

Устройство содержит несколько буферов FIFO следующего назна чения:

Memory Controller обеспечивает взаимодействие с внешней памя тью, FIFO APIC хранит приходящие от КПИ прерывания, FIFO Answer накапливает ответы на запросы, FIFO Sequence последовательно буферизует запросы к КПИ, Register содержит регистры статуса и управления, IOLink Controller обеспечивает взаимодействие с IOlink интерфей сом, PCI Сontroller обеспечивает взаимодействие с шиной PCI.

Данное устройство позволило повысить скорость тестирования в 100 раз, появилась возможность проверки работы КПИ при подклю Рис. 2. Функциональная схема тестирующего устройства чении различных устройств (USB, SATA и т. д). Сочетание программ ных и аппаратных средств позволяет добиться наилучших результа тов при отладке устройства (рис. 1, 2).

Литература 1. PCI Local Bus Specication Revision 3.0 // PCI Special Interest Group, 2004.



Pages:   || 2 | 3 | 4 |
 

Похожие работы:





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

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