Методы построения пакетов прикладных программ для неоднородных многоядерных процессоров тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Недоводеев, Константин Владимирович

• Недоводеев, Константин Владимирович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Недоводеев, Константин Владимирович

ВВЕДЕНИЕ.

ГЛАВА 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% от общего объема инструментальных средств пакета.

Список литературы диссертационного исследования кандидат технических наук Недоводеев, Константин Владимирович, 2012 год

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 с.