УСТРОЙСТВО ДЛЯ ПОИСКА ЛИНЕЙНЫХ УЧАСТКОВ ВНУТРИ ЦИКЛА

Полезная модель относится к области цифровой вычислительной техники и предназначено для поиска линейных участков внутри циклов для их последующего распараллеливания.
Известен элемент однородной среды, включающий блок обработки входных сигналов, блок запоминания признака конечной точки, блок выходной логики, триггер записи трасс, блок оценки текущего размещения, блок передачи информации, входы, выходы, управляющий вход, информационные входы, информационные выходы, индикаторный выход (а.с. 1291957 СССР кл. G06F 7/00, опубл. 23.02.87, БИ №7).
Недостатком указанного элемента является узкая область применения, обусловленная отсутствием средств для поиска и распараллеливания линейных участков внутри циклов.
Наиболее близким к предлагаемому устройству по технической сущности является устройство для оценки размещения элементов, содержащее матрицу элементов однородной среды, состоящую из элементов однородной среды, блоки подсчета единиц, блок нахождения максимума, первый сумматор, блок памяти, вход записи исходного гиперграфа, вход управления перестановкой столбцов, вход управления перестановкой строк, вход управления записью в блок памяти, выходы оценки текущего размещения, информационный выход и вход установки (а.с. 1430949 СССР, кл. G06F 7/00, 15/20, опубл. 15.10.88, БИ №38).
Недостатком указанного устройства является узкая область применения, обусловленная отсутствием средств для поиска и распараллеливания линейных участков внутри циклов.
Технической задачей полезной модели является распараллеливание циклических участков последовательных программ за счет выделения и распараллеливания независимых линейных участков.
Техническая задача решается тем, что в устройство для оценки размещения по критериям суммарной длины ребер и максимальной длины ребра, содержащее матрицу из m строк и n столбцов элементов однородной среды, первый блок нахождения максимума, сумматор, блок памяти, n блоков подсчета единиц, причем входы управления перестановкой столбцов матрицы элементов однородной среды соединены с входом управления перестановкой столбцов устройства, входы управления перестановкой строк матрицы элементов однородной среды соединены с входом управления перестановкой строк устройства, входы установки матрицы элементов однородной среды соединены с входом установки устройства, информационные входы матрицы элементов однородной среды соединены с входом записи матрицы электрических цепей устройства, индикаторные выходы элементов j-го столбца (j=1,2, n) матрицы элементов однородной среды соединены с входом j-го блока подсчета единиц, выход которого соединен с j-м входом первого блока нахождения максимума и j-м входом сумматора, выходы которых соединены с выходами максимальной длины ребра и суммарной длины ребер устройства соответственно, вход управления записью блока памяти соединен с входом управления записью устройства, информационные выходы элементов i-й строки (i=1, 2, …, M) матрицы элементов однородной среды соединены с i-м информационным входом блока памяти, выход которого соединен с информационным выходом устройства, дополнительно введен блок поиска линейных участков, содержащий матрицу из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, тактовый генератор, счетчик импульсов стробирования загрузки исходных данных, первый дешифратор номера строба, два счетчика и два дешифратора для формирования эталонных значений строк/столбцов, счетчик операторов, дешифратор номера обрабатываемой строки/столбца, счетчик найденных линейных участков, первое однопортовое оперативное запоминающее устройство (ОЗУ) обработки строк, второе однопортовое ОЗУ обработки столбцов, два компаратора эталонных значений строк/столбцов с реальными значениями строк/столбцов, три элемента И, два счетчика для хранения текущих границ найденного линейного участка, компаратор для формирования сигнала готовности выходных данных, третье однопортовое ОЗУ хранения границ найденных линейных участков, причем информационные входы матрицы из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с соответствующими выходами матрицы элементов однородной среды, на синхровходы матрицы из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных подается сигнал со входа управления записью устройства, на вход тактового генератора подаются сигналы со входов подачи “питания” и подачи “земли”, выход тактового генератора соединен с входами подачи частоты трех однопортовых ОЗУ, счетчика номера обрабатываемой строки/столбца, счетчика найденных линейных участков, счетчиков текущих границ найденного линейного участка, вход CLK счетчика импульсов стробирования загрузки исходных данных соединен с входом управления записью устройства, первый выход дешифратора номера строба соединен с входом CLK счетчика эталонного значения строки и входом разрешения записи первого однопортового ОЗУ, второй выход дешифратора номера строба соединен с входом CLK счетчика эталонного значения столбца и входом разрешения записи второго однопортового ОЗУ, третий выход дешифратора номера строба соединен с входами стробирования компараторов эталонных значений строк/столбцов с реальными значениями строк/столбцов, четвертый выход дешифратора номера строба соединен с вторым входом третьего элемента И, выход счетчика эталонного значения строки соединен с входом дешифратора эталонного значения строки, выход счетчика эталонного значения столбца соединен с входом дешифратора эталонного значения столбца, выход счетчика номера обрабатываемой строки/столбца соединен с входом дешифратора формирования разрешающего сигнала загрузки строки/столбца из матрицы D триггеров, входами установки счетчиков границ найденных линейных участков и входом компаратора формирования сигнала готовности выходных данных, выход счетчика найденных линейных участков соединен с адресным входом третьего однопортового ОЗУ хранения границ найденных линейных участков, выход дешифратора эталонного значения строки соединен с вторым входом компаратора эталонного значения строки с реальным значением строки, выход дешифратора эталонного значения столбца соединен с вторым входом компаратора эталонного значения столбца с реальным значением столбца, информационные входы первого и второго однопортового ОЗУ соединены с матрицей D триггеров таким образом, что в первое однопортовое ОЗУ загружаются значения строк матрицы D триггеров, а во второе однопортовое ОЗУ загружаются значения столбцов матрицы D триггеров, выход первого однопортового ОЗУ соединен с первым входом компаратора эталонного значения строки с реальным значением строки, выход второго однопортового ОЗУ соединен с первым входом компаратора эталонного значения столбца с реальным значением столбца, прямой выход компаратора эталонного значения строки с реальным значением строки соединен с первым входом первого элемента И, инверсный выход компаратора эталонного значения строки с реальным значением строки соединен с первым входом второго элемента И, прямой выход компаратора эталонного значения столбца с реальным значением столбца соединен со вторым входом первого элемента И, инверсный выход компаратора эталонного значения столбца с реальным значением столбца соединен со вторым входом второго элемента И, выход первого элемента И соединен с входом счетчика второй границы найденного линейного участка, выход второго элемента И соединен с первым входом третьего элемента И, входом разрешения записи третьего однопортового ОЗУ, и входом счетчика найденных линейных участков, выход третьего элемента И соединен с входом разрешения установки значения в счетчики границ найденного линейного участка, выход счетчика первой границы найденного линейного участка соединен со старшей половиной информационных входов третьего однопортового ОЗУ, выход счетчика второй границы найденного линейного участка соединен с младшей половиной информационных входов третьего однопортового ОЗУ, выходы третьего однопортового ОЗУ соединены с выходами S1 и S2 устройства, выход компаратора формирования сигнала готовности выходных данных соединен с выходом RDY устройства, вход разрешения записи третьего однопортового ОЗУ соединен с входом RW устройства, второй вход компаратора формирования сигнала готовности устройства соединен с входом N устройства.
Сущность полезной модели поясняется чертежами, где на фиг. 1 изображена функциональная схема устройства для поиска линейных участков внутри циклов.
Предлагаемое устройство может использоваться в области проектирования вычислительных систем (ВС), например, при проектировании и эксплуатации многопроцессорных систем, для функционирования которых требуются специализированные параллельные программы.
В ВС исходный (распараллеливаемый) фрагмент программы задается в следующем виде:
1. Исходный текст программы (фиг. 2а);
i
ij
2. Исходный алгоритм (фиг. 2б) представляется графом взаимодействия задач: G=<Х,Е>, где X - множество вершин графа G, вершины x∈X которого соответствуют операторам программы, а дуги e=∈E представляют информационные связи (фиг. 2б), где N - число операторов последовательной программы;
3. Матрица следования , где , , (N - число операторов программы) (фиг. 2в) характеризует последовательность выполнения операторов. Она формируется на основе анализа графа G следующим образом: на пересечении i-го и j-го столбца ставится единица, если из i-го оператора можно напрямую попасть в j-й. При формировании матрицы достижимости в случае появления условия оно воспринимается как оператор;
4. Границы найденных линейных участков (фиг. 2г).
Устройство для поиска линейных участков внутри циклов (фиг 1.) содержит матрицу 1 из m строк и n столбцов элементов однородной среды, блок 5 памяти, входы установки матрицы 1 элементов однородной среды соединены с входом 13 установки устройства, вход управления записью блока 5 памяти соединен с входом 9 управления записью устройства, информационные выходы элементов i-й строки (i=1) матрицы 1 элементов однородной среды соединены с i-м информационным входом блока 5 памяти, выход которого соединен с информационным выходом 12 устройства, а также дополнительно введенный блок 45 поиска линейных участков, содержащий матрицу 14 из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных, тактовый генератор 15, счетчик импульсов стробирования загрузки исходных данных 16, первый дешифратор номера строба 17, два счетчика 18-19 и два дешифратора 20-21 для формирования эталонных значений строк/столбцов, счетчик операторов 22, дешифратор номера обрабатываемой строки/столбца 23, счетчик найденных линейных участков 24, первое однопортовое ОЗУ обработки строк 25, второе однопортовое ОЗУ обработки столбцов 26, два компаратора эталонных значений строк/столбцов с реальными значениями строк/столбцов 27-28, три элемента И 29-31, два счетчика для хранения текущих границ найденного линейного участка 32-33, компаратор для формирования сигнала готовности выходных данных 34, третье однопортовое ОЗУ хранения границ найденных линейных участков 35, причем информационные входы матрицы 14 из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных соединены с соответствующими выходами матрицы элементов однородной среды 1, на синхровходы матрицы 14 из (i.j) (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных подается сигнал со входа управления записью устройства, на вход тактового генератора 15 подаются сигналы со входов подачи “питания” 43 и подачи “земли” 44, выход тактового генератора 15 соединен с входами подачи частоты трех однопортовых ОЗУ 25, 26, 35, счетчика номера обрабатываемой строки/столбца 22, счетчика найденных линейных участков 23, счетчиков текущих границ найденного линейного участка 32-33, вход CLK счетчика импульсов стробирования загрузки исходных данных 16 соединен с входом управления записью устройства, первый выход дешифратора номера строба 17 соединен с входом CLK счетчика эталонного значения строки 18 и входом разрешения записи первого однопортового ОЗУ 25, второй выход дешифратора номера строба 17 соединен с входом CLK счетчика эталонного значения столбца 20 и входом разрешения записи второго однопортового ОЗУ 26, третий выход дешифратора номера строба 17 соединен с входами стробирования компараторов эталонных значений строк/столбцов с реальными значениями строк/столбцов 32-33, четвертый выход дешифратора номера строба соединен с вторым входом третьего элемента И 31, выход счетчика эталонного значения строки 18 соединен с входом дешифратора эталонного значения строки 19, выход счетчика эталонного значения столбца 20 соединен с входом дешифратора эталонного значения столбца 21, выход счетчика номера обрабатываемой строки/столбца 22 соединен с входом дешифратора формирования разрешающего сигнала загрузки строки/столбца 23 из матрицы D триггеров 14, входами установки счетчиков границ найденных линейных участков 32-33 и входом компаратора формирования сигнала готовности выходных данных 34, выход счетчика найденных линейных участков 24 соединен с адресным входом третьего однопортового ОЗУ 35 хранения границ найденных линейных участков, выход дешифратора эталонного значения строки 19 соединен с вторым входом компаратора эталонного значения строки с реальным значением строки 27, выход дешифратора эталонного значения столбца 20 соединен с вторым входом компаратора эталонного значения столбца с реальным значением столбца 28, информационные входы первого и второго однопортового ОЗУ 25-26 соединены с матрицей D триггеров 14 таким образом, что в первое однопортовое ОЗУ 25 загружаются значения строк матрицы D триггеров, а во второе однопортовое ОЗУ 26 загружаются значения столбцов матрицы D триггеров, выход первого однопортового ОЗУ 25 соединен с первым входом компаратора эталонного значения строки с реальным значением строки 27, выход второго однопортового ОЗУ 26 соединен с первым входом компаратора эталонного значения столбца с реальным значением столбца 28, прямой выход компаратора эталонного значения строки с реальным значением строки 27 соединен с первым входом первого элемента И 29, инверсный выход компаратора эталонного значения строки с реальным значением строки 27 соединен с первым входом второго элемента И 30, прямой выход компаратора эталонного значения столбца с реальным значением столбца 28 соединен со вторым входом первого элемента И 29, инверсный выход компаратора эталонного значения столбца с реальным значением столбца 28 соединен со вторым входом второго элемента И 30, выход первого элемента И 29 соединен с входом счетчика второй границы найденного линейного участка 32, выход второго элемента И 30 соединен с первым входом третьего элемента И 31, входом разрешения записи третьего однопортового ОЗУ 35, и входом счетчика найденных линейных участков 24, выход третьего элемента И 31 соединен с входом разрешения установки значения в счетчики границ найденного линейного участка 32-33, выход счетчика первой границы найденного линейного участка 33 соединен со старшей половиной информационных входов третьего однопортового ОЗУ 35, выход счетчика второй границы найденного линейного участка 32 соединен с младшей половиной информационных входов третьего однопортового ОЗУ 35, выходы третьего однопортового ОЗУ 35 соединены с выходами S1 и S2 утройства, выход компаратора формирования сигнала готовности выходных данных 34 соединен с выходом RDY устройства, вход разрешения записи третьего однопортового ОЗУ 35 соединен с входом RW устройства, второй вход компаратора формирования сигнала готовности устройства 34 соединен с входом N устройства.
Назначение элементов и блоков устройства для поиска линейных участков внутри цикла (фиг. 1) состоит в следующем:
Матрица 1 элементов однородной среды предназначена для хранения матриц входных/выходных переменных.
Блоки 2.1 - 2.n подсчета единиц предназначены для преобразования кодов с индикаторных выходов элементов соответствующих столбцов матрицы 1 в двоичные коды.
Блок 3 нахождения максимума предназначен для выделения максимального кода из множества кодов на его входах.
Сумматор 4 предназначен для суммирования n двоичных кодов.
Блок 5 памяти предназначен для хранения входных данных.
Вход 6 записи устройства служит для записи матрицы, представляющей двоичный код для сжатия.
Вход 7 управления перестановкой столбцов устройства предназначен для приема сигнала от внешнего устройства управления (ВУУ) о перестановке столбцов.
Вход 8 управления перестановкой строк устройства предназначен для приема сигнала от ВУУ о перестановке строк.
Вход 9 управления записью устройства необходим для приема сигнала «Запись» от ВУУ. По этому сигналу в блок 5 памяти заносится текущий вариант размещения из матрицы 1.
Выход 10 максимальной длины ребра устройства необходим для выдачи значения максимальной длины ребра на ВУУ.
Выход 11 суммарной длины ребер устройства необходим для выдачи значения суммарной длины ребер на ВУУ.
Информационный выход 12 устройства необходим для выдачи варианта размещения, находящегося в блоке 5 памяти, на ВУУ.
Вход 13 установки устройства необходим для синхронизации записи информации в элементы матрицы 1.
Матрица 14.i.j (i=1, 2, …, N, j=1, 2, …, M) D-триггеров синхронизации записи входных данных предназначена для синхронизации записи элементов матрицы 1 в первое 25 однопортовое ОЗУ обработки строк матрицы следования, второе 26 однопортовое ОЗУ обработки столбцов матрицы следования.
Тактовый генератор 15 служит для генерации тактовых сигналов устройства.
Счетчик 16 импульсов стробирования загрузки исходных данных управляет перебором стробов загрузки разных типов исходных данных: строки матрицы следования, столбца матрицы следования, сравнения эталонов, а также строба записи результата. По приходу высокого уровня сигнала на вход clr счетчика 16 осуществляется его сброс. Счет происходит по приходу импульсов на счетный вход CLK счетчика 16. Выходы  2, содержат информацию о текущем номере строба STROB.
Первый 17 дешифратор номера строба, исходя из выходных данных счетчика 16, поступающих на его входы А, формирует выходной строб, выдавая его на одну из выходных линий D1…D4.
Счетчик 18 эталона строки предназначен для формирования кода эталонного значения строки матрицы следования.
Дешифратор 19 эталона строки предназначен для формирования эталонного значения строки матрицы следования из кода строки, полученного со счетчика 18.
Счетчик 20 эталона столбца предназначен для формирования кода эталонного значения столбца матрицы следования.
Дешифратор 21 эталона столбца предназначен для формирования эталонного значения столбца матрицы следования из кода столбца, полученного со счетчика 18.
Счетчик 22 предназначен для перебора строк/столбцов обрабатываемой матрицы следования.
Дешифратор 23 предназначен для формирования управляющих импульсов для чтения текущих строк/столбцов матрицы 14 D триггеров.
Счетчик 24 предназначен для хранения количества найденных линейных участков.
Первое однопортовое ОЗУ 25 предназначено для хранения обрабатываемой строки матрицы следования.
Второе однопортовое ОЗУ 26 предназначено для хранения обрабатываемого столбца матрицы следования.
Первый компаратор 27 предназначен для сравнения эталонного значения строки с реальным значением строки матрицы следования.
Второй компаратор 28 предназначен для сравнения эталонного значения столбца с реальным значением столбца матрицы следования.
Первый элемент И 29 предназначен для формирования управляющего сигнала на увеличение значения счетчика 32 второй границы найденного линейного участка.
Второй элемент И 30 предназначен для формирования управляющего сигнала на запись текущих границ линейного участка в ОЗУ 35 хранения границ линейных участков, и для формирования управляющего сигнала на увеличение значения счетчика 24 линейных участков.
Третий элемент И 31 предназначен для формирования управляющего сигнала установки текущего значения номера обрабатываемой строки/столбца в счетчики границ линейных участков.
Счетчик 32 второй границы линейного участка предназначен для хранения промежуточного значения второй границы найденного линейного участка.
Счетчик 33 первой границы линейного участка предназначен для хранения промежуточного значения первой границы найденного линейного участка.
Компаратор 34 формирования сигнала готовности выходных данных предназначен для выдачи на внешнее устройство управления сигнала RDY, говорящего о том, что работа устройства завершена.
Третье однопортовое ОЗУ 35 предназначено для хранения границ найденных линейных участков.
Вход 36 считывания границ блоков предназначен для того, чтобы ВУУ могло считать границы найденных линейных участков из ОЗУ 35.
Выход 37 признака наличия результата предназначен для оповещения ВУУ о готовности результата.
На вход 38 ВУУ подает количество строк обрабатываемой матрицы следования.
На выход 39 подается значение со счетчика 24 линейных участков. На выход 40 подается значение первой границы найденных линейных участков.
На выход 41 подается значение второй границы найденных линейных участков.
Выход 42 синхронизации частот предназначен для синхронизации работы устройства с ВУУ.
Вход 43 подачи питания и вход 44 подачи “земли” служат для подачи “питания” H и “земли” L соответственно на устройство для поиска линейных участков 45.
Оценка размещения по критериям суммарной длины ребер и максимальной длины ребра происходит следующим образом. Информация с индикаторных выходов элементов каждого столбца матрицы 1 поступает в соответствующие блоки подсчета единиц. Блок 2.i (i=1, 2, …, n) выдает двоичное число (код), равное количеству поступивших на его вход единиц. Полученное число далее поступает на входы сумматора 4 и блока 3 нахождения максимума, соответствующие данному блоку подсчета единиц. В результате на выходе 10 устройства образуется код (оценка) максимальной длины ребра, а на выходе 11 - код (оценка) суммарной длины ребер, отвечающие текущему варианту размещения схемы (содержащемуся в матрице 1). Полученные оценки далее поступают на ВУУ, где происходит их сравнение с предыдущими значениями. В случае улучшения оценок ВУУ подает импульс (сигнал «Запись») на вход 9 управления записью устройства и текущий вариант размещения переписывается в блок 5 памяти из матрицы 1. Более подробно рассмотренный режим работы устройства описан в прототипе.
Предлагаемое устройство предназначено для поиска линейных участков внутри циклов для их последующего распараллеливания в режиме реального времени.
Работа устройства для поиска линейных участков состоит из следующих шагов: Первоначально в матрице 1 элементов однородной среды содержится исходная матрица следования анализируемого участка программы. В счетчике 22 строк хранится код единицы («0…01»). Этот код подается на вход дешифратора 23 и на его первом выходе появляется единичный импульс, который поступает на управляющие входы управления матрицы 14 и разрешает прохождение сигналов с индикаторных выходов первой строки/столбца матрицы 1. Эти сигналы устанавливают соответствующие триггеры матрицы 14 в единичные состояния при условии наличия единичных сигналов.
Поиск линейных участков в режиме реального времени решается в предлагаемом устройстве следующим образом. После записи очередной матрицы следования в матрицу 14 D триггеров запускается генератор 15 импульсов и начинается работа блока 45 поиска линейных участков.
Тактовый импульс с выхода генератора 15 импульсов поступает на счетный вход счетчика 16, и по переднему фронту увеличивает содержимое счетчика 16 на единицу, Значение с выхода счетчика 16 поступает на вход дешифратора 17, и на его выходе STB_ROW появляется единичное значение которое поступает на вход разрешения записи первого однопортового ОЗУ 25, при этом в счетчике 22 хранится код единицы («00…01»), который поступает на адресный вход первого однопортового ОЗУ 25, и по переднему фронту сигнала CLK происходит загрузка первой строки матрицы следования в первое однопортовое ОЗУ 25. При этом значение счетчика 18 принимает значение нуля («00…00») и поступает на вход дешифратора 19, на выходе которого формируется значение эталонной строки матрицы следования.
На следующем шаге тактовый импульс с выхода генератора 15 импульсов поступает на счетный вход счетчика 16, и по переднему фронту увеличивает содержимое счетчика 16 на единицу, Значение с выхода счетчика 16 поступает на вход дешифратора 17, и на его выходе STB_COL появляется единичное значение которое поступает на вход разрешения записи второго однопортового ОЗУ 26, при этом в счетчике 22 хранится код единицы («00…01»), который поступает на адресный вход второго однопортового ОЗУ 26, и по переднему фронту сигнала CLK происходит загрузка первого столбца матрицы следования во второе однопортовое ОЗУ 26. При этом значение счетчика 20 принимает значение двойки («00…10») и поступает на вход дешифратора 21, на выходе которого формируется значение эталонного столбца матрицы следования.
На следующем шаге тактовый импульс с выхода генератора 15 импульсов поступает на счетный вход счетчика 16, и по переднему фронту увеличивает содержимое счетчика 16 на единицу, Значение с выхода счетчика 16 поступает на вход дешифратора 17, и на его выходе STB_CMP появляется единичное значение, которое поступает на входы разрешения работы компараторов 27-28. В случае, если обрабатываемая строка совпадает с эталоном, и обрабатываемый столбец совпадает с эталоном, на выходе первого элемента И 29 появляется высокий уровень, который увеличивает значение счетчика 32 второй границы найденного линейного участка. В случае, если либо строка, либо столбец не совпадают с эталонами, на выходе первого элемента И появится низкий уровень, а на выходе второго элемента И появляется высокий уровень, что говорит о том, что линейный участок завершился, и текущие значения границ найденного линейного участка сохраняются в третьем однопортовом ОЗУ 35.
На следующем шаге тактовый импульс с выхода генератора 15 импульсов поступает на счетный вход счетчика 16, и по переднему фронту увеличивает содержимое счетчика 16 на единицу, Значение с выхода счетчика 16 поступает на вход дешифратора 17, и на его выходе STB_SET появляется единичное значение, которое через третий элемент И 31 при наличии высокого уровня на выходе второго элемента И 30 формирует на выходе третьего элемента И 31 высокий уровень, который соединен с входами принудительной установки счетчиков 32-33 и по положительному фронту этого сигнала происходит сохранение в промежуточных счетчиках 32-33 номера текущей обрабатываемой строки.
Эта последовательность действий повторяется до тех пор, пока не закончатся строки/столбцы исходной матрицы следования, при этом на выходе компаратора 34 появляется высокий уровень сигнала RDY, который говорит ВУУ о том, что работа блока 45 поиска линейных участков завершена.
Таким образом, предлагаемое устройство поиска линейных участков обеспечивает возможность как оценки размещения по критериям суммарной длины ребер, максимальной длины ребра, так и возможность поиска линейных участков внутри циклов в оперативном режиме. Тем самым обеспечивается расширение функциональных возможностей устройства и, следовательно, области его целесообразного применения.