автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Способы, алгоритмические, программные и аппаратные средства построения и визуализации образов катастроф в сложных системах

Введение.

Глава 1. Аналитический обзор средств аппаратной поддержки и способов построения и визуализации образов катастроф.

1.1. Общие сведения.

1.2. Средства аппаратной поддержки методов умножения.

1.2.1. Краткая история

1.2.2. Аппаратная поддержка методов умножения в универсальных процессорах.

1.2.3. Аппаратная реализация методов умножения в цифровых сигнальных процессорах.

1.2.4. Аппаратная поддержка методов умножения в ПЛИС

1.2.5. Специализированные устройства аппаратной поддержки методов умножения.

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

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

1.5. Выводы.

Глава 2. Разработка математической модели построения геометрических образов катастроф.

2.1. Основные положения теории катастроф.

2.2. Применение теории катастроф.

2.3. Основы математического аппарата теории катастроф.

2.3.1. Критические точки.

2.3.2. Диффеоморфизм.

2.3.3. Лемма Морса.

2.3.4. Лемма расщепления.

2.3.5. Структурная устойчивость.

2.3.6. Многообразия.

2.4. Понятийная схема бифуркационного множества.

2.5. Математическая постановка задачи построения многообразия катастрофы.

2.6. Список типичных катастроф.

2.7. Алгоритмическая реализация построения многообразий катастроф.

2.8. Выводы.

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

3.1. Алгоритм построения геометрических образов катастроф

3.2. Разработка аппаратных средств построения и визуализации образов катастроф.

3.2.1. Общая схема устройства.

3.2.2. Блок вычислений (БВ).

3.2.3. Вычислительный блок (ВБ)

3.2.4. Арифметический блок (АБ).

3.2.5. Командный блок (КБ).

3.2.6. Блок оперативной памяти одномерных данных (БЛПД)

3.2.7. Блок оперативной памяти табличных данных (БТПД).

3.2.8. Блок оперативной памяти индексов (БЛПИ).

3.2.9. Блок оперативной памяти команд (БЛПК).

3.2.10. Блок организации цикла по переменной i (БЦВ).

3.2.11. Блок организации цикла по переменной j (БЦИ).

3.2.12. Коммутатор шин (КШ)

3.2ЛЗ. Регистр результата сумматора (РРС).

3.3. Выводы.

Глава 4. Алгоритмы управления и оценка скоростных характеристик разработанного устройства.

4.1. Алгоритмы управления устройством.

4.1.1. Общий алгоритм работы устройства.

4.1.2. Инициализация блока БВ.

4.1.3. Инициализация блока КБ.

4.1.4. Инициализация блока ВБ.

4.1.5. Инициализация блока ВМ.

4.1.6. Инициализация блока ВП.

4.1.7. Инициализация блока МЗ

4.1.8. Инициализация блока ВЗ.

4.1.9. Инициализация блока ЦВ

4.1.10. Копирование параметров в блок БВ.

4.1.11. Копирование параметров в блок ВБ.

4.1.12. Вычисления блока БВ.

4.1.13. Вычисления блока ВБ.

4.1.14. Копирование параметров в блок MP.

4.1.15. Переход к следующему набору параметров.

4.1.16. Вывод количества координат.

4.1.17. Вывод координат.

4.2. Набор команд для блока вычислений БВ.

4.3. Оценка скоростных характеристик разработанного устройства.

4.3.1. Условия проведения экспериментов.

4.3.2. Быстродействие программной реализации алгоритма построения катастроф.

4.3.3. Быстродействие аппаратной реализации алгоритма построения катастроф.

4.3.4. Сравнительная оценка быстродействия программных и аппаратных средств.

4.4. Выводы.

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

Проблемам визуализации посвятили свои научные работы А. Пуанкаре, Д. Сэммон, У. Торгенсон, К. Пирсон, К. Фукунага, А.Ю. Терехина, Р.С. Лбов, Н.Г. Загоруйко и др.

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

На основании изложенного тема диссертационного исследова-% ния является актуальной и перспективной.

Работа выполнялась в рамках госбюджетных НИР по распоряжению Госкомвуза № 10-36-41, ИН/10-20-03 от 16.03.92 г. с пролонгацией до 2001 г. и гранту ГОО-1.4-1.5 (2000-2002 г.) Министерства образования РФ при непосредственном участии автора диссертации.

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

Задачи диссертации определяются следующим списком:

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

2. Разработать программные средства, реализующие работу созданных алгоритмов на персональных компьютерах.

3. Разработать схему вычислительного блока на основе двух базовых операционных автоматов (умножитель и сумматор).

4. Разработать обобщенную аппаратную реализацию специализированного устройства построения и визуализации образов катастроф и алгоритмы, определяющие работу управляющих автоматов

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

Методы исследования основываются на теории алгоритмов, топологической теории динамических систем, теории катастроф, а также теории автоматов и теории проектирования ЦЭВМ.

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

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

2. Создан комплекс алгоритмов построения образов катастроф и их визуализации, являющийся основой как для разработки программных средств и/или средств аппаратной поддержки.

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

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

5. Проведен сопоставительный анализ процессов визуализации образов катастроф, выполненных на уровне программных средств для персонального компьютера и на уровне разработанного специализированного устройства. Анализ позволил установить скоростные преимущества от 2 до 10 раз при реализации процессов визуализации с использованием специализированного устройства, что определяет целесообразность использования сопроцессора-акселератора построения и визуализации образов катастроф в составе архитектуры современных персональных компьютеров и вычислительных систем.

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

Апробация результатов работы. Результаты диссертационной работы обсуждались и получили положительную оценку на следующих научных кворумах: V-ой Международной конференции «Распо-знавание-2001», Курск, 2001 г., VI-ой Международной научно-технической конференции «Медико-экологические информационные технологии-2003», Курск, 2003 г (дважды).

Внедрение результатов работы. Полученные в диссертационной работе результаты используются при выполнении НИР по гранту Г02-4.2-5 и в учебном процессе Курского государственного технического университета, а также внедрены в Московском Агентстве сетевых технологий.

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

На защиту выносятся:

1. Способы и алгоритмы построения и визуализации геометрических многомерных образов катастроф.

2. Технические решения блока скоростных вычислений.

3. Структурно-функциональная реализация специализированного устройства построения и визуализации многомерных образов катастроф, а также алгоритмы работы его устройства управления.

4. Результаты исследования скоростных характеристик разработанных программных и аппаратных средств.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 56 наименований, одного приложения. Диссертация изложена на 130 страницах и содержит 50 рисунков и 15 таблиц.

4.4. Выводы

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

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

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

4. Определен набор экспериментов для исследования скоростных характеристик разработанных программных и аппаратных средств.

5. Проведен сопоставительный анализ процессов визуализации образов катастроф, выполненных на уровне программных средств для персонального компьютера и на уровне разработанного специализированного устройства. Анализ позволил установить скоростные преимущества от 2 до 10 раз при реализации процессов визуализации с использованием специализированного устройства в качестве сопроцессора-акселератора в составе архитектуры современных персональных компьютеров.

Заключение

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

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

2. Создан комплекс алгоритмов построения образов катастроф и их визуализации, являющийся основой для разработки программных средств и средств аппаратной поддержки.

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

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

5. Разработаны программные средства реализации созданных алгоритмов, пригодные для практического использования на ПЭВМ массового распространения.

6. Проведен сопоставительный анализ процессов визуализации образов катастроф, выполненных на уровне программных средств для персонального компьютера и на уровне разработанного специализированного устройства. Анализ позволил установить скоростные преимущества от 2 до 10 раз при реализации процессов построения и визуализации с использованием специализированного устройства, что обосновывает целесообразность его использования в качестве сопроцессора-акселератора в составе архитектуры современных персональных компьютеров.

Таким образом, целъ, поставленная в диссертационной работе, достигнута.

Публикации автора:

1. Киреев В. Н. Способ построения модели катастроф в системах обработки сигналов/ Сборник «Обработка сигналов». Ростов на Дону, АЛТЭК, 2002. С. 18-20.

2. Киреев В. Н. Построение геометрического образа катастрофы в N-мерном пространстве/ Материалы VI Международной научно-технической конференции «Медико-экологические информационные технологии-2003». Курск, 2003. С. 160-161.

3. Киреев В. Н. Аппаратные средства моделирования геометрического образа катастрофы/ Материалы VI Международной научно-технической конференции «Медико-экологические информационные технологии-2003». Курск, 2003. С. 159-160.

4. Крамаренко В. Ю., Киреев В. Н. К вопросу о разработке компьютерной модели теории катастроф и ее аппроксимации к системам распознавания сигналов/ Материалы V-ой Международной конференции «Распознавание-2001». Курск, 2001. С. 196-197.

5. Захаров И. С., Крамаренко В. Ю., Киреев В. Н. Сжатие и защита информации в условиях сетевой передачи данных, полученных при оценке явлений методами теории катастроф// Известия Курск, гос. техн. ун-та. 2002. №9. С. 89-94.

6. Довгаль В. М., Киреев В. Н., Крамаренко В. Ю. Построение аппроксимирующих эталонов катастроф для исследования оцифрованных сигналов// Известия Курск, гос. техн. ун-та. 2002. №9. С. 94-97.

1. Марков А.А., Нагорный P.M. "Теория алгорифмов". М.: Наука, 1984, 432 с.

2. Ачасова С.М., Бандман O.JI. "Корректность параллельных вычислительных процессов". Новосибирск: Наука, 1990, 252 с.

3. Джордейн Р. "Справочник программиста персональных компьютеров типа IBM PC, XN и AT". М: Финансы и статистика, 1992, 543 с.

4. Смит Б.Э., Джонсон М.Т. "Архитектура и программирование микропроцессора Intel 80386". М: ТОО "Кондор", 1992, 334 с.

5. Волш Д. "Технология программных модемов". М.: "ComputerWeek", 1997г, №32, с. 12-15.

6. Симэн Г. "Вейвлеты на программируемом кремнии". М.: "Компьютерра", 1998, №9, с. 17-23.

7. Цифровая обработка сигналов на ПЛИС Xilinx: Каталог продукции. Scan Engineering Telecom (код DSP-CAT-9906). 1999.

8. CORE Solutions Products Catalog. Xilinx Inc. 1999.

9. Балашов Ю.С., Мистюков В.Г., Капитанов В.Д. "Библиотеки цифровых макромодулей для средств проектирования ПЛИС". Воронеж. Xilinx Inc. 1999, с. 26.

10. Villasenor J., Mangione-Smith W. "Configurable Computing". Scientific American. June 1997.

11. П.Довгаль B.M. "Методы модификации формальных систем обработки символьной информации", Курск: Курск, гос. техн. ун-т, 1996. 115 с.

12. А.с. 1807481 СССР, МКИ G 06 F 7/52 / Устройство умножения /. Опубл. 1993 г.

13. А.с. 1783519 СССР, МКИ G 06 F 7/52 / Устройство умножения /. Опубл. 1992 г.

14. А.с. 2021633 Россия, МКИ G 06 F 7/52 / Последовательный умножитель /. Опубл. 1994 г.

15. А.с. 1803914 СССР, МКИ G 06 F 7/52 / Устройство умножения /. Опубл. 1993 г.

16. А.с. 1758644 СССР, МКИ G 06 F 7/52 / Устройство для умножения чисел с фиксированной запятой/. Опубл. 1992 г.

17. А.с. 1777134 СССР, МКИ G 06 F 7/52 / Отказоустойчивое устройство умножения/. Опубл. 1992 г.

18. А.с. 1789981 СССР, МКИ G 06 F 7/52 / Отказоустойчивое устройство умножения /. Опубл. 1993 г.

19. А.с. 2021631 Россия, МКИ G 06 F 7/52 / Отказоустойчивое устройство умножения /. Опубл. 1994 г.

20. А.с. 1833866 СССР, МКИ G 06 F 7/52 / Устройство умножения по методу Четвертьквадратичного умножения /. Опубл. 1993 г.

21. А.с. 1735843 СССР, МКИ G 06 F 7/52 / Матричное устройство умножения с модифицированной ячейкой /. Опубл. 1992 г.

22. А.с. 2018932 Россия, МКИ G 06 F 7/52 / Матричное устройство для умножения и деления /. Опубл. 1994 г.

23. А.с. 1741128 СССР, МКИ G 06 F 7/52 / Аппаратный контроль в умножителях /. Опубл. 1992 г.

24. А.с. 1784973 СССР, МКИ G 06 F 7/52 / Устройство для умножения двоичных чисел /. Опубл. 1992 г.

25. А.с. 1741129 СССР, МКИ G 06 F 7/52 / Устройство умножения для чисел /. Опубл. 1992 г.

26. А.с. 2054709 Россия, МКИ G 06 F 7/52 / Устройство для умножения чисел в позиционном коде /. Опубл. 1996 г.

27. А.с. 2022338 Россия, МКИ G 06 F 7/52 / Умножение чисел с плавающей запятой с использованием логарифмирования и экспоненцирования /. Опубл. 1994 г.

28. А.С. 2012039 Россия, МКИ G 06 F 7/52 / Одно-тактовый умножитель двоичных чисел /. Опубл. 1994 г.

29. А.С. 2097826 Россия, МКИ G 06 F 7/50 / Параллельный асинхронный сумматор /. Опубл. 1997 г.

30. Абышкин В.Е. "Устройства умножения на основе параллельных продукционных алгоритмов". Курск: Курск, гос. техн. ун-т, 2001.

31. Томсон Дж. М. Т. "Неустойчивости и катастрофы в науке и технике". М.: Мир, 1985, 254 с.

32. Постон Т., Стюарт И. "Теория катастроф и ее приложения". М.: Мир, 1980, 607 с.

33. Арнольд В. И. "Теория катастроф". Московский университет, 1983, 79 с.

34. Маневич JI. И. "О теории катастроф". Соросовский образовательный журнал, том 6, №7, 2000, с. 85-90.

35. Фейгин М. И. "Динамические системы, функционирующие в сопровождении опасных бифуркаций". Соросовский образовательный журнал, №10, 1999, с. 122-127.

36. Арнольд В. И. "Критические точки гладких функций и их нормальные формы". УМН, 1975, 665 с.

37. Стюарт И. Н., Толл Д. О. (I. N. Stewart, D. О. Tall) "The Foundations of Mathematics". Oxford University Press, London and New York, 1977.

38. Хант Дж. У. (G. W. Hunt) "Local diffeomorphisms umbilic catastrophes". New York and London, 1973.

39. Морс M. (M. Morse) "The critical points of a functions of n variables". Trans. Amer. Math. Soc. №33, 1931.

40. Арнольд В. И. "Wave front evolution and equivariant Morse lemma". Common. Pure. Appl. Math. №29, 1976.

41. Tom P. (R. Thom) "The two-fold way of catastrophe theory In Structural Stability". Springer, Berlin and New York, 1976.

42. Том P. (R. Thom) "Structural stability, catastrophe theory and applied mathematics". SI AM, 1977.

43. Томпсон Дж. M. Т., Хант Дж. У. (J. М. Т. Thompson, G. W. Hunt) "A bifurcation theory for the instabilities of optimization and design". Mathematical Methods in the Social Sciences, 1978.

44. Кэллахан Дж. Дж. (J. J. Callahan) "Singularities of plain maps II. Sketching catastrophes". University of Warwick, 1976.

45. Арнольд В. И. "Нормальные формы для функций вблизи вырожденных критических точек, группы Вейля Ak, Dk и Е^ и лагранжевы особенности". Функц. анализ и его приложения, 1972.

46. Вудкок А. Э. Р., Постон Т. (А. Е. R. Woodcock, Т. A. Poston) "Geometrical Study of the Elementary Catastrophes". Springer, Berlin and New York, 1976.

47. Арнольд В. И. "Особенности в вариационном исчислении". Современные проблемы математики т. 22. М: ВИНИТИ, 1983.

48. Томпсон Дж. М. Т. "Неустойчивости и катастрофы в науке и технике". М.: Мир, 1985.

49. Джилмор Р. "Теория катастроф для ученых и инженеров". М.: Мир, 1983.

50. Берг А. Предисловие к книге Ст. Бира "Кибернетика и управление производства". М.: Мир, 1965.

51. Киреев В. Н. Способ построения модели катастроф в системах обработки сигналов/ Сборник «Обработка сигналов». Ростов на Дону, АЛТЭК, 2002. С. 18-20.

52. Киреев В. Н. Построение геометрического образа катастрофы в N-мерном пространстве/ Материалы VI Международной научно-технической конференции «Медико-экологические информационные технологии-2003». Курск, 2003. С. 160-161.

53. Киреев В. Н. Аппаратные средства моделирования геометрического образа катастрофы/ Материалы VI Международной научно-технической конференции «Медико-экологические информационные техноло-гии-2003». Курск, 2003. С. 159-160.

54. Крамаренко В. Ю., Киреев В. Н. К вопросу о разработке компьютерной модели теории катастроф и ее аппроксимации к системам распознавания сигналов/ Материалы V-ой Международной конференции «Распо-знавание-2001». Курск, 2001. С. 196-197.

55. Захаров И. С., Крамаренко В. Ю., Киреев В. Н. Сжатие и защита информации в условиях сетевой передачи данных, полученных при оценке явлений методами теории катастроф// Известия Курск, гос. техн. ун-та. 2002. №9. С. 89-94.

56. Довгаль В. М., Киреев В. Н., Крамаренко В. Ю. Построение аппроксимирующих эталонов катастроф для исследования оцифрованных сигналов// Известия Курск, гос. техн. ун-та. 2002. №9. С. 94-97.

57. КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ1. На правах рукописи1. КИРЕЕВ ВИКТОР НИКОЛАЕВИЧ

58. СПОСОБЫ, АЛГОРИТМИЧЕСКИЕ, ПРОГРАММНЫЕ И АППАРАТНЫЕ СРЕДСТВА ПОСТРОЕНИЯ И ВИЗУАЛИЗАЦИИ ОБРАЗОВ КАТАСТРОФ В СЛОЖНЫХ СИСТЕМАХ

59. Специальность 05.13.05 "Элементы и устройства вычислительной техники и систем управления"