Дано ИСТОЧНИК(чип) с которого считываются параметры( П1, П2, П3, ... П32).
На длинну списка накладываю ограничение: число параметров никогда не будет 64.
Каждый из параметров я хотел бы считывать с определённой периодичностью (примерно). Хотелось бы получить список в котором параметры могут повторяться. С очередным тиком базового таймера рассматривать следующий элемент.
--------------------------------------------- Вопрос: может у кого есть определённые мысли по вопросу? Может эта задача имеет уже решение.
сколь подходит для тематики Weighted-Fair-Queuing? (Честная очередь с весовыми коэффициентами)?
я начал было час назад думать как бы замастерить чтото свое. а именно:
создать список, каждый из параметров можит входить в него один или более раз. Те что должны чаще считываться -- чаще встречаются в списке. создать такой список не так то просто, как я определил.
мог бы кто подсказать, плиз?
Re: Распределение нагрузки между задачами с приоритетами "ла
Здравствуйте, BAC, Вы писали:
BAC>Дано ИСТОЧНИК(чип) с которого считываются параметры( П1, П2, П3, ... П32).
BAC>На длинну списка накладываю ограничение: число параметров никогда не будет 64.
BAC>Каждый из параметров я хотел бы считывать с определённой периодичностью (примерно). Хотелось бы получить список в котором параметры могут повторяться. С очередным тиком базового таймера рассматривать следующий элемент.
BAC>создать список, каждый из параметров можит входить в него один или более раз. Те что должны чаще считываться -- чаще встречаются в списке. создать такой список не так то просто, как я определил.
Создавать такой список не обязательно. Решение лучше базировать на более интуитивных вещах, а список пусть сам себе строится в процессе. Впрочем, я там ниже также приведу размышления по поводу списка.
Пусть у тебя tps тиков в секунду. i-й параметр должен считываться в среднем ki раз в секунду, т.е. его "потребность" в обновлении растет с каждым тиком на ni=ki/tps (за tps тиков она вырастает до ki). Изначальную потребность параметров в обновлении можно инициировать либо нулем, либо каким-нибудь случайным числом от 0 до 1, либо по возрастающей для всех параметров, либо как-то еще. С каждым тиком ты пробегаешь по массиву этих самых double nfu[32] и увеличиваешь i-й элемент на ni. Можно вместо double взять числа с фиксированной точкой. Тебе важно отловить момент, когда целая часть nfu перевалит к следующему значению. На ассемблере в игрушках часто делают так: используют банальный byte или int для хранения дробной части только, а отлавливают переполнение. Таким образом, если экран надо обновлять максимум 60 раз в секунду, интеллект должен работать для AI 10 раз в секунду, а ввод отлавливаться 20 раз в секунду, то очередь на все эти функции выстраивается сама собой.
Если же такое саморегулирующееся решение не подходит (оно может не подходить по очень многим причинам), и хочется просто (циклическую) очередь обновления параметров, то тебе надо следующее.
а) Выявить минимальное время L в тиках, за которое каждый параметр должен обновиться [i]целое число раз, т.е. wi=L*ki/tps целое для всех. Еще лучше, если время L будет степенью двойки, чтобы индекс, который будет бежать по времени, можно было просто увеличивать и and-ть по младшим битам.
б) Для i-го параметра, который должен встретиться в этой очереди wi раз с шагом si или si+1, где si=[tps/ki], надо расставить его так: первая позиция x0i должна быть от 0 до si-1, затем j-я позиция должна быть x0+j*si или x0+j*si+1. В этом случае достигается максимально равномерное считывание каждого параметра.
Далее, могут возникать коллизии, когда на какой-то тик вдруг надо считывать сразу несколько параметров. Более того, обработка одного входного параметра может длиться более одного тика. В этом случае в очереди, чтобы не было таких коллизий, надо размещать считывание очередного параметра с учетом возможной задержки в считывании или обработке предыдущего параметра. В первом варианте обычно либо считывают все, что набрало достаточное количество тиков к данному моменту, либо считывают один, а остальные откладывают на следующий цикл/тик, но продолжают для них обновлять их nfu, чтобы эта задержка не сказалась на последующем времени обработки.
Поиск расстановки параметров по второму варианту -- дело кропотливое и нудное. Допустим, что первый параметр k обновляется сразу, т.е. его x0k=0. Далее, ему соответствует цепочка тиков j*sk[+1], в которые он должен обновляться. Второй параметр l обновляется в моменты x0l+j*sl[+1]. Если возникает коллизия этих двух параметров, то она решается просто: за счет того, что j-я позиция обновления может быть в пределах двух возможных тиков. Коллизию трех параметров k,l,m нельзя разрешить, если x0k+jk*sk = x0l+jl*sl = x0m+jm*sm для каких-то чисел k,l,m. Разрешить такую коллизию можно только путем изменения x0 для одного из параметров. А вообще, какого порядка у тебя величины tps, ki и длина обработки одного входного сигнала? Насколько вообще такие коллизии вероятны?
А вот зайца кому, зайца-выбегайца?!
Re[2]: Распределение нагрузки между задачами с приоритетами
Здравствуйте, vadimcher, спасибо за участие. течение моих мыслей совпадает с Вашими. Это радует, ибо вероятность ошибки минимируется.
Первый метод — динамический список он же впринципе wfq алгоритм. оптимален по использованию памяти, но памяти море. Но я бы предпочел второй метод, потому что считать очередь нужно только один раз. Параметр тика тоже. Конфликтные ситуации возникают только один раз, при создании списка. Если некоторые элементы становятся инактивными, то придётся список создавать заново — в динамическом списке это лучше решено.
планирую решить так:
задаю параметры по приоритетам группами (стэтик эррэй). для удобства я буду называть параметры каждой группы другой буквой. для упрощения беру три группы по три параметра.
теперь я обьединяю все три множества используя подобие бинарного поиска. внедряю поэлементно одно множество в другое. Конфликтные ситуации есть уже в примере. ну чтож, решаем.
Теперь если задан тик, то я могу выситать период. Или если есть период то могу высчитать тик.
Важный для меня вопрос: ЭТО СИЛЬНО КОРЯВО?
Точность периода считывания не столь важна. главное чтоб я не грузанул источник(чип). придётся экспериментировать с приоритетами.
V>Создавать такой список не обязательно. Решение лучше базировать на более интуитивных вещах, а список пусть сам себе строится в процессе. Впрочем, я там ниже также приведу размышления по поводу списка.
V>Пусть у тебя tps тиков в секунду. i-й параметр должен считываться в среднем ki раз в секунду, т.е. его "потребность" в обновлении растет с каждым тиком на ni=ki/tps (за tps тиков она вырастает до ki). Изначальную потребность параметров в обновлении можно инициировать либо нулем, либо каким-нибудь случайным числом от 0 до 1, либо по возрастающей для всех параметров, либо как-то еще. С каждым тиком ты пробегаешь по массиву этих самых double nfu[32] и увеличиваешь i-й элемент на ni. Можно вместо double взять числа с фиксированной точкой. Тебе важно отловить момент, когда целая часть nfu перевалит к следующему значению. На ассемблере в игрушках часто делают так: используют банальный byte или int для хранения дробной части только, а отлавливают переполнение. Таким образом, если экран надо обновлять максимум 60 раз в секунду, интеллект должен работать для AI 10 раз в секунду, а ввод отлавливаться 20 раз в секунду, то очередь на все эти функции выстраивается сама собой.
V>Если же такое саморегулирующееся решение не подходит (оно может не подходить по очень многим причинам), и хочется просто (циклическую) очередь обновления параметров, то тебе надо следующее. V>а) Выявить минимальное время L в тиках, за которое каждый параметр должен обновиться [i]целое число раз, т.е. wi=L*ki/tps целое для всех. Еще лучше, если время L будет степенью двойки, чтобы индекс, который будет бежать по времени, можно было просто увеличивать и and-ть по младшим битам. V>б) Для i-го параметра, который должен встретиться в этой очереди wi раз с шагом si или si+1, где si=[tps/ki], надо расставить его так: первая позиция x0i должна быть от 0 до si-1, затем j-я позиция должна быть x0+j*si или x0+j*si+1. В этом случае достигается максимально равномерное считывание каждого параметра.
V>Далее, могут возникать коллизии, когда на какой-то тик вдруг надо считывать сразу несколько параметров. Более того, обработка одного входного параметра может длиться более одного тика. В этом случае в очереди, чтобы не было таких коллизий, надо размещать считывание очередного параметра с учетом возможной задержки в считывании или обработке предыдущего параметра. В первом варианте обычно либо считывают все, что набрало достаточное количество тиков к данному моменту, либо считывают один, а остальные откладывают на следующий цикл/тик, но продолжают для них обновлять их nfu, чтобы эта задержка не сказалась на последующем времени обработки.
V>Поиск расстановки параметров по второму варианту -- дело кропотливое и нудное. Допустим, что первый параметр k обновляется сразу, т.е. его x0k=0. Далее, ему соответствует цепочка тиков j*sk[+1], в которые он должен обновляться. Второй параметр l обновляется в моменты x0l+j*sl[+1]. Если возникает коллизия этих двух параметров, то она решается просто: за счет того, что j-я позиция обновления может быть в пределах двух возможных тиков. Коллизию трех параметров k,l,m нельзя разрешить, если x0k+jk*sk = x0l+jl*sl = x0m+jm*sm для каких-то чисел k,l,m. Разрешить такую коллизию можно только путем изменения x0 для одного из параметров. А вообще, какого порядка у тебя величины tps, ki и длина обработки одного входного сигнала? Насколько вообще такие коллизии вероятны?
Re[3]: Распределение нагрузки между задачами с приоритетами
Здравствуйте, BAC, Вы писали:
BAC>Здравствуйте, vadimcher, спасибо за участие. течение моих мыслей совпадает с Вашими. Это радует, ибо вероятность ошибки минимируется.
BAC>Первый метод — динамический список он же впринципе wfq алгоритм. оптимален по использованию памяти, но памяти море. Но я бы предпочел второй метод, потому что считать очередь нужно только один раз. Параметр тика тоже. Конфликтные ситуации возникают только один раз, при создании списка. Если некоторые элементы становятся инактивными, то придётся список создавать заново — в динамическом списке это лучше решено.
В динамическом списке даже более того, автоматически решен такой случай, например, когда само считанное значение параметра может влиять на периодичность считывания. Вот представь, что у тебя есть унимодальная функция ("колокол"). Ты считываешь значение параметра по x и вычисляешь по этой функции значение параметра по y. На концах (при малых и больших x) значение функции от x зависит слабо. Т.е. если тебе нужен y с заданной точностью, то при получении очередного x на концах, если x меняется непрерывно по времени и с ограниченной скоростью, можно увеличить время до следующего считывания, однако если x лежит близко к пику функции, то малейшие изменения x могут приводить к большим изменениям y, т.е. x надо считывать чаще. Это такой частный случай, который, возможно, не имеет отношения к твоей задаче, но это просто как пример. У тебя в примере другой случай -- когда список параметров меняется.
BAC>планирую решить так:
BAC>задаю параметры по приоритетам группами (стэтик эррэй). для удобства я буду называть параметры каждой группы другой буквой. для упрощения беру три группы по три параметра. BAC>Г2 ( А1, А2, А3 ). BAC>Г1 ( Б1, Б2, Б3 ). BAC>Г0 ( В1, В2, В3 ). BAC>частота считывания зависит от индекса группы: 2^индекс. Г2 считывается в два раза чаще чем Г1, например. BAC>формирую из каждого списка список на максимальный период. тоесть максимальный период Г0 потому список без изменений. BAC>Г0" ( В1, В2, В3 ). BAC>Г1" ( Б1, Б2, Б3, Б1, Б2, Б3 ). BAC>Г2" ( А1, А2, А3, А1, А2, А3, А1, А2, А3, А1, А2, А3 ). BAC>Теперь расчитываю для каждого параметра фазовый сдвиг для каждой группы : BAC>( 1/(колличество элементов) ) * индекс элемента. Запишу для примера сдвиг в скобках с точностью два знака после запятой. BAC>Г0" ( В1(.33), В2(.66), В3(.99) ). BAC>Г1" ( Б1(.16), Б2(.32), Б3(.48), Б1(.64), Б2(.80), Б3(.96) ). BAC>Г2" ( А1(.08), А2(.16), А3(.24), А1(.32), А2(.40), А3(.48), А1(.56), А2(.64), А3(.72), А1(.80), А2(.88), А3(.96) ). BAC>теперь я обьединяю все три множества используя подобие бинарного поиска. внедряю поэлементно одно множество в другое. Конфликтные ситуации есть уже в примере. ну чтож, решаем.
Ну тут у тебя существенное облегчение задачи. Сделай так. Пусть нулевая группа обновляется каждые s тиков, т.е. если в ней n0 параметров, то расстояние между ними равно s/n0. Тогда параметры первой группы должны обновляться каждые s/2 тиков. Если их там n1, то расстояние между ними s/2n1. В твоем примере n0=n1. В этом случае смещение для первой группы выбирается так, что первый элемент стоит на 1:3 между соседними элементами нулевой группы (второй будет стоять на 3:1 и т.д.). Если ты можешь поделить группы на равное число элементов, то так их и надо расставлять. Если же не можешь, то надо искать НОК(n0,n1,...) и расставлять так, что твои арифметические прогрессии в этом кольце вычетов не пересекаются.
А вот зайца кому, зайца-выбегайца?!
Re[4]: Распределение нагрузки между задачами с приоритетами
V>Здравствуйте, BAC, Вы писали:
BAC>>Здравствуйте, vadimcher, спасибо за участие. течение моих мыслей совпадает с Вашими. Это радует, ибо вероятность ошибки минимируется.
BAC>>Первый метод — динамический список он же впринципе wfq алгоритм. оптимален по использованию памяти, но памяти море. Но я бы предпочел второй метод, потому что считать очередь нужно только один раз. Параметр тика тоже. Конфликтные ситуации возникают только один раз, при создании списка. Если некоторые элементы становятся инактивными, то придётся список создавать заново — в динамическом списке это лучше решено.
V>В динамическом списке даже более того, автоматически решен такой случай, например, когда само считанное значение параметра может влиять на периодичность считывания. Вот представь, что у тебя есть унимодальная функция ("колокол"). Ты считываешь значение параметра по x и вычисляешь по этой функции значение параметра по y. На концах (при малых и больших x) значение функции от x зависит слабо. Т.е. если тебе нужен y с заданной точностью, то при получении очередного x на концах, если x меняется непрерывно по времени и с ограниченной скоростью, можно увеличить время до следующего считывания, однако если x лежит близко к пику функции, то малейшие изменения x могут приводить к большим изменениям y, т.е. x надо считывать чаще. Это такой частный случай, который, возможно, не имеет отношения к твоей задаче, но это просто как пример. У тебя в примере другой случай -- когда список параметров меняется.
BAC>>планирую решить так:
BAC>>задаю параметры по приоритетам группами (стэтик эррэй). для удобства я буду называть параметры каждой группы другой буквой. для упрощения беру три группы по три параметра. BAC>>Г2 ( А1, А2, А3 ). BAC>>Г1 ( Б1, Б2, Б3 ). BAC>>Г0 ( В1, В2, В3 ). BAC>>частота считывания зависит от индекса группы: 2^индекс. Г2 считывается в два раза чаще чем Г1, например. BAC>>формирую из каждого списка список на максимальный период. тоесть максимальный период Г0 потому список без изменений. BAC>>Г0" ( В1, В2, В3 ). BAC>>Г1" ( Б1, Б2, Б3, Б1, Б2, Б3 ). BAC>>Г2" ( А1, А2, А3, А1, А2, А3, А1, А2, А3, А1, А2, А3 ). BAC>>Теперь расчитываю для каждого параметра фазовый сдвиг для каждой группы : BAC>>( 1/(колличество элементов) ) * индекс элемента. Запишу для примера сдвиг в скобках с точностью два знака после запятой. BAC>>Г0" ( В1(.33), В2(.66), В3(.99) ). BAC>>Г1" ( Б1(.16), Б2(.32), Б3(.48), Б1(.64), Б2(.80), Б3(.96) ). BAC>>Г2" ( А1(.08), А2(.16), А3(.24), А1(.32), А2(.40), А3(.48), А1(.56), А2(.64), А3(.72), А1(.80), А2(.88), А3(.96) ). BAC>>теперь я обьединяю все три множества используя подобие бинарного поиска. внедряю поэлементно одно множество в другое. Конфликтные ситуации есть уже в примере. ну чтож, решаем.
V>Ну тут у тебя существенное облегчение задачи. Сделай так. Пусть нулевая группа обновляется каждые s тиков, т.е. если в ней n0 параметров, то расстояние между ними равно s/n0. Тогда параметры первой группы должны обновляться каждые s/2 тиков. Если их там n1, то расстояние между ними s/2n1. В твоем примере n0=n1. В этом случае смещение для первой группы выбирается так, что первый элемент стоит на 1:3 между соседними элементами нулевой группы (второй будет стоять на 3:1 и т.д.). Если ты можешь поделить группы на равное число элементов, то так их и надо расставлять. Если же не можешь, то надо искать НОК(n0,n1,...) и расставлять так, что твои арифметические прогрессии в этом кольце вычетов не пересекаются.
