Методы построения пакетов прикладных программ для неоднородных многоядерных процессоров

• Автор: Недоводеев, Константин Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 275 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ОРГАНИЗАЦИЯ ПАКЕТОВ ПРИКЛАДНЫХ ПРОГРАММ ДЛЯ МНОГОЯДЕРНЫХ АРХИТЕКТУР
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
ВЫВОДЫ ПО ГЛАВЕ
ГЛАВА 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 Алгоритм синтеза макро-потокового графа
ВЫВОДЫ ПО ГЛАВЕ
ГЛАВА 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 Верхняя оценка длины расписания
ВЫВОДЫ ПО ГЛАВЕ
ГЛАВА 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
ВЫВОДЫ ПО ГЛАВЕ
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЕ А. СПИСОК РИСУНКОВ, ТАБЛИЦ, УСЛОВИЙ, ПРАВИЛ,
ТЕОРЕМ И ЛЕММ
ПРИЛОЖЕНИЕ Б. РАЗРАБОТАННЫЕ ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА
ПРИЛОЖЕНИЕ В. ЗАДАЧИ ОБРАБОТКИ МАТРИЦ В BLAS
ПРИЛОЖЕНИЕ Г. ОБЛАСТИ ПРИМЕНЕНИЯ АЛГОРИТМОВ МАТРИЧНОЙ
АЛГЕБРЫ
ПРИЛОЖЕНИЕ Д. ОЦЕНКА ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМА
РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
ПРИЛОЖЕНИЕ Е. АНАЛИЗ ВРЕМЕНИ РАБОТЫ ИНСТРУМЕНТАЛЬНЫХ
СРЕДСТВ
ПРИЛОЖЕНИЕ Ж. АНАЛИЗ ТРУДОЗАТРАТ ПРИ ПОРТИРОВАНИИ ПАКЕТА И
РАСШИРЕНИИ ЕГО ФУНКЦИОНАЛЬНОСТИ
ПРИЛОЖЕНИЕ И. ДАННЫЕ ЭКСПЕРИМЕНТОВ
ПРИЛОЖЕНИЕ К. ДОКУМЕНТЫ, ПОДТВЕРЖДАЮЩИЕ ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

Architectures) [96], а затем и MAGMA (Matrix Algebra on GPU and Multicore Architectures) [9, 24, 64].
Как и прочие исследователи [19,70,89,115], разработчики каркаса PLASMA подчеркивают перспективность использования крупногранулярной модели потоков данных при построении программного обеспечения для многоядерных архитектур [75, 94], поскольку гибкость указанного подхода состоит в присущей этой модели асинхронности выполнения подзадач и способности к подстройке программы под ресурсы аппаратной платформы.
Первым шагом в направлении перехода к модели потоков данных при построении пакетов подпрограмм являлось использование методики опережающего выполнения стадий (look-ahead) в алгоритмах разложения матриц [49]. В указанной работе описано два подхода к распределению вычислительной нагрузки по ядрам процессора: статический и
динамический. При использовании статического подхода, степень «опережения» (look-ahead depth) стадии алгоритма фиксируется до сборки программы, каждому потоку назначается фиксированный набор блочных строк (столбцов), каждый поток выполняет стадии алгоритма разложения в фиксированном порядке, проверяя соблюдение зависимостей по данным с другими потоками с использованием сервисной таблицы (progress table) [49]. При использовании динамического подхода, последовательность выполнения стадий алгоритма разложения в рамках каждого из потоков определяется динамически.
В более поздних работах [2,20,47, 69, 74, 75] содержится более детализированное описание более развитых вариантов организации программ, предназначенных для разложения матриц. В частности, подробно описывается подход, использованный при создании каркаса PLASMA, который состоит в использовании распределения вычислительной нагрузки между потоками, «жестко» закодированного в программе, с конвейеризацией выполнения различных стадий алгоритма разложения матриц. Анализ