Курсовая работа

Задание
Написать вычислительную подпрограмму по заданию варианта.
Реализовать возможность вызова полпрограммы из п.1 в цикле для заданного диапазона размеров матрицы или вектора с заданным шагом приращения размера.
Встроить измерение времени выполнения главной вычислительной операции с помощью таймера с заданным вариантом таймера.
Собрать статистику времени выполнения вычислительной подпрограммы для нескольких уровней оптимизации в выбранном компиляторе. Построить графики зависимости времени выполнения от размеров.
(только для варианта с умножением матриц) провести транспонирование второй матрицы, сделать обход по ней по строкам, повторить для этого варианта реализации п. 4.
векторизовать вычисления в теле самого вложенного цикла вычислительной подпрограммы. Повторить для этого варианта реализации п. 4.
(для всех вариантов, кроме решения системы линейных уравнений) Реализовать многопоточный вариант вычислительной процедуры. Замерить ускорение для различного числа потоков по сравнению с последовательной версией.
(только для скалярного произведения векторов) Объединить векторизованную версию и многопоточную. Оценить полученный выигрыш в производительности по сравнению с последовательной, векторной и многопоточной версиями.

Рекомендации по выполнению работы
Векторизованную версию вычислительной процедуры можно реализовать с помощью SIMD/SSE интринсиков или ассемблерных вставок с SIMD/SSE командами. Если имеется компьютер с процессором с AVX, желательно построить версию на AVX и сравнить выигрыш с SSE.
Многопоточную версию вычислительной процедуры можно реализовать с помощью OpenMP, POSIX Threads или Windows Threads.


Номер варианта Вашего индивидуального задания курсовой работы соответствует последней цифре Вашего пароля (если последняя цифра 0, то вариант - 10).

=============================================

Примерные темы контрольных работ:
№ Наименование темы
1 Умножение двух квадратных матриц. Элементы матрицы имеют тип float
2 Скалярное произведение двух векторов. Элементы векторов имеют тип float
3 Решение системы линейных уравнений методом Гаусса для переменных типа float
4 Умножение двух квадратных матриц. Элементы матрицы имеют тип long
5 Скалярное произведение двух векторов. Элементы векторов имеют тип long
6 Вычисление свертки двух сигналов. Тип элемента, хранящего значение отсчета сигнала, - float
7 Вычисление свертки двух сигналов. Тип элемента, хранящего значение отсчета сигнала, - long
8 Умножение двух прямоугольных матриц. Элементы матрицы имеют тип short
9 Скалярное произведение двух векторов. Элементы векторов имеют тип short
10 Умножение двух квадратных матриц. Элементы матрицы имеют тип unsigned long

Варианты выбора таймера
Предпоследняя цифра Таймер
1,5, 9 Таймер астрономического времени (системный таймер)
2, 6, 0 Монотонный таймер
3, 7 Таймер времени выполнения процесса
4, 8 Счетчик тактов

Вопросы для самоконтроля

На каких принципах базируется архитектура Фон Неймана?
Какие классы архитектур есть по параметру сложности системы команд? Какие преимущества и недостатки главных представителей этих классов?
Какие есть основные алгоритмы отображения в кэш памяти? Какие у каждого из них достоинства и недостатки?
Для CISC и RISC архитектур где проще реализовывать оптимизирующий компилятор? Где проще эффективно загрузить конвейер? В чем могут быть причины того, что существуют и широко используются оба класса архитектур?
Понятие локальности доступа к данным. Какие существуют виды локальности доступа к данным?
Какие обычно присутствуют уровни в иерархической памяти современного компьютера? Какими ключевыми свойствами, параметрами, достоинствами и недостатками они обладают?
Какие основные технологии используются в современных компьютерах для построения внешней памяти? В чем их достоинства и недостатки?
Каково назначение аппаратной предвыборки данных? Как в общих чертах устроен алгоритм ее работы?
К каким уровням иерархической памяти можно получить непосредственный доступ из программы на ассемблере, Си?
Каково назначение кэш памяти? Какие основные характеристики кэш памяти?
Какие алгоритмы отображения применяются в кэш памяти?
Какие используются алгоритмы замещения в кэш памяти?
Что такое пробуксовка кэша? Как она влияет на эффективность программы? Какие программные способы устранения эффекта буксования есть?
Как работает алгоритм проецирования во множественно-ассоциативном кэше?
Каково назначение виртуальной памяти? Как в общих чертах устроен алгоритм ее работы?
Каков принцип работы трансляции виртуальных адресов в физические? Как устроена таблица трансляции? Для чего введен TLB?
Назначение механизма защиты памяти в современном компьютере.
В чем сходства и различия кэш памяти и виртуальной памяти?
Какие технологии построения памяти представляются на данный момент перспективными? Какое влияние может оказать их внедрение на программное обеспечение?
Какие основные виды и уровни параллелизма можно выделить? Какие из них применяются в современном компьютере?
Как представлен SIMD параллелизм в современном микропроцессоре?
Как реализуется параллелизм на уровне команд в современных микропроцессорах? В чем отличия суперскалярной архитектуры и VLIW? В чем достоинства и недостатки каждой их них?
Какие задачи решает многоядерная архитектура? Какова общая структура современного многоядерного процессора? Как в нем организована кэш память?
Какие используются основные показатели производительности компьютеров? Чем отличается реальная производительность от пиковой?
Что такое процесс с ОС? Какое данные хранятся в дескрипторе процесса, в адресном пространстве процесса?
Какую функцию выполняет планировщик задач в ОС? Какие в нем применяются дисциплины?
Какие основные этапы обработки можно выделить у компилятора? В какие моменты происходит оптимизация компилируемой программы?
Каково назначение статических и динамических библиотек? В чем их отличие?
Какие имеются аппаратные средства измерения времени в современном компьютере?
Какие таймеры реализуются в ОС? Каково их назначение и в чем их отличия?
Каково назначение и основные функции профилировщиков?
Какие задачи решает верификатор? Какие виды ошибок можно обнаружить, используя Electric Fence?
Каковы задачи анализа потока управления? Понятие графа потока управления.
Понятия достижимости и доминатора в графе потока управления.
Опишите работу алгоритма поиска обратных дуг.
Уровни оптимизации в GCC. Для чего они введены? Чем они отличаются между собой?
Примеры оптимизационных преобразований в GCC. Назначение и приблизительное функционирование пары оптимизационных преобразований.
Какие существуют основные критерии оптимизации программного обеспечения?
Эффективность использования кэш памяти. Виды промахов
Основные рекомендации по повышению эффективности использования кэш памяти.
Сравните функционирование подсистемы памяти при случайном обходе массива и последовательном обходе.
К чему приводят промахи по конфликтам? Какие есть способы их устранения на уровне программы?
Какими основными способами можно использовать векторные расширения современных микропроцессоров?
Какие группы команд можно выделить в SIMD векторных расширениях SSE?
Какие задачи решает middleware?
Какие задачи решает микросервисная архитектура? На каких принципах она базируется?
Для чего нужны промежуточные представления программ?
Какое влияние на эффективность программы может быть от систематизированного поиска и применения доступных системных библиотек по сравнению с подходом, при котором весь функционал реализуется разработчиком приложения?
Какие проблемы позволяет решить (или упростить) переход к многопоточной реализации программ?
Каково назначение и основные функции верификаторов?
Какие существуют основные модели построения многопоточных программ?
Какие виды промахов есть при доступе к кэш памяти?
Какие есть способы устранения промахов по объему при доступе к кэш памяти?
Как влияет порядок обхода элементов на эффективность программы, обрабатывающей массив? Какие обходы предпочтительнее? Последовательные или произвольные? Почему?
Какие существуют способы обеспечить последовательный обход массива?
Как оформляются ассемблерные вставки в программах на Си в GNU Linux и Windows?
Какие факторы влияют на выбор числа потоков в программе?
Какие имеются механизмы для взаимодействия процессов внутри одного компьютера? Какие из них более эффективны?
Что такое динамическая балансировка нагрузки? Какие задачи она решает? В каких случаях целесообразно ее применение?
Какие существуют способы экономии памяти? Каковы границы их применимости?
Какие есть способы экономии вычислений? В каких ситуациях они применимы, а в каких – нет?
Чем отличаются требования, предъявляемые к программному обеспечению встраиваемых систем, по сравнению с требованиями к программному обеспечению для персональных компьютеров?
Какие критерии эффективности программного обеспечения используются? Какие из них являются ключевыми?
На каких этапах разработки ПО разработчик может заниматься оптимизацией и каким образом?