Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Distributed Neural Launch

No description
by

Serge Ionov

on 20 January 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Distributed Neural Launch

в каждом классе найти минимальный разрез





выбрать минимальный результат
заменить класс на два, полученных применением разреза Сергей Ионов
progsdi@gmail.com

Институт Математики и Механики
УрО РАН Распределенный запуск
нейронных сетей
на множестве
вычислительных узлов Задача Решение Реализация Спасибо за внимание! Задача о размещении узлов нейронной сети на узлах физической сети Двухуровневая задача о назначениях Алгоритм Матильды Штор
и Френка Вагнера Итоговый алгоритм Время ожидания Динамическое изменение конфигурации Разместить нейронную сеть на кластере из физических узлов, выполнив условия: сохранить связность нейронной сети, учитывая топологию физической сети, размещать нейроны пропорционально производительности физических узлов, минимизировать сетевое взаимодействие между физическими узлами Дано Найти Условия 1. связность 2. взаимодействие 3. пропорциональность goo.gl/muuOV - вариант выбора множества выполняемых работ - список работ - список исполнителей - вариант выбора исполнителей - затраты заказчика на выполнение i-работы
j-исполнителем - доход j-исполнителя от выполнения i-работы Кооперативная - решение задачи нижнего уровня Антикооперативная Кооперативная Антикооперативная - множество вариантов выбора работ задачи верхнего уровня Сложность - вариант выбора множества выполняемых работ - список работ - список исполнителей - вариант выбора исполнителей - затраты заказчика на выполнение i-работы
j-исполнителем - доход j-исполнителя от выполнения i-работы - полиномиальная разрешимость - NP-полная задача Разделение графа нейронной сети на классы с минимальной связностью Размещение нейронов по узлам графа
физической сети k - количество узлов физической сети k-1 - количество искомых минимальных разрезов Шаг 0: все узлы принадлежат одному классу Шаг i = [1..k-1]: O(nm+n log(n)) 2 O(n mlog(n /m)) 3 2 O(knm+kn log(n)) 2 Шаг i=[1..n]: s , t - некоторые вершины графа G G - начальный граф 1 строится минимальный разрез C между s и t строится G = (G \ {s ,t }) U {s t } i i i i i i i i i i i i+1 min C - минимальный разрез графа G i 1 O(m+nlog(n)) O(n ) 3 Поиск минимального разреза между вершинами s и t A - множество вершин Шаг 0: A = {s} Шаг i=[1..n-1]: A = A U { }, max На n-1 шаге получен минимальный разрез, равный Шаг 1: Размещение наибольшей группы на физический узел с наибольшей производительностью Шаг i=[2..k]: Размещение последующих групп с сохранением условия связности нейронной сети O(k) Крайний случай с = 2 с = 1 с = 1 с = 1 определение времени ожидания сигналов со входов динамическое изменение конфигурации сети 0 1 2 3 4 5 1 2 3 4 5 0 1 2 3 4 5 1 2 3 4 5 t 1 t 4 t 1-3 t 1-2 t 4-5 условие, учитывающее пропускную способность канала связи условие, учитывающее не прямой доступ к некоторым узлам физической сети Усложнение задачи: алгоритм с динамической коррекцией выбранного распределения - функция производительности узла - отображение узлов нейронной сети на узлы физической сети k k
Full transcript