Весёлая задачка про обмен данными
Все персонажи вымышлены, совпадения случайны.
Есть два абсолютно одинаковых прибора, играющих роль левого и правого глаза. Каждые 200 мс их практически одновременно (со сдвижкой на десятки микросекунд) спрашивают, "где мы находимся". Как только пришёл запрос - отвечать надо МГНОВЕННО (от запроса до ответа должна пройти пауза от 2 до 12 мкс), вовремя не ответишь - считаешься мёртвым.
Всего на получение новых данных уходит примерно 100 мс: сначала "холостой" кадр, затем "светлый", затем ещё промежуточный (он необходим, чтобы при скользящем затворе, rolling shutter, один кадр вышел полностью светлым, т.е со включённой подсветкой, а второй полностью тёмным), затем "тёмный" кадр, и потом ещё некоторое время на обработку результатов.
Мы стремимся отдавать наиболее свежую информацию, поэтому постараемся войти в ритм: начинать работу аккурат за 100 мс до того, как придёт запрос, чтобы данные были готовы лишь чуть перед тем, как их хватятся.
Пока всё довольно просто. Веселье начинается, если мы хотим именно в этих приборах построить стереокартину...
Для определённости, пусть запросы "где мы находимся" приходят в моменты 0, T, 2T, 3T и так далее, где T=200 мс - период опроса.
Теперь нам оставлена некоторая свобода выбора - придумать, в какой момент будет дан запрос "прислать сырые данные", и спустя короткий промежуток времени контроллер шины пошлёт команду "принять сырые данные", так что левый "глаз" получит информацию о том, что увидел правый, и наоборот. Иными словами, нам позволено выбрать число k от 0 до 1, и теперь запросы на сырые данные будут приходить в моменты kT, kT+T, kT+2T, kT+3T и так далее.
Надо понять, какую задержку от получения данных до их финальной обработки мы хотя бы в теории можем получить.
Что "сырые данные", что обработанные, но с использованием только локальной (от одного глаза) информации - получаются практически одновременно. В смысле, сама экспозиция 2 кадров занимает время, а обработка занимает считанные миллисекунды. Так что первое, что мы можем придумать - запрашивать целевую информацию ("где мы находимся") и сырые данные одновременно, типа "как только получили - так и запросим".
Но это очень грустно: да, мы отправили сырые данные, соседний комплект их почти тут же получил, и теперь, располагая полной информацией, смог построить стереокартину и получить офигительно точные данные о нашем положении в пространстве, только вот ближайшие 200 мс никто его об этом не спросит!
Как результат, у нас уже была задержка в 100 мс от начала измерений до выдачи "одноглазых" данных (если считать, что эти данные соотв середине экспозиции светлого кадра, задержка уже поменьше, 30..70 мс в зависимости от фазировки кадров), но потом совершенно "на ровном месте" задерживаемся ещё на 200. ОБИДНО!
Удивительно долгое время я сидел в ступоре относительно этой ситуации, смотрел как баран на циклограмму информационного обмена, и всё мне казалось, что меня зажали в угол, сделав весь обмен ПОЛНОСТЬЮ СИММЕТРИЧНЫМ, т.е опрашивая оба глаза синхронно. А у меня же один "глаз" должен другому что-то передать, затем этот второй посылку получить, ещё пару миллисекунд подумать - и только тогда у него сложится стереокартинка. Вот ровно сейчас бы его опросить - а НЕЛЬЗЯ, жди 200 мс. Но на этой укороченной неделе немного отвлёкся на батарейки для теодолитов и тахеометров, и на очередной "МКО для бедных" - и резко осенило. ВСЁ ОЧЕНЬ ПРОСТО.
Правильный ответ: k≈0,95, т.е запрос сырых данных надо делать на 190й миллисекунде, затем на 390й, 590й и так далее. А мы должны подстроиться, и начинать измерения на 90й миллисекунде, затем на 290й и так далее. На 190й миллисекунде у нас уже имеются сырые данные, и целевая информация тоже есть, но пока что одноглазая.
Вот в этот самый момент два комплекта обмениваются данными друг с другом, на что у них есть около 10 мс. И наконец, на 200й миллисекунде у них запрашивают целевую информацию. Если со стереокартинкой что-то не сложилось - не страшно, буквально 10 мс назад у них была монокартинка - не так точно, но требованиям удовлетворяет. Если же всё хорошо - то оба комплекта уже обработали "соседские" данные вместе со своими - и по запросу выдадут более точное положение в пространстве. По идее, у них должны получиться абсолютно идентичные результаты, только в разных системах координат.
Наверное, вот эта "близость к единице" смущала, что мы почти до самого конца "периода опроса" дотягиваем, что кажется дофига долго, но ведь мы сами придумываем фазировку нашей собственной работы, так что 0,95 превращается в -0,05.
Внезапно выходит, что тут и нет как такового "ведущего" и "ведомого", каждый исполняет обе роли, что проще для конфигурации. Вообще, никаких специальных мер не требуется для "перехода в стереорежим". Прибор сделал измерения, и подождал немножко - вдруг ему сейчас пришлют данные от соседа. Прислали - он обработал всё скопом. Не прислали - хрен с ним, обработает только свои. Запросили данные - он выдаёт, что у него есть. Т.е, если вдруг нам "подбили глаз" (ну, скорее, сам из строя зачем-то вышел), сосед и глазом не моргнёт, не будет периода "дезориентации", для перенастройки на обычный режим, не нужно никакой перенастройки.
Осталось только оценить более точно, сколько нам надо времени на обработку. Вся часть, что касается решения системы линейных уравнений 6х6 с симметричной положительно определённой матрицей - остаётся в силе, просто эта матрица суммируется из бОльшего числа отдельных, что улучшает её число обусловленности.
И были всё-таки идеи "распараллелить" это дело, я хотел передавать соседу не "сырые данные" как таковые, а как раз свою матрицу и вектор, чтобы сосед их пересчитал в свою систему координат и просуммировал со своей. Матрица 6х6, но за счёт симметрии нужно только 21 значение передать. Ещё 6 значений для вектора ненормированной оценки сдвига, итого 27. Ещё заголовок и CRC, это 29. Идеально: в 32 слова данных влезаем. Тогда издержки стереорежима оказываются совсем смешными.
Есть два абсолютно одинаковых прибора, играющих роль левого и правого глаза. Каждые 200 мс их практически одновременно (со сдвижкой на десятки микросекунд) спрашивают, "где мы находимся". Как только пришёл запрос - отвечать надо МГНОВЕННО (от запроса до ответа должна пройти пауза от 2 до 12 мкс), вовремя не ответишь - считаешься мёртвым.
Всего на получение новых данных уходит примерно 100 мс: сначала "холостой" кадр, затем "светлый", затем ещё промежуточный (он необходим, чтобы при скользящем затворе, rolling shutter, один кадр вышел полностью светлым, т.е со включённой подсветкой, а второй полностью тёмным), затем "тёмный" кадр, и потом ещё некоторое время на обработку результатов.
Мы стремимся отдавать наиболее свежую информацию, поэтому постараемся войти в ритм: начинать работу аккурат за 100 мс до того, как придёт запрос, чтобы данные были готовы лишь чуть перед тем, как их хватятся.
Пока всё довольно просто. Веселье начинается, если мы хотим именно в этих приборах построить стереокартину...
Для определённости, пусть запросы "где мы находимся" приходят в моменты 0, T, 2T, 3T и так далее, где T=200 мс - период опроса.
Теперь нам оставлена некоторая свобода выбора - придумать, в какой момент будет дан запрос "прислать сырые данные", и спустя короткий промежуток времени контроллер шины пошлёт команду "принять сырые данные", так что левый "глаз" получит информацию о том, что увидел правый, и наоборот. Иными словами, нам позволено выбрать число k от 0 до 1, и теперь запросы на сырые данные будут приходить в моменты kT, kT+T, kT+2T, kT+3T и так далее.
Надо понять, какую задержку от получения данных до их финальной обработки мы хотя бы в теории можем получить.
Что "сырые данные", что обработанные, но с использованием только локальной (от одного глаза) информации - получаются практически одновременно. В смысле, сама экспозиция 2 кадров занимает время, а обработка занимает считанные миллисекунды. Так что первое, что мы можем придумать - запрашивать целевую информацию ("где мы находимся") и сырые данные одновременно, типа "как только получили - так и запросим".
Но это очень грустно: да, мы отправили сырые данные, соседний комплект их почти тут же получил, и теперь, располагая полной информацией, смог построить стереокартину и получить офигительно точные данные о нашем положении в пространстве, только вот ближайшие 200 мс никто его об этом не спросит!
Как результат, у нас уже была задержка в 100 мс от начала измерений до выдачи "одноглазых" данных (если считать, что эти данные соотв середине экспозиции светлого кадра, задержка уже поменьше, 30..70 мс в зависимости от фазировки кадров), но потом совершенно "на ровном месте" задерживаемся ещё на 200. ОБИДНО!
Удивительно долгое время я сидел в ступоре относительно этой ситуации, смотрел как баран на циклограмму информационного обмена, и всё мне казалось, что меня зажали в угол, сделав весь обмен ПОЛНОСТЬЮ СИММЕТРИЧНЫМ, т.е опрашивая оба глаза синхронно. А у меня же один "глаз" должен другому что-то передать, затем этот второй посылку получить, ещё пару миллисекунд подумать - и только тогда у него сложится стереокартинка. Вот ровно сейчас бы его опросить - а НЕЛЬЗЯ, жди 200 мс. Но на этой укороченной неделе немного отвлёкся на батарейки для теодолитов и тахеометров, и на очередной "МКО для бедных" - и резко осенило. ВСЁ ОЧЕНЬ ПРОСТО.
Правильный ответ: k≈0,95, т.е запрос сырых данных надо делать на 190й миллисекунде, затем на 390й, 590й и так далее. А мы должны подстроиться, и начинать измерения на 90й миллисекунде, затем на 290й и так далее. На 190й миллисекунде у нас уже имеются сырые данные, и целевая информация тоже есть, но пока что одноглазая.
Вот в этот самый момент два комплекта обмениваются данными друг с другом, на что у них есть около 10 мс. И наконец, на 200й миллисекунде у них запрашивают целевую информацию. Если со стереокартинкой что-то не сложилось - не страшно, буквально 10 мс назад у них была монокартинка - не так точно, но требованиям удовлетворяет. Если же всё хорошо - то оба комплекта уже обработали "соседские" данные вместе со своими - и по запросу выдадут более точное положение в пространстве. По идее, у них должны получиться абсолютно идентичные результаты, только в разных системах координат.
Наверное, вот эта "близость к единице" смущала, что мы почти до самого конца "периода опроса" дотягиваем, что кажется дофига долго, но ведь мы сами придумываем фазировку нашей собственной работы, так что 0,95 превращается в -0,05.
Внезапно выходит, что тут и нет как такового "ведущего" и "ведомого", каждый исполняет обе роли, что проще для конфигурации. Вообще, никаких специальных мер не требуется для "перехода в стереорежим". Прибор сделал измерения, и подождал немножко - вдруг ему сейчас пришлют данные от соседа. Прислали - он обработал всё скопом. Не прислали - хрен с ним, обработает только свои. Запросили данные - он выдаёт, что у него есть. Т.е, если вдруг нам "подбили глаз" (ну, скорее, сам из строя зачем-то вышел), сосед и глазом не моргнёт, не будет периода "дезориентации", для перенастройки на обычный режим, не нужно никакой перенастройки.
Осталось только оценить более точно, сколько нам надо времени на обработку. Вся часть, что касается решения системы линейных уравнений 6х6 с симметричной положительно определённой матрицей - остаётся в силе, просто эта матрица суммируется из бОльшего числа отдельных, что улучшает её число обусловленности.
И были всё-таки идеи "распараллелить" это дело, я хотел передавать соседу не "сырые данные" как таковые, а как раз свою матрицу и вектор, чтобы сосед их пересчитал в свою систему координат и просуммировал со своей. Матрица 6х6, но за счёт симметрии нужно только 21 значение передать. Ещё 6 значений для вектора ненормированной оценки сдвига, итого 27. Ещё заголовок и CRC, это 29. Идеально: в 32 слова данных влезаем. Тогда издержки стереорежима оказываются совсем смешными.