Реконфигурируемый мультипроцессор для реализации модифицированных алгоритмов обработки сигналов
Диссертация
Практическая ценность работы заключается в разработке набора алгоритмов для автоматизации процесса планирования параллельного выполнения алгоритмов Винограда вычисления свертки и ДПФ, и разработке ряда инженерно-технических решений, позволяющих на алгоритмическом и аппаратном уровне повысить скорость выполнения указанных алгоритмов. При этом мультипроцессор, архитектура которого основана… Читать ещё >
Список литературы
- ппенгейм А., Шафер Р. Цифровая обработка сигналов. -М.: Связь, 1979, 416с.
- Инвестиции фирмы Texas Instruments в новые разработки на сигнальных процессорах. // Электронные компоненты и системы. 19 98. № 4, С.12
- Рабинер JI.P., Гоулд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978, — 848с.
- Вайрадян А.С., Пчелинцев И. П., Челышев М. Н. Алгоритмы вычисления цифровых сверток. // Зарубежн. радиоэлектрон. 1982. № 3, с.3−34.
- Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989, — 448с.
- Быстрые алгоритмы в цифровой обработке изображений / Т. С. Хуанг, Дж.-О. Эклунд, Г. Дж. Нуссбаумер и др.- под ред. Т. С. Хуанга. М.: Радио и связь, 1984.
- Agarwal R.C., and Cooley J.W., New Algorithms for Digital Convolution // IEEE Trans. Acoust., Speech, Signal Proc. ASSP-25 (1977): 392−410.
- Даджион Д. л Мерсеро Р. Цифровая обработка многомерных сигналов. М.: Мир, 1988.
- Nussbaumer Н. J., Digital Filtering Using Polynomial Transforms // Electron. Lett. 13 (1977): 386−387.
- Winograd S., On Computing the Discrete Fourier Transform // Math. Сотр., 32 (1978): 175−199.
- Winograd S., On Computing the Discrete Fourier Transform // Proc. Nat. Acad. Sci. USA, 73 (1976): 10 051 006.
- 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.
- Ахмед H., Pao K.P. Ортогональные преобразования для цифровой обработки сигналов. М.: Радио и связь, 1980,
- Г/.Дагман Э. Е., Кухарев Г. А. Быстрые дискретные ортогональные преобразования. Новосибирск: Наука, 1983,232с.
- Гагарин Ю.И. Псевдогнездовые алгоритмы двумерного косинусного преобразования // Электронное моделирование. Киев, 19 91. № 2, с. 107.
- Брайсуэлл Р.Н. Быстрое преобразование Хартли. // ТИИЭР 1984. т.72, № 8 с.19−27.
- Гагарин Ю.И., Гагарин К. Ю., Козлов В. Р. Быстрые алгоритмы теоретико-числовых преобразований Мерсенна // Логическое управление с использованием ЭВМ. Труды 13 Всесоюзного симпозиума. Москва: 19 90, 20с.
- Солодовников А.И., Спиваковский A.M. Основы теории и методы спектральной обработки информации. JI.: Изд. ЛГУ, 1986. — 270с.
- Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. -17 6с.
- Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции. М.: Наука, 1981. — 254с.
- Параллельные вычисления / под ред.Г. Родрига. М.: Наука, 1986. — 372с.
- Карцев М.А. Архитектура цифровых вычислительных машин. М.: Наука, 1978. 296с.
- Майерс, Гленфорд. Архитектура современных ЭВМ. В 2-х кн. М.: Мир, 1985.
- Самофалов К.Г., Луцкий Г. М. Основы теории многоуровневых конвейерных вычислительных систем. М.: Радио и связь, 1989. — 272с.
- Мультипроцессорные системы и параллельные вычисления / под ред. Ф. Г. Энслоу М.: Мир, 1976. — 383с.
- Бессалах X., Луцкий Г. М. Алгоритмы быстрого преобразования Фурье и их реализация на рекурсивных конвейерных процессорах // Вестн. КПИ. Сер. автоматики и электроприборостроения. 1981. -№ 18. — с.55−59.
- Мясников В.А., Игнатьев М. Б., Шейнин Ю. Е. Архитектура модульной многомикропроцессорной вычислительной системы // Кибернетика 1984. — № 3. — с.46−53.3 6. Системы параллельной обработки / под ред. Д. Ивенса,
- М.: Мир, 1985. 413с. 37 .Кун С. Матричные процессоры на СБИС. — М.: Мир, 1991.
- Цифровые сигнальные процессоры. Кн.1 / Марков С. М.: Микроарт, 1996.
- Ерофеев А,.А. Сигнальные процессоры. М.: Знание, 1991. 63с.
- ADSP 21xx Family Manual. Analog Devices, Inc., 19 95.
- 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.
- TMS320C62xx. Technical Brief. Texas Instruments, Inc., January 1997.
- ЗО.Кухарев Г. А. Систолические процессоры для обработки сигналов. Минск: Беларусь, 1988. 127с.
- Rader, С.М., and N.M. Brenner, A new Principle for Fast Fourier Transformation, IEEE Trans. Acoust., Speech, Signal .Proc. ASSP-24 (1976): 264−265.
- Bluestein, L.I., A Linear Filtering Approach to the Computation of the Discrete Fourier Transform, IEEE Trans. Audio Electroacoust. AU-18 (1970): 451−455.
- Evader C.M., Discrete Fourier Transforms When the Number of Data Samples Is Prime, Proc. IEEE 56 (1968): 1107−1108.
- Селезнев M.E. К вопросу о создании технических средств обработки сигналов. // Сборник материалов 3 международной конференции «Распознавание-97″. Курск, гос. техн. ун-т. Курск, 1997. С. 214.
- Селезнев М.Е. Архитектура высокопроизводительного сигнального мультипроцессора. // Сборник материалов 4 международной конференции „Распознавание-99″. Курск, гос. техн. ун-т. Курск, 1999. С. 73.
- Заявка о выдаче патента Российской Федерации на изобретение № 99 109 904, приоритет от 05.05.99 г. // „Рекон-фигурируемый асинхронный сумматор-умножитель“, Довгалв В. М., Селезнев М. Е., Старков Ф. А., Титов B.C.
- Селезнев М.Е. К вопросу о создании высокопроизводительных устройств обработки и передачи цифровой информации. // Труды всероссийской конференции „Интеллектуальные информационные системы“. Воронежский гос. техн. ун-т. Воронеж, 1999. С. 186−187.
- К вопросу о минимизации числа сложений в алгоритмах вычисления свертки и ДПФ / М.Е. Селезнев- Курск, гос.техн. ун-т. Курск, 1999. 9с.: Библиогр. 5 назв. Рус. Деп. в ВИНИТИ 03.12.99 № 3 610-В99.
- Планирование параллельной реализации алгоритмов Винограда вычисления свертки и ДПФ / Курск, гос. техн. унт. Курск, 1999. 29с.: ил. Библиогр. 10 назв. Рус. Деп. в ВИНИТИ 28.12.99 № 3862-В99.
- Реконфигурируемый сигнальный мультипроцессор / Курск, гос. техн. ун-т. Курск, 1999. 21с.: ил. Библиогр. 8 назв. Рус. Деп. в ВИНИТИ 28.12.99 № 38 63-В99.
- Айэрленд К., Роузен Н. Классическое введение в современную теорию чисел. М.: Мир, 1987. 415с.65.Ä-XO А., Хопкрофт Дж., Улвман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. — 536с.
- Барский A.B. Планирование параллелвных вычислительных процессов. М.: Машиностроение, 1980. — 191с.
- Бахтеяров C.B. Транспьютерная технология. М.: Радио и связо, 1993. 302с.
- Белый A.A., Бовбель Б. И., Микулович В. И. Алгоритмы быстрого преобразования Фурве и их свойства. // Зарубежн. радиоэлектрон. 1979. № 2 с.3−29.
- Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. — 57 6с.
- Власенко В.А., Лаппа Ю. М. Матричный подход к построению быстрых алгоритмов многомерного дискретного преобразования Фурье. // Изв. вузов. Радиоэлектроника. 1986. т. 29. № 1 с. 8 6−8 9.
- Калабеков Б.А. Микропроцессоры и их применение в система?: обработки и передачи сигналов. М.: Радио и связв, 1988. 368с.
- Корнеев В.В., Киселев A.B. Современные микропроцессоры. М.: Нолидж, 1998. 231с.
- Кумаресан Р., Гупта П. К. Алгоритм БПФ для простых множителей на основе арифметики действительных чисел. // ТИИЭР 1985, т.73 № 7 с.98−100.
- Маклеллан Дж.Х., Рейдер Ч. М. Применение теории -чисел в цифровой обработке сигналов. М.: Радио и связь, 1983. — 264с.
- Матричная интерпретация и вычислительная эффективноств алгоритмов БПФ. // РЭ. 198 4 т.29, № 2 с. 2 65−274.
- Рабинер Л.Р., Шафер Р. В. Цифровая обработка речевых сигналов. М.: Радио и связь, 1981. — 496с.7 9. Уэйзер Л. Быстродействующий цифровой умножитель для обработки сигналов в реальном времени // Электроника. -1977. № 20. — с.40−49.
- O.Xoap Ч. Взаимодействующие последовательные процессы. -М.: Мир, 1989. 264с.
- Цифровая обработка сигналов и ее применения. Сб. статей под ред. Л. П. Ярославского. — М.: Наука, 1981. -222с.82:.ГОэн 11. Микропроцессорные системы и их применение при обработке сигналов. М.: Радио и связв, 1988.167
- FPGA Adders: Performance Evaluation and Optimal Design / Xing Shanzhen // IEEE Des. And Test Comput. 15 (1998) № 1: 24−29.
- VLIW Architecture offers a Ten-Fold Improvement in Digital Signal Processing / Bursky D. // Electron. Des. 4 5 (1997) № 5: 52. end- begin
- PAS:=New (PAdditionsStore, Init) — PRM1.:=New (PRepMatrix, Create) — PRM1.A.Load ('dftci.dat', 9) — PRM1.A.Show- PRM[1]A.WriteFiff) — i: = 1-
- 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
- Program Graf- uses crt, graf1−1. Ачрех-
- Arcs- object {Дуга графа} OutApex: PApex- I n Ар e x: P Ар e x — Next: PArcs- end-1. PArcsByNum = AArcsByNum-
- ArcsByNum = object {Дуга графа по номерам вершин} OutApex: integer- InApex: integer- N e x t: PAr с s В у Num. -end-
- PApexPointer=AApexPointer-
- ApexPointer = object {Элемент списка указателей на вершины графа}
- Next: PApexPointer — Apex: РАрех- ArcToApex: РАрех- end-1. POperSet=/4OperSet —
- OperSet=object {Множество, хранящее взаимно независимые операторы (ВНО)}rv: integer,“ {Число операций, входящих в ВНО} ApexSet: PApexPointer- ApexSetLast: PApexPointer-
- ArcsGenerated: boolean- {Сгенерированы варианты дугили еще нет}
- AV: PArcVariantStore- {Варианты дуг} publicconstructor Create- destructor Destroy-procedure AppendApex (hApex: PApex) — function
- Graf = object {Модель графа программы} Tkr: integer- iruntv: integer-
- ApexSet: PApex- { Совокупность вершин графа} ApexSetLast: PApex-
- ArcSet: PArcs- { Совокупность дуг графа} ArcSetLast: PArcs-
- Gr1: PGraf- Time: integer-
- ApexSet :=nil- ApexSetLast: r-=nil- rv:=0-
- 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-
- ApexSet :=nil- ApexSetLast :=nil- rv:=0-
- ApexSetLastA.Next := hPApexPointer- ApexSetLast := hPApexPointer- end-rv:=rv+1- end-function
- OperSet.ControlTime (AVar:iAl00-ArcNumber:integer):boolean- var hPArc: PArcVariant-hPApexOut, hPApexIn: PApexPointer- i, j: integer-beginif ArcNumber>0 then ControlTime:=true else
- GenerateArcs:=true- ArcsGenerated:=true end else
- GenerateArcs:=false- AVA. WriteVariants (ff) — end-function OperSet. GetNextArcsVariant (var hPAxcs: PArcsByNum):boolean- var G: iAl00-
- GetNextArcsVariant:=true- end else
- GetNextArcsVariant:=false-end-constructor Graf. Create- begin
- Tkr:=0- mintv:=0- ApexSet :=nil-
- 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
- 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-
- 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-
- Val (hSpl, OutArc, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции выхода дуги: Code) — exit — end-
- Val (hSp2, InArc, Code) — if code <> 0 then begin
- Wri teln ('Ошибка в позиции входа дуги: Code)-exit — end-if GetPApex (OutArc)=Nil then
- AppendApex (OutArc, 1) — if GetPApex (InArc)=Nil then
- Val (hSpl, NumApex, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции номера вершины: Code) — exit- end-
- Val (hSp2, WeightApex, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции веса вершины: Code) — exit- end -if GetPApex (NumApex)-Nil then
- AppericiApex (NumApex, Weight Apex) else
- 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
- Tkr:=GrA.Tkr- mintv:=GrA.min t v- h PAp ex: =Gr A. ApexSet. — while hPApexOnxi do begin
- 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
- 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-
- 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
- SG0 j :=New (PGraf, Create) — PrevGr:-SG [ 0.-
- PrevGr. LoadFromSet (GrafName) -1. PrevGr».FindEarlyTimes-
- PrevGr".FindLateTimes (Time)-1. PrevGr ". Shovvr-
- Pre vG i"" .WriteGraf (f f) -n:=PrevGr".MinProcessors (Time)-writein (n)-writelij (ff, 'Минимальное количество процессоров = ', n)-v: = 0 -repeat
- NoMoreVariants:=false- end else1. NoMoreVariants:=true-end-if PrevGr".SetVNO".GetNextArcsVariant (hPArcsByNum) thenbegin
- NoMoreVariants:=false — v:—vf1-
- SGvj :=New (PGraf, Create) — G r: = S G [ v. -1. Gr А. Copy (PrevGr) —
- Gr A. AppendSetOfArcs (hPArcsByNum) — GrA. FindEarlyTimes — GrA. FindLateTimes (Time) — Gr A. Show-
- GrA.WriteGraf (ff) — PrevGr:=Gr- end else
- NoMoreVariants:-true- if NoMoreVariants then begin if v^O then begin n:-?1+1-
- PrevGr'"4. FindEarlyTimes- PrevGr74. FindLateTimes (Time) — PrevGrA. Show- PrevGr-" .WriteGraf iff) -writeln (ff, 'Количество процессоров = ', n) — end else beginif SG v. onil then
- Dispose (SGv., Destroy) — v:=v-1 —
- Pre"GrЛ.LoadFromSet (GrafName) —
- PrevGr '"'. EnndEarlyTimes —
- PrevGr''4. FindLateTimes (PrevGrA. Tkr) -r'revGr '. Show-
- РгоЫеш2: =Т0 end else begin v: ~ 0 -1. Tm:^Bescon-
- PrevGrА.FindLateTimes™ — repeat
- NoMoreVariants:=false- end. else1. NoMoreVariants:=true-end-if PrevGrA.SetVNOA.GetNextArcsVariant (hPArcsByNum) thenb e g i n
- NoMo r eVa r i a n t s:= f a1s e- v:=v+1-
- S Gv. :-New (PGraf, Create)-1. Gr:=SGv.-1. GrA. Copy (PrevGr) —
- GrA.AppendSetOfArcs (hPArcsByNum) — GrA. FindEarlyTimes- GrA. FindLateTimes™ — GrA. Show-
- GrA.WriteGraf (ff) — PrevGr:=Gr- end else
- NoMoreVariants:=true- if NoMoreVariants then begin if v>0 then begin if SGv. onil then
- Dispose (SGv., Destroy) — v:=v-l-
- P г о g ram G r a fMo d i f у- uses crt, grafl-type
- P Ар e x = «Ар e x — PArcs = „Arcs- Arcs = object {Дуга графа} Ou tАр e x: PАр e x- InApex: PApex- Next: PArcs- end-1. PArcsByNum = '^ArcsByNum-
- Ar-csByNum = object {Дуга графа по номерам вершин} OutApex: integer- InApex: integer- Next: PAr с s В yNum- end-
- Apex = object {Вершина графа} ID: integer-
- Weight: integer- {Вес вершины} Energy: integer- {Мощность вершины} taue: integer- {Раннее время выполнения} taul: integer- {Позднее время выполнения} Next: PApex- processed: boolean- TTkr: integer- {T-Tkr} publicfunction IsCritical? boolean- end-
- PApexPointer-AApexPointer-
- ApexPointer = object {Элемент списка указателей на вершины графа}
- Next: PApexPointer- Apex: РАрех- ArcToApex: РАрех- end-1. POperSet^OperSet-
- OperSet=object {Множество, хранящее взаимно независимые операторы (ВНО)}erv: integer- {Мощность операций, входящих в ВНО} ApexSet: PApexPointer- ApexSetLast: PApexPointer-
- ArcsGenerated: boolean- {Сгенерированы варианты дугили еще нет}
- AV: PArcVariantStore- {Варианты дуг} publicconstructor Create- destructor Destroy-procedure AppendApex (hApex: PApex) — function
- Graf = object {Модель графа программы} Tkr: integer- mintv: integer-
- ApexSet: PApex- { Совокупность вершин графа} ApexSetLast: PApex-
- ArcSet: PArcs- { Совокупность дуг графа} ArcSetLast: PArcs-
- ApexSet :=nil- ApexSetLast :=nil- erv:=0-
- 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-
- ApexSet :=nil- ApexSetLast :=nil- erv: = 0-
- ApexSetLast».Next := hPApexPointer- ApexSetLast := hPApexPointer- end-erv:=erv+hApexA.Energy- end-function
- 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
- 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
- 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-
- 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-
- Val (hSpl, OutArc, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции выхода дуги: Code) — exit — end-
- Val (hSp2, InArc, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции входа дуги: Code) — exit — end-if GetPApex (OutArc)=Nil then
- AppendApex (OutArc, 1,1) — if GetPApex (InArc)=Nil then
- Val (hSpl, NumApex, Code) — if code <> 0 then begin
- Writeln (1 Ошибка в позиции номера вершины: Code) — exit — end-
- Val (hSp2, WeightApex, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции веса вершины: Code) — exit — end-
- Val (hSp3, EnergyApex, Code) — if code <> 0 then begin
- Writeln ('Ошибка в позиции мощности вершины: Code) — exit- end -if GetPApex (NumApex)=Nil then
- AppendApex (NumApex, WeightApex, EnergyApex) else begin
- 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
- Tkr:=GrA.Tkr- mintv:=Gr".mintv- hPApex:=Gr A. ApexSet- while hPApexonrl do begrn
- 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
- SGfO.:=New (PGraf, Create) — PrevGr:=SG 0]-
- 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, а с
- 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-
- PrevGr". SetVNOA. WriteSet (ff) -if PrevGr'1. SetVNO74. GenerateArcs (n) then begin
- NoMoreVariants:=false- end. else1. NoMoreVariants:=true-end-if PrevGr'"'. SetVNO-«. GetNextArcsVariant (hPArcsByNum) thenbegin
- NoMo r eVar i an t s:= f a1s e- v: = v+1 —
- SGv.:=New (PGraf, Create) — Gr:=SG[v]-1. GrA. Copy (PrevGr) —
- GrA.AppendSetOfArcs (hPArcsByNum) — GrA. FindEarlyTimes- GrA. FindLateTimes (Time) — Gr „.Show-
- GrA.WriteGraf (ff) — PrevGr:=Gr- end else
- NoMoreVariants:=true- if NoMoreVariants then begin if v-0 then begin n:—n+1 —
- PrevGrA.FindEarlyTimes- PrevGr'4. FindLateTimes (Time) — PrevGr“.Show- PrevGrA. WriteGraf (ff) -writeln (ff,'Количество процессоров = ', n) — end else beginif SG v. Onil then
- Dispose (SGv., Destroy) — v:=v-1-
- SG0. :=New (PGraf, Create) -1. PrevGr:=SG0.-
- PrevGrA.LoadFromSet (GrafName) —
- P r e vGrA. FindEarlyTimes-
- Problem2:=Т0 end else begin v:=0−1. Тга: =Bescon-
- PrevGrA.FindLateTimes™ — repeat
- NoMoreVariants:=false- end else1. NoMoreVariants:=true-end-if PrevGrA.SetVNOA.GetNextArcsVariant (hPArcsByNum) thenbegin
- NoMoreVariants:=false- v: =v+1 —
- S Gv. :=New (PGraf, Create)-1. Gr:=SGv.-1. GrA. Copy (PrevGr) —
- GrA.AppendSetOfArcs (hPArcsByNum) — GrA. FindEarlyTimes- GrA. FindLateTimes™ — GrA. Show-
- GrA.WriteGraf (ff) — PrevGr:=Gr- end else
- NoMoreVariants:=true- if NoMoreVariants then begin if v>0 then beginif SG v. Onil then1. Dispose (SGv., Destroy) —
- PrevGr:=SGv.- end- end- end elserf (v=0) OR (Tm=T0+1) then begin Tm:=SGv.л.Tkr- if SG [ v] Onil then
- Gr:=New (PGraf, Create) — GrA. LoadFromSet ('c9c.grf') — Gг/Л. FindEarlyTimes — GrA. FmdLateTimes (Time) — Gr'4. Show-
- GrA.WriteGraf (ff) — writeln (GrA.MinProcessors (Time)) — writeln (GrA.MinTime (64)) — close (ff) — End.
- Модуль DIS1. PAS Unit disl- interface constsignl 0- vl = 1- sign2 = 2- v2 — 3 — Q = 4-type
- AddDescription = array 0.4. of integer- LArray array [0.10 000] of integer- PL = '"LArray-1. ConstMatrix = object
- Ar: array 0. .19,0.19. of integer- X: integer- Y: integer- publicconstructor Create (FileName: string-1.ra: integer) -procedure Show- end-
- PMatrix „Matrix- Matrix = object
- PRepMatrix = „RepMatrix- RepMatrix = object (Matrix) RX: integer- RY: integer-
- 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-
- Ar: array 0.30, 0.30. of integer-beginif (X<>0) AND (Y<>0) then begin
- Ar i, j. :=hl- j:=j+l- end- i:=i+l-until hS1.='<'- Y:=i- X:=j- end-close (ff) —
- GetMem (PAr, (X+l) * (Y+l) *SizeOf (integer)) — for i:=0 to Y-l do for j:=0 to X-l do
- PL (PAr)Ai*(X+1)+j. :=Ar[ i, j ] - for i:=0 to Y-l do
- 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
- FreeMem (PAr,(X+l)*(Y+l)*SizeOf (integer))-1. X: = 0 — Y: = 0 — end-1. X:=A.X- Y:=A.Y-
- GetMeni (PAr, (X+l) * (Y+l) *SizeOf (integer)) — for 1:^=0 to Y-l dofor j:=0 to X-l do begin
- PL (PAr)Ai*(X+l)+j.:=A.Ar[i, j]- end-for i:-0 to Y-l do
- 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
- FreeMem (PAr,(X+l)*(Y+l)*SizeOf (integer))-1. X: = 0 — Y: = 0 — end-
- X: =A'“. X * B'"' .X- Y: = A'“. Y*BA. Y-
- 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
- PL (PAr)A (j1*BA.Y+j2)* (X+l) + (il*BA.X+i2).: =
- 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
- PL (PAr)Ail*(X+l)+X.: = 0- for j1:=0 to X do
- 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
- 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-
- 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
- FreeMem (PAr,(X+l)*(Y+l)*SizeOf (integer))-1. X: = О — Y: = О — end-
- X:=PA.X+CopylncX- Y: = P. Y — RX: =P'X .RX- RY:=РЛ.RY-
- GetMem (PAr, (X+l)* (Y+l)*SizeOf (integer)) — for i:=0 to X-l do begin
- AddWeight 1. :=РЛ .AddWeight i. — for j:=U to Y-l do
- PL (PAr)лj* (X+l)+1. :=PL (Рл.PAr)л[j* (X+1-CopyIncX)+i] - for i:=U to 3 do
- AddDesci, j.:=РЛ.AddDesc[i, j]-end-for i:=0 to Y-l do
- 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
- 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 —
- 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
- PL (PAr)лi*(X+l)+X-1. :=-1 —
- 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
- PL (PAr)Ai* (X + l)+X-1.: = -1- if Sign (PL (PAr)A[i*(X+l)+DV[vl]])=1 then begin
- 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
- 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
- AddWeightX.:=AddWeight[DV[vl]]+l else
- Модуль DIS2. PAS Unit dis2- i n t e r f, а с e uses disl- type
- PAdditionsStore = ЛAdditionsStore- AdditionsStore = object
- P Add it ionsGen = '"'A.aditionsGen- AdditionsGen = object (AdditionsStore)
- 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
- 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-
- QVQVDepth, vl. :=i- QV[QVDepth, v2]: =j- QV[QVDepth, sign2]: =ms- QV[QVDepth, Q]: =1- if ms<0 then
- QVQVDepth, signl.:=0 e ]. s e if ms>0 thenif PL (PMA.PAr)An*(PMA.X+l)+i.>0 then
- QVQVDepth, s ignl. :=1 else
- V1.:=QVidx[LenPosition., i]-end-1.n:=LenPosition- end-1. End.
- Модуль GRAF1. PAS Unit grafl- interfacetypeiAIOO = array 1.100. of integer- iA = array [1.1000] of integer-1. PiA = Л iA-
- P An: с Va riant = '"ArcVariant- ArcVariant = object
- ArcsStored: integer- {Количество дуг} Arcs: Pointer- {Указатель на массив номеров выходных и входных вершин дуг}1. Next: PArcVariant- publicconstructor Create (ArcNumber: integer) — destructor Destroy- end-
- PArcVariantStore = AArcVariantStore — ArcVariantStore = object
- ArcNumber: integer- {Количество дуг в каждомварианте}
- CurrentVariant: PArcVariant- ArcVariantSet: PArcVariant- ArcVariantSetLast: PArcVariant- publicconstructor Create- destructor Destroy- procedure
- AppendArcVariant (AVar:iAl00-ArcNumber: integer) — {Добавить сгенерированный вариант в хранилище}function GetNextVariant (var AVar: iAIOO- var ArcNumber: integer): boolean-
- GetMem (Arcs, ArcNumber*2*Size0f (integer)) — for i:=l to ArcNumber*2 do
- Pi A (Arcs)"1. := 0- Ar c s S t o r e d:=ArcNumb e r- Next:=nil- end -destructor ArcVariant. Destroy- begin
- FreeMem (Arcs, ArcsStored*2*Size0f (integer)) — ArcsStor ed:=0- end-constructor ArcVariantStore. Create- begin1. ArcNumber:=0- }1. CurrentVariant:=nil-
- 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-
- CurrentVariant:=ni1 — Ar cVarrantSet :=nil- Z’vrcVar iantSetLast: =nil — I Ar’cNumber:= 0 — } end -procedure
- 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
- 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
- AVar1.:= PiA (CurrentVariant".Arcs)Ai.- ArcNumber:=CurrentVariantA.ArcsStored- CurrentVariant:=CurrentVariantA.Next- GetNextVariant:=true- end else
- GetNextVariant:=false- end-procedure ArcVariantStore. Reset- begin