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

• Ховансков, Сергей Андреевич
• кандидат технических наук
• 1998

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

ВВЕДЕНИЕ.

1. РАЗРАБОТКА АЛГОРИТМА ПОСТРОЕНИЯ ОРТОГОНАЛЬНЫХ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ НА МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЕ (МВС)

1.1 АНАЛИЗ АЛГОРИТМОВ ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС.

1.2 АЛГОРИТМ ПАРАЛЛЕЛЬНОГО ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ.

1.3 ОЦЕНКА УСКОРЕНИЯ ВЫПОЛНЕНИЯ РАЗРАБОТАННОГО АЛГОРИТМА ПОСТРОЕНИЯ ДЕРЕВЬЕВ НА МВС.

1.4 ВЫВОДЫ.

2. РАЗРАБОТКА И ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМА ВЫДЕЛЕНИЯ МНОЖЕСТВ НЕПЕРЕСЕКАЮЩИХСЯ ЦЕПЕЙ НА МВС..

2.1 АНАЛИЗ АЛГОРИТМОВ ВЫДЕЛЕНИЯ МНОЖЕСТВ НЕПЕРЕСЕКАЮЩИХСЯ

ЦЕПЕЙ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС.

2.2 АЛГОРИТМ РАСПРЕДЕЛЕНИЯ ЦЕПЕЙ ПО СЛОЯМ НА МВС

2.3. ОЦЕНКА ЭФФЕКТИВНОСТИ ВЫДЕЛЕНИЯ КЛИК ГРАФА НА МВС.

2.4. ВЫВОДЫ.

3. РАЗРАБОТКА АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ СОЕДИНЕНИЙ

НА МВС.

3.1 АНАЛИЗ АЛГОРИТМОВ ТРАССИРОВКИ.,СОЕДИНЕНИЙ И ОЦЕНКА ИХ УСКОРЕНИЯ НА МВС.;.

3.2 ПАРАЛЛЕЛЬНАЯ ТРАССИРОВКА СОЕДИНЕНИЙ НА ОСНОВЕ АЛГОРИТМА ПОСТРОЕНИЯ СВЯЗЫВАЮЩИХ ДЕРЕВЬЕВ НА МВС.

3.3. МОДЕЛИРОВАНИЕ РАБОТЫ АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ

ДЛЯ МВС НА ПЕРСОНАЛЬНОМ КОМПЬЮТЕРЕ.

3.4 ВЫВОДЫ.

4.РЕАЛИЗАЦИЯ АЛГОРИТМА ПАРАЛЛЕЛЬНОЙ ТРАССИРОВКИ НА МВС СО СТРУКТУРНО-ПРОЦЕДУРНОЙ РЕАЛИЗАЦИЕЙ ВЫЧИСЛЕНИЙ.

4.1. СТРУКТУРА И ОБЩИЕ ПРИНЦИПЫ РАБОТЫ МВС.

4.2. ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНОГО ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА И

СИНТЕЗ БАЗОВОГО НАБОРА МАКРООПЕРАЦИЙ ЗАДАЧИ ТРАССИРОВКИ.

4.3. ОЦЕНКА ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ТРАССИРОВКИ.

4.4. АППАРАТНО - ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ САПР СБИС.

4.5 ВЫВОДЫ.

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

С момента появления первой простейшей электронно вычислительной аппаратуры (ЭВА) прошло немало времени. Использование и внедрение ЭВА стало одним из показателей научно-технического прогресса. Прогресс требует своевременного повышения быстродействия, качества, эффективности применяемых ЭВА, что ведет к постоянному ее усложнению. Препятствием повышения качества ЭВА и сокращением сроков ее создания, в свое время, стали несоответствия между возрастающей сложностью микроминиатюризации ЭВА и устаревшими методами и средствами ее конструирования [1-311. Для разрешения этого несоответствия в 70-х - начале 80-х годов была разработана и внедрена новая технология проектирования, связанная с использованием и применением систем автоматизированного проектирования (САПР) [I-3,5-21,24-54 3.

Автоматизация процесса проектирования ЭВА и разработка САПР позволили не только сократить сроки создания аппаратуры и облегчить условия труда, но и повысить качество производимой продукций. Это стало возможным потому, что при производстве изделий для управления станками, автоматами и поточными линиями используется информация, разработанная с помощью САПР и записанная на ЭВМ. Благодаря этому время проектирования сократилось, а ЭВА усложнялась и наметилась тенденция к очередному увеличению сроков разработки изделий, даже с использованием САПР. В тоже время стала заметна тенденция к уменьшению средних сроков эксплуатации ЭВА, которая связана с ускорением прогресса в микроэлектронике и, соответственно с быстрым моральным старением эксплуатируемой аппаратуры [3,8,13,14,16-18,22,23,28,30,31,36,37,40-42,49,52,5460]. При таких противоречивых тенденциях возникло положение, при котором выпускаемые изделия ЭВА становятся с самого начала производства морально устаревшими.

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

Решение этой проблемы может идти четырьмя путями [3,8,22,23, 30,31,36,40,41,52,561. Один из них состоит в разработке эффективных численных методов решения уравнений, в применении иерархического ряда различных по сложности моделей, в использовании адаптивных алгоритмов и т.д., то есть, в совершенствовании программных средств САПР. Этот путь к настоящему времени практически исчерпал себя.

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

В силу принципиального различия в математической постановке задач разных этапов премирования оказывается достаточно сложным создание сквозной САПР СБИС на базе одного общего специализированного вычислителя. Поэтому к настоящему времени наибольшие успехи получены в создании процессоров-акселераторов для логического и физического моделирования, но начинают появляться спецпроцессоры и для других этапов, в частности, для топологического проектирования СБИС [3,8,16,28,30,37,563.

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

Четвертый путь - применение параллелизма для решения задач САПР СБИС. Параллелизм все более широко используется как средство, позволяющее повышать производительность вычислительных систем, не прибегая к повышению быстродействия их компонентов [8,28,30,37].

Реализация параллелизма стала возможна с созданием многопроцессорных вычислительных систем (МВС). МВС вычислительная система, базирующаяся на принципах параллельной обработки информации. Многопроцессорные вычислительные структуры с программируемой архитектурой отличаются способностью аппаратно адаптироваться к характеру вычислительных процессов и обеспечивать высокий уровень распараллеливания вычислений, соответственно, сверхвысокую производительность [9,28,30,55].

В системах автоматизированного р ттйктр^нной аппаратуры в качестве базовых алгоритмов используются различные алгоритмы решения задач на графах. Однако применение этих алгоритмов ограничивается их комбинаторной сложностью. Одним из наиболее эффективных путей сокращения временных затрат на их выполнение является использование многопроцессорных вычислительных систем (МВС). Сокращение времени решения задач проектирования дает возможность повышать качество проектирования увеличением числа циклов итерации, использованием более точных, но трудоемких методов решения [5,7-10,15-54].

Существует множество разработок МВС. Они отличаются друг от друга структурой, объемом и организацией памяти, разновидностями набора выполняемых команд, коммутациями, разрядностью обрабатываемой информации, типами операций и др. [9,28,30,55,61-68]. По сути, МВС является алгоритмическим операционным устройством [61,65,66,681. Алгоритмические операционные устройства по своему назначению можно разделить на три группы.

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

Вторую группу составляют устройства вычисления одноместных функций X, 1/Х, е, log X, тригонометрических функций и т.д.

Третья группа предназначена для вычисления специальных многоместных функций, таких как свертка, БПФ и др.

На рис. I изображена классификация устройств по структурной, аппаратной сложности и по.принципу организации потоков данных.

Матричные устройства можно разделить на 4 класса [9,28,30,55, 61-68]. К первому относят комбинационные схемы (итеративные сети). Если комбинационную матрицу совместить с матрицей триггеров, то, добавив необходимые соединения, получим второй и третий классы устройств - систолические и ассоциативные матрицы [28,30,62,65].

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

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

Для создания наиболее технологичных современных микроэлектронных алгоритмических операционных устройств требуются специфические изменения в структуре самого устройства. Одним из основных необходимых изменений в его структуре является такая организация, при которой оно строилось бы на основе небольшого числа типов элементов. Необходимость обеспечения высокой живучести и надежности требует построения алгоритмических операционных устройств из структурно - однородных блоков. Из приведенных выше структур МВС видно, что наиболее многочисленным семейством являются матричные МВС. Процессорное поле составляют матрицы БИС с идентичными элементами, их структурная сложность незначительна, поэтому матрицы БИС с одноразрядными идентичными элементами экономичны в проектировании и изготовлении. Они получают все большее распространение [30,55,61-64,66-681.

Выполнение любого алгоритма может быть разбито на отдельные процессы, это могут быть микрооперации, операции, команды, блоки и т.д., а с точки зрения последовательности выполнения процессов, любой алгоритм можно представить как параллельный, ярусный и параллельно-ярусный. Параллелизм решения задач реализуется на МВС, когда алгоритм решения является параллельным и для МВС создана специальная параллельная программа, предназначенная достичь цели, заданной алгоритмом задачи и обеспечить эффективную параллельную обработку информации [42,55,61-64,69-713. От эффективности параллельной обработки информации зависит время решения задач на МВС [63,64,703.

Существует два основных метода использования параллелизма -параллелизм структуры (структурный параллелизм) и параллелизм процессов [42,55,61,63,69-713. Различие этих видов параллелизма заключается в том, что структурный параллелизм определяется на уровне одной операции и что эти операции выполняются так, как если бы они выполнялись одновременно над каждым элементом структуры данных и параллелизм процессов определяется на уровне более крупных совокупностей операций. Синхронизация между параллельными потоками команд выполняется с помощью генератора. Эти методы весьма сходны и для многих алгоритмов могут быть применены с одинаковой эффективностью [55,63,70,713. Однако считается, что динамическое создание и уничтожение процессов, обеспечивая большую гибкость программирования, требует большей избыточности для реализации параллелизма и для повышения эффективности необходимо уменьшение глубины детализации [55,61-64,69,703, т.е. параллельный алгоритм должен строиться из возможно более крупных, но редко взаимодействующих блоков. Из этого следует, что наиболее эффективен второй метод распараллеливания - параллелизм процессов.

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

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

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

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

- исследование существующих алгоритмов построения связывающих деревьев, для оценки ускорения их выполнения на МВС, на основе выделения в них максимальных параллельных процессов; разработка нового алгоритма параллельного построения ортогональных связывающих деревьев и оценка ускорения его выполнения на МВС;

- исследование существующих алгоритмов распределения фрагментов цепей по слоям для оценки ускорения их выполнения на МВС на основе выделения в них максимальных параллельных процессов;

- разработка алгоритма определения клик графа для выполнения на МВС и оценка эффективности его выполнения;

- исследование существующих алгоритмов трассировки соединений для оценки ускорения их выполнения на МВС на основе выделения в них максимальных параллельных процессов;

- разработка нового алгоритма параллельной трассировки соединений и оценка ускорения его выполнения на МВС;

- разработка организации вычислительного процесса и синтез базового набора макроопераций необходимых для реализации задачи параллельной трассировки на МВС;

- разработка аппаратно-программного комплекса, для работы САПР

СБИС, на основе разработанных алгоритмов и МВС со структурно процедурной организацией вычислений, в качестве аппаратного ускорителя выполнения задач САПР;

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

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

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

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

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

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

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

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

- разработаны принципы организации вычислительного процесса и синтезирован базовый набор макроопераций для выполнения параллельной трассировки на МВС СПРВ.

Практическая ценность работы

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

На защиту выносятся следующие основные тезисы и положения изложенные в диссертации:

1.Алгоритм параллельного построения связывающих деревьев на МВС.

2.Алгоритм определения клик графа на МВС.

3.Алгоритм параллельной трассировки на МВС.

4.Организация вычислительного процесса и синтез базового набора макроопераций, необходимых для выполнения параллельной прокладки трасс на МВС.

Апробация результатов:

Основные результаты диссертационной работы докладывались и обсуждались на:

- всероссийской XXXIX научно-технической конференции, ТРТУ, г. Таганрог, 1993г.; всероссийской научно-технической конференции "Актуальные проблемы твердотельной электроники и микроэлектроники", г. Таганрог , 1994г.;

- всероссийской научно-технической конференции "Интеллектуальные САПР-96", г. Геленджик, 1997г.;

- научно-технических и научно-методических конференциях профес-сорско-преподователъского состава, аспирантов и сотрудников Таганрогского государственного радиотехнического университета в 19861996 г.

Публикации по теме диссертационной работы

Материалы, содержащие основные научные . результаты, опубликованы в 13 печатных работах, кроме того во ВНТИЦ зарегистрировано 5 отчетов по хоздоговорным и научно - исследовательским работам в области автоматизации и проектирования РЭА и БИС, выполненных при непосредственном участии автора. Структура и объем диссертационной работы.

Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложения. Работа содержит 172 стр. машинописного текста, включая 37 стр. рисунков и таблиц, список литературы из 90 наименований, 3 стр. приложений и актов об

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Ховансков, Сергей Андреевич

4.5 ВЫВОДЫ

Впервые разработана организация вычислительного процесса для решения задачи разработанным алгоритмом параллельной трассировки на существующей многопроцессорной вычислительной системе со структурно - процедурной реализацией вычислительного процесса (МВС СПЕВ).Задача разбита на 4 кадра, представляющих собой законченные подзадачи с точки зрения реализации кадров на ресурсе МВС СПРВ.

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

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

Выполнено сравнение времени выполнения•задачи трассировки на МВС СПРВ разработанным алгоритмом и волновым алгоритмом. В результате получено, что разработанный алгоритм дает сокращение времени решения в 200-8000 раз при количестве процессоров т=1-1000.

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

На основе существующего комплекса ПЭВМ типа IBM PC и МВС СПРВ и программ, реализующих разработанные алгоритмы, предложен аппаратно-программный комплекс для выполнения САПР СБИС, использующий МВС СПРВ в качестве ускорителя решения задач САПР СБИС.

ЗАКЛЮЧЕНИЕ

В данной диссертационной работе анализировались возможности решения задач конструкторского проектирования ВМС на базе многопроцессорных вычислительных систем и получены следующие результаты : на основе анализа классических алгоритмов исследована организация процессов решения алгоритмов на МВС и в них выделены максимальные по объему параллельные вычислительные процессы;

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

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

- предложен алгоритм решения задачи расслоения, путем определения клик графа на базе МВС. Алгоритм позволяет выделять независимые множества графа без петель и кратных ребер;

- впервые разработан алгоритм параллельной трассировки соединений на МВС;

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

- произведены оценки ускорения выполнения разработанных алгоритмов при использовании МВС по сравнению с временем работы алгоритмов на ОВС;

- разработаны принципы организации вычислительного процесса решения задачи трассировки соединений на многопроцессорной системе в зависимости от архитектуры МВС СПРВ;

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

- предложен, на основе программ, реализующих разработанные алгоритмы и существующего комплекса ПЭВМ типа IBM PC, и МВС СПРВ, аппаратно-программный комплекс для выполнения САПР СВИС, использующий МВС СПРВ в качестве ускорителя решения задач САПР СБИС.

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

1. Будя А.П., Кононюк А.Е., Куценко Г.П. и др. Справочник по САПР / Под общей ред. Скурихина В.И. - К.: Техника, 1988.- 375с.

2. Возрастание роли САПР//Comput.Des. 1995 - 34, N2,с.52.

3. Выбор правильной стратегии разработки / Jani Yushvant, Leshem Gabi // Electron. Des. 1996 - 44, N 2, c. 111 - 117.

4. Дракин В.И., Попов Э.В., Преображенский А.Б. Общение конечных пользователей с системами обработки данных. М.: Радио и связь, 1988. - 288 с.

5. Жук К.Д., Тимченко A.A., Родионов A.A. и др. Построение современных систем автоматизированного проектирования. К.: Наукова думка, 1983. - 248 с.

6. Ильин В.Н., Коган В.А. Разработка и применение программ автоматизации схемотехнического проектирования. М. : Радио и связь, 1984. - 368 с.

7. Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных микросхем. /В.А. Мищенко, Л.М.Городецкий, Л.И.Гурский и др.- М.: Радио и связь, 1988.-272с.

8. Интегрированная САПР высокоуровневого синтеза БИС, адаптирующаяся к библиотеке модулей / Jon Jer Min, Kuang Shiann -Rong//Proc.Nat.Sei.Comic, Rep.China. A.-1995 - 19, N3,c.220 - 234.

9. Каляев A.B., Мелихов A.H., Курейчик В.M., Гузик В.Ф., Калашников В. А. Автоматизация проектирования вычислительных структур ИРУ, 1983 г., 224 с.

10. Колин Джонсон Р. Средства автоматизации проектирования, практически исключающие прикладное программирование. Электроника, 1982, т.55, N11, с. 129-140.

11. П. Курейчик В.М.»Калашников В.А.,Лебедев Б.К. Автоматизацияпроектирования печатных плат. Ростов, РТУ, 1984, сб.труд.- 80 с.

12. Курейчик В.М., Лебедев Б.К., Боли Л.И. Методические указания по использованию в дипломном проектировании системы автоматизированного проектирования двухслойных печатных плат.-Таганрог, РТИ, 1982. сб.трудов 63 с.

13. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР М.: Радио и связь, 1990 г. 352 с.

14. Кузьмин Б.А., Эйдес A.A., Игуров Б.С. Адаптируемые системы автоматизированного проектирования печатных плат. М.: Радио и связь, 1984.

15. Мурога С. Системное проектирование сверхбольших интегральных схем Т. 1: Пер. с англ. М.: Мир, 1985 г. 288 с.

16. Новые САПР передвигают ключевые решения к началу цикла разработки / Dondlin Mike // Gomput. Des. 1996 -34, N 1, с. 31.

17. Новый подход к упорядочению перестановки вентилей в одномерных логических матрицах /У IEEE Prog. Circuits, Devices and Syst. 1995 - 142, N 1, с.90 - 96.

18. Норенков M.П., Маничев В.Б. Основы теории и проектирования САПР М.: Высшая школа, 1990 г., 335 с.

19. Ньютон А.Р., Санджованни Винчентелли А.Л. Системы автоматизированного проектирования специализированных ш /'/ ТМИЭР,т.75, N 6, 1987 г. с. 30 - 43.

20. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. М. .-Высшая школа, 1986.-304с.

21. Обучающие машины, системы и комплексы. Справочник / Под ред. А.Я. Савельева. К.: Вища школа, 1986. - 303 с.

22. Оценка вычислительных ресурсов для реализации схемцифровой обработки сигналов' // IEEE Trans. Comput. Aid.Des.Integr. Circuits and Syst. 1994 - 13, N 6, с.669 - 683.

23. Оценка компактности размещения БИС на основе SQP -алгоритма // Microelectron. J. 1995 - 26, N 4, с.351 - 359.

24. Паркер Э.С., Хайяти С. Использование экспертных систем и кремниевой компиляции для освоения автоматизации процесса проектирования СБИС // ТИИЭР, т. 75, N 6, 1987 г.,с. 43 54.

25. Петренко А.И., Семенков О.И. Основы построения систем автоматизированного проектирования. К.:Вища школа, 1984. - 296с.

26. Петренко А.И., Цурин О.Ф., Киселев Г.Д. Автоматизация проектирования цифровых устройств. К.: Вища школа, 1978. - 152с.

27. Петухов Г.А., Смолич Г.Г., Юлин Б.И. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. M.: Радио и связь, 1987.

28. Принципы создания универсального сверхпроизводительного супермакронейрокомпьютера с программируемой самоорганизующейся архитектурой и элементами искусственного интеллекта. (Отчет о НИР) /' НИИ МВС при ТРТИ. N ГР 01.9110055147 - Таганрог, 1991г., кн.З.

29. Проектирование СБИС /М. Ватанабэ, К. Асада, К. Кани, Т.Оцуки: Пер. с япон. М.: Мир, 1988 г., 304 с.

30. Разработка и исследование архитектуры, принципов построения и элементной базы высокопроизводительного суперпроцессора для решения задач САПР СБИС. (Отчет о НИР) / НИИ МВС при ТРТИ.-N ГР 01.9/10 054183 Таганрог, 1991 г., 90 с.

31. Решение проблемы совместимости средств САПР / KurpisPeter //' Electron. Des. 1996 - 44, N 2, с. 118 - 119.

32. Абрайтис Л.Б. Автоматизация проектирования топологии цифровых интегральных микросхем. М.: Радио и связь, 1985 г., 200 с.

33. Абрайтис JI. Б., Шейнаускас P.M., Жилевичус В. А. Автоматизация проектирования ЭВМ М.: Сов. радио, 1978 г., 272 с.

34. Автоматизированное конструирование монтажных плат РЭА : Справочник специалиста / А.Т. Абрамов, В.Б. Артемов,В.П. Богданов и др.; Под ред. Л.П. Рябова. М.: Радио и связь, 1986. - 192 с.

35. Автоматизация конструирования больших интегральных микросхем /A.M. Петренко, П.П. Сыпчук, А.Я. Тетельбаум и др. -Киев: Вища школа, 1983 г., 312 с.

36. Автоматизация проектирования БИС. В 6 кн.: Практич. пособие. Кн. 4. Г.Г. Казеннов, В.М. Щемелинии. Топологическое проектирование нерегулярных БИС /Под ред. Г.Г. Казеннова -M.:Высшая школа, 1990 г., 110с.

37. Автоматизация проектирования встроенных систем /У GMD -Вег. 1995 N 245, c.I - XII,1 - 111.

38. Анисимов В.И., Дмитрович Г.Д., Скобельцын К.Т. и др. Диалоговые системы схемотехнического проектирования / Под ред. Анисимова В.И. М.: Радио и связь, 1988. - 288 с.

39. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств Львов: Вща школа, 1981 г., 168 с.

40. Большаков A.C. Тенденции развития интеллектуальных инструментов САПР //' 48 науч.-техн. конф. С.-Петерб. гос. ун-та телекоммуникаций: тез. докл. СПб, 1995 г., с.68.

41. Методология выбора средств автоматизации электронного проектирования EDA // Electron. Des. 1995 - 43, N 17, с.81 - 94.

42. Мобильная объектно ориентированная параллельная среда САПР СБИС // IEEE Trans. Comput. - Aid. Des. Integr. Circuits and Syst. - 1994 - 13, N 7, с.829 - 842.

43. Морозов K.K., Одшгоков В-Г. > Курейчик В.M. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры М.: Радио и связь, 1983 г., 280 с.

44. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. - 128 с.

45. Рябов Л.П. Автоматизированное конструирование монтажных плат РЭА. М.: Радио и-связь, 1986.

46. Селютин В.А. Автоматизированное проектирование топологии ВМС. М.: Радио и связь, 1983.

47. Сорокопуд В.А. Автоматизированное конструирование микроэлектронных блоков с помощью малых ЭВМ. М.: Радио и связь, 1988.

48. Системы автоматизированного проектирования в радиоэлектронике: Справочник/ Е.В. Авдеев и др. Под ред. И.П. Норенкова. М.:Радио и связь, 1986. - 368 с.

49. САПР электротехнических установок // Autom. Precision 1995 16, N 8 - с.44.

50. Селютин В.А. Автоматизация проектирования топологии БИС -М.: Радио и связь, 1983 г., 112 с.

51. Селютин В. А. Машинное конструирование электронных устройств М.: Сов. радио, 1977 г., 384 с.

52. Сервисные программы для разработки заказных БИС и ПЛМ //ELRAD 1995 - N 8, с.56 -61.

53. Системы автоматизированного проектирования : Учебное пособие для вузов: В 9 кн. /Под. ред. И.П. Норенкова М.: Высшая школа, 1986 г.

54. Средства управления процессом создания проектов БИС /donlln Mike // Comput. Des. 1995 - 34, N 2, с. 44-45.

55. Супер-ЭВМ с программируемой архитектурой инейрокомпьютеры. (Отчет о НИР) / НИИ МВС при ТРТИ. N ГР 01.090036910 - Таганрог, 1991 г., кн. 3.

56. Цикл проектирования сегодня / Adams Steve // Electron. Compon. News 1995 - 39, N 6, с.1ST.

57. W.G. Kao and T.M Perug. Gross Point Assignment with. Global Rerouting for Genetal Architecture Designs IEEE Trans. Computer-Aided Design, vol. 14, no. 3, pp.337- 348 (march, 1995).

58. S. Papers On Over-the-Gell Channel Routing with Cell Orientetions Consideration, vol.14, no.6, pp. 766-772 (June,1995).

59. B.A. McCoy and Gabriel Robins Non-Tree Routing, vol.6, no.6, pp. 780-784.

60. M.K. Dhodhi, P.H. Mielscher, R.M. Storer Datapath Synthesis Using a Problem-Space Genetic Algorithm, vol. 14, no.8, pp. 934-943 (august, 1995).

61. Мизин И.А., Махиборода А.В.Концепция самоопределяемых данных и архитектуры распределенных систем.: Информационные технологии и вычислительные системы, 1995, Ш, с.22-31.

62. Программирование на параллельных вычислительных системах. Под ред.Бэбб P.II-M.: Мир, 1991, -376с.

63. Cray Balances Vector and MPP. Electronics, 1993, v.66, Я15, p.5.

64. Каляев B.A., Левин И.И., Фомин С.3D.' Об оценке эффективности решения 'задач математической физики на многопроцессорныхсистемах. // Электронное моделирование, 1989, N6, с.11-15.

65. Каляев A.B. Многопроцессорные системы. М.:Наука. -*1987.

66. Parallel channel routlng/25th АСМ/ IEEE Des. Autom. Conf., Anahelm -June 12-15,1988: Proc.- New York -1988.-s.128-133.

67. КАЛЯЕВ A.B. и др. Супер-ЭВМ на основе процессора ЕС-2703. Перспективы развития. Конструирование алгоритмов и решение задач математической физики. - М.:Наука.-1987.-с. 177-190.

68. Тарасенко Л.Г. Реализация языков программирования на ЭВМ архитектуры потоков данных.СуперЭВМ, вып.2,ВЦКП РАН,1994,с.108-125.

69. Landman В. S., Russo R.L. On a Pin Versus Block Relationship for Partitions at Logic Graphs. IEEE Trans., 1971, V. C-20, N12, pp.1469-1479

70. ИВАНОВ E.A. Параллельные алгоритмы на графах.-Кибернетика. -I98I.-3.-c.8I-83.

71. Теория и методы автоматизации проектирования вычислительных систем: Пер. с англ. /Под ред. Врейера М.: Мир,1977г., 285с.

72. Шумков Ю.М., Эйдельпапт В.М. Программное обеопичипие автоматизированного проектирования радиоэлектронных схем.- К.: Техника, 1984. 135 с.

73. Эвристический подход к исключению неоптимальных проводных связей // Dr. Dobb's J. 1995 - 20, N 4, с.28 - 33.

74. Энкарначчо Ж., Шлехтендаль Э. Автоматизированное проектирование. Основные понятия и архитектура систем: Пер. с англ. М.: Радио и связь, 1986. - 288 с.

75. LOCUS ROUTE.A parallel global router for standart sells. Rose Jonathan U25th ACM/IEEE Des. Autom. Conf. Anaheim, June12.15, 1988.-Proc. New York -1988.-s.189-195.

76. WATANABLA TAKUMI,KITARAWA HITOSHI.SUSIYAMA YOSHI. A parallel adapteble routing algorithm and its implementation on a twodimensional array processor. IEEE Trans. Comput. - Aid. Des. Integr. Circuits and Syst. -1987,b ^-s.241-250

77. Ш1МЕВ Ю.Т., MJIMEBA Г.М. Алгоритм и программа для параллельной трассировки соединений при топологическом проектировании ИС.- "25 год полупроводниковой промышленности : Юбилейная научно-техническая конференция "- Ботевград.-б.г.- с.107-III.

78. КАЛАШНИКОВ В.А., КУРЕЙЧИК В.М. и др. Автоматизация проектирования печатных плат. Ростов н/д.,сб. трудов, 1984.

79. Файзулаев В.И., Павлычев В.Н., Драбин В.А. Оценка длины связи в логических цепях ЭВМ. Вопросы радиоэлектроники. Сер. ЭВТ, 1982, Вып.16, с.95-100

80. Siegel L.J., Siegel H.J., Swain Р.Н. Performance measures for evaluation algorithms for SIMD machines. IEEE Trans. Software Eng., 1982, N4, pp.319-331

81. H.N.GABOW. Efficient algorithms for finding minimum spanning and aerected grafs.-Combinatorica.-1986. -p.109-112.

82. BALAS EGON. Finding a maximum clique in an abbitrary grath.-SIAM J.Comput.-1 986.-p. 1054-1068.

83. DOSHI K., SHITU A. Optimal grath algorithms on a fixed size linear array.-IEEE Trans.Comput.-1087.-p.460-470.

84. NAOR JOSEPH. A fast parallel coloring of planar graths with five colors.- Inf.Process Lett.-198?.-p.51-53.

85. МЕЛИХОВ A.H. и др. Применение графов для проектирования дискретных устройств.- М: Наука. -1974. •

86. ЖТВИНЕНКО В.А. Методы определения семейств клик графа.

87. В кн: Методы и программы решения оптимизационных задач на графах и сетях. Часть 2.- Новосибирск.-1982.-с.90-02.

88. HEMMERLING ARMIN. Edge coloredgraths In labyrinth theory. Prep. Ems t-More tz. Arndt-Univ. Greif swalci Math. - 198T.

89. Добронравов O.E., Цурин О.Ф., Трофимов Б.М. Интерактивная система проектирования гибридных интегральных схем.- М.: Энергоатомиздат, 1985. 120 с.

90. Файзулаев Б.М. Средняя длина и трассировочная способность матричных БИС ЭВМ. Микроэлектроника, 1983, т.12, вып.5, с.457-4631. р И Л О Ж Е II И Е

91. Акты об использовании результатов диссертационной работы• -V "УТВЕРЖДАЮ" jí^y'gx^'VV; Директор НИИ МВС

92. Д-ЪН. профессор y&H^S^^^Y'^ Божич В .11.

93. Настоящим подтверждается , что результаты диссертационной работы сотрудника НИИ МВС С.А.Хованскова "Исследование и разработка параллельных алгоритмов трассировки СБИС" использованы при выполнении следующих научно-технических работ:

94. Разработка и исследование архитектуры, принципов построения и элементной базы • высокопроизводительного универсального суперпроцессора со cTpyicrypHoií организацией вычислений" N ГР 01.9.10

95. При этом использованы следующие конкретные результаты диссертационной работы.

96. По теме N ГР 01.9.70 003041:1. параллельный алгоритм выделения клик графа на МВС;2. теоретические оценки времени работы и эффективности решения задачи выделения на МВС.

97. Проведенные исследования позволили обосновать эффективность применения МВС СПРВ в качестве ускорителя решения задач САПР054183;1. СБИС.

98. Завлабораторией 250, к.т.н.

99. Зав.отделом 26, д.т.н., профессор1. И.А.Каляев1. И ЛI.Левин

100. УТВЕРЖДАЮ" Замдиректора ^"Супер ЭВМ"4 К Т

101. Об использовании результатов кандидатской диссертации

102. Хованскова Сергея Андреевича "Исследование и разработка параллельных алгоритмов трассировки СБИС" в НИР .

103. Проведенные исследования позволили обосновать эффективность применения МВС СПРВ в качестве ускорителя решения задач САПР1. СБИС.1. А К Тоб использовании в учебном процессе результатов диссертационной работы Хованскова С.А.

104. Зав.кафедрой КЭО д.т.н., профессор1. Л. А.Болио й1404 .92.