Реконфигурируемый мультипроцессор для реализации модифицированных алгоритмов обработки сигналов тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Селезнев, Михаил Евгеньевич

• Селезнев, Михаил Евгеньевич
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Селезнев, Михаил Евгеньевич

ВВЕДЕНИЕ

Глава 1. ОБЗОР АЛГОРИТМИЧЕСКИХ И АППАРАТНЫХ

СРЕДСТВ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ

1.1. Алгоритмы вычисления свертки и ДПФ

1.2. Планирование параллельного исполнения 23 алгоритмов

1.3. Процессоры обработки сигналов

1.4. Сущность предлагаемого подхода

1.5. Выводы

Глава 2. БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ СВЕРТКИ

И ДПФ И ИХ ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ

2.1. Исследование вычислительной сложности 35 алгоритмов быстрого преобразования

Фурье

2.2. Матричное представление быстрых алго- 51 ритмов Винограда вычисления свертки и

2.3. Способ минимизации числа сложений в 62 алгоритмах Винограда вычисления свертки и ДПФ

2.4. Способ параллельного выполнения груп- 65 пы алгоритмов Винограда

2.5. Способ параллельного выполнения моди- 7 8 фицированных алгоритмов Винограда

2.6. Выводы

Глава 3. АРХИТЕКТУРА СИГНАЛЬНОГО

МУЛЬТИПРОЦЕССОРА, ОРИЕНТИРОВАННОГО НА ВЫЧИСЛЕНИЕ СВЕРТОК И ДПФ ПО МЕТОДУ ВИНОГРАДА

3.1. Построение сигнальных процессоров, 88 основанных на принципе реконфигурации

3.2. Структурный операционный элемент 92 мультипроцессора, первый уровень рек о н ф и г у р а ци и

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

3.4. Выводы

Глава 4.МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА

АЛГОРИТМОВ ВИНОГРАДА И РЕЗУЛВТАТЫ ЕГО ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ

4.1. Разработка и исследование алгоритма 122 минимизации числа сложений группы алгоритмов Винограда

4.2. Оценка производительности архитектуры 125 реконфигурируемого сигнального мультипроцессора

4.3. Пример практического использования 147 сигнального мультипроцессора

4.4. Выводы 155 ЗАКЛЮЧЕНИЕ 15 7 БИБЛИОГРАФИЧЕСКИЙ СПИСОК 15 9 ПРИЛОЖЕНИЕ

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

Актуальность темы. Конец XX века характеризуется ла винообразным нарастанием потоков информации в самых различных областях человеческой деятельности. Информация поступает к конечному пользователю в виде сигнала, который можно определить как функцию, переносящую информацию о состоянии и поведении физической системы [1].

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

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

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

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

По мнению ведущих специалистов таких признанных фирм-лидеров в области сигнальных процессоров, как TI (Texas Instruments), Analog Devices, Motorola, производство ЦПОС в ближайшие 10 лет возрастет в десятки раз и достигнет объема продаж на сумму 50 млрд. долларов. Рынок сигнальных процессоров увеличивается ежегодно не менее чем на 4 0%, значительно опережая развитие других направлений электронной промышленности. Фирма TI инвестировала 800 млн. долларов на создание научного центра для разработки сигнальных процессоров нового поколения, а также 100 млн. долларов для поддержки компаний, разрабатывающих аппаратуру на сигнальных процессорах нового поколения [2].

Исследованием в области алгоритмических и аппаратных средств ЦОС посвятили свои работы известные зарубежные и отечественные ученые Ярославский Л.П., Гагарин Ю.И., Луцкий P.M., Кули Дж.В. (Cooley J.W.), Тьюки Дж.В. (Tukey J.W.), Виноград С. (Winograd S.), Нуссбаумер Г.Дж. (Nussbaumer H.J.), Рейдер K.M. (Rader С.М.), Агарвал P.K. (Agarwal R.С.).

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

Диссертационная работа выполнялась в рамках НИР единому заказ-наряду (распоряжение Госкомвуза №10-36-41, ИН/10-20-03 от 16.03.92).

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

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

1.Исследование вычислительной сложности алгоритмов Винограда вычисления свертки и ДПФ.

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

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

4.Модификация известных базовых алгоритмов Винограда.

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

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

7.Исследование скоростных характеристик разработанного вычислительного устройства.

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

Научная новизна работы состоит в следующем:

1.Впервые разраОотан неэвристический алгоритм минимизации числа сложений в матрицах предсложения и постсложения алгоритмов Винограда, позволяющий повысить скорость обработки сигналов.

2.Предложена способ модификации алгоритмов Винограда вычисления свертки и ДПФ, дающая возможность распараллеливать вычислительные процессы.

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

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

5.Разработан способ структурно-функциональной организации базовой архитектуры реконфигурируемого мультипроцессора, ориентированного на высокоскоростное выполнение алгоритмов Винограда и имеющего скоростные преимущества по сравнению с аналогом (при вычислении свертки в 2 - 5,4 раза, ДПФ в 1,7 5 - 6,5 раз).

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

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

1.Способ и алгоритм минимизации числа сложений в матрица?: предсложений и постсложений алгоритмов Винограда вычисления свертки и ДПФ.

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

3.Способы и алгоритмы планирования параллелвного выполнения о а з о вых и модифицированных алгоритмов Винограда вычисления свертки и ДПФ.

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

5.Способ структурно-функциональной организации мультипроцессора, ориентированного на высокоскоростное выполнение алгоритмов Винограда вычисления свертки и ДПФ.

6.Архитектура АЛУ и реконфигурируемого сигнального мультипроцессора на его основе.

7.Результаты исследования скоростных характеристик реконфигурируемого мультипроцессора, ориентированного) на высокоскоростное выполнение алгоритмов Винограда вычисления свертки и ДПФ.

Реализация и внедрение результатов иследований. Результаты диссертационной работы нашли применение при выполнении госбюджетных НИР КурГТУ (по единому заказ-наряду) , внедрены в СКВ "Авиаавтоматика" г.Курск, а также в учебный процесс Курского Государственного Технического университета (дисциплина: "Высокопроизводительные системы обработки информации").

Апробация работы. Результаты, полученные в ходе диссертационных исследований, были представлены на 3-й международной конференции "Распознавание-97" (г.Курск, 1997г.), международной технической конференции "Медико-э коло ги ч е с ки е и н форма ци о н ные технологии" (г.Кур с к, 1998г.), 4-ой международной конференции "Теория и техника передачи, приема и обработки информации" ("Новые информационные технологии") (г.Харьков, 1998г.), 1-ой всероссийской научно-технической конференции "Компьютерные технологии в науке, проектировании и производстве" (г.Нижний Новгород, 1999г.), 4-ой международной конференции "Распо-знавание-99" (г.Курск, 1999г.), всероссийской конференции "Интеллектуальные информационные системы" (г.Воронеж, 19 9 9 г . ) .

Публикации. Результаты, представленные в диссертационной работе, были отражены в 10 печатных работах, из них 3 статьи и 1 положительное решение по заявке на выдачу патента на изобретение.

Структура и объем работы. Ди ссертационная раоота состоит из введения, четырех глав, заключения, списка литературы 84 наименования и приложения. Текст диссертации включает 223 машинописные страницы основного текста, содержит 33 рисунка и 16 таблиц.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Селезнев, Михаил Евгеньевич

4.4 Выводы.

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

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

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

ЗАКЛЮЧЕНИЕ

1. Произведен сравнительный анализ вычислительной сложности алгоритмов Кули-Тьюки и Винограда быстрого преобразования Фурье, показывающий преимущество БПФ-алгоритмов Винограда.

2. Разработан способ и алгоритм минимизации числа сложений в матрицах предсложений и постсложений алгоритмов Винограда вычисления свертки и ДПФ.

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

4. Разработан способ и комплекс алгоритмов планирования хода вычислительного процесса базовых и модифицированных алгоритмов Винограда с целью повышения скорости вычисления свертки и ДПФ.

5. Предложена архитектура высокопроизводительного сигнального мультипроцессора, особенностью которой является наличие двух уровней реконфигурации. Реконфигурация первого уровня осуществляется путем изменения конфигурации арифметико-логических устройств мультипроцессора, реконфигурация второго уровня осуществляется путем изменения структуры связей между АДУ и регистровой памятью мультипроцессора. Использование двух уровней реконфигурации позволяет достигнуть скоростных премиуществ по сравнению с аналогом ТМЭ320С80 при вычислении свертки в 2 - 5,4 раза, и ДПФ в 1,7 5 - 6,5 раза.

Список литературы диссертационного исследования кандидат технических наук Селезнев, Михаил Евгеньевич, 2000 год

1.0ппенгейм А., Шафер Р. Цифровая обработка сигналов. -М.: Связь, 1979, 416с.

2. Инвестиции фирмы Texas Instruments в новые разработки на сигнальных процессорах. // Электронные компоненты и системы. 19 98. №4, С.12

3. Рабинер JI.P., Гоулд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978, - 848с.

4. Вайрадян А.С., Пчелинцев И.П., Челышев М.Н. Алгоритмы вычисления цифровых сверток. // Зарубежн. радиоэлектрон. 1982. №3, с.3-34.

5. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989, - 448с.

6. Быстрые алгоритмы в цифровой обработке изображений / Т.С. Хуанг, Дж.-О. Эклунд, Г.Дж. Нуссбаумер и др.; под ред. Т.С. Хуанга. М.: Радио и связь, 1984.

7. Agarwal R.C., and Cooley J.W., New Algorithms for Digital Convolution // IEEE Trans. Acoust., Speech, Signal Proc. ASSP-25 (1977): 392-410.

8. Даджион Д. л Мерсеро Р. Цифровая обработка многомерных сигналов. М.: Мир, 1988.

9. Nussbaumer Н. J., Digital Filtering Using Polynomial Transforms // Electron. Lett. 13 (1977): 386-387.

10. Winograd S., On Computing the Discrete Fourier Transform // Math. Сотр., 32 (1978): 175-199.

11. Winograd S., On Computing the Discrete Fourier Transform // Proc. Nat. Acad. Sci. USA, 73 (1976): 10051006.

12. Nussbaumer H.J., and Quandalle P., Fast Computation of Discrete Fourier Transforms Using Polynomial Transforms // IEEE Trans. Acoust., Speech, Signal Proc. ASSP-27 (1979) : 1 69-181.

13. Ахмед H., Pao K.P. Ортогональные преобразования для цифровой обработки сигналов. М.: Радио и связь, 1980,

14. Г/.Дагман Э.Е., Кухарев Г.А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983,232с.

15. Гагарин Ю.И. Псевдогнездовые алгоритмы двумерного косинусного преобразования // Электронное моделирование. Киев, 19 91. №2, с.107.

16. Брайсуэлл Р.Н. Быстрое преобразование Хартли. // ТИИЭР 1984. т.72, №8 с.19-27.

17. Гагарин Ю.И., Гагарин К.Ю., Козлов В. Р. Быстрые алгоритмы теоретико-числовых преобразований Мерсенна // Логическое управление с использованием ЭВМ. Труды 13 Всесоюзного симпозиума. Москва: 19 90, 20с.

18. Солодовников А.И., Спиваковский A.M. Основы теории и методы спектральной обработки информации. JI. : Изд. ЛГУ, 1986. - 270с.

19. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М. : Радио и связь, 1989. -17 6с.

20. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981. - 254с.

21. Параллельные вычисления / под ред.Г. Родрига. М.: Наука, 1986. - 372с.

22. Карцев М.А. Архитектура цифровых вычислительных машин. М.: Наука, 1978. 296с.

23. Майерс, Гленфорд. Архитектура современных ЭВМ. В 2-х кн. М.: Мир, 1985.

24. Самофалов К.Г., Луцкий Г.М. Основы теории многоуровневых конвейерных вычислительных систем. М. : Радио и связь, 1989. - 272с.

25. Мультипроцессорные системы и параллельные вычисления / под ред. Ф.Г. Энслоу М.: Мир, 1976. - 383с.

26. Бессалах X., Луцкий Г.М. Алгоритмы быстрого преобразования Фурье и их реализация на рекурсивных конвейерных процессорах // Вестн. КПИ. Сер. автоматики и электроприборостроения. 1981. -№18. - с.55-59.

27. Мясников В.А., Игнатьев М.Б., Шейнин Ю.Е. Архитектура модульной многомикропроцессорной вычислительной системы // Кибернетика 1984. - №3. - с.46-53.3 6.Системы параллельной обработки / под ред. Д.Ивенса,

28. М.: Мир, 1985. 413с. 37 .Кун С. Матричные процессоры на СБИС. - М. : Мир, 1991.

29. Цифровые сигнальные процессоры. Кн.1 / Марков С. М.: Микроарт, 1996.

30. Ерофеев А,.А. Сигнальные процессоры. М.: Знание, 1991. 63с.

31. ADSP 21xx Family Manual. Analog Devices, Inc., 19 95.

32. DSP56000 24-bit. Digital Signal Processor. Family Manual. Motorola, Inc., 1995.4 8.TMS32 0C80. Multimedia Video Processor (MVP). Technical Brief, Texas Instruments, Inc., 1994.

33. TMS320C62xx. Technical Brief. Texas Instruments, Inc., January 1997.

34. ЗО.Кухарев Г. А. Систолические процессоры для обработки сигналов. Минск: Беларусь, 1988. 127с.

35. Rader, С.М., and N.M. Brenner, A new Principle for Fast Fourier Transformation, IEEE Trans. Acoust., Speech, Signal .Proc. ASSP-24 (1976): 264-265.

36. Bluestein, L.I., A Linear Filtering Approach to the Computation of the Discrete Fourier Transform, IEEE Trans. Audio Electroacoust. AU-18 (1970): 451-455.

37. Evader C.M., Discrete Fourier Transforms When the Number of Data Samples Is Prime, Proc. IEEE 56 (1968) : 1107-1108.

38. Селезнев M.E. К вопросу о создании технических средств обработки сигналов. // Сборник материалов 3 международной конференции «Распознавание-97». Курск, гос. техн. ун-т. Курск, 1997. С. 214.

39. Селезнев М.Е. Архитектура высокопроизводительного сигнального мультипроцессора. // Сборник материалов 4 международной конференции «Распознавание-99». Курск, гос. техн. ун-т. Курск, 1999. С. 73.

40. Заявка о выдаче патента Российской Федерации на изобретение №99109904, приоритет от 05.05.99г. // «Рекон-фигурируемый асинхронный сумматор-умножитель», Довгалв В.М., Селезнев М.Е., Старков Ф.А., Титов B.C.

41. Селезнев М.Е. К вопросу о создании высокопроизводительных устройств обработки и передачи цифровой информации. // Труды всероссийской конференции «Интеллектуальные информационные системы». Воронежский гос. техн. ун-т. Воронеж, 1999. С. 186-187.

42. К вопросу о минимизации числа сложений в алгоритмах вычисления свертки и ДПФ / М.Е. Селезнев; Курск, гос.техн. ун-т. Курск, 1999. 9с.: Библиогр. 5 назв. Рус. Деп. в ВИНИТИ 03.12.99 № 3 610-В99.

43. Планирование параллельной реализации алгоритмов Винограда вычисления свертки и ДПФ / Курск, гос. техн. унт. Курск, 1999. 29с.: ил. Библиогр. 10 назв. Рус. Деп. в ВИНИТИ 28.12.99 № 3862-В99.

44. Реконфигурируемый сигнальный мультипроцессор / Курск, гос. техн. ун-т. Курск, 1999. 21с.: ил. Библиогр. 8 назв. Рус. Деп. в ВИНИТИ 28.12.99 № 38 63-В99.

45. Айэрленд К., Роузен Н. Классическое введение в современную теорию чисел. М.: Мир, 1987. 415с.65.ÄXO А., Хопкрофт Дж. , Улвман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536с.

46. Барский A.B. Планирование параллелвных вычислительных процессов. М.: Машиностроение, 1980. - 191с.

47. Бахтеяров C.B. Транспьютерная технология. М. : Радио и связо, 1993. 302с.

48. Белый A.A., Бовбель Б.И., Микулович В.И. Алгоритмы быстрого преобразования Фурве и их свойства. // Зарубежн. радиоэлектрон. 1979. №2 с.3-29.

49. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. - 57 6с.

50. Власенко В.А., Лаппа Ю.М. Матричный подход к построению быстрых алгоритмов многомерного дискретного преобразования Фурье. // Изв. вузов. Радиоэлектроника. 1986. т. 29. №1 с.8 6-8 9.

51. Калабеков Б.А. Микропроцессоры и их применение в система?: обработки и передачи сигналов. М. : Радио и связв, 1988. 368с.

52. Корнеев В.В., Киселев A.B. Современные микропроцессоры. М.: Нолидж, 1998. 231с.

53. Кумаресан Р., Гупта П.К. Алгоритм БПФ для простых множителей на основе арифметики действительных чисел. // ТИИЭР 1985, т.73 №7 с.98-100.

54. Маклеллан Дж.Х., Рейдер Ч.М. Применение теории -чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. - 264с.

55. Матричная интерпретация и вычислительная эффективноств алгоритмов БПФ. // РЭ. 198 4 т.29, №2 с.2 65-274.

56. Рабинер Л.Р., Шафер Р. В. Цифровая обработка речевых сигналов. М.: Радио и связь, 1981. - 496с.7 9.Уэйзер Л. Быстродействующий цифровой умножитель для обработки сигналов в реальном времени // Электроника. -1977. №20. - с.40-49.

57. O.Xoap Ч. Взаимодействующие последовательные процессы. -М.: Мир, 1989. 264с.

58. Цифровая обработка сигналов и ее применения. Сб. статей под ред. Л.П. Ярославского. - М.: Наука, 1981. -222с.82:.ГОэн 11. Микропроцессорные системы и их применение при обработке сигналов. М.: Радио и связв, 1988.167

59. FPGA Adders: Performance Evaluation and Optimal Design / Xing Shanzhen // IEEE Des. And Test Comput. 15 (1998) №1: 24-29.

60. VLIW Architecture offers a Ten-Fold Improvement in Digital Signal Processing / Bursky D. // Electron. Des. 4 5 (1997) №5: 52.end; begin

61. PAS:=New(PAdditionsStore, Init) ; PRM1.:=New(PRepMatrix,Create); PRM1.A.Load('dftci.dat' , 9) ; PRM1.A.Show; PRM[1]A.WriteFiff) ; i : = 1;

62. DoRecurse ( i) ; Dispose(PRM 1. ); Dispose(PAS); end ;1. B e g i n clrscr;assign ( ff, 'res.txt'); r ewrite(ff);1. Do 11;close (ff) ; End.1. Программа GRAF.PAS

63. Program Graf; uses crt,graf1;1. Ачрех;

64. Arcs; object {Дуга графа} OutApex: PApex; I n Ар e x : P Ар e x ; Next: PArcs; end;1. PArcsByNum = AArcsByNum;

65. ArcsByNum = object {Дуга графа по номерам вершин} OutApex: integer; InApex: integer; N e x t: PAr с s В у Num. ;end;

66. PApexPointer=AApexPointer;

67. ApexPointer = object {Элемент списка указателей на вершины графа}

68. Next: PApexPointer ; Apex: РАрех; ArcToApex: РАрех; end;1. POperSet=/4OperSet ;

69. OperSet=object {Множество, хранящее взаимно независимые операторы (ВНО)}rv: integer," {Число операций, входящих в ВНО} ApexSet: PApexPointer; ApexSetLast: PApexPointer;

70. ArcsGenerated: boolean; {Сгенерированы варианты дугили еще нет}

71. AV: PArcVariantStore; {Варианты дуг} publicconstructor Create; destructor Destroy;procedure AppendApex(hApex: PApex); function

72. Graf = object {Модель графа программы} Tkr: integer; iruntv: integer;

73. ApexSet: PApex; { Совокупность вершин графа} ApexSetLast: PApex;

74. ArcSet: PArcs; { Совокупность дуг графа} ArcSetLast: PArcs;

75. Gr1: PGraf; Time: integer;

76. ApexSet :=nil; ApexSetLast :r-=nil; rv:=0;

77. ArcsGenerated:=false; AV:=New(PArcVariantStore,Create); end;destructor GperSet.Destroy;var hPApex,hPApex2: PApexPointer; beginhPApex:=ApexSet; while hPApexOnii do begin hPApex2:=hPApexA.Next; Dispose(hPApex); hPApex:=hPApex2; end;

78. ApexSet :=nil; ApexSetLast :=nil; rv:=0;

79. ApexSetLastA.Next := hPApexPointer; ApexSetLast := hPApexPointer; end;rv:=rv+1; end;function

80. OperSet.ControlTime(AVar:iAl00;ArcNumber:integer):boolean; var hPArc: PArcVariant;hPApexOut,hPApexIn: PApexPointer; i,j: integer;beginif ArcNumber>0 then ControlTime:=true else

81. GenerateArcs:=true; ArcsGenerated:=true end else

82. GenerateArcs:=false; AVA.WriteVariants(ff); end;function OperSet.GetNextArcsVariant(var hPAxcs:PArcsByNum):boolean; var G:iAl00;

83. GetNextArcsVariant:=true; end else

84. GetNextArcsVariant:=false;end;constructor Graf.Create; begin

85. Tkr:=0; mintv:=0; ApexSet :=nil;

86. ApexSetLast :=nil; ArcSet :=nil; ArcSetLast :=nil; SetVNO :=nil; end;destructor Graf.Destroy; va r hPAp ex,h PAp ex 2: PAp e x; hPArc, hPArc2: PArcs;begin Tkr:=0; mintv:=0;if SetVNOOnil then

87. Dispose(SetVNO,Destroy) ; h P Ap e x : = Ap e x S e t; 'while hPApexonil do begin h PApe x 2:= h PAp exA.Ne x t; Dispose(hPApex); hPApex: --hPApex 2; end;h PAr c:=Ar cSet; while hPArcOnil do begin hPArc2:=hPArcA.Next; Dispose(hPArc); hPArc:=hPArc2; end;

88. AppendArc(GetPApex(hPArc^.OutApex) , GetPApex(hPArcA.InApex) ) ; hPArc: =hPAro .Next; Dispose(hPArc2); end ; end;procedure Graf.LoadFromSet(FileName:string); var i: integer; ff: text;hS, iiSpi , hSp2 : String;

89. Val(hSpl, OutArc, Code); if code <> 0 then begin

90. Writeln('Ошибка в позиции выхода дуги: Code); exit ; end;

91. Val(hSp2, InArc, Code); if code <> 0 then begin

92. Wri teln('Ошибка в позиции входа дуги: Code);exit ; end;if GetPApex(OutArc)=Nil then

93. AppendApex(OutArc, 1) ; if GetPApex(InArc)=Nil then

94. Val (hSpl, NumApex, Code) ; if code <> 0 then begin

95. Writeln('Ошибка в позиции номера вершины: Code); exit; end;

96. Val (hSp2, WeightApex, Code) ; if code <> 0 then begin

97. Writeln('Ошибка в позиции веса вершины: Code); exit; end ;if GetPApex(NumApex)-Nil then

98. AppericiApex (NumApex, Weight Apex) else

99. Get PAp e x (NuniAp e x) A . W e i gh t: = W e i gh t Ap e x ;end; end; unti1 (h S —''); end;procedure Graf.Copy(Gr:PGraf); var h PApe x: PAp e x; hPArc: PArcs;begin

100. Tkr:=GrA.Tkr; mintv:=GrA.min t v; h PAp ex : =Gr A . ApexSet. ; while hPApexOnxi do begin

101. AppendApex(hPApexA.ID,hPApexA.Weight); ApexSetLastA.tau e:=hPApexA.tau e; ApexSetLastA.tau 1:=hPApexA.tau 1; ti PAp ex : =hPApex A . Next;hPArc:=GrA.ArcSet; while hPArcOnil do begin

102. MinProcessors:=Trunc2(n); end;function Graf.MinTime(n:integer): integer; v a r h PAp e x: PAp e x;st, T, 02,01: integer; d: real;begin s t: -- 0;h PAp e x:=Ape x S e t; while hPApexONil do begin s t:= s t + h PAp exA.Weight; hPApex:"hPApexA.Next; end;

103. SetVNO:=New(POperSet,Create);h PA p e x:=Ар e x S e t;while hPApexOnil do beginif (mintv^PApex74. taue-hPApexA . Weight) AND (mintv<=hPApexA.taue) then

104. SG0 j :=New(PGraf,Create) ; PrevGr:-SG [ 0.;

105. PrevGr . LoadFromSet (GrafName) ;1. PrevGr".FindEarlyTimes;

106. PrevGr".FindLateTimes(Time);1. PrevGr " . Shovvr;

107. Pre vG i"" .WriteGraf ( f f) ;n:=PrevGr".MinProcessors(Time);writein(n);writelij (ff, 'Минимальное количество процессоров = ',n);v : = 0 ;repeat

108. NoMoreVariants:=false; end else1. NoMoreVariants:=true;end;if PrevGr".SetVNO".GetNextArcsVariant(hPArcsByNum) thenbegin

109. NoMoreVariants:=false ; v:—vf1;

110. SGvj :=New(PGraf,Create); G r : = S G [ v . ;1. Gr А.Copy(PrevGr);

111. Gr A.AppendSetOfArcs(hPArcsByNum); GrA. FindEarlyTimes ; GrA.FindLateTimes(Time); Gr A.Show;

112. GrA.WriteGraf(ff); PrevGr:=Gr; end else

113. NoMoreVariants:-true; if NoMoreVariants then begin if v^O then begin n:-¡1+1;

114. PrevGr'"4 . FindEarlyTimes; PrevGr74 . FindLateTimes (Time) ; PrevGrA.Show; PrevGr-" .WriteGraf iff) ;writeln ( ff, 'Количество процессоров = ',n); end else beginif SG v. onil then

115. Dispose(SGv.,Destroy); v:=v-1 ;

116. Pre"GrЛ.LoadFromSet(GrafName);

117. PrevGr '"' . EnndEarlyTimes ;

118. PrevGr''4 . FindLateTimes (PrevGrA . Tkr) ;r'revGr ' . Show;

119. РгоЫеш2 : =Т0 end else begin v: ~ 0 ;1. Tm:^Bescon;

120. PrevGrА.FindLateTimes(Tm); repeat

121. NoMoreVariants:=false; end. else1. NoMoreVariants:=true;end;if PrevGrA.SetVNOA.GetNextArcsVariant(hPArcsByNum) thenb e g i n

122. NoMo r eVa r i a n t s:= f a1s e; v:=v+1;

123. S Gv. :-New(PGraf,Create);1. Gr:=SGv.;1. GrA.Copy(PrevGr);

124. GrA.AppendSetOfArcs(hPArcsByNum); GrA.FindEarlyTimes; GrA.FindLateTimes(Tm); GrA.Show;

125. GrA.WriteGraf(ff); PrevGr:=Gr; end else

126. NoMoreVariants:=true; if NoMoreVariants then begin if v>0 then begin if SGv.onil then

127. Dispose(SGv.,Destroy); v:=v-l;

128. P г о g ram G r a fMo d i f у; uses crt,grafl;type

129. P Ар e x = " Ар e x ; PArcs = "Arcs; Arcs = object {Дуга графа} Ou tАр e x: PАр e x; InApex: PApex; Next: PArcs; end;1. PArcsByNum = '^ArcsByNum;

130. Ar-csByNum = object {Дуга графа по номерам вершин} OutApex: integer; InApex: integer; Next: PAr с s В yNum; end;

131. Apex = object {Вершина графа} ID: integer;

132. Weight: integer; {Вес вершины} Energy: integer; {Мощность вершины} taue: integer; {Раннее время выполнения} taul: integer; {Позднее время выполнения} Next: PApex; processed: boolean; TTkr: integer; {T-Tkr} publicfunction IsCritical¡boolean; end;

133. PApexPointer-AApexPointer;

134. ApexPointer = object {Элемент списка указателей на вершины графа}

135. Next: PApexPointer; Apex: РАрех; ArcToApex: РАрех; end;1. POperSet^OperSet;

136. OperSet=object {Множество, хранящее взаимно независимые операторы (ВНО)}erv: integer; {Мощность операций, входящих в ВНО} ApexSet: PApexPointer; ApexSetLast: PApexPointer;

137. ArcsGenerated: boolean; {Сгенерированы варианты дугили еще нет}

138. AV: PArcVariantStore; {Варианты дуг} publicconstructor Create; destructor Destroy;procedure AppendApex(hApex: PApex); function

139. Graf = object {Модель графа программы} Tkr: integer; mintv: integer;

140. ApexSet: PApex; { Совокупность вершин графа} ApexSetLast: PApex;

141. ArcSet: PArcs; { Совокупность дуг графа} ArcSetLast: PArcs;

142. ApexSet :=nil; ApexSetLast :=nil; erv:=0;

143. ArcsGenerated:=faise; AV:=New(PArcVariantStore,Create); end;destructor OperSet.Destroy;var hPApex,hPApex2: PApexPointer; beginhPApex:=ApexSet; while hPApexOnil do begin hPApex2:=hPApex".Next; Dispose(hPApex); hPApex:=hPApex2; end;

144. ApexSet :=nil; ApexSetLast :=nil; erv: = 0;

145. ApexSetLast".Next := hPApexPointer; ApexSetLast := hPApexPointer; end;erv:=erv+hApexA.Energy; end;function

146. OperSet.ControlTime(AVar:iA100;ArcNumber:integer):boolean; va r h PAr c: PAr cVa riant;hPApexOut,hPApexIn: PApexPointer; i,j: integer;beginif ArcNumber>0 then ControlTime:=true else

147. Gk. : =G [ к] -t-1 ; end ;if f then begin1. GenerateArcs:=true;var hPApex,hPApex2: PApex; hPArc, hPArc2: PArcs;begin1. Tkr:=0; mintv:= 0;if SetVNOornl then

148. Dispose(SetVNO,Destroy); hPApex:=ApexSet; while hPApexOnil do begin hPApex2:=hPApexA.Next; Dispose(hPApex); hPApex :=hPApex.2 ; end;hPArc:=ArcSet;while hPArcOnil do begin hPArc2:=hPArcA .Next; Dispose (hPArc:) ; hPArc:=hPArc2; end;

149. AppendArc(GetPApex(hPArcA.OutApex),GetPApex(hPArcA.InApex)); hPArc:=hPArcA.Next; Dispose(hPArc2); end; end;procedure Graf.LoadFromSet(FileName:string); var i: integer; ff: text;hS, hSpl,hSp2,hSp3: String;

150. Val(hSpl, OutArc, Code); if code <> 0 then begin

151. Writeln('Ошибка в позиции выхода дуги: Code); exit ; end;

152. Val(hSp2, InArc, Code); if code <> 0 then begin

153. Writeln('Ошибка в позиции входа дуги: Code); exit ; end;if GetPApex(OutArc)=Nil then

154. AppendApex(OutArc,1,1); if GetPApex(InArc)=Nil then

155. Val(hSpl, NumApex, Code); if code <> 0 then begin

156. Writeln(1 Ошибка в позиции номера вершины: Code); exit ; end;

157. Val(hSp2, WeightApex, Code); if code <> 0 then begin

158. Writeln('Ошибка в позиции веса вершины: Code); exit ; end;

159. Val(hSp3, EnergyApex, Code); if code <> 0 then begin

160. Writeln('Ошибка в позиции мощности вершины: Code); exit; end ;if GetPApex(NumApex)=Nil then

161. AppendApex (NumApex, WeightApex, EnergyApex) else begin

162. GetPApex(NumApex)A.Weight:=WeightApex; GetPApex(NumApex)A.Energy:=EnergyApex; end; end; end; unti1 (hS=''); end;procedure Graf.Copy(Gr:PGraf); var hPApex: PApex; hPArc: PArcs;begi n

163. Tkr:=GrA.Tkr; mintv:=Gr".mintv; hPApex:=Gr A.ApexSet; while hPApexonrl do begrn

164. AppendApex (hPApex74. ID, hPApexA .Weight, hPApex74 .Energy) ; ApexSetLastA. taue : =ЬРАрехл . taue; Арex S e t L a s tл.taul:=hPApexA.tau~l; hPApex:-hPApex".Next; end;h PAr с:=G г л.Ar с S e t; while hPArcOnil do begin

165. SGfO.:=New(PGraf,Create); PrevGr:=SG 0];

166. PrevGrA.LoadFromSet(GrafName); PrevGrA.FindEarlyTimes; PrevGrA.FindLateTimes(Time); PrevGrA.Show; PrevGrA.WriteGraf(ff); n:=PrevGrA.MinProcessors(Time); writeln (n) ;writeln(ff,'Минимальное количество процессоров = T,n); v: = 0 ;г e p e а с

167. PrevGr74.mintv: =PrevGrA . FindMintv (n) ; if PrevGr74 .mintv<=PrevGrA . Tkr then begin writeln ( ff, 'Уровень ',v); if PrevGr74. SetVNO=nil then begin PrevGrA.AcquireSetVNO; PrevGr A . SetVNO74 . Show;

168. PrevGr". SetVNOA .WriteSet (ff) ;if PrevGr'1. SetVNO74. GenerateArcs (n) then begin

169. NoMoreVariants:=false; end. else1. NoMoreVariants:=true;end;if PrevGr'"' . SetVNO-". GetNextArcsVariant (hPArcsByNum) thenbegin

170. NoMo r eVar i an t s:= f a1s e; v: = v+1 ;

171. SGv.:=New(PGraf,Create); Gr:=SG[v];1. GrA.Copy(PrevGr);

172. GrA.AppendSetOfArcs(hPArcsByNum); GrA.FindEarlyTimes; GrA.FindLateTimes(Time); Gr ".Show;

173. GrA.WriteGraf(ff); PrevGr:=Gr; end else

174. NoMoreVariants:=true; if NoMoreVariants then begin if v-0 then begin n:—n+1 ;

175. PrevGrA.FindEarlyTimes; PrevGr'4. FindLateTimes (Time) ; PrevGr".Show; PrevGrA.WriteGraf(ff) ;writeln(ff,'Количество процессоров = ',n); end else beginif SG v. Onil then

176. Dispose(SGv.,Destroy); v:=v-1;

177. SG0. :=New(PGraf,Create) ;1. PrevGr:=SG0.;

178. PrevGrA.LoadFromSet(GrafName);

179. P r e vGrA.FindEarlyTimes;

180. Problem2:=Т0 end else begin v:=0;1. Тга: =Bescon;

181. PrevGrA.FindLateTimes(Tm); repeat

182. NoMoreVariants:=false; end else1. NoMoreVariants:=true;end;if PrevGrA.SetVNOA.GetNextArcsVariant(hPArcsByNum) thenbegin

183. NoMoreVariants:=false; v: =v+1 ;

184. S Gv. :=New(PGraf,Create);1. Gr:=SGv.;1. GrA.Copy(PrevGr);

185. GrA.AppendSetOfArcs(hPArcsByNum); GrA.FindEarlyTimes; GrA.FindLateTimes(Tm); GrA.Show;

186. GrA.WriteGraf(ff); PrevGr:=Gr; end else

187. NoMoreVariants:=true; if NoMoreVariants then begin if v>0 then beginif SG v. Onil then1. Dispose(SGv.,Destroy);

188. PrevGr:=SGv.; end; end; end elserf (v=0) OR (Tm=T0+1) then begin Tm:=SGv.л.Tkr; if SG [ v] Onil then

189. Gr:=New(PGraf,Create); GrA.LoadFromSet('c9c.grf'); Gг/Л . FindEarlyTimes ; GrA . FmdLateTimes (Time) ; Gr'4 . Show;

190. GrA.WriteGraf(ff); writeln(GrA.MinProcessors(Time)); writeln(GrA.MinTime(64)); close(ff); End.

191. Модуль DIS1.PAS Unit disl; interface constsignl 0; vl = 1; sign2 = 2; v2 - 3 ; Q = 4;type

192. AddDescription = array 0.4. of integer; LArray array [0.10000] of integer; PL = '"LArray;1. ConstMatrix = object

193. Ar: array 0 . .19,0.19. of integer; X: integer; Y: integer; publicconstructor Create(FileName: string;1.ra: integer) ;procedure Show; end;

194. PMatrix "Matrix; Matrix = object

195. PRepMatrix = "RepMatrix; RepMatrix = object (Matrix) RX: integer; RY: integer;

196. FreeMem(PAr,(X+l)*(Y+l)*SizeOf(integer)); X : = 0; Y: = 0 ; end; end;procedure Matrix.Load(FileName:string; Dim:integer) var i,j: integer; ff: text; hC: char; hS,hSp: String; hi, Code: integer;

197. Ar: array 0.30, 0.30. of integer;beginif (X<>0) AND (Y<>0) then begin

198. Ar i,j. :=hl; j:=j+l; end; i:=i+l;until hS1.='<'; Y:=i; X:=j; end;close(ff);

199. GetMem(PAr, (X+l) * (Y+l) *SizeOf (integer) ) ; for i:=0 to Y-l do for j:=0 to X-l do

200. PL (PAr)Ai*(X+1)+j. :=Ar[ i, j ] ; for i:=0 to Y-l do

201. PL(PAr)A i* (X+l)+X. : = 0; for j n=0 to X do1. PL(PAr)A(X+l)*Y+j.:=0;end;procedure Matrix.Take(A: ConstMatrix);var i,;j: integer; beginif (X<>0) AND (YO0) then begin

202. FreeMem(PAr,(X+l)*(Y+l)*SizeOf(integer));1. X : = 0 ; Y : = 0 ; end;1. X:=A.X; Y:=A.Y;

203. GetMeni (PAr, (X+l) * (Y+l) *SizeOf (integer) ) ; for 1:^=0 to Y-l dofor j:=0 to X-l do begin

204. PL(PAr)Ai*(X+l)+j.:=A.Ar[i,j]; end;for i:-0 to Y-l do

205. PL(PAr)Ai * (X+1)+X. :=0; for j:=0 to X do1. PL(PAr)AI(X+l)*Y+j.:=0;end;procedure Matrix.KMul(A,B: PMatrix);var i1,12,j1,j2:integer; beginif (XO0) AND (YO0) then begin

206. FreeMem(PAr,(X+l)*(Y+l)*SizeOf(integer));1. X : = 0 ; Y : = 0 ; end;

207. X : =A'" . X * B'"' .X; Y : = A'" . Y*BA . Y;

208. GetMem(PAr,(X+l)*(Y+l)*Size0f(integer)); for j1:= 0 to A".Y-1 do for j 2 : = 0 to BA.Y-l do for il:=0 to A".X-1 do for 12:=0 to BA.X-l do

209. PL(PAr)A (j1*BA.Y+j2)* (X+l) + (il*BA.X+i2) . : =

210. PL(AA.PAr)A j 1*(AA.X+l)+il.*PL (BA.PAr)A[j2*(BA.X+l)+i2]; for il:=0 to Y-l do

211. PL(PAr)Ail*(X+l)+X.: = 0; for j1:=0 to X do

212. PL(PAr) A (X+l)*Y+j1. :=0;end;procedure Matrix.Mui(A,B: PMatrix); var i,j,n:integer; hP: integer;beginif (X<>0) AND (YOG) then begin

213. FreeMem(PAr,(X+l)*(Y+l)*SizeOf(integer));1. X:=0; Y:= 0; end;if A'.XOBXY then begin writein(''); writein('' ) end else begin X:=BA.X; Y:=AA.Y;

214. GetMem(PAr, (X+l)* (Y+l)*SizeOf(integer) ) ; for i:=0 to Y-l dofor j :=0 to X.-1 do begin hD:=0;for n:=0 to AA.X-l dohD:=hD+PL(AA.PAr)Ai* (X+l)+n.*PL(BA.PAr)A[n* (X+l)+j] ; PL(PAr)A[i*(X+l)+3]:=hD; end;for I:= 0 to Y-l do

215. FreeMem(PAr,(X+l)*(Y+l)*SizeOf(integer));1. X : = О ; Y : = О ; end;

216. X:=PA.X+CopylncX; Y : = P . Y ; RX : =P'X .RX; RY:=РЛ.RY;

217. GetMem(PAr, (X+l)* (Y+l)*SizeOf(integer) ) ; for i:=0 to X-l do begin

218. AddWeight 1. :=РЛ .AddWeight i. ; for j:=Û to Y-l do

219. PL(PAr)лj* (X+l)+1. :=PL(Рл.PAr)л[j* (X+1-CopyIncX)+i] ; for i:=Û to 3 do

220. AddDesci,j.:=РЛ.AddDesc[i, j];end;for i:=0 to Y-l do

221. PL (PAr) i* (X+l)+X. : = 0 ; for j:=0 to X do1. PL(PAr)" (X+l)*Y+j. :=0 ;end;procedure RepMatrix.Replacement(DV: AddDescription); var i: integer;mp,mi : integer;beginif DVsign2.=l then begin for i:=0 to Y-l doif

222. ModSign (PL (PAr) л i* (X+l) +DV[vl. ] , PL (PAr) л [i* (X+l) +DV[v2] ] ) =DV[sign 2 j thenif Sign(PL(PAr)Ai*(X+l)+DV[vl.])=1 then begin PL (PAr) 74 [i* (X+l) +X-1] : =1 ;

223. PL(PAr)лi+(X+l)+DV[vl.]:=PL(PAr)л[i*(X+l)+DV[vl]]-1; PL(PAr)л[i*(X+l)+DV[v2]]:=PL(PAr)л[i*(X+l)+DV[v2]]-1; end else begin

224. PL(PAr)лi*(X+l)+X-1. :=-1 ;

225. ModSign(PL(PAr)лi*(X+l)+DV[vl.],PL(PAr)л[i*(X+l)+DV[v2]])=DV[sign 2] then beginif ((Sign(PL(PAr)Ai*(X+l)+DV[vl.])=1) AND (mp>=mi)) OR ( (Sign (PL (PAr) A [i* (X+l). + DV[vl] ] ) =-1) AND (mpCrni)) then PL(PAr)A [i*(X+l)+X-1]:=1else

226. PL(PAr)Ai* (X + l)+X-1. : = -1; if Sign(PL(PAr)A[i*(X+l)+DV[vl]])=1 then begin

227. PL(PAr)Ai*(X+l)+DV[vl.]:=PL(PAr)A[i*(X+l)+DV[vl]]-1; PL(PAr)A[i*(X+l)+DV[v2]]:=PL(PAr)A[i*(X+l)+DV[v2]]+1; end else begin

228. PL(PAr)Ai*(X+l)+DV[vl.]:=PL(PAr)A[i*(X+l)+DV[vl]]+1; PL(PAr)A[i*(X+l)+DV[v2]]:=PL(PAr)A[i*(X+l)+DV[v2]]-1; endend end;if AddWeicjht DV[vl. ] >=AddWeight [DV[v2] ] then

229. AddWeightX.:=AddWeight[DV[vl]]+l else

230. Модуль DIS2.PAS Unit dis2; i n t e r f а с e uses disl; type

231. PAdditionsStore = ЛAdditionsStore; AdditionsStore = object

232. P Add it ionsGen = '"'A.aditionsGen; AdditionsGen = object (AdditionsStore)

233. PM: PRepMatrix; LenPosition: integer; privateprocedure ProcessVariant(n,i,j: integer); publicconstructor Init(P: PRepMatrix); procedure CalcAdditions; function CalcAdditionsMax: integer; prc'cedure Clear;procedure GetNextByLen(var

234. QV1—1,Q.:=QV[1-1,Q]+ 1; if (ms=l) AND (QV[1-1,signl ] <~>Sign (PL (PMA .PAr)A[n*(PMA.X+l)+i])) then QV[1-1,signl]:=0; exi t ; end; end;

235. QVQVDepth, vl. :=i; QV[QVDepth,v2]:=j; QV[QVDepth,sign2]:=ms; QV[QVDepth,Q]:=1; if ms<0 then

236. QVQVDepth,signl.:=0 e ]. s e if ms>0 thenif PL(PMA.PAr)An*(PMA.X+l)+i.>0 then

237. QVQVDepth, s ignl. :=1 else

238. V1.:=QVidx[LenPosition.,i];end;1.n:=LenPosition; end;1. End.

239. Модуль GRAF1.PAS Unit grafl; interfacetypeiAIOO = array 1.100. of integer; iA = array [1.1000] of integer;1. PiA = Л iA;

240. P An: с Va riant = '"ArcVariant; ArcVariant = object

241. ArcsStored: integer; {Количество дуг} Arcs: Pointer; {Указатель на массив номеров выходных и входных вершин дуг}1. Next: PArcVariant; publicconstructor Create(ArcNumber: integer); destructor Destroy; end;

242. PArcVariantStore = AArcVariantStore ; ArcVariantStore = object

243. ArcNumber: integer; {Количество дуг в каждомварианте}

244. CurrentVariant: PArcVariant; ArcVariantSet: PArcVariant; ArcVariantSetLast: PArcVariant; publicconstructor Create; destructor Destroy; procedure

245. AppendArcVariant(AVar:iAl00;ArcNumber: integer) ; {Добавить сгенерированный вариант в хранилище}function GetNextVariant(var AVar:iAIOO; var ArcNumber:integer) : boolean;

246. GetMem(Arcs,ArcNumber*2*Size0f(integer)); for i:=l to ArcNumber*2 do

247. Pi A(Arcs)"1. := 0; Ar c s S t o r e d:=ArcNumb e r; Next:=nil; end ;destructor ArcVariant.Destroy; begin

248. FreeMem(Arcs,ArcsStored*2*Size0f(integer)); ArcsStor ed:=0; end;constructor ArcVariantStore.Create; begin1. ArcNumber:=0; }1. CurrentVariant:=nil;

249. ArcVar rantSet-Last: =nil ; e;id;destructor ArcVariantStore.Destroy;var hPArc,hPArc2: PArcVariant; beg inhPA r c:^Ar cVa r i an t S e t; while hPArcOnil do begin hPA.rc.2 : -hPArcA . Next ; Dispose (hPArc, Destroy) ; hPArc:=hPArc2; end;

250. CurrentVariant:=ni1 ; Ar cVarrantSet :=nil; Z'vrcVar iantSetLast : =nil ; I Ar'cNumber:= 0 ; } end ;procedure

251. Ar c v a r l an t S tore.AppendArcVariant(AVar:iAl00;ArcNumber:integer); var hPArc: PArcVariant; 1: integer;b e g i niiPArc : = New (PArcVariant, Create (ArcNumber) ) ; for i:=.l to ArcNumber*2 do

252. PiA(hPArcA.Arcs)A1.:= AVar i . ; hPArcA .A^rcsStored := ArcNumber; hPAr c A.Next := Nil;if ArcVariantSetLast=Nil then begin ArcVariantSetLast :=hPArc; ArcVariantSet :=hPArc; CurrentVariant :=hPArc; end else begin

253. AVar1.:= PiA(CurrentVariant".Arcs)Ai.; ArcNumber:=CurrentVariantA.ArcsStored; CurrentVariant:=CurrentVariantA.Next; GetNextVariant:=true; end else

254. GetNextVariant:=false; end;procedure ArcVariantStore.Reset; begin