Найти

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

• ПРЕДСТАВЛЕНИЕ ГРАФОВ С АССОЦИАТИВНЫМИ ОПЕРАЦИЯМИ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ SET@L

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

  2020-10-11

  Аннотация ▼

  Как правило, информационный граф с ассоциативными операциями реализуется в
  виде последовательной («голова/хвост») или параллельной («разбиение пополам») топ о-
  логии, причем обе структуры содержат одинаковое число операционных вершин. Реду к-
  ционные преобразования графов с представленными топологиями при недостатке в ы-
  числительного ресурса не обеспечивают создание эффективной ресурсонезависимой пр о-
  граммы: вариант «разбиение пополам» характеризуется нерегулярной межитерацион-
  ной коммутацией, а структура «голова/хвост» – увеличенной скважностью данных при
  редукции. В данной статье предлагается преобразовать топологию графа с ассоци а-
  тивными операциями в один из комбинированных вариантов с последовательными и па-
  раллельными фрагментами вычислений, синтезированный в соответствии с заданным
  вычислительным ресурсом. Это позволяет повысить удельную производительность в ы-
  числений при редукции. Модифицированная топология включает изоморфные подграфы с
  топологией «разбиение пополам», содержащие максимальное число аппаратно реализу е-
  мых операционных вершин, а обработка промежуточных данных осуществляется по
  принципу «голова/хвост». Вычислительная структура для рассмотренной топологии
  имеет минимальную латентность и состоит из одного базового подграфа и одной вер-
  шины, в которую редуцируется блок обработки промежуточных данных с топологией
  «голова/хвост». Разработан алгоритм, позволяющий в зависимости от доступного а п-
  паратного ресурса перейти от базового последовательного варианта реализации к раз-
  личным комбинированным топологиям вплоть до предельного случая топологии «разби е-
  ние пополам». Поскольку традиционные методы параллельного программирования могут
  описать множество топологий только в виде набора отдельных подпрограмм, для соз-
  дания ресурсонезависимого описания графов с ассоциативными операциями предлагае т-
  ся использовать язык архитектурно-независимого программирования Set@l. Принципы
  построения топологий «голова/хвост» и «разбиение пополам» описаны в виде признаковметода обработки множеств на языке Set@l, а ресурсонезависимая программа оперирует
  этими типами и типами параллелизма для модификации топологии графа и последующей
  редукции производительности в соответствующих аспектах программы.

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

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

  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 сек. Для полученных оценок сложности проанализированы возможности современных кластерных вы-числительных систем на основе универсальных процессоров, графических ускорителей и реконфигурируемых вычислительных систем на основе программируемых логических интегральных схем. Для каждой технологии определено число вычислительных узлов, требуемых для расчета точных приближений с указанными параметрами в заданное время. Показано, что ни одна из рассмотренных вычислительных технологий на современном уровне развития техники не позволяет получить решение для необходимых параметров расчета точных приближений распределений вероятностей значений статистик. В заключении сделан вывод о необходимости анализа возможностей перспективных вычислительных технологий на основе квантовых и фотонных компьютеров, а также гибридных вычисли-тельных систем для расчета точных приближений распределений вероятностей значений статистик с заданными параметрами в оперативно-приемлемое время

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

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

  2022-11-01

  Аннотация ▼

  Статья посвящена оценке аппаратного ресурса вычислительных систем для решения
  вычислительно-трудоемкой задачи – расчета распределений вероятностей значений ста-
  тистик методом второй кратности на основе Δ-точных приближений для выборок объе-
  мом от 320 до 1280 знаков при мощности алфавита от 128 до 256 символов с точностью
  =10-5. Общее время решения не должно превышать 30 дней или 2,592·106 секунд при круг-
  лосуточном режиме вычислений. Использование свойств метода второй кратности позво-
  ляет привести вычислительную сложность расчета к диапазону 9,68·1022–1,60·1052 опера-
  ций с числом проверяемых векторов – от 6,50·1023 до 1,39·1050. Решение этой задачи для
  указанных параметров выборок в заданное время с помощью современных вычислительных
  средств (процессоров, графических ускорителей, программируемых логических интеграль-
  ных схем) требует недостижимого на практике аппаратного ресурса. Поэтому в статье
  анализируются возможности перспективных квантовых и фотонных технологий для ре-
  шения задачи с заданными параметрами. Основным преимуществом квантовых вычисли-
  тельных систем является высокая скорость вычислений для всех возможных значений па-
  раметров. Однако, для расчета распределений вероятностей значений статистик кванто-
  вое ускорение не будет достигнуто из-за необходимости проверки всех полученных реше-
  ний, число которых соответствует размерности задачи. Кроме того, текущий уровень
  развития элементной базы не позволяет создавать и использовать квантовые вычислите-
  ли с разрядностью 120 кубитов, необходимой для решения рассматриваемой задачи. Фо-
  тонные вычислители могут обеспечить высокую скорость вычислений при низком энерго-
  потреблении и для решения рассматриваемой задачи требуют наименьшее число узлов.
  Однако, нерешенные проблемы с физической реализацией элементов оперативного хране-
  ния данных и отсутствием доступной элементной базы не позволяют в обозримой пер-
  спективе (5–7 лет) использовать фотонные вычислительные технологии для расчета рас-
  пределений вероятностей значений статистик, поэтому наиболее целесообразно примене-
  ние гибридных вычислительных систем, содержащих узлы различных архитектур.
  Для реализации задачи на различных аппаратных платформах (универсальные процессоры,
  графические ускорители, программируемые логические интегральные схемы) и конфигура-
  циях гибридных вычислительных систем предложено использование архитектурно-
  независимого языка программирования высокого уровня SET@L, объединяющего представ-
  ление вычислений в виде множеств и совокупностей с помощью альтернативной теории
  множеств П. Вопенка с абсолютным параллелизмом информационного графа и парадиг-
  мами аспектно-ориентированного программирования.

• КОМПЛЕКС СРЕДСТВ ТРАНСЛЯЦИИ ПРОГРАММ НА ЯЗЫКЕ C В ПРОГРАММЫ НА ЯЗЫКЕ ПОТОКА ДАННЫХ COLAMO

  А. И. Дордопуло, A.A. Гуленок, А.В. Бовкун, И.И. Левин, В. А. Гудков, С.А. Дудко

  2021-02-25

  Аннотация ▼

  Рассматриваются программные средства трансляции последовательных программ
  на языке C в масштабируемые параллельно-конвейерные программы на языке программи-
  рования реконфигурируемых вычислительных систем COLAMO. В отличие от существую-
  щих средств высокоуровневого синтеза, результатом трансляции является не IP-ядро
  фрагмента задачи, а комплексное решение задачи для многокристальных реконфигурируе-
  мых вычислительных систем с автоматической синхронизацией информационных и управ-
  ляющих сигналов. Рассмотрены основные этапы трансляции последовательной программы
  на языке C: преобразование в информационный граф, анализ информационных зависимо-
  стей и выделение функциональных подграфов, преобразование в масштабируемую ресурсо-
  независимую параллельно-конвейерную форму и масштабирование программы на языке
  COLAMO для заданной многокристальной реконфигурируемой вычислительной системы.
  Масштабирование программы осуществляется с помощью методов редукции производи-
  тельности абсолютно-параллельной формы задачи – информационного графа, который
  адаптируется под архитектуру реконфигурируемой вычислительной системы. Разрабо-
  тан ряд правил, позволяющих существенно сократить число шагов преобразований при
  масштабировании задачи и обеспечить плотный поток обработки данных в функциональ-
  ных подграфах задачи. Созданный комплекс средств трансляции программ на языке C в
  конфигурационные файлы ПЛИС позволяет существенно сократить время синтеза вычис-
  лительной структуры задачи для многокристальных РВС и обеспечить сокращение общего
  времени решения задачи.