МИНИМИЗАЦИЯ ЗАТРАТ НА ПОСТРОЕНИЕ МОДЕЛЕЙ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ ПРИ ИХ РАСПРЕДЕЛЕННОЙ РЕАЛИЗАЦИИ
Аннотация
Рассматривается задача минимизации затрат на построение математических моделей последовательных программ при их распределенной реализации. В качестве моделей программ используются ориентированные графы, веса вершин которых представляют собой числа выполнений линейных участков, веса дуг – числа переходов между линейными участками при решении задач с помощью рассматриваемой программы. Предлагаются алгоритмы поиска минимальных по мощности множеств вершин и дуг графа, задание значений весов которых позволяет вычислить веса всех остальных вершин и дуг графа.
Об авторах
А. С. Поляков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
В. Е. Самсонов
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Губкин, А.Ф. Об определении временных характеристик последовательных про-грамм / А.Ф. Губкин, В.А Матвеев // УСИМ. – 1991. – № 5. – С. 48–54.
2. Закревский, А.Д. К оптимизации динамического использования регистров в программах / А.Д. Закревский // Доклады АН БССР. – Т. 20, № 2. – 1976. – С. 127–129.
3. Поляков, А.С. О распределенной обработке программ в вычислительных сетях / А.С. Поляков // АВТ. – 1992. – № 2. – С. 45–49.
4. Поляков, А.С. Размещение фрагментов последовательных программ на процессорах распределенной системы / А.С. Поляков // Весці НАН Беларусі. Сер. фіз.-тэхн. навук. – 1999. – № 3. – С. 84–88.
5. Головкин, Б.А. Расчет характеристик и планирование параллельных вычислительных процессов / Б.А. Головкин. – М.: Радио и связь, 1983. – 272 с.
6. Joseph, D. Prefetching using markov predictors / D. Joseph, D. Grunwald // IEEE Transactions on Computers. – Vol. 48, № 2. – February 1999. – P. 121–133.
7. Chilimbi, T.M. Dynamic hot data stream prefetching for general-purpose programs / T.M. Chilimbi, M. Hirzel // Proc. of the ACM SIGPLAN 2002 Conference on Programming language design and implementation. – ASM Press, 2002. – P. 199–209.
8. Поляков, А.С. Нахождение максимальных полных подграфов / А.С. Поляков // Алгоритмы решения логико-комбинаторных задач: сб. науч. тр. – Минск: Ин-т техн. кибернетики АН БССР, 1975. – С. 32–42.
Рецензия
Для цитирования:
Поляков А.С., Самсонов В.Е. МИНИМИЗАЦИЯ ЗАТРАТ НА ПОСТРОЕНИЕ МОДЕЛЕЙ ПОСЛЕДОВАТЕЛЬНЫХ ПРОГРАММ ПРИ ИХ РАСПРЕДЕЛЕННОЙ РЕАЛИЗАЦИИ. Информатика. 2007;(1(13)):67-75.
Просмотров: 427
Послать статью по эл. почте 