• Вычисление центра масс за O(1) с помощью интегральных изображений



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

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

      В этой статье я расскажу:

      • Что за задача такая, о которой идет речь;
      • Подробнее об интегральных изображениях;
      • Как использовать интегральные изображения для приближенного решения гравитационной задачи N тел применительно к дискретному полю импульсов (масс-скоростей);
      • Какой недостаток имеет это решение и как его исправить;
      • И, наконец, как за константное время вычислить центр масс для произвольного региона.
      Читать дальше →
    • Чем больше, тем хуже или почему важен игровой цикл

      • Translation


      По мере эволюции геймдизайна в течение последних 20 лет, продолжительность игр постоянно увеличивалась. В The Witcher 3 легко можно наиграть сотни часов, а Factorio или Dwarf Fortress можно вообще перепроходить не один раз.

      Разработчики давно преследуют идею игр с бесконечной реиграбельностью. Отсюда и появились игры-сервисы. Многие геймдизайнеры (особенно на AAA-проектах) смотрят на игровой опыт как на десятки часов геймплея. А это не всегда хорошо.
      Читать дальше →
      • +20
      • 10.2k
      • 8
    • Под чёрным флагом пост, или Как я не выложил ваш видеокурс на трекер

      captain_flint.jpg

      Привет, Хабр! В трудное время мы живем, не находите? Люди эгоистичны, не признают ценность чужих трудов, любят приходить сразу на все готовое. Интеллектуальная собственность для многих вообще выглядит не более чем бюрократической шуткой: «Как же это так, информация должна быть свободной, ведь это ИН-ФОР-МА-ЦИ-Я!!!11». Согласен, в идеале это так. Эти ваши анархии, мятежнические настроения и философии андерграундных хакеров/пиратов, стоящих на страже прав простого люда, мне не чужды. Но парадокс в том, что истинная справедливость – это еще и отплачивать всем за их труд и заслуги, поэтому в большинстве случаев пиратство – антагонистическое предприятие. Но вот политика предоставления услуг по защите интеллектуальной собственности, предлагаемая таким замечательным вендором, как ИнфоПротектор, вызвал у меня праведный гнев.

      Под катом история о том, как я приобрел платный видеокурс, выпал в осадок после осознания того, что я не смогу сохранить видеоролики из оного для повторного просмотра в будущем, разозлился на тех, кто скропал этот квазизащитный софт (который, ко всему прочему, безжалостно лагает и жрет много ресурсов машины) и решил немного восстановить справедливость… Не нарушая закон, конечно же. Amen.
      Читать дальше →
    • Lock-free структуры данных. Основы: откуда пошли быть барьеры памяти

      • Translation

      Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
      Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
      Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
      Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
      Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].
      Передаю слово Полу
    • Флеш-ускорители PCI-E от 800GB до 6.4TB: от рассвета до жизни в обычном ПК/сервере



        Были времена, когда накопители на основе флэш-памяти стоили настолько дорого, что как накопители их даже никто и не рассматривал. Десятки тысяч долларов. Они позиционировались как нечто революционное, способное придать космическую скорость системам хранения данных. Прямо как Intel Optane в последнее время, но о нём пока не будем, пока ещё слишком дорог.

        Наверное, тогда маркетологи и придумали такое название как Flash Accelerator (флеш-акселератор или флеш-ускоритель).

        Хитрость в том, что устройства изначально позиционировавшиеся как ускорители, сейчас трудно продать как SSD, поэтому иногда их можно купить очень выгодно.

        Мотивация


        • Хотелось ли вам за разумные деньги купить SSD размером в несколько терабайт?
        • Чтобы ресурс был на десятки петабайт?
        • Такой, что что бы вы ни делали, вы бы не смогли его исчерпать?
        • При этом с защитой по питанию и сделанный из самых качественных деталей и самой стойкой памяти?

        Поехали!
      • Никогда больше не игнорируйте обучение с подкреплением

        • Translation
        Привет, Хабр! Представляю вашему вниманию перевод статьи «Don’t Ever Ignore Reinforcement Learning Again» автора Michel Kana, Ph.D.

        Обучение с учителем и обучение без учителя — это ещё не все. Все это знают. Начните с OpenAI Gym.

        image

        Собираетесь победить чемпиона мира по шахматам, нардам или го?

        Есть способ, который позволит вам это сделать — обучение с подкреплением.
        Читать дальше →
        • +16
        • 8.6k
        • 5
      • Бесплатная библиотека Wolfram Engine для разработчиков программного обеспечения

        • Translation

        Оригинал перевода в моём блоге

        Пара видео о Wolfram Language


        Почему вы до сих пор не используете технологии Wolfram?


        Что ж, такое случается, и довольно часто. В процессе общения с разработчиками программного обеспечения, они достаточно лестно отзываются о наших технологиях, например о том как они очень помогали им при обучении в школе или в проведении научных работ, но когда после этого я задаю им вопрос: «Итак, вы используете язык Wolfram Language и его вычислительные возможности в своих системах программного обеспечения?» Иногда они отвечают — да, но слишком часто наступает неловкое молчание, и после этого они говорят: «Нет, а разве это возможно?».

        Free Wolfram Engine for DevelopersЯ хочу быть убежден, что ответом на этот вопрос всегда будет только: «Да, это просто!». И чтобы помочь Вам в этом, мы сегодня запускаем бесплатный движок Wolfram Engine для разработчиков (Free Wolf Engine for developers). Это полноценный движок языка Wolfram Language, который можно развернуть в любой системе и вызвать из любых программ, языков, веб-серверов или чего-либо еще…

        Wolfram Engine — это сердце всех наших программных продуктов. Это то, что реализует язык Wolfram, со всем его вычислительным интеллектом, алгоритмами, базой знаний и так тому подобным. Это то, что поддерживает наши настольные продукты (включая Mathematica), а также нашу облачную платформу. Это то, что сидит внутри Wolfram|Alpha, а также во все большем и большем количестве основных производственных систем в мире. И вот, наконец, мы предоставляем возможность бесплатного скачивания этого движка для решения задач использования в своих проектах по разработке программного обеспечения всем желающим.
        Читать дальше →
      • Сеть обменной сортировки со слиянием Бэтчера

          Сортировка является одной из базовых операций при обработке данных, которая используется в самом широком спектре задач. В данной статье будет рассмотрена сеть обменной сортировки со слиянием Бэтчера для параллельной сортировки массива произвольного размера.

          Читать дальше →
          • +17
          • 17.9k
          • 1
        • Уравнение Навье-Стокса и симуляция жидкостей на CUDA

          Привет, Хабр. В этой статье мы разберемся с уравнением Навье-Стокса для несжимаемой жидкости, численно его решим и сделаем красивую симуляцию, работающую за счет параллельного вычисления на CUDA. Основная цель — показать, как можно применить математику, лежащую в основе уравнения, на практике при решении задачи моделирования жидкостей и газов.


          Читать дальше →
        • Posit-арифметика: победа над floating point на его собственном поле. Часть 1

          • Translation
          Часть 2

          От переводчика: Тема формата Posit уже была на хабре здесь, но без существенных технических подробностей. В этой публикации я предлагаю вашему вниманию перевод статьи Джона Густафсона (автора Posit) и Айзека Йонемото, посвящённой формату Posit.
          Так как статья имеет большой объём, я разделил её на две части. Список ссылок находится в конце второй части.




          Новый тип данных, называемый posit, разработан в качестве прямой замены чисел с плавающей точкой стандарта IEEE Standard 754. В отличие от ранней формы — арифметики универсальных чисел (unum), стандарт posit не требует использования интервальной арифметики или операндов переменного размера, и, как и float, числа posit округляются, если результат не может быть представлен точно. Они имеют неоспоримые преимущества над форматом float, включая больший динамический диапазон, большую точность, побитовое совпадение результатов вычислений на разных системах, более простое аппаратное обеспечение и более простую поддержку исключений. Числа posit не переполняются ни в сторону бесконечности, ни до нуля, и «нечисла» (Not aNumber, NaN) — это действия, а не битовые комбинации. Блок обработки posit имеет меньшую сложность, чем FPU стандарта IEEE. Он потребляет меньшую мощность, и занимает меньшую площадь кремния, таким образом, чип может выполнять существенно больше операций над числами posit в секунду, чем FLOPS, при тех же аппаратных ресурсах. GPU и процессоры глубокого обучения, в частности, могут выполнять больше операций на ватт потребляемой мощности, что позволит повысить качество их работы.
          Читать дальше →
        • И все-таки, почему Posit являются достойной альтернативой IEEE 754

            Месяц Posit на Хабре объявлен открытым, а значит я не могу пройти мимо и проигнорировать обрушившуюся на них критику. В предыдущих сериях:

            Новый подход может помочь нам избавиться от вычислений с плавающей запятой
            Posit-арифметика: победа над floating point на его собственном поле. Часть 1
            Posit-арифметика: победа над floating point на его собственном поле. Часть 2
            Испытания Posit по-взрослому

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

            Именно с таким неприятием сегодня сталкивается формат Posit: критикующие зачастую просто “не туда смотрят“ и даже банально неправильно используют Posit в своих экспериментах. В данной статье я попытаюсь объяснить почему.
            Читать дальше →
          • Джулия и параллельные вычисления


              С момента выхода в августе 2018, язык Julia активно набирает популярность, войдя в топ 10 языков на Github и топ 20 самых популярных профессиональных навыков по версии Upwork. Для начинающих стартуют курсы и выпускаются книги. Julia используется для планирования космических миссий, фармакометрики и климатического моделирования.


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

              Читать дальше →
            • Чем быстрее вы забудете ООП, тем лучше для вас и ваших программ

              • Translation

              Объектно-ориентированное программирование — чрезвычайно плохая идея, которая могла возникнуть только в Калифорнии.

              — Эдсгер Вибе Дейкстра

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

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

              Многие люди и раньше обсуждали проблемы ООП, и в конце этого поста я приведу список своих любимых статей и видео. Но прежде я хочу поделиться собственным взглядом.
              Читать дальше →
            • Задача N тел или как взорвать галактику не выходя из кухни




                Не так давно я прочёл фантастический роман «Задача трёх тел» Лю Цысиня. В нём у одних инопланетян была проблема — они не умели, с достаточной для них точностью, вычислять траекторию своей родной планеты. В отличии от нас, они жили в системе из трёх звёзд, и от их взаимного расположения сильно зависела «погода» на планете — от испепеляющей жары до леденящего мороза. И я решил проверить, можем ли мы решать подобные задачи.
                Читать дальше →
              • Коллапс волновой функции: алгоритм, вдохновлённый квантовой механикой

                • Translation
                image

                Алгоритм Wave Function Collapse генерирует битовые изображения, локально подобные входному битовому изображению.

                Локальное подобие означает, что

                • (C1) Каждый паттерн NxN пикселей в выходных данных должен хотя бы раз встречаться во входных данных.
                • (Слабое условие C2) Распределение паттернов NxN во входных данных должно быть подобным распределению паттернов NxN в значительно большом количестве наборов выходных данных. Другими словами, вероятность встречи определённого паттерна в выходных данных должна быть близка к плотности таких паттернов во входных данных.
                Читать дальше →
                • +87
                • 19.1k
                • 6
              • Создание шейдера дыма на GLSL

                • Translation
                • Tutorial
                image
                [Дым на КДПВ несколько сложнее получаемого в туториале.]

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

                Именно поэтому его так сложно обрабатывать в видеопроцессоре: дым можно разбить на поведение одной частицы, повторяемой миллионы раз в различных местах.

                В этом туториале я подробно расскажу о создании шейдера дыма с нуля и научу вас некоторым полезным техникам разработки шейдеров, чтобы вы могли расширить свой арсенал и создавать собственные эффекты.
                Читать дальше →
                • +33
                • 21k
                • 8
              • Бинарная сегментация изображений методом фиксации уровня (Level set method)

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

                В этой статье я кратко рассмотрю понятие метода фиксации уровня и неявно заданных динамических поверхностей (level set method). Также рассмотрю роль этого метода в бинарной сегментации с введением и определением математических конструкций, таких как SDT (Signed Distance Transforms), маркированной карты расстояний.

                Слева — исходное изображение, справа — сегментированное
                Читать далее...
              • Анализ схем уровней для улучшения многопользовательских шутеров

                • Translation


                Мир соревновательных игр находится на подъёме, поэтому всё больше и больше шутеров от первого лица прокладывают себе путь в мир киберспорта. Однако не все эти новые игры успешны в качестве соревновательных многопользовательских игр. Причинами этого могут быть игровые механики, дизайн уровней, а иногда — недостаточное количество игроков. В этой статье я раскрою основы дизайна уровней. Мы не будем останавливаться на ассетах и ресурсах, оживляющих уровень, и обсудим только схемы уровней, на которых игроки могут перемещаться и взаимодействовать.
                Читать дальше →
                • +21
                • 7.6k
                • 3
              • Maple: составление уравнений Лагранжа 2 рода и метод избыточных координат

                  Предисловие



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

                  С Maple (на кафедре была 6-я версия, а у лоточников домой была куплена 8-я) познакомился ещё студентом, когда начинал работать над будущей кандидатской под крылом моего первого (ныше покойного) научного руководителя. Были и добрые люди, что помогли на самом первом этапе разобраться с пакетом и начать работать.

                  И вот так постепенно на его плечи была переложена большая часть вычислительной работы по подготовке диссертации. Диссертация была защищена, а Maple навсегда остался надёжным помошником в научном труде. Часто бывает необходимо быстро оценить какую-нибудь задачу, составить уравнения, исследовать их аналитически, быстро получить численное решение, построить графики. В этом отношении Maple просто незаменим для меня (ни в коем разе не хочу обидеть приверженцев других пакетов).

                  Сделать всё то, что будет предложено читателю под катом, меня подвигла задача принесенная ученицей (приходится ещё заниматься и репетиторством) со школьной олимпиады. Условие задачи таково:
                  Груз, висящий на нити длины L = 1,1 м, привязанной к гвоздю, толкнули так, что он поднялся, а затем ударился в гвоздь. Какова его скорость в момент удара о гвоздь? Ускорение свободного падения g = 10 м/с2.

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



                  И вот тут захотелось проверить решение, полученное с оглядкой на школьную программу по физике независимым способом, например составив дифференциальные уравнения движения этого маятника, да не просто, а с учетом освобождения от связи (в процессе движения нить, считаемая невесомой, провисает и маятник движется как свободная точка).

                  Это послужило катализатором для того, чтобы взять да и откопать свои старые задумки, накопленные ещё со времен работы в оргкомитете Всероссийской Олимпиады студентов по теоретической механике — три года подряд занимался там подготовкой задач компьютерного конкурса. Задумки касались автоматизации построения уравнений движений для механических систем с неудерживающими связями и трением, используя известные всем уравнения Лагранжа 2 рода



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

                  Что касается Maple, то его библиотека для решения задач вариационного исчисления дает возможность быстро получить уравнения Эйлера-Лагранжа, решение которых минимизирует действие по Гамильтону, что применимо для консервативных систем



                  где — функция Лагранжа, равная разности кинетической и потенциальной энергий системы.

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

                  Читать дальше →