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

• Гончаров, Денис Александрович
• кандидат технических наук
• 2004

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

ВВЕДЕНИЕ.

1. Управление проектированием в технологии программируемых логических интегральных схем (ПЛИС).

1.1. Роль ПЛИС в проектировании устройств.

1.2. Обзор архитектур и классификация ПЛИС.

1.2.1. Программируемые логические матрицы.

1.2.2. Программируемая матричная логика.

1.2.3. Программируемые коммутируемые матричные блоки.

1.2.4. Программируемые вентильные матрицы.

1.3. Управление проектированием в инструментальной среде MAX+PLUS II.

Выводы.

2. Алгоритмы логического синтеза.

2.1. Программируемые регулярные схемы.

2.2. Описание структуры логической ячейки.

2.3. Синтез логических функций общего назначения в ПЛИС.

2.4. Методы синтеза.

2.5. Синтез библиотечных модулей (макрофункций и мегафункций).

2.5.1. Счетчики.

2.5.2. Компараторы.

2.5.3. Мультиплексоры.

2.5.4. Комбинированная схема.

Выводы.

3. Реализация алгоритмов в ПЛИС.

3.1. Алгоритмы и их применение на этапе аппаратной реализации.

3.2. Синтез схем конечных автоматов (КА) с памятью.

3.3. Параллельное преобразование КА в ПЛИС.

3.3.1. Параллельное преобразование КА, полученных на сетевых моделях алгоритмов.

3.3.2. Параллельное преобразование КА для микропрограммных автоматов.

Выводы.

4. Выбор соединений в ПЛИС.

4.1. Предпосылки к разработке точного алгоритма выбора соединений.

4.2. Структура соединений.

4.3. Математическая модель массива межсоединений.

4.4. Последовательный комбинаторный метод выбора соединений.

4.5. Проблемы при размещении.

4.6. Метод выбора соединений на основе алгоритма системы различных представителей.

4.7. Алгоритм трассировки соединений в ПЛИС.

Выводы.

5. Применение технологии ПЛИС при проектировании авиационных распределенных информационных систем (РИС).

5.1. Архитектура авиационных РИС.

5.2. Интерфейсные модули.

5.3. Применение методов проектирования схем в ПЛИС.

5.3.1. Модуль А429-3-24.

5.3.2. Модуль ABB.

5.3.3. Модуль АКО.

Выводы.

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

АКТУАЛЬНОСТЬ ТЕМЫ

Развитие технологии производства средств вычислительной техники влияют на развитие и совершенствование средств проектирования.

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

Если сопоставить сроки разработки и создания реального проекта с уровнем: сложности 105 логических ячеек и/или Кбайт в 90-е годы и в начале 2000-х годов, то различие составляет два порядка: несколько лет в начале 90-х годов и два-три месяца в 2000 году.

В связи с ожидаемым ростом этих показателей; активизировались работы в . области создания методологий проектирования систем? на кристалле. В рамках: этих систем необходимо решать как системные задачи из области "архитектуры", так и конкретные задачи проектирования, опирающиеся на существующую элементную базу.

За последнее десятилетие опробованы различные технологии. Весь накопленный опыт суммируется в современных интегрированных технологиях фирм ALTERA, XILINX, ACTEL, ATMEL, CYPRESS и еще десятка фирм, создающих системы на кристалле.

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

Все эти ожидания и значительный прогресс в создании информационных систем относится к интегральным технологиям создания встроенной и распределенной аппаратуры на основе программируемых логических интегральных схем (ПЛИС).

Практическое применение САПР MAX+PLUS II, FOUNDATION и LIBERO выявило проблемы в следующих областях.

1. Методы синтеза регулярных схем.

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

2. Реализация схем конечных автоматов в ПЛИС.

Канонические методы синтеза схем конечных автоматов (Лазарев В.Г.,

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

3. Алгоритм размещения и трассировки.

Исследования показали, что на этапе размещения и трассировки с высокой вероятностью возникают отказы вследствие ограничений используемых в САПР алгоритмов. ф Таким образом, работа, посвященная разработке методов проектирования цифровых устройств на ПЛИС, АКТУАЛЬНА и представляет научный и практический интерес.

ПРЕДМЕТОМ ИССЛЕДОВАНИЯ диссертационной работы являются математические методы, алгоритмы и их применение при проектировании распределенных информационных систем на ПЛИС фирмы ALTERA с использованием САПР MAX+PLUS II.

ЦЕЛЬ РАБОТЫ. Целью диссертационной работы является разработка методов проектирования цифровых устройств на ПЛИС.

Для достижения этой цели решались следующие задачи. 1. Разработка методов для этапа логического проектирования на ПЛИС:

- разработка методов синтеза регулярных схем;

- разработка методов синтеза и преобразований конечных автоматов.

2. Разработка методов для этапа конструкторского проектирования на ПЛИС:

- разработка методов размещения функций по логическим ячейкам ПЛИС;

- разработка методов распределения контактов;

- разработка методов трассировки соединений.

МЕТОДЫ ИССЛЕДОВАНИЯ. Методами исследования являются теория регулярных языков, теория алгоритмов, теория графов, комбинаторика и теория множеств, теория конечных автоматов, теория сетей Петри и теория программирования.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем.

1. Разработаны методы для этапа логического проектирования на ПЛИС:

- методы синтеза регулярных схем в ПЛИС, которые позволяют улучшить параметры схемы;

- метод алгоритмического описания ячейки ПЛИС на основе регулярных языков, который может использоваться на этапе логического синтеза;

- метод преобразования конечных автоматов в систему эквивалентных параллельно работающих конечных автоматов;

- метод синтеза конечных автоматов, направленный на минимизацию количества функций и применение параметризируемых модулей.

2. Разработаны методы для этапа конструкторского проектирования на ПЛИС:

- математическая модель матрицы межсоединений на основе графов связности;

- алгоритм выбора соединений на основе системы различных представителей;

- алгоритм распределения контактов, основанный на решении задачи о назначении.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ представляют:

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

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

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

4. Разработанные методы и алгоритмы применялась при проектировании авиационных интерфейсных модулей в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76, БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов, что подтверждается актом внедрения.

ПУБЛИКАЦИИ. По материалам диссертации опубликовано восемь печатных работ.

• АПРОБАЦИЯ РАБОТЫ. Обсуждение материалов работы производилось на

XXXI научной и учебно-методической конференции Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПб ГУ ИТМО), XXXII научной и учебно-методической конференции СПб ГУ ИТМО и Шестой межведомственной научно-технической конференции в филиале Военно-космической Краснознаменной Академии (г. Пушкин).

ЭФФЕКТ ОТ ИСПОЛЬЗОВАНИЯ результатов данной работы заключается в сокращении числа ячеек и максимальной задержки в ПЛИС при разработке распределенных информационных систем на 20-30% по сравнению с методами, ^ использующимися в САПР стандартной поставки.

ОСНОВНЫЕ ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ.

1. Методы синтеза регулярных схем в ПЛИС.

2. Метод алгоритмического описания ячейки ПЛИС.

3. Метод преобразования конечных автоматов в ПЛИС.

4. Алгоритм выбора соединений.

5. Алгоритм распределения контактов. СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ

Диссертация состоит из введения, , пяти глав, заключения и списка литературы (53 наименования). Материал изложен на 139 страницах машинописного текста и содержит 112 рисунков и 23 таблицы.

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

Выводы

1. Рассмотрены архитектуры авиационных РИС, показано, что существенная часть оборудования относится к интерфейсным блокам.

2. Приведена обобщенная структура интерфейсного модуля.

3. Приведены примеры применения разработанных методов проектирования в технологии ПЛИС для реализации авиационных интерфейсов. Показано, что применение методов дает существенное улучшение параметров (20-30%) ПЛИС.

ЗАКЛЮЧЕНИЕ

В работе получены следующие результаты.

1. Разработаны методы и алгоритмы для этапов проектирования цифровых устройств на ПЛИС:

- методы синтеза регулярных схем;

- методы синтеза и преобразований конечных автоматов;

- алгоритм выбора соединений;

- алгоритм распределения контактов.

2. Предложен метод алгоритмического описания структуры ПЛИС на основе регулярных языков, который используется на этапе логического синтеза.

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

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

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

6. На основе разработанного точного метода выбора соединений написана программа, выполняющая трассировку соединений.

7. Методы и алгоритмы применялись при разработке авиационных интерфейсных модулей в рамках работ ЗАО ОКБ "Русская Авионика" для гражданских (ИЛ-76, БЕ-200, ТУ-154) и военных (СУ, МИГ) самолетов, что подтверждается актом внедрения.

Список литературы диссертационного исследования кандидат технических наук Гончаров, Денис Александрович, 2004 год

1. Грушвицкий Р. И., Мурсаев А. X., Угрюмов Е. П. Проектирование систем на микросхемах программируемой логики. - СПб.: БХВ-Петербург, 2002. - 608 с.

2. Соловьев В.В., Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия-Телеком, 2001. - 636 с.

3. МАХ7000. Programmable Logic Device Family. ALTERA, 2003. - 85 с.

4. FLEX 1 OK. Embedded Programmable Logic Device Family. ALTERA, 2003. -128 c.

5. APEX 20K. Programmable Logic Device Family. ALTERA, 2004. - 117 c.

6. Антонов А.П., Мелехин В.Ф., Филлипов A.C. Обзор элементной базы фирмы "ALTERA". СПб.: "ЭФО", 1997. - 110 с.

7. XILINX Data Book. XILINX, 2003. - 210 с.

8. Мальцев П.П., Гарбузов Н.И. Программируемые логические ИМС на КМОП-структурах и их применение. -М.: Энергоатомиздат, 1998. — 160 с.

9. ACTEL Data Book. ACTEL, 2003. - 320 с.

10. ATMEL Data Book. ATMEL, 2003. - 126 c.1 l.CYPRESS Data Book. CYPRESS, 2003. -212 c.

11. Комолов Д.А., Мяльк P. А., Зобенко А. А., Филиппов A.C. Системы автоматизированного проектирования фирмы ALTERA MAX+PLUS II и Quartus II. M.: Радиософт, 2002. - 352 с.

12. З.Антонов А.П. Язык описания цифровых устройств AHDL. М.: РадиоСофт, 2002.- 224 с.

13. Бибило П.Н. Основы языка VHDL. М.: Солон-Р, 2000. - 200 с.

14. VHDL для моделирования, синтеза и формальной верификации аппаратуры / пер с англ. М.: Радио и связь, 1995. - 256 с.1 б.Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. -250 с.

15. Холл М. Комбинаторика. М.: Мир, 1970. - 424 с.

16. Рыбников К.А. Введение в комбинаторный анализ. М.: Московский университет, 1972. -254 с.

17. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. - 476 с.

18. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. -264 с.

19. Шалыто А.А. SWITH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. - 628 с.

20. Котов В.Е. Сети Петри. М.: Наука, 1984. - 160 с.

21. Юдицкий С.А., Мачергут В.З. Логическое управление дискретными процессами. М.: Машиностроение, 1980 — 300 е.

22. Luciano Lavagno. Models of Computation for Embedded System Design, 1998. www.polito.it.

23. System C, 2002. www.systemc.org.

24. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1979. — 348 с.

25. Варшавский В.И. и др. Апериодические автоматы. М.: Наука, 1976. — 420 с.

26. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. -М.: Энергия, 1989. 326 с.

27. Девятков В.В. Программная реализация управляющих алгоритмов. — М.: Наука, 1980.-210 с.

28. Вавилов Е.М., Портной Т.П. Синтез схем ЭЦМ. М.: Советское радио, 1963. -430 с.

29. Чу Я. Организация ЭВМ и микропрограммирование. М.: Мир, 1975. - 592 с.

30. Ахо А., Ульман Дж. Д. Вычислительные аспекты СБИС. М.: Радио и связь, 1990.-306 с.

31. Ахо А., Ульман Дж. Д. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.-200 с.

32. Миллер Р. Теория переключательных схем. Т.2. М.: 1971. - 304 с.

33. Ахо А., Ульман Дж. Д. Теория синтаксического анализа, перевода икомпиляции. М. Мир, 1972. - 612 с.

34. Шило В.JI. Популярные микросхемы ТТЛ. М. Аргус, 1993. - 64 с.

35. Фридман А., Менон П. Теория и проектирование переключательных схем. -М.: Мир, 1978.-350 с.

36. ГОСТ 18977-79. Комплексы бортового оборудования:самолетов и вертолетов. Типы функциональных связей. Виды и уровни электрических сигналов. М.: Издательство стандартов, 1979. — 10 с.

37. РТМ 1495-75. Обмен информацией двуполярным кодом в оборудовании летательных аппаратов, 1975. 124 с.

38. ГОСТ 26765.51-86. Интерфейс магистральный параллельный МПИ. Системы электронных модулей. М.: Издательство стандартов, 1986. - 30 с.

39. ГОСТ 26765.52-87. Интерфейс магистральный последовательный. Системы электронных модулей. М.: Издательство стандартов, 1987. - 30 с.

40. Мячев А.А. Интерфейсы средств вычислительной техники. М.: Радио связь, 1993.-354 с.

41. Скорубский В.И., Кордонов Г.Н. Синтез схем МПА на основе счетчиков и сдвигателей. СПб.: Полиграфический институт, 2003.

42. Гончаров Д. А. Микросхемы программируемой логики // Изв. вузов. Приборостроение. 2003. Т.46, № 2. С.24-28.

43. Гончаров Д.А., Скорубский В.И. Стратегия частичных расширителей // Современные технологии. Сборник научных статей. СПб.: СПб ГУ ИТМО, 2003. С.146-152.

44. Гончаров Д.А., Скорубский В.И. Алгоритмы выбора соединений в ПЛИС // Научно-технический вестник СПб ГУ ИТМО. Вып. 10. Информация и управлениев технических системах. 2003. С.39-49.

45. Гончаров Д.А., Скорубский В.И, Жвариков В.А. Алгоритмы выбора соединений в ПЛИС. СПб.: Санкт-Петербургский государственный политехнический университет, 2003 (в печати).

46. Гончаров Д.А., Скорубский В.И. Эффективность реализации регулярных схем в ПЛИС // Шестая межведомственная научно-техническая конференция. Тезисы докладов. Филиал Военно-космической Краснознаменной Академии им. А.Ф. Можайского. 2003. С. 163-164.

47. Гончаров Д.А., Скорубский В.И. Стандартные библиотечные модули // Изв. вузов. Приборостроение. 2004 (в печати).

48. Глушкин Е.З., Рубин Г.С., Гончаров Д.А. УСТРОЙСТВО ВВОДА-ВЫВОДА. Свидетельство на полезную модель № 24296 от 21.01.2002.

49. Глушкин Е.З., Рубин Г.С., Гончаров Д.А. УСТРОЙСТВО ВВОДА-ВЫВОДА. ПАТЕНТ на изобретение № 2221267 от 10.01.2004.1. Текст программы CORE.

50. SRD14. .0. = srd.q[15. . 1] ; SRD15 = DIN Sc chin;

51. CTB1F = (ctb.q4 Sc ctb.q3 Sc ctb.q2 Sc ctb.ql & ctb.qO);ctp.data . = DORAM[9. . 8] ;ctp.clock = CLK;1. Ctp.sload = RDRS;ctp.cnten = WRRD Sc 'start;ctp.sclr = WRRD Sc start Sc chin;ctp.aclr = RESET;

52. DORAM13 & RDRS; rdy.clock = CLK; rdy.enable = RDRS #

53. WRRD & ENACHG & Ictp.qO & ctp.ql & Irdy.qO & chin #

54. VRDY3.0. = vrdy.q[3. .0] ; VRDY[13.4] = GND; VRDY14 = GND; VRDY15 = GND;--Vrdyena;• NCH 4 . . 0. = vrdy.q[4. .0] ;

55. RSRAM5.0. RSRAM[7.6] RSRAM [9 . .8] RSRAM10 RSRAM11 RSRAM12 RS RAM13ctb.q . ; = GND; = ctp.q [] ; = par.q [] ; = nbl .q [] ; = enatr .q [] ; = rdy.q [] ;

56. RSRAM 15 . . 14. = GND; END;

57. PUT; INPUT; INPUT; INPUT; INPUT; INPUT; OUTPUT;1. VARIABLE

58. EQ00(WIDTH-1).0. : NODE; upeq[(WIDTH).0] : NODE; BEGINupeq0. = VCC;

59. FOR i IN 0 TO WIDTH-1 GENERATEout1. = TFFE( EQ00i. $ GND, GLOBAL( CLK), GLOBAL( RESET), EQ00 [i] = ! CLR & LOAD & IN[i] Sc !out[i] --(sload)

60. CLR Sc 'LOAD & COUNT Sc upeq1. --(up)

61. CLR & out i. ; --(sclr) upeq[i + l] = upeq1. & out [i];1. END GENERATE; END;1. VCC, VCC);1. Текст программы AVTPETRI.

62. CLUDE "lpmdf f.inc"; INCLUDE "cntmod.inc"; INCLUDE "cmpalb";1. SUBDESIGN cpwm (1. D15.0. WRT[7.0] WE1.PUT INPUT INPUT1. CLK : INPUT;1. RESET : INPUT;1. PWMOUT7.0. : OUTPUT;

63. PWMOUT. = cmpl [] & RESET; END;cntnod with (LPMWIDTH=10); lpmdff with (LPMWIDTH=10); lpmdff with (LPMWIDTH=10); cmpalb with (WIDTH=10);

64. Ниже приведен текст модуля CNTMOD из разработанной библиотеки. Выражение строится таким образом, что число термов не зависит отразрядности счетчика.mod) терм для сброса триггера при достижении заданного значения; (up) - терм для инкремента.

65. CLUDE "lpmcounter"; PARAMETERS1. WIDTH = 15,

66. MODUL = B"0110000000000001";считать будет от 0 до MODUL-1)1. SUBDESIGN cntmod (1. CLK RESET1. OUT(WIDTH-1).0.1. VARIABLE

67. EQOO{WIDTH-1) mdl[WIDTH.0. M [WIDTH.0] MO[WIDTH.0] T[WIDTH.0] pmod[WIDTH.0] BEGIN1.PUT; INPUT; OUTPUT;0. : NODE; NODE ;

68. NODE; -- M= out2 & outl & loutO; (б) до какого считать NODE; — MO до какого считать начиная со старших разрядов NODE; -- Т - произведение для инкремента cnt2 = cntl & cntO; : NODE;

69. ASSERT (MODUL>2A(WIDTH-1))

70. REPORT "Значение MODUL должно быть больше 2Л(WIDTH-1)!" SEVERITY INFO;mdl . = MODUL-1;

71. M0. = VCC; pmod[0] = VCC; T[0] = VCC;

72. FOR i IN 0 TO WIDTH-1 GENERATE

73. M i + 1. = M1. & {out[i] & mdl[i] # !out[i] & !mdl[i]); T [i + 1] = T [i] & out [i] ; pmod[i+l] = pmodti] & mdl [i]; END GENERATE;-- обратное произведение модуля MO1. MOWIDTH. = VCC;

74. FOR i IN WIDTH-1 TO 0 GENERATE

75. MO 1. = MO i + 1. & (out [i] & mdl [i] # !out[i] & !mdl[i]); END GENERATE;out 0. = TFFE( EQ00[0] $ GND, GLOBAL( CLK), GLOBAL( RESET), VCC, VCC) ; if mdl[0] then EQ00[0] = VCC;else EQ000. = !(M[WIDTH]);end if;

76. FOR i IN 1 TO WIDTH-1 GENERATEout1. » TFFE( EQ00i. $ GND, GLOBAL( CLK), GLOBAL( RESET), VCC, VCC) if mdl[i] then EQ00[i] = T[i] # M[WIDTH];elsif pmod1. then EQ00i. = T[i] & !(MO[i]); else EQ00[i] = T[i] ;end if;1. END GENERATE;1. END;

77. Ниже приведен текст модуля CMPALB из разработанной библиотеки. Компаратор предназначен для сравнения двух двоичных кодов и выдачи сигнала "меньше".1. PARAMETERS (1. WIDTH = 5;1. SUBDESIGN cmpalb (