Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС

Диссертация: Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Уменьшение размеров привело к тому, что проводники вносят существенный вклад в задержку распространения сигнала даже в топологии стандартной ячейки. Следовательно, необходимо учитывать данные схемотехнические проблемы при разработке топологии ячеек. Особенно сильно на задержку распространения сигнала в стандартной ячейке влияет расстояние между затворами транзисторов, так как диффузионная область… Читать ещё >

Содержание

  • Введение,
  • Глава 1. Обзор методов сжатия топологии
    • 1. 1. Постановка задачи сжатия
    • 1. 2. Классификация алгоритмов сжатия
    • 1. 3. Одномерное сжатие
    • 1. 4. Алгоритмы, использующие два графа ограничений
    • 1. 5. Двумерное сжатие
    • 1. 6. Иерархическое сжатие
    • 1. 7. Оптимизация топологии
  • Выводы
  • Глава 2. Представление топологии и построение графа ограничений
    • 2. 1. Контурное представление топологии
    • 2. 2. Представление технологических правил
    • 2. 3. Построение графа ограничений
    • 2. 4. Способы минимизации длины критического пути в графе ограничений
    • 2. 5. Выводы
  • Глава 3. Методы сжатия топологии стандартных ячеек
    • 3. 1. Алгоритм 1.5 мерного сжатия
    • 3. 2. Анализ графа ограничений
    • 3. 3. Критерий остановки и анализ дальнейшей сжимаемости топологии
    • 3. 4. Выход из локальных минимумов
    • 3. 5. Заключительная оптимизация топологии
    • 3. 6. Сложность алгоритма сжатия
    • 3. 7. Выводы
  • Глава 4. Снижение размерности задачи сжатия
    • 4. 1. Метод линейной декомпозиции
    • 4. 2. Способы применения линейной декомпозиции
    • 4. 3. Выводы
  • Глава 5. Исследование эффективности методов сжатия
    • 5. 1. Выбор характеристики размера топологии стандартной ячейки
    • 5. 2. Зависимость времени сжатия от размеров топологии
    • 5. 3. Сравнение качества сжатия топологии
    • 5. 4. Минимизация задачи сжатия
    • 5. 5. Выводы

Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС (реферат, курсовая, диплом, контрольная)

Актуальность работы.

В настоящее время современные субмикронные технологии достигли такой степени интеграции, что минимальный размер топологического объекта меньше длины волны, используемой при фотолитографии. Например, длина затвора транзистора равна 45 нм, а длина волны — 193 нм. (Для сравнения размер вируса гриппа равен 60 нм.) Как следствие этого, к известным технологическим ограничениям на минимальное расстояние и размер объектов топологии добавились новые, более сложные правила. Данные правила зависят от конфигурации, геометрических размеров и взаимного расположения объектов топологии. Кроме того, для создания объектов меньше чем длина волны применяются специальные приемы, позволяющие улучшить разрешающую способность технологического оборудования. Одним из таких приемов является засветка противоположными фазами с разных сторон проводника. Это порождает ряд правил, гарантирующих отсутствие конфликтов противоположных фаз. Например, необходимо выдерживать специальное минимальное расстояние между проводами, если:

• они перпендикулярны и их ширина меньше длины волны;

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

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

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

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

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

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

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

— разработка алгоритмов для улучшения быстродействия, трассируемости и выхода годных на этапе сжатия;

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

— разработка иерархических методов сжатия больших ячеек;

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

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

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

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

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

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

Реализация.

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

Практическая значимость работы.

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

Апробация основных теоретических и практических результатов работы проводилась на конференциях:

• Международная научно-техническая конференция «Интеллектуальные САПР» (г. Геленджик, 1999;2003 г., 5 докладов).

• Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2003», (МИЭТ, 2003 г., 1 доклад).

Публикации. Результаты диссертации отражены в пяти статьях [2,3,6,7,12], шести тезисах научных докладов на конференциях [1,4,8−11] и одном патенте [5].

Структура и объем диссертационной работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 119 страницы и 2 акта о внедрении.

5.5. Выводы.

В данной главе проведено исследование предложенных ранее алгоритмов сжатия, а именно:

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

• Проведено сравнение предложенных алгоритмов сжатия с известными методами по различным критериям: время сжатия, плотность топологии, количество DRC ошибок и т. д.

• Оценена эффективность метода линейной декомпозиции задачи сжатия.

• Предложен способ выбора оптимальной ширины окна сжатия и величины перекрытия соседних окон при линейной декомпозиции.

Заключение

.

Настоящая диссертационная работа была посвящена исследованию проблем сжатия топологии стандартных ячеек СБИС при соблюдении современных технологических ограничений.

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

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

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

• Для постановки некоторых объектов топологии в сетку трассировщика предложен алгоритм вычисления длиннейших путей графа ограничений, учитывающий данные требования.

• Критерии остановки позволяют уменьшить время работы алгоритма сжатия. Предложен ряд критериев: целевой размер, плотность и память объектов топологии.

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

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

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

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

4. Проведено исследование разработанных алгоритмов сжатия, а именно:

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

• Проведено сравнение предложенных алгоритмов сжатия с известными методами по различным критериям: время сжатия, плотность топологии, количество DRC ошибок и т. д. Показано преимущество разработанного метода.

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

5. Предложенные алгоритмы реализованы в виде программы сжатия топологии стандартных ячеек, написанной на языке С++. Данная программа интегрирована в систему автоматического синтеза топологии стандартных ячеек СБИС и внедрена в ЗАО «Моторола ЗАО». Кроме того, в МИЭТе результаты диссертации внедрены в учебный процесс в курсе «Автоматизация топологического проектирования БИС» .

4 Г 4.

Показать весь текст

Список литературы

  1. A.M., Плис А. П., Сотников М. А. Контурная модель топологии для задачи сжатия на основе графа ограничений // Известия ТРТУ, тезисы докладов. 1999. — С. 353−354.
  2. A.M., Плис А. П., Сотников М. А. Контурная модель топологии ячейки СБИС для задачи сжатия // Труды НИИР. 2000. — С. 73−75.
  3. A.M., Сотников М. А. Сжатие с одновременным использованием сдвига и разбиения // Труды НИИР. 2001. — С. 74 — 76.
  4. A.M., Сотников М. А. Методы реорганизации контуров при сжатии топологии // Известия ТРТУ, тезисы докладов. 2001. — С. 205 206.
  5. V. К. R., Marchenko A.M., Sotnikov М.А. Method and Apparatus for Constraint Graph Based Layout Compaction for Integrated Circuits // United States Patent, № 6,434,721 Bl, Aug. 13, 2002.
  6. A.M., Сотников М. А. Методы реорганизации контурной топологии при сжатии ячеек СБИС // Труды НИИР. 2002. — С. 105−107.
  7. М.А. Алгоритм сжатия топологии стандартных ячеек субмикронных СБИС // Труды НИИР. 2002. — С. 108−112.
  8. A.M., Сотников М. А. Метод линейной декомпозиции топологии СБИС в задаче сжатия // Международная научно-технической конференции «Интеллектуальные САПР», Труды конференций. 2002. -С. 346−347.
  9. A.M., Сотников М. А. Методы выхода из локального минимума в итерационных алгоритмах сжатия топологии // Международная научно-технической конференции «Интеллектуальные САПР», Труды конференций. 2002. — С. 323−326.
  10. A.M., Сотников М. А. Метод линейной декомпозиции ячеек СБИС при сжатии топологии // Труды НИИР. 2003. — С. 117−121.
  11. A.M., Сотников М. А. Критерии остановки в итеративных алгоритмах сжатия топологии стандартных ячеек СБИС. // Международная научно-технической конференции «Интеллектуальные САПР», Труды конференций. 2003. — Т. 2. — С. 96−99.
  12. Wayne Н. Wolf, Robert G. Mathews, Jon A Newkirk, and Robert W.Dutton. Algorithm for Optimizing Two-Dimensional Symbolic Layout Compaction, IEEE Transactions On Computer-aided Design, Vol.7, April* 1988, pp. 451−466
  13. Hyunchul Shin and Chi-Yuan Lo, An Efficient Two-Dimensional Layout Compaction Algorithm, Proceedings of the 26th ACM/IEEE Design Automation Conference, pp. 290−295, ACM Press, June 1989
  14. N.Sherwani. Algorithm for the VLSI Physical Design Automation, Second Edition, Kluwer Academic Publishers, 1995
  15. F.-L.Heng, Z. Chen, G.E.Telfez. A VLSI Artwork Legalization Technique Based on a New Criterion of Minimum Layout Perturbation, ISPD'97, 1997, pages 116−121
  16. F.-L.Heng, L. Liebmann, J. Lund. Application of Automated Design Migration to Alternating Phase Shift Mask Design, ISPD'01, April, 2001
  17. L.-Y. Wang, Y.-T. Lai, Graph-Theory-Based Simplex Algorithm for VLSI Layout Spacing Problem with Multiple Variable Constraints, IEEE Transaction on Computer-Aided Design of Integrated Circuits an Systems, vol. 20, no 8, pp. 967−979, August 2001
  18. Reinhardt, Michael, Automatic Layout Modification, Kluwer Academic Publishers Group, 2002
  19. R.Sedgewick, Algorithms in С++, Addison-Wesley Publishing Company, 1992
  20. Thomas Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, 1990
  21. Ralf Seepold, Amo Kunzmann, Breuse Technique for VLSI Design, Kluwer Academic Publishers 1999
  22. H.Veendrick, Deep-Submicron ICs, Kluwer Academic Publisher, s 2000
  23. D.J.Eaglesham 0.18um CMOS and beyond, // DAC-99, pp703−707, 1999
  24. M.A.Breuer, M. Sarrafzadeh and F. Somenzi, Fundamental CAD Algorithms, // IEEE Transaction on Computer-Aided Design, vol. 19, No 12, pp. 1449−1475, December 2000
  25. R.W.Dutton, and A.J.Strojwas, Perspectives on Technology and Technology-Driven CAD, // IEEE Transaction on Computer-Aided Design, vol. 19, No 12, pp. 1544−1560, December 2000
  26. Abdul A. Malik, An Efficient Algorithm for Generation of Constraint Graph for Compaction, 1С CAD, pp. 130−133, 1987
  27. W.H.Crocher, C.Y.Lo and R Varadarajan, MACS: a Module Assembly and Compaction System, Proc. Of the IEEE International Conference on Computer Design, pp205−208, Oct. 1987
  28. X.M Xiong and E.S.Kuh, An Efficient and Intelligent Channel Spacer, Proc. ACM/IEEE Design Automation Conference, pp298−304,1986
  29. Y.E.Cho, A Subjective Review of Compaction, Proc. of the ACM/IEEE 22nd Design Automation Conference, pp 396−404, June 1985.
  30. S.B.Akers, J.M.Geyer and D.L.Roberts 1С Mask Layout with a Single Conductor Layer //Proceedings of 7th Design Automation Workshop, pages 716,1970
  31. M.Y. Hsueh and D.O.Pederson Computer-Aided Layout of LSI Circuit Building-Block // PhD. thesis, University of California at Berkeley, December 1979
  32. S.Kirpatrick, C.D.Gelatt, MP. Vecchi, Optimization by Simulated Annealing, Science, vol. 20, pp. 671−680, May 1983.
  33. H.Shin, A.L.Sangiovanni-Vinncentelli, C.H.Sequin Two-Dimensional Compaction by 'Zone Refining', Proc of the 23rd IEEE Design Automation Conference, pp. 115−122, June 1986
  34. H.Shin, A.L.Sangiovanni-Vinncentelli, C.H.Sequin Two-Dimensional Module Compactor Based on 'Zone Refining', Proc of the IEEE International Conference, on Computer Design, pp. 201−204, October 1987
  35. H.Shin, A.L.Sangiovanni-Vinncentelli, C.H.Sequin 'Zone Refining' Techniques for 1С Layout Compaction, IEEE Transaction on Computer-Aided Design, vol. 9, No 2, pp. 167−179, February 1990
  36. W.L. Schiele, Automatic Design Rule Adaptation of Leaf Cell Layouts, // INTEGRA TION, the VLSIjournal (3), 1985, pages 93−112
  37. W.L. Schiele, Compaction with Internal Over-Constraints Resolution, ACM/IEEE 27th Design Automation Conference, pages 390−395, 1988
  38. J.Burns and A.R.Newton. SPARCS: A new constraint-based 1С symbolic layout? spacer, Proc. of the IEEE Custom Integrated Circuits Conference, pages 534 539, May 1986
  39. J.Burns and A.R.Newton, Efficient Constraint Generation for Hierarchical Compaction, Proc. of the IEEE Custom Integrated Circuits Conference, pages 197−200, October 1987
  40. B.G.Boyer and N.Weste. Virtual Grid Compaction Using the Most Resent Layers Algorithm, Proc. of the IEEE International Conference on Computer-Aided Design, pages 92−93, September 1983
  41. D. G. Boyer, Split Grid Compaction for a Virtual Grid Symbolic Design System, Proc. of the IEEE International Conference on Computer-Aided Design, pp. 134−137, November 1987
  42. D. G. Boyer, Symbolic Layout Compaction Benchmarks Introduction and Ground Rules, Proc. of the IEEE International Conference on Computer Design, pp. 186−191, October 1987
  43. D. G. Boyer, Symbolic Layout Compaction Benchmarks Results, Proc. of the IEEE International Conference on Computer Design, pp. 209−217, October 1987
  44. D. G. Boyer, Symbolic Layout Compaction Renew, Proceedings of the 25th ACM/IEEE Design Automation Conference, pp. 383−389, IEEE Computer Society Press, June 1988
  45. D.N.Deutsch. Compacted channel routing, Proc. of the IEEE International Conference on Computer-Aided Design, pages 223−225, November 1985
  46. W.W. Dai and E.S. Kuh, Global Spacing of Building Block Layout, in С. H. Sequin, editor, VLSI'87. Elsevier Science Publisher В. V., Amsterdam, The Netherlands, 1987.
  47. T. Lengauer, On the Solution of Inequality System Relevant to IC-Layout. Journal of Algorithms, 5:408−421,1984
  48. Jurgen Doenhardt and Thomas Lengauer, Algorithmic Aspects of One-Dimensional Layout Compaction, IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-6, No.5, pp863−878, September 1987
  49. Y.-Z. Liao and C.K. Wong An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints, IEEE Transaction on Computer-Aided Design of Integrated Circuits an Systems, vol. CAD-2, No 2, pp. 62−69, April 1983
  50. M. Schlag, Y.-Z. Liao and С. K. Wong, An algorithm for optimal two-dimensional compaction of VLSI layouts, INTEGRATION, the VLSI journal, Elsevier Science Publisher В. V., Amsterdam, The Netherlands, 1983, pp. 179 209
  51. T.Yoshimura, A Graph Theoretical Compaction Algorithm, Proc. of the International Symposium on Circuits and Systems, June 1985, pages 1455−1458
  52. J.F.Lee and C.K.Wong A Performance-Aimed Cell Compactor with Automatic Jogs, IEEE Transaction on Computer-Aided Design, Vol.11, No. 12, December 1992, pages 1495−1507
  53. S.K.Dong, P. Pan, C.Y.Lo and C.L.Liu, Constraint Relaxation in Graph-Based Compaction, Proc of the 5th ACM/SIGMA Physical Design Workshop, April 1996, pages 256−261
  54. Sching L. Lin and Jonathan Allen, Minplex A Compactor that Minimizes the Bounding Rectangle and Individual Rectangles in a Layout, 23rd Design Automation Conference, 1986, pp. 123−129
  55. W.L.Schiele, Improved Compaction by Minimized Length of Wires, Proceedings of the 20th ACM/IEEE Design Automation Conference, pp. 121 127, 1983
  56. R.E.Tarian, Data structures and network algorithms, SIAM, 1983
  57. А. С. Плеханов, Метод минимизации задержек сигналов при сжатии топологии с учетом технологической сетки // Автоматизация и новые технологии, № 1,2001
  58. Э. Рейнгольд, Ю. Нивергельт, Н. Део, Комбинаторные алгоритмы теория и практика, издательство «Мир», Москва, 1980
  59. В.Липский, Комбинаторика для программистов, издательство «Мир», Москва, 1988
  60. W.Kim, J. Lee, Н. Shin, A New Hierarchical Layout Compactor Using Simplified Graph Models, 29th ACM/IEEE Design Automation Conference, 1992
  61. David Marple, M. Smulders, H Hegen, An Efficient Compactor for 45° Layout, Proc. of the 25th ACM/IEEE Design Automation Conference, pages 396−402, June 1988
  62. D.Marple, A Hierarchy Preserving Hierarchical Compactor, ACM/IEEE 27th Design Automation Conference, pages 134−140, 1990
  63. David Marple, M. Smulders and H Hegen, Tailor: A Layot System Based on Trapezoidal Corner Stitching, IEEE Transaction on Computer Aided Design, Vol.9, No. J, January 1990
  64. Jin-fuw Lee, Donald T. Tang, HIMALAYAS- A Hierarchical Compaction System with a Minimized Constraint Set, IEEE Transaction on Computer-Aided Design of Integrated Circuits an Systems, 1992
  65. So-Zen Yao, Chung-Kung Cheng, Debaprosat Dutt, Surendra Nahar and Chi-Yuan Lo, Cell-Based Hierarchical Pitch-Matching Compaction Using Minimal LP, ACM/IEEE 30th Design Automation Conference, pages 395−400, 1993
  66. C. S. Bamji and R. Varadarajan, Hierarchical Pitchmatching Compaction Using Minimum Design, Proceedings of the 29th Conference on Design Automation, pp. 311−317, IEEE Computer Society Press, June 1992.
  67. C.Bamji and R. Varadarajan, MSTC: A Method for Identifying Overconstraints during Hierarchical Compaction, ACM/IEEE 30th Design Automation Conference, pages 389−394, 1993
  68. W.Crocker, R. Varadarajan, C.Y. Lo, MACS: A Module Assemble and Compaction System, Proc. of the IEEE International Conference on Computer Design, pages 205−208, October 1987
  69. P. Eichenberger, Fast Symbolic Layout Translation for Custom VLSI Integrated Circuit, PhD thesis, Stanford University, April 1986
  70. P. Eichenberger and M. Horowitz, Topological Compaction of Symbolic Layouts for rectangular structures, IEEE International Conference on Computer-Aided Design, pages 142−145, November 1987
  71. G. Entenman, S. Daniel, A Fully Automatic Hierarchical Compactor, Proceeding of the 22nd Design Automation Conference, pages 69−75, June 1985
  72. С Kingsley, A Hierarchical Error-Tolerant Compactor, Proc. of the 21s' Design Automation Conference, pages 126−132, June 1984
  73. M Reichelt, W. Wolf, A Improved Cell Model for Hierarchical Constraint-Graph Compaction, Proc of the IEEE International Conference on Computer-AidedDesign, pages 482−485,1986
  74. Дж. Данцинг, Линейное программирование его применения и обобщения, издательство «Прогресс «, Москва 1966
  75. J. Dao, N. Matsumoto, Т. Hamai, С. Ogawa and S. Mori, A Compaction Method for Full Chip VLSI Layouts, 30th ACM/IEEE Design Automation Conference, 1993, pp. 407−412
  76. H. Kitazawa and K. Ueda, A look-ahead line search algorithm with high wireability for custom VLSI design, Proc. ISCAS, pp.1035−1038, 1985
  77. D. Dutt and C. Y. Lo, On minimal closure constraint generation for symbolic cell assembly, Proc. 28th ACM/IEEE Design Automation Conf, 1991, pp.736 739
  78. Peichen Pan, Sai-keung Dong, and C.L. Liu, Optimal Graph Constraint Reduction for Symbolic Layout Compaction, ACM/IEEE 30th Design Automation Conference, pages 401−406,1993
  79. D.E.Goodman A.Y.Tetelbaum and V.M.Kureichik, A Genetic Algorithm Approach to Compaction, Bin Packing and Nesting Problems, Technical Report #940 702, Case Center for Computer-Aided Engineering and Manufacturing Michigan State University, 1994
  80. E.Papadopoulou, Critical Area Computation for Missing Material Deffects in VLSI Circuits, IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No 5, May 2000
  81. C.-K.Cheng, X. Deng, Y.-Z.Liao and S.-Z.Yao, Symbolic Layout Compaction Uder Conditional Design Rules, IEEE Transaction on Computer-Aided Design, Vol. 11, No 4, April 1992
  82. P.Dood, J. Wawrzynek, E. Liu, R. Suaya, A Two-Dimensional Topological Compactor with Octagonal Geometry, 28th ACM/IEEE Design Automation Conference, pages 727−731,1991
  83. J.Valainis, S. Kaptanoglu, E. Liu, R. Suaya, Two Dimensional 1С Layout Compaction Based on Topological Design Rule Checking, IEEE Transactions on CAD oflCs and Systems, 9(3), March 1990
  84. А.В.Бондалетов, Двумерная упаковка со связями, Известия ТРТУ, Материалы Международной конференции «Интеллектуальные САПР», 1999
  85. W.Dai. B. Eschermann, E. Skuh and M. Pedram, Hierarchical Placement and Floorplaning in BEAR, IEEE Transaction on Computer-Aided Design, Vol. 8, No. 12,1989, pages 1335−1348
  86. A. V. Aho, M. R. Garey and J. D. Ullman, The transitive reduction of a directed graph, in SIAMJ. Comput., Vol.2, No. 2, pp. 131−137,1972
  87. J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North-Holland, New York, 1976.
  88. Andrew J. Harrison, VLSI Layout Compaction Using Radix Priority Search Trees, Proceedings of the 28th ACM/IEEE Design Automation Conference, pp. 732−735, ACM Press, June 1991.
  89. M.Barzaghi, F. Curatelli, D.D.Caviglia, G.M.Bisio, Symbolic Compaction of Digital CMOS Cells, IEEE, pages 222−225, vol. 1, May 1991
  90. C.Y.Lo and R Varadarajan, An 0(nl 5logn) 1-d Compaction Algorithm, ACM/IEEE 27th Design Automation Conference, pages 382−386, 1990
  91. G. Kedem, H. Watanabe, Graph Optimization Techniques for 1С Layout and Compaction, 2(fh Design Automation Conference, pages 113−120,1983
  92. G. Kedem, H. Watanabe, Graph Optimization Techniques for 1С Layout and Compaction, IEEE Trans. On CAD oflCs, Vol3, Nol, January 1984
  93. H.Watanabe, 1С Layout Generation and Compaction Using Mathematical Optimization, PhD Thesis, University of Rochester, 1984
  94. S.Gao, M. Kaufmann and F.M.Maley, Advances in Homotopic Layout Compaction, Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 273−282, ACM Press, June 1989.
  95. F.M.Maley, Compaction with automatic jog introduction, Chapel Hill Conference on VLSI, pages 261−283, May 1985
  96. C. W. Carpenter and M. Horowitz, Generating Incremental VLSI Compaction Spacing Constraints, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 291−297, IEEE Computer Society Press, June 1987.
  97. W.S.Scott, J.K.Ousterhout, Plowing: Interactive Stretching and Compaction in Magic, ACM/IEEE 21st Design Automation Conference, pp. 166−172, IEEE Computer Society Press, June 1984.
  98. J.K.Ousterhout, G.T.Hamachi, R.N.Mayo, W.S.Scott and G.S.Taylor, Magic: A VLSI Layout System, ACM/IEEE 21st Design Automation Conference, pp. 152 159, June 1984
  99. T. Hedges, W. Dawson and Y.E. Cho, Bitmap Graph Build Algorithm for Compaction, Proc. of the IEEE International Conference on Computer-Aided Design, pages 340−342, November 1985
  100. J. Do and W. Dawson, SPACER II: Well-Behaved 1С Layout Compactor, Proc of VLSI 85, pages 283−291
  101. K.Mehlhorn and S. Naher, A Faster Compaction Algorithm with Automatic Jog Insertion, IEEE Transaction on Computer-Aided Design, vol. 9, No 2, February 1990
  102. Akira Onozawa, Layout Compaction With Attractive and Repulsive Constraints, Proceedings of the 27th ACM/IEEE Design Automation Conference, pp. 369−374, ACM Press, June 1990.
  103. A.Onozawa, K. Chaudhary, E.S.Kuh, Performance-Driven Spacing Algorithm using Attractive and Repulsive Constraints for Submicron LSIs, IEEE Transaction on Computer-Aided Design, Vol. 14, June 1995, pages 707−719
  104. P.-Y. Hsiao and W.-S. Feng, An Edge-Oriented Compaction Scheme Based on Multiple Storage Quad Tree, Proc. of the IEEE International Symposium on Circuits and Systems, June 1988
  105. A.E. Dunlon, SLIM The translation of Symbolic Layouts into Mask Data, Proc. of the 17th Design Automation Conference, pages 595−602, Junel980
  106. Z.V. Apanovich and A.G. Marchuk Top-Down Approach to Technology Migration for Full-Custom Mask Layouts, Proceedings of the Eleventh International Conference on VLSI Design: VLSI for Signal Processing, 1998
  107. R.C.Mosteller, A.H.Frey and R. Suaya 2-D Compaction a Monte Carlo Method, Proc. of the Stanford Conference on Advanced Research in VLSI, 1987, pages 173−197
  108. Wayne H. Wolf, Robert G. Mathews, Jon A Newkirk, and Robert W.Dutton. Two-dimensional Compaction Strategies, Proc of the IEEE International Conference on Computer-Aided Design, pp. 90−91, September 1983
  109. W. Wolf, An Experimental Comparison of 1-D Compaction Algorithms, Chapel Hill VLSI Conference, pp. 165−180, 1985
  110. W. Wolf, Sticks Compaction and Assembly, IEEE Design & Test of Computers, pp. 57−63, June 1986
  111. T.M.Hsieh, H.W.Leong, C.L.Liu, Two-Dimensional Layout Compaction by Simulated Annealing, Proc. of the IEEE International Symposium on Circuits and Systems, June 1988
  112. E.G.Goffman and P.W.Shor, Average-case analysis of cutting and packing in two dimensions, Europenian Journal of Operational Research, Elsevier Science Publisher В. V., Amsterdam, The Netherlands, 1983, pp. 134−144
  113. J. Lee, A New Framework of Design Rules for Compaction of VLSI Layouts, IEEE trans, on CAD, vol.7, No 11, pages 1195−1204, November 1988
  114. W. Kim, J. Lee, and H. Shin, A New Hierarchical Layout Compactor Using Simplified Graph Models, Proceedings of the 29th Conference on Design Automation, pp. 323−326, IEEE Computer Society Press, June 1992
  115. L.-Y. Wang, Y.-T. Lai, B.-D. Liu and T.-C. Chang, Layout Compaction with Minimized Delay Bound on Timing Critical Path, Proc. of the International Symposium on Circuits and Systems, June 1993, pages 1849−1852
  116. L.-Y. Wang, Y.-T. Lai, B.-D. Liu and T.-C. Chang, A Graph-Based Simplex Algorithm for Minimizing the Layout Size and the Delay on Timing Critical Path, Proc. of the IEEE International Conference on Computer-Aided Design, November 1993, pages 703−708
  117. L.-Y. Wang, Y.-T. Lai, B.-D. Liu and T.-C. Chang, Performance-Directed Compaction for VLSI Symbolic Layouts, Computer-aided Design, 27(1), pp. 65−74, Elsevier Science, 1995
  118. Awashima, Sato and Ohtsuki, Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced Plane-Sweep Method TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1993.
  119. Ishima, Tsukiyama, On an Algorithm to Detect Positive Cycles in a Constraint Graph for Layout Compaction, T1EICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1991.
  120. S. E. Hambrusch, Y. Tu, New Algorithms and Approaches for 1—Dimensional Layout Compaction, Proceedings of New Results and New Trends in Computer Science, LNCS, Vol. 555, pp. 152−171, Springer, June 1991.
  121. D. G. Boyer, Process Independent Constraint Graph Compaction, Proceedings of the 29th Conference on Design Automation, pp. 318−322, IEEE Computer Society Press, June 1992
  122. Sai-Keung Dong, Graph-Based Algorithms for Floorplanning, Routing and Compaction, Technical Report, University of Illinois at Urbana-Champaign, Number UIUCDCS-R-94−1845, January 1994.
  123. Matthias, F.M.Stallmann, T.A.Hughes, Fast Algorithms for One-Dimensional Compaction with Jog Insertion, Algorithms and Data Structures, Third Workshop, Lecture Notes in Computer Science, Vol. 709, pp. 589−600, Springer, 11−13 August 1993
  124. Klau, and Mutzel, Optimal Compaction of Orthogonal Grid Drawings, IPCO: 7th Integer Programming and Combinatorial Optimization Conference, 1999.
  125. Klau, and Mutzel, Combining Graph Labeling and Compaction, GDRAWING: Conference on Graph Drawing (GD), 1999.
  126. Narayan Vikas, Computational Complexity of Compaction to Cycles, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 977−978, ACM-SIAM, January 17−19 1999.
  127. N.G.Sullivan and J.B.Rosenberg, Parallel Incremental Compaction Technical Report, Department of Computer Science, Duke University, Number Technical report DUKE-TR--1988--18,1988.
  128. Chen, and Lee, A Faster One-dimensional Topological Compaction Algorithm, ISAAC: 8th International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms), 1997.
  129. R. Andersonl, S. Kahan and M. Schlag, An 0(n log n) Algorithm for 1-D Tile Compaction, Graph-Theoretic Concepts in Computer Science, pp. 287−301, Springer, June 1990.
  130. A. A. J. de Lange, J. S. J. de Lange and J. F. Vink, A Hierarchical Constraint Graph Generation and Compaction System for Symbolic Layout, International
  131. Conference on Computer Design, VLSI in Computers and Processors, pp. 532 535, IEEE Computer Society Press, October 1989.
  132. A. Herrigel, J. Kamm and W. Fichtner, Macrocell-Level Compaction with Automatic Jog Introduction, International Conference on Computer Design, VLSI in Computers and Processors, pp. 536−541, IEEE Computer Society Press, October 1989.
  133. F.M.Maley, A Generic Algorithm for One-Dimensional Homotopic Compaction, Algorithmica, Vol. 6, pp. 103−128,1991.
  134. S.E.Hambrusch and H.-Y. Tu, New Algorithms for Minimizing the Longest Wire Length During Circuit Compaction, Algorithmica, 17(4), pp. 426−448, April 1997.
  135. Awashima, Sato and Ohtsuki, Optimal Constraint Graph Generation Algorithm for Layout Compaction Using Enhanced Plane-Sweep Method, TIEICE: IEICE Transactions on Communications/Electronics/Information and Systems, 1993.
  136. R.Okuda, T. Sato, H. Onodera, and K. Tamaru, An efficient algorithm for layout compaction problem with symmetry constraints, in Digest int’l. Conf. on Computer-Aided Design, 1989, pp. 148−153
  137. J.Royle, M. Palczewski, H. VerHeyen, N. Naccache, J. Soukrup, Geometrical Compaction in One Dimension for Channel Routing, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 140−145, IEEE Computer Society Press, June 1987.
  138. L.S.Nyland, S.W.Daniel, D. Rogers, Improving Virtual-Grid Compaction Through Grouping, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 305−310, IEEE Computer Society Press, June 1987.
  139. P.C.Shah, H.N.Mahabala, A New Compaction Scheme Based on Compression Ridges, Proceedings of the 24th ACM/IEEE Design Automation Conference, pp. 645−648, IEEE Computer Society Press, June 1987.
  140. G.Lakhani, R. Varadajan, A Wire-Length Minimization Algorithm for Circuit Layout Compaction, Proc. of the IEEE International Symposium on Circuits and System, 1987, pages 276−279
  141. Y.Shigehiro, T. Nagata, I. Shirakawa, I. Arungsrisangchai, H. Takahashi, Automatic Layout Recycling Based on Layout Description and Linear Programming, IEEE Transaction on Computer Design of Integrated Circuits and Systems, vol. 15, No. 8, August 1996.
  142. M.C.Utesch, A New Approach to Hierarchical Adaptation Using Sequence-Control Based on Cell Interactions, In 28th ACM/IEEE Design Automation Conference, 1991
  143. А.М.Марченко, М. А. Сотннков, Приближенный метод решения задачи коммивояжера//Труды НИИР, 1995, сс. 102−105.
  144. А.М.Марченко, В. П. Розенфельд, М. А. Сотннков Модифицированный силовой алгоритм планировки кристалла СБИС // Технология и конструирование в электронной аппаратуре. № 2, 1995, сс. 6−8.
  145. А.М.Марченко, А. П. Плис, М. А. Сотннков, И. Г. Топузов, Е. Г. Широ. Алгоритм уменьшения максимальной локальной плотности канала // Труды НИИР, 1998, сс. 55−59
  146. Е.Г.Березин, А. М. Марченко, А. С. Плеханов, В. П. Розенфельд, М. А. Сотннков, Е. Г. Широ, Гибридная модель трассировки соединений в ультра-БИС //Труды НИИР, 1998, сс. 49−54.
  147. A.Marchenko, A. Plis, E. Shiro, M. Sotnikov, I. Topouzov, P. McGuinness, Method and Apparatus for Channel-Routing of an Electronic Device // United States Patent, No: 6,477,692 Bl, Nov.5,2002
  148. A.Marchenko, A. Plis, M. Sotnikov, P. McGuinness, Method for channel routing and apparatus // United States Patent, No: 6,564,366 Bl, May.13,2003
  149. S.Even, Graph Algorithms, IIComputer Science Press, 1979
  150. В. А. Сынгаевский Е. Г. Широ1. Акт внедрениярезультатов диссертационной работы Сотникова Михаила
  151. Анатольевича «Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС», представленной на соискание ученой степени кандидата технических наук по специальности 05.13.12 «Системы автоматизации проектирования».
  152. Декан ЭКТ факультета Члены комиссии:
Заполнить форму текущей работой

На отлично!