• Авторизация


Упрощенные вычисления 10-07-2011 01:04 к комментариям - к полной версии - понравилось!


Есть идея для научной работы. Берите кто хочет
Писать буду простым языком, в упрощённых терминах на конкретном примере. Желающие могут исследовать эту тему и вывести более точные алгоритмы. Речь идет о компьютерном моделировании очень больших миров.

Постановка задачи
Существует город, состоящий из большого количества зданий. По этому городу можно ходить. Подойдя к одному из зданий, можно увидеть его внешние атрибуты, которые меняются во времени. Например, если это витрина магазина, то мы увидим перечь товаров на прилавке. Этот город может моделироваться в реальном времени на двуядерном процессоре, целиком занимая одно ядро. Товары на прилавках и прочие внешние атрибуты вычисляются по простым законам, т.е. генерятся. Требуется получить возможность не только гулять по городу, но и зайти в любое здание и лицезреть сложное поведение его внутренних механизмов, будь то хлебопекарня, завод, офис или жилой дом. Допустим, алгоритмы, детально описывающие эти сложные процессы, у нас есть, но вычислительные затраты на 1 дом равны затратам процессорного времени на моделирование городских улиц. Требуется иметь возможность заходить куда угодно и на всё зырить. При этом все процессы должны выглядеть для наблюдателя естественными и логичными.

[показать]
Нетрудно догадаться, что при прямом real-time моделировании внутренних процессов всех подсистем задача не имеет решения.

Существующие методы
Неизвестны. Реализаций таких не видел. Если кто-то знает какие-либо научные работы на эту тему, прокомментируйте плз.

Предлагаемый метод
В основе предлагаемого метода лежит эффект Кота Шрёдингера. Суть в том, что когда мы стоим перед закрытой дверью, мы не знаем что там внутри реально происходит и происходит ли вообще. Чудесное предположение заключается в том, что нет никакой уверенности, что Вселенная сама знает что за этой дверью, поскольку ни одного наблюдателя за ней нет. Вероятно, что даже наш "реальный" мир поступает с нами не совсем честно. С другой стороны, т.к. обстановка за дверью неизвестна никому и не может быть вычислена точно, то всё вполне честно. Этот принцип можно использовать для компьютерного моделирования: не важно что там - не вычисляй.

[показать]

При прогулке по городским улицам внешние атрибуты зданий вычисляются упрощенно. Например, на полках магазинов время от времени генерятся товары с разной вероятностью. Такие вычисления занимают одно ядро процессора по условию задачи. Как только мы зашли в здание, включается второе ядро, которое начинает моделировать и показывать нам все внутренние процессы. Первое ядро при этом продолжает делать упрощенные вычисления для всех других зданий и улиц в целом. Когда мы насмотрелись на то как пекарь носит булки на прилавок, мы выходим из здания и закрываем дверь. Что теперь за ней происходит? Этого никто не знает: ни мы, ни программа моделирования, потому что она больше не моделирует процессы внутри этого здания. Программа переключила здание на упрощенные вычисления.

[показать]

Как же синхронизировать упрощенные вычисления и детальные "внутренние" процессы для одной такой подсистемы? Предлагается мыслить в обратном направлении. Сначала описать мат. модель и алгоритмы упрощенных вычислений для каждой подсистемы и считать их выходные данные эталонными. Затем описывать и реализовывать детальное моделирование внутренних процессов таким образом, чтобы выходные данные (кол-во хлеба на прилавке) точно соответствовали результату упрощенного моделирования. Внутренние процессы подсистемы также должны зависеть от внешних атрибутов. В этом направлении есть куда копать! Таким образом, в обоих случаях подсистема выдаёт один и тот же результат, поэтому ведёт себя с точки зрения наблюдателя совершенно честно.

Следует отметить, что если описание процессов реального мира с такими критериями может вызвать сложности, поскольку поведение подсистем уже дано. С другой стороны, если мир не настоящий, а игровой, то описывать детальную логику работы ориентируясь на результаты упрощённого моделирования, становится гораздо проще, поскольку реалистичность не важна.

С помощью приведённого подхода можно организовать моделирования очень больших двухуровневых миров. Уровнями этого логического дерева в данном примере являются город и здание. С использованием большего количества ядер процессора можно организовать моделирование и многоуровневых систем и адаптировать под них предлагаемый метод.

Автор будет благодарен за конструктивную критику и за использование этих идей в любой сфере.
вверх^ к полной версии понравилось! в evernote
Комментарии (15):
10-07-2011-11:38 удалить
http://ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F

Чем то похоже
d0rc 10-07-2011-17:58 удалить
Если твоя мысль заключается в том, что "не надо знать - не вычисляй", то это вообщем-то не ново, в игре wolf3D, именно так все и было устроено - вычислять надо только то, что видно в данный момент.

Если твоя мысль заключается в том, что можно предложить два алгоритма вычисления происходящего - easy vs. heavy для моделирования процессов, и такие, чтобы easy(dataset) == heavy(dataset), то в случае строго равенства - не ясно, чем же они должны отличаться друг от друга, а в случае равенства приблизительного - эта идея лежит в основе любого сжатия с потерями от JPEG до DejaVue, а по точке зрения похоже с идеями фрактального сжатия.

Что же касается общей аналогии, то все же более вероятно, что вселенная вычисляет сама себя, и от того у нее нет проблем с производительностью, поскольку она сама и есть этот процесс. В этом смысле, активность взаимодействия - и есть расстояние, отсюда и эффект кривизны пространства-времени "пропорциональный" количеству вещества (ОТО), и эффект редукции квантового состояния тем более вероятный, чем выше вероятность взаимодействия.
eugene20237 10-07-2011-18:50 удалить
Ответ на комментарий # Нет, это не отложенные вычисления, поскольку всё происходит в реальном времени. Их нельзя отложить.
eugene20237 10-07-2011-19:12 удалить
Ответ на комментарий d0rc # Второе...
easy(external_dataset, dt) == heavy(external_dataset, dt)
easy(internal_dataset, dt) ~== heavy(internal_dataset, dt)
Чем больше dt тем более реалистично для пользователя второе равенство
Мысль моя сырая конечно. Внутренние атрибуты надо вычислять при входе в подсистему. Для для этого надо придумать функцию вида internal_dataset = f(prev_internal_dataset, external_dataset, dt).

Большое спасибо на ссылку про сжатие с потерями и про фрактальное сжатие! Буду копать дальше и искать как применить их принципы!
eugene20237 10-07-2011-19:37 удалить
Исходное сообщение d0rc
Что же касается общей аналогии, то все же более вероятно, что вселенная вычисляет сама себя, и от того у нее нет проблем с производительностью, поскольку она сама и есть этот процесс. В этом смысле, активность взаимодействия - и есть расстояние, отсюда и эффект кривизны пространства-времени "пропорциональный" количеству вещества (ОТО), и эффект редукции квантового состояния тем более вероятный, чем выше вероятность взаимодействия.

Применением этой теории будут распределённые вычисления на клиентах в онлайн играх Кое-где такое уже успешно применяется, вместе с проверкой читерства. По-моему очень правильное направление. Вселенная вычисляет сама себя - сколько игроков, столько и компьютеров в ботнете
Вероятно, что даже наш "реальный" мир поступает с нами не совсем честно.

----
Не, он, гад, не по принципу Шредингера работает. Протекшие трубы гарантируют это :)
----
Этот принцип можно использовать для компьютерного моделирования: не важно что там - не вычисляй.

----
Насколько я помню, похожий принцип был использован в Carmageddon (или как-то так, не помню название). Разрушаемые объекты не были разрушаемыми, пока на них не наткнешься.
----
[qupte]вычислять надо только то, что видно в данный момент.[/qupte]
----
Я считаю что видео-карта так и работает. Можно показать на примере слабой машины и мощной игры. Если смотреть вперед, где происходит сложное действо - начнет тормозить, опустишь камеру в пол - часть лагов пройдет, ибо действо выходит за пределы экрана и часть нагрузки спадает.

----
Идея интересная, но частями я не совсем понял о чем идет речь. К тому же такая система будет очень ресурсоемкая (или я ошибаюсь?)
eugene20237 11-07-2011-18:06 удалить
Ответ на комментарий Акира_Томео # Это всё не про то )
eugene20237 12-07-2011-02:03 удалить
Ответ на комментарий Акира_Томео # То невидимое, что находится за дверью предлагаю вычислять, но упрощенно. А наблюдатель всё равно не сможет проверить точность этих результатов, да и не важна она.
eugene20237 12-07-2011-02:19 удалить
Хе-хе, а вот ещё что подумалось. Допустим детальное тяжелое моделирование описывается следующим алгоритмом:
while (true)
{
simulate_subsystem(getTimer() - last_time);
last_time = getTimer();
sleep(10 ms);
}

Упрощённые вычисления могут быть например такими:
while (true)
{
simulate_subsystem(getTimer() - last_time);
last_time = getTimer();
sleep(100 ms);
}

Просто вызываем ту же самую функцию real-time моделирования в 10 раз реже. Правильно написанный алгоритм всё равно отработает как надо, потому что она учитывает разницу по времени. Даже все столкновения правильно определит. Таким образом уже можно свободно моделировать 10 невидимых подсистем, а не одну.
d0rc 12-07-2011-05:23 удалить
Ответ на комментарий eugene20237 # ты за деревьями не видишь леса - вся сложность скрывается во фразе "Правильно написанный алгоритм всё равно отработает как надо". Если алгоритм представим в виде линейной операции, то действительно нет проблем. И даже не надо так сильно изъебываться и делать system()/subsystem() и проч. Например, x = x0 + v*t + at**2/ - линейное уравнение, мы можем подставить любое значение t и посмотреть какие будут координаты.

Но проблемы начинаются тогда, когда вычисления оказываются плохо разложимы в линейные операции, слово "плохо" здесь означает, что не существует линейного оператора такого, чтобы спектр его собственных значений совпадал со спектром собственных значений оператора, описывающего эволюцию системы. Это может быть, например, какая-нибудь рекурсия. И так далее. Несжимаемые вычисления, то есть такие, что нельзя просто "проскипать" интервал времени. И физическая реальность именно такая, да и 99% задач по моделированию естественным образом такие же.
eugene20237 12-07-2011-05:43 удалить
Ответ на комментарий d0rc # Наверное я использовал не правильные термины. Я вовсе не претендовал на универсальность. Однако, перед тем как я написал этот пост, я попробывал в своей игре (в серверной части) вызывать событие моделирования в 5 раз реже и ничего не ухудшилось вообще (для постоянно наблюдаемого мира!). В игре летают космические корабли между ключевыми точками, развозят грузы, торгуют со станциями, стреляют друг в друга... Потому что полёты, например, отлично описываются приведенным линейным уравнением.

Теперь представим себе какую-нибудь базу, которую игроки будут строить на Богом забытых планетах. Эта игровая логика примерно такая же как в StarCraft и т.п. Выбор маршрутов и движение по ним. Причем большую часть времени только движение. Бои вообще можно переложить на какую-нибудь ролевую систему типа DnD, чтобы не проверять пересечений. Всё будет работать. А когда игрок снова посетит свою любимую базу он увидит, что все юниты находятся в логичных с его точки зрения местах и что мир живёт. Вот вам область применения упрощенных вычислений.
d0rc 12-07-2011-05:48 удалить
Ответ на комментарий eugene20237 # Если у тебя есть процессы, описываемые линейными уравнениями, значит, ты можешь вообще не вызывать моделирование, а сразу узнать, когда будут особые точки, и запланировать событие на нужный момент времени, превращая таким образом пустое молотилово процессором в те самые несжимаемые вычисления.
eugene20237 12-07-2011-05:54 удалить
Ответ на комментарий d0rc # Теоретически да. Например, там есть случайные события, которые могут возникнуть между ключевыми точками... А вообще интересно, что если написать конвертер heavy-программы, написанной для этого на каком-нибудь специальном языке, в программу, содержащую только несжимаемые вычисления. Это было бы супер... А может уже есть такие наработки в мире?
eugene20237 15-07-2011-06:06 удалить
Вот ещё идея. Насмотревшись разных фильмов, подумалось следующее.
Время на разных уровнях системы идёт по разному: чем глубже вложена подсистема, тем быстрее идёт там время. Уточню, что под "временем", я имел в виду среднюю скорость процессов. Например электроны в ядре летают значительно быстрее чем планеты вокруг солнца. Как это можно использовать? Точно не знаю, но ясно что это свойство делает подсистему на уровень ниже труднопредсказуемой, а раз предсказать там ничего нельзя, то можно смело упрощать эти вычисления и нагло сжимать их, оставляя в стороне реальное моделирование. "Компрессия" будет конечно же необратимой.
d0rc 16-07-2011-00:22 удалить
eugene20237, попытка написать несжимаемую программу - это оптимизация, так что - наработок очень много, но универсального решения нет. Были попытки написать супер-компилятор, но они, насколько мне известно, не увенчались успехом. Так или иначе, такого рода оптимизация, скорее всего, потребует полного перебора всех возможных вариантов, в качестве оптимальной стратегии. Не следует, однако, сбрасывать со счетов тот факт, что у нас нет уверенности, что концепция вычислений, которой мы располагаем единственно возможная.

По поводу разной характеристической скорости течения времени в подсистемах, и сжатия вычислений с потерями, ты возвращаешься к тем же идеям, что и раньше, тем самым, что перекликаются с идеей фрактального сжатия.


Комментарии (15): вверх^

Вы сейчас не можете прокомментировать это сообщение.

Дневник Упрощенные вычисления | eugene20237 - Дневник eugene20237 | Лента друзей eugene20237 / Полная версия Добавить в друзья Страницы: раньше»