Как найти граф (дерево) «среднее» для данного набора графов (деревьев)? Другая задача. Дана последовательность в фиксированном алфавите. На ней отмечены два типа участков, называемых промоторами и генами (на каждом указано направление). Для каждого промотора задана очередь попыток связаться с ним одинаковых объектов. В момент попытки объект успешно связывается, если промотор свободен от всех других объектов; после чего объект начинает двигаться в указанном направлении. При встречном столкновении оба объекта покидают последовательность. Каковы частоты прохождений генов в указанных направлениях. Эта важная задача далека от теоретического анализа и с трудом поддаётся моделированию на многопроцессорных системах.

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

В докладе будет дан обзор второго поколения алгоритмов BFS, с помощью которых были получены результаты для систем IBM Blue Gene/Q Mira и Sequoia, отраженные в редакциях рейтинга Graph500 за 2012-2013 годы. Будут описаны структура для хранения графа, схема декомпозиции данных, принципы балансировки нагрузки и методы, позволяющие в ряде случаев на порядок сократить число ребер, которые необходимо рассмотреть в процессе обхода. Вторая часть доклада будет посвящена новому параллельному алгоритму решения задачи SSSP. Алгоритм характеризуется существенно меньшим по сравнению с известными алгоритмами объемом межпроцессорных коммуникаций. Будут рассмотрены классы оптимизаций, направленные на решение проблемы балансировки нагрузки для больших графов, а также вопросы уменьшения количества итераций алгоритма и числа релаксаций ребер. В докладе будет показано влияние отдельных приемов оптимизации на производительность алгоритмов BFS и SSSP на системах архитектуры IBM Blue Gene/Q. Материалы для доклада любезно предоставлены доктором Fabrizio Petrini (IBM Research) и будут опубликованы в трудах конференции IPDPS-2014.

Каждый день Яндекс обрабатывает сотни миллионов запросов. Группа аналитики поиска ставит перед собой амбициозную цель: понять как устроено это множество и проследить его эволюцию во времени. Изучение структуры позволяет, например, выделять крупные классы запросов и строить специальные системы поиска для них (поиск по людям, поиск по музыке). Выявление трендов помогает, например, готовить систему к изменениям на рынке (рост числа мобильных запросов). Для решения этой задачи строится граф, в котором вершины — это запросы, а связи тем сильнее, чем больше похожи запросы по смыслу. Затем граф кластеризуется и соединяется в похожие кластеры в соседних днях. В докладе будет рассказано, как именно строится граф, какими средствами он кластеризуется, будут продемонстрированы некоторые результаты, показаны проблемы, с которыми приходится сталкиваться.

При решении неструктурированных задач на распределенных вычислительных системах возникает необходимость разбиения исходной высокоразмерной задачи на подзадачи для того, чтобы решать каждую из них на выделенных узлах. При этом требуется сбалансировать использование вычислительных ресурсов и минимизировать межпроцессорные коммуникации. Если исходная задача может быть описана в виде графа или гиперграфа, то задача балансировки может быть решена с помощью алгоритмов сбалансированного разбиения графа. В нашей работе разработан новый многоуровневый алгоритм разбиения графа. Предложены новые эвристики и комбинации эвристик для FM-алгоритма, позволяющие решать задачу минимизации разбиения графа с лучшим качеством.

В докладе представлена GPU-реализация теста производительности Graph500. Основными отличительными особенностями данной custom-реализации является механизм балансировки нагрузки между вычислительными потоками на GPU, а также работа с глобальной битовой маской, хранящей информацию обо всех размеченных вершинах. Данная реализация проводит разметку как массива предшествующих вершин, так и массива уровней, и при этом демонстрирует ускорение в два раза по сравнению со стандартной replicated-реализацией, выполняющей только разметку массива предшествующих вершин.