ВОСЬМАЯ
ОТКРЫТАЯ
НАУЧНО-ПРАКТИЧЕСКАЯ КОНФЕРЕНЦИЯ ЛИЦЕЯ
20 января 2011 года
www.l2s-conference.narod.ru, www.ded32.net.ru
Все материалы докладов необходимо представить
в Оргкомитет до начала конференции
для публикации в сборнике трудов конференции и на сайте конференции в Интернете
(http://l2s-conference.narod.ru, http://ded32.net.ru).
Материалы принимаются в электронной форме председателями секций по электронной почте mail@ded32.net.ru. Форматы файлов – текстовый (txt), Microsoft Word, OpenOffice Word, ТеХ, рисунки и схемы – PNG, JPG.
Секция Computer Science
(Предс.
И.Р. Дединский)
900
– 1200
1. Рязановский
Данила (8). Реализация системы частиц для задач компьютерной графики.
2. Петряйкин Федор (10В). Разработка
DICOM-ассистента, осуществляющего функцию вычитания томографических
изображений.
3. Лушковский Сергей, Сквирский Валентин (7В).
Моделирование движения тел на разных планетах.
4. Пономарев Олег (11А). Дизайн и эволюция
архитектуры универсального построителя фракталов TBG Fractal.
5. Столяров Леонид (10В). Трёхмерная
визуализация высокодетализированных ландшафтов большого размера в графическом
движке XEngine.
6. Татаринов Андрей (nVidia Corporation). Алгоритм Reyes
для кинематографической визуализации трехмерных сцен с использованием DirectX
11.
1220
– 1420
7. Дедков Антон, Шевелев Александр (11А).
Quffman: кроссплатформенная реализация алгоритма сжатия информации с
использованием кода Хаффмана.
8. Янушковский Владимир (11В).
Cudaffman: алгоритм сжатия по Хаффману с примен-нием технологии nVidia CUDA.
9. Смирнов Илья (11А). NanoGCC:
система символьного преобразования выражений и оптимизирующей компиляции в
байт-код.
10. Меркулов Алексей (Институт системного
программирования РАН). Эмуляция трёхмерной графики в QEMU.
11. Уваров Никита (9В). Разработка
библиотеки анализа исходного кода программ на языке С.
12. Шаповалов Иван (8В). Разработка
JIT-компилятора арифметических и логических выражений для платформы Intel x86.
13. Платонов Владимир (Институт системного
программирования РАН). Разработка и реализация системы автоматизации
программирования для программируемых логических интегральных схем.
1440
– 1640
14. Шемарин Антон (8В). Разработка
виджета для ОС Android.
15. Андриенко Матвей (11В). Разработка
системы управления сайтом, ориентированной на содержимое.
16. Пимкин Артем (8В). Этапы создания
двумерной игры на С++.
17. Байтеков Никита (8В). Алгоритм
морфемного анализа русских слов.
18. Никифоров Дмитрий (9В).
Компьютерный анализ шумового фона в аудитории.
19. Башлыков Леонид (11А). Экспертная система
диагностики проблем подключения к интернету.
ТЕЗИСЫ ДОКЛАДОВ
Когда с развитием интернета и веб-технологий сайты начали становиться сложнее и насыщеннее, возникла проблема эффективного управления содержимым сайта. Необходимость изменять исходный код страниц для внесения изменений в содержимое повышала риск допустить ошибку, критичную для работы сайта. Кроме того, с ростом числа страниц управление содержимым таким образом становилось практически невозможным. Стало ясным, что необходимы дополнительные программные средства, которые бы предоставляли более удобный интерфейс для управления сайтом, – так называемые системы управления содержимым (CMS, Content Management System).
Современные CMS предоставляют богатейшие возможности помимо собственно редактирования содержимого сайта, такие как модуль авторизации пользователей, модуль для автоматической почтовой рассылки и т.д. Однако, такие CMS имеют и ряд недостатков. Во-первых, они ориентированы скорее на корпоративных пользователей, а не обладателей простых «домашних страничек» с небольшой нагрузкой. Таким пользователем зачастую нужно только редактировать тексты на сайте и управлять его структурой. В таком случае сложные интерфейсы административных панелей CMS только мешают пользователю выполнять свои задачи. Во-вторых, такие CMS зачастую сложны в установке и настройке, именно в силу своей универсальности. Системные требования CMS заставляют пользователя оплачивать более «продвинутый» хостинг по более высокому тарифу, а разобраться с настройками пользователь зачастую вообще не в состоянии.
В связи с изложенным, были сформулированы принципы, положенные в основу разрабатываемой CMS:
– Минимальные требования к веб-серверу (на данный момент обязательно только наличие PHP5, никаких баз данных)
– Минимальное количество настроек; пользователь должен получать готовый продукт из «коробки»
– Отсутствие административной панели; пользователь может пользоваться для редактирования текстов на сайте любым удобным ему текстовым редактором
– По возможности простое управление оформлением сайта (шаблонизация)
– Для продвинутых пользователей: открытый исходный код, наличие документации и расширяемость
В результате была создана система управления сайтом Sintey, ориентированная на содержимое. Разработка системы велась с использованием методологии разработки FDD (feature-driven development). В докладе будет предоставлен отчет о разработке и продемонстрированы достигнутые результаты.
Морфемный анализ (разбор слова по его составу) – это выделение отдельных частей слова, или морфем, в разбираемом слове (окончаний, приставок, суффиксов и т.д.), а также определение части речи. В жизни мы, не задумываясь, быстро разбираем любые слова по составу благодаря подбору однокоренных слов и выделению корня (или корней), основываясь на многолетнем знании русского языка. Но разработать и реализовать алгоритм, производящий точный разбор слова по составу крайне трудно из-за ряда определенных проблем, связанных с гибкостью русского языка.
В ходе работы были реализованы собственные алгоритмы и методы решения некоторых проблем, связанных с анализом состава слова. В результате удалось разработать программу, которая в состоянии произвести морфемный анализ существительных, прилагательных, глаголов и причастий (при условии, что в их состав не входит более двух морфем одного вида), а также определить к какой части речи относится данное слово. В докладе будут разобраны основные проблемы морфемного анализа и алгоритмы, использующиеся в программе.
Цель работы состоит в автоматизации процесса диагностики проблем интернет подключения. Сценарий работы диагностической программы строится как диалог с пользователем, в ходе которого определяется, в чем состоит проблема, и предлагаются пути ее решения. Это позволяет снять лишнюю нагрузку с инженерного персонала на производстве, экономит время и деньги.
К программе прилагается пополняемая база данных возможных неполадок, сохраняемая в файле текстового формата, что позволяет при желании редактировать ее вручную. Программа использует структуру данных в виде динамического двоичного дерева, что позволяет сделать базу данных пополняемой.
Программа разработана под операционные системы Linux и Windows с использованием языка программирования C++.
Программа имеет два режима использования: пользовательский и администраторский. В пользовательском режиме блокируется доступ к функции изменения информации в базе данных, чтобы избежать нежелательных изменений в ней, и работает только выдача ответов. В режиме администратора программа будет позволять полный доступ к базе данных. Эксперт или инженер в этом режиме сможет добавлять новые узлы в дерево, пополняя тем самым базу данных и расширяя возможности программы, что сделает ее более мобильной.
Окончательно готовая программа будет полезна на любом высокотехнологичном производстве с большим количеством работников, которым для работы необходим интернет.
Целью работы было создание кроссплатформенной библиотеки сжатия информации методом Хаффмана и интерфейсов пользователя для взаимодействия с ней. Задача библиотеки – абстрагировать приложение от особенностей алгоритма кодирования и формата сжатых данных. Библиотека предоставляет инструменты для работы приложения с архивом: считывания/редактирования внутриархивной файловой системы, добавление файлов в очередь на кодирование/декодирование.
В работе были поставлены и реализованы следующие задачи:
– Реализация алгоритма сжатия методом Хаффмана таким образом, чтобы она была абстрагирована от архитектуры ядра библиотеки.
– Анализ факторов, влияющих на скорость и качество сжатия, таких как мощность используемого алфавита, размеры блоков, на которые разбивается кодируемый файл.
– Разработка формата хранения сжатых данных, в котором минимизирована системная информация. Формат позволяет хранить как отдельные файлы, так и файловые иерархии. В нем также хранится информация для декодирования, такая как физическое расположение блоков сжатого файла на диске и информация о частотах, необходимая компрессору для декомпрессии.
– Реализация CLI (интерфейс командной строки).
– Реализация GUI (графического интерфейса пользователя) на основе оконного фреймворка Qt.
Основной задачей проекта является разработка программы для моделирования движения тел на разных планетах (при разной силе притяжения) и в невесомости.
При написании программы использовалась среда Dev-Cpp и компилятор GCC.
Программа состоит из двух модулей: меню (выбора планеты для моделирования и других параметров) и анимации (моделирования движения объектов). В меню можно выбрать планету Солнечной системы, на которой будет производиться моделирование, и далее с учётом заранее введённых параметров гравитации планеты запускается анимационное окно, в котором отображаются моделируемые объекты. Пользователь также может управлять параметрами движущихся объектов.
Объектами анимации являются три шара, цвет которых меняется. При соприкосновении шара и стенок происходит упругое отталкивание, вследствие чего меняется вектор скорости тела (направление его движения).
В программе присутствует функция «ветра» вносящая коррективы в движение объектов. Также доступна функция «магнита», увеличивающая силу взаимодействия с планетой. При помощи клавиатуры пользователь может управлять гравитацией и «ветром».
Для разработки, тестирования и отладки приложений под архитектуры, отличные от архитектуры компьютера разработки, часто используется эмуляторы, в частности, QEMU. Чтобы эмулировать архитектуру, требуется эмулировать центральный процессор, память и другие устройства, такие как звуковая карта, графическая карта, клавиатура и другие. Иногда встречаются устройства, которые на уровне регистров эмулировать крайне сложно, или на которые закрыта техническая документация по аппаратной части. Тогда требуется заменить реальное (с точки зрения эмулируемой ОС) устройство виртуальным с сохранением функциональных свойств исходного. Для такого устройства необходимо написать собственный драйвер. Целью работы является эмуляция трёхмерной графики в QEMU при помощи такого драйвера. В процессе работы были решены такие задачи, как создание виртуального устройства, разработка драйвера OpenGL ES для него, а так же применения аппаратного графического ускорения при эмуляции.
В образовательном процессе средней и высшей школы нередко встречается ситуация потери контроля преподавателя над семинарским или лекционным занятием по причине высокого шумового фона аудитории. В этом случая преподавателю требуется каким-либо образом реагировать на данную ситуацию с целью обретения этого контроля (повышать голос, стучать и т.д). Подобные реакции, направленные на привлечение внимания, неприятны для всех участников образовательного процесса, включая преподавателя, и иногда приводят к конфликтам.
Целью работы является разработка программы, реагирующей на
повышение шумового фона в аудитории путём плавного повышения громкости
стороннего звука, не раздражающего людей, но привлекающего внимание к
«неучебной» атмосфере.
Основным этапом является разработка анализатора общего уровня шума. Одной из задач являлось изучение библиотеки OpenAL, использующейся для взаимодействия со звуковой каартой. Другие задачи включали запись звука с микрофонного входа, его усреднение за определенное время, оценка скорость изменения шума и его величины в данный момент. Вторым этапом является непосредственное тестирование программы и подбор приемлемой частоты исходящего звука.
Таким образом данная программа поможет вести преподавателю занятие, не отвлекая внимание аудитории от сути учебного процесса.
Целью работы является реализация DICOM-ассистента, упрощающего диагностику сосудистых патологий, находящихся в кости.
К продукту предъявлялись следующие требования: поддержка DICOM-формата (в т.ч. способа хранения данных в DICOM – единиц Хаундсфилда, программа должна принимать этот формат на вход и выдавать его на выходе) и сопоставление DICOM файлов по позиции среза.
Для выполнения поставленной цели был использован язык программирования C++ для платформы Win32 в среде Micriosoft Visual Studio 9.0 (2008).
Для чтения DICOM-формата была использована библиотека с открытым исходным кодом ITKDicomParser.
Ассистент реализован в виде консольного приложения, принимающего названия папок с исходными файлами и название конечной папки в качестве аргументов командной строки. В исходных папках находятся два набора изображений: до введения контраста и после него. Во время работы программа проходит следующие этапы: загрузка исходных DICOM-файлов, их сортировка (составление пар файлов из исходных папок, имеющих одинаковую позицию среза), вычитание, запись результата.
На основании полученных изображений строится трёхмерное изображение сосудистого рисунка на станции EBW (Extended Brilliance Workspace) производства фирмы Siemens.
В составе EBW есть утилита, выполняющая схожие задачи. Однако она не может в полной мере удовлетворить потребности врачей, так как полученные с её помощью изображения не достаточно хорошо отражают сосудистый рисунок. Программа, разработанная автором, позволяет получать изображения значительно лучшего качества.
В данной работе был разработан консольный DICOM-ассистент, выполняющий вычитание наборов срезов (до введения контраста и после него). Полученные изображения могут быть визуализированы в трёхмерном виде с помощью средств станции EBW.
Целью доклада является рассказ об этапах разработки компьютерной игры, в частности какие этапы необходимо выделить при разработке двумерной игры, даже если до этого у разработчика не было опыта написания компьютерных игр. В качестве примера процесса разработки игры будет приведена написанная автором игра PunkMania.
В докладе из процесса разработки выделены три стадии, которые будут разделены на различные этапы.
В первой стадии содержится два этапа – это этап концепта (задумки), который необходим, чтобы понять, о чем или зачем планируется создать игру. Второй этап – это этап прототипа, который необходимо выделить, чтобы понимать, откуда «начинать писать» свою игру, что является ее «базой», необходимым функциональным минимумом.
Во второй стадии важен этап разработки различных надстроек над начальным прототипом, в конце которого необходимо получить законченный игровой процесс. В конце этого этапа необходимо провести так называемый альфа-тест о смысле, подробнее о котором будет рассказано в докладе.
Есть еще третья стадия – интерфейсная. Это стадия реализации и «доводки» интерфейса игры и ее графики. В конце этой стадии также необходимо провести тест, о чем также будет рассказано в ходедоклада.
За последние несколько лет всё большее распространение получают FPGA платы (дополнительное вычислительное устройство для прототипирования). Они представляют удобное средство для программирования отдельных функций или целиком логики алгоритма на аппаратном уровне, что позволяет увеличить скорость вычисления для конкретно взятой задачи по сравнению с процессором общего назначения. Однако, до сих пор отсутствует унифицированный способ взаимодействия программы, выполняющейся на компьютере, с FPGA платой.
OpenCL – фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных устройствах(таких как GPU, Multicore CPU). Он удобен, стандартизирован и поддерживается многими крупными корпорациями.
Целью работы является добавление поддержки FPGA-устройств в OpenCL, для реализации удобного интерфейса взаимодействия с программой, выполняющейся на хосте.
В прошлом году автором была разработана и реализована программа для исследованию множества Мандельброта с использованием технологии распределенных вычислений nVidia CUDA. Изначально программа должна была обладать ограниченным набором возможностей. Однако в ходе работы с программой и при обсуждениях полученных результатов на семинарах в Институте теоретической и экспериментальной физики РАН постоянно выдвигались новые требования к ней, что через некоторое время привело к необходимости переработки архитектуры программы. Среди особенностей разработанной архитектуры следует отметить использование GNU Maxima для математических расчетов и nVidia CUDA для ускорения построения множества. Цель данного доклада – проследить эволюцию программы, предназначенной для научных исследований в области теоретической физики, и разобрать серию рефакторингов, которые привели к заметным архитектурным улучшениям и упрощениям, облегчив дальнейшее расширение проекта. Это позволило добавить множество новых возможностей, таких как построение множества Julia, а также построение трехмерных срезов множества Мандельброта.
Цель работы – разработка системы частиц и создание программы для демонстрации её возможностей.
Система частиц – это способ легко создать множество красивых эффектов, таких как снег, дождь, туман, дым, огонь, взрыв, искры, фейерверки и других. Она состоит из множества частиц – материальных точек, обладающих различными дополнительными свойствами. Они двигаются, меняют цвет, размер и создают необходимый эффект.
В ходе работы была создана программа для демонстрации систем частиц с графическим пользовательским интерфейсом, позволяющим менять все параметры системы частиц во время выполнения программы. Также была реализована возможность сохранять параметры системы частиц.
В дальнейшем планируется реализовать обработку частиц в пространстве, усложнить обработку физики, реализовать обработку взаимодействия частиц.
Целью работы явилось создание пакета программ nanoGcc – системы для преобразования и оптимизации числовых выражений, а также для их компиляции их в другие варианты записи (фактически, перевода кода из одного языка программирования в другой). Данный пакет программ может использоваться при решении алгебраических задач.
Основным объектом является Tree – класс дерева, удобный для использования благодаря системе отладки и наличия высокоуровневых средств, позволяющих снизить вероятность ошибки. Это необходимое условие для решения поставленных задач, так как алгоритм оптимизации достаточно сложен в отладке.
На данный момент nanoGcc реализована лишь для UNIX-систем, однако в будущем возможен и кроссплатформенный вариант.
Для осуществления поставленных задач был изучен и использован метод символьного дифференцирования. Он позволяет относительно быстро и просто дифференцировать любое алгебраическое выражение.
Одна из самых благоприятных для разработчика особенностей – это модульный дизайн, дающий возможность замены штатной составной части (ядра, фронт-энда или бэк-энда) на стороннюю. Подобные перестановки помогают при отладке системы и способствуют ее гибкости. Данный проект позволяет активно участвовать в нем сторонним разработчикам, например, для реализации поддержки компиляции нескольких языков программирования (способов записи выражений), для чего взаимозаменяемым образом могут использоваться их модули.
Несмотря на некоторую сложность в архитектуре и разработке, связанную со взаимодействием разработчиков между собой, nanoGcc является интереснейшим проектом, просторы развития которого крайне велики.
Возрастающие в последнее время требования к качеству компьютерной графики в игровых и модельных и образовательных приложениях, таких как автоматная многоагентная система Auto2Kill, диктуют необходимость визуализации высоко детализированных ландшафтов больших размеров. В докладе будет рассмотрен набор технологий визуализации ландшафта, применяемый в графическом движке XEngine, лежащем в основе Auto2Kill. Основным затруднением при визуализации таких ландшафтов оказывается огромная вычислительная сложность, вызванная его большими размерами. Для её оптимизации используются алгоритмы, позволяющие значительно повысить производительность, путём упрощения расчёта получаемого изображения, без заметной потери качества. Это такие алгоритмы, как LoD (Level of Detail; уровни детализации), Geo Mipmapping, Quadtree (четвертичное дерево геометрии), отсечение невидимой геометрии.
Трёхмерный ландшафт включает в себя рельеф местности (terrain) и детальные объекты, такие как трава и листья. Рельеф местности описывается картой высот – текстурой, задающей высоту поверхности во всех её точках. Во время загрузки ландшафт разбивается на некоторое количество равных блоков по регулярной сетке, что необходимо для работы применяемых алгоритмов оптимизации. Для каждого из блоков статически генерируются версии для всех уровней детализации. Далее происходит построение четвертичного дерева геометрии и расчёт нормалей к вершинам поверхностей.
При визуализации ландшафта происходит отсечение невидимой геометрии, то есть блоки, не попавшие в поле зрения «наблюдателя» (viewing frustum) и, как следствие, не присутствующие в получаемом изображении, не будут обрабатываться видеокартой. Такая проверка уменьшает зависимость производительности визуализации от размера ландшафта, так как обрабатывается только видимая часть ландшафта. Использование сгенерированного ранее дерева геометрии позволяет значительно оптимизировать процесс отсечения, уменьшая количество проверок (сложность алгоритма без использования дерева – линейная, в то время как с его использованием – логарифмическая), тем самым уменьшая нагрузку на центральный процессор. В то же время, при визуализации видимой части ландшафта, ближайшие к «наблюдателю» блоки отрисовываются с использованием высокого уровня детализации, а по мере увеличения расстояния от «наблюдателя» до блоков, для их отрисовки используются всё более низкие уровни детализации. Такой подход ведёт к значительному повышению производительности, уменьшая сложности геометрии сцены, в то время как качество ухудшается незначительно, так как удалённые от «наблюдателя» участки ландшафта вносят гораздо меньший вклад в получаемое изображение, чем наиболее близкие к нему.
Текстурирование ландшафта осуществляется с использованием глобальной текстуры (megatexture), накладывающейся на весь ландшафт целиком, и детальной текстуры (detail texture), которая служит для улучшения качества визуализации очень близких к «наблюдателю» участков ландшафта, компенсируя недостаточное разрешение глобальной текстуры. Освещение ландшафта рассчитывается динамически с использованием шейдерной программы, основываясь на ранее сгенерированных нормалях для каждой вершины. В основе алгоритма освещения поверхности лежит модель Ламберта в сочетании с эффектом тумана.
Применённые алгоритмы позволили реалистично визуализировать ландшафт внушительного размера с большим количеством деталей, в том числе и на относительно маломощных компьютерах с видеокартами посредственной производительности.
Reyes, или Renders Everything You Ever Saw, – это графический конвейерный алгоритм, который является мировым стандартом компьютерной графики и широко используется в кинематографии и мультипликации. Такие особенности, как поддержка гладких поверхностей, интерполяция атрибутов поверхностей в пространстве объекта, высокое качество сглаживания, поддержка таких эффектов, как motion-blur (размытие в движении) и depth-of-field (глубина резкости), делают Reyes незаменимым инструментом при создании реалистичных изображений, используемых в кинематографе.
Естественно, что высокое качество получаемого изображения дается ценой колоссальных затрат производительности. Скорость расчета одного кадра может занимать минуты, часы и даже дни, в зависимости от сложности используемого контента.
В то же время, графические ускорители (GPU), используемые в персональных компьютерах, позволяют запускать трехмерные графические приложения в реальном времени. И если до недавних пор разница в качестве между кинематографическими изображениями и графикой компьютерных игр была колоссальна, то с появлением все более и более мощных GPU и нового API DirectX 11 стало возможным приблизиться по качеству графики к кино, при этом сохраняя интерактивную скорость рендеринга.
DirectX 11 предоставляет расширенный и дополненный графический пайплайн, с помощью которого возможно напрямую реализовать Reyes, и достичь тех характеристик изображения, за которые он настолько ценится в киноиндустрии. Такие возможности DirectX 11, как тесселляция и поддержка Compute, делают традиционный графический пайплайн гораздо более гибким и позволяют разработчикам использовать Reyes в современных приложениях для значительного повышения качества изображения.
Целью работы явилось создание библиотеки для лексического, синтаксического и семантического анализа программ на языке С. На её основе можно реализовать инструменты, которые используют препроцессированный текст, поток лексем, печатают или оптимизируют синтаксическое дерево. Модули системы взаимодействуют через интерфейсы, что позволяет пользователю самому реализовать некоторую функциональность, например, класс оптимизации на основе классов синтаксического и семантического анализа.
Рассмотрим процесс построения синтаксического дерева. На вход лексическому анализатору подается входной поток (который может быть не только файлом, но и объектом в памяти). Он разбивает его на лексемы – неделимые единицы языка. Любое имя, строка, число, знак являются лексемами. Напротив, отдельные цифры числа, символы строки сами по себе лексемами не являются и в задачу лексического анализа как раз входит их объединение.
Полученный поток лексем может быть передан препроцессору, который выполняет анализ директив и обработку инструкций define. Данная реализация препроцессора может быть использована для его изучения, так как поддерживает все функции, определённые в действующем стандарте языка С (С99, ISO/IEC 9899:1999 E).
Наконец, поток лексем доходит до синтаксического анализатора (класс SyntaxTreeBuilder), который строит синтаксическое дерево программы методом рекурсивного пуска. Данная часть библиотеки взаимодействует с генератором типов посредством интерфейса, вызывая определённые функции для каждой вершины. Алгоритм построения дерева будет рассмотрен в докладе отдельно.
На выходе мы получаем синтаксическое дерево, которое можно распечатать или сохранить для дальнейшей визуализации. Несмотря на большое количество модулей, которые можно использовать по отдельности, препроцессирование, построение дерева и генерация типов вершин выполняются за один проход.
Библиотека разделена на файлы заголовков и реализации, допускает использование через DLL. Для обработки ошибок на уровне программиста используются исключения, а на уровне пользователя предусмотрено ведение лога компиляции.
Некоторой внутренней мотивацией автора, в числе прочего, была проблема изучения частей языка С, которые описаны только в спецификациях стандарта, весьма трудного для изучения документа. Примером такой части может служить система типов со всеми ее деталями и особенностями. Например, все программисты умеют объявлять указатели на функции, но не все четко знают, как объявить, например, массив указателей на них, или почему нельзя заключить возвращаемый тип в скобки: (void) func(). Другая «загадочная» часть языка С – препроцессор – зачастую мало требуется в программах на С++ но тем не менее полезно знать, как он работает, и какие уникальные возможности предоставляет.
Данный проект был развит из составной части предыдущего проекта – интерпретатора конечных автоматов. Исходный модуль интерпретатора был реализован как замена скриптовому движку Lua для обработки условий автоматов. Конечный вариант компилятора также будет встроен в этот интерпретатор.
Достоинствами компилятора являются простота использования, кроссплатформенность и изменяемая семантика выражений (набор операторов, типов и правил кодогенерации). Поддержка этих функций реализована как на уровне ядра компилятора, так и на уровне стандартной семантики выражений. Осуществляется интенсивная работа над возможностями оптимизации выражений и сгенерированного машинного кода.
Компилятор состоит из нескольких основных частей: парсер (лексический и синтаксический анализаторы), оптимизатор, семантический анализатор и кодогенератор. Задача парсера – построение дерева выражения, в точности соответствующего исходному выражению. Затем выполняется первый шаг оптимизации – максимальное упрощение дерева выражения с сохранением его изначальной семантики. Далее при семантическом анализе дерева производится установка промежуточного типа каждого подвыражения и проверка правильности типов. В конце осуществляется построение и оптимизация промежуточного кода, за которыми следует генерация машинных кодов (машинного образа), вычисляющего значение выражения. Он является результатом работы JIT-компилятора.
Проект был полностью переработан в июне 2010 года с целью устранения неэффективности метода разбора выражения, следствием чего являлась чрезмерная сложность алгоритмов оптимизации. Также при рефакторинге был выполнен переход на активное использование библиотеки STL и различных дополнительных механизмов C++.
В настоящее время разработка подходит к завершению; из этого проекта в дальнейшем будет развит компилятор языка Си.
В настоящее время имеется большое разнообразие операционных систем для мобильных устройств, и почти каждый год появляются новые. Из-за этого каждый год многие разработчики вынуждены выпускать свои программы под новые мобильные платформы. Некоторые из них жестко диктуют использования программ только определенных языков (например, все приложения под iOS должны быть написаны только на языке Objective C). В этом плане наиболее «либеральной» является OS от Google – Android. Для Android программы могут быть написаны как на Java, так и на C++, или даже HTML/JavaScript (хоть это даже и не язык программирования). Android также удобен тем, что он основан на ядре Unix и является проектом, открытом для всех (исходный код Android OS может просмотреть любой желающий). Таким образом, у разработчика имеются все возможности для изучения особенностей данной системы.
По всему миру наблюдается рост продаж устройств под управлением Android, что способствует развитию SDK для написания приложений. Написание приложений для мобильных платформ, к сожалению, вещь не всегда простая и понятная, особенно для начинающих. В докладе будут разобраны простейшие примеры разработки приложений (виджетов) для Android.
Программна Cudaffman – реализация алгоритма сжатия Хаффмана с использованием технологии nVidia CUDA, позволяющей выполнять большой объём параллельных вычислений. и таким образом потенциально ускоряющую работу алгоритма.
Способ распараллеливания. Было принято решение разбить исходный файл на части (pieces) постоянного размера и при сжатии подгружать по несколько частей, параллельно запускать для них процедуру архивации (kernel) и записывать их в архив.
Формат архива. В начале архива находится 4-байтная сигнатура с номером версии алгоритма, затем 1 Кб информации, необходимой для восстановления дерева Хаффмана (256 целых чисел – частот символов). Далее следуют куски (pieces) зашифрованной информации, в начале каждого – длина куска и количество значащих бит в последнем байте.
Архитектура программы. Основу программы составляет класс CudaffmanCompressor, который содержит методы сжатия (compress) и "разжатия" (декомпрессии, decompress) файлов. Оба эти метода работают в соответствии с выбранным алгоритмом, то есть подгружают несколько частей, а затем вызывают функцию ядра для каждой из этих частей. Расмотрим ядро алгоритма сжатия. Оно представлено CUDA-функцией CudaffmanCompressorKernel и её обёрткой – CudaffmanCompressorKernelCall. Также имеются аналогичные функции CudaffmanCompressorKernelCPU и CudaffmanCompressorKernelCPUCall, которые практически совпадают с предыдущими, но выполняются на ЦП. Класс CudaffmanCompressor позволяет включить или отключить использование CUDA. При этом он просто вместо одной обёртки вызывает другую. Декомпрессия устроена абсолютно аналогично. Программа реализована на языке С++ в среде программирования MS Visual Studio 2008.
Работа была выполнена в рамках курса «Алгоритмы и структуры данных» (преп. И. Р. Дединский). Для распараллеливания алгоритма и его реализации на CUDA использованы материалы семинаров по CUDA, проводившихся на факультете ВМиК МГУ А. В. Боресковым и А. Харламовым.