Презентация "Фрагментированное программирование" по информатике – проект, доклад

Зимняя Школа Параллельного Программирования 2011 Проект «Фрагментированное Программирование» : генератор графа фрагментированной программы для алгоритма блочного умножения матриц

Кудрявцев Владислав ФПМИ, 2 курс

Руководитель: Перепёлкин В.А.

План доклада

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

Постановка задачи

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

Cij =

Идея решения

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

LOAD “*” “+” Store

Реализация

Программа написана на языке С. При выполнении не строит никаких вспомогательных графов. Выводит результат в формате:

Пример выходного файла 24 28 "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 1 1 9 1 1 1 11 1 2 1 10 1 2 1 12 1 …

Тестирование

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

Результаты работы

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

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