Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач 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 или шину данных ОП, то они будут замедлять друг друга, и это замедление может быть существенным. Этот вопрос подробно рассматривается здесь
в соответствии с тем, какие ресурсы в основном нужны задаче. Может быть, первые 3 класса можно объединить в один, CORE_BOUNDED, так как во всех трех случаях речь идет об использовании ресурсов только ядра.
Отнесем каждую задачу к одному из этих классов на основе интуитивных соображений. Вполне возможно, что это отнесение окажется неверным, это не беда(см. ниже).
Выберем 4 задачи разных классов и запустим их под управлением собственного менеджера в отдельных потоках, при этом установим потокам affinity mask таким образом, чтобы каждый поток мог выполняться только на "своем" ядре.
Через некоторое время (квант времени) менеджер определяет для каждой задачи счетчики производительности (количество кеш-промахов, количество переданных байт из RAM и др.) , анализирует их и выясняет, не мешают ли задачи друг другу. Если выяснится, что задачи мешают друг другу, значит , их первичная классификация была произведена неверно. В этом случае менеджер изменяет отнесение задачи к классу и приостанавливает одного из "конкурентов" , запуская следующую задачу, которая вроде бы по классификации не должна конкурировать за ресурсы с той задачей, что осталась.
Теперь задачам дают проработать еще один квант времени, после чего делается то же самое, в результате либо дают продолжиться какой-то из приостановленных задач, либо запускают еще одну новую. Если в течение кванта какая-то задача закончится, то менеджер либо дает продолжиться одной из приостановленных задач, либо запускает "подходящую" по классу
новую.
Возможно, что приостанавливать задачи и не потребуется, достаточно будет снизить/повысить приоритет задачи.
Менеджер может быть и более сложным. Например, он может учитывать, сколько задач какого класса еще осталось, чтобы выбирать очередную, пусть даже в ущерб вышеприведенной схеме. Иначе может оказаться, что в конце всего процесса у нас окажется много конкурирующих друг с другом задач и их волей-неволей придется запускать в режиме, когда они друг другу мешают. Может быть, на основе анализа прохождения задач данного типа менеджер посчитает нужным изменить класс задачи этого типа, и т.д.
Понятно, что тут будет некоторый оверхед за счет переключения потоков и очистки кеша и т.д. Но если это переключение будет производиться не слишком часто по сравнению с временем работы задачи, то в итоге мы будем иметь выигрыш.
Вот в целом вся идея.
Вопросы же такие.
1. Сама идея имеет право на существование ? Я тут ничего важного не пропустил, что может помешать ей реализоваться ?
2. Если ответ на первый вопрос положительный — есть ли попытки ее реализации ? Не изобрел ли я велосипед ? Если есть — просьба дать ссылки.
3. И последнее. Может кто-то порекомендовать хорошую библиотеку для чтения счетчиков производительности ? Для Windows и для Linux. Для Linux я нашел libperf, но ее последняя модификация десятилетней давности. Может, конечно, это и не так важно — кеши и тогда уже были. Программировать самому команду RDPMC что-то не хочется.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Рассмотрим следующую ситуацию
PD>Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач N, причем К типов , каждого типа nk задач.
PD>Задачи независимы и выполнять их можно в любом порядке.
Условия какие — то сферические.
PD>Цель — пропустить все задачи за минимальное астрономическое время. PD>Отнесем каждую задачу к одному из этих классов на основе интуитивных соображений. Вполне возможно, что это отнесение окажется неверным, это не беда(см. ниже).
PD>Выберем 4 задачи разных классов и запустим их под управлением собственного менеджера в отдельных потоках, при этом установим потокам affinity mask таким образом, чтобы каждый поток мог выполняться только на "своем" ядре.
PD>Через некоторое время (квант времени) менеджер определяет для каждой задачи счетчики производительности (количество кеш-промахов, количество переданных байт из RAM и др.) , анализирует их и выясняет, не мешают ли задачи друг другу. Если выяснится, что задачи мешают друг другу, значит , их первичная классификация была произведена неверно. В этом случае менеджер изменяет отнесение задачи к классу и приостанавливает одного из "конкурентов" , запуская следующую задачу, которая вроде бы по классификации не должна конкурировать за ресурсы с той задачей, что осталась.
PD>Вопросы же такие.
PD>1. Сама идея имеет право на существование ? Я тут ничего важного не пропустил, что может помешать ей реализоваться ?
Задача имеет право, но на практике думаю такой менеджер выиграет десяток — другой процентов производительности по сравнению с рэндомным запуском.
А оптимизация и подбор самих алгоритмов , или оптимизация количества вычислений (например исключить какие — то ненужные, или повторяющиеся), может дать большую экономию.
Если код уже не какой то супероптимизированный.
PD>Рассмотрим следующую ситуацию PD>Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач N, причем К типов , каждого типа nk задач. PD>Например, надо 100 раз произвести обращение матрицы, 50 раз вычислить сумму ряда и 200 раз обработать некое графическое изображение. Тогда N=350, K=3, n1 = 100, n2 = 50, n3 = 200. PD>Задачи независимы и выполнять их можно в любом порядке. PD>Цель — пропустить все задачи за минимальное астрономическое время. PD>Выполнение производится на машине с C-ядерным процессором (будем считать C=4) PD>Никакие другие "тяжелые" вычисления на машине не производятся, так что загрузка процессора другими процессами близка к 0.
Выяснить, какие задачи из смеси к какому кешу обращаются можно только на основе реального отслеживания.
Как это отслеживать и можно ли — хрен знает, не интересовался.
Мой опыт такой.
Писал я задачу моделирования перколяционных процессов.
Матрицы там большие, 10000х10000 — это маленькая.
На моей 32-битной машине удалось достичь 40000х40000
Вторая засада — моделирование методом монте-карло.
Процесс повторяется от 1000 раз (а лучше 10000) и собирается полная статистика.
Естественно, я пытался выжать из 1 прогона максимальную скорость.
И вот заметил, что обработка матрицы по горизонтали в 4 (четыре) раза быстрее, чем по вертикали.
Сообразил, что это зависит от кеша.
Простое решение ускорило работу в 3 раза.
Просто предварительно переписал столбец в вектор.
Поэтому даже отслеживание мало что даст.
Ну, будет задача тормозиться по смене кеша.
И что с этим делать?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
PD>>Рассмотрим следующую ситуацию PD>>Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач N, причем К типов , каждого типа nk задач. PD>>Например, надо 100 раз произвести обращение матрицы, 50 раз вычислить сумму ряда и 200 раз обработать некое графическое изображение. Тогда N=350, K=3, n1 = 100, n2 = 50, n3 = 200.
LVV>Поэтому даже отслеживание мало что даст. LVV>Ну, будет задача тормозиться по смене кеша. LVV>И что с этим делать?
Как я написал, оптимизировать сами алгоритмы по отдельности будет эффективней.
В результате, как часто бывает, оптимизированные алгоритмы 1 потоке выполнятся быстрее чем какие попало в параллели.
Из моих недавних оптимизаций — нужно было писать много измерений в файл, миллионы в секунду, время в каждой записи.
Написание своей функции преобразования времени в строку дало выигрыш в 40 раз по сравнению с библиотечной функцией.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Рассмотрим следующую ситуацию
PD>Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач N, причем К типов , каждого типа nk задач.
Вам просто необходимо построить функцию оценки ресурсов (время, память и обр к диску т.п.) для каждого типа задачи.
Модели могут быть очень простыми например Tk=C0 + C1*n + C2*V где n — количество подзадач или V объём задач (например кол-во обр элем)
Можно на части задач эти коэф уточнить или уточнять по мере выполнения.
А далее задача оптимизации, как обычно решается приближенно.
PD>Если несколько задач будут конкурировать за кеш L3 или шину данных ОП, то они будут замедлять друг друга, и это замедление может быть существенным. Этот вопрос подробно рассматривается здесь
Это всё тонкости, в среднем это погоды не делает. Каждая отдельная задача, предполагается, уже выжимает всё что можно изжелеза.
PD>https://embedded.cs.uni-saarland.de/literature/AddressingSharedResourceContentionInMulticoreProcessorsViaScheduling.pdf
Если есть желание в модели можно добавить пагубное взаимовлияние других задач. (Например интенсивное целочисленное деление в intel-ах способно остановить соседний гипертридинговый поток практически в 0)
PD>Поступим иначе. Введем классификацию задач следующим образом
Вы можете создать модель в которой есть параметры (скорость кэшей, скорость памяти, пиковые gflops и т.п.) и по ним разложить разные типы задач, когда зада много то можно довольно точно найти коэффиценты.
И если более сложные модели предсказывают лучше простых, можно использовать их или их комбинации типа xgboost. И тогда по воходным параметрам задач и параметрам машины можно будет оценивать время выполнения.
PD>1. Сама идея имеет право на существование ? Я тут ничего важного не пропустил, что может помешать ей реализоваться ?
Да PD>2. Если ответ на первый вопрос положительный — есть ли попытки ее реализации ? Не изобрел ли я велосипед ? Если есть — просьба дать ссылки.
Такие задачи часто всплывают на суперкомпьютерах. Там можно и покопаться в статьях.
PD>3. И последнее. Может кто-то порекомендовать хорошую библиотеку для чтения счетчиков производительности ? Для Windows и для Linux. Для Linux я нашел libperf, но ее последняя модификация десятилетней давности. Может, конечно, это и не так важно — кеши и тогда уже были. Программировать самому команду RDPMC что-то не хочется.
Оно как правило не особо нужно. libperf требует админских прав, зато можно смотреть сколько энергии тратиться на вычисления.
Здравствуйте, swame, Вы писали:
S>Условия какие — то сферические.
Ну не без этого, да. Но не слишком — просто длительные вычислительные задачи.
S>Задача имеет право, но на практике думаю такой менеджер выиграет десяток — другой процентов производительности по сравнению с рэндомным запуском.
Да, именно об этом и идет речь. Ускорить в разы я не рассчитываю.
S>А оптимизация и подбор самих алгоритмов , или оптимизация количества вычислений (например исключить какие — то ненужные, или повторяющиеся), может дать большую экономию. S>Если код уже не какой то супероптимизированный.
Идея в том, чтобы исходные программы не модифицировать никаким способом и вообще ничего почти о них не знать, разве что интуитивно относить их кому или иному классу.
Здравствуйте, LaptevVV, Вы писали:
LVV>Выяснить, какие задачи из смеси к какому кешу обращаются можно только на основе реального отслеживания.
Об этом и речь
LVV>Как это отслеживать и можно ли — хрен знает, не интересовался.
Ну вроде можно, а как — это второй вопрос.
LVV>И вот заметил, что обработка матрицы по горизонтали в 4 (четыре) раза быстрее, чем по вертикали.
Ну это классика.
Я студентам давал задачу найти сумму элементов строк и сумму элементов столбцов большой матрицы.
Строк — понятно, идем по строкам. А вот столбцов — ну напрашивается же проход по столбцам. А надо и тут идти по строкам , и будет быстрее.
LVV>Сообразил, что это зависит от кеша.
И от свопинга, если матрица не помещается целиком в ОП и имеет место подкачка. Она идет страницами, а страница содержит одну или несколько строк (возможно, неполные первую и последнюю строки)
LVV>Ну, будет задача тормозиться по смене кеша. LVV>И что с этим делать?
Надежда на то, что правильный выбор подходящих задач перекроет этот эффект.
Здравствуйте, kov_serg, Вы писали:
_>Вам просто необходимо построить функцию оценки ресурсов (время, память и обр к диску т.п.) для каждого типа задачи.
Увы, не получится. Разные задачи одного типа могут выполняться очень разное время. Это зависит и от размера данных, но это еще полбеды. Хуже, что и при одном и том же размере данных время может отличаться в разы. Например, алгоритм Якоби для диагонализации. Он итеративный, и бог знает, сколько понадобится итераций, прежде чем он сойдется.
_>Это всё тонкости, в среднем это погоды не делает. Каждая отдельная задача, предполагается, уже выжимает всё что можно изжелеза.
Да, но речь идет именно о тонкостях. Задача-то выжимает, допустим, но если она одна. А когда их несколько, то они друг другу могут и мешать.
PD>>Поступим иначе. Введем классификацию задач следующим образом _>Вы можете создать модель в которой есть параметры (скорость кэшей, скорость памяти, пиковые gflops и т.п.) и по ним разложить разные типы задач, когда зада много то можно довольно точно найти коэффиценты.
Опять же время, см. выше.
PD>>1. Сама идея имеет право на существование ? Я тут ничего важного не пропустил, что может помешать ей реализоваться ? _>Да PD>>2. Если ответ на первый вопрос положительный — есть ли попытки ее реализации ? Не изобрел ли я велосипед ? Если есть — просьба дать ссылки. _>Такие задачи часто всплывают на суперкомпьютерах. Там можно и покопаться в статьях.
PD>>3. И последнее. Может кто-то порекомендовать хорошую библиотеку для чтения счетчиков производительности ? Для Windows и для Linux. Для Linux я нашел libperf, но ее последняя модификация десятилетней давности. Может, конечно, это и не так важно — кеши и тогда уже были. Программировать самому команду RDPMC что-то не хочется. _>Оно как правило не особо нужно. libperf требует админских прав, зато можно смотреть сколько энергии тратиться на вычисления.
Админские права — полбеды, для начала можно и с админскими запустить.
А вот насчет энергии — можно подробнее ? Я не понял, о чем речь идет.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, swame, Вы писали:
PD>Идея в том, чтобы исходные программы не модифицировать никаким способом и вообще ничего почти о них не знать, разве что интуитивно относить их кому или иному классу.
Не взлетит. Для своих алгоритмов лучше оптимизировать свои алгоритмы — даст экономию возможно в разы.
Для чужих процессов — будет какая то очень сложная настройка, никто этим не будет заниматься для выигрыша максимум 20% скорости.
PD>Надежда на то, что правильный выбор подходящих задач перекроет этот эффект.
Правильный выбор — это какой ?
А то в ОС уже в 60-е существовала дисциплина запуска "короткие задачи — первыми".
НО тогда в управляющих перфокартах задавали примерное время выполнения...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Увы, не получится. Разные задачи одного типа могут выполняться очень разное время. Это зависит и от размера данных, но это еще полбеды. Хуже, что и при одном и том же размере данных время может отличаться в разы. Например, алгоритм Якоби для диагонализации. Он итеративный, и бог знает, сколько понадобится итераций, прежде чем он сойдется.
Это не правда. У вас должен быть критерий сходимости и ограничение на кол-во итераций. Если у вас много задач, то вы найдёте средние коэффициенты. Тут не требуется 100% точность. При желании вы можете оценить и погрешность. И еще ни кто не мешает по ходу выполнения задач обновлять данные моделей.
PD>Да, но речь идет именно о тонкостях. Задача-то выжимает, допустим, но если она одна. А когда их несколько, то они друг другу могут и мешать.
Если у вас есть N типов задач, то при длительном наблюдении вы спокойно выявите кто, кому мешает. И это уже учитывать при составлении расписания для оставшихся задач.
PD>Админские права — полбеды, для начала можно и с админскими запустить. PD>А вот насчет энергии — можно подробнее ? Я не понял, о чем речь идет.
Я про то что есть возможность измерять потребление энергии разными компонентами.
S>Для чужих процессов — будет какая то очень сложная настройка, никто этим не будет заниматься для выигрыша максимум 20% скорости.
Как сказать... Участвовал я когда-то в проекте, где на обработку и анализ изображения отводилось некоторое время. Не уложился — задача снимается без разговоров. Качество — процент успешно обработанных изображений. Если бы я сказал, что могу бесплатно повысить скорость обработки на 20% — мне бы большое спасибо сказали.
_>Это не правда. У вас должен быть критерий сходимости и ограничение на кол-во итераций.
Разумеется они есть, как же иначе ? Максимальное количество итераций есть, вот только если оно, скажем, 100, то иногда понадобится все 100, а иногда и 10 хватит.
>Если у вас много задач, то вы найдёте средние коэффициенты. Тут не требуется 100% точность.
Верно, точность не нужна, но и дисперсия большая не годится. А если еще размер матрицы варьируется хотя бы в 2-3 раза, то все становится вообще зыбким. Все же это O(N^3)
Да и не в этом дело. Я не хочу анализировать задачи. Я вообще не хочу знать, что они делают и сколько им времени на это надо. Сколько надо — столько и будет в итоге, а по ходу исполнения менеджер будет ими управлять. Быстро работают — управление почти не понадобится. Долго работают — если начнут конкурировать с другими, менеджер разрулит. Не будут конкурировать — он не будет вмешиваться.
>При желании вы можете оценить и погрешность. И еще ни кто не мешает по ходу выполнения задач обновлять данные моделей.
Это годится, если набор задач известен и можно для них на основе анализа сделать формулы. А я именно этого и не хочу. Давайте любые задачи, только сделайте предположение о классе (а впрочем, можно и не делать, сами разберемся по ходу дела). Что угодно давайте, лишь бы были только операции с CPU и RAM, и ничего другого
PD>>Да, но речь идет именно о тонкостях. Задача-то выжимает, допустим, но если она одна. А когда их несколько, то они друг другу могут и мешать. _>Если у вас есть N типов задач, то при длительном наблюдении вы спокойно выявите кто, кому мешает. И это уже учитывать при составлении расписания для оставшихся задач.
PD>>Админские права — полбеды, для начала можно и с админскими запустить. PD>>А вот насчет энергии — можно подробнее ? Я не понял, о чем речь идет.
_>Я про то что есть возможность измерять потребление энергии разными компонентами.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Разумеется они есть, как же иначе ? Максимальное количество итераций есть, вот только если оно, скажем, 100, то иногда понадобится все 100, а иногда и 10 хватит.
Если задач не 3 а сотни то всё равно можно найти средние значения, более того можно уточнять по мере выполнения.
>>Если у вас много задач, то вы найдёте средние коэффициенты. Тут не требуется 100% точность. PD>Верно, точность не нужна, но и дисперсия большая не годится. А если еще размер матрицы варьируется хотя бы в 2-3 раза, то все становится вообще зыбким. Все же это O(N^3)
Так модель можно использовать не линейную, а полиномиальную или даже экспоненциальную. Всё от типа реализации зависит.
PD>Да и не в этом дело. Я не хочу анализировать задачи. Я вообще не хочу знать, что они делают и сколько им времени на это надо. Сколько надо — столько и будет в итоге, а по ходу исполнения менеджер будет ими управлять. Быстро работают — управление почти не понадобится. Долго работают — если начнут конкурировать с другими, менеджер разрулит. Не будут конкурировать — он не будет вмешиваться.
Задачу надо загрузить на ноду, потом запустить и после выполнения забрать данные или логи если не срослось. Всё это требует времени, как на вычисление так и на перемещение.
PD>Это годится, если набор задач известен и можно для них на основе анализа сделать формулы. А я именно этого и не хочу. Давайте любые задачи, только сделайте предположение о классе (а впрочем, можно и не делать, сами разберемся по ходу дела). Что угодно давайте, лишь бы были только операции с CPU и RAM, и ничего другого
Так делайте общую модель и выясняйте поведение по ходу, но входные данные описывающие задачи всё равно значительно улучшат модели.
Ну тут как минимум надо не забыть про векторизацию вычислений и использование SIMD-инструкций либо же интринсиков. Это само по себе уже очень сильно ускорит вычисления. А уж процессор сам все как надо разложит и быстро посчитает 18/16/32/64 числа за одни и те же такты.
Здравствуйте, DiPaolo, Вы писали:
DP>Ну тут как минимум надо не забыть про векторизацию вычислений и использование SIMD-инструкций либо же интринсиков. Это само по себе уже очень сильно ускорит вычисления. А уж процессор сам все как надо разложит и быстро посчитает 18/16/32/64 числа за одни и те же такты.
Речь не идет об оптимизации кода. Речь идет о менеджере, который управляет порядком исполнения существующего кода .
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Рассмотрим следующую ситуацию
PD>Надо пропустить достаточно большое количество задач, каждая из которых выполняет большое количество арифметических операций. Иных действий в задачах нет.Все данные для всех задач уже размещены в ОП. Всего задач N, причем К типов , каждого типа nk задач.
Похоже на задачу из теории расписаний. Не получится свести к задаче о станках, например? Честно говоря, я не читал полностью, слишком много ненужных подробностей.
