WWW.KNIGA.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Книги, пособия, учебники, издания, публикации

 

Pages:   || 2 |

«ТРУДЫ 49-Й НАУЧНОЙ КОНФЕРЕНЦИИ МФТИ СОВРЕМЕННЫЕ ПРОБЛЕМЫ ФУНДАМЕНТАЛЬНЫХ И ПРИКЛАДНЫХ НАУК Часть VII УПРАВЛЕНИЕ И ПРИКЛАДНАЯ МТЕМАТИКА 24–25 ноября 2006 года Москва – ...»

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

Министерство образования и наук

и Российской Федерации

Федеральное агентство по образованию

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

Государственное образовательное учреждение

высшего профессионального образования

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

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

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

ТРУДЫ 49-Й НАУЧНОЙ КОНФЕРЕНЦИИ МФТИ

СОВРЕМЕННЫЕ ПРОБЛЕМЫ

ФУНДАМЕНТАЛЬНЫХ И ПРИКЛАДНЫХ НАУК

Часть VII

УПРАВЛЕНИЕ И ПРИКЛАДНАЯ МТЕМАТИКА

24–25 ноября 2006 года Москва – Долгопрудный 49-я научная конференция МФТИ Секция информатики Д.Е. Колесников

ТРЕХМЕРНАЯ СИСТЕМА ВИЗУАЛИЗАЦИИ РЕЗУЛЬТАТОВ ЧИСЛЕННОГО

РЕШЕНИЯ ЗАДАЧ МЕХАНИКИ СПЛОШНЫХ СРЕД

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

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

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

Литература 1. P. J. Schneider, D. H. Eberly “Geometric Tools for Computer Graphics” // Morgan Kaufmann Publishers, 2. Ласло М. «Вычислительная геометрия и компьютерная графика на С++»

// Пер. с англ. – М. «Издательство БИНОМ», 1997 – 304 с.

3. R. J. Rost “OpenGL® Shading Language, Second Edition” // Addison Wesley Professional, 2006 – 800 p.

4. Lorensen, William and Harvey E. Cline., “Marching Cubes: A High Resolution 3D Surface Construction Algorithm” Computer Graphics (SIGGRAPH 87 Proceedings) 21(4) July 1987, p. 163-170) 5. C. Everitt “Interactive Order-Independent Transparency”, NVIDIA OpenGL Applications Engineering 25 Факультет управления и прикладной математики 49-я научная конференция МФТИ Секция информатики Н.Г. Матюшев Московский физико-технический институт (государственный университет)

МОДИФИЦИРОВАННЫЙ МЕТОД МАРКЕРОВ ДЛЯ ЗАДАЧИ

ВОССТАНОВЛЕНИЯ ГРАНИЦЫ РАЗДЕЛА СРЕД.

Проблема восстановления границы сред или описания топологии объектов возникает при исследовании различных динамических процессов в жидкостях и твердых телах. Решение подобной задачи с помощью явного описания границ или деформируемых подвижных сеток затруднительно в случае больших деформаций, турбулентных течений и сложной геометрии объектов. Недавно был предложен гибкий и простой в реализации метод – метод функции уровня [1, 2, 5]. Хранение информации о расстоянии до границы в каждой точке фиксированной расчетной сетки позволяет с легкостью рассчитывать сложные топологические изменения, такие как соударения, слияния и разрывы. Для расчетов используются классические схемы решения нелинейных гиперболических уравнений сохранения.

Метод функции уровня успешно применяется для решения задач гидродинамики и механики сплошных сред. Однако этот метод в чистом виде страдает от «численной диффузии» - потери массы при расчетах в областях с высокой кривизной границы и в длинных узких выступах границы. Также применение этого метода обладает всеми недостатками эйлеровых методов, например жестким ограничением на размер шага по времени. Для решения этих проблем была предложена комбинация с методом маркеров и схемами реинициализации функции уровня [3].

Модифицированный метод функции уровней допускает использование быстрых схем первого порядка точности для расчета движения маркеров и изменения функции уровня и второго порядка для реинициализации. Метод обеспечивает сохранение объема и высокую геометрическую точность по сравнению с методами явного отслеживания границ и методом Volume-Of-Fluid (VOF). При этом сохраняются простота и гибкость метода функции уровня.

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

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

26 Факультет управления и прикладной математики Ниже приведен пример расчета границы в модельной задаче – твердотельное перемещение круга с прямоугольным вырезом по радиусу в однородном и постоянном поле скоростей.

Иллюстрация 1: Сравнение результатов применения модификации с использованием маркеров (справа) 1. Osher, S. and Fedkiw, R., "Level Set Methods: An Overview and Some Recent Results", J. Comput. Phys. 169, 463-502 (2001).

2. Enright, D., Nguyen, D., Gibou, F. and Fedkiw, R., "Using the Particle Level Set Method and a Second Order Accurate Pressure Boundary Condition for Free Surface Flows", Proc. of the 4th ASME-JSME Joint Fluids Eng. Conf., FEDSM2003-45144, edited by M. Kawahashi and A. Ogut and Y. Tsuji, pp. 1-6, Honolulu, HI 2003.

3. Enright, D., Fedkiw, R., Ferziger, J. and Mitchell, I., "A Hybrid Particle Level Set Method for Improved Interface Capturing", J. Comput. Phys. 183, 83-116 (2002).

4. Enright, D., Losasso, F. and Fedkiw, R., "A Fast and Accurate Semi-Lagrangian Particle Level Set Method", Computers and Structures 83, 479-490 (2005).

5. Эффективное решение конвективного уравнения переноса современными численными методами: Методические указания по изучению спецкурса «Решение задач на ЭВМ» / Перм. Ун-т; сост. А.В. Штраубе. - Пермь, 2003. - 28 с.

Н.В. Сурин1, Т.Р. Исходжанов Московский физико-технический институт (государственный университет)

МЕТОД КОМПЕНСАЦИИ ВАРИАЦИИ СЕТЕВОЙ ЗАДЕРЖКИ НА ОСНОВЕ

АДАПТИВНОЙ БУФЕРИЗАЦИИ И ГРАНУЛЯРНОГО СИНТЕЗА

МУЗЫКАЛЬНЫХ ФРАГМЕНТОВ

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

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

Авторами работы был предложен метод гладкой склейки последнего фрагмента звуковой волны с новым фрагментом, синтезированным на основе небольшой части (гранулы) уже воспроизведённой звуковой информации. Выбор наиболее похожего в смысле гладкости склейки фрагмента звуковой волны предлагается осуществлять на основе минимизации дискретного функционала c – номер сэмпла, на котором вызвана процедура восстановления информации при опустошении буфера, Wk – значение дискретной аппроксимации функции звуковой волны на k-м сэмпле, L – длина звукового окна, используемая для нахождения оптимального (в смысле min F(x)) предгранульного фрагмента звука, x – дискретный временной сдвиг (в сэмплах).

В ходе экспериментов было обнаружено, что при гранулярном синтезе звука происходит изменение спектра результирующей звуковой волны. Это связано с конечным размером звукового окна. Для комфортного восприятия однократных и двукратных фрагментов синтеза, длина звукового окна L должна быть не менее 50мс (базовая частота Фурье разложения результирующей звуковой волны не более 20Гц, нижний предел слышимости человеческого уха).

После выбора оптимального значения временного сдвига, происходит линейное кросс-микширование Wk и W’k = Wk-x на протяжении 1-2мс. При накоплении в буфере количества звука, превышающего пороговое значение (около 30мс), происходит временной сдвиг в обратную сторону аналогичным образом, но с кроссмикшированием длительностью около 20мс.

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

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

Реализация метода была встроена в систему музыкальных конференций и прошла успешное внедрение в рамках проекта «Джаз со скоростью света» [4].

1. Markopoulou, A. P. (2003) PhD Dissertation: Assessing the Quality of Multimedia Communications over Internet Backbone Networks. Stanford University, US.

2. Liang, Y. J., Farber, N. & Girod, B. (2001) Adaptive Playout Scheduling Using TimeScale Modification in Packet Voice Communications. Stanford University, US.

3. Сурин Н.В., Воног С.Н., Исходжанов Т.Р., Программный комплекс для исследования поведения основных характеристик сетей на базе протокола IP в условиях непрерывной передачи потоков данных большого объема // Информатика – управление и прикладная математика: Сборник трудов 49-й научной конференции МФТИ, Т. II / МФТИ – М.: 2006.

4. Воног С.Н., Сурин Н.В., Технические особенности реализации крупномасштабных распределенных музыкальных концертов через сеть Интернет на примере инновационного проекта "Джаз со скоростью света" в рамках международного фестиваля "Джаз Коктебель 2006" // Информатика – управление и прикладная математика: Сборник трудов 49-й научной конференции МФТИ, Т. II / МФТИ – 5. L. F. Sun, E. C. Ifeachor. Prediction of perceived Convestional Speech Quality and Effects of Playout Buffer Algorithms. IEEE, Anchorage, USA, May 2003, pp. 1-6.

6. C. S. Perkins. RTP: Audio and Video for the Internet. Addison-Wesley, June 2003.

7. C. Fulton, S. Li, “Delay Jitter First-Order and Second-Order Statistical Functions of General Traffic on High-Speed Multimedia Networks” IEEE/ACM Transactions on Networking, Vol. 6, No. 2, April 1998.

С.Н. Воног1, Н.В. Сурин1, Т.Р. Исходжанов Московский физико-технический институт (государственный университет)

ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ ИССЛЕДОВАНИЯ ПОВЕДЕНИЯ

ОСНОВНЫХ ХАРАКТЕРИСТИК СЕТЕЙ НА БАЗЕ ПРОТОКОЛА IP В

УСЛОВИЯХ НЕПРЕРЫВНОЙ ПЕРЕДАЧИ ПОТОКОВ ДАННЫХ БОЛЬШОГО

ОБЪЕМА.

Авторами создан программный комплекс для измерения основных характеристик IP сети таких как средняя, минимальная и максимальная задержка, средний уровень потери пакетов, средние и максимальные значения всплесков задержки, среднее расстояние между всплесками. Тестирование сети может проводиться в течение неограниченного времени между 2 компьютерами. Возможна эмуляция любого протокола передачи данных по сети IP, а также любой объем потока данных c помощью удобной системы конфигурации. Состояние сети за период тестирования записывается в файл и представляется для дальнейшего анализа в графической форме (см. рис. 1). Второе предназначение программы – эмуляция реальных параметров сети в условиях лабораторной локальной сети. Эмуляция сети может быть определена заданием описанных выше параметров или воспроизведена «запись» состояния реальной сети из файла.

Программа CoreEmulator работает следующим образом: 1) устанавливается соединение с удаленной программой CoreEmulator. При работе в режиме эмуляции сети программы на обоих компьютерах открывают соединение с третьим компьютером, который вносит искусственные задержки или потерю пакетов в соотвествии с «записью» сети или заданными параметрами эмуляции; 2) производится начальная синхронизация часов компьютеров (~1.5с); 3) выполняется моделирование потоков данных тестируемой программы. При этом продолжается периодический процесс синхронизации часов в течение всего времени работы теста; 4) по истечении времени работы теста, указанного при запуске программы, данные о полученных пакетах, сохраняются в файл и программа завершает свою работу.

Основным измеряемым параметром является TripTime (TT) – задержка, вносимая сетью, при передачи пакета от начального до конечного узла маршрута. При отправке пакета в его теле указывается точное время отправки (непосредственно перед копированием в сетевой буфер). На принимающей стороне вычисляется точное время приема и вычитается время, указанное в теле принятого пакета. Порядковый номер, записанный в теле пакета, а также его размер и вычисленная задержка записываются в оперативную память программы. Накопленная информация по завершению работы программы записывается в файл.

Процедура вычисления задержки зависит от точной синхронизации часов на участвующих компьютерах. Отсутствие компенсации рассинхронизации часов приводит к серьезным неточностям в расчетах. Синхронизационные данные содержатся в каждом отправляемом каждой из сторон пакете. В теле синхронизационных данных содержатся: поле №1 - порядковый номер данного пакета;

поле №2 - время последнего принятого пакета по часам удалённого компьютера; поле 30 Факультет управления и прикладной математики №3 - время отправки данного пакета по часам локального компьютера. При получении очередного пакета данных, значение его поля № 3 становится значением поля № 2 для следующего к отправке пакета. В случае получения нового набора синхронизационных данных до отправки следующего пакета, предыдущая информация отбрасывается как устаревшая.

При получении синхронизационных данных, на основании принятых данных и времени их приёма вычисляется, необходимая при расчётах задержки, компенсация рассинхронизации. Значение компенсации, вычисленной по синхронизационным данным индивидуального пакета, обладает статистической ошибкой t (t – период отправки пакетов, 5мс для аудиопотока, 50мс для видеопотока). Для увеличения точности процесса компенсации используется статистический подход – величина компенсации является средним значением последних N индивидуальных значений, таким образом, достигается погрешность в. Увеличивая N, мы можем уменьшить статистическую ошибку до пренебрежимо малых величин.

Погрешность функции вычисления текущего времени, использованной в данной программе, равна ±0,5мс. Также присутствует погрешность, связанная с периодичностью отправки пакетов (из-за невозможности абсолютно непрерывной передачи данных, связанной с физическими ограничениями компьютерного и сетевого оборудования, а также с особенностями используемого протокола). Её величина равна t/2 (t – период отправки пакетов).

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

Рис.1. Графики сетевой задержки при слабой (слева) и сильной (справа) загрузке сети.

1. M. Allman and V. Paxson, “On estimating end-to-end network path properties,” in Proc.

ACM SIGCOMM, Cambridge, MA, 1999, pp.263–276.

2. Q. Li, “Delay characterization and performance control of wide-area networks,” Ph.D.

dissertation, Univ. of Delaware, Newark, May 2000.

31 Факультет управления и прикладной математики С.Н. Воног1, Н.В. Сурин Московский физико-технический институт (государственный университет)

ТЕХНИЧЕСКИЕ ОСОБЕННОСТИ РЕАЛИЗАЦИИ КРУПНОМАСШТАБНЫХ

РАСПРЕДЕЛЕННЫХ МУЗЫКАЛЬНЫХ КОНЦЕРТОВ ЧЕРЕЗ СЕТЬ ИНТЕРНЕТ

НА ПРИМЕРЕ ИННОВАЦИОННОГО ПРОЕКТА «ДЖАЗ СО СКОРОСТЬЮ

СВЕТА» В РАМКАХ МЕЖДУНАРОДНОГО ФЕСТИВАЛЯ «ДЖАЗ КОКТЕБЕЛЬ

2006».

«Джаз со скоростью света» – инновационный проект, который был успешно реализован авторами публикации в рамках фестиваля Джаз Коктебель 2006.

Цель проекта – обеспечить музыкантам и аудитории, находящимся на расстоянии более тысячи километров друг от друга, возможность играть совместно. Музыканты и зрители могли слышать одновременно всех участников концерта, а также видеть их на плазменных и светодиодных экранах. Конфигурация проекта подразумевает полную синхронизацию видео и аудио потоков CD-качества в диапазоне 20-20.000 Гц. Сигнал передавался по сети Интернет в условиях приемлемой задержки 30-100 мс при пропускной способности подключений к сети Интернет до 4 Мбит/с.

Для проведения проекта были оборудованы согласно схеме на рис. 1 пять студий:

в Коктебеле (главная сцена фестиваля), Оксфорде, Москве и Киеве (2 студии). 14- сентября 2006 г. были проведены три распределенных концерта с использованием технологии Musigy Music Conferencing™ через сеть Интернет. В проекте успешно приняли участие музыканты из Бразилии, Канады, США, Великобритании, Финляндии, Израиля, Франции, Швейцарии, Испании, Польши, России, Украины.

Инновационные особенности проекта, позволяющие утверждать о том, что подобный формат мероприятия был реализован впервые в мире [1]: 1) использование реальной сети Интернета, а не Интернет-2. Это означает, что фактически любой пользователь может использовать разработанную технологию в личных целях без применения специальных выделенных каналов; 2) транснациональность задействованных cтудий, расстояния больше 1000 километров; 3) джазовые звезды первых величин, выступающие в рамках ежедневных концертных программ; 4) применение специальной технологии, разработанной авторами, предназначенной для передачи в сети Интернет музыки и видео высокого качества с ультранизкими задержками (от 20 мс для аудио и от 80мс для видео). Именно в этом заключается ее принципиальное отличие от существующих на рынке технологий, специализирующихся на передаче голоса (Skype, IP-телефония и т.д.).

В реализацию проекта были вовлечены четыре крупнейших европейских интернет-оператора, предоставивших организационно-техническую поддержку при испытании и реализации данного проекта: Укртелеком (Украина), TeliaSonera International Carrier (Швеция), Synterra (Россия), Pipex (Великобритания).

32 Факультет управления и прикладной математики Рис. 1. Техническая схема типичного подключения студии «Джаз со скоростью света».

В результате были обеспечены подключения к сети Интернет по студиям со следующими характеристиками: 1) Коктебель – симметричное подключение со скоростью 4 Мбит/с; 2) Москва – последняя миля 10 Мбит/с, симметричное подключение к Интернет со скоростью 4 Мбит/с ; 3) Оксфорд – два симметричных подключения с фактической скоростью 2 Мбит/с каждое; 4) Киев – студия «Бабуин», два симметричных подключения с фактической скоростью 1.6 Мбит/с, студия «МИМ» симметричное подключение со скоростью 4 Мбит/с.

Реально была задействована пропускная способность 1,9Мбит/с (1,6Мбит для аудиопотока и 300кбит/с для видеопотока, качество видео было достаточным для использовавшихся светодиодных и плазменных экранов). Характеристики компьютеров: процессор Intel Pentium D 3,4 ГГц, 1 ГБ оперативной памяти, видеокарты ATI X1800XT 256 MБ, звуковые карты Creative E-MU 1820, ОС Windows XP Pro SP2.

Литература http://www.cim.mcgill.ca/sre/projects/rtnm/history.html 33 Факультет управления и прикладной математики С.А.Опекунов Московский физико-технический институт (государственный университет)

СОЦИАЛЬНЫЕ СЕТИ ОСНОВАННЫЕ НА СУБЪЕКТИВНОМ ДОВЕРИИ.

Большое количество P2P сетей и других коммуникаций в Интернете(Skype, ISQ, Advogado, Moikrug.ru) затрудняют оценку доверия другим пользователям подсети.

Существует несколько стандартных способов защиты от атак или появления нежелательных пользователей[1,2]. Их можно разделить на две группы:

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

«доверия»(некоторого значения характеризирующего отношение между узлами сети)каждым пользователем подсети с учетом мнений его друзей[5,6]. Выпишем три основных правила в такой подсети:

Мнения каждого про своих друзей можно записать в виде графа. Новый пользователь расставляет значения доверия о знакомых и получает данные от своих друзей. Далее, проделав несколько итерационных алгоритмов, у него и остальных появляются окончательные значения доверия. При этом в алгоритме учитывается следующее: 1)чем больше ребер графа отделяют узлы сети, тем меньше они влияют на взаимное доверие; 2)негативное мнение вычисляется раздельно. Таким образом, каждый пользователь получает граф субъективного доверия другим. Каждому узлу графа соответствует пара значений – позитивное и негативное мнение.

Автору удалось показать достаточную стабильность и надежность такой сети.

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

Рассмотрены возможные атаки.

На данный момент алгоритмы реализованы в виде дополнительного модуля для программы интерактивного общения Skype[7]. Сейчас в подсети около пользователей и их число непрерывно растет.

1. S. Buchegger and J. Le Boudec. A robust reputation system for p2p and mobile ad-hoc networks. In Second Workshop on the Economics of Peer-to-Peer Systems, 2004.

2. http://p2pay.net/Theory?v=wwk 3. http://bitchun.org 4. http://www.sims.berkeley.edu:8000/research/conferences/p2pecon/papers/s2moreton.pdf 5. http://krotty.livejournal.com/ 6. http://www.amazon.com/Probability-Causality-AI/lm/R2GX832Q1M6CHV 7. http://sourceforge.net/project/showfiles.php?group_id= УДК 007.52, 004.451, 004. Е.С. Коротков Институт проблем передачи информации РАН

РАСПРЕДЕЛЁННАЯ ОПЕРАЦИОННАЯ СИСТЕМА КАК КОЛЛЕКТИВ

ВЗАИМОДЕЙСТВУЮЩИХ ПОДСИСТЕМ

Операционная система – это программное обеспечение, которое служит для управления ресурсами компьютера и предоставления их программному обеспечению более высокого уровня, т. е. пользовательским программам [3]. Распределённая операционная система представляет собой среду, состоящую из множества таких компьютеров, соединенных сетью, и, соответственно, множества локальных для этих компьютеров операционных систем, которые взаимодействуют друг с другом через сеть [2].

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

В работе выдвигается идея рассмотрения распределенной операционной системы как коллектива локальных операционных систем. Здесь термин «коллектив»

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

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

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

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

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

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

1. Стефанюк В.Л. Локальная организация интеллектуальных систем. – М.:

Физматлит, 2004. – 328 с.

2. Таненбаум Э., Ван Стен М. Распределенные системы. Принципы и парадигмы. – 3. Таненбаум Э. Современные операционные системы. 2-е изд. – СПб.: Питер, 4. Цетлин М.Л. Исследования по теории атоматов и моделированию биологических систем. Изд-во «Наука», М., 1969, 316 с.

5. Варшавский В.И. Коллективное поведение автоматов. Изд-во «Наука», М., 6. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям:

философия, психология, информатика. – М.: Эдиториал УРСС, 2002. – 352 с.

7. Kennedy J., Eberhart R.C. Swarm Intelligence. - Morgan Kaufmann Publishers, 2001, 8. Срагович В.Г. Теория адаптивных систем. Изд-во «Наука», М., 1976, 320 с.

9. Цыпкин Я.З. Основы теории автоматических систем Изд-во «Наука», М., 1977, УДК 004. П. В. Емельянов, Д. В. Лунев Московский физико-технический институт (государственный университет)

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ПРЕДОСТАВЛЕНИЯ ГАРАНТИЙ ВЫДЕЛЕНИЯ

РЕСУРСОВ НА БАЗЕ ЖЕСТКИХ ОГРАНИЧЕНИЙ

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

Нетрудно видеть, что гарантировать выделение группе требуемого объема ресурсов можно всего лишь двумя способами:

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

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

Основная идея подхода заключается в следующем – если группе i требуется гарантировать ri единиц ресурса из R доступных, то для этого необходимо ограничить все остальные группы в системе пределами l j так, чтобы их суммарное ограничение равнялось R ri. Такое условие должно выполняться для любой группы, и чтобы вычислить требуемые пределы для n групп требуется решить следующую систему линейных уравнений:

Решая соответствующее матричное уравнение, нетрудно получить, что величины li вычисляются следующим образом:

где величина s вычисляется так:

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

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

37 Факультет управления и прикладной математики Достоинствами данного подхода являются • возможность использования существующими системами контроля ресурсов без добавления новой функциональности;

• поддержка механизма „разделяемой памяти“;

• возможность работы с NUMA архитектурами.

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

Литература 1. Емельянов П., Савочкин А. Расширение функциональности существующей модели контроля памяти в ядре Linux // Процессы и методы обработки информации. 2005. 77- 2. Emelianov P., Korotaev K. Resource beancounters // Электронный ресурс // http://lwn.net/Articles/197377/ 3. Shailabh Nagar, Rik van Riel, Hubertus Franke, Chandra Seetharaman, Vivek Kashyap, Haoqiang Zheng Improving Linux resource control using CKRM // Proceedings of the Linux Symposium. 2004. V. 38 Факультет управления и прикладной математики Ляховицкий Л. Б.

ОПЫТ ИСПОЛЬЗОВАНИЯ ТЕХНОЛОГИИ РАЗРЕЖЕННЫХ ФАЙЛОВ В

РЕАЛИЗАЦИИ ВИРТУАЛЬНЫХ ДИСКОВ.

Основным интерфейсом, который предоставляют устройства хранения данных, являются операции чтения и записи. Запросы на чтение и запись могут поступать к устройству, например, в виде команды "записать в диапазон секторов с 5-го по 10-й такие-то данные" или "прочитать данные, хранящиеся в секторах с 11-го по 17-й". Это означает, что программы, эмулирующие работу устройства хранения данных, должны такие операции обрабатывать. Чаще всего происходит это следующим образом. Если программа эмулирует жесткий диск размером X гигабайт, то программа вначале создает файл размером в X гигабайт, называемый файлом образа диска, и заполняет его нулями. В дальнейшем, поступившие запросы на чтение/запись программа удовлетворяет следующим образом: она считывает/записывает данные в файл/из файла, согласно диапазону, указанному в запросе.

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

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

Рис.

Работа виртуального диска на основе разреженного файла.

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

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

Другой стороной использования технологии разреженных файлов является пониженная дисковая производительность. Это связано с тем, что одна операция чтения/записи на виртуальном диске может потребовать выполнения нескольких 39 Факультет управления и прикладной математики операций чтения/записи в файл. Однако в нашей реализации, для такой типовой задачи, как компиляция, снижение производительности составляет всего 10-15 %.

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

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

Литература:

1. Jim Gray, Andreas Reuter. Transaction processing: concepts and techniques. // Morgan Kaufman Publishers, Inc., 1993.

40 Факультет управления и прикладной математики УДК 517. П.И. Агапов1, А.В. Васюков Московский физико-технический институт (государственный университет)

КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ БИОМЕХАНИЧЕСКИХ ПРОЦЕССОВ

В ПОКРОВАХ МОЗГА

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

В задаче можно выделить несколько характерных особенностей:

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

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

Большое количество компонентов системы и их сложная геометрия.

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

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

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

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

В качестве опорных схем были выбраны схема Куранта-Изаксона-Риса и схема ЛаксаВендрофа ([2], [6]).

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

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

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

Работа проведена в рамках программы поддержки научных исследований МФТИ компанией SWSoft(www.swsoft.com).

1. Работнов Ю.Н. Механика деформируемого твёрдого тела. – М.: Наука, 2. Магомедов А.М., Холодов А.С. Сеточно-характеристические численные 3. Агапов П.И., Обухов А.С., Петров И.Б., Челноков Ф.Б. Компьютерное моделирование биомеханических процессов сеточно-характеристическим методом. // Управление и обработка информации: модели процессов. Сб. ст.

– М., 2001 и сайт http://www.cs.mipt.ru/index.php?id= 4. Агапов П.И., Петров И.Б., Челноков Ф.Б. Численное исследование задач механики деформируемого твёрдого тела в неоднородных областях интегрирования. // Обработка информации и моделирование. Сб. ст. – М., 2002 и сайт http://www.cs.mipt.ru/index.php?id= 5. Петров И.Б., Холодов А.С. Численное исследование некоторых динамических задач механики деформируемого твёрдого тела сеточнохарактеристическим методом. //Ж. выч. матем. и матем. физ. – 1984 – Т.24, 6. Федоренко Р.П. Введение в вычислительную физику. – М.: Издательство Московского физико-технического института, 42 Факультет управления и прикладной математики А. Ю. Солодовщиков Московский Физико-Технический Институт (государственный университет)

МАСШТАБНЫЙ АНАЛИЗ ОПЕРАТОРОВ ВЫДЕЛЕНИЯ ЭЛЕМЕНТОВ

КОНТУРОВ ИЗОБРАЖЕНИЯ

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

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

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

Одним из наиболее простых способов обнаружения границ пространственных свойств изображения является дифференцирование яркости, как функции пространственных координат. Дискретные градиентные операторы выделения изображения по заданной маске m(i, j ) :

Свертки являются КИХ-фильтрами, импульсные характеристики которых определяются коэффициентами масок. Недостатком является малый размер масок, что приводит к высокой чувствительности операторов к шумам.

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

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

В качестве вейвлет-образующих функций приняты первые восемь функций базиса Карунена-Лоэва из [2], соответствующих функциям Хюккеля[1]:

Функции H j ( x, y ), j = 0..7 обладают свойством локализации границы скачка яркости. По этой причине была рассмотрена следующая система:

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

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

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

Литература 1. Hueckel М., An Operator which Locates Edges in Digitized Pictures // J. Ass. comput.

Match, 18:113-- 125, 2. Солодовщиков А.Ю., Платонов А.К. Исследование метода Карунена-Лоэва // препринт ИПМ РАН №19, 2006, 28 стр.

3. Jun Li, A Wavelet Approach to Edge Detection // Sam Houston State University, 4. И. Добеши, Десять лекций по вейвлетам // Москва-Ижевск, 2004, 464 стр.

И. Т. Кадощук, В. О. Савраева Московский физико-технический институт (государственный университет)

АГРЕГИРОВАНИЕ ЭКСПЕРТНЫХ ОЦЕНОК

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

Широкий класс экспертных оценок во многих прикладных задачах составляют интервальные ЭО. С начала 80-х годов активно развивается интервальная математика [1], как наиболее практически важная часть её — интервальная статистика [2].

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

Так как теория и практика экспертных оценок весьма математизированы, модели поведения экспертов обычно основаны на предположении, что эксперты оценивают интересующий лицо, принимающее решение (ЛПР) параметр с некоторой допустимой вероятностью. Если мнения комиссии экспертов или какой-то ее части признаны согласованными, то каково же итоговое (среднее, общее) мнение комиссии? Некоторые современные методы определения результирующей коллективной ЭО основаны на использовании при обработке экспертной информации мер близости — аналога расстояний между оценками различных экспертов. Прежде всего, это относится к оценкам экспертами сравнительной предпочтительности альтернативных вариантов [3].

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

В работе рассматриваются процедуры оценки длительности/стоимости (time/cost estimation) в управлении проектами. Предположим, что в обоих случаях количество экспертов мало и нельзя рассматривать их оценки как одинаково распределенные случайные величины. Задача состоит в получении корректной интегрированной оценки с некоторой достоверностью.

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

МП должен установить доверительную вероятность (CP) для плана проекта как значение внутри интервала от 0 до 1; чем выше CP, тем ближе предполагаемый интервал к реалистичному интервалу.

• Определить реально осуществимый интервал оценок;

• Определить тип распределения вероятности значений внутри интервала;

• Определить вероятность применения прогноза.

Если задачи взаимосвязаны, МП должен складывать (или умножать) предполагаемые значения.

Например, МП складывает все предполагаемые длительности задач критического пути, чтобы определить минимальную длительность проекта.

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

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

1. МП консультируется в оценке длительности/ ресурсов проекта с некоторым числом n 1 экспертов.

2. Каждый эксперт имеет определенные оценки для большинства задач в проектном разбиении работ.

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

Выделим два возможных случая: (1) оцениваемые значения независимы и (2) оцениваемые значения — зависимые величины1.

(1) Независимые величины Шаги алгоритма:

• МП получает от экспертов оценки границ a и b и соответствующий тип распределения;

• МП вычисляет средние значения и дисперсии;

• МП вычисляет сумму средних значений и сумму дисперсий;

• МП вычисляет границы.

(2) Зависимые величины Шаги алгоритма:

• МП получает от экспертов оценки границ aj и bj и соответствующие типы распределений;

• МП вычисляет для каждой оценки эксперта доверительную вероятность:

МП вычисляет значение границ предполагаемого интервала для оценки каждого эксперта;

МП вычисляет границы предполагаемого интервала как сумму границ полученных интервалов.

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

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

Например, в случае оценки экспертом длительности работы (V hours) и числа человек для выполнения задачи (W people) МП должен определить стоимость (man – hours) для задачи как C = V * W.

Определение возможного наилучшего решения (для наиболее узкого предполагаемого интервала) состоит в следующем алгоритме:

• Определить средние значения и дисперсии для каждого распределения;

• Определить среднее значение произведения C как произведение средних значений;

• Определить дисперсию произведения как:

• Определить предполагаемые границы интервала произведения C как M C ± z, где z – нормированное отклонение.

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

Данный метод рассматривается как эмпирический, так как вводится допущение, что кто-то из экспертов знает правду об истинном значении.

Пусть есть мнения нескольких экспертов. Чтобы определить итоговое (среднее, общее) мнение группы экспертов, следует найти среднее мнение как решение оптимизационной задачи. А именно, надо минимизировать суммарное расстояние от «кандидата в средние» до мнений экспертов. Найденное таким способом среднее мнение называют "медианой Кемени".

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

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

Заключение.

В результате проделанной работы найдены решения задачи агрегирования экспертных оценок при ограничении на число экспертов • Для суммы зависимых и независимых случайных величин;

• Для произведения случайных величин.

1. Шокин Ю. И. Интервальный анализ // Н.: Наука, Сибирское отделение, 1981. –– 112 с.

2. Orlov A. I. Interval computations. 1992. No.1 (3), P.44-52.

3. Литвак Б. Г. Экспертные технологии в управлении // М.: Дело, 2004.

УДК 517. Феоктистов М.С. Международный университет «Дубна» (государственный университет)

ЗАГРУЗЧИК ДРАЙВЕРОВ ДЛЯ ВИРТУАЛЬНОГО ОКРУЖЕНИЯ ОС WINDOWS

2000/XP/SERVER В работе виртуальной системы часто возникает ситуация когда приложения загружают в свое виртуальное окружение по сути одинаковые драйвера. При использовании штатного алгоритма загрузки в ОС Windows 5.x для каждого драйвера будет выделена своя физическая память и место в файле подкачки. Если взять драйвер размером 5 Кб, который имеет 100 своих клонов, то получим 500 Мб физической памяти занятой по сути одним драйвером. Замечу, что в виртуальных системах таких драйверов может быть огромное количество.

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

Проект состоит из двух модулей. Один расположен в пользовательском режиме.

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

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

Механизм разделения секций драйверов реализуется за счет модифицирования штатного алгоритма загрузки. В модуле ядра загрузчика находятся функции ОС переписанные с учетом возможности разделения при загрузке. Сам алгоритм построен на подмене физических адресов и слежении за загруженными страницами. Реализован учет драйверов совместно использующих страницы физической памяти. Проделана работа по изучению и документированию штатных функций ядра для загрузки и выгрузки драйверов. Разработка ведется с использованием исходных кодов ОС Windows 2003 Server, распространяемых по лицензии Microsoft. [5] 48 Факультет управления и прикладной математики Рис. 1 Результат работы загрузчика драйверов для виртуального окружения Литература 1. IA-32 Intel Architecture Software Developer’s Manual Volume 3:System Programming Guide.

2. М. Руссинович, Д. Соломон «Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000» // Мастер-класс. 4-е изд. – М.:

Издательско-торговый дом «Русская редакция»; СПб.: Питер; 2005. – 992 стр.

3. Г. Неббет «Справочник по базовым функция API Windows NT/2000» М.:

Издательский дом «Вильямс», 2002. – 528 с.

4. Sven B. Schreiber «Undocumented Windows 2000 secrets: a programmer's cookbook»

Second printing, July 2001, Addison-Wesley ISB 0-201-72187- 5. Windows Research Kernel (WRK) http://www.microsoft.com/resources/sharedsource/Licensing/researchkernel.mspx 49 Факультет управления и прикладной математики Прокопенко А.С., Тарасов В.Н.

Московский физико-технический институт (государственный университет)

ПЕРСПЕКТИВЫ ПРИМЕНЕНИЯ СТРУКТУР НЕ ТРЕБУЮЩИХ

СИНХРОНИЗАЦИИ ПРИ ПАРАЛЛЕЛЬНОМ ДОСТУПЕ

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

При параллельном исполнении кода возникает проблема синхронизации. Для решения этой проблемы применяются классические алгоритмы синхронизации: семафоры, mutex, spin lock и другие. Такие алгоритмы приемлемы пока количество процессов одновременно выполняющихся в системе не велико, а в связи с вышеуказанными тенденциями это условие выполняется все реже. Поэтому в данный момент проводятся интенсивные исследования в области структур не требующих синхронизации при параллельном доступе (non-blocking structures, далее NBS). Типичным примером такой структуры является транзакционная память.

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

Авторами в качестве примера были рассмотрены наиболее распространенные архитектуры: x86 и x64. На этих архитектурах выделены минимальные наборы команд и с их помощью реализован небольшой тестовый алгоритм: с использованием семафоров и с использованием NBS на основе транзакционной памяти. Построенная таким образом математическая модель позволила сравнить производительности NBS и классических алгоритмов. Важным параметром данной математической модели является паттерн нагрузки: в зависимости от него преимущество имеет тот или иной алгоритм.

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

1. McRT-Malloc – A Scalable Transactional Memory Allocator, Proceedings of the 2006 international symposium on Memory management, Richard L. Hudson, Bratin Sah, Ali-Reza Adl-Tabatabai, Benjamin C. Hertzberg.

2. Non-blocking Synchronization and System Design, Ph.D. Thesis, M. Greenwald.

3. A Hight Performance Software Transactional Memory System For A Multi-Core Tuntime, Proceedings of the Principles and Practice of Parallel Programming, Saha B., Ali-Reza Adl-Tabatabai, Richard L. Hudson, Benjamin C. Hertzberg.

4. Intel Architecture Software Developer’s Manual, Volume 1-3.

5. AMD64 Architecture Programmer's Manual Volume 1-3.

50 Факультет управления и прикладной математики А. А. Жданов1, А. А. Танцуев Институт системного программирования РАН

АУТЕНТИФИКАЦИЯ ПОЛЬЗОВАТЕЛЯ, ОСНОВАННАЯ НА ОБРАБОТКЕ

ДИНАМИКИ МАНИПУЛЯТОРОВ

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

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

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

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

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

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

Литература 1. Philippe Zimmermann, Sissel Guttormsen, Brigitta Danuser, Patrick Gomez. Affective Computing - A Rationale for Measuring Mood with Mouse and Keyboard. - Swiss Federal Institute of Technology, 2003.

2. -Florida. Mueller, Andrea Lockerd. Cheese: Tracking Mouse Movement Activity Websites, a Tool for User Modeling. - MIT Media Lab, 2001.

3. Maja Pusara, Carla E. Brodley. User ReAuthentication via Mouse Movements. - School Electrical and Computer Engineering Purdue University, Departn\ent of Computer Science Tufts University 1999.

4. Hugo Gamboa, Ana Fred. An Identity Authentication System Based On Human Computer Interaction Behaviour // Lecture Notes in Computer Science 2003. V. 246. P. 2652.

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

МОДЕЛИРОВАНИЕ РАЗРУШЕНИЯ СТЕКЛА ПРИ ДИНАМИЧЕСКИХ

НАГРУЗКАХ

НА ПРЯМОУГОЛЬНЫХ СЕТКАХ

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

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

В настоящей работе рассматриваются особенности численной реализации задачи о двумерной фрагментации бесконечно толстого слоя стекла под действием динамической нагрузки с учетом вероятностного характера процесса дробления Исследовался круглый образец стекла ( = 2500 г/см3, vs = 4900м/с, E = 6,87·1010 Па) с вырезом в центре, на внутренней поверхности которого в начальный момент времени задавалось напряжение. Нагрузка имела характерную базовую часть (полтора предела прочности материала), дополнительно к которой случайным образом задавалось 0–50% от базовой части (подобным формировалась неоднородность исходного материала). В итоге, в начальный момент времени в отдельных точках на свободной границе нагрузка могла превышать 2 предела прочности стекла.

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

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

52 Факультет управления и прикладной математики Трещины в стекле при различной мелкости сетки, указано число точек на внутренней 53 Факультет управления и прикладной математики 1. Новацкий В.К. Теория упругости. — М.: Мир, 1975.

2. Майчен Дж., Сак. С. Метод расчета «Тензор» // Вычислительные модели в гидродинамике — М.: Мир, 1967. С. 185-211.

3. Магомедов К.М., Холодов А.С. Сеточно-характеристические численные методы.

4. Петров КБ., Холодов А.С. Численное исследование некоторых динамических задач механики деформируемого твердого тела сеточно-характериетическим методом // Журнал вычислительной математики и математической физики, 1969.

5. Белоцерковский О.М. Численное моделирование в механике сплошных сред — М.:

6. Броек Д. Основы механики разрушения — М.: Высшая школа, 1980.

54 Факультет управления и прикладной математики УДК 517. В.Н. Петров1, Н.В. Заборовский Московский физико-технический институт (государственный университет)

РАЗРАБОТКА И РЕАЛИЗАЦИЯ ТЕХНОЛОГИИ ШАБЛОННОГО ХРАНЕНИЯ

ДАННЫХ А РЕЕСТРЕ WINDOWS.

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

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

В данной работе предлагается механизм хранения данных без избыточности:

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

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

Реализована соответствующая функциональность пользовательского уровня, присущая реестру Windows: создание и удаление ключей и значений, перечисление ключей и значений, чтение и запись информации о ключе, установка значений и т.д.

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

1. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000, Д. Соломон, М. Руссинович четвёртое издание.

2. Windows Kernel Internals NT Registry Implementation, David B. Probert, Ph.D., Windows Kernel Development, Microsoft Corporation 3. Microsoft Windows XP Registry Guide, Jerry Honeycutt 4. Managing the Windows 2000 Registry, Paul Robicbaux 55 Факультет управления и прикладной математики Петров В.А.

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

ОСОБЕННОСТИ ПОИСКА В РАСПРЕДЕЛЕННОЙ СИСТЕМЕ С РЕГУЛЯРНОЙ

СТРУКТУРОЙ.

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

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

Главным вопросом доставке информации является поиск ее местонахождения.

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

Данная работа проводится в рамках создания распределенной системы Torfs[1].

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

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

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

Примером регулярной структуры распределенной системы может служить двухмерная решетка (Рис. 1).

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

• Вычислить количество путей из одной точки в другую.

• Ввести ограничения на длины путей (количество пересекаемых данным путем узлов): они могут отличаться друг от друга только на четное число, т. е.

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

• Вычислить количество путей из одной точки в другую.

• Ввести ограничения на длины путей (количество пересекаемых данным путем узлов): они могут отличаться друг от друга только на четное число, т. е.

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

Литература:

1. Хасин М.А. «Модель распределенного хранилища в глобальной сети», кандидатская диссертация, кафедра информатики, 2001 год.

2. Петров В.А., Тормасов А.Г. «Доставка информации пользователю в распределенных системах», сборник Лобанова.

57 Факультет управления и прикладной математики УДК 519. Е.И. Нижник Московский физико-технический институт (государственный университет)

ОЦЕНКА ПАРАМЕТРОВ В ПРОГНОЗИРУЮЩЕЙ МОДЕЛИ ТЕСТИРОВАНИЯ

ПРОИЗВОДИТЕЛЬНОСТИ ФАЙЛОВЫХ СИСТЕМ

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

Реализация прогнозирующей модели выглядит следующим образом:

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

3. Нахождение такого диапазона параметров нагрузки x, при котором приближение работает. В случае выхода за границы диапазона необходимо изменить выбранное приближение, т.е. повторить шаги 1-3 с другими Набор полученных приближений f и диапазонов значений x даст возможность вычислять производительность ФС, не осуществляя непосредственного тестирования ФС в условиях нагрузки, интересующей пользователя. Понятно, что применимость такого подхода напрямую зависит от охваченных значений нагрузки.

Простейшая реализация прогнозирующей модели была выполнена для нагрузки web-сервера Microsoft Internet Information Server (IIS) 5.1 на файловой системе NTFS. В качестве параметров нагрузки были выбраны следующие характеристики: общий объем данных, расположенных на сервере, средний размер запрашиваемых файлов, а также количество параллельных соединений. Характеристикой производительности послужила скорость отправки данных клиенту.

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

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

Кроме того, полученная модель применима лишь для тестирования web-серверов, а потому не даст результатов для других типов нагрузки. Дальнейшее исследование будет направлено на поиск более низкоуровневого базиса x, который позволил бы, во-первых, представлять унифицированной форме и, вовторых, более точно аппроксимировать f(x).

1. Руссинович М., Соломон Д. Внутреннее устройство Microsoft Windows: Windows Server 2003, Windows XP и Windows 2000. Мастер-класс. Пер. с англ. – 4-е изд. – М.: Издательско-торговый дом «Русская Редакция»; СПб.: Питер; 2005. – 992 с.:

2. Smith K.A. Workload-Specific File System Benchmark [Электронный ресурс] – Режим дост.: http://eecs.harvard.edu/~syrah/filesystems/papers/keith_a_smith_thesis.pdf 3. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений/ Ю.В. Линник – Л., Физматгиз, 1962г., 352 стр с УДК 517. М.А. Копелев1, В.В. Шейнин Московский физико-технический институт (государственный университет)

РАСПРЕДЕЛЕНИЕ НАГРУЗКИ ПРОЦЕССОРОВ МЕЖДУ НИТЯМИ В

МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ

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

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

Работа проведена в рамках программы поддержки научных исследований МФТИ компанией SWsoft (www.swsoft.com).

1. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000 // Пер.

с англ. – СПб.: Питер; М.: Издательско-торговый дом «Русская редакция», 2004. – 2. Современные операционные системы. 2-е изд. // Таненбаум Э. – СПб.: Питер, 2004.

60 Факультет управления и прикладной математики УДК 517. Шувалов П.В., Тормасов А.Г. Московский физико-технический институт (государственный университет)

РАЗДЕЛЯЕМЫЕ ФАЙЛОВЫЕ СИСТЕМЫ В ВИРТУАЛЬНОЙ МАШИНЕ XEN

Виртуальная машина XEN позволяет создавать изолированные друг от друга домены. Прямой доступ к физическим ресурсам имеет только привелигерованный домен. В непривелигерованном (гостевом) домене драйвера физических устройств заменеы на драйвера XEN, называемые frontend драйверами. Если пользовательская программа запрашивает ресурс, то начинается сложная процедура междоменного взаимодействия с backend драйвером в привелигерованном домене, который передает frontend драйверу нужные данные.

Операционная система Linux предоставляет всем пользовательским программам единый интерфейс, называемый Virtual File System(VFS), для доступа к различным файловым системам. Пользовательские программы используют стандартные команды ввода вывода(write(), read() и т.д.). Ядро перенаправляет эти команды драйверу конкретной файловой системы, который выполняет требуемую низкоуровневую операцию. Таким обрзом, драйвер файловой системы должен выполнять стандартные команды VFS применительно к конкретной файловой системе.

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

Когда запускается новый домен, xend посылает сообщение BLKIF_BE_CREATE для backend посредством Control rings. Backend подготавливает структуры для этого домена и отсылает назад сообщение STATUS_OK. Далее xend для каждого устаройства посылает сообщения BLKIF_BE_VBD_CREATE и BLKIF_BE_VBD_GROW для backend в котором передает информацию об экспортируемом устройстве. После этого запускается гостевой домен и в итоге frontend драйвер.Далее frontend посылает xend сообщение BLKIF_FE_DRIVER_STATUS_CHANGED, которое означает, что можно INTERFACE_STATUS_CHANGED, после которого frontend выделяет общую BLKIF_INTERFACE_CONNECT в котором содержится адрес blk_ring. Xend посылает backend сообщение BLKIF_BE_CONNECT, после чего backend запоминает адрес общей страницы и создает в гостевом домене прерывание для использования event channel`а. Xend отправляет frontend сообщение INTERFACE_STATUS_CHANGED которое сообщает ему, что event channel создан. Далее идет обмен данными при помощи общей страницы памяти и event cahnell`а.

В операционной системе Linux данные, которые задействованны в операциях ввода-вывода хранятся в памяти(page cache). При первичном обращении данные с диска копируются в память и добавляются в inode cache. Если потом данные требуются опять, то они берутся из кэша, а не снова считываются, что сильно ускоряет работу с устройством. Однако, при использовании такого механизма в виртуальной машине возникают трудности. Каждая виртуальная машина должна иметь свой кэш для хранения используемых данных. Это сказывается на общей производительности. Кроме того, blkif не позволяет использовать одну систему в режиме read-write. Изменения сделанные в одном домене отображаются в кэше, расположенном в изолированной памяти этого домена, другие домены не будут о них ничего знать до момента синхронизации.

61 Факультет управления и прикладной математики Как вариант можно использавать Network File System для когерентного доступа к файлам. Но более производительный выход из этой ситуации может быть таким. Кэш, в котором хранятся данные нужно располложить не в памяти гостевого домена, а в памяти привелигерованного. В качестве примера реализации такой схемы можно рассмотреть проект XenFS, созданный Марком Уильямсоном(Mark Williamson). Этот проект развивается в течении двух лет, и через некоторое время будет включен в stable релиз XEN.

1. Love R. Linux Kernel Development. 2005. Chapter 12.

2. Williamson M. First Year PhD Proposal. July,2005. Chapter about XenFS.

http://www.cambridge.intel-research.net/~mwilli2/report_final.pdf 3. Xen 3.0.2 doucumentation about blkif.

62 Факультет управления и прикладной математики УДК 681. А.C. Лялин Московский физико-технический институт (государственный университет)

АЛГОРИТМИЧЕСКИЙ АНАЛИЗ ДЛЯ ПРОЕКТИРОВАНИЯ ЦИФРОВОЙ

АППАРАТУРЫ: АВТОМАТИЧЕСКИЙ ПОДХОД

Основной задачей компиляции является разложение алгоритма, заданного своей программой, по аппаратным ресурсам конкретного процессора. Программа при этом разделяется на управляющую структуру (CFG, в русской литературе чаще называется как Логическая Структура Алгоритма-ЛСА) и структуру взаимодействия над данными (DFG, в русской литературе чаще называется как Информационная Структура Алгоритма-ИСА). Анализируя структурное описание программы в виде графов, компилятор раскладывает алгоритм по ресурсам процессора. Аналогичная схема используется в этой работе для реализации алгоритма в виде аппаратной или программно-аппаратной системы. В качестве инструмента, который использовался для получения структуры программы использовался программный комплекс SPARK FRAMEWORK [1]. При SPARK-компиляции программа представляется в виде CDFG графа (CFG+DFG), описанного в специальном формате dotty. Для данного формата файлов существуют инструменты просмотра (пакет Graphviz [2]), к нему также существуют модуль Perl, с помощью которого из dotty-файла формируется программная структура графа программы. На основании этой структуры в представленной методологии проводятся автоматические алгоритмические преобразования на основании специальных сценариев аппаратного планирования.

В настоящее время апробирован технологический маршрут рис.1. У программного комплекса SPARK есть ограничения на Си-описание алгоритма: все указатели массивов должны быть заменены действительными элементами массива. Кроме того, из программы алгоритма должны быть исключены все системные вызовы [1]. Поэтому изначальный текст программы, описывающий алгоритм, изменяется (преобразуется в “аппаратный” Си) – и для проверки компилируется и моделируется при тех же внешних условиях, что и изначальная программа. Для исследований использовался описанный на Си++ стандарт JPEG2000 [3]. Для аппаратной реализации было выбрано вейвлет-преобразование. Полученный “аппаратный” Си вейвлет-преобразования был включён в JPEG2000 и была проверена работоспособность на фото-изображениях.

Далее “аппаратный” Си был скомпиллирован программным комплексом Spark, в 63 Факультет управления и прикладной математики результате чего был получен CDFG-граф программы. На основании CDFG-графа было сформировано SystemC описание аппаратуры.

Рис.11 Технологический маршрут для аппаратной реализации Waveletпреобразования В данный момент реализуются сценарии алгоритмических преобразований типа [4, 5] на языке Perl, основанием для алгоритмического анализа является CDFG-структура программы. Исследования в этом направлении поддерживаются грантом РФФИ № 05Литература 1. Spark Website. SPARK parallelizing high-level synthesis framework website.

http://mesl.ucsd.edu/spark 2. Graphviz Website. Graph Visualization Software. http://www.graphviz.org http://www.tele.ucl.ac.be/PROJECTS/OPENJPEG/ 4. Лялин А.С. Информационная технология “От алгоритма к аппаратуре” на примере аппаратной реализации БПФ// Сборник научный трудов “Моделирование процессов управления”, М.: МФТИ - 5. Лялин А.С. Алгоритмический анализ как основа оптимизации для реализации энергосберегающих вычислений. // Сборник трудов 11-й Байкальской Конфернции “Информационные и математические технологии в научных исследованиях” Иркутск, ИСЭМ СО РАН – 64 Факультет управления и прикладной математики К.Д.Ватев Московский физико-технический институт (государственный университет)

ВЕРОЯТНОСТНЫЕ ОЦЕНКИ ПОВЫШЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ В

РАСПРЕДЕЛЕННОЙ ФАЙЛОВОЙ СИСТЕМЕ LUSTREFS ПУТЕМ ВНЕДРЕНИЯ

(N,K)-СХЕМЫ.

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

Распределенная файловая система, исходя из названия, это файловая система, распределенная на некотором множестве компьютеров, т.е. данные которой находятся на некотором множестве компьютеров, соединенных какой-либо сетью [2].

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

Существует параллельная масштабируемая распределенная файловая система LustreFS ([3],[4],[5]). Система заявлена поддерживающей posix стандарт. Система широко используется различными организациями как компонент – распределенная файловая система (среди примеров – HP StorageWorks SFS, Cray XT3 и XD суперкомпьютеры).

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

В работе доработан дизайн LustreFS, что обусловлено внедрением (n, k ) -схемы, чтобы повысить отказоустойчивость и понизить требования к оборудованию. В работе так же посчитана вероятность отказа в рамках приведенной математической модели системы.

Дизайн предполагает, что каждый блок файла разбивается на n кусков и записывается на разные компьютеры файловой системы, при этом если k из них будут доступны, то блок можно будет прочесть. Всего компьютеров – N.

65 Факультет управления и прикладной математики В математической модели конфигурация задается как ( N, n, k, p ), где p – вероятность того, что компьютер не работает в некоторый момент времени (p не зависит от времени и от компьютера).

В работе выводится приближенная формула для вероятности отказа файловой системы в течении заданного промежутка времени при определенных условиях на числа ( N, n, k, p ) (расчет отказоустойчивой работы для рейд-массивов сделан в работе [1]), а так же на кол-во файлов и некоторые другие параметры.

Литература 1. "A Case for Redundant Arrays of Inexpensive Disks (RAID)". David A. Patterson, Garth Gibson and Randy H. Katz, International Conference on Management Proceedings of the 1988 ACM SIGMOD international conference on Management of data table of contents; Chicago, Illinois, United States; Pages: 109 – 116, Year of Publication: 2. H. Sturgess, J. Mitchell, and J. Isreal, "Issues in the Design and Use of Distributed File System", ACM SIGOPS Operating Systems Review, Volume 14, Issue 3 (July 1980) table of contents; Pages: 55 – 69, Year of Publication: 3. Lustre 1.6 manual (draft 1.1), Cluster File Systems Inc., 2 Dec 4. Lustretm: "A how-to guide for installing and configuring Lustre 1.4.1", May 2005, Oak Ridge National Laboratory 5. Cluster File System, Inc., "Lustre: A Scalable, High Performance File System." Super computing 2003, Phoenix, Arizona, 17 Nov Вагин А.С., Тормасов А.Г.

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

РАСЧЕТ СКОРОСТИ ОТКАЗОУСТОЙЧИВОГО РАСПРЕДЕЛЕННОГО

БЛОЧНОГО ХРАНИЛИЩА.



Pages:   || 2 |
 





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

«СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ 2 КРАТКИЙ ИСТОРИЧЕСКИЙ ОЧЕРК 3 Введение 4 Начальный период радиофизических исследований в БГУ 6 Подготовка специалистов по радиофизике и электронике 7 Открытие факультета.Годы самостоятельной деятельности 12 ФАКУЛЬТЕТ СЕГОДНЯ 21 Деканат, структура факультета, кадры 22 Учебный процесс 24 Научно-инновационная деятельность 27 Сотрудничество 33 Студенческая жизнь 35 КАФЕДРЫ Кафедра радиофизики и цифровых медиатехнологий...»

«1. Титульный лист (скан-копия) 2. Технологическая карта дисциплины Информатика 2.1. Общие сведения о дисциплине. Название дисциплины – Информатика Факультет, на котором преподается данная дисциплина – математический Направление подготовки – Информационные системы и технологии Квалификация (степень) выпускника – бакалавр Цикл дисциплин – естественно-научный Часть цикла – базовая Курс – 1 Семестры – 1 Всего зачетных единиц – 5 Всего часов – 180 Аудиторные занятия 90 часов (из них лекции – 36...»

«Национальная академия наук Беларуси Совет молодых ученых НАН Беларуси Информационно-организационный студенческий научный отдел ПЕРВЫЙ ШАГ В НАУКУ – 2007 СБОРНИК МАТЕРИАЛОВ МЕЖДУНАРОДНОГО ФОРУМА СТУДЕНЧЕСКОЙ И УЧАЩЕЙСЯ МОЛОДЕЖИ К I СЪЕЗДУ УЧЕНЫХ РЕСПУБЛИКИ БЕЛАРУСЬ Том I Минск 2009 Р е д а к ц и о н н а я г р у п п а: Н.М. Писарчук, В.В. Казбанов, А.В. Степуленок, В.В. Осипчик, А.О. Тарасик, А.А. Русак, А.И. Линник, Ю.И. Линник, И.А. Августинович, Д.В. Куницкий, С.Н. Мартынюк, Т.В. Студнева,...»

«152 Евсеенко Александр Васильевич Унтура Галина Афанасьевна доктор экономических наук, доктор экономических наук, профессор,ведущий научный Институт экономики и организации сотрудник Института экономи- промышленного производства ки и организации промышленного СО РАН. производства СО РАН. untura@ieie.nsc.ru evseenko@ieie.nsc.ru ИННОВАЦИОННАЯ ЭКОНОМИКА СИБИРИ1 Формирование инновационного сектора экономики Сибири Инновационный сектор экономики формируется в результате функционирования...»

«№ 8(26) АВГУСТ 2011 В НОМЕРЕ: Новости: Международный авиакосмический салон МАКС-2011 2 Жаркое небо 1941 года. 4 Новости Концерна и отрасли 5 Актуальное интервью: Дизайн-центр 6 Быть в курсе: Пособия по новому 7 Вакансии ННИИРТ на сентябрь 7 Чтобы у каждого был дом 8 О нововведениях в области автоматизации и информатизации IT 9 Страницы истории: Наш славный главный инженер 10 За проходной: В гармонии с природой 12 Туристический слет попытка номер два 14 Поздравляем Вас: Поздравление с 90-летием...»

«УДК 004.432 ББК 22.1 Х27 Хахаев И. А. Х27 Практикум по алгоритмизации и программированию на Python: / И. А. Хахаев М. : Альт Линукс, 2010. 126 с. : ил. (Библиотека ALT Linux). ISBN 978-5-905167-02-7 Учебно-методический комплекс Практикум по алгоритмизации и программированию на Python предназначен для начального знакомства с основными алгоритмами и с программированием на языке Python в интегрированных средах разработки (IDE) Geany и Eric. Комплекс состоит из учебного пособия, в котором...»

«Сведения об авторе. Сведения о дисциплине Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики Евразийский открытый институт М.С. Каменецкая Международное частное право Учебно-практическое пособие Москва 2007 Международное частное право УДК - 341 ББК – 67.412.2 К – 181 Каменецкая М.С. МЕЖДУНАРОДНОЕ ЧАСТНОЕ ПРАВО: Учебно-практическое пособие. – М.: Изд. центр ЕАОИ, 2007. – 306 с. © Каменецкая М.С., 2007 © Евразийский открытый...»

«Министерство образования и наук и Российской Федерации Ярославский государственный университет им. П. Г. Демидова Сборник аннотаций курсовых и квалификационных работ математического факультета Ярославль 2012 Сборник аннотаций курсовых и квалификационных работ математического факультета. Яросл. гос. ун-т им. П. Г. Демидова. Ярославль: ЯрГУ, 2012. Сборник содержит аннотации курсовых и квалификационных работ студентов и магистрантов математического факультета Ярославского государственного...»

«Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ РУКОВОДЯЩИЙ РД ПГУТИ ДОКУМЕНТ 2.64.7-2013 Система управления качеством образования ПОРЯДОК ПЕРЕВОДА, ОТЧИСЛЕНИЯ И ВОССТАНОВЛЕНИЯ СТУДЕНТОВ В ПГУТИ Положение Самара 2013 РД ПГУТИ 2.64.7 – 2013 ПОРЯДОК ПЕРЕВОДА, ОТЧИСЛЕНИЯ И ВОССТАНОВЛЕНИЯ СТУДЕНТОВ В ПГУТИ Положение Предисловие 1 РАЗРАБОТАН Отделом качества образования ПГУТИ...»

«Теоретические, организационные, учебно-методические и правовые проблемы ПРАВОВЫЕ ПРОБЛЕМЫ ИНФОРМАТИЗАЦИИ И ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ Д.ю.н., профессор А.В.Морозов, Т.А.Полякова (Департамент правовой информатизации и научнотехнического обеспечения Минюста России) Развитие общества в настоящее время характеризуется возрастающей ролью информационной сферы. В Окинавской Хартии Глобального информационного Общества, подписанной главами “восьмерки” 22 июля 2000 г., государства провозглашают...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное образовательное учреждение высшего профессионального образования КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ У ЧЕБНО- М ЕТ ОДИЧЕ СКИЙ КОМ ПЛЕКС по дисциплине Информатика Код и направление 111801 - Ветеринария подготовки Профиль 111801.65 - Ветеринария подготовки Квалификация Специалист ветеринарии (степень) выпускника прикладная информатика Факультет Ведущий Анищик Татьяна Алексеевна преподаватель кафедра...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра математического анализа и моделирования УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ Теория вероятностей и математическая статистика Основной образовательной программы по специальности 160400.65–Проектирование, производство и эксплуатация ракет и ракетно-космических комплексов Благовещенск 2012 г....»

«Информатика. 11 класс. Вариант ИНФ10101 2 Инструкция по выполнению работы Тренировочная работа № 1 На выполнение работы по информатике и ИКТ отводится 235 минут. Работа состоит из 3 частей, содержащих 32 задания. Рекомендуем не более по ИНФОРМАТИКЕ 1,5 часов (90 минут) отвести на выполнение заданий частей 1 и 2, а остальное время – на часть 3. 8 октября 2013 года Часть 1 содержит 13 заданий (А1–А13). К каждому заданию даётся четыре варианта ответа, из которых только один правильный 11 класс...»

«Серия ЕстЕствЕнныЕ науки № 1 (5) Издается с 2008 года Выходит 2 раза в год Москва 2010 Scientific Journal natural ScienceS № 1 (5) Published since 2008 Appears Twice a Year Moscow 2010 редакционный совет: Рябов В.В. ректор МГПУ, доктор исторических наук, профессор Председатель Атанасян С.Л. проректор по учебной работе МГПУ, кандидат физико-математических наук, профессор Геворкян Е.Н. проректор по научной работе МГПУ, доктор экономических наук, профессор Русецкая М.Н. проректор по инновационной...»

«СБОРНИК РАБОЧИХ ПРОГРАММ Профиль бакалавриата : Математическое и программное обеспечение вычислительных машин и компьютерных сетей Содержание Страница Б.1.1 Иностранный язык 2 Б.1.2 История 18 Б.1.3 Философия 36 Б.1.4 Экономика 47 Б.1.5 Социология 57 Б.1.6 Культурология 71 Б.1.7 Правоведение 83 Б.1.8.1 Политология 89 Б.1.8.2 Мировые цивилизации, философии и культуры Б.2.1 Алгебра и геометрия Б.2.2 Математический анализ Б.2.3 Комплексный анализ Б.2.4 Функциональный анализ Б.2.5, Б.2.12 Физика...»

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

«Научные исследования подавателей факультета I математики и информатики 70-летию университета посвящается УДК 517.977 Е.А. Наумович ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДЕЯТЕЛЬНОСТИ КАФЕДРЫ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ И ОПТИМАЛЬНОГО УПРАВЛЕНИЯ (1979-2009 гг.) В статье приводятся краткие сведения из истории создания и развития кафедры дифференциальных уравнений и оптимального управления. Сформулированы основные научные направления и наиболее важные результаты, полученные сотрудниками кафедры. Приведена информации...»

«Научное обоснование развития сети особо охраняемых природных территорий в Республике Карелия Карельский научный центр Российской академии наук Научное обоснование развития сети особо охраняемых природных территорий в Республике Карелия Петрозаводск 2009 УДК 502.172 (470.22) ББК 20.18 (2Рос. Кар.) Н 34 Научное обоснование развития сети особо охраняемых природных территорий в Республике Карелия. Петрозаводск: Карельский научный центр РАН, 2009. 112 с.: ил. 14, табл. 6. Библиограф. 96 назв. ISBN...»

«Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Амурский государственный университет Кафедра общей математики и информатики УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ СОВРЕМЕННЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В СОЦИАЛЬНЫХ НАУКАХ Основной образовательной программы по направлению подготовки 040100.62 – Социология Благовещенск 2012 УМКД разработан доцентом, канд. пед. наук Чалкиной Натальей...»

«Раздел 1 УМК Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего профессионального образования УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ: Декан факультета Информационных систем и технологий В. В. Шишкин 2011 г. РАБОЧАЯ ПРОГРАММА Дисциплины (модуля) Пакеты прикладных программ для подготовки научных документов наименование дисциплины (модуля) 230700.62 Прикладная информатика (шифр и наименование...»







 
© 2014 www.kniga.seluk.ru - «Бесплатная электронная библиотека - Книги, пособия, учебники, издания, публикации»

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