Для авторов
Найти
Результаты поиска
Найдено результатов: 7.
-
ОЦЕНКА ВРЕМЕННЫХ ЗАТРАТ НА УМНОЖЕНИЕ КВАДРАТНЫХ БИНАРНЫХ МАТРИЦ УСТРОЙСТВА С КОНВЕЙЕРИЗАЦИЕЙ ЧТЕНИЯ ДАННЫХ ИЗ СПЕЦИАЛИЗИРОВАННОЙ МНОГОПОРТОВОЙ ПАМЯТИ
А.В. Болгак , Э.И. Ватутин , Д.А. Трокоз6-202025-10-01Аннотация ▼Целью данной работы является оценка временных затрат на умножение квадратных бинарных матриц размером n × n устройства с конвейеризацией операции чтения данных из специализированной многопортовой памяти и ее сравнение с временными затратами прототипа. В данной работе использовались методы математической логики, теории множеств и графов, дискретных систем и устройств ЭВМ, теории проектирования конечных автоматов. В результате исследования было показано, что использование конвейеризации операции чтения данных из специализированной многопортовой памяти позволяет снизить временные затраты на обработку квадратных бинарных матриц размером n ≤ 2048 до 206,3 раза. Из полученных данных видно, что время загрузки и выгрузки исходных и результирующих данных для предложенного устройства существенно выше времени умножения матриц, ввиду чего частые загрузки и выгрузки матриц нецелесообразны. Например, при выполнении операции транзитивного замыкания бинарного отношения, представленного в виде бинарной матрицы, производится однократная загрузка исходной матрицы с последующей серией ее возведения в квадрат, что эффективно реализуется предложенным устройством. На основании полученных результатов можно сделать вывод, что предложенное устройство для умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти обеспечивает существенный выигрыш во времени обработки и умножения квадратных бинарных матриц по сравнению с прототипом. Кроме того, результаты показали, что частые загрузки и выгрузки матриц нецелесообразны для предложенного устройства с конвейеризацией операции чтения из специализированной многопортовой памяти, так как затрачиваемое время на загрузку и выгрузку исходных и результирующих данных существенно превышает время на операцию умножения матриц
-
МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ
М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев21-372025-10-01Аннотация ▼Целью работы является разработка и исследование методов биоинспирированного поиска для решения задач одномерной упаковки в одинаковые контейнеры на базе эффективных алгоритмов кодирования и декодирования решений, композитного критерия и двухуровневой структуры эволюционной памяти. В работе предложена структура упорядоченного кода упаковки одномерных элементов в одинаковые контейнеры главное достоинство которого заключается в том, что одному решению упаковки соответствует один код и наоборот. Поисковая процедура базируется на модифицированной метаэвристике муравьиного алгоритма. На каждой итерации алгоритм одномерной упаковки имеет многостадийную структуру. Стадии выполняются последовательно одна за другой, начиная с первой. Каждая стадия Сk включает процедуры, выполняемые агентом zk. Число стадий равно числу агентов в популяции плюс заключительная стадия итерации. Основная задача, решаемая конструктивным алгоритмом на стадии Сk, заключается в построении кода Rk упаковки множества элементов X в одинаковые контейнеры. Стадия делится на периоды по числу формируемых агентом zk списков Xjк. Период делится на этапы. На каждом периоде последовательно по этапам решаются следующие задачи: агент zk конструктивным алгоритмом формирует набор Rk упорядоченных списков Xjк одномерной упаковки в одинаковые контейнеры; рассчитываются оценки fjk упаковки каждого контейнера Oj элементами списка <Xjк>; рассчитывается количество λjk феромона, пропорциональное оценке fjk; рассчитывается оценка Wk=∑i(fjk) одномерной упаковки множества элементов X в H одинаковых контейнеров; производится отложение феромона на ребрах графа G, соответствующих списку Xjк в ячейки накопительной матрицы памяти E второго уровня. После формирования всеми агентами zk популяции Z упорядоченных списков Rk, накопленный феромон добавляется в основную матрицу памяти Φ первого уровня. Для каждого Rk рассчитывается общий показатель Fk качества упаковки множества элементов X. Заключительная операция на итерации ‒ испарение феромона на ребрах графа G и фиксация zk c лучшим Fk. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников
-
ОЦЕНКА ОСУЩЕСТВИМОСТИ РЕШЕНИЯ ЗАДАЧ НА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ПРИ ГРУППОВОМ ОБСЛУЖИВАНИИ
В.А. Павский , К.В. Павский2022-11-01Аннотация ▼Рост производительности вычислительных систем (ВС) связан как с масштабируе-
мостью, так и с развитием архитектуры вычислительных элементов системы. Кластер-
ные ВС, которые являются масштабируемыми, составляют 93% суперкомпьютеров спи-
ска Top500 и относятся к высокопроизводительным. При этом по – прежнему остается
проблема эффективного и полного использования всего имеющегося вычислительного ре-
сурса суперкомпьютера и ВС для решения пользовательских задач. Отказы элементарных
машин (узлов, вычислительных модулей) снижают технико-экономическую эффектив-
ность вычислительных систем и эффективность решения пользовательских задач. По-
этому при планировании процесса решения задач, уменьшение потерь времени на восста-
новление ВС от сбоев, отказов является важной задачей. Для количественной оценки по-
тенциальных возможностей вычислительных систем используются показатели осущест-
вимости решения задач. Эти показатели характеризуют качество работы систем с уче-
том надежности, временных характеристик и параметров обслуживания поступающих
задач. В работе предлагается математическая модель функционирования вычислительной
системы с накопителем при групповом обслуживании потока задач. Математическая
модель использует методы теории массового обслуживания, основанных на теории веро-
ятностей и системах дифференциальных уравнений. Следует заметить, что методика
составления систем дифференциальных уравнений достаточна проста, если представлена
соответствующая им граф-схема. Однако точное решение систем уравнений и, как прави-
ло, в элементарных функциях, не существует, либо формулы труднообозримы. Здесь реше-
ние получено в стационарном режиме функционирования системы массового обслужива-
ния. Рассчитаны показатели, позволяющие оценить наполненность накопителя. Получен-
ные аналитические решения просты, могут быть использованы для экспресс-анализа
функционирования вычислительных систем. -
ЭВОЛЮЦИОННЫЙ ПОПУЛЯЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
Б.К. Лебедев , О.Б. Лебедев , Е.О. Лебедева2022-11-01Аннотация ▼Рассматривается эволюционный популяционный метод решения транспортной за-
дачи на основе метаэвристики кристаллизации россыпи альтернатив. Исследуется за-
крытая (или сбалансированная) модель транспортной задачи: сумма груза у поставщиков
равно общей сумме потребностей в пунктах назначения. Цель оптимизации – минимизация
стоимости (достижение минимума затрат на перевозку) или расстояний и критерий вре-
мени (затрачивается минимум времени на перевозку). В основу метаэвристики кристалли-
зации россыпи альтернатив положена стратегия, основанная на запоминании и повторе-
нии прошлых успехов. Стратегия делает упор на «коллективную память», под которой
подразумевается любой вид информации, которая отражает прошлую историю развития
и хранится независимо от индивидуумов. В качестве кода решения транспортной задачи
рассматривается упорядоченная последовательность Dk маршрутов. Объектами являют-
ся маршруты, альтернативами – множество позиций P в списке, где np – число позиций в
списке Dк. Множество объектов Dк соответствует множеству всех маршрутов. Множе-
ство альтернативных состояний P объекта соответствует множеству альтернативных
вариантов размещения объекта списке Dк. Работа популяционного эволюционного алго-
ритма кристаллизации россыпи альтернатив опирается на коллективную эволюционную
память, называемую россыпью альтернатив. Под россыпью альтернатив решения в рабо-
те называется структура данных, используемая в качестве коллективной эволюционной
памяти, несущая информацию о решении, включающую сведения о реализованных альтер-
нативах агентов в данном решении и о полезности решения. Разработан конструктивный
алгоритм формирования опорного плана путем декодирования списка Dк. На каждом шаге
t решается задача выбора очередного в последовательности Dк маршрута и определения
количества груза, перевозимого из пункта отправления Ai в пункт назначения Bj по этому
маршруту. Разработанный алгоритм является популяционным, реализующим стратегию
случайного направленного поиска. Каждый агент является кодом некоторого решения
транспортной задачи. На первом этапе каждой итерации l конструктивным алгоритмом
на базе интегральной россыпи альтернатив формируется nk кодов решений
Dk.Формирование каждого кода решения Dk выполняется последовательно по шагам путем
последовательного выбора объекта и позиции. Для построенного кода решения Dk рассчи-
тывается оценка решения ξk и оценка полезности δk. Формируется индивидуальная рос-
сыпь альтернатив Rk и переход к построению следующего кода решения.
На втором этапе итерации производится суммирования интегральной россыпи альтерна-
тив, сформированной на предыдущих итерациях от l до (l-1), cо всеми индивидуальными
россыпями альтернатив, сформированных на итерации l. На третьем этапе итерации l
производится снижение всех интегральных оценок полезности r*αβ интегральной россыпи
альтернатив R*(l) на величину δ*. Алгоритм решения транспортной задачи был реализован
на языке С++ в среде Windows. Сравнение значений критерия, на тестовых примерах, сизвестным оптимумом показало, что у 90% примеров полученное решение было оптималь-
ным, у 2% примеров решения были на 5% хуже, а у 8% примеров решения отличались ме-
нее, чем на 2%. Временная сложность алгоритма, полученная экспериментальным путем,
лежит в пределах О(n2). -
ГИБРИДНОЕ ИСПОЛНЕНИЕ ЗАПРОСОВ К АНАЛИТИЧЕСКИМ БАЗАМ ДАННЫХ
П. А. Курапов2021-07-18Аннотация ▼Для повышения эффективности системам исполнения аналитических запросов необ-
ходимо использовать все доступные ресурсы современных распределенных гетерогенных
систем. Ускорители, сложная иерархия памяти и распределенность вычислений создают
возможности для оптимизации производительности. В статье проводится обзор сущест-
вующих подходов к реализации механизмов исполнения аналитических запросов к СУБД для
данных в оперативной памяти с использованием аппаратных ускорителей, в частности,
особое внимание уделено графическим ускорителям. За счет массивного параллелизма и
высокой пропускной способности памяти устройства графические ускорители представ-
ляют перспективную альтернативу основного устройства исполнения аналитических за-
просов. Существующие методы не задействуют всех возможностей современной аппара-
туры и обычно основываются на передаче данных по относительно медленной шине PCIe
для исполнения ядер каждого отдельно взятого оператора. Другой проблемой существую-
щих методов является явное разделение кодовой базы кодогенераторов реляционных опе-
раторов для ускорителей (графических процессоров) и центрального процессора, и невоз-
можность переиспользования сгенерированного кода для других устройств в системе, что
существенно ограничивает возможности их совместного использования с целью повыше-
ния производительности. В статье представлен метод эффективного исполнения запро-
сов на примере системы из двух классов устройств (ЦПУ и графический процессор) при
помощи компиляции с построением единого, независимого от устройства, промежуточно-
го представления (SPIR-V) и подход к оптимизации соответствующего гибридного физи-
ческого плана запроса на основе расширенного классического оператора “Exchange” с ис-
пользованием гетерогенных вычислительных ресурсов и явным контролем уровня параллелизма для каждого устройства. Для поиска оптимального физического плана предложен
способ построения модели затрат на основе данных о поведении основных вычислитель-
ных паттернов реляционных и вспомогательных операторов. Потенциал прироста произ-
водительности за счет оптимизации запросов целиком для наилучшего с точки зрения про-
изводительности устройства оценивается с помощью эмпирических данных, полученных
для коммерческой СУБД с открытым исходным кодом OmniSci DB. Предварительные ре-
зультаты демонстрируют возможность ускорения обработки запросов в разы (3-8х) при
выборе наиболее подходящего устройства исполнения. -
ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС
Б. К. Лебедев , О.Б. Лебедев , В. Б. Лебедев2020-11-22Аннотация ▼В работе рассматривается поисковый популяционный алгоритм размещения компо-
нентов СБИС. По аналогии с процессом возникновения и формирования кристаллов из ве-
щества, процесс порождения решения путем последовательного проявления и конкретиза-
ции решения на базе интегральной россыпи альтернатив назван методом кристаллизации
россыпи альтернатив. Решение Qk задачи размещения представляется в виде биективного
отображения Fk=A→P, каждому элементу множества A соответствует один единст-
венный элемент множества P и наоборот. Лежащая в основе алгоритма метаэвристика
кристаллизации россыпи альтернатив выполняет поиск решений с учетом коллективной
эволюционной памяти, под которой подразумевается информация, отражающая историю
поиска решения и памяти поисковой процедуры. Отличительной особенностью используе-
мой метаэвристики является учет тенденции к использованию альтернатив из наилучших
найденных решений. Предложены компактные структуры данных для хранения интерпре-
таций решений и памяти. Алгоритм, связанный с эволюционной памятью, стремится к
запоминанию и многократному использованию способов достижения лучших результатов.
Разработанный алгоритм относится к классу популяционных алгоритмов. Итерационный
процесс поиска решений включает три этапа. На первом этапе каждой итерации конст-
руктивным алгоритмом формируется nq решений Qk. Работа конструктивного алгоритма
базируется на базе показателей основной интегральной россыпи альтернатив – матрицы
R, в которой хранятся интегральные показатели решений, полученных на предыдущих
итерациях. Процесс назначения элемента в позицию включает две стадии. На первой ста-
дии выбирается элемент, а на второй стадии – позиция pj. При этом должно выполняться
ограничение: каждому элементу соответствует одна позиция pj. Рассчитывается оценка
ξk решения Qk и оценка полезности δk множества позиций Pk выбранных агентами. В рабо-
те используется циклический метод формирования решений. В этом случае наращивание
оценок интегральной полезности δk в основной интегральной россыпи альтернатив B вы-
полняется после полного формирования множества решений Q. На втором этапе итера-
ции производится наращивание оценок интегральной полезности δk в основной интеграль-
ной россыпи альтернатив – матрице R. На третьем этапе итерации осуществляетсяснижение оценок полезности δk интегральной россыпи альтернатив R на априори заданную величину δ*. Работа алгоритма завершается после выполнения заданного числа итера-
ций. Сравнительный анализ с другими алгоритмами решения производился на стандартных
тестовых примерах (бенчмарках) корпорации IBМ, при этом решения, синтезируемые ал-
горитмом CAF, превосходят по эффективности решения известных методов в среднем на
6%. Временная сложность алгоритма – О(n2)-О(n3). -
ИНТЕЛЛЕКТУАЛЬНЫЙ МЕТОД ИЗВЛЕЧЕНИЯ ЗНАНИЙ НА ОСНОВЕ ОПРЕДЕЛЕНИЯ ТОНАЛЬНОСТИ ОТЗЫВОВ
Е.М. Герасименко , В. В. Стеценко2020-11-22Аннотация ▼В этой работе исследуется влияние возраста и пола при анализе тональности отзы-
вов, поскольку эти данные могут помочь ретейлерам электронной коммерции увеличить
продажи, ориентируясь на определенные демографические группы, а также увеличить
удовлетворение потребностей людей разных возрастных и гендерных групп. Используемый
набор данных сформирован путем сбора отзывов о книгах. Был создан вопросник, содер-
жащий информацию о предпочтениях книжных носителей (мнения пользователей об элек-
тронных книгах, книгах в мягкой и твердой обложках, изображениях и аудиокнигах), а
также данные о возрастной группе и гендерной принадлежности. Помимо этого, вопрос-
ник также содержит информацию о положительном либо отрицательном мнении касае-
мо предпочтений, которая послужила основой достоверности для классификаторов.
В результате, было получено 900 анкет, которые были разделены на группы по половому
признаку и возрасту. Каждая конкретная группа данных была разделена на обучающую и
тестовую. Были проанализированы сегментированные данные на предмет настроений в
зависимости от каждой возрастной группы и пола. Возрастная группа «старше 50 лет»
продемонстрировала лучшие результаты по сравнению со всеми другими возрастными
группами во всех классификаторах; данные в женской группе показали более высокую точ-
ность по сравнению с данными из групп без информации о гендерной принадлежности.
Высокие результаты, показанные этими группами, показывают, что подходы к анализу
тональности способны предсказать настроения в этих группах лучше, чем в других. Анализ
тональности проводился с использованием различных подходов машинного обучения (ML),
включая максимальную энтропию, метод опорных векторов, сверточную нейронную сеть и
долгую краткосрочную память.
1 - 7 из 7 результатов
