Профилирование OpenMP-программы

Порядок выполнения работы:
1. Измерить время выполнения каждого из четырёх этапов (Generate, Map, Merge, Sort).
2. Написать функцию, которая один раз в K мс выводит в файл коэффициент загрузки каждого ядра. Эту функцию необходимо запустить в отдельном потоке (треде), параллельно работающем с основным вычислительным циклом. Значение K нужно подобрать так, чтобы новая функция существенно не влияла на производительность основных вычислений (обоснование выбора конкретного значения К нужно привести в отчёте).
3. Для профилирования полученной программы провести эксперименты, по результатам которых построить график зависимости доли времени, проведённого на каждом из этапов параллельной программы, от N.
4. Используя график из п.3, для наибольшего значения N = Nmax найти этап алгоритма, который является узким местом параллельной программы.
5. Используя график из п.3 найти такое значение N = N*, при котором узким местом программы является этап, отличный от найденного в п.4. Изменить исходную программу так, чтобы распараллеленным остался только этот этап.
6. Приняв за M количество процессоров (ядер), на которых выполняется программа, записать выражение для времени выполнения всей программы T(N, M, Сi ) и каждого i-го её этапа Ti (N, M, Сi ), где i = {generate, map, merge, sort}. Для простоты считать, что все виды элементарных операций (арифметические, логические, проверка условий, присваивание и т.п.) выполняются за одинаковое константное время Сi на i-ом этапе. Необходимый теоретический материал для выполнения этого пункта можно найти в книге Т. Кормена «Алгоритмы. Построение и анализ».
7. Записать выражение для вычислительной сложности (как по времени, так и объёму затрачиваемой памяти) для каждого i-го этапа и для всей программы в целом, используя асимптотические нотации O, Θ, Ω, представляющие собой функции от M и N. Используя полученные зависимости, найти узкое место программы при конечном М (реалистичный сценарий) и при M >> N (сценарий использования идеализированного мультипроцессора).