Зимняя Школа Параллельного Программирования 2011 Проект «Фрагментированное Программирование» : генератор графа фрагментированной программы для алгоритма блочного умножения матриц Кудрявцев Владислав ФПМИ, 2 курс Руководитель: Перепёлкин В.А.

План доклада 1.Постановка задачи 2.Идея решения 3.Реализация 4.Тестирование 5.Результаты работы

Постановка задачи Даны две матрицы А и B размера N на N каждая. Реализовать блочный алгоритм умножения матриц, сгенерировать граф, вершинами будут являться операции, а ребра – значения переменных, передаваемые от операции к операции. Cij =

Идея решения Выполняемые операции при умножении матриц: Load, * – перемножение двух блоков, + – сложение блоков, Store. Количество Load можно посчитать, как Количество операций * Количество операций + Количество Store LOADLOAD LOADLOAD * + Store

Реализация Программа написана на языке С. При выполнении не строит никаких вспомогательных графов. Выводит результат в формате: Пример выходного файла "LOAD" 1 "LOAD" 2 "LOAD" 3 "LOAD" 4 "LOAD" 5 "LOAD" 6 "LOAD" 7 "LOAD" 8 "*" 1 "*" 2 "*" 3 "*" 4 "*" 5 "*" 6 "*" 7 "*" 8 "+" 1 "+" 2 "+" 3 "+" 4 "STORE" 1 "STORE" 2 "STORE" 3 "STORE" …

Тестирование Программа была протестирована с помощью интерпретатора с использованием матриц размера 4 × 4, 500 × 500, 1500 × Рассчитывалась сумма элементов результирующей матрицы и сравнивалась с верным ответом. Все тесты программа прошла с корректным выходным значением. В качестве интерпретатора использована исполнительная система, реализованная Олегом Багмуцким.

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

Идея решения Количество ребер Ребра, из Load блоков массива А в вершину с операцией * Ребра, из Load блоков массива B в вершину с операцией * Ребра, извязывающие * и операцию + Ребра, связывающие + и операцию Store Ребра, входящие в Store