Найти

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

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

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

  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

  Аннотация ▼

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

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

  А.А. Диченко , И. И. Левин , Д.А. Сорокин

  33-46

  2025-12-30

  Аннотация ▼

  Для реконфигурируемых вычислительных систем на базе ПЛИС эффективными прикладными программами являются параллельно-конвейерные программы, обеспечивающие реальную производительность более 50% от пиковой. Статья посвящена решению проблемы сокращения времени их разработки. Вычислительные структуры таких программ используют большой объём вычислительного ресурса ПЛИС, функционирующих на  высокой тактовой частоте. Однако одновременная максимизация объёма задействованного ресурса ПЛИС и тактовой частоты находится в некотором противоречии, поскольку при большом заполнении снижается вариативность размещения функциональных узлов вычислительных структур и коммутационная матрица ПЛИС при трассировке информационных каналов между ними не обеспечивает требуемых характеристик по времени  распространения сигналов. Более того в современных САПР алгоритмы размещения и трассировки учитывают только архитектурные и геометрические особенности ПЛИС. Поэтому при использовании большого числа специализированных примитивов, вариативность размещения которых крайне мала, достижение высоких тактовых частот в автоматическом режиме синтеза практически невозможно. Для решения этой проблемы также необходимо учитывать информационные зависимости между функциональными узлами вычислительных структур, но характер информационных зависимостей решаемых задач различных предметных областей может существенно отличаться. Поэтому разработчики вынуждены каждый раз вручную размещать на ПЛИС функциональные узлы путём создания скриптовых инструкций топологических ограничений. Время формирования топологических ограничений для ПЛИС прежних поколений было приемлемым, поскольку они содержали, как правило, до нескольких сотен специализированных примитивов. Однако в современных ПЛИС их количество достигает нескольких тысяч и даже десятков тысяч штук, что приводит к значительному увеличению времени разработки эффективных прикладных программ. Предлагаемый метод позволяет автоматизировать процесс разработки топологических ограничений вычислительных структур. Исследования были проведены при разработке прикладных программ решения ряда задач на основе алгоритмов БПФ, AES и
  LU-разложения для реконфигурируемого компьютера «Tertius-2». В результате значительного сокращения временных затрат, обусловленных числом итераций оптимизации вычислительных структур, общее время синтеза было сокращено до трех раз

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

  Е.Р. Мунтян , Э.В. Мельник

  2021-08-11

  Аннотация ▼

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