Рассмотрим следующую ситуацию
Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач N, причем К типов , каждого типа nk задач.
Например, надо 100 раз произвести обращение матрицы, 50 раз вычислить сумму ряда и 200 раз обработать некое графическое изображение. Тогда N=350, K=3, n1 = 100, n2 = 50, n3 = 200.
Задачи независимы и выполнять их можно в любом порядке.
Цель — пропустить все задачи за минимальное астрономическое время.
Выполнение производится на машине с C-ядерным процессором (будем считать C=4)
Никакие другие "тяжелые" вычисления на машине не производятся, так что загрузка процессора другими процессами близка к 0.
Стандартное решение — выбрать случайным образом 4 задачи, запустить их в потоках. Когда одна из них закончится, выбрать случайным образом еще одну задачу, пустить ее в освободившемся потоке. И т.д., пока все задачи не будут пропущены.
Однако это решение не учитывает того, что задачи бывают разные. Задачи одного типа выполняют все операции на регистрах и к памяти почти не обращаются. Другим хватит кеша L1 для их работы, третьим — кеша L2, четвертым — кеша L3, ну а пятым потребуется все время обращаться к RAM, так как данные такой задачи даже в L3 не поместились бы, если бы она работала в монопольном режиме.
Если несколько задач будут конкурировать за кеш L3 или шину данных ОП, то они будут замедлять друг друга, и это замедление может быть существенным. Этот вопрос подробно рассматривается здесь
https://embedded.cs.uni-saarland.de/literature/AddressingSharedResourceContentionInMulticoreProcessorsViaScheduling.pdf
Поступим иначе. Введем классификацию задач следующим образом
enum TASK_CLASS {
CPU_BOUNDED,
L1_BOUNDсED,
L2_BOUNDED,
L3_BOUNDED,
RAM_BOUNDED
}
в соответствии с тем, какие ресурсы в основном нужны задаче. Может быть, первые 3 класса можно объединить в один, CORE_BOUNDED, так как во всех трех случаях речь идет об использовании ресурсов только ядра.
Отнесем каждую задачу к одному из этих классов на основе интуитивных соображений. Вполне возможно, что это отнесение окажется неверным, это не беда(см. ниже).
Выберем 4 задачи разных классов и запустим их под управлением собственного менеджера в отдельных потоках, при этом установим потокам affinity mask таким образом, чтобы каждый поток мог выполняться только на "своем" ядре.
Через некоторое время (квант времени) менеджер определяет для каждой задачи счетчики производительности (количество кеш-промахов, количество переданных байт из RAM и др.) , анализирует их и выясняет, не мешают ли задачи друг другу. Если выяснится, что задачи мешают друг другу, значит , их первичная классификация была произведена неверно. В этом случае менеджер изменяет отнесение задачи к классу и приостанавливает одного из "конкурентов" , запуская следующую задачу, которая вроде бы по классификации не должна конкурировать за ресурсы с той задачей, что осталась.
Теперь задачам дают проработать еще один квант времени, после чего делается то же самое, в результате либо дают продолжиться какой-то из приостановленных задач, либо запускают еще одну новую. Если в течение кванта какая-то задача закончится, то менеджер либо дает продолжиться одной из приостановленных задач, либо запускает "подходящую" по классу
новую.
Возможно, что приостанавливать задачи и не потребуется, достаточно будет снизить/повысить приоритет задачи.
Менеджер может быть и более сложным. Например, он может учитывать, сколько задач какого класса еще осталось, чтобы выбирать очередную, пусть даже в ущерб вышеприведенной схеме. Иначе может оказаться, что в конце всего процесса у нас окажется много конкурирующих друг с другом задач и их волей-неволей придется запускать в режиме, когда они друг другу мешают. Может быть, на основе анализа прохождения задач данного типа менеджер посчитает нужным изменить класс задачи этого типа, и т.д.
Понятно, что тут будет некоторый оверхед за счет переключения потоков и очистки кеша и т.д. Но если это переключение будет производиться не слишком часто по сравнению с временем работы задачи, то в итоге мы будем иметь выигрыш.
Вот в целом вся идея.
Вопросы же такие.
1. Сама идея имеет право на существование ? Я тут ничего важного не пропустил, что может помешать ей реализоваться ?
2. Если ответ на первый вопрос положительный — есть ли попытки ее реализации ? Не изобрел ли я велосипед ? Если есть — просьба дать ссылки.
3. И последнее. Может кто-то порекомендовать хорошую библиотеку для чтения счетчиков производительности ? Для Windows и для Linux. Для Linux я нашел libperf, но ее последняя модификация десятилетней давности. Может, конечно, это и не так важно — кеши и тогда уже были. Программировать самому команду RDPMC что-то не хочется.
