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

На правах рукописи 0050ьоэо- |

П '.АУ^'у

НЕДОВОДЕЕВ Константин Владимирович

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

? 9 НОЯ 2012

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

005055984

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный политехнический университет» (ФГБОУ ВПО «СПбГПУ»)

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

Шейнин Юрий Евгеньевич Официальные оппоненты: Устинов Сергей Михайлович

доктор технических наук, профессор, профессор кафедры информационных и управляющих систем ФГБОУ ВПО «СПбГПУ» Помозова Татьяна Геннадьевна кандидат технических наук, доцент, начальник лаборатории ОАО «ЦНПО «Ленинец»

Ведущая организация: Федеральное государственное бюджетное учреждение науки Санкт-Петербургский институт информатики и автоматизации Российской академии наук

Защита состоится "20" декабря 2012 года в 16 часов на заседании диссертационного совета Д 212.229.18 ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу: 195251, Санкт-Петербург, ул. Политехническая, д. 21, 9-й учебный корпус, ауд. 325.

С диссертацией можно ознакомиться в фундаментальной библиотеке ФГБОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Автореферат разослан "(Г" 20{Ъг.

Ученый секретарь

диссертационного совета Д 212.229.18

к.т.н., доцент Г^Х > Васильев Алексей Евгеньевич

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

Актуальность работы. Развитие микропроцессорной техники в современных условиях тесно связано с использованием концепции многоядерности. На сегодняшний день сформировалось два направления: создание однородных многоядерных процессоров, в которых все ядра архитектурно идентичны и функционально симметричны, а также создание неоднородных многоядерных процессоров (НМП), в которых кристалл включает ядра, имеющие различную архитектуру и предназначенные для решения своего круга задач. Среди представителей НМП можно выделить процессоры для встраиваемых применений, построенные как «системы-на-кристалле». Вычислительные ядра таких процессоров имеют непосредственный доступ только к своей локальной памяти, объем которой составляет от нескольких десятков до нескольких сотен килобайт. В состав ВС входит модуль основной оперативной памяти объемом до одного гигабайта, в котором размещаются код и данные программы. Основным отличием указанных СнК является наличие независимо работающих ядер, предназначенных для организации информационного обмена (ЯОИО) между различными модулями памяти ВС. Основной проблемой в таких системах является организация параллельной обработки больших массивов данных в рамках локальной памяти вычислительных ядер с необходимостью явной организации информационного обмена.

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

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

параллельных программ, значительный вклад внесли такие ученые как Джек Донгарра, Фрэд Густавсон, Чарльз Лэйзерсон и др. Значительный вклад в развитие отечественных многоядерных структур, а также проектирование высокопроизводительных программных комплексов для них, внесли Я.Я. Петричкович, Т.В. Солохина, Ю.Н. Александров, A.A. Беляев, В.Д. Глушков, В.Ф. Никольский и др.

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

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

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

Задачи исследования.

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

2. исследовать существующие методы построения пакетов прикладных программ для многоядерных «систем-на-кристалле», выявить их преимущества и недостатки;

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

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

5. разработать формальную модель НМСнК;

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

Методы исследования. При разработке метода построения высокопроизводительных ППП использован аппарат теории графов и гиперграфов, теории множеств и теории расписаний. При синтезе макро-потоковых графов используется формализм графов потоков данных (data-flow graphs), при распределении ресурсов используется эвристический метод листового планирования.

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

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

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

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

также наличие ЯОИО, способных вести обмен асинхронно по отношению к обработке данных вычислительными ядрами;

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

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

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

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

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

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

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

Внедрение и реализация результатов работы. Основные результаты диссертационной работы использованы в ОАО НПЦ "ЭЛВИС" и ФНПЦ ОАО «НПО «Марс». Реализация научных положений и результатов диссертационной работы подтверждена соответствующими документами о внедрении.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на конференциях: «IX Международная научная конференция, посвященная 45-летию Снб. гос. аэрокосмич. ун-та имени акад. М.Ф.Решетнева» (2005 год), «IEEE Tenth International Symposium on Consumer Electronics» (2006 год), «Шестой международный научно-практический семинар и молодежная школа «Высокопроизводительные параллельные вычисления на кластерных системах»» (2006 год), «Всероссийский форум студентов, аспирантов и молодых ученых «Наука и инновации в технических университетах» (2007 год), «7lh conference of open innovations framework program FRUCT» (2010 год), «11th conference of open innovations framework program FRUCT» (2012 год).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, списка использованных источников и девяти приложений. Диссертация содержит 174 страницы машинописного текста, включая 33 рисунка и 16 таблиц, а также приложения объемом 86 страниц, включая 25 рисунков и 5 таблиц. В списке использованной литературы 127 наименований.

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

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

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

Неоднородный многоядерный процессор

Упр. ядро

Управление

Сигнал завершения |

111111 '.....-

Выч.

ядра

ВМЛ-ядра

Локальная память

ЩЯт"

лп к

Рисунок 1. Обобщенная структурная схема НМП

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

1. модуль основной ОП имеет размер от нескольких Мб до нескольких сотен Мб;

2. локальная память вычислительного ядра имеет объем от нескольких десятков до сотен Кб;

3. управляющее ядро, имеет доступ ко всем ключевым ресурсам системы;

4. каждое вычислительное ядро имеет доступ только к локальной памяти;

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

6. для организации информационного обмена между различными модулями памяти требуется привлечение ЭМА-ядер (ЯОИО);

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

8. ОМА-ядра способны работать асинхронно по отношению к работе других компонентов ВС.

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

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

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

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

Исходные

тексты программы

Рисунок 2. Укрупненная схема метода синтеза программы

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

Определение 1. Макро-потоковый граф - размеченный ориентированный ациклический граф потоков данных Од = <Уа> ЕА> с дополнительным разбиением всего множества акторов УА на множество акторов передачи данных Уц и множество вычислительных акторов Ус. Правила срабатывания акторов такие же, как в модели статических потоков данных. Разметка акторов позволяет адекватно описать процесс параллельной обработки блоков данных.

ю

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

вычислительной гранулы;

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

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

Необходимым условием применимости разработанного метода построения ППП является существование формулы в блочных обозначениях, на вид которой наложены дополнительные ограничения, указанные в работе. По формуле Р с использованием методики С0^ткист_Р0Ь0Е0_0яАРН строится графовое представление обобщенной задачи обработки матриц - «свернутый» граф.

Определение 2: «Свернутый» граф - размеченный ориентированный граф Ов = <УВ, Ев>. Все множество вершин графа вв можно разделить на взаимно-непересекающиеся подмножества Ув = У0и УсиУаиВиЕиЦ где: Ун - акторы передачи данных, Ус - вычислительные акторы, V,, -константные акторы, В - акторы, генерирующие управляющие токены, Е -акторы, поглощающие токены, Ь - вершины-циклы. Множество дуг можно разделить на взаимно-непересекающиеся подмножества Ев = Е0 и Ес, где: Е0 -дуги передачи данных, Ес - дуги передачи управления.

Ключевым элементом, на базе которого строится любой «свернутый» граф, является вершина-цикл (У|, на рис. 3). Назначение вершины-цикла заключается в представлении процесса перебора значений одной координатной переменной в аналитической записи решения задачи. Каждому квантору общности, а также каждому знаку сокращенной суммы (X) в формуле ставится

п

Сь1

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

Представленный на рис. 3 «свернутый» граф соответствует следующей формуле:

У,! = 2>ij Xj + yi Viel

Vje J

, где A e RM x N, x e RN, у e RM, I и J — множества блочных координат.

В результирующем «свернутом» графе (см. рис. 3) квантору общности соответствует подграф Gl', знаку сокращенной суммы - подграф Gl2, равенству - подграф Ggr. Константные акторы (v2-v4, v8-v|0) задают границы и шаг изменения координатных переменных i и j.

Construct_Folded_Graph(F)

1 Добавить актор Vb е В и запомнить его

2 while в формуле F есть элементы do

3 if встретилась область действия V then

4 Добавить подграф GL, отражающий перебор значений координатной переменной и запомнить V|, соответствующую V

5 Добавить связи с другими вершинами-циклами (vi)

6 else if встретилось = без знака Е then

7 Добавить Gg,- и запомнить его

8 else if встретилось = со знаком Е then

9 Добавить подграф Gl, отражающий перебор значений переменной суммирования и запомнить V|, соответствующую Е

10 Добавить связи с другими V|

11 Добавить Ggr

12 Связать Gl и Ggr дугами

13 end if

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

15 if закончилась область действия V then

12

16 Связать дугой последний запомненный элемент и V|, соответствующую v, и запомнить V|

17 end if

18 end while

19 Добавить актор vc 6 E

20 Связать дугой последний запомненный элемент и vc

Методика Construct_Folded_Graph обладает важным свойством, указанным ниже.

Лемма 1. Для любой заданной формулы F, удовлетворяющей ограничивающим условиям, используя методику Construct_Folded_Graph, можно построить конечный «свернутый» граф GB.

Доказательство указанного свойства приведено в работе.

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

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

Macroflow_Graph_Synth(Gb, Q)

1 while в графе есть вершина-цикл vi do

2 Произвести «развертку» вершины-цикла V|

3 if вершина-цикл V| соответствует Z then

4 Произвести «склейку» соответствующих акторов передачи данных

5 end if

6 end while

7 Произвести «склейку» оставшихся акторов передачи данных

8 Удалить из графа все вспомогательные элементы

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

13

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

Алгоритм МАСЯОРШи^ОяАР^БУМТН обладает указанными далее свойствами.

Теорема 1. При использовании алгоритма Маскоршш_Окарн_8уытн по заданному кортежу параметров индивидуальной задачи О. и соответствующему ему «свернутому» графу Ов, построенному по методике СО1зтаист_Р01.0Е0_0яАРН всегда можно построить конечный макро-потоковый граф Од.

Теорема 2. Макро-потоковый граф Од, построенный с использованием алгоритма МасяорьсжОяар^Зумтн, является адекватным представлением индивидуальной задачи, которой соответствует формула Р, при условии, что ранее по Р был построен «свернутый» граф Ов и задан соответствующий ему кортеж параметров индивидуальной задачи О.

Доказательство указанных свойств приведено в работе.

Третья глава посвящена задаче распределения ресурсов НМП. Вводятся понятия гиперграфовой модели процессора и расписания. Представлено описание предложенного многоэтапного метода распределения ресурсов и детально рассмотрен каждый из этапов. Приведены и доказаны основные свойства предложенного метода.

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

По синтезированному ранее макро-потоковому графу, с использованием гиперграфовой модели НМП Нр = <Ур, Ер> производится распределение его ресурсов и строится расписание. В модели процессора управляющие ядра Бр с Ур, вычислительные ядра Ср с Ур и ЭМА-ядра Ор с Ур, а также модули памяти Мр с Ур представлены вершинами. Каналы информационного обмена Ер,ео с Ер, работающие под управлением специализированных ядер, представлены ориентированными гипердугами е; = <Ш|, с!ь т2>, каждая из которых инцидентна двум вершинам ГП|, пъ е Мр, представляющим модули

14

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

Рисунок 4. Структурная схема процессора МС24

Для процессора МС24, структурная схема которого представлена на рис.4, структура множества Vp следующая: Sp = {s,}, Ср={с,}, Dp={d|}, Мр = {гП|, ш2, m3, mi, m5}, Ep,ed = {<ш2, d,, т3>, < т2, db пг,>, < ш2, db ш5>, < т,, d|, ш2>} . При этом, соответствие между вершинами из Мр и модулями памяти следующее: ш, - CRAM, m2 - внешняя память, ш3 - PRAM, m, - XRAM, ш5 -YRAM. Поскольку память CRAM не участвует в обработке данных, каналы информационного обмена с ее участием в модели Нр не отражены.

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

Resource_Alloc(Ga, hp)

1 Оценить достаточное количество памяти

2 Выделить память под буферы

3 Распределить вычислительную нагрузку

4 Произвести реструктуризацию макро-потокового графа

5 Организовать подкачку кода вычислительных гранул

6 Распределить информационные обмены

7 Распределить пространство буферов

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

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

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

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

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

Использование описанного выше правила не оказывает сильного влияния на длительность расписания при справедливости следующих

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

Для распределения обменов данными сначала все обмены распределяются по этапам обработки данных, затем - внутри этапов, учитывая присущий транспортной подсистеме параллелизм. Далее представлен алгоритм межэтапного распределения обменов данными. Transfer_To_Stage_Map(Ga, Нр)

1 Выделить из VD множества Q и L // Составить одноименные списки

2 for all v, из L do

3 Произвести оценку значений gmin, gmax

4 end for

5 Произвести сортировку списка L в порядке невозрастания значений

Cinin

6 Упорядочить этапы согласно максимуму вычислительной нагрузки в невозрастающем порядке следования значений

7 for all этапов do // С номером i при просмотре слева-направо

8 Построить список S акторов из L, которые могут сработать в течение i-ro этапа

9 Произвести сортировку S в порядке невозрастания времени передачи данных

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

11 end for

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

13 Распределить акторы из Q максимально «приближая» обмен данными к их обработке

В алгоритме Transfer_To_Stage_Map используются следующие обозначения: множество L = VD\QuM, Q = Qin u Qout, Qin содержит акторы, соответствующие начальной загрузке данных в локальную память с

17

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

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

?min> ^max* ^D —> Zo ,

где qmjn - точная «левая» граница интервала р, сп„х - точная «правая» граница р. Правила оценки границ интервала р приведены в работе.

Per_Stage_Transfer_Sequencing(Ga, Hp)

1 Составить список D

2 Упорядочить D по невозрастанию номеров этапов

3 for all этапов do // С номером i при просмотре слева-направо

4 Составить список R

5 Составить список Q

6 Упорядочить Q по невозрастанию суммарного времени обмена в каждой группе

7 while в Q есть группы do

8 Найти первую группу gj, для которой количество конфликтующих с ней групп из L минимально

9 Назначить акторы из gj на DMA-ядро, обеспечивающее минимум конфликтов и при этом - мпппмалыюе время запуска

10 Увеличить время освобождения выбранного DMA-ядра

11 Назначить акторам из gj номера заданий в очереди

12 Увеличить номер нового задания выбранного DMA-ядра

13 Добавить gj в L

14 Удалить gj из Q

15 end while

16 end for

В алгоритме Per_Stage_Transfer_Sequencing приняты следующие обозначения: D - список всех акторов передачи данных, соответствующих

18

обменам, требующим привлечения DMA-ядра; R - список, содержащий все акторы передачи данных, срабатывающие в течение заданного этапа; Q -список, содержащий все группы (группировка по каналам информационного обмена) акторов передачи данных, требующие распределения по DMA-ядрам в рамках заданного этапа; L - список, содержащий К групп акторов передачи данных, распределенных ранее, где К равно количеству DMA-ядер в процессоре.

Для описанного алгоритма распределения ресурсов НМП справедлива указанная ниже теорема.

Теорема 3. Расписание, построенное с использованием алгоритма Resource Alloc, является допустимым.

Доказательство теоремы приведено в работе.

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

Для вычислительно-емких подпрограмм (strsm, sgemm) были получены следующие экспериментальные результаты:

- ускорение при распараллеливании вычислений на два ядра процессора МС0226 составляет от 1,42 для strsm с размерностью 152 элемента, до 1,97 для sgemm с размерностью 168 элементов;

- производительность подпрограммы sgemm при использовании двух вычислительных ядер процессора МС0226 составляет: 233 МФлоп/с (72,8% от пиковой производительности двух ядер, что составляет 85% от максимальной производительности двух гранул) для размерности задачи равной 84 элементам и 264 МФлоп/с (82,5% от пиковой производительности двух ядер, что составляет 96,4% от максимальной производительности двух гранул) для размерности задачи равной 168 элементов. Разрыв между производительностью гранул и производительностью программы обусловлен наличием синхронизации, подкачки данных в начале и отвода результатов в конце процесса их обработки и не может быть сокращен.

Ускорение вычислений (sgemm)

Ускорение вычислений (strsm)

Линейное ус к о р с* H и о Ускорение N = 16 »•••Ускорение N = 12 ■&■■■ Ускорение N = R

Ж

: Ж Ж'

Линейное ускорение Ускорение N = 1 <> Ускорение N = 12 Ускорение N = М

1 2 3 4 5 6 7 8 9 1011 1213 14 15 16 Количество ядер (ее)

12 3 4 5 6 7 8 9 10 11 12 1314 15 16 Количество ядер (се)

Рисунок 5. Графики масштабирования вычислений

В результате имитационного моделирования поведения подпрограмм sgemm и БЬят на синтетической модели процессора, содержащей 16 вычислительных ядер, получены следующие результаты:

- масштабируемость указанных подпрограмм близка к линейной (см. рис. 5, где N - блочная размерность задачи);

- производительность подпрограммы вйът достигает 91% от производительности вычислительной гранулы 8§етш.

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

- перенос прототипа ППП между процессорами МС24 и МС0226 потребовал изменения менее чем 0,5% от общего объема инструментальных средств пакета;

- добавление в прототип каждой из четырех подпрограмм потребовало добавления менее чем 1,5% от общего объема инструментальных средств пакета для каждой подпрограммы.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты работы можно сформулировать следующим образом:

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

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

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

4. предложена методика построения экземпляров модели обобщенной задачи обработки двумерных числовых матриц;

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

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

7. предложена гиперграфовая модель неоднородного многоядерного процессора, отражающая устройство транспортной подсистемы и подсистемы памяти;

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

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

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

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

1. расширение класса задач обработки матриц за счет совершенствования метода синтеза формального представления индивидуальной задачи;

2. отказ от использования барьерной синхронизации процессов;

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

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

5. оценка отклонения длины расписания от длины оптимального расписания;

6. совершенствование метода распределения ресурсов неоднородного многоядерного процессора.

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

1. Недоводеев К.В. Метод генерации графов потоков данных, нснользуемых при автоматическом синтезе параллельных программ для неоднородных многоядерных процессоров // Научно-технические ведомости СПбГПУ. - 2012. - №3. - Т. 2. - С. 47-52.

22

2. Nedovodeev K.V. Adaptive libraries for multicore architectures with explicitly-managed memory hierarchies // 11th conference of open innovations framework program FRUCT: conference proceedings. - Saint-Petersburg: SUAI, 2012. - P. 126135.

3. Nedovodeev K.V. Self-adapting software as a means of meeting the multicore challenge // 7lh conference of open innovations framework program FRUCT: conference proceedings. - Saint-Petersburg: SUAI, 2010. - P. 83-86.

4. Недоводеев K.B. Метод синтеза блочного алгоритма по его графовому представлению // Научно-технические ведомости СПбГПУ. - 2007. - №4. -Т. 2.-С. 141-148.

5. Недоводеев К.В. Применение модели потоков данных для описания (макро)блочных алгоритмов // Всероссийский форум студентов, аспирантов и молодых ученых «Наука и инновации в технических университетах»: материалы всероссийского форума. - СПб: Изд-во СПбГПУ, 2007. - С. 53-54.

6. Недоводеев К.В. Организация (макро)потоковых вычислений в неоднородных мультиядерных процессорах // Высокопроизводительные параллельные вычисления на кластерных системах: сб. науч. тр. / под ред. проф. Р.Г. Стронгина - СПб.: Изд-во СПбГУ, 2007. - Т. 2. - С. 72-77.

7. Недоводеев К.В., Шейнин Ю.Е. Высокопроизводительная обработка больших массивов данных в неоднородных мультиядерных процессорах // Электронные компоненты. -2006. -№9. - С. 116-122.

8. Nedovodeev KV. Multimedia Data Processing On Dual-Core Soc Multicore-24 // IEEE Tenth International Symposium on Consumer Electronics (ISCE 2006): conference proceedings. - NY: IEEE, 2006. - P. 142-147.

9. Недоводеев К.В. Организация взаимодействия RISC- и DSP-ядер сверхбольшой интегральной схемы «Мультикор» в задачах обработки сигналов // IX Междунар. науч. конф. посвящ. 45-летию Сиб. гос. аэрокосмич. ун-та имени акад. М.Ф. Решетнева: материалы междунар. науч. конф.. -Красноярск: Изд-во СибГАУ, 2005. - С. 293-294.

Подписано в печать 15.11.2012. Формат 60x84/16. Печать цифровая. Усл. печ. л. 1,0. Тираж 100. Заказ 9952Ь.

Отпечатано с готового оригинал-макета, предоставленного автором, в типографии Издательства Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29. Тел.: (812)550-40-14 Тел./факс: (812) 297-57-76

ВВЕДЕНИЕ.

ГЛАВА 1. ОРГАНИЗАЦИЯ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ ДЛЯ

МНОГОЯДЕРНЫХ АРХИТЕКТУР.

1.1 Архитектура неоднородных многоядерных процессоров.

1.1 Л Архитектура многоядерных процессоров семейства «Мультикор».

1.1.2 Архитектура процессора CELL.

1.1.3 Архитектура процессоров фирм Texas Instruments, Atmel.

1.2 Современный подход к построению пакетов программ.

1.2.1 Язык параллельного программирования Cilk.

1.2.2 Среда поддержки программирования CellSs.

1.2.3 Язык параллельного программирования Sequoia.

1.2.4 Программные каркасы PLASMA и MAGMA.

ВЫВОДЫ ПО ГЛАВЕ 1.,

ГЛАВА 2. СИНТЕЗ ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ ПРОГРАММЫ.

2.1 Организация обработки данных в многоядерном процессоре.

2.1.1 Внутренняя организация программы.

2.1.2 Проблема автоматического синтеза программы.

2.2 Представление индивидуальной задачи.

2.2.1 Макро-потоковый граф.

2.3 Аналитическая запись решения задачи.

2.3.1 Свойства формул.

2.3.2 Задачи алгебры матриц.

2.3.3 Пример построения формулы для задачи алгебры матриц.

2.4 Представление обобщенной задачи.

2.4.1 «Свернутый» граф.

2.4.2 Методика построения «свернутого» графа.

2.5 Синтез макро-потокового графа.

2.5.1 «Развертка» вершин-циклов.

2.5.2 «Склейка» подграфов.

2.5.3 Алгоритм синтеза макро-потокового графа.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3. РАСПРЕДЕЛЕНИЕ РЕСУРСОВ ПРОЦЕССОРА.

3.1 Модель вычислительной системы.

3.2 Распределение вычислительной нагрузки.

3.2.1 Построение списка вычислительных акторов.

3.2.2. Метод листового планирования.

3.2.3 Организация подкачки гранул.

3.2.4 Реструктуризация макро-потокового графа.

3.3 Распределение информационных обменов.

3.3.1 Распределение обменов по этапам.

3.3.2 Распределение обменов внутри этапов.

3.4 Распределение памяти.

3.4.1 Исключение фрагментации буферов данных.

3.4.2 Распределение пространства буферов данных.

3.4.3 Верхняя оценка нужного количества локальной памяти.

3.4.4 Верхняя оценка размера временного буфера.

3.4.5 Распределение пространства временного буфера.

3.5 Свойства построенного расписания.

3.5.1 Допустимость построенного расписания.-.

3.5.2 Верхняя оценка длины расписания.

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И ОЦЕНКА ЭФФЕКТИВНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ.

4.1 Анализ данных экспериментов.

4.1.1 Эксперименты с программой SGEMM.

4.1.2 Эксперименты с программой SGEMV.

4.1.3 Эксперименты с программой STRSV.

4.1.4 Эксперименты с программой STRSM.

4.2 Анализ масштабируемости.

4.2.1 Описание имитационной модели.

4.2.2 Модели многоядерных процессоров.

4.2.3 Анализ масштабируемости SGEMM.

4.2.4 Анализ масштабируемости STRSM.

ВЫВОДЫ ПО ГЛАВЕ 4.

Развитие микропроцессорной техники в современных условиях тесно связано с использованием концепции многоядерности. На сегодняшний день сформировалось два направления: создание однородных многоядерных процессоров, в которых все ядра архитектурно идентичны и функционально симметричны, а также создание неоднородных многоядерных процессоров (НМЛ), в которых кристалл включает ядра, имеющие различную архитектуру и предназначенные для решения своего круга задач. Среди представителей НМЛ можно выделить процессоры для встраиваемых применений, построенные как «системы-на-кристалле». Вычислительные ядра таких процессоров имеют непосредственный доступ только к своей локальной памяти, объем которой составляет от нескольких десятков до нескольких сотен килобайт. В состав ВС входит модуль основной оперативной памяти объемом до одного гигабайта, в котором размещаются код и данные программы. Основным отличием указанных СнК является наличие независимо работающих ядер, предназначенных для организации информационного обмена (ЯОИО) между различными модулями памяти ВС. Основной проблемой в таких системах является организация параллельной обработки больших массивов данных в рамках локальной памяти вычислительных ядер с необходимостью явной организации информационного обмена.

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

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

После появления многоядерных процессоров усилилась тенденция перехода от использования явного потока управления на уровне крупных фрагментов задачи к использованию модели потоков данных, которая позволяет гибко подстраивать вычислительный процесс под имеющиеся ресурсы ВС. Одними из первых работ, посвященных изучению модели потоков данных применительно к построению программно-аппаратных комплексов, являются работы Алана Дэвиса и Джека Денниса, содержащие описание модели вычислений, формализма графов потоков данных и архитектуры с поддержкой исполнения программ, представленных в графовой форме. В изучение вопросов, связанных с эффективной организацией высокопроизводительных ППП и разработкой средств поддержки создания параллельных программ, значительный вклад внесли такие ученые как Джек Донгарра, Фрэд Густавсон, Чарльз Лэйзерсон и др. Значительный вклад в развитие отечественных многоядерных структур, а также проектирование высокопроизводительных программных комплексов для них внесли Я.Я. Петричкович, Т.В. Солохина,

Ю.Н. Александров, A.A. Беляев, В.Д. Глушков, В.Ф. Никольский и др.

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

Объектом исследования в данной работе являются неоднородные многоядерные СнК, а предметом исследования - методы построения высокопроизводительных ППП, предназначенных для обработки больших массивов данных в рамках таких систем.

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

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

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

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

- исследовать существующие методы построения пакетов прикладных программ для многоядерных систем на кристалле, выявить их преимущества и недостатки;

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

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

- разработать формальную модель НМСнК;

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

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

При синтезе макро-потоковых графов используется формализм графов потоков данных (data-flow graphs), при распределении ресурсов используется эвристический метод листового планирования.

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

1. модель обобщенной задачи обработки двумерных числовых матриц -«свернутый» граф;

2. методика построения «свернутого» графа по формуле в блочных обозначениях;

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

4. метод синтеза макро-потокового графа для индивидуальной задачи по «свернутому» графу;

5. гиперграфовая модель неоднородного многоядерного процессора;

6. эвристический метод распределения ресурсов неоднородного многоядерного процессора;

7. экспериментальное исследование характеристик ППП, построенного с применением предложенного в работе метода.

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

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

• предложена методика построения «свернутого» графа по формуле в блочных обозначениях; предложена модель системы заданий - макро-потоковый гоаф. отражающая необходимость проведения обработки данных в рамках локальной памяти вычислительного ядра, имеющей малый объем, а также наличие ЯОИО, способных вести обмен асинхронно по отношению к обработке данных вычислительными ядрами;

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

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

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

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

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

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

• распределение ресурсов в ППП производится на основании формальной модели НМСнК. На вход инструментария подается текстовый файл с описанием модели, что позволяет расширять возможности ППП на новые системы без дописывания, перекомпиляции и повторной сборки инструментальных средств;

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

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

Реализация

Основные результаты диссертационной работы использованы в ОАО НПЦ "ЭЛВИС" и ФНПЦ ОАО «НПО «Марс». Реализация научных положений и результатов диссертационной работы подтверждена соответствующими документами о внедрении.

Апробация работы

Основные положения и результаты диссертации докладывались и обсуждались на конференциях: «IX Международная научная конференция, посвященная 45-летию Сиб. гос. аэрокосмич. ун-та имени акад. М.Ф.Решетнева» (2005 год), «IEEE Tenth International Symposium on Consumer Electronics» (2006 год), «Шестой международный научно-практический семинар и молодежная школа «Высокопроизводительные параллельные вычисления на кластерных системах»» (2006 год), «Всероссийский форум студентов, аспирантов и молодых ученых «Наука и инновации в технических университетах» (2007 год), «7th conference of open innovations framework program FRUCT» (2010 год), «11th conference of open innovations framework program FRUCT» (2012 год).

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

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

Основные результаты работы можно сформулировать следующим образом:

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

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

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

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

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

6. предложена гиперграфовая модель неоднородного многоядерного процессора, отражающая устройство транспортной подсистемы и подсистемы памяти;

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

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

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

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

1. расширение класса задач обработки матриц за счет совершенствования метода синтеза формального представления индивидуальной задачи;

2. отказ от использования барьерной синхронизации процессов;

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

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

5. оценка отклонения длины расписания от длины оптимального расписания;

6. совершенствование метода распределения ресурсов неоднородного многоядерного процессора.

Заключение

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

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

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

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

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

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

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

В четвертой главе представлен анализ результатов экспериментальных исследований, проведенных с использованием разработанного автором инструментария. Полученные результаты подтверждают эффективность предложенного метода построения ППП как по производительности генерируемых подпрограмм, так и по легкости сопровождения и расширения возможностей ППП. Так, например, ускорение ключевой подпрограммы умножения матриц, входящей в состав библиотеки BLAS, при распараллеливании на два вычислительных ядра процессора МС0226 оказывается близко к линейному (1,97) уже при размерности задачи равной 168 элементам. Подпрограмма матричного умножения линейно распараллеливается на 16 вычислительных ядер, а подпрограмма решения СЛАУ с несколькими правыми частями ускоряется более чем в 13 раз, достигая при этом 91% от производительности гранулы матрично-матричного умножения, работающей в идеальных условиях на всех вычислительных ядрах. Портирование разработанного прототипа ППП с процессора МС24 на процессор МС0226 потребовало изменения менее чем 0,5%), а добавление каждой из подпрограмм - добавления менее чем 1,5% от общего объема инструментальных средств пакета.

1. A tuning framework for software-managed memory hierarchies / M. Ren, J.Y. Park, M. Houston etc. // 17th international conference on Parallel architectures and compilation techniques: conference proceedings. NY: ACM, 2008.-P. 280-291.

2. A Comparison of Empirical and Model-driven Optimization / K. Yotov, X. Li, G. Ren etc. // Programming Language Design and Implementation (PLDI'03): conference proceedings. NY: ACM, 2003. - P. 63-76.

3. AMBA™ specification. Rev. 2.0: сайт компании ARM.- 1999 Электронный ресурс. URL: http://www.arm.com (дата обращения: 19.08.2012).

4. Ant colony optimization for mapping and scheduling in heterogeneous multiprocessor systems / A. Tumeo, C. Pilato, F. Ferrandi etc. // ICSAMOS International Conference: conference proceedings. NY: IEEE, 2008. - P. 142149.

5. AT572D940HF. Preliminary Summary: сайт компании Atmel. 2007 Электронный ресурс. URL: www. atmel. com/ dyn/ resources/proddocuments/7 010 s .pdf (дата обращения: 19.08.2012).

6. AT572D940HF. Preliminary: сайт компании Atmel. 2008,-Электронный ресурс. URL: http://www.atmel.com/dyn/resources/proddocuments/doc7010.pdf (дата обращения: 19.08.2012).

7. Bailey D., Snavely A. Performance modeling, metrics, and specifications // Workshop on the Roadmap for the Revitalization of High-End Computing: workshop proceedings. Washington, D.C: CRA, 2003. - P. 59-68.

8. Basic Linear Algebra Subprograms Technical (BLAST) Forum Standard. -Knoxville: University of Tennessee, 2001 Электронный ресурс. URL: www.netlib.org/blas/blast-forum/blas-report.pdf (дата обращения: 19.08.2012).

9. Cao L. Singular value decomposition applied to digital image processing. -Arizona: Arizona State University Polytechnic Campus Электронный ресурс. URL: http://www.lokminglui.com/CaoSVDintro.pdf (дата обращения: 19.08.2012).

10. Cell broadband engine. Programming handbook. NY: IBM, 2007. - 877 p. Электронный ресурс. URL: www.daimi.au.dk/~zxr/papers/CBEHandbookv 1. l24APR2007pub.pdf (дата обращения: 19.08.2012).

11. CellSs: a Programming Model for the Cell BE Architecture / P. Bellens, J.M. Perez, R. Badia etc. // 2006 ACM/IEEE conference on Supercomputing: conference proceedings. Tampa, Florida, November 2006.

12. Cilk 5.4.6 Reference Manual. MA: MIT, 2001.- 56 p. Электронный ресурс. URL: http://supertech.lcs.mit.edU/cilk/manual-5.4.6.pdf (дата обращения: 19.08.2012).

13. Cilk: An Efficient Multithreaded Runtime System / R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul etc. // Journal of Parallel and Distributed Computing. 1996. - Vol. 37, No. 1. - P. 55-69.

14. Compilation for Explicitly Managed Memory Hierarchies / T.J. Knight, J. Young, P. Manman etc. // 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming: conference proceedings. NY: ACM, 2007. -P. 226-236.

15. Davis A.L., Keller R.M. Data flow program graphs // IEEE Computer. -1982.-Vol. 15, Issue 2.-P. 26-41.

16. Dennis J.B., Misunas D.P. A preliminary architecture for a basic data-flow processor // 2nd annual symposium on Computer architecture: conference proceedings. NY: ACM, 1975. - P. 126-132.

17. Dense Linear Algebra Solvers for Multicore with GPU Accelerators / S. Tomov, R. Nath, H. Ltaief etc. // IPDPSW 2010. Atlanta, GA, April 2010. P. 1-8.

18. Dongarra J., Wasniewski J. High Performance Linear Algebra Package for FORTRAN 90 // Lecture Notes in Computer Science. 1998. - Vol. 1541. - P. 579-583.

19. Dubey P. Recognition, Mining and Synthesis Moves Computers to the Era of Tera // Technology@Intel Magazine. 2005. - Vol. 9. - P. 1-10.

20. Embedded Microprocessor Benchmark Consortium: каталог продуктов консорциума. 2012 Электронный ресурс. URL: http://www.eembc.org (дата обращения: 19.08.2012).

21. Entering the Petaflop Era: The Architecture and Performance of Roadrunner / K.J. Barker, K. Davis, A. Hoisie etc. // Proc. IEEE/ACM Supercomputing (SC08). Washington, DC: IEEE CS Press, 2008. - P. 1-11.

22. Fet Ya., Pospelov D. Parallel computing in Russia // Lecture notes in computer science. 1995. - Vol. 964. - P. 464-476.

23. FLAME: Formal Linear Algebra Methods Environment / J.A. Gunnels, F.G. Gustavson, G.M. Henry etc. // ACM Transactions on Mathematical Software. -2001. Vol. 27, No. 4. - P. 422-455.

24. Frigo M., Johnson S.G. FFTW: An Adaptive Software Architecture for the FFT // 1998 ICASSP: conference proceedings. NY: IEEE, 1998,- Vol.3.-P. 1381-1384.

25. Frigo M., Leiserson C.E., Randall K.H. The Implementation of the Cilk-5 Multithreaded Language 11 ACM SIGPLAN Notices. 1998. - Vol. 33, Issue 5. -P. 212-223.

26. GeerD. Industry Trends: Chip Makers Turn to Multicore Processors // Computer. 2005. - Vol. 38, No. 5. - P. 11-13.

27. Golub M., Kasapovic S. Scheduling multiprocessor tasks with genetic algorithms // Proceedings of the IASTED International Conference Applied Informatics: conference proceedings. Calgary: ACTA press, 2002. - P. 273-278.

28. GotoBLAS library: домашняя страница проекта. 2008. - 7 февраля Электронный ресурс. URL: http://docs.notur.no/uit/files-uit/math-lib-stuff/gotoblas (дата обращения: 19.08.2012).

29. Hackenberg D. Fast Matrix Multiplication on Cell (SMP) Systems // Сайт технического университета Дрездена. 2007 Электронный ресурс. Дата обновления: 26.02.2012.- URL: http://www.tu-dresden.de/zih/cell/matmul (дата обращения: 19.08.2012).

30. Hennesy J.J., Patterson D.A. Computer architecture: A quantitative approach. 2nd edition. - San Francisco: Morgan Kaufman, 1996. - 1000 p.

31. Heterogeneous chip multiprocessors / R. Kumar, D.M. Tullsen, N.P. Jouppi etc. // Computer. 2005. - Vol. 38, No. 11. - P. 32-38.

32. Hopcroft J., TaijanR. Efficient algorithms for graph manipulation // Communications of the ACM. 1973. - Vol. 16, No. 6. - P. 372-378.

33. Intel® Math Kernel Library (Intel® MKL): домашняя страница проекта Электронный ресурс. URL: http://software.intel.com/en-us/articles/intel-mkl (дата обращения: 19.08.2012).

34. Introduction to the Cell multiprocessor / J.A. Kahle, M.N. Day, H.P. Hofstee etc. // IBM Journal of Research and Development. 2005. - Vol. 49, No. 4/5.-P. 589-604.

35. Kaur K., Chhabra A., Singh G. Heuristics based genetic algorithm for scheduling static tasks in homogeneous parallel system // International journal of Computer Science and Security. 2010. - Vol. 4, Issue 2. - P. 183-198.

36. Kim S.J., Browne J.C. A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures // International Conference on Parallel Processing: conference proceedings. PA: Pennsylvania State University Press, 1988.-Vol. 3.-P. 1-8.

37. Kurzak J., Buttari A., Dongarra J. Solving Systems of Linear Equations on the CELL Processor Using Cholesky Factorization // IEEE Transactions on Parallel and Distributed Systems. 2008. - Vol. 19, No. 9. - P. 1175-1186.

38. Kurzak J., Dongarra J. Fully Dynamic Scheduler for Numerical Computing on Multicore Processors. Knoxville: University of Tennessee, 2009 Электронный ресурс. URL: http://icl.cs.utk.edu/newspub/submissions/lawn220.pdf (дата обращения: 19.08.2012).

39. Kurzak J., Dongarra J. Implementation of Mixed Precision in Solving Systems of Linear Equations on the Cell Processor // Concurrency and Computation: Practice and Experience. 2007.- Vol. 19, Issue 10.- P. 13711385.

40. Kurzak J., Dongarra J. Implementing Linear Algebra Routines on Multi-Core Processors with Pipelining and a Look-Ahead // Lecture Notes in Computer Science. 2007. - Vol. 4699. - P. 147-156.

41. Kurzak J., Dongarra J. QR Factorization for the CELL Processor. -Knoxville: University of Tennessee, 2008 Электронный ресурс. URL: www.netlib.org/lapack/lawnspdf/lawn201.pdf (дата обращения: 19.08.2012).

42. KurzakJ., Tomov S., DongarraJ. Autotuning GEMMs for Fermi. -Knoxville: University of Tennessee, 2011 Электронный ресурс. URL: icl.cs.utk.edu/newspub/submissions/lawn245.pdf (дата обращения: 19.08.2012).

43. Kwok Y.-K., Ahmad I. Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors // IEEE Transactions on parallel and distributed systems. 1996. - Vol. 7, Issue 5. - P. 506-521.

44. Kwok Y.-K., Ahmad I. On multiprocessor task scheduling using efficient state space search approaches // Journal of Parallel and Distributed Computing. -2005.-Vol. 65, No. 12.-P. 1515-1532.

45. Kwok Y.-K., Ahmad I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors // ACM Computing Surveys. 1999. -Vol. 31, No. 4.-P. 406-471.

46. LAPACK Users' Guide / E. Anderson, Z. Bai, C. Bischof etc. . -Philadelphia: SIAM, 1999 [Электронный ресурс]. URL: http://www.netlib.org/lapack/lug/ (дата обращения: 19.08.2012).

47. Lee E.A., Messerschmitt D.G. Static scheduling of synchronous data flow programs for digital signal processing // IEEE Transactions on computers. -1987. Vol. C-3, No. 1. - P. 24-35.

48. Matrix2png: домашняя страница проекта Электронный ресурс. URL: http://www.chibi.ubc.ca/matrix2png/ (дата обращения: 19.08.2012).

49. Multi-layer АНВ. Overview: сайт компании ARM. 2004 Электронный ресурс. URL: http://www.arm.com (дата обращения: 19.08.2012).

50. Nedovodeev К.V. Adaptive libraries for multicore architectures withthexplicitly-managed memory hierarchies // 11 conference of open innovations framework program FRUCT: conference proceedings. Saint-Petersburg: SUAI, 2012.-P. 126-135.

51. Nedovodeev K.V. Self-adapting software as a means of meeting thethmulticore challenge HI conference of open innovations framework program FRUCT: conference proceedings. Saint-Petersburg: SUAI, 2010. - P. 83-86.

52. Nedovodeev KV. Multimedia Data Processing On Dual-Core Soc Multicore-24 // IEEE Tenth International Symposium on Consumer Electronics (ISCE 2006): conference proceedings. NY: IEEE, 2006. - P. 142-147.

53. Numerical linear algebra on emerging architectures: The PLASMA and MAGMA projects / E. Agullo, J. Demmel, J. Dongarra etc. // Journal of Physics: Conference Series. 2009. - Vol. 180, Issue 1.

54. NVIDIA CUD A Basic Linear Algebra Subroutines (cuBLAS) library: домашняя страница проекта Электронный ресурс. URL: http://developer.nvidia.com/cublas (дата обращения: 19.08.2012).

55. ОМАР59Ю Dual-core processor. Data manual. TX: Texas Instruments, 2004.- 169 p Электронный ресурс. URL: http://www.promelec.ru/pdf/omap5910.pdf (дата обращения: 19.08.2012).

56. Optimization of BLAS on the cell processor / V. Saxena, P. Agrawal, Y. Sabharwal etc. // Lecture Notes in Computer Science. 2008. - Vol. 5374. -P. 18-29.

57. Optimizing matrix multiply using PHiPAC: A Portable, High-performance, ANSI С Coding Methodology / J. Bilmes, K. Asanovic, C.-W. Chin etc. // 11th international conference on Supercomputing: conference proceedings. NY: ACM, 1997.-P. 340-347.

58. Parallel Tiled QR Factorization for Multicore Architectures / A. Buttari, J. Langou, J. Kurzak etc.. Knoxville: University of Tennessee, 2008

59. Электронный ресурс. URL: www.netlib.org/lapack/lawnspdf/lawnl90.pdf (дата обращения: 19.08.2012).

60. Perez J.M., Badia R.M., Labarta J. A flexible and portable programming model for SMP and multi-cores. Barcelona: Barcelona Supercomputing Center, 2007 Электронный ресурс. URL: www.bsc.es/media/994.pdf (дата обращения: 19.08.2012).

61. QuickNet: домашняя страница проекта Электронный ресурс.: Домашняя страница проекта [Электронный ресурс]. URL: http://www.icsi.berkeley.edu/Speech/qn.html (дата обращения: 19.08.2012).

62. Recursive Blocked Data Formats and BLAS's for Dense Linear Algebra Algorithms / F. Gustavson, A. Henriksson, I. Jonsson etc. // PARA98: conference proceedings. Berlin: Springer-Verlag, 1998.-P. 195-206.

63. ScaLAPACK Users' Guide / L.S. Blackford, J. Choi, A. Cleary etc.. -Philadelphia: SIAM, 1997 [Электронный ресурс]. URL: http://www.netlib.org/scalapack/slug/index.html (дата обращения: 19.08.2012).

64. Scheduling Two-sided Transformations using Tile Algorithms on Multicore Architectures / H. Ltaief, J. Kurzak, J. Dongarra etc. // Journal of Scientific Programming. 2010. - Vol. 18, No. 1. - P. 35-50.

65. Scheduling Linear Algebra Operations on Multicore Processors / J. Kurzak, H. Ltaief, J. Dongarra etc.. Knoxville: University of Tennessee, 2009 [Электронный ресурс]. URL: icl.cs.utk.edu/newspub/submissions/lawn213.pdf (дата обращения: 19.08.2012).

66. Scheduling precedence graphs in systems with interprocessor communication times / J.-J. Hwang, Y.-C. Chow, F.D. Anger etc. // SIAM Journal on Computing. 1989. - Vol. 18, No. 2. - P. 244-257.

67. SchneiderS., YeomJ.-S., Nikolopoulos D.S. Programming Multiprocessors with Explicitly Managed Memory Hierarchies // Computer. 2009. - Vol. 42, No. 12.-P. 28-34.

68. Selvan T.V., Chitra M.P., Venkatesh D.P. Parallel implementation of task scheduling using Ant colony optimization // International journal of recent trends in engineering. 2009. - Vol. l,No. 1.-P. 339-343.

69. Sequoia : programming the memory hierarchy / K. Fatahalian, D.R. Horn, T.J. Knight etc. // 2006 ACM/IEEE conference on Supercomputing: conference proceedings. Tampa, Florida, November 2006.

70. Sequoia++ user manual / M. Bauer, J. Clark, E. Schkufza etc.. Stanford: Stanford university, 2010 [Электронный ресурс]. URL: http://sequoia.stanford.edu/source/manual.pdf (дата обращения: 19.08.2012).

71. Sinnen O. Task scheduling for parallel systems. NJ: Wiley, 2007. - 296 p.

72. Smith J., Sohi G. The microarchitecture of superscalar processors // Proceedings of the IEEE. NY: IEEE, 1995. - Vol. 83, Issue 12. - P. 1609-1624.

73. Sriram S.„ Bhattacharyya S.S. Embedded multiprocessors: scheduling and synchronization. NY: Marcel Dekker Inc., 2000. - 353 p.

74. Standard Performance Evaluation Corporation (SPEC): каталог продуктов корпорации Электронный ресурс. Дата обновления: 8.08.2012. URL: http://www.spec.org/index.html (дата обращения: 19.08.2012).

75. Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software // Dr. Dobb's Journal. 2005. - March 1 Электронный ресурс. URL: http://drdobbs.com/web-development/184405990 (дата обращения: 19.08.2012).

76. Synergistic Processing in Cell's Multicore Architecture / M. Gschwind, P. Hofstee, B. Flachs etc. // IEEE Micro. 2006. - Vol. 26, No. 2. - P. 10-24.

77. The Potential of the Cell Processor for Scientific Computing / S. Williams, J. Shalf, L. Oliker etc. // 3rd conference on Computing frontiers (CF'06): conference proceedings. NY: ACM, 2006. - P. 9-20.

78. The impact of multicore on math software / A. Buttari, J. Dongarra, J. Kurzak etc. // Workshop State-of-the-Art in Scientific and Parallel Computing (PARA): conference proceedings. Berlin: Springer-Verlag, 2007. - P. 1-10.

79. Treleaven P., Brownbridge D., Hopkins R. Data-Driven and Demand-Driven Computer Architecture // ACM Computing Surveys (CSUR). 1982. - Vol. 14, Issue l.-P. 93-143.

80. Vaseqhi S.V. Advanced digital signal processing and noise reduction. -4 ed.-Wiley, 2008.-544 p.

81. WhaleyR.C., Petitet A. Minimizing development and maintenance costs in supporting persistently optimized BLAS // Software: practice and experience. -2005. Vol. 35, Issue 2. - P. 101-121.

82. Whaley R.C., Petitet A., Dongarra J.J. Automated Empirical Optimization of Software and the ATLAS project // Parallel Computing. 2001. - Vol. 27, No. 1-2.-P. 3-35.

83. Wu M.-Y., Gajski D.D. Hypertool: a programming aid for message-passing systems // IEEE Transactions on parallel and distributed systems. 1990. - Vol. 1, Issue 3.-P. 330-343.

84. Yang Т., GerasoulisA. DSC: scheduling parallel tasks on an unbounded number of processors // IEEE Transactions on parallel and distributed systems. -1994.-Vol. 5, Issue 9.-P. 951-967.

85. Yi Q., Whaley R.C. Automated transformation for performance-critical kernels // 2007 Symposium on Library-Centric Software: conference proceedings Design.-NY: ACM, 2007.-P. 109-119.

86. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест и др. / под ред. И.В. Красикова. 2-е изд. - М.: Вильяме, 2005. - 1296 с.

87. Виноградов И.М. Математическая энциклопедия.- М.: Сов. энциклопедия, 1977. Том 3. - 1176 с.

88. Воеводин B.B. Математические модели и методы в параллельных процессах. М.: Наука, 1986. - 296 с.

89. Голуб Дж., ВанЛоун Ч. Матричные вычисления. М.: Мир, 1999. -458 с.

90. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982. 416 с.

91. Иванова Г.С. Способы представления структурных моделей // Электронный журнал Наука и образование. 2007. - № 1 Электронный ресурс. URL: http://technomag.edu.ru/doc/62742.html (дата обращения: 19.08.2012).

92. Карпов Ю.Г. Анализ и синтез параллельных информационных процессов на основе свойства когерентности: автореф. дис. . д-ра. техн. наук. Л.: ЛПИ, 1990. - 33 с.

93. Котов В.Е. Сети петри. М.: Наука, 1984. - 157 с.

94. Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978.-432 с.

95. Макконнелл С. Совершенный код. Практическое руководство по разработке программного обеспечения. СПб.: Питер, Русская Редакция, 2007. - 896 с.

96. Микросхемы базовых серий «Мультикор». Сигнальный микроконтроллер 1892ВМ2Т (МС-24) / Т.В. Солохина, Я.Я. Петричкович, Ю.Н. Александров и др. // Chip news. 2005. - №2. - С. 20-31.

97. Недоводеев K.B. Метод генерации графов потоков данных, используемых при автоматическом синтезе параллельных программ для неоднородных многоядерных процессоров // Научно-технические ведомости СПбГПУ. 2012. - №3. - Т. 2. - С. 47-52.

98. Недоводеев К.В. Метод синтеза блочного алгоритма по его графовому представлению // Научно-технические ведомости СПбГПУ. -2007. №4. - Т. 2. - С. 141-148.

99. Недоводеев К.В., Шейнин Ю.Е. Высокопроизводительная обработка больших массивов данных в неоднородных мультиядерных процессорах // Электронные компоненты. 2006. - №9. - С. 116-122.

100. Новая отечественная платформа СБИС «МУЛЬТИКОР» для высокоточной скоростной обработки информации и управления объектами / Ю.Н. Александров, A.A. Беляев, A.B. Глушков и др. //Цифровая обработка сигналов. 2001. -№3.~ С. 15-19.

101. Система программирования отечественной серии сигнальных контроллеров "Мультикор" (начало) / Д. Бочарников, И. Замятин, С. Крысенков и др. // Электронные компоненты. 2005. - № 12. - С. 90-93.

102. Система программирования отечественной серии сигнальных контроллеров "Мультикор" (окончание) / Д. Бочарников, И. Замятин, С. Крысенков и др. // Электронные компоненты. 2006. - № 1. - С. 87-89.

103. Солохина Т., Александров Ю., ГлушковА., и др. Отечественные трехъядерные сигнальные микроконтроллеры с производительностью 1,5 GFlops // Электронные компоненты. 2006, № 6. - С. 73-78.

104. Солохина Т., Александров Ю., Петричкович Я. Сигнальные контроллеры компании «Элвис»: первая линейка отечественных DSP // ЭЛЕКТРОНИКА: Наука, Технология, Бизнес. 2005. - №7. - С. 70-77.

105. Стручков И.В. Распределение и планирование вычислений в многоканальной многопроцессорной системе цифровой обработки сигналов // Системное программирование. 2007. - Вып. 3. - С. 33-53.

106. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

107. Шейнин Ю.Е. Организация параллельных процессов и вычислительных систем для динамических параллельных вычислений: автореф. дис. . д-ра. техн. наук. СПб.: СПбГУАП, 2002. - 36 с.