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

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

Анализ обращений программы к памяти в оптимизирующей распараллеливающей системе

На правах рукописи

Полуян Степан Вячеславович АНАЛИЗ ОБРАЩЕНИЙ ПРОГРАММЫ К ПАМЯТИ В ОПТИМИЗИРУЮЩЕЙ РАСПАРАЛЛЕЛИВАЮЩЕЙ СИСТЕМЕ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Санкт-Петербург 2011 2

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» на кафедре алгебры и дискретной математики.

Научный консультант: доктор технических наук, с.н.с.

Штейнберг Борис Яковлевич

Официальные оппоненты: доктор физико-математических наук, профессор Терехов Андрей Николаевич доктор технических наук, профессор Бухановский Александр Валерьевич

Ведущая организация: Учреждение Российской академии наук Институт систем информатики им. А.П. Ершова Сибирско го отделения РАН

Защита состоится 22 декабря 2011 г. в 11 часов на заседании диссертационного совета Д 212.227.06 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу:

197101, г. Санкт-Петербург, Кронверкский пр., д. 49, центр интернет образования.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан 16 ноября 2011 г.

Ученый секретарь диссертационного совета Лисицына Л.С.

доктор технических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Среди наиболее известных оптимизирующих и распараллеливающих ком пиляторов можно назвать GNU Compiler Collection (GCC), SUIF Compiler и Intel C++ Compiler. В отечественной науке наиболее заметными в этой области явля ются система V-Ray, система ПРОГРЕСС, DVM-система, T-система, среда ParJava, языки mpC и НОРМА, системы ОРС и ДВОР.

По мере увеличения производительности вычислительных систем все ост рее проявляет себя проблема под названием "стена памяти" (memory wall), кото рая заключается в отставании скорости подготовки данных от скорости их обра ботки. Причем это отставание имеет тенденцию к постоянному увеличению. Так, по данным, приведенным в работе В.В. Корнеева, «тактовая частота процессоров растёт с темпом 40%, а быстродействие схем динамической памяти только 9% в год». В итоге, для ряда программ, активно обращающихся к памяти, увеличение быстродействия процессора практически не приводит к уменьшению времени ра боты этих программ.

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

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

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

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

Задачи исследования. Достижение поставленной цели подразумевает ре шение следующих задач:

• Исследование существующих алгоритмов анализа обращений программы к памяти;

• Разработка анализа псевдонимов для корректного определения обращений программы к памяти;

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

• Разработка анализа размещения данных в общей памяти с минимизацией кэш промахов;

• Разработка анализа размещения данных в распределенной памяти с минимиза цией количества пересылок данных;

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



Методы исследования включают в себя методы теории компиляции про грамм, теории графов, теории алгоритмов и элементы теории множеств. При реа Graph500. URL: http://www.graph500.org лизации программного обеспечения использовались принципы объектно ориентированного программирования.

Научную новизну результатов работы определяют:

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

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

• Новый алгоритм выбора размещения данных в общей памяти с минимизацией количества кэш-промахов, который по сравнению с известными алгоритмами позволяет сократить количество вариантов размещений данных;

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

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

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

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

• Анализатор размещения данных в системах с общей памятью, который позво ляет вычислить размещение данных, минимизирующее кэш-промахи;

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





Основные положения, выносимые на защиту:

1. Алгоритмы и программная реализация анализа псевдонимов для высокоуров невого внутреннего представления;

2. Алгоритмы и программная реализация статического профилирования с диало говым режимом работы;

3. Алгоритм и программная реализация анализа размещения данных в общей па мяти с минимизацией кэш-промахов;

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

Внедрение результатов работы. Результаты работы используются в проек те «Диалоговый высокоуровневый оптимизирующий распараллеливатель про грамм и его приложения» (ДВОР) ФЦП «Научные и научно-педагогические кад ры инновационной России» на 2009-2013 годы, государственный контракт № 02.740.11.0208 от 7 июля 2009 г. В процессе работы получено свидетельство о го сударственной регистрации программ для ЭВМ: «Диалоговый высокоуровневый оптимизирующий распараллеливатель программ» (свидетельство №2011617205).

Кроме того, части данной работы используются в проектах «Тренажер параллель ного программиста», «Анализатор распараллеливаемости циклов» и «Создание биоинформационной технологии поиска взаимосвязанных сценариев организации в геномах животных и человека некодирующей ДНК и кодирующей белок ДНК» ФЦП «Научные и научно-педагогические кадры инновационной России», госу дарственный контракт № 14.740.11.0006 от 1 сентября 2010.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на международных и российских научно-технических конференци ях: THE 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (2009, Moscow), Всероссийская суперкомпьютерная конференция «Научный сервис в сети Интер нет: масштабируемость, параллельность, эффективность» (2009 г., Новороссийск), Всероссийская конференция молодых ученых «Теория и практика параллельного программирования» (2010 г., Новороссийск), 5-ая Международная конференция «Параллельные вычисления и задачи управления» (2010 г., Москва), Междуна родная суперкомпьютерная конференция «Научный сервис в сети Интернет: су перкомпьютерные центры и задачи» (2010 г., Новороссийск), XVIII Всероссий ская научно-методическая конференция Телематика'2011 (2011 г., Санкт Петербург).

Публикации. По теме диссертации опубликовано 12 печатных работ (из них 2 – в изданиях из перечня ведущих рецензируемых научных журналов и из даний Высшей аттестационной комиссии Министерства образования и науки РФ).

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

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы (139 наименований) и одного приложе ния. Содержит 147 страниц текста, включая 50 рисунков и 13 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Во втором разделе первой главы описаны алгоритмы анализа псевдонимов, разработанные и реализованные автором данной работы в системе ДВОР. Пред ложенный анализ псевдонимов основывается как на анализе целей указателей (points-to analysis), так и на анализе типов переменных (type-based alias analysis), что позволяет, не снижая точности анализа псевдонимов, обойтись более просты ми вычислениями там, где это возможно.

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

Отличительными особенностями предложенного автором алгоритма анали за псевдонимов являются:

• независимость от языка входной программы;

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

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

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

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

В четвертом разделе первой главы произведено сравнение анализа псевдо нимов, реализованного автором данной работы в системе ДВОР, с анализом псев донимов, реализованным в известных коммерческих компиляторах.

Тестирование анализа псевдонимов в компиляторе Intel C++ Compiler XE 12.0.3.175 показало, что компилятор проводит распараллеливание с ошибкой, ес ли программа содержит информационную зависимость, образованную путем соз дания псевдонимов через присвоение адреса целочисленной переменной. Напри мер, если сначала выполнить присваивание “int addrB = (int)(&B)”, а затем соз дать указатель “double **pB=(double**)addrB”, то компилятор не может опреде лить к какой переменной указатель pB является псевдонимом. В итоге, результат работы программы, собранной с помощью Intel C++ Compiler XE в исполняемый файл с использованием ключа распараллеливания «Enable Parallelization (/Qparallel)», получается некорректным.

Реализованный автором данной работы в системе ДВОР алгоритм анализа псевдонимов способен выявить подобные псевдонимы, так как учитывает все программные переменные, а не только переменные указательного типа (рис. 1).

Рис. 1. Анализ псевдонимов в системе ДВОР Тестирование анализа псевдонимов в компиляторе Microsoft Visual C++ 2008 показало, что он не выполняет оптимизацию той части кода, которая содер жит псевдонимы массивов. Так, при замене в программе обращения к массиву по индексу “A[1]=1;

” на обращение к массиву через указатель “pA1 = &A[1];

*pA1 = 1;

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

Тестирование быстродействия анализатора псевдонимов проведено на из вестных тестах производительности NAS и SPEC. Результаты измерений приве дены в таблице 1.

Таблица Время проведения анализа псевдонимов Время анализа, Время класси Тестируемая Решаемая задача реализованного ческого анали программа в ДВОР, мин за, мин Программа реализует оператор «куб NPB DC 10,37 274, данных» для технологии OLAP (3154 строк кода).

Программа реализует несколько ва SPEC 24,03 980, риантов игры в шахматы ( 458.sjeng строк кода).

Программа реализует «метод реше SPEC ток Больцмана» для симуляции по 3,51 23, ведения несжимаемых текучих сред 470.lbm (1161 строк кода).

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

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

В первом разделе данной главы сделан обзор существующих алгоритмов профилирования программ. Рассмотрены особенности таких профилировщиков, как Intel VTune Amplifier XE, AMD CodeAnalyst, AQtime Pro, Visual Studio Team System Profiler и IBM Rational Software Analyzer.

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

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

Рис. 2. Схема взаимодействия пользователя с профилировщиком в ДВОР Отличительными особенностями предложенного автором данной работы алгоритма профилирования являются:

• независимость от языка входной программы;

• способность учета пользовательской информации;

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

Таким образом, реализованный автором в рамках проекта ДВОР профили ровщик позволяет определить на этапе компиляции время выполнения таких про граммных единиц, как операторы и подпрограммы, для произвольных программ.

В третьем разделе второй главы описано сравнение результатов статическо го профилирования, реализованного автором в системе ДВОР, с результатами ра боты коммерческих динамических профилировщиков. Результат профилирования программы SPEC 470.lbm в системе ДВОР изображен на рисунке 3.

LBM_performStreamCollide LBM_loadObstacleFile LBM_initializeGrid LBM_showGridStatistics LBM_handleInOutFlow LBM_initializeSpecialCellsForChannel main MAIN_parseCommandLine LBM_allocateGrid MAIN_initialize MAIN_printInfo LBM_swapGrids MAIN_finalize LBM_freeGrid storeValue loadValue MAIN_stopClock MAIN_startClock 0 50000 100000 150000 200000 Рис. 3. Результат профилирования программы SPEC 470.lbm в ДВОР Результат профилирования этой программы с помощью профилировщика Intel VTune Amplifier XE 2011(build 119041) приведен на рисунке 4.

Рис. 4. Профилирование SPEC 470.lbm с помощью Intel VTune XE Профилировщик Intel VTune XE 2011 показывает, что самой горячей точкой про граммы является функция LBM_performStreamCollide, что подтверждает резуль таты, полученные с помощью статического профилировщика в системе ДВОР.

Профилирование той же программы с помощью профилировщика AQtime PRO (ver. 7.10.380.86) дало следующий результат (рис. 5):

Рис. 5. Профилирование SPEC 470.lbm с помощью AQtime PRO Можно видеть, что результаты, полученные с помощью реализованного автором в ДВОР статического профилировщика (рис. 3), в целом аналогичны результатам, полученным с помощью динамических профилировщиков (рис. 4 и 5), однако есть несколько различий:

• Подпрограммы LBM_allocateGrid и LBM_freeGrid при статическом профи лировании получаются менее горячими, чем при динамическом, что вызва но наличием в них функций malloc и free, время выполнения которых зави сит от работы системы памяти.

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

Для оценки быстродействия реализованного в ДВОР профилировщика про изведено измерение времени его выполнения на известных тестах производитель ности NAS и SPEC (табл. 2).

Таблица Время профилирования тестовых программ Тестируемая Кол-во Время, Решаемая задача программа строк сек SPEC Программа численного решения задачи распро 923 1, странения взрывной волны (язык Fortran).

410.bwaves SPEC Программа реализует несколько вариантов иг 13870 7, ры в шахматы (язык C).

458.sjeng Программа реализует «метод решеток Больц SPEC 1161 2, мана» для симуляции поведения несжимаемых 470.lbm текучих сред (язык C).

NPB CG Программа решения СЛАУ (язык Fortran).

1177 2, Программа реализует оператор «куб данных» 3154 5, NPB DC для технологии обработки информации баз данных OLAP (язык C).

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

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

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

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

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

График показывает во сколько раз доступ к матрице по строкам быстрее доступа по столбцам при пострчном размещении матрицы Отношение времени доступа по столбцам ко времени доступа по строкам 0 300 700 1100 1500 1900 2300 2700 3100 3500 3900 4300 4700 параметр N Чтение Запись Рис. 6. Ускорение программы при оптимальном размещении данных в системах с общей памятью На рисунке 6 видно, что ускорение программы при оптимальном размеще нии данных в общей памяти может достигать 2,5 раз при записи данных и 4 раз при чтении данных.

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

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

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

Алгоритм Профилирование;

Цикл (пока существуют неразмещенные массивы) { Выбирается самая горячая точка программы, содержащая хотя бы одно вхождение еще неразмещенного массива;

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

} Конец алгоритма.

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

Время проведения анализа размещения данных, реализованного автором работы в системе ДВОР, представлено в таблице 3.

Таблица Время проведения анализа размещения данных Время Время Программа Примечание Ускорение без эври- с эвристи стики, мин кой, мин В программе используются Перемноже 3,23 2,05 1, квадратные матрицы размера ние матриц В программе используются Сложение 1,42 1,14 1, квадратные матрицы размера матриц В программе используются LU разложе 3,51 2,33 1, квадратные матрицы размера ние матриц Программа численного реше ния задачи распространения SPEC 33,23 17,51 1, взрывной волны (923 строк 410.bwaves кода, 51 массив размерности от 3 до 5).

Программа реализует не SPEC сколько вариантов игры в 13,04 8,23 1, шахматы (13870 строк кода, 458.sjeng 11 двумерных массивов).

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

Заключение. В ходе диссертационной работы получены следующие ре зультаты:

• Произведено исследование существующих алгоритмов анализа обращений программы к памяти;

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ Полуян С.В. Уточнение графа информационных связей с помощью анализа 1.

псевдонимов // Информационные технологии. –2011. – №4. – С. 36-40. (из перечня ВАК) Полуян С.В. Выбор оптимального размещения многомерных массивов в па 2.

мяти компьютера // Известия вузов. Северо-Кавказский регион. Естествен ные науки. – 2010. – №3. – С. 15-18. (из перечня ВАК) Полуян С.В. Статический анализ высокоуровневых программ. – Saarbrcken:

3.

Lambert Academic Publishing, 2011. - 154 c.: ил. – ISBN 978-3-8454-4150-4.

Полуян С.В. Автоматическое размещение массивов в распределенной памяти 4.

с минимизацией количества пересылок // Труды научной школы И.Б. Симо ненко. – Ростов-на-Дону: Изд-во ЮФУ, 2010. – С. 214-219.

Полуян С.В. Анализ обращений программы к памяти в оптимизирующей рас 5.

параллеливающей системе // Труды XVIII Всероссийской научно методической конференции Телематика'2011. Том 2 (20-23 июня 2011 г., г.

Санкт-Петербург). – СПб.: СПбГУ ИТМО, 2011. – С. 328-329.

Полуян С.В. Анализ указателей для распараллеливания // Параллельные вы 6.

числения и задачи управления (PACO’2010): Труды V Международной кон ференции (26-28 октября 2010 г., г. Москва). – М.: Институт проблем управ ления им. В.А. Трапезникова РАН, 2010. – С. 1065-1069.

Полуян С.В. Профилирование и его применение в диалоговом высокоуровне 7.

вом оптимизирующем распараллеливателе // Научный сервис в сети Интер нет: суперкомпьютерные центры и задачи: Труды Международной супер компьютерной конференции (20-25 сентября 2010 г., г. Новороссийск). – М.:

Изд-во МГУ, 2010. – С. 652-653.

Полуян С.В. Оптимальное размещение данных на этапе компиляции // Науч 8.

ный сервис в сети Интернет: масштабируемость, параллельность, эффектив ность: Труды Всероссийской суперкомпьютерной конференции (21-26 сен тября 2009 г., г. Новороссийск). – М.: Изд-во МГУ, 2009. – С. 283-286.

9. Steinberg B., Abramov A., Alymova E., Baglij A., Guda S., Demin S., Dubrov D., Ivchenko A., Kravchenko E., Makoshenko D., Molotnikov Z., Morilev R., Nis Z., Petrenko V., Povazhnij A., Poluyan S., Skiba I., Suhoverkhov S., Shapovalov V., Steinberg O., Steinberg R. Dialogue-based optimizing parallelizing tool and C2HDL converter // Proceedings of 7th IEEE EAST-WEST DESIGN & TEST SYMPOSIUM (Moscow, Russia, September 18-21, 2009). – 2009 – P. 216-218.

10. Штейнберг Б.Я., Абрамов А.А., Алымова Е.В., Баглий А.П., Гуда С.А., Дубров Д.В., Кравченко Е.Н., Морылев Р.И., Нис З.Я., Петренко В.В., Полуян С.В., Скиба И.С., Шаповалов В.Н., Штейнберг О.Б., Штейнберг Р.Б., Юрушкин М.В. Диалоговый высокоуровневый оптимизирующий распараллеливатель (ДВОР) // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды Международной суперкомпьютерной конференции (20- сентября 2010 г., г. Новороссийск). – М.: Изд-во МГУ, 2010. – С. 71-75.

11. Штейнберг Б.Я., Абрамов А.А., Баглий А.П., Морылев Р.И., Петренко В.В., Полуян С.В., Штейнберг Р.Б. Уточнение зависимостей программы в ДВОР // Параллельные вычисления и задачи управления (PACO’2010): Труды V Ме ждународной конференции (26-28 октября 2010 г., г. Москва). – М.: Институт проблем управления им. В.А. Трапезникова РАН, 2010. – С. 855-864.

12. Штейнберг Б.Я., Штейнберг Р.Б., Морылев Р.И., Петренко В.В., Полуян С.В., Штейнберг О.Б., Баглий А.П., Нис З.Я., Скиба И.С., Юрушкин М.В., Шаповалов В.Н., Алымова Е.В., Кравченко Е.Н., Гуда С.А. Диалоговый высо коуровневый оптимизирующий распараллеливатель программ // Свидетель ство о государственной регистрации программы для ЭВМ № 2011617205 – 2011.



 

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





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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