Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения

Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас гра...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
Hauptverfasser:	Турчина, В.А., Федоренко, Н.К.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Оптимальное управление и методы оптимизации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207448
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207448
record_format	dspace
spelling	irk-123456789-2074482025-10-08T00:07:14Z Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения Дослідження впливу транзитивних дуг на оптимальність деяких алгоритмів паралельного упорядкування Research of the Transitive Edges Influence on the Optimality of Some Scheduling Algorithms Турчина, В.А. Федоренко, Н.К. Оптимальное управление и методы оптимизации Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптимальність отриманого за алгоритмом розв’язку. Transitive edges influence on the optimality of the scheduler built by the algorithm based on the lexicographic principle is considered. The sufficient condition when transitive edges don’t influence the optimality of the solution is given. Besides the class of graphs describing not branching arithmetic expressions is studied and it’s proved that transitive edges don’t influence optimality of the schedule for such graphs with transitive edges. 2012 Article Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207448 519.8 10.1615/JAutomatInfScien.v44.i2.40 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Турчина, В.А. Федоренко, Н.К. Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения Проблемы управления и информатики
description	Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптимальність отриманого за алгоритмом розв’язку.
format	Article
author	Турчина, В.А. Федоренко, Н.К.
author_facet	Турчина, В.А. Федоренко, Н.К.
author_sort	Турчина, В.А.
title	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
title_short	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
title_full	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
title_fullStr	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
title_full_unstemmed	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
title_sort	исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207448
citation_txt	Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT turčinava issledovanievliâniâtranzitivnyhdugnaoptimalʹnostʹnekotoryhalgoritmovparallelʹnogouporâdočeniâ AT fedorenkonk issledovanievliâniâtranzitivnyhdugnaoptimalʹnostʹnekotoryhalgoritmovparallelʹnogouporâdočeniâ AT turčinava doslídžennâvplivutranzitivnihdugnaoptimalʹnístʹdeâkihalgoritmívparalelʹnogouporâdkuvannâ AT fedorenkonk doslídžennâvplivutranzitivnihdugnaoptimalʹnístʹdeâkihalgoritmívparalelʹnogouporâdkuvannâ AT turčinava researchofthetransitiveedgesinfluenceontheoptimalityofsomeschedulingalgorithms AT fedorenkonk researchofthetransitiveedgesinfluenceontheoptimalityofsomeschedulingalgorithms
first_indexed	2025-10-08T01:10:00Z
last_indexed	2025-10-09T01:05:31Z
_version_	1845464328428322816
fulltext	© В.А. ТУРЧИНА, Н.К. ФЕДОРЕНКО, 2012 62 ISSN 0572-2691 УДК 519.8 В.А. Турчина, Н.К. Федоренко ИССЛЕДОВАНИЕ ВЛИЯНИЯ ТРАНЗИТИВНЫХ ДУГ НА ОПТИМАЛЬНОСТЬ НЕКОТОРЫХ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОГО УПОРЯДОЧЕНИЯ Введение При решении различных практических задач часто возникает необходимость распределения некоторого конечного множества частично упорядоченных одно- родных заданий между некоторым числом исполнителей. Примерами таких задач могут быть:  распараллеливание вычислений на многопроцессорных ЭВМ;  распределение некоторого количества работ между исполнителями;  определение порядка выполнения заданий на оборудовании. При этом возникает необходимость минимизации либо общего времени, по- траченного на выполнение всех заданий, либо количества исполнителей для вы- полнения заданий. Математической моделью, определяющей частичный порядок выполнения работ, может быть ориентированный граф, а сама задача построения расписания становится задачей построения параллельного упорядочения минимальной длины или минимальной ширины. В общем случае задачи такого класса относятся к NP-сложным и не могут быть решены алгоритмом полиномиальной сложности. Только для некоторых частных случаев, касающихся либо структуры графов, либо ограничений на ширину или длину упорядочения, известны алгоритмы полиномиальной сложности. Частично это касается известного алгоритма построения оптимального параллельного упо- рядочения ширины 2 )2( h [1], приведенного ниже. Известно, что этот алгоритм является точным, когда в графе нет транзитивных дуг (которые не несут суще- ственной информации с точки зрения практического толкования задачи). А вот для алгоритма [2], который также строит оптимальное параллельное упорядоче- ние ширины 2, транзитивные дуги не влияют на оптимальность. Более того, вве- дение всех возможных транзитивных дуг упростит поиск оптимального упорядо- чения. На практике в заданных орграфах часто встречаются транзитивные дуги. При задании порядка выполнения некоторых работ мы всегда можем определить от- ношение предшествования для них, но при этом не всегда можем отследить, явля- ется ли это отношение транзитивным. Поэтому задача выделения таких подклассов графов, для которых можно найти точное решение за полиномиальное время независимо от наличия транзи- тивных дуг в графе, является актуальной. 1. Постановка задачи Задан ориентированный ациклический граф },,{ UVG  nV  (он является моделью, определяющей отношение частичного порядка на конечном множестве однородных заданий, которые должны быть выполнены). Необходимо разместить вершины этого орграфа на минимальном количестве мест l так, чтобы: 1) количество вершин на каждом месте не превышало заданной константы h (количества исполнителей); 2) если пара вершин ,),( Uvv ji  то вершина iv находится левее вершины .jv Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 63 Построенное размещение S называют параллельным упорядочением вершин орграфа G [3]. Очевидно, что для каждой вершины существует некоторое количество мест, которые она может занимать при данной конкретной ширине упорядочения h, ведь эта вершина не может находиться в упорядочении раньше, чем будут упоря- дочены все предшественники, и должна быть размещена так, чтобы в упорядоче- ние попали все вершины, следующие за ней. Параллельное упорядочение, постро- енное для ,nh  в котором каждая вершина занимает самое крайнее левое допу- стимое место, обозначают ,S а его длину (количество занятых мест) — .l Параллельное упорядочение, построенное для ,nh  в котором каждая вершина занимает самое крайнее правое допустимое место, обозначают ,S а его длину (количество занятых мест) — l (при этом ).ll  Множество вершин, располо- женных на месте k в упорядочении S, обозначаются ].[kS Понятно, что ]1[S со- держит все вершины графа, не имеющие входящих дуг, ][ lS — вершины, не имеющие исходящих дуг. 2. Алгоритм, основанный на лексикографическом принципе [1] Определение 1. Пусть имеется две числовые последовательности  },,,{ 21 m  и },,,,{ 21 k  в которых i и j расположены в убы- вающем порядке. Тогда считается, что последовательность  лексикографически меньше, чем последовательность  ),(   если выполняется одно из следующих условий: 1) ;11  2) ,ii  mi ,1 );( km 3) ,ii  si ,1 );( ksms  и .11   ss Алгоритм решает задачу в два этапа. I. Расстановка меток. 1. Ищем в графе G множество вершин, из которых не исходят дуги (количе- ство таких вершин равно ),][ lS и в произвольном порядке этим вершинам при- сваиваем метки .][,,2,1 lS 2. Удаляем из графа все вершины, которые получили метки, вместе с входя- щими в них дугами. 3. Переходим ко второму этапу, если все вершины получили метки. 4. Ищем в графе G множество вершин, которые не имеют исходящих дуг, и для каждой из них записываем список всех меток тех вершин, которые в исход- ном графе непосредственно следуют за данной. Метки в списке располагаем в по- рядке убывания, и вершина, которой отвечает наименьшая лексикографическая последовательность меток, получает следующую по порядку метку. Если двум вершинам соответствуют одинаковые последовательности, то следующие две метки присваиваем им произвольным образом. По этому принципу ставим метки всем вершинам, из которых не выходят дуги. Переходим на шаг 2. II. Построение упорядочения. 1. Ищем в графе G множество вершин, в которые не входят дуги, и распола- гаем их в порядке убывания меток. Если количество таких вершин не больше h, то заносим их на первое свободное слева место в упорядочении S, а если больше, за- носим на это место первые h вершин. 2. Удаляем из графа G выбранные вершины вместе с дугами, которые из них исходят. 3. Алгоритм заканчивает работу, если все вершины распределены, иначе воз- вращаемся на первый шаг. 64 ISSN 0572-2691 Доказано, что этот алгоритм дает точное решение для случая, когда ,2h при условии отсутствия в графе транзитивных дуг. 3. Влияние транзитивных дуг на оптимальность алгоритма При наличии в графе транзитивных дуг решение, полученное заданным алго- ритмом, может быть неоптимальным (пример 1) и оптимальным (пример 2). Пример 1. Для графа, изображенного на рис. 1, множество }10,9,8,7,6{][ lS и при указанных метках вершин этого множества параллельное упорядочение, построенное по алгоритму, имеет вид . 7952 6810431       S Пример 2. Для графа на рис. 1 изменим метки вершин таким образом, как показано в таблице. Получим по алгоритму такое парал- лельное упорядочение: . 79562 810413       S В рассмотренных примерах на опти- мальность решения влияет расстановка ме- ток на последнем уровне (только на нем, со- гласно алгоритму, метки присваиваются произвольным образом). Добавим к графу, рассматриваемому в этих примерах, не- сколько вершин. Получим новый граф (пример 3), для которого при наличии тран- зитивных дуг упорядочение будет неопти- мальным при любой расстановке меток по- следнего уровня. Пример 3. Для графа, изображенного на рис. 2, параллельное упорядочение, по- строенное по алгоритму, имеет вид . 13127952 14116810431       S Оптимальное параллельное упорядоче- ние запишем . 141279562 1311810413*       S Возникает вопрос: можно ли по свойствам графа, имеющего транзитивные дуги, утверждать, что рассмотренный выше алгоритм даст оптимальное решение? То есть перед нами ставится задача выделения класса графов, для которых нали- чие транзитивных дуг не влияет на точность алгоритма, основанного на принципе расстановки лексикографических меток. Введем вспомогательное определение. Определение 2. Будем говорить, что вершины iv и jv принадлежат одному уровню, если в упорядочении S они расположены на одном месте. При этом бу- 7(2) 6(1) 2(10) 8(3) 9(4) 10(5) 1(9) 4(6) 5(7) 3(8) Рис. 1 Таблица Номер вершины Метки вершин, следующих за данной Метка Этап 1 6 — 5 7 — 1 8 — 2 9 — 3 10 — 4 Этап 2 4 1 6 5 4, 3, 2 7 Этап 3 1 7, 6, 1 8 2 7, 6, 2 9 3 7, 6, 5 10 6(5) 4(10) 2(14) 7(6) 1(13) 8(7) 9(8) 10(9) 5(11) 3(12) 11(4) 12(3) 13(2) 14(1) Рис. 2 Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 65 дем считать, что вершины, которые принадлежат ],[ lS находятся на первом уровне, а вершины, которые принадлежат ],1[S — на уровне с номером .l Пусть задан орграф G, который не имеет транзитивных дуг, и для него по лексикографическому принципу построено оптимальное упорядочение S шири- ны 2 и длины ,l и граф ,G отличающийся от графа G наличием в нем транзи- тивных дуг, для которого построено упорядочение S ширины 2 и длины .ll  Рассмотрим возможные причины увеличения длины упорядочения S. Можно утверждать, что длина упорядочения увеличивается тогда, когда в нем есть «кри- тические» вершины iv и ,jv т.е. такие, что в упорядочении S вершина iv рас- положена левее ,jv а в упорядочении S — правее ,jv и за счет этого длина упо- рядочения увеличивается (рис. 3). Очевидно, что вершины iv и jv должны быть расположены на одном уровне (иначе их расположение однозначное и не может измениться от появления транзитивных дуг). Упорядочение S Вершины iv Вершины, которые Другие вершины упорядочения с неизменным расположением jv зависят от iv а Упорядочение S Вершины jv iv Вершины, которые Другие вершины упорядочения с неизменным расположением зависят от iv б Рис. 3 Рассмотрим подробнее, как именно могут транзитивные дуги влиять на дли- ну упорядочения. Пусть в орграфе G вершине iv соответствует последователь- ность меток ),,,,( 21 m  а вершине jv — последовательность меток ).,,,( 21 k  Так как в исходном упорядочении вершина iv расположена левее ,jv то можно утверждать, что либо ),,,(),,,( 2121 km   и метки выбраны однозначно, либо ),,,(),,,( 2121 km   (причем ,pp  mp ,1 и ),km  метки выбраны случайно и вершине iv присвоили бóльшую метку. Рассмотрим случай равенства ),,,,(),,,( 2121 km   т.е. метки выбраны случайно и вершина iv получила бóльшую метку. Поскольку случайный выбор меток не влияет на оптимальность строящегося упорядочения, очевидно, что для вершин iv и jv порядок не имеет значения, т.е. оптимальность не будет нарушена вследствие добавления транзитивной дуги. Рассмотрим ситуацию неравенства ).,,,(),,,( 2121 km   Пусть добавлена транзитивная дуга, исходящая из jv и входящая в некоторую вершину с меткой . Тогда новая последовательность меток для вершины jv будет ),,,(),,,,,( 2121 mk   или ).,,,(),,,,,( 2121 mk   1. Рассмотрим случай равенства ),,,(),,,,,( 2121 mk   ).( km  Так как дуга в вершину с меткой  из вершины jv транзитивная, то существует некоторая вершина с меткой , в которую идет дуга из вершины jv и из которой идет дуга в вершину с меткой . Но так как ),,,,(),,,,,( 2121 mk   то такие же дуги исходят и из вершины ,iv а значит, в исходном графе были транзитивные дуги. Получили противоречие. 66 ISSN 0572-2691 2. Рассмотрим случай неравенства. Для начальных последовательностей ме- ток ),,,(),,,( 2121 km   возможны такие варианты: либо ,11  либо ppt  : ),,1( tp  11   tt , либо pp  ),,1( kp  .mk  Оче- видно, при условии kt  второй и третий случаи совпадают, поэтому достаточно проанализировать первый и второй случаи. В первом случае добавление метки 1 (так как дуга транзитивна и идет в вер- шину более низкого уровня) не может привести к ситуации  ),,,,,( 21 k ).,,,( 21 m  Эта ситуация всегда будет иметь место, например, для графов, в которых каждая вершина имеет не больше одной исходящей дуги. Рассмотрим второй случай. Фактически он означает, что из вершин iv и jv выходит t дуг в одинаковые вершины. Тогда при добавлении метки  возможно, что либо ,1 t либо ,1 tt либо .t Если ,1 t то добавление транзитивной дуги не может привести к ситуа- ции ).,,,(),,,,,( 2121 mk   Если ,1 tt то, так как нам известно, что ,11   tt далее возмож- ны три варианта: либо ,1  t в этой ситуации добавление транзитивной дуги также не может привести к ситуации ),,,,(),,,,,( 2121 mk   либо ,1  t когда добавление метки  приводит к «критической» ситуации ),,,,(),,,,,( 2121 mk   либо ,1  t но такая ситуация вообще невозможна, поскольку в этом случае дуга из iv в вершину с меткой  также бы- ла бы транзитивной. Если же ,t то переходим к сравнению последовательностей ),,,,,( 21 t  и ).,,,( 21 t  Причем нам известно, что pp  , ),,1( tp  т.е. упорядочение схематически можно изобразить так: 1 … 1t t 1 … 1t  t Известно, что ,t значит, и ,t т.е. это ситуация, когда добавление метки  может привести к «критической» ситуации  ),,,,,( 21 k ).,,,( 21 m  Таким образом, мы показали, что добавление транзитивной дуги может приве- сти к построению неоптимального упорядочения ширины 2 по алгоритму, основан- ному на расстановке лексикографических меток только в случае, если для любой вершины ,jv которой отвечает последовательность меток ),,,,( 21 k  и из ко- торой добавляется транзитивная дуга в вершину с меткой , существует вершина ,iv которой отвечает лексикографическая последовательность ),,,( 21 m  такая, что: Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 67 1) ),,,(),,,( 2121 km   и ppkt  : ),,1( tp  11   tt (ес- ли ,kt  то фиктивно вводим );01  t 2) .1  t Практически это означает, что в графе существует две вершины iv и jv некоторо- го уровня, из которых выходят дуги в одина- ковые вершины следующего уровня и в раз- ные вершины более низких уровней (рис. 4). iv jv Рис. 4 68 ISSN 0572-2691 4. Условия, при которых наличие транзитивных дуг не влияет на оптимальность алгоритма Из рассмотренного выше следуют такие утверждения. Утверждение 1. Наличие транзитивных дуг не повлияет на оптимальность решения, если в графе без транзитивных дуг вершина ,iv к которой добавляются транзитивные дуги, имеет наивысшую метку среди вершин своего уровня. Утверждение 2. Наличие транзитивных дуг не повлияет на оптимальность решения, если вершина, из которой исходят транзитивные дуги, является един- ственной вершиной своего уровня. Анализируя графы, в которых наличие транзитивных дуг не влияет на опти- мальность упорядочения, можно сформулировать следующую теорему. Теорема 1. Наличие транзитивной дуги не повлияет на оптимальность упо- рядочения, построенного по лексикографическому принципу, если в графе для вершины ,iv из которой исходит эта транзитивная дуга, и для любой другой вер- шины ,jv принадлежащей одному уровню с iv , множества вершин следующего уровня, в которые идут дуги из этих вершин, не равны. Доказательство. Рассмотрим процесс расстановки меток. В ходе расстановки меток по лексикографическому принципу вершины получают метки по уровням: вершины первого уровня — от 1 до ,][1 lSk  вершины второго уровня — от 11k до ,]1[12  lSkk вершины уровня l — от 11lk до .]1[ 1 Skk ll   При этом понятно, что .21 lkkk   Пусть iv — вершина уровня ,t из которой выходят транзитивные дуги ),3( lt  вершина jv — любая другая вершина уровня .t Предположим, что без учета транзитивной дуги вершинам iv и jv соответ- ствуют последовательности меток ),,,( 21 m  и ).,,,( 21 k  Покажем, что добавление транзитивных дуг не изменит лексикографическое отношение по- следовательностей меток, т.е. не изменит и самих меток вершин. Если ),,,,(),,,( 2121 km   то добавление метки  вершины, в которую идет транзитивная дуга, в первую последовательность только увеличит ее и никак не изменит отношение лексикографического порядка последовательно- стей меток, а также и метки вершин. Для случая ),,,(),,,( 2121 km   можно утверждать, что суще- ствует некоторая вершина уровня ),1( t в которую идет дуга из jv и не идет дуга из iv (так как множество вершин уровня ),1( t в которые идут дуги из вершин iv и ,jv не совпадают), т.е. ss  ,1( ms  ,1 12   tst kk ).1 112   tst kk Рассмотрим, как повлияет на лексикографическую последовательность добавле- ние транзитивной дуги. Поскольку дуга транзитивна, то вершина, в которую она идет, расположена на уровне не больше, чем ),2( t и ее метка меньше, чем .12 tk Если транзитивная дуга идет в вершину с меткой меньшей, чем метка ,s то эта метка будет расположена в последовательности правее, чем ,s и не повлияет на лексикографический порядок последовательностей меток. Если транзитивная дуга идет в вершину с меткой большей, чем ,s то она будет расположена в упорядоче- нии левее, чем .s Но так как ,1 12   tst kk а метка, которая добавляется, меньше ,12 tk то на лексикографический порядок ее добавление не повлияет. Теорема доказана. Следствие 1. Если условия теоремы выполняются, то наличие в орграфе не- скольких транзитивных дуг, исходящих из одной вершины, не повлияет на опти- мальность упорядочения, построенного по лексикографическому принципу. Следствие 2. Если условия теоремы выполняются для каждой вершины, из которой исходят транзитивные дуги, то наличие в орграфе любого количества Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 69 транзитивных дуг, исходящих из нескольких вершин, не повлияет на оптималь- ность упорядочения, построенного по лексикографическому принципу. Доказательство. Действительно, каким бы ни было отношение меток вершин iv и :jv ),,,(),,,( 2121 km   или ),,,,(),,,( 2121 km   это отношение определяется наличием некоторой метки уровня )1( t с «критической» меткой, т.е. либо ss  ,1( ks  ,1 12   tst kk ),1 112   tst kk либо ss  ,1( ms  ,1 12   tst kk ).1 112   tst kk В любом случае метки вершин с учетом добавленных транзитивных дуг не повлияют на отношение последовательностей меток вершин, а значит, и на поря- док добавления вершин в строящееся упорядочение. 5. Транзитивные дуги в графах, задающих неветвящиеся арифметические выражения Предложенная выше теорема описывает класс графов, для которых наличие транзитивных дуг не повлияет на оптимальность. Заметим, что это условие явля- ется достаточным, но не необходимым. Покажем, что существуют еще некоторые классы графов, для которых нали- чие транзитивных дуг не влияет на оптимальность упорядочения, построенного по лексикографическому принципу. Одним из таких классов является класс гра- фов, задающих неветвящиеся арифметические выражения, т.е. таких графов, в ко- торых в каждую вершину может входить не больше двух дуг. Теорема 2. В графах, задающих неветвящиеся арифметические выражения, наличие транзитивных дуг не повлияет на оптимальность упорядочения, постро- енного по лексикографическому принципу. Доказательство. Пусть в исходном графе, не имеющем транзитивных дуг, есть две вершины: iv и ,jv принадлежащие одному уровню и такие, чтобы в ис- ходном упорядочении S вершина iv была расположена правее вершины ,jv т.е. упорядочение имело вид .        k ij v vv S  Вершина kv — некоторая вершина с меткой, большей, чем метки вершин jv и iv (иначе она была бы расположена в упорядочении S правее). Пусть в графе с транзитивными дугами из вершины iv (и, возможно, из )jv исходят транзитивные дуги, вследствие чего в новом оптимальном упорядочении она будет расположена левее ,jv т.е. новое оптимальное упорядочение будет иметь вид .        k ji v vv S  Рассмотрим, изменится ли длина .S Возможны такие случаи. 1. Существует вершина ,mv не связанная дугами с iv и ,jv такая, что .        mk ij vv vv S  Тогда упорядочение        mk ji vv vv S  и наличие тран- зитивной дуги не повлияет на оптимальность. 2. Такой вершины mv не существует. Тогда пусть последовательность меток для вершины iv — ),,,,( 121 r  последовательность меток для вершины jv — ),,,,( 221 r  последовательность меток для вершины kv — ),,,,( 321 r  причем ),,,,(),,,( 31 2121 rr   ведь метка вершины kv больше, чем метка вершины .iv Для того чтобы вершины iv и jv изменили метки при добав- лении транзитивной дуги из ,iv необходимо, чтобы ,1: 1rrr  ii  . ).,1( ri  Так как мы рассматриваем граф, задающий неветвящееся арифметиче- ское выражение, то можно сделать вывод, что ii  , ),,1( ri  причем ,11  т.е. из вершины kv как минимум r дуг исходит в другие вершины, чем из iv и ,jv и при этом существует вершина x с меткой .11  Для этой вершины 70 ISSN 0572-2691 возможно одно из двух: либо в нее входит дуга только из ,kv либо в нее входит дуга из kv и из некоторой другой вершины .mv Во втором случае вершина mv должна быть расположена в упорядочении левее .kv Действительно, если бы вершина mv в лексикографической последовательности получила метку, мень- шую, чем ,kv то она была бы расположена на одном с ней месте. Но мы знаем, что это место могут занимать вершины iv и ,jv в лексикографической последо- вательности которых 1 нет. А значит, можно утверждать, что метка mv большая и она была добавлена в упорядочение. В обоих случаях вершина x с меткой 1 может быть добавлена в упорядоче- ние одновременно с вершиной .jv Таким образом, будет построено упорядочение        xv vv S k ji * , т.е. в упорядочении не будет пустых мест и длина упорядочения не увеличится. Теорема доказана. Заключение Полученные условия влияния транзитивных дуг на оптимальность позволяют для реальных задач, в которых количество вершин и дуг велико (тысячи дуг и вершин, например, при распараллеливании сеточных задач), не тратить время на выявление и выделение неинформативных дуг в графе. Заметим, что сформули- рованные условия описывают только некоторый класс графов, к которым можно применить метод, основанный на лексикографическом принципе без дополни- тельной проверки на наличие транзитивных дуг. Открытым остается вопрос поис- ка необходимых условий, которые описывали бы все графы, в которых наличие транзитивных дуг влияет на оптимальность решения. Кроме того, теоретический интерес представляет оценка количества таких графов среди всех графов с задан- ным количеством дуг и вершин. В.А. Турчина, Н.К. Федоренко ДОСЛІДЖЕННЯ ВПЛИВУ ТРАНЗИТИВНИХ ДУГ НА ОПТИМАЛЬНІСТЬ ДЕЯКИХ АЛГОРИТМІВ ПАРАЛЕЛЬНОГО УПОРЯДКУВАННЯ Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядку- вання, побудованого за алгоритмом, що базується на лексикографічному прин- ципі. Запропоновано достатню умову, при якій транзитивні дуги не впливати- муть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптималь- ність отриманого за алгоритмом розв’язку. V.A. Turchina, N.K. Fedorenko RESEARCH OF THE TRANSITIVE EDGES INFLUENCE ON THE OPTIMALITY OF SOME SCHEDULING ALGORITHMS Transitive edges influence on the optimality of the scheduler built by the algorithm based on the lexicographic principle is considered. The sufficient condition when transitive edges don’t influence the optimality of the solution is given. Besides the class of graphs describing not branching arithmetic expressions is studied and it’s proved that transitive edges don’t influence optimality of the schedule for such graphs with transitive edges. 1. Coffman E.G. Jr., Graham R.L. Optimal scheduling for two-processor systems // Acta Inform. — 1972. — 1, N 3. — P. 200–213. 2. Fujii M., Kasami T., Ninomiya K. Optimal sequencing of two equivalent processors // SIAM J. Appl. Math. — 1969. — 17, N 4. — P. 784–789. Международный научно-технический журнал «Проблемы управления и информатики», 2012, № 1 71 3. Бурдюк В.Я., Турчина В.А. Алгоритмы параллельного упорядочения. — Днепропетровск : ДГУ, 1985. — 84 с. Получено 04.07.2011

Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения

Institution

Ähnliche Einträge