Найти

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

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

  А.К. Мельников

  2021-07-18

  Аннотация ▼

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

• ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНОГО ИНФОРМАЦИОННОГО ГРАФА МЕТОДА ПРОГОНКИ В ПАРАЛЛЕЛЬНУЮ ФОРМУ

  Д. В. Михайлов

  177-188

  2021-10-05

  Аннотация ▼

  Множество вычислительных задач может быть представлено в виде последова-тельного информационного графа. В общем случае такой информационный граф не может быть приведён к параллельному виду с целью ускорения выполнения его операций. Но в слу-чае если вершины этого графа обладают свойствами ассоциативности, дистрибутивно-сти и т.д., такой граф можно преобразовать в параллельно-конвейерную форму. Эти пре-образования могут быть произведены не только над графами, содержащими элементар-ные операции – сложение, умножение, логическое И и т.д. – но и над графами, содержа-щими макрооперации. Одним из примеров таких графов является информационный граф решения СЛАУ методом прогонки (методом Томаса). В статье рассмотрено решение для трёхдиагональных СЛАУ. Информационный граф метода прогонки состоит из двух час-тей: прямого хода, в котором выполняется переход от трёхдиагональной формы к двух-диагональной, и обратного хода, в котором непосредственно вычисляются значения неиз-вестных. Несмотря на то, что операции, составляющие базовую макрооперацию метода прогонки, обладают свойством ассоциативности, простое преобразование графа к пира-мидальному виду не даст необходимого результата. Необходимо преобразовать базовые макрооперации особым образом и изменить то, какие данные на них поступают. После этого возможно будет привести граф к пирамидальному виду. Для обратного хода приме-няется аналогичное преобразование графа и составляющих его базовых подграфов. По-скольку для того, чтобы начать вычисления в обратном ходе, нам необходимо полное за-вершение вычислений прямого хода, следует перейти от двух специализированных типов вычислительных блоков к одному универсальному, и построить на его основе универсаль-ную вычислительную структуру.