Найти

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

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

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

  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

  Аннотация ▼

  Статья посвящена нахождению всех целочисленных неотрицательных решений сис-
  темы линейных уравнений второй кратности типов, далее с.л.у., методом последователь-
  ного опробования векторов на принадлежность к решениям системы. Рассматривается
  количество различных векторов, опробование которых на принадлежности к решениям
  с.л.у. приведет к получению всех решений с.л.у. Вектор опробований с.л.у. состоит из эле-
  ментов определяющих число знаков алфавита, имеющих одинаковое число вхождений в
  выборку. С.л.у. связывает между собой число вхождений элементов всех типов в рассмат-
  риваемую выборку, мощность алфавита, объём выборки и ограничение на максимальное
  число вхождений знаков алфавита в выборку. Решение с.л.у. является основой расчета
  точных распределений вероятностей значений статистик и их точных приближений ме-
  тодом второй кратности, где в качестве точных приближений выступают Δточные
  распределения, отличающиеся от точных распределений не более чем на заранее заданную,
  сколь угодно малую величину Δ. Величина, выражающая количество опробуемых векторов,
  является одной из величин определяющих алгоритмическую сложность метода второй
  кратности, без знания значения которой нельзя определить параметры выборок, для ко-
  торых при ограничениях на вычислительный ресурс могут быть рассчитаны точные рас-
  пределения и их точные приближения. Количество различных опробуемых векторов рас-
  сматривается в условиях ограничения на максимальное значение числа вхождений элемен-
  тов алфавита в выборку, так и без ограничений. Найдены аналитические выражения, по-
  зволяющие для любых значений мощности алфавита, объёма выборки и ограничения на
  значение максимального числа вхождений знаков алфавита в выборку вычислять количест-
  во опробований различных векторов для получения всех целочисленных неотрицательных
  решений системы линейных уравнений второй кратности типов. Вид полученного анали-
  тического выражения для количества опробований векторов позволяет использовать его
  при изучении алгоритмической сложности расчетов точных распределений и их точных
  приближений с заранее указанной точностью Δ.