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

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

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

Pages:   || 2 | 3 |

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

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

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

Дюбрюкс Сергей Александрович

Метод, алгоритм и устройство обеспечения

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

для вычислительных систем

Специальность 05.13.05 – Элементы и устройства

вычислительной техники и систем управления

АВТОРЕФЕРАТ

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

кандидата технических наук

Курск – 2010

Работа выполнена в ГОУ ВПО «Курский государственный технический университет» на кафедре вычислительной техники в совместной научно-исследовательской лаборатории Центра информационных технологий в проектировании РАН и Курского государственного технического университета: «Информационные распознающие телекоммуникационные интеллектуальные системы»

Научный руководитель:

доктор технических наук, профессор Титов Виталий Семенович

официальные оппоненты:

д.т.н., профессор Сизов Александр Семенович

к.т.н. Таныгин Максим Олегович

Ведущая организация:

Белгородский Государственный Технологический Университет им.В.Г.Шухова

Защита диссертации состоится «13» мая 2010 г. в 14:00 часов на заседании диссертационного совета Д 212.105.02 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

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

Автореферат разослан «11» апреля 2010 г.

Ученый секретарь совета по защите

докторских и кандидатских

диссертаций Д 212.105.02 Е.А. Титенко

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

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

Количество процессоров в многопроцессорных системах постоянно увеличивается, поэтому для их полного и эффективного использования, требуется загрузка каждого процессора информационно-независимыми задачами. В связи с этим возникает задача отображения последовательных программ на множестве процессоров. Для этого применяются методы и алгоритмы выявления линейных, условных и циклических независимых участков (Вл.В. Воеводин, В.В. Воеводин, А.В. Каляев, Б.Я. Штейнберг, Э.А. Трахтенгерц, А.П. Типикин, И.В. Зотов), которые в основном ориентированы на программную реализацию. В многопроцессорных системах задача распараллеливания выполняется, как правило, централизованно хост–процессором. Известно, что в число его задач кроме компиляции входит также маршрутизация, назначение и перераспределение заданий, реконфигурация системы в случае сбоев и другие функции, обеспечивающие управление системой. Процедура компиляции состоит из нескольких этапов, отличающихся вычислительной сложностью, поэтому для решения задачи обеспечения распараллеливания сложных последовательных программ требуется привлечение дополнительных технических средств.





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

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

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

Объектом исследования являются процессы обработки данных в вычислительных системах.

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

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

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

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

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

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

Научная новизна результатов диссертации:

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

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

Работа выполнена в рамках плана НИР Курского государственного технического университета по единому заказ–наряду Министерства образования и науки РФ в 2006-2009 годах.



Практическая ценность результатов исследований:

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

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

3. Разработан пакет программ для имитационного моделирования, позволяющий получить оценку временного выигрыша в скорости решения задач с использованием разработанного вычислительного устройства. Моделирование показало, что применение устройства ускоряет решение задачи компиляции для 10-400 операторов в 5-8 раз, а для 520 и более – примерно в 10 раз.

Реализация и внедрение. Результаты диссертационной работы применены в модернизированной версии расчетного комплекса «ТОКСИ+» по оценке последствий аварий на опасных производственных объектах для увеличения быстродействия комплекса в ОАО «НТЦ «Промышленная безопасность», а также внедрены в учебном процессе на кафедре вычислительной техники КурскГТУ при проведении занятий по дисциплинам «Организация ЭВМ и систем», «Теоретические основы организации многопроцессорных комплексов и систем».

Научные результаты, выносимые на защиту:

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

Апробация работы. Основные положения и результаты диссертации обсуждались и получили положительную оценку на региональных российских и международных конференциях: “Машиностроение и техносфера XXI века” (Украина 2007, 2009 год), “Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации” (Курск 2008).

Публикации. По результатам диссертации опубликовано 12 печатных работ, среди которых 7 статей (из них 3 по перечню ВАК Минобрнауки РФ) и патент на изобретение, получены два свидетельства о государственной регистрации программ для ЭВМ.

Личный вклад автора.

Все выносимые на защиту научные результаты получены соискателем лично. В работах, опубликованных в соавторстве, автором выполнено следующее: в [1] предложен метод выявления параллелизма внутри линейных участков последовательных программ, в [2] описан метод объединения и разделения тел циклических участков последовательных программ, в [3] предложен алгоритм выявления независимых фрагментов последовательных программ, основанный на анализе их внутренней структуры, в [4] разработана схема подключения вычислительного устройства к хост-процессору, в [5, 6] разработан метод выявления параллелизма между линейными и циклическими участками последовательных программ, в [7] предложена структурная схема специализированного вычислительного устройства для выявления параллелизма внутри линейных и циклических участков программ, в [8] приведено решение задачи переназначения переменных при выявлении параллельных участков внутри последовательных программ, в [9] разработана методика поиска и устранения избыточных вычислений в последовательных участках программ, в [10] предложен принцип схемотехнической реализации устройства, в [11, 12] разработан пакет программ для имитационного моделирования работы предлагаемых методов распараллеливания и устройства на их основе.

Объём и структура работы. Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 80 наименований. Диссертация содержит 141 страницу текста (включая 7 приложений) и поясняется 25 рисунками и 15 таблицами.

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

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

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

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

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

По способу реализации выделяют программные и аппаратные методы распараллеливания. Существующие программные методы распараллеливания (MPI, OpenMP) являются низкоуровневыми и отличаются временной избыточностью.

Одно из наиболее известных направлений аппаратного распараллеливания предполагает реализацию алгоритмов на ПЛИС (быстрое преобразования Фурье, метод Гаусса). Подобные разработки, как правило, имеют узкую специализацию на конкретный тип задач. Кроме того, они отличаются невысокой скоростью распараллеливания, ограниченной частотой работы ПЛИС. Ещё один недостаток связан с необходимостью повторного проектирования в других САПР при переносе схемного решения на другие модели ПЛИС одного или разных производителей.

Реализация распараллеливателя на одном кристалле с процессором и несколькими вычислительными ядрами (архитектура VELOCITI в сигнальных процессорах Texas Instruments семейства 6000, EPIC в суперскалярных процессорах Itanium ф. Intel и др.) наряду с достоинствами также имеет ряд недостатков – требует увеличения объёма кристалла, следствием чего является увеличение количества и длин трасс внутри микросхемы, задержек распространения сигнала и повышение энергопотребления. Также аппаратная реализация устройства распараллеливания на одном кристалле с процессором требует существенного увеличения встроенной оперативной памяти или обращения к более медленным внешним запоминающим устройствам. Подобные распараллеливатели не обладают достаточной универсальностью, так как предназначены для работы в определённой архитектуре.

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

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

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

, (1)

где - признак выполняемой операции, f – номер единичного коэффициента для i-той строки.

Множество из N подмножеств , задаётся матрицей входных переменных , .

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



Pages:   || 2 | 3 |
 

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







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

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