Распределение различных ресурсов, и в том числе, ресурсов, из которых формируются параллельные материальные или информационные потоки является одной из наиболее часто встречающихся проблем на практике. В частности такие задачи возникают при распределении и синхронизации ресурсов памяти процессоров. Однако решение таких задач в большинстве случаев связано со значительными вычислительными проблемами. Причина в том, что параллельные объекты обычно являются частично однотипными и это приводит к появлению малого параметра в моделях этих задач и связанной с ним проблемы неустойчивости полученных решений, из-за «плохой обусловленности» их матриц ограничений.
Проблема нахождения устойчивых решений систем уравнений с вырожденной матрицей, с помощью введения стабилизирующих функционалов, рассматривалась академиком А.Н. Тихоновым. Его идеи получили распространение и для решения оптимизационных задач с базисной матрицей ограничений близкой к вырожденной. Так профессор А.А. Первозванский [1] предложил метод, суть которого состоит в выделении порождающей системы, полученной из исходной оптимизационной задачи без учета слабых различий между ее ограничениями, т.е. без возмущений, и в использовании характеристик порождающей системы. для оценки роли возмущений в формировании оптимального решения. Вышеуказанные подходы имеют большую теоретическую значимость, однако их вычислительные процедуры связаны с выполнением достаточно жестких ограничений на характер вырожденности и приводят только к приближенным решениям. В работе [2] предложен метод расширения множества допустимых значений для решения оптимизационных задач распределения ресурсов между параллельными объектами с учетом возможной, но не обязательной вырожденности матриц ограничений, где рассматривается иной подход к учету данной проблемы. Суть этого подхода состоит в том, что решение исходной оптимизационной задачи определяется путем направленного перехода к ее оптимальному решению из точки, соответствующей решению некоторой вспомогательной задачи с расширенным множеством допустимых значений. При этом вычислительная процедура становится не только нечувствительной к вырожденности матрицы ограничений задачи, но из-за специфики модели систем с параллельной структурой обеспечивает нахождение точного решения задачи.
В данной работе метод расширения обобщен для нового класса задач распределения потоковых ресурсов в системе, состоящей из двух процессоров: передатчика и приемника, которые обмениваются сообщениями через общедоступную буферную память ограниченной емкости. Результатом исследований является определение влияния согласованности распределения ресурсов взаимодействующих процессоров и ресурсов буферной памяти на производительность системы на основе имитационного анализа протекающих в ней процессов.
Литература.
1. Pervozvanskyi A. A., Optimizatciya system so slabymi svyazami, Systems Science No. 1-2, 1979, Vol. 2., p. 23-32.
2. Shukayev D.N. Optimization of resourse allocation processes in parallel structure systems. Presentation of International scientific and technical conferenceFEIIC, Almaty, 1999, p.185-192.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск