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

{оригинальный алгоритм очень мутный, вместо него предлагается несколько более простой и ясный, хотя
и менее эффективный (наверное) :)))))
Исходные данные: матрица следования, веса вершин(время выполнения оператора), веса ребер
(время передачи данных)
Конечные данные: описание нитей в виде массива структур TThreads, в которых описывается
время старта и конца нити, входящие в нее операторы и связанные с ней нити.

1) Алгоритм изначально порождает столько нитей, сколько начальных вршин в S.

2) Вычисляем ранние сроки выполнения операторов по матрице следования S(лаба 7). Так как
задача всей курсовой состоит в том, чтобы минимизировать время при минимзации числа процов,
то можно брать ранние сроки и не заботится о числе процов. На основании этого можно вычислить
раннее времени решения задачи (то есть минмиальное время, за которое задача вообще может быть решена).
При вычислении рассматриваем, что передача данных идет мгновенно, то есть дуги взвешены 0.
По сути, рассматриваем вариант, что у нас есть 40 процов, на каждом из которых выполняется
по одному оператору.

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

4) После того, как выполнили построение стержневых нитей, начинаем строить остальные. В цикле
просматриваем операторы алгоритма, берем первый, для которого не указана принадлежность к нити,
строим аналогично п.3, отмечаем его зависимости от операторов, принадлежащих другой нити, рассчитываем
сроки выполнения нити (здесь уже учитываем время передачи информации между нитями)
и берем следующий оператор, для которого не указана нить. Таким образом, на выходе получится,
что все операторы закрепляются за нитями, для которых можно оценить:
- ранний срок начала выполнения(ранний срок выполнения первого оператора t0)
- ранний срок конца выполнения(сумма t0 и раннего срока )
}

Добавлено (23.03.08, 00:13:51)
---------------------------------------------
Используемая структура TThread
TThread=record//описывает нить
StartTime:integer;//раннее время запуска нити
EndTime:integer;//раннее время останова нити
Alg:array[0..PathMatrixD-1] of integer;//операторы, входящие в нить
MitThread:array[0..PathMatrixD-1] of integer;//нити, связанные с данной
end;

По поводу поста про логические связи. Этот алгоритм разрезания работает только с ИГ, то есть с графами, у которых в матрице следования либо 0, либо 1 (или, по новым веяниям, целый вес). Поэтому для его запуска из исходного ИЛГ требуется сформировать n ИГ. Алгоритм формирования также есть в лекциях. Насчёт doc-варианта не знаю, а в конспектах Дамиры есть. Они, кстати, мне показались более корректными, чем печатный вариант. И лицензия на MS Office для просмотра не требуется

В целом проблема обозначена правильно, поскольку алгоритм весьма запутан.

Предлаемая идея не связана ни с какими разрезаниями. Просто каждый оператор прикрепляется к нити и все. А потом нити разбрасываются по процам. Связанные нити - по соседним, несвязанные - по удаленным. Единствееное НО: он говорил, что есть просто передача данных в соседний проц, а есть транзитная передача (когда связей не хватает). Хоть убейся, но не ясно, как время передачи информации транзитно и напрямую может быть одинаково. У него просто получается, что алгоритм (а не ВС), характеризуется временем передачи данных между операторами, хотя на самом деле алгоритм характеризуется объемом передаваемых данных, а вот их скорость (и время) передачи - свойство ВС, которое зависит от того, как спланировали вычисления. Неувязочка вышла Алгоритмы надо применять как-то параллельно, а не последовательно.

По поводу отметок в матрице следования - обозначать отсутсвие связи -1. И все, нулевой вес есть.

Единственно не понятно про ИЛГ - в чем тут принципиальное отличие от ИГ, может, просто рассматривать значения TF как 1 и все? Что мы должны будем при планировании исключить операторы, которые не пойдут в исполнение? Это существенно усложнит задачу, так как потребует заново формировать алгоритмы и их анализировать. Всего 2^n различных графов, где n-число логических операторов плюс писать еще один алгоритм переделки графов

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

Добавлено (24.03.08, 19:25:17)
---------------------------------------------
И в дополнение к вышесказанному. Алгоритм распределения нитей по ВС.
Известна: список нитей и их взаимосвязь, структура ВС (гипертор, гиперкуб, циркулянта)
Надо: раскидать нити по ВС, чтобы процы, на которых выполняются нити, были связаны между собой напрямую или через транзитные процы.
Вроде все легко, у Руденко все это описано в алгоритме, но есть одно НО: что делать в том случае, когда есть 3 и более взаимосвязанных нитей (такое на 40 операторах вполне реально)??? Несложно предстваить ситуацию, когда физически трудно (в некоторых случаях - нереально) разместить эти нити руками (автоматом молчу - алгоритм будет очень хитрый ), если использовать только один транзитный проц. Самое противное то, что очень сложно сделать руками даже "куклу" - муляж проги, а если писать прогу, то она в этом случае будет явно валиться или некорректно работать.

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

Добавлено (24.03.08, 19:27:59)
---------------------------------------------
Кого заинтерсовала структура гипертора и гиперкуба, обеспечивающая связь через транзитные процы "каждый с каждым", звоните или пишите в личку.