Найти

Результаты поиска

• АНАЛИЗ ВОЗМОЖНОСТЕЙ СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ ДЛЯ РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК

  А.К. Мельников , И.И. Левин , А.И. Дордопуло , И.В. Писаренко

  6-19

  2021-10-05

  Аннотация ▼

  В статье рассматривается решение вычислительно-трудоемкой задачи – расчета распределений вероятностей значений статистик – с помощью современных вычисли-тельных технологий. Для сокращения вычислительной сложности при обеспечении достаточного уровня эффективности критериев не ниже заданного порога предложено использование Δ-точных приближений. Для расчета точных приближений используется метод второй кратности, основанный на решении системы линейных уравнений, который позволяет при заданном вычислительном ресурсе рассчитывать точные приближения для максимальных значений параметров выборок. Наиболее трудоемкая часть метода второй кратности состоит в процедуре последовательного получения векторов возможных решений и их проверки на принадлежность к самим решениям. Проверка векторов возможных решений на принадлежность к решениям системы информационно независима, поэтому алгоритм расчета можно распараллелить по данным. Приведена формула определения алгоритмической сложности расчета точных приближений распределений вероятностей значений статистик, на основе которой получены оценки сложности современных практических задач для выборок со следующими значениями (N, n) мощности алфавита и объёма выборки: (256,1280), (128,640), (128, 320) и (192,3200) при точности расчета =10-5. Вычислительная сложность расчета составляет от 9,68·1022 до 1,60·1052 операций, средняя порядка 4,55·1025 операций, число проверяемых векторов – от 6,50·1023 до 1,39·1050, а число решений – от 4,67·1012 до 5,60·1025 соответственно. Общее время решения при круглосуточном режиме вычислений не должно превышать 30 дней или 2,592·106 сек. Для полученных оценок сложности проанализированы возможности современных кластерных вы-числительных систем на основе универсальных процессоров, графических ускорителей и реконфигурируемых вычислительных систем на основе программируемых логических интегральных схем. Для каждой технологии определено число вычислительных узлов, требуемых для расчета точных приближений с указанными параметрами в заданное время. Показано, что ни одна из рассмотренных вычислительных технологий на современном уровне развития техники не позволяет получить решение для необходимых параметров расчета точных приближений распределений вероятностей значений статистик. В заключении сделан вывод о необходимости анализа возможностей перспективных вычислительных технологий на основе квантовых и фотонных компьютеров, а также гибридных вычисли-тельных систем для расчета точных приближений распределений вероятностей значений статистик с заданными параметрами в оперативно-приемлемое время

• ГИБРИДНОЕ ИСПОЛНЕНИЕ ЗАПРОСОВ К АНАЛИТИЧЕСКИМ БАЗАМ ДАННЫХ

  П. А. Курапов

  2021-07-18

  Аннотация ▼

  Для повышения эффективности системам исполнения аналитических запросов необ-
  ходимо использовать все доступные ресурсы современных распределенных гетерогенных
  систем. Ускорители, сложная иерархия памяти и распределенность вычислений создают
  возможности для оптимизации производительности. В статье проводится обзор сущест-
  вующих подходов к реализации механизмов исполнения аналитических запросов к СУБД для
  данных в оперативной памяти с использованием аппаратных ускорителей, в частности,
  особое внимание уделено графическим ускорителям. За счет массивного параллелизма и
  высокой пропускной способности памяти устройства графические ускорители представ-
  ляют перспективную альтернативу основного устройства исполнения аналитических за-
  просов. Существующие методы не задействуют всех возможностей современной аппара-
  туры и обычно основываются на передаче данных по относительно медленной шине PCIe
  для исполнения ядер каждого отдельно взятого оператора. Другой проблемой существую-
  щих методов является явное разделение кодовой базы кодогенераторов реляционных опе-
  раторов для ускорителей (графических процессоров) и центрального процессора, и невоз-
  можность переиспользования сгенерированного кода для других устройств в системе, что
  существенно ограничивает возможности их совместного использования с целью повыше-
  ния производительности. В статье представлен метод эффективного исполнения запро-
  сов на примере системы из двух классов устройств (ЦПУ и графический процессор) при
  помощи компиляции с построением единого, независимого от устройства, промежуточно-
  го представления (SPIR-V) и подход к оптимизации соответствующего гибридного физи-
  ческого плана запроса на основе расширенного классического оператора “Exchange” с ис-
  пользованием гетерогенных вычислительных ресурсов и явным контролем уровня параллелизма для каждого устройства. Для поиска оптимального физического плана предложен
  способ построения модели затрат на основе данных о поведении основных вычислитель-
  ных паттернов реляционных и вспомогательных операторов. Потенциал прироста произ-
  водительности за счет оптимизации запросов целиком для наилучшего с точки зрения про-
  изводительности устройства оценивается с помощью эмпирических данных, полученных
  для коммерческой СУБД с открытым исходным кодом OmniSci DB. Предварительные ре-
  зультаты демонстрируют возможность ускорения обработки запросов в разы (3-8х) при
  выборе наиболее подходящего устройства исполнения.