zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СТРУКТУР

 

Чумаченко С.В., Мищенко А.С.

Украина, г. Харьков,

Харьковский национальный университет радиоэлектроники

 

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

 

1. Постановка цели и задач исследования

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

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

Задачи исследования:

1) Анализ методов оценивания вычислительных структур и поиска кратчайших путей между парой вершин [5-9].

2) Разработка критерия оценивания эффективности вычислительных структур на основе использования графовой модели функциональных блоков цифровых систем на кристаллах с параллельно-треугольными межсоединениями элементов [1-4].

3) Модификация алгоритма Дейкстра для определения средней стоимости межсоединений вычислительной архитектуры для пары вершин графа [5-8].

4) Верификация критерия оценивании эффективности рассматриваемой топологии [1-4].

2. Оценивание топологии связей компонентов цифровой системы для прямоугольно-диагональная структуры G6,11

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

Критерий связан с упрощением обработки графовой структуры, имеющей E дуг и n вершин. Его особенность заключается в вычислении абсолютного и не приведенного к интервалу значения, формируемого стоимостью соединений, умноженной на качество транзакций между всеми парами вершин: .

Применение данной формулы к оцениванию графовой структуры, имеющих 6 вершин и топологию соединения прямоугольно-диагональной структуры, представлена на рис. 1. Здесь граф имеет 11 дуг. Подсчет критерия в соответствии с последней формулой дает:

Модификация оценки эффективности топологии связана с приведением реальных затрат (число дуг E) к максимально возможному количеству  парных соединений в графе , которое обеспечивает качество коммуникационных свойств :

a            b            c

d            e           f

Рис. 1 - Структура соединений процессорных примитивов G6;11

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

При этом платой за качество коммуникаций является мощность соединений, приведенная к максимально возможному количеству ребер:

Целесообразно иметь две оценки: интегральный критерий качества коммуникаций, который неявно определяет затраты времени на среднюю достижимость между каждой парой вершин графовой структуры, а также приведенную к максимально возможному числу мощность соединений, которая демонстрирует стоимость качества инфраструктуры системы, имеющей целевую функцию, минимизирующую среднюю достижимость (длину пути или времени) между парой вершин графовой структуры. В зависимости от числа соединений первый критерий имеет тенденцию к возрастанию от 0 до 1, второй также увеличивается по мере увеличения числа ребер в графе. Поэтому мультиплицирование двух критериев не дает нового свойства при оценивании инфраструктуры достижимостей каждой пары вершин.

Таким образом, необходимо использовать оба критерия для оценивания структурного проекта. Следует также модифицировать алгоритм Дейкстры для вычисления среднего значения достижимостей между парой вершин в графе, что и представлено ниже.

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

Задача. Для графа с единичными весовыми коэффициентами, представленного на диаграмме (см. рис. 1) с соответствующей матрицей смежности (рис. 2), необходимо найти кратчайшие расстояния между всеми парами вершин.

 

 

Рис. 2 - Матрица смежности графа G6,11

 

Подзадача 1. Найти расстояния и указать все кратчайшие пути от вершины а до остальных вершин графа G6,11.

В процессе реализации алгоритма Дейкстры заполняется таблица, количество строк и столбцов которой определяется мощностью множества вершин графа, т.е. 6х6. В заголовках строк таблицы указываются вершины, до которых предстоит найти кратчайшее расстояние (таблица 1).

 

Таблица 1

 

1

2

3

4

5

u=a

r=0

u=b

r=1

u=d

r=1

u=e

r=1

u=f

r=1

b

a, 1

 

 

 

 

c

a,

b, 2

b,2

b,2

b,2

d

a, 1

а, 1

a,1

 

 

e

a,1

a, 1

a,1

 

 

f

a,

b,2

b,2

b,2

 

 

Модифицированные вычисления даются в таблице 2.

Таблица 2

 

1

2

u=a

r=0

u=b

r=1

b

a, 1

 

c

a,

b, 2

d

a, 1

а, 1

e

a,1

a, 1

f

a,

b,2

 

Данные для всех кратчайших цепей из вершины а представлены в таблице 3.

Таблица 3

Цепь

Длина

 

Граф, иллюстрирующий дерево кратчайших цепей из вершины а, представлен на рис. 3.

a            b            c

d            e            f

Рис. 3 - Дерево кратчайших цепей из вершины а графа G6,11

 

Следует заметить, что кратчайшие маршруты из вершин c, d, f и деревья кратчайших путей будут идентичными тем, что построены из вершины а.

Подзадача 2. Для графа, представленного на рис. 1, необходимо найти кратчайшие расстояния и указать все кратчайшие пути от вершины b до всех остальных вершин. В заголовках строк таблицы указываются вершины, до которых предстоит найти кратчайшие расстояния (таблица 4).

Таблица 4

 

1

u=b

r=0

a

b,1

c

b,1

d

b,1

e

b,1

f

b,1

 

Stop

 

Из таблицы 4 видно, что алгоритм Дейкстры остановлен после первого прохода, поскольку все кратчайшие расстояния определены на начальном этапе расстановки меток (1-й столбец).

 

Данные для всех кратчайших цепей из вершины а представлены в таблице 5.

Таблица 5

Цепь

Длина

 

 

 

Дерево кратчайших цепей из вершины b имеет топологию типа «звезда» и представлено на рис. 4.

 

a            b            c

d            e           f

Рис. 4 - Дерево кратчайших цепей из вершины b для графа G6,11

 

Матрица кратчайших расстояний между всеми парами вершин графа G6,11 имеет вид:

 

 

Дерево кратчайших цепей из вершины е будет иллюстрироваться графом, аналогичным графу на рис. 4, где все кратчайшие расстояния также будут равны 1.

В традиционном алгоритме Дейкстры учитывается такой шаг: если полученное значение длины меньше значения метки соседа, то метка соседа заменяется полученным значением длины.

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

4. Выводы

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

Практическая значимость. Рыночная привлекательность анализа эффективности топологии соединения компонентов в структурах актуальна не только для цифровых систем, сетей, телекоммуникаций, но для инфраструктуры городов в условиях существования транспортных заторов.

Перспективы исследования связаны с созданием аналитических моделей оценки эффективности использования инфраструктуры встроенного ремонта для сервисного обслуживания комбинационных цифровых систем с различным уровнем сложности примитивов и структур.

 

Перечень ссылок:

5.      Reliability of Technical Systems / Ed. I.A.Ushakova. Moscow, 1985. 512 (in Russian)

5.      Hahanov V.I., Litvinova E.I., Chumachenko S.V., Guz O.O. Logical associative computer // J. Electronic simulation. .№ 1. 2011. С. 73-90 (in Russian).

5.      Hahanov V., Wajeb Gharibi, Litvinova E., Chumachenko S. Information analysis infrastructure for diagnosis. Information. An international interdisciplinary journal. 2011. Japan. Vol. 14. No 7. Р. 2419-2433.

5.      Hahanov V.I. and others. Infrastructure of intellectual property for SoC simulation and diagnosis service. Springer, Germany, 2011. Р. 289-330.

5.      Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik. Vol. 1. 1959. P. 269-271.

6.      Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ = Introduction to Algorithms. М.: Вильямс, 2006. 1296 с.

7.      Левитин А. В. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. М.: Вильямс, 2006. С. 189-195.

8.      Кузнецов Н.А., Фетисов В.Н. Алгоритм Дейкстры с улучшенной робастностью для управления маршрутизацией в IP-сетях // Автоматика и телемеханика. 2008. № 2. С. 80–85.

9.      Томас Т.М. Структура и реализация сетей на основе протокола OSPF. Руководство Cisco = OSPF Network Design Solutions. М.: Вильямс, 2004. 816 c.



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info