Thursday, January 9, 2014

atmosphere_gm. Российский анонс библиотеки быстрых сеточных методов разделения смесей вероятностных распределений.



Всем добрый день и с Наступившим!


Библиотека

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

Библиотека разделена на пакеты:
  1. kernel - весь BLAS и подобный API, который можно оптимизировать. Также утилиты работы с многомерной кластеризацией на гиперторах и многомерными индексами, поиском корней функции одной переменной.
  2. fractal - описание фракталов.
  3. cyclone - алгоритмы независимые от платформы
    1. phiallocator - максимально оптимизированный и гибкий модуль управления памятью при поточном получении данных. Оптимально работает в том числе с данными, которые поступают неравномерными порциями. Данный пункт очень важен: количество перемещений не должно превышать количество новых данных, и при этом нужно иметь в памяти плоскую матрицу для оптимальной работы в том числе с ее транспонированной версией. Управление детерминировано по времени и может использоваться в программах реального времени.
    2. generator - итератор по фракталам
    3. eye - модуль структуры одной итерации. Работает с информацией с предыдущих шагов при принятии решений (то, что нам известно с предыдущего шага мы не пересчитываем, что во многом зависит от обстоятельств работы и аргументов итерации). В нем сосредоточена вся логика алгоритма. В зависимости от того, как им пользоваться можно получить совершенно разные алгоритмы, в том числе родительский алгоритм Алексея Назарова.
    4. cyclone - примеры управления структурой одной итерации. В настоящий момент сделан двухпараметрический пример для смесей нормальных законов. Всего 150 строчек задают все параметры, весь алгоритм от чтения файла до полного управления структурой одной итерации и параметров сетки, и описания отображения собственно нормального распределения на параметрическую сеть.
BLAS API стандартный. Возможна работы без BLAS вовсе.

Технические возможности оптимизации и использования API

  1. Библиотека написана на языке программирования D (компиляторы dmd (dmc-32 или win64), gdc (с версии 4.9 часть gcc), ldc (llvm компилятор, включен в анонс llvm 3.4)). Язык имеет С прямой API - можно интегрировать с openBLAS, cuBLAS, Intel MKL, MATLAB, Julia, R и т.д.
  2. Возможно использовать библиотеку в системах реального времени. Память управляется самим алгоритмом и не участвует в сборке мусора, поэтому сборщик можно вообще отключить.
  3. В плане оптимизации кода компиляторами библиотека полностью эквивалента аналогичной программе написанной на чистом С. Возможно использовать SIMD или встроеный ассемблер. Весь код, который может быть подвержен оптимизации на уровне железа вынесен в пакет kernel.
  4. Библиотека платформнонезависима. Сейчас работает на всех основных ОС для ПК или серверов. Потом добавлю поддержку смартфонов :-)
  5. Вы можете задать свою функцию правдоподобия в модуле kernel, для этого также нужно сделать согласованную версию кластеризации. Изменение алгоритма при этом не потребуется. По умолчанию алгоритм можно запускать с двумя версиями функции правдоподобия: логарифм произведения сумм (быстрая), или сумма логарифмов сумм (всегда точная).

Стабильность

Программа стабильна и протестирована до уровня RC (release candidate). Сама структура библиотеки располагает к быстрому обнаружению ошибок. Для тестирования использовалась специально созданная система визуализации. В прямом смысле алгоритм тестировался и визуализировался на каждом шаге внутри итерации. При этом API вероятно будет немного меняться согласно пожеланиям пользователей.

Сроки

  1. Препринт по алгоритму будет в середине февраля. С этого момента с удовольствием начну совместную работу (если нужно раньше, прошу связаться со мной). В публикации будут использоваться как можно более заезженные данные, ее основная цель - описание алгоритма, а не выводов. Был бы рад иметь после ряд совместных статей с актуальными данными и уже детальным анализом.
  2. Исходный код будет опубликован под свободной лицензией на github (рассчитываю на совместную поддержку) как только Виктор Юрьевич примет препринт для публикации.
  3. В течении двух недель с момента публикации кода, он будет детально прокомментирован на английском.

Дополнительно

  • Разработана библиотека на основе openGL для визуализации данных в реальном времени. Сейчас 2D, будет и 3D к концу учебного года (к примеру для обобщенных гамма, картинки обещают быть красивыми).
  • Биндинг blas к D.


TODO

  1. Поддержка для kernel различных драйверов:
    1. Intel MKL (в том числе SIMD реализация функции логарифма для ФП и других)
    2. cuBLAS
    3. обобщенная реализация SIMD, в том числе AVX2 и AVX3.
  2. 3D визуализация

3 comments:

  1. Все пока откладывается в связи с обобщением мат. аппарата.

    ReplyDelete
  2. https://github.com/9il/atmosphere_gm - код. Будет переписан и упрощен.

    ReplyDelete
  3. И так, код переписан и упращен =)

    Новый анонс: http://spiceandmath.blogspot.ru/2014/10/atmosphere-gm-statistical-package.html

    ReplyDelete