Исследование динамических характеристик программ на масштабируемых ресурсах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Топоркова, Анна Станиславовна

• Топоркова, Анна Станиславовна
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Топоркова, Анна Станиславовна

Введение.

Глава 1. Модели упорядочения и проблема масштабирования ресурсов для оптимизации динамики программ.

1.1. Конфигурация вычислительной среды и планирование процессов.

1.1.1. Априорное и динамическое планирование.

1.1.2. Выявление структуры ресурсов при фиксированных свойствах операции.

1.1.3. Планирование с преобразованием отношения предшествования.

1.1.4. Циклическое планирование.

1.1.5. Динамическое конфигурирование ресурсов.

1.2. Общая модель упорядочения для детерминированных расписаний и ее ограничения.

1.3. Модели упорядочения с произвольными параметрами.

1.4. Постановка задачи оптимизации выполнения программ на масштабируемых ресурсах.

1.5. Выводы по главе 1.,.

Глава 2. Основные компоненты модели планирования и назначения процессов программных приложений на масштабируемых ресурсах.

2.1. Условия допустимости масштаба процессов.

2.2. Масштабируемые вычислительные ресурсы.

2.3. Модель обработки.

2.4. Ограничения при масштабировании процессов.

2.5. Критерии масштабирования.

2.6. Ключевые понятия в алгоритмах масштабирования.

2.7. Методы динамического программирования и алгоритмы масштабирования.

2.8. Выводы по главе 2.

Глава 3. Алгоритмы оптимизации динамики программ в масштабируемой среде.

3.1. Алгоритмы масштабирования критических задач по частному критерию.

3.2. Алгоритмы поиска оптимальной стратегии выполнения программы на масштабируемых ресурсах.

3.3. Арбитраж конфликтов между конкурирующими процессами.

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

3.5. Выводы по главе 3.

Глава 4. Статико-динамический анализ программ и тестирование алгоритмов масштабирования.

4.1. Методика статико-динамического анализа априорных характеристик программ.

4.1.1. Задача статико-динамического анализа.

4.1.2. Фрагментация кода программы.

4.1.3. Оценка длительности и сложности выполнения фрагмента.

4.1.4. Алгоритмы фрагментации и оценки сложности в особых случаях.

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

4.3. Эвристики для снижения избыточности оптимальных стратегий.

4.4. Особенности программной реализации алгоритмов арбитража.

4.5. Выводы по главе 4.

Введение диссертации (часть автореферата) на тему «Исследование динамических характеристик программ на масштабируемых ресурсах»

К настоящему времени роль и место математического и программного обеспечения в повышении реальной производительности параллельных аппаратных платформ хорошо осознаны. В связи с развитием масштабируемых систем, от однородных SMP-архитектур до гетерогенных, распределенных метавычислительных сред, возникает проблема эффективного использования их ресурсов программными приложениями. Помимо распараллеливания программ [1], чрезвычайно актуальной является задача планирования процессов в масштабируемой вычислительной среде [2-7]. На сегодняшний день разработан ряд интерфейсов для статического и динамического распараллеливания программ. В частности, стандарт Open MP для SMP-систем (SSMP, CC-NUMA и т. д. [8]), интерфейсы MPI, POSIX, Т-система [1]. Однако практически отсутствуют работы, посвященные методам конфигурирования, "настройки" вычислительных ресурсов с целью оптимизации выполнения программ. По сути, оптимизация динамических характеристик конкретных программных приложений на масштабируемых ресурсах означает обоснованный выбор интервала времени и типа ресурса для исполнения каждого из процессов программы. Один из возможных путей практической реализации этой идеи представлен проектом AppLeS для динамического планирования метавычислений [2-4, 7]: агент-планировщик формирует и координирует выполнение расписания приложения с целью повышения эффективности его работы с точки зрения конкретного пользователя. Планировщик и приложение образуют своего рода программную среду, оптимизирующую динамику программ на основе выбора соответствующей комбинации ресурсов.

Планирование процессов на масштабируемых ресурсах принципиально отличается от составления расписаний под заданную архитектуру (модель) вычислительной системы [9-12]. Составление расписания предполагает фиксацию характеристик процессов программ, получаемых в результате статико-динамического анализа [13, 14]. Однако перераспределение априори полученных значений времени и стоимости использования ресурсов, или масштабирование, представляет собой сильный оптимизирующий механизм [15]. (Здесь под стоимостью понимается вес [16], являющийся функцией длительности процесса и других параметров, в частности, объема вычислений.)

Работа посвящена оптимизации динамических характеристик параллельных программ на основе выбора и масштабирования ресурсов -процессоров и коммуникационной среды. Актуальность этой проблемы определяется необходимостью эффективного программирования приложений для суперкомпьютерных систем [1-8], организации реконфигурируемых вычислений [17], совместного проектирования аппаратуры и программ [14, 18-21], разработки встроенных программных систем реального времени [22-25].

Цель диссертации - разработка методов оптимизации динамических характеристик параллельных программ, исполняемых на масштабируемых вычислительных ресурсах.

Для достижения поставленной цели в работе решаются следующие основные задачи.

1. Разработка модели упорядочения процессов при назначении их на масштабируемые ресурсы.

2. Исследование методов решения одно- и многокритериальных задач масштабирования.

3. Создание инструментальных средств статико-динамического анализа и оптимизации характеристик программ для масштабируемых ресурсов.

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

Научная новизна заключается в разработке совокупности методов планирования и назначения процессов программ на масштабируемые ресурсы.

Основные положения, которые выносятся на защиту:

1. Модель упорядочения процессов с изменяемой векторной потребностью в вычислительных ресурсах.

2. Одно- и многокритериальные методы оптимизации динамических характеристик программ в процессе их компиляции.

3. Экспериментальные методы исследования и оптимизации статико-динамических характеристик параллельных программ.

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

Полученные результаты обеспечивают:

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

2. Возможность масштабирования процессов в ходе компиляции, благодаря полиномиальной сложности алгоритмов оптимизации динамических характеристик программ.

3. Эффективность и надежность статико-динамического анализа программ в инструментальной среде.

Результаты работы реализованы в государственном научном центре «Центральный институт авиационного моторостроения» при создании программного обеспечения бортовых вычислительных комплексов, 1ШИ точного электронного приборостроения при разработке нетрадиционных архитектур спецвычислителей и внедрены в учебный процесс Московского энергетического института (технического университета).

Основные положения диссертации апробированы на ряде международных и всероссийских конференций в период с 1993 года по 2001год: Международных конференциях и школах "Новые информационные технологии в науке, образовании и бизнесе" (Ялта-Гурзуф, 1993, 1995, 1996, 1997); межвузовской научно-технической конференции "Фундаментальные основы создания наукоемких и высокотехнологичных приборов" (Москва -Сергиев-Посад, 1997), XXV Юбилейной Международной конференции и дискуссионном научном клубе "Новые информационные технологии в науке, образовании, телекоммуникации и бизнесе. 1Т+8Е'98" (Украина, Крым, Ялта-Гурзуф, 1998); Международной конференции "Информационные средства и технологии" в рамках Международного форума информатизации МФИ - 2001 (Москва, 2001).

Основные результаты опубликованы в 7 печатных работах и двух сборниках методических указаний по курсу "Программирование и алгоритмические языки", изд-во МГИЭМ, 1999г.

Диссертация состоит из введения, четырех глав, списка литературы из 126 наименований и двух приложений.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Топоркова, Анна Станиславовна

4.5. Выводы по главе 4

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

1. Разработаны эффективные и надежные программные средства для априорного анализа характеристик программ.

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

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

4. C существлена эффективная программная реализация алгоритмов арбитража конфликтов между процессами программы. Экспериментальное ft ft тестирование подтверждает возможности двуслойного разрешения конфликтов, реализуемого алгоритмами квадратичной временной сложности.

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

ЗАКЛЮЧЕНИЕ

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

1. На основе анализа взаимосвязи задач планирования процессов и конфигурирования вычислительных ресурсов в различных предметных областях сформулирована общая задача оптимизации динамики программ на масштабируемой среде. Выявлены принципиальные ограничения моделей упорядочения процессов при составлении детерминированных расписаний. Исследованы главные отличия задачи оптимизации динамических характеристик программ путем масштабирования ресурсов и детерминированного планирования процессов программ с априори фиксированными свойствами.

2. Создана модель упорядочения действий программы на масштабируемых ресурсах: определены условия допустимости масштаба процессов; формализовано понятие масштабируемой среды, образуемой ресурсами и программным приложением; обоснованы ограничения и критерии эффективности масштабирования. Разработаны ключевые положения и определены понятия в алгоритмах масштабирования. Обосновано применение методов динамического программирования на уровне масштабирования отдельных фрагментов и на уровне системы действий программы при арбитраже конфликтов между процессами.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Топоркова, Анна Станиславовна, 2001 год

1. Абрамов СМ., Адамович А.И. Т-система среда программирования с поддержкой автоматического динамического распараллеливания программ // Юбилейный сб. трудов Института программных систем РАН. Под ред. проф. В.И. Гурмана. Переславль-Залесский. ИПС РАН. 1999.

2. Herman F., Wolski R. Scheduling from the perspective of the application // Proc. of High-Performance Distributed Computing Conf. Syracuse. NY. August 6-9, 1996.

3. Casanova H. et al. Heuristics for scheduling parameter sweep applications in Grid environments //Proc. of the 9th Heterogeneous Computing Workshop (HCW'2000). 2000. P. 349-363.

4. Dail H. et al. Application-aware scheduling of a magnetohydrodynamics application in the Legion metasystem // Proc. of the 9th Heterogeneous Computing Workshop (HCW2000). May 2000.

5. Chapin S.J. et al. Resource management in Legion // J. of Future Generation Computing Systems. 1999. Vol. 15. P. 583-594.

6. Grimshaw et al. Wide-area computing: resource scharing on a large scale // IEEE Computer. 1999. Vol. 32. №5. P. 29-37.

7. Shao G., Wolski R., Herman F. Performance effects of scheduling strategies for master/slave distributed applications // UCSD CSE Technical Report №CS98-598. University of CaHfornia, SanDiego, 1998. 13p.

8. Дикарев H.K., Шабанов Б.М. Реальная и пиковая производительности суперЭНМ//Автоматизация проектирования. 2000. №1-2(13). С. 3-15.

9. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.- 360 с.

10. Липаев В.В. Распределение ресурсов в вычислительных системах. -М.: Статистика, 1979. 247 с.

11. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. - 272 с.

12. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация. М.: Радио и связь, 1990. - 256 с.

13. Toporkov V. V. Performance-complexity analysis in hardware-software codesign for real-time systems // European Design Automation Conference 1995 (EURO-DAC'95) with EURO-VHDL: Proc. Brighton, UK, IEEE CS Press, 1995. - P. 340-345.

14. Топорков В.В. Поведенческий синтез систем. М.: Изд-во МЭИ. 2001.192с.

15. Топорков В.В. Модели и методы системного синтеза. М.: Изд-во МЭИ. 1999. 64с.

16. Теория расписаний и вычислительные машины / Под ред. Э.Г. Коффмана. М.: Наука, 1984.-334с.

17. Najjar W.A., Lee Е.А., Gao G.R. Advances in the dataflow computational model // Parallel Computing. N.-H.: Elserier Science. 1999. Vol. 25. P. 19071929.

18. De Micheli G., Gupta R.K. Hardware/software co-design // Proc. of the IEEE. 1997. Vol. 85. №3. P. 349-365.

19. Rosenblit J.W., Schulz S. Simulation-based design of heterogeneous systems // Hardware/Software Codesign. Ed. K. Bucheurieder. IT press. 1999. P. 95-110.

20. Bakhmurov A.G., Kapitonova А.Р., Smeliansky R.L. DYANA: an environment for embedded system design and analysis // Proc. of the 5th Int. Conf. "Tools and algorithms for the construction and analysis of systems". 1999. P. 390404.

21. Lee E.A. What's ahead for embedded software? // IEEE Computer. 2000. №9. P. 18-26.

22. Cortadella J. et al. Task generation and compile-time scheduling for mixed data-control embedded software // Proc. of the 37th Design Automation Conf. June 5-9, 2000. P. 489-494.

23. Shin Y., Kim D., Choi K. Schedulability-driven performance analysis of multiple mode embedded real-time systems // Proc. of the 37th Design Automation Conf June 5-9, 2000. P. 495-500.

24. DiNatale M., Sangiovanni-Vincentelli, Balarin F. Task scheduling with RT constraints //Proc. of the 37th Design Automation Conf. June 5-9, 2000. P. 483-488.

25. Игнатущенко B.B., Клушин Ю.С. Прогнозирование выполнения сложных программных комплексов на параллельных компьютерах: прямое стохастическое моделирование // Автоматика и телемеханика. 1994. Jf 11. С. 142-157.

26. Игнатущенко В.В., Подшивалова И.Ю. Динамическое управление параллельными вычислительными процессами на основе статического прогнозирования их выполнения // Автоматика и телемеханика. 1997. №5. С. 160-173.

27. Buck J.T., Lee E.A. Scheduling dynamic dataflow graphs with bounded memory using the token flow model // Proc. of ICASSP'93, Minneapolis, April 1993.

28. Buck J.T. Static scheduling and code generation from dynamic dataflow graphs with integer-valued control streams // Proc. of the 28th Asilomar Conf. on Signals, Systems and Computers. November 1994.

29. Гэри M.P. Джонсон Д.С. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

30. Джонсон С. Оптимальное расписание для двух- и трехступенчатых процессов с учетом времени наладки // Кибернетический сборник. Новая серия. Вып. 1. Сборник переводов. М.: Мир, 1965. - С.78-86.

31. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983.-208 с.

32. Ханаев B.C., Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984. - 384 с.

33. Фейгин Л.И. О влиянии возмущений на расписание // Изв. АН СССР. Техническая кибернетика. 1967. - № 4.

34. Фейгин Л.И. Векторная оптимизация в задачах теории расписаний при неполной информации // Изв. АН СССР. Техническая кибернетика. -1976.-№ 5.

35. Ху Т.е. Параллельное упорядочивание и проблемы линии сборки // Кибернетический сборник. Новая серия. Вып. 4. Сборник переводов. М.: Мир, 1967. - С. 43-56.

36. Bruno J., Coffman E.G., Sethi R. Scheduling independent tasks to reduce mean finishing time // Communications of the ACM. 1974. - V. 17. - № 7. - P. 382-387.

37. Bruno J., Coffman E.G., Sethi R. Algorithms for minimizing mean flow time // MPS Congress: Proc. North Holland, August 1974. - P. 504-510.

38. Coffman E.G., Graham R.L. Optimal scheduling for two processor systems // Acta Informatica. 1972. - V. 1. - № 3. - P. 200-213.

39. Coffman E.G., Sethi R. Algorithms minimizing mean flow-time // Acta Informatica. 1976. - V. 6. - № 1. - P. 1-14.

40. Garey M.R., Johnson D.S. Complexity results for multiprocessor scheduling under resource constraints // SI AM Journal on Computing. 1975. -V.4.-№4.-P. 397-411.

41. Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling // Math. Oper. Res. 1976. - V. 1. - №2. - P. 117-129.

42. Gonzalez M.J. Deterministic processor scheduling // Computing Surveys. 1977.-V. 9.-№3.-P. 173-204.

43. Horn W.A. Minimizing average flow time with parallel machines // Operations Research. 1973. - V.21. - № 3. - P. 846-847.

44. Horn W.A. Single machine job sequencing with treelike precedence ordering and linear delay penalties // SIAM Journal on Applied Mathematics. -1972.-V.23.-№ 2.-P. 189-202.

45. Liu C.L. Layland J.W. Scheduling algorithms for multiprogramming in a hard real-time environment // Journal of the ACM. 1973. - V.20. - № 1. - P. 4661.

46. McNaughton R. Scheduling with deadlines and loss functions // Management Science. 1959. - V. 6. - № 1. - P.1-12.

47. Ramamoorthy C. V., Chandy K.M., Gonzalez M.J. Optimal scheduling strategies in a multiprocessor system // IEEE Trans. Comput. 1972. - V. C-21. -№2.-P. 137-146.

48. Rothkopf M.H. Scheduling independent tasks on parallel processors // Management Science. 1966. - V. 12. - № 5. - P. 437-447.

49. Ullman J.D. Polynomial complete scheduling problems // Operating Systems Review. 1973. - V.7. - № 4. - P.96-101.

50. Lee E.A., Messerschmitt D.G. Static scheduling of synchronous data flow programs for digital signal processing // IEEE Trans, on Comput. 1987. - V.36. -№1.-P. 24-35.

51. Sha L., Goodenough J.B. Real-time scheduling theory in Ada // IEEE Computer. April 1990. - P. 53-62.

52. Sha L., Rajkumar R., Lehoczky J.P. Priority inheritance protocols: an approach to real-time synchronization // IEEE Trans, on Computers. 1990. -V.39.-№9.

53. Sih G.C., Lee E.A. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures // IEEE Trans, on Parallel and Distributed Systems. 1993. - V.4. - № 2.

54. Kim T., Yonezawa N., Liu J.W.S., Lin C.L. A scheduling algorithm for conditional resource sharing a hierarchical reduction approach // IEEE Trans, on CAD of Integrated Circuits and Systems. - 1994. - V. 13. - № 4. - P. 425-437.

55. McFarland M.C., Parker A.C., Camposano R. Tutorial on high-level synthesis // 25th ACM/IEEE Design Automation Conference: Proc, 1988. P. 330-336.

56. McFarland M.C., Parker A.C., Camposano R. The high-level synthesis of digital systems // Proc. of the IEEE. 1990. - V. 78. - P. 302-318.

57. Park I.-Ch., Kyung Ch.-M. FAMOS: an efficient scheduling algorithm for high-level synthesis // IEEE Trans, on CAD of Integrated Circuits and Systems. -1993. V.12. - № 10. - R 1437-1448.

58. Benner Th., Ernst R., Osterling A. Scalable performance scheduling for hardware-software cosynthesis // European Design Automation Conference: Proc. Brighton, UK, IEEE CS Press, 1995. - P. 164-169.

59. Chou P., Boriello G. Software scheduling in the co-synthesis of reactive real-time systems // 31st Design Automation Conference: Proc. San Diego, CA, June 1994.

60. Chou P., Walkup B.A., Boriello G. Scheduling for reactive real-time systems // IEEE Micro. August 1994. - P. 37-47.

61. Lee E.A. Computing for embedded systems // IEEE Instrumentation and Measurement Technology Conf. May 21-23 2001.

62. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. М.: Наука, 1988. - 296 с.

63. Mermet J. Three decades of hardware description languages in Europe // Journal ofElectrical Engineering and Information Science. 1998. - Vol. 3. - № 6.

64. Rim M., Mujumdar A., Jain R., De Leone R. Optimal and heuristic algorithms for solving the binding problems // IEEE Trans, on VLSI Systems. -1994.-V.2.-№2.-P. 211-224.

65. Camposano R. From behavior to structure: high-level synthesis // IEEE Design &Test of Computers. October 1990. - P. 8-18.

66. Springer D.L., Thomas D.E. Exploiting the special structure of conflict and compatibility graphs in high-level synthesis // IEEE Trans, on CAD of Integrated Circuits and Systems. 1994. - V.13. - № 7. p. 843-856.

67. Ku D., De Micheli G. Relative scheduling under timing constraints: algorithms for high-level synthesis of digital circuits // IEEE Trans, on CADACAS. 1992. - V.U. - №6. - P. 696-718.

68. Rahmouni M., Jerraya A.A. Formulation and evaluation of scheduling techniques for control flow graphs // European Design Automation Conference: Proc. Brighton, UK, IEEE CS Press, 1995. - P. 386-391.

69. Rabaey J.M., Potkonjak M. Estimating implementation bounds for real time DSP application specific circuits // IEEE Trans, on CAD of Integrated Circuits and Systems. 1994. - V.13. - A2 6. - P. 669-683.

70. Camposano R. Design process model in the Yorktown Silicon Compiler // 25th ACM/IEEE Design Automaton Conference: Proc, 1988. P. 489-494.

71. Paulin P.G., Knight J.P. Force-directed scheduling for the behavioral synthesis of ASIC's // IEEE Trans, on CAD. 1989. - V.8. - P. 661-679.

72. Tseng C, Siewiorek D.P. Automated synthesis of data paths in digital systems // IEEE Trans, on CAD of Integrated Circuits and Systems. 1986. -V.CAD-5.-№3.-P. 379-395.

73. Davidson S., Landskov D., Shriver B.D., Mallet R.W. Some experiment in local microcode compaction for horizontal machines // IEEE Trans, on Computers. 1981. - V.30. - № 7. - P. 460-477.

74. Fisher J.A. Trace scheduhng: a technique for global microcode compaction // IEEE Trans, on Computers. 1981. - V.C-30. - P. 478-490.

75. Girczyc E.F., Knight J.P. An ADA to standard cell-hardware compiler based on graph grammars and scheduling // Int. Conf Computer Design: Proc, 1984.-P. 726-731.

76. Lee J.H., Hsu Y.C., Lin Y.L. A new integer linear programming formulation for the scheduling problem in data path synthesis // Int. Conf. Computer-Aided Design: Proc, 1989. P. 20-23.

77. Jain R., Mujumdar A., Sharma A., Wang H. Experimental evaluation of some high-level synthesis scheduling heuristics // 28th Design Automation Conference: Proc, 1991.

78. Rim M., Jain R. Lower-bound performance estimation for the high-level synthesis scheduling problem // IEEE Trans, on CAD of Integrated Circuits and Systems. 1994. - V.13. - f 4. - R 451-458.

79. Peng Z., Kuchinsky K., Lyles B. CAMAD: A unified data path/control synthesis environment // Design Methodologies for VLSI and Computer Architecture / Ed. D. A. Edwards. North-Holland: Elsevier Science Publishers B. -V.IFIP, 1989.-R 53-67.

80. Chen Y.Y., Hsu Y.C., King C.T. MULTIPAR: behavioral partition for synthesizing multiprocessor architectures // IEEE Trans, on VLSI Systems. 1994. -Vol.2.-№1.-P. 21-32.

81. Gebotys C.H., Elmastry M.I. Simultaneous scheduling and allocation for cost constrained optimal architectural synthesis // 28th Design Automation Conference: Proc, 1991. P. 2-7.

82. Hafer L., Parker A. A formal method for the specification, analysis, and design ofregister transfer-level digital logic // IEEE Trans, on CAD. 1983. - V.2. -№1.-P. 4-17.

83. Shin H., Woo N.S. A cost function based optimization technique for scheduling and data path synthesis // Int. Conference on Computer Design: Proc, 1989.

84. Hwang C.-T., Hsu Y.-C, Lin Y.-L. Optimum and heuristic data path scheduling under resource constraints // 27th Design Automation Conference: Proc, 1990.-P.65-70.

85. Landwehr B., Marwedel P., Domer R. OSCAR: Optimum Simultaneous Scheduling, Allocation and Resource binding based on integer programming // University of Dortmund. April 1994. Report № 484. - 54 p.

86. Pangrle B.M., Gajski D.D. Sheer : a state synthesizer for intelligent silicon compilation // IEEE Int. Conf on Computer Aided Design: Proc, 1987. -P. 42-45.

87. Tsai F.S., Hsu Y.C. STAR: an automatic data path allocator // IEEE Trans, on CAD. 1992. - V.l 1. - № 9.

88. Amellal S., Kaminska B. Functional synthesis of digital systems with TASS // IEEE Trans, on CAD of Integrated Circuits and Systems. 1994. - Vol. 13.-№5.-P. 537-552.

89. Glover F. Tabu search, Part I, Part II // ORSA J. Computing. 1989. - P. 4-32, 190-206.

90. Kirkpatric S., Gellat C, Jr., Vecchi M. Optimization by simulated annealing // Science. 1983. - Vol. 220. - P. 671-680.

91. Roussel-Ragot P., Dreyfus G. A problem independent parallel implementation of simulated annealing: models and experiments // IEEE Trans, on CAD. 1990. - Vol. 9. - № 8. - P. 827-835.

92. Axo A., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

93. Aho А. V., Garey M.R., Ullman J.D. The transitive reduction of a directed graph // SIAM Journal on Computing. 1972. - V.l. - № 2. - P. 131-137.

94. Lee E.A., Parks T.M. Dataflow process networks // Proc. of the IEEE. 1995. Vol 83. P. 773-801.

95. Buck J.T. Scheduling dynamic dataflow graphs with bounded memory using the token flow model // Technical Report UCB/ERL 93/69, Ph. D. Dissertation, Dept. EECS, University of Cahfornia, Berkeley, CA 94720. 1993. 177p.

96. Dennis J.B. First version of a data flow procedure language // Proc. Colloque sur la Programmation / Ed. B. Robinet. Lecture Notes in Computer Science. Vol. 19. -N.-Y.: Springer-Verlag, 1974. - P. 362-376.

97. Lee E.A. Consistency in dataflow graphs // IEEE Trans, on Parallel and Distributed Systems. April 1991. Vol. 2. №2.

98. Топорков В.В. Реализуемость потоковых моделей распределенных программ//Программирование. 2001. №5. С. 18-25.

99. Пакет программ решения задач оптимального упорядочения (ППП РУПОР). Описание программ // B.C. Танаев, B.C. Гордон, Ю.Н. Сотсков и др. Минск: Академия Наук БССР, Ин-т технической кибернетики. - 1987. - 78с.

100. Ульман Дж. Сложность задач упорядочения // Теория расписаний и вычислительные машины /Под ред. Э.Г. Коффмана. М.: Наука, 1984. - С. 158-189.

101. Ernst R., Henkel J., Benner Т. Hardware-software cosynthesis for microcontrollers // IEEE Design & Test of Computers. Dec. 1993. - P. 64-75.

102. Gupta R.K., De Micheli G. Hardware-software cosynthesis for digital systems // IEEE Design & Test of Computers. Sept. 1993. - P.29-41.

103. Аникушина A.C. Иерархическое моделирование программно-аппаратных систем // Тр. XXV Юбилейной междунар. конф. и дискуссионного научного клуба IT+SE'98, Украина, Крым, Ялта-Гурзуф. 1998. 4.1. С. 85.

104. Toporkov V.V., Anikushina A.S., Denesh A.M., Yazhuk A.A. Dataflow-dominated system-level partitioning // Труды Между нар. конф. и дискуссионного научного клуба IT+SE'97, Украина, Крым, Ялта-Гурзуф. 1997. С. 105-107 (на англ. яз.).

105. Anikushina A.S. Mixed flow models in system level design // Proc. of the XXII Int. School and Conf. on Computer Aided Design CAD-95. Ukraine, Crimea, Yalta-Gurzuff 1995. Part 2. P. 149 (на англ. языке).

106. Форд Л.Д., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966. - 274 с.

107. Сверхбольшие интегральные схемы и современная обработка сигналов /Под ред. С. Гуна, X. Уайтхауса, Т. Кайлата. М.: Радио и связь, 1989.-472 с.

108. Байцер Б. Микроанализ производительности вычислительных систем. М.: Радио и связь, 1983. - 360 с.

109. Рихтер К. Динамические задачи дискретной оптимизации. М.: Радио и связь, 1985. - 136 с.

110. Юдин Д.Б. Вычислительные методы теории принятия решений. -М.: Наука, 1989.-320 с.

111. Таха X. Введение в исследование операций: В 2-х книгах. М.: Мир, 1985. Кн. 1.-1985.-479 с; Кн. 2.- 1985.-499 с.

112. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.-328 с.

113. Липский В. Комбинаторика для программистов. М.: Мир, 1988. -213 с.

114. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: В 2-х книгах. М.: Мир, 1986. Кн.1. - 1986 - 349с.; Кн.2 - 1986. - 320 с.

115. Беллман Р. Динамическое программирование. М.: Изд-во иностранной лит-ры, 1960. - 400 с.

116. ТопорковаА.С, Топорков В.В. Оптимизация выполнения программ на масштабируемых ресурсах // Междунар. форум информатизации МФИ-2001. Доклады междунар. конф. "Информационные средства и технологии". М.: Изд-во "СТАНКИН". 2001. Т. 2. С. 10-13.

117. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.- М.: Наука, 1990. 384с.

118. Аникушина A.C. Автоматизированная система документирования процесса разработки программного обеспечения // Тр. Юбилейной XX Междунар. конф. и школы молодых ученых и специалистов САПР-93. Крым, Гурзуф, 1993. С. 76. *

119. Петерсон Р. LINUX: руководство по операционной системе. Издательская группа BHV. 1999.