автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства экспериментального проектирования архитектуры ЭВМ и микропроцессоров

Р Г П ОТ РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ

_ >; г ■ , • ■ ' ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР и '.iL.lt

На правах рукописи

МАРЧУК Александр Гурьевич

Методы и средства экспериментального проектирования архитектуры ЭВМ и микропроцессоров

Специальность 05.13.11 - математическое и программное- обеспечение вычислительных машин, комплексов, систем и сетей

Диссертация на соискание ученой степени доктора физико-математических наук (в форме научного доклада)

Новосибирск 1993

Работа выполнена в Институте систем информатики Сибирского отделения Российской академии наук и Вычислительном центре СО АН СССР

Официальные оппоненты:

доктор технических наук, член-корреспондент РАН Левин В.К. доктор технических наук, член-корреспондент РАН Васьков С.Т. доктор физико-математических наук, профессор Ильин В. П.

Ведущая организация:

Институт точной механики и вычислительной техники РАН, г. Москва

Защита диссертации состоится " 199^ г.

в " " часов на заседании Специализированного совета Д002.10.02

по адресу: 630090, Новосибирск-90, пр. ак. Лаврентьева. 6

С диссертацией можно ознакомиться в библиотеке ВЦ СО РАН (пр. Лаврентьева, 6)

Диссертационный доклад разослан ".

Ученый секретарь Специализированного совета

Д002.10.02, к. т.н. Г.И.Забиняко

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

1. Выработка общих архитектурных принципов и решений по созданию параллельных архитектур, ориентированных на различные классы задач.

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

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

4. Создание языка и программных средств высокого уровня, адекватного предмету исследования и разработки - архитектуре, и методологии экспериментальных разработок.

5. Выработка методологии программных средств проектирования сверхбольших интегральных схем типа "кремниевый компилятор" и реализация такого подхода.

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

Научная новизна выполненных работ и предложенных решений состоит:

- в постановке задачи обеспечения соответствующими методами и высокоуровневыми средствами фазы экспериментальных исследований архитектуры компьютеров и анализе наиболее существенных черт этой задачи [5. 7, 17, 36];

- в предложении, анализе и реализации новой параллельной архитектуры, основанной на асинхронных потоковых взаимодействиях разнородных иерархически построенных модулей [4, 18, 20, 23. 31. 38. 56];

- в создании подхода к построению базового программного обеспечения параллельных систем предложенной архитектуры [15, 21. 24]:

- в исследовании языковых аспектов проблемы описания архитектуры, создании средств описания архитектуры, в том числе параллельной, создании и исследовании языка описания архитектуры [3. 5. И. 28. 32, 45];

- в выработке методологии построения систем САПР СБИС типа "кремниевый компилятор", экспериментальной реализации кремниевого компилятора [27, 29, 41. 47, 53];

- в создании новых и модификации существующих алгоритмов решения отдельных задач САПР СБИС [29, 44, 51].

Ряд работ развивался параллельно с аналогичными работами других исследователей в стране и за рубежом, и научные результаты в отдельных аспектах получены близкие или родственные. Это касается, в частности, транспьютерного направления в архитектуре, по которому автором диссертации независимо были выработаны основные концепции, а после знакомства с результатами по архитектуре компьютеров фирмы Inmos была перенята терминология "транспьютер". В работах по языку описания архитектуры автором независимо были получены результаты, близкие к идеям, которые были реализованы в языке VHDL. В предложенных автором диссертации подходах к реализации кремниевого компилятора также имеются моменты, близкие к подходам коллег из других стран.

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

бота велась в рамках Временного научно-технического коллектива (ВНТК) СТАРТ, созданного ГКНТ СССР для опережающих фундаментальных исследований в области архитектуры ЭВМ и интеллектуального программного обеспечения. Автор диссертации возглавлял ряд архитектурных и программистских работ, в частности разработку процессоров Кронос и рабочих станций Кронос-2. бЯБ, разработку системы программирования Поляр, разработку САПР СБИС и проектирование 32-разрядного микропроцессорного набора. Задание ВНТК СТАРТ выполнил, что подтверждено актами испытаний и решением Межведомственной комиссии по приемке работ.

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

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

Апробация. Результаты исследований докладывались на Всесоюзных конференциях и симпозиумах: Конференция по методам трансляции - Новосибирск, 1981: Высокопроизводительные вычислительные системы - Москва, 1981; Распараллеливание обработки информации - Львов, 1983; - Иверси-85, Гагра. 1985; САПР ЭВМ и БИС-86 - Ереван, 1986, Душанбе, 1987; Автоматизация конструк-

торского проектирования РЭА и ЭВА - Пенза, 1988; Высокопроизводительные вычислительные системы - Таллинн, 1988; САПР СВТ-89 - Ленинград, 1989 и некоторых других; а также на международных конференциях: Sixth Symposium on Microcomputer and Microprocessor Applications - Budapest October, 1989; Euro ASIC'92 - Paris June 1-5, 1992; Seventh Symposium on Microcomputer and Microprocessor Applications - Budapest. April 1992 и на Конгрессе ИФИП (IFIP 11th World Computer Congress) - San Francisco, USA. 1989.

Отдельные части работы докладывались на семинарах Вычислительного центра СО АН СССР - Новосибирск; Института точной механики и вычислительной техники - Москва; Института кибернетики - Таллинн; INRIA - Paris; University of Utah - Salt Lake City; MCNC - Raleigh; ГКНТ СССР - Москва; НПО "Импульс" - Се-веродонецк; НПО "Микропроцессор" - Киев; НПО "Интеграл" -Минск; НИИ ЭВМ - Минск; НИИТТ - Москва и др.

По тематике диссертации под руководством автора защищены 2 кандидатские диссертации (руководство одной из них совместное) .

Публикации. По теме диссертации автором опубликовано 57 работ, в том числе две монографии, обе в соавторстве.

Личный вклад автора. Постановки задач и основные идеи в совместных статьях, приведенных в списке публикаций, принадлежат автору диссертации, за исключением монографии [12]. в которой автор написал Гл. 1, что отмечено во введении, а также работ [4, 8. 13. 18, 20. 31. 35. 36, 40, 56] по проекту МАРС, исходные идеи по концепции которого были предложены Г. И.Марчу-ком и В.Е.Котовым, а сама многолетняя работа носила коллективный характер, в которой автор диссертации возглавлял определенную часть.

Работа [50] носит обзорный характер, в работах [22, 33, 49] основные заслуги по реализации систем принадлежат соавторам.

- 8 -ГЛАВА 1

Обзор основных выполненных работ и полученных результатов

В работе Г.И.Марчука и В.Е.Котова [Мар78] была сформулирована концепция создания и развития параллельной архитектуры МАРС, положившая начало многолетней работы целого коллектива и автора диссертации в частности. Эта концепция вобрала в себя много передового и перспективного, существовавшего на конец 70 -х гг. В отличие от других аналогичных концепций и проектов, проект МАРС обозначает целый спектр архитектурных возможностей и не ограничивает исследователей и разработчиков в стов.

Автор диссертации принимал активное участие во всех разработках. проводившихся в рамках проекта МАРС, и сделал вклад в архитектуру и реализацию каждой. К таким разработкам относятся:

- суперкомпьютер МАРС-М;

- мультипроцессор с транспьютеро-подобной организацией МАРС-Т;

- 32-разрядный микропроцессорный набор, предназначенный для создания рабочих станций и параллельных систем.

Параллельный потоковый суперкомпьютер МАРС-М [4. Виш82] был создан для наустов.

Автор диссертации принимал активное участие во всех разработках, проводившихся в рамках проекта МАРС, и сделал вклад в архитектуру и реализацию каждой. К таким разработкам относятся:

- суперкомпьютер МАРС-М;

- мультипроцессор с транспьютеро-подобной организацией МАРС-Т;

- 32-разрядный микропроцессорный набор, предназначенный для создания рабочих станций и параллельных систем.

Параллельный потоковый суперкомпьютер МАРС-М [4, Виш82] был создан для научно-технических расчетов. Он представлял собой высокопараллельную систему, состоящую из специализированных подсистем, взаимодействующих через асинхронные каналы. Компьютер МАРС-М состоит из 4 подсистем:

- подсистемы управления, выполняющей основные функции по

интерпретации инструкций и обеспечению управляющими потоками другие подсистемы;

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

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

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

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

Работа по разработке МАРС-М выполнялась с 1979 г., реализация осуществлялась в кооперации с ИТМ и ВТ, НФ ИТМ и ВТ, СКБ ВТ и рядом заводов МРП.

Другая концепция была опробована в проекте МАРС-Т. Упор в архитектуре был сделан на создание высокоэффективной мультипроцессорной организации системы через отработанные в компьютере МАРС-М асинхронные каналы. При этом обрабатывающими модулями являются более традиционные процессорные элементы, состоящие из пары процессор - память. Была предложена модель параллельных вычислений, наиболее адекватная заложенным архитектурным принципам и формализующая распределенное потоковое взаимодействие процессов. На компьютере МАРС-Т был проведен ряд содержательных экспериментов по пропуску параллельных программ, в целом подтвердивших перспективность предложенной архитектуры. Работа по созданию МАРС-Т, также как и предыдущая работа по МАРС-М, дали возможность автору диссертации сформулировать концепцию транспьютерной (транспьютероподобной) архитектуры [23. 38].

Мультипроцессор МАРС-Т состоит из нескольких процессоров (использовались процессоры Кронос-2.6 [Куз86]), взаимодействующих между собой, с общей памятью и внешним окружением через специально реализованную систему асинхронных каналов. Каждый

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

Макет МАРС-Т был реализован в течение 1985-1987 гг. при поддержке со стороны НПО "Импульс" (Северодонецк) и совместно с СКВ ВТ СО АН.

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

Научный вклад автора диссертации в работы по архитектуре заключается не только в созданных макетах и экспериментальных системах, но и в опубликованных научных исследованиях по архитектуре, предложенных подходах, концепциях и технических решениях. Кроме того, существенными видятся работы по языковому и инструментальному обеспечению проектов, выполненные автором совместно с коллегами под его руководством [5, 11, 22, 29].

В области архитектуры параллельных компьютеров было исследовано следующее:

- общая архитектура потокового иерархического типа, примененная в суперкомпьютере МАРС-М [4, 8, 13, 18];

- разнообразные способы применения асинхронных каналов в параллельных вычислительных системах [15. 17, 23, 31, 38, 56];

- транспьютерное направление в архитектуре параллельных

- И -

компьютеров [23, 38];

- архитектура мультипроцессор транспьютерополобного типа МАРС-Т [31. 36].

Для обоснования параллельной архитектуры, основывающейся на системе асинхронных каналов, была предложена и исследована модель параллельных вычислений [3, 15]. Был предложен подход к созданию ядра операционной системы для таких систем и базовая система программирования [21, 24].

Работы в области архитектуры потребовали от автора диссертации углубленного изучения формальных аспектов, относящихся к описанию объекта проектирования и исследования. В работах автора [1. 3, 5] была сформирована концепция языка описания архитектуры параллельных вычислительных систем.

Дальнейшее развитие концепции языка описания архитектуры привело к созданию языка программирования Поляр [9, И. 28. 32]. В отличие от предшествующих подходов, модель вычислений приобрела законченный характер и была проанализирована в ряде работ автора и коллег [26. 45. Кре87]. Более строгой стала семантика. и главным нововведением стала система рекурсивной типизации. на базе которой были сформированы структуры данных языка Поляр. Анализу свойств рекурсивных типизованных структур данных были посвящены работы [37, 45].

Язык Поляр был реализован [22, 33] и использовался в экспериментальных работах по кремниевой компиляции. Использование Поляра как самостоятельного языка программирования оказалось непрактичным,, что вызвало разработку системы Поляр в виде расширения стандартного языка программирования С. Сделано это было до появления языка С++ и активного перехода программистской общественности на его использование, однако цели расширения С объектно-ориентированными возможностями были близкими, хотя способ решения данной задачи - принципиально иным. Реализованной система использовалась в течение длительного времени в работах по кремниевой компиляции и САПР СБИС и продолжает использоваться до сих пор. В качестве основных достоинств Поляра и Поляр-расширения С можно упомянуть следующие:

- 12 -

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

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

- эффективно реализованные структурные операции и формирователи, объектная концепция сборки мусора;

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

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

Микроминиатюризация электроники и переход к микропроцессорным и мультимикропроцессорным системам поставили ряд новых задач перед создателями новых архитектур. К таким задачам относятся:

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

- создание средств быстрой, эффективной и бездефектной разработки сверхбольших интегральных схем;

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

- создание средств модульного проектирования,микропрограммирования и программирования узлов компьютеров и систем.

В этом направлении автором'диссертации, совместно с коллегами, велись работы с 1983 г. и был получен ряд результатов [29. 41. 47, 52, 53]. В частности:

- 13 -

- был создан ряд экспериментальных систем проектирования СБИС с элементами кремниевой компиляции;

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

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

- системы были опробованы при решении практических задач проектирования СБИС и микропроцессоров.

ГЛАВА 2

Архитектура параллельных вычислительных систем

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

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

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

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

Концептуальные основы построения систем МАРС в рамках выполнявшегося проекта были изложены в работах [4, 8]. Архитектурные и технические решения описаны в [13, 18, 20, 36]. Полученные результаты и достижения опубликованы в [31, 35, 56].

Модель вычислений, применяемая в предлагаемой архитектуре

Используемая в исследованиях модель вычислений - это распределенные вычисления без общей памяти с потоковым взаимодействием процессов. Это означает, что каждый процесс развивается на своей локальной памяти, возможно на своем процессоре, а взаимодействие осуществляется потоками данных, передаваемыми через так называемые программные каналы [21]. Программный канал реализует структуру -типа "очередь" конечной глубины, является однонаправленным и в общем случае его концы соединяют разные процессоры или модули.

Наиболее близкой к принятой в архитектуре МАРС является модель вычислений, зафиксированная в языке Оккам и принятая как базовая в транспьютерах фирмы 1НМ0Б [Мау84]. Основным отличием является то. что оккамовские каналы реализуют безбуферный синхронный обмен "рандеву", кроме того. Оккам фиксирует единственность процессов источника и получателя для каждого канала. Предложенная нами модель может эффективно имитировать семантику Оккама (равно как и наоборот), поэтому она не уже, а потоковые механизмы дают более гибкие и естественные механизмы для целого ряд применений.

Наиболее полно предлагаемая модель вычислений опубликована в [21]. см. также [23, 24].

- 15 -

Общие архитектурные и структурные решения

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

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

Изложенный подход в разных видах применялся при создании компьютеров МАРС-М и МАРС-Т. В системе МАРС-М [4] ориентация была принята на максимально глубокое распараллеливание процессов интерпретации потоков команд в задачах научно-технических расчетов (векторные алгоритмы, специальные функции. быстрые преобразования). В противоположность этому МАРС-Т [36] разрабатывался как мультипроцессор, ориентированный на нечисловые задачи, характерные для проблем системного программирования. Разными были также уровни распараллеливания (уровень отдельных функциональных конвейерных устройств - в МАРС-М и процессорный уровень - в МАРС-Т).

Общие принципы организации параллельных систем с архитектурой МАРС и результаты выполненных экспериментальных работ опубликованы в [35, 36].

- 16 -

Создание и использование спецпроцессоров средствами транспьютерной архитектуры

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

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

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

Исследованиями автора 12, 4. 8. 17, 23] были охвачены три популярных вида спецпроцессоров: параллельные конвейерные, ориентированные на научно-технические вычисления; систолические структуры; спецпроцессоры, поддерживающие средства интеллектуализации.

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

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

Один подход к операционной системе для распределенных вычислительных систем

По мнению автора, операционные системы для ЭВМ с архитектурой МАРС и транспьютерной организацией должны проектироваться принципиально иначе, чем традиционные, так как существующие ОС обычно ориентированы на конкретную архитектуру и систему команд (DOS IBM, VMS) либо на конкретный язык программирования и модель вычислений, связанную с этим языком (напр. UNIX). "Кроме того, стандартные реализации ОС навязывают решения. существенно ограничивающие разработчиков систем программирования. особенно систем, ориентированных на параллельные и асинхронные вычисления. К таким решениям относятся способы управления процессами и средства их взаимодействия, организация файловой системы, оверлеи, виртуальная память и др.

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

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

распределения ресурсов позволит избежать интерференции с алгоритмами планирования, применяемыми в конкретных системах программирования (СП), реализованных на данных ВМ.

Ядро ОС предоставляет также стандартное средство коммуникации и синхронизации - виртуальный канал (ВК). Виртуальные, или программные, каналы - это статические образования, порождаемые при генерации ОС и служащие для передачи сообщений между системой и ВМ и между различными ВМ. Взаимодействие с очередями со стороны виртуальных машин производится через порты.

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

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

- защита общей и внешней памяти;

- разделение процессора как ресурса между системами программирования;

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

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

собственно обработка.

Данные вопросы исследованы автором в [10. 15, 17, 21.

23].

Базовая система программирования

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

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

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

В работе [24] была описана и проанализирована возможная для систем с транспьютерной организацией система программирования. Кроме семантической стороны вопроса, определены средства и способы описания данных и вычислений - в виде системы команд виртуальной машины, или В-код. к которому предъявляются следующие требования:

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

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

- использование в В-коде отдельных элементов техники смешанных вычислений (в частности, проверка соответствия типов

данных, если возможно, проводится до конца на стадии трансляции или оставляется на стадию исполнения);

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

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

ГЛАВА 3

Поляр - язык проектирования и описания архитектуры

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

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

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

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

- в языках описания, как. ппавило. слабо ппллегштаютоя

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

Язык Поляр создавался с учетом идей и подходов, использованных в современных языках высокого и сверхвысокого уровня, таких как Сетл, Лисп. Concurrent Pascal, Occam и ряд других. Одним из самых важных свойств языка является компактность, т.е. немногочисленность понятий и изобразительных средств.

В языке Поляр можно выделить следующие основные черты:

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

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

- создано гибкое технологическое обрамление языка в виде (в общем случае параметризованных) пакетов и других понятий.

В предшествующих созданию языка работах [1, 5, 6] были предложены основные подходы к формальному описанию асинхронной архитектуры. Язык Поляр детально описан в [28] и монографии автора [32]. исследованию разных сторон и свойств языка посвящены работы [9, И. 14.-16. 19, 24, 34. 37, 45, Ден85]. Вопросы реализации и использования рассмотрены в [22, 32]. Поляр применялся в работах по созданию кремниевого компилятора [29]. на его базе было создано расширение стандартного языка программирования С, которое активно используется как инструментальная система в работах по САПР СБИС и проектированию СБИС.

Структуры данных

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

НАН - пустое множество значений;

ЦЕЛ - целые значения;

ВЕЩ - вещественные значения;

ЛИТ - литерные значения.

Конструкторами составных типов являются запись, последовательность и объединение.

В общем случае определение типа представляет собой типовую формулу, выраженную в некотором (поляровском) синтаксисе.

Для иллюстрации приведем используемый синтаксис для типовых формул:

сист_типов : имен_тип.. имен_тип : имя_типа = тип ; ТИП : HAH I ЦЕЛ I ВЕЩ I ЛИТ

I имя_типа I запись I послед I объед I ( тип ) запись : поле_зап... поле_зап : имя_ключа,.. : тип послед : < тип > объед : вариант... вариант : имя_тега,.. л тип

Примеры:

STR = <ЛИТ>; IDN = STR;

DATABASE = < Name:IDN, Address: STR, Pass:(Ser:STR,

Norn:ЦЕЛ)>;

LIST = N11 " HAH.

Atom" IDN. Int " ЦЕЛ.

Pair" (Car: LIST, Cdr: LIST);

TREE

<TREE>;

Вопросы корректности предложенной системы типовых определений рассматривались в ряде работ [6. 37. Ден85]. Были определены необходимые и достаточные условия для построения корректных систем типовых формул. Для иллюстрации дадим некоторые простые примеры некорректных систем типов:

1) А = А;

2) А = К1: В, К2: ЦЕЛ; В = А;

3) А = Т1л А. Т2~ (К1: А. К2: ЦЕЛ);

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

Обработка структурных значений

Не. вдаваясь в подробности введенных операций и операторов, следует, отметить следующие наиболее существенные черты предложенного подхода. Для структурных значений введен минимальный базис операций выделения подзначений (поле записи, элемент последовательности, подзначение объединения) и структурных операций (конкатенация последовательностей, убавление элемента из последовательности и добавление элемента к последовательности), которые являются достаточно традиционными. Менее традиционными и весьма принципиальными являются связанная совокупность понятий значение - переменная - поле - выражение - расширенное выражение и концепция оператора присваивания.

Значения являются динамическими объектами языка (программы), все значения типизованы, структурные значения состоят из подзначений и т.д. Значения, не содержащиеся в других значениях. либо связаны с переменными, либо являются открепленными и существуют только как промежуточные результаты некоторых выражений. Начиная от идентификаторов переменных, можно "углубляться", выделяя компоненты значений, связанных с переменными; такие объекты называются полями. Поле дает возможность выделить подобъект без его копирования или открепления. Значения полей модифицируются с помощью оператора присваивания. Синтаксически оператор присваивания выглядит аналогично оператору присваивания в большинстве языков программирования, семантика его следующая: вместо значения поля, выделенного левой частью

присваивания, подставляется открепленное значение, вычисленное в правой части. Открепленное значение появляется как результат вычисления расширенного выражения, поставленного в правую часть. Расширенное выражение - это либо выражение, либо формирователь структурного значения. Выражение составлено из полей, которые в этом контексте означают создание открепленного значения путем копирования значения поля и функций, как встроенных. так и описанных. Формирователи структурных значений позволяют создавать структуры путем перечисления их подзначений. Более подробно работа с данными в языке Поляр описана в [6, 28. 32, 37].

Немаловажными особенностями структур данных Поляра являются:

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

- осуществление сборки мусора "на лету";

- концепция открепления значений (от поля) и автоприсваивание.

Асинхронное управление вычислениями

Ориентация на описание архитектуры в языке Поляр проявилась в создании модели потоковых вычислений и адекватных реализующих конструкций.

Модель вычислений основана на модификации моделей ОБР и обобщенных сетей Петри [Кот84]. С точки зрения управления параллельными вычислениями базовыми являются понятия (управляющей) переменной и модуля, а сами параллельные вычисления описываются следующей моделью [3, 26].

Переменная - это именованная' объектно-ориентированная память. Она соединяет в себе традиционные понятия памяти и данных, ибо структурирована под хранимые в ней данные, и управляется в зависимости от типа этих данных. Тип данных определяет допустимые способы работы с переменной в виде набора процедур и Функций доступа, которые с точки зрения асинхронно-

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

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

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

ющей этому сопряжению, принимает истинное значение. Таким образом, условия активизации модуля (порождения процесса по данному модулю) являются потоковыми, а переменная принимает непосредственное участие в управлении вычислениями. Концепция управляющих переменных близка к механизмам мониторов Бринк-Хансена [Вг175]. Принципиальное отличие состоит в том, что управляющая переменная управляет порождением новых процессов в асинхронной среде, в то время как монитор - это только механизм синхронизации в последовательно-параллельных вычислениях.

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

Технологические аспекты Поляра

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

Пакет - программная единица Поляра - это совокупность определений статических объектов: типов, констант, процедур и

функций. Все определения в пакете - одноуровневые, т.е. не содержат внутри себя определений других статических объектов. Несколько независимых пакетов могут быть связаны между собой, образуя иерархию пакетов так, чтобы из одного пакета были доступны объекты (описания) других присоединенных к нему пакетов. Такая совокупность связей между пакетами представляет собой направленный граф зависимости, который по требованиям языка Поляр не должен содержать циклов. Пакеты описаний статических объектов и их взаимосвязь определяют видимость для вводимых определений типов, констант и процедур, т.е.. в определениях можно испопьзовать введенные объекты данного пакета и присоединенных к нему объектов. Но наиболее существенной чертой пакетной организации описаний является возможность параметризации пакетов, что позволяет определять родовые описания, характерные для современных языков программирования, особенно объектно-ориентированных. Такая техника была подробно изложена в [9. 28].

Реализация Поляра

Поляр практически в полном виде был реализован и опробован на различных тестовых задачах. Под руководством автора диссертации в реализации ядра системы принимали участие Г.И.Алексеев, А.С.Денисов и С.П.Мыльников, реализация асинхронного управления вычислениями производилась Г. М. Креккером. Кроме того, совместно с А.С.Денисовым была осуществлена реализация поляровского расширения языка программирования С. Реализация описана в [22. Кре87], анализ принципов реализации - в [1, 6, 14, 28. 32, Лел83, Ден85. Кре87]. экспериментальное исследование и опыт использования приведены в [33].

ГЛАВА 4

Система автоматизации проектирования СБИС типа "кремниевый компилятор"

Прогресс в элементной базе, равно как и достижения в об-

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

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

В работе принимали участие 3.В.Апанович. В.И.Константинов. А. В.Клековкин, А. А. Фурсенко и другие сотрудники. Одновременно с созданием и совершенствованием кремниевого компилятора и отдельных его частей производилось опробование реализованных идей и программ на фрагментах реальных разработок СБИС, проводившихся также в основном с участием сотрудников лаборатории. Наибольший вклад в опробование и исследование возможностей кремниевого компилятора внесли A.B.Курочкин, М.Н.Ильин. Г.К.Корабельщиков.

Задача кремниевой компиляции

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

На период выполнения данной работы не существовало ни общепринятых средств спецификации функциональных описаний (таким

средством впоследствии стал язык УНБЬ), ни отработанных алгоритмов решения конкретных задач, тем более доступных программ, поэтому выполненная работа во многом повторяет эволюцию подходов к данной проблеме, осуществлявшуюся в мире весьма быстрыми темпами. Основными результатами представляемой работы видится то, что удалось предложить и реализовать комплексный подход к построению систем кремниевой компиляции [25, 27, 29, 39, 42. 43, 47, 52] характеризующийся единообразием и простотой используемых конструкций, который может быть воплощен в эффективную систему путем интеграции современных алгоритмов и программ, реализующих отдельные этапы обработки. Ряд предложенных в работе алгоритмов также являются новыми, их достоинства и недостатки были проанализированы в [30, 41. 44, 46, 48, 49. 50. 51, 53, 54]. Вклад автора диссертации и его коллег в данную проблематику иллюстрируется докладами на международных конференциях и соответствующими публикациями [48, 51, 53, 54].

В работах [27, 29, 41, 47] было показано, что задача кремниевой компиляции распадается на средства:

- описания структуры и функции проектируемых устройств;

- синтеза схем по функциональным (поведенческим) описаниям;

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

- генерации топологии (в общем случае параметрических) библиотечных элементов;

- синтеза топологии кристаллов.

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

- 30 -

Языки описания структуры устройств и геометрического чертежа

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

Автор диссертации предложил применять технику поляровских типовых описаний структур для единообразия и согласованности описаний форматов данных и использования синтаксиса Поляра для внешнего представления структур [29. 41]. Таким образом, автором были сформированы форматы (языки):

- СХЕМА - для описания иерархических схем;

- ЛАУТ - для построения геометрических, в том числе параметризованных [29]. чертежей топологии.

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

В синтаксисе языка Поляр типы данных, определяющие структуры СХЕМА и ЛАУТ, выглядят следующим образом:

СХЕМА = <Имя: ИДН. Опис_Блока: БЛОКУ. БЛОК = Вх_сигн: <ИДН>, Вых_сигн: <ИДН>. Внутр_сигн: <ИДН>, Внутр_Блоки: < Имя:ИДН, Вид:ИДН, Вх_сигн: <ЩЩ>. Вых_сигн: <ИДН>>; ЛАУТ = Прям ~ (Слой:ЦЕЛ. Ниж:ТОЧКА. Верх:ТОЧКА). Мног л (Слой:ЦЕЛ, Точки: <Т0ЧКА>). Транс" (Топология : ЛАУТ. Матр : МАТР), Итер " (Топология:ЛАУТ.Сдвиг:ТОЧКА,Количество:ЦЕЛ),

Элемент ~ ИДН;

Набор" (Топология:<ЛАУТ>.Сдвиг: ТОЧКА),

Если л (Условие:ЛОГ.Топология:ЛАУТ); ТОЧКА = X: ЦЕЛ, У: ЦЕЛ;

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

Было опасение, что такие форматы будут не удобны для пользователей-разработчиков и придется "закрывать" их дополнительными средствами. Однако опыт работы показал, что для ряда применений, напр. для формирования геометрических образов параметризованной библиотеки элементов, конструкторы не испытывают больших затруднений в пользовании языками [29].

Алгоритмы синтеза топологии СБИС

Синтез топологии имеет своей целью формирование геометрического чертежа (топологии) СБИС по заданному схемному описанию, построенному в базисе библиотечных элементов. В случае использования параметризованных библиотечных элементов отдельной задачей является синтез (генерация) геометрического чертежа собственно используемых библиотечных элементов с заданными фактическими параметрами, такая постановка была реализована и проанализирована, см. [29, 30].

Задача синтеза топологии в основном распадается на подзадачи:

- планирование кристалла;

- размещение элементов;

- локальная (канальная) трассировка;

- глобальная трассировка и разводка шин питания;

- постпроцессирование и сопряжение со стандартными выходными форматами.

Во второй задаче были предложены существенно новые алгоритмы [48, 51. 53, 54, 55]. в остальных осуществлены модифика-

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

Одним из существенных моментов при проектировании топологии СБИС является вопрос о способе отображения иерархического описания логической схемы проектируемого устройства в топологию кристалла. Преобразование описания схемы к одноуровневому виду становится неприемлемым ввиду того, что размерность получаемых в этом случае задач трассировки и размещения становится слишком большой, не позволяя решать эти задачи эффективно. С другой стороны, последовательный синтез топологии узлов уровня п+1 из элементов уровня п, давая, как правило, задачи приемлемой размерности, порождает некачественную топологию за счет того, что требуется трассировка межблочных промежутков для макроблоков каждого уровня иерархии. В реализованной системе TOPS выбран компромиссный 'подход к решению этой задачи. Разработчику предоставляется возможность в интерактивном режиме мо^ дифицировать схему устройства таким образом, чтобы размерность решаемых задач трассировки и размещения, а также количество уровней иерархии было приемлемым для имеющейся системы синтеза топологии.

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

- 33 -

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

Важным элементом комплекса программ кремниевой компиляции является программа автоматического размещения элементов. В силу ограниченности доступной вычислительной техники пришлось отказаться от алгоритмов типа имитации отжига, сделав выбор в пользу рекурсивного алгоритма метода сечений. При этом в метод было добавлено два принципиальных новшества, которые в совокупности обеспечили качество получаемой топологии, близкое к получаемому стохастическими алгоритмами, при значительно меньших затратах времени на решение задачи. Первая модификация касается итерационного метода выполнения перемещения элементов через выбранное сечение. Было предложено использовать в данном локальном алгоритме стохастические алгоритмы минимизации, родственные методу имитации отжига, что позволило устранить "сползание" в локальные минимумы и получить (в пределе) решение, близкое к оптимальному. Другим существенным добавлением в известный алгоритм явилась рекуррентная процедура определения наиболее выгодного расположения точек внешнего расположения точек подключения сигналов подблоков к сигналам других подблоков. Это позволяет эффективно учесть особенности структуры связей схемы для оптимизации размещения элементов по основному функционалу - длине связей. Предложенные методы и алгоритмы опубликованы в [48].

Программа логического моделирования СБИС

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

го проекта, хотя и не гарантирующим полной корректности результата.

В предложенном и реализованном подходе основное внимание уделялось возможности выполнения моделирования относительно больших схем при малой оперативной памяти компьютеров типа IBM PC/AT. Это было достигнуто за счет комбинированного использования библиотечных элементов разного уровня. В единой модели удалось согласовать каскады, состоящие из транзисторов, с каскадами из вентилей и "крупных" элементов уровня языка межрегистровых передач (блоки регистров, памяти, мультиплексоры, кодеры, ПЛМ и т.д.). Таким образом, у разработчика электронной схемы есть возможность моделировать большие модели микропроцессорного уровня, описав их в базисе регистровой логики, а далее конкретизируя отдельные подсхемы до удобного ему уровня, вплоть до транзисторного. Была использована'достаточно традиционная 12-значная логика для каскадов транзисторного и вентильного уровней и двоичная "словная" (напр. 16 разрядов для IBM PC) для уровня межрегистровых пересылок.

Программа DART была реализована в полном объеме для компьютеров типа IBM PC/AT и для 32-разрядных UNIX-компьюте-ров. Программа внедрена, использовалась и используется как в автономном режиме, так и в комплексе программ кремниевой компиляции.

Организация системы сквозного проектирования СБИС

Связующая системная часть кремниевого компилятора формировалась на уже упомянутых принципах выделения стандартных системных интерфейсов (форматов). Были определены основные структуры данных и произведена разбивка на программы-проходы, осуществляющие содержательные этапы обработки/преобразования. В такие программы "вставлялись" отработанные алгоритмы предметного уровня. Многочисленные особенности такого процесса были изложены в [29. 41, 44. 47, 52].

Важная роль в достижении высоких параметров функционирования комплекса отводилась оптимизации ряда алгоритмов на

реальных тестовых задачах. Проблема усложнялась тем, что один прогон нетривиальной задачи синтеза занимает минуты и десятки минут, а результаты по характеристикам получаются скорее статистического характера. Однако за счет такой кропотливой работы по оптимизации удалось сформировать внутренние параметры алгоритмов, которые дают возможность надежно получать результаты высокого качества. Это как-бы "встроенное" в программы "know-how".

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

Сопоставление созданных программ и алгоритмов с зарубежными результатами проводилось, к сожалению, фрагментарно из-за сложностей информационного обмена с коллегами. Сравнение с отечественными родственными программами показало высокие качества созданных программ, а сравнение с "ручными" разработками на примере СБИС серии "Дублер" показало, что для схем более 5-10 тыс. элементов полученная топология по основному параметру - занимаемой площади, является лучше, при том, что затраты труда на синтез схем являются несравнимыми (2-3 часа против 12 человеко-лет).

ЗАКЛЮЧЕНИЕ

В диссертации автором получены следующие результаты:

1. Создана методика разработки экспериментальных параллельных архитектур компьютеров. Предложен и обоснован класс параллельных архитектур - системы с транспьютероподобной архитектурой.

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

3. Предложена и реализована методика построения систем автоматизации проектирования СБИС типа "кремниевый компиля-

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

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

Кроме того, под руководством и при личном участии автора были получены следующие результаты:

5. Создана архитектура параллельной вычислительной системы с транспьютерной архитектурой в соответствии с которой реализован 4-процессорный компьютер МАРС-Т.

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Лельчук Т.И., Марчук 'А.Г. Особенности реализации языка описания архитектуры системы МАРС// Всесоюзн. конф. по методам .трансляции: Тезисы докл. - Новосибирск, 1981. - С. 97-99.

2. Марчук А.Г. Архитектура одного класса иерархических параллельных систем// Эффективность и качество распараллеливания алгоритмов в системах обработки информации. - Львов, 1981. - С. 4-5.

3. Марчук А.Г. Модель вычислений в языке описания архитектуры// Параллельные вычислительные и программные системы. - Новосибирск, 1981. С. 37-42.

4. Вишневский Ю.Л.. Котов В.Е., Марчук А. Г. Архитектура и принципы организации параллельного процессора для числовой об-

работки// Высокопроизводительные вычислительные средства для обработки данных. - Новосибирск. 1981. С. 5-13.

5. Лельчук Т.И., Марчук А.Г. Язык описания функциональной архитектуры вычислительных систем. - Новосибирск. 1981. - 19 с.

- (Препр./ АН СССР. Сиб. отд-ние. ВЦ; N285)

6. Лельчук Т.И., Марчук А.Г. Работа с данными в языке описания функциональной архитектуры// Параллельные вычислительные и программные системы. - Новосибирск. 1981. - С. 43-52.

7. Марчук А.Г. Исследования в области архитектурных моделей системы МАРС// Высокопроизводительные вычислительные системы: Тез. докл. Ч. 2. - Москва. 1981. - С. 73-75.

8. Вишневский Ю.Л.. Котов В.Е.. Марчук А.Г. Проблемы создания модульной асинхронной развиваемой системы (МАРС)// Многопроцессорные вычислительные структуры. - Таганрог, 1981. -Вып 3 (XII). - С. 15-17.

9. Лельчук Т.И., Марчук А.Г. Технологические особенности языка параллельного программирования ПОЛЯР// Многопроцессорные вычислительные системы и их математическое обеспечение. Новосибирск, 1982. - С. 84-93.

10. Марчук А.Г. Анализ накладных расходов на параллельную реализацию вычислительного процесса// Труды четвертой всесоюз. школы-семинара "Распараллеливание обработки информации". -Львов, 1983. - Ч. 1. С. 13-14.

И. Лельчук Т.И., Марчук А.Г. ПОЛЯР - язык параллельного асинхронного программирования// Программирование. - 1983. N 4. С. 59-68.

12. Вальковский В.А.. Котов В.Е.. Марчук А.Г., Миренков Н.Н. Элементы параллельного программирования. - М.: Радио и связь. 1983. - 240 с.

13. Котов В.Е.. Марчук А.Г. Некоторые итоги и перспективы развития проекта МАРС// Актуальные проблемы развития архитектуры и программного обеспечения ЭВМ и вычислительных систем. --Новосибирск. 1983. - С. 13-23.

14. Лельчук Т.И., Марчук А.Г. Асинхронный метод программирования и его реализация в языке Поляр// Системное и теоретическое программирование. - Кишинев: Штиинца, 1983.

- С. 238-239.

15. Марчук А.Г. Предложения по созданию переносимой операционной системы// Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ. - Новосибирск. 1983. -С. 31-45.

16. Марчук А. Г. Языковые,, средства описания распределенных систем// Осма национална школа ПРОГРАМИРАНЕ 83 (Болгария). -Приморско, 1983. - С. 136-144.

17. Марчук А.Г. Организация вычислительного процесса в модульных лабораторных вычислительных комплексах// Персональные ЭВМ в задачах информатики. - Новосибирск. 1984. - С. "73-81.

18. Вишневский Ю.Л., Котов В. Е.. Марчук А.Г. Модульная асинхронная развиваемая система// Кибернетика. - 1984. - N 3. -С. 22-29.

19. ЛельчукТ.И., Марчук А. Г. Средства описания функциональной архитектуры вычислительных систем// Высокопроизводительные вычислительные системы: Тез. докл. - Батуми, 1984. - С. 99100.

20. Котов В. Е.. Марчук А. Г. Проект МАРС - комплексный подход к разработке вычислительных систем// Кибернетика и вычислительная техника. - М.: Наука. 1985. - Вып. 1. - С. 69-77.

21. Марчук А.Г. Об операционной системе для ЭВМ с архитектурой МАРС// Теория программирования и средства описания параллелизма дискретных систем. - Новосибирск, 1985. - С. 138-149.

22. Алексеев Г.И., Лельчук Т.Н.. Марчук А.Г.. Мыльников С.П. Переносимый транслятор с языка Поляр// Теория программирования и средства описания параллелизма дискретных систем. -Новосибирск, 1985. - С. 150-162.

23. Марчук А.Г. Архитектура логического процессора для интеллектуальной ЭВМ// Автоматизированные рабочие места интеллектуальной деятельности. - Новосибирск. 1985. - С. 141-149.

24. Марчук А.Г. Базовая система программирования// Архитектура и программное обеспечение высокопроизводительных систем. -Новосибирск, 1985. - С. 36-54.

25. Апанович 3.В., Марчук А.Г. АРМ интерактивной работы с топологией сверхбольших интегральных схем// Тез. докл. Всесоюз. школы "Иверси-85". - Гагра, 1985. - С. 10-11.

26. Лельчук Т.И., Марчук А.Г. Средства асинхронного программирования в языке Поляр// Программное обеспечение многопроцессорных систем. - Калинин, 1985.

27. Константинов В.И., Максимов В.Л., Марчук А.Г. О методологии и технологии проектирования СБИС// Архитектура и программное обеспечение высокопроизводительных вычислительных систем. - Новосибирск, 1985. С.55-64.

28. Лельчук Т.И., Марчук А.Г. Описание языка Поляр - Новосибирск. 1985. - 37 с. - (Препр./ АН СССР. Сиб. отделение. ВЦ; N285)

29. Апанович 3.В.. Курочкин А.В.. Марчук А.Г. Реализация экспериментального кремниевого компилятора// Вычислительные системы и программное обеспечение. - Новосибирск. 1986. - С. 152-164.

30. Апанович 3.В.. Курочкин А.В.. Марчук А.Г. Об одном методе решения задачи топологического синтеза в системе "кремниевый компилятор"// Тез. докл. Всесоюз. школы-семинара "САПР ЭВМ и БИС-86". - Ереван. 1986. - С. 241-243.

31. V.E.Kotov. A.G.Marchuk, Yu.L.Vishnevsky MARS - A Hierarchical Heterogeneous Modular System// Fifth Generation Computer Architectures. - Elsevier Science Publishers B.Y.(North-Holland), IFIP, 1986. -P. 133-140.

32. Лельчук Т.И., Марчук А.Г. Язык программирования Поляр: описание. использование, реализация. - Новосибирск: Вычислительный центр СО АН СССР, 1986. - 96 С.

33. Алексеев Г.И.. Лельчук Т.И., Марчук А.Г., Мыльников С.П. Интерактивная система поддержи проектирования архитектуры и ПО ЭВМ нового поколения// Персональные компьютеры и локальные сети. - Тбилиси. 1986. - С. 49-50.

34. Лельчук Т.Н.. Марчук А.Г. Язык Поляр - элемент технологии проектирования СВТ// Вычислительные системы и программное обеспечение. - Новосибирск, 1986: - С. 23-29.

35. Котов В.Е.. Марчук А.Г. Реализация концепции МАРС в архитектуре ЭВМ нового поколения// Разработка ЭВМ нового поколения: архитектура, программирование, интеллектуализация. -Новосибирск, 1986. - С. 155-160.

36. Котов В.Е., Марчук А.Г. Архитектура макета системы МАРС//

Вычислительные системы и программное обеспечение. - Новосибирск, 1986. - С. 5-12.

37. Денисов A.C., Лельчук Т.И., Марчук А.Г. Рекурсия в определении и описании обработки динамических структур данных// Программирование. - 1987. - N 2. - С. 36-43.

38. Марчук А.Г. Транспьютерная архитектура для построения параллельных систем// Технология и проектирование функционально-сложных БИС. - М.: ЦНИИ "Электроника". 1987. - С. 8385.

39. Апанович 3.В., Марчук А.Г. и др. Кремниевый компилятор Лотос// Автоматизация проектирования в машиностроении. - Тез. докл. / Всесоюз. Конф. - Душанбе. 1987. - С. 87-88.

40. Котов В.Е., Лельчук Т.И., Марчук А.Г. Архитектура и программное обеспечение макета системы МАРС// Высокопроизводительные вычислительные системы. - Москва. 1988. - С. 12-13.

41. Апанович З.В., Марчук А.Г. Подсистема топологического синтеза сверхбольших интегральных схем// Архитектура и программное обеспечение многопроцессорных вычислительных комплексов. - Новосибирск, 1988. - С. 5-21.

42. Апанович З.В.. Марчук А.Г. Средства автоматизации проектирования СБИС// Автоматизация конструкторского проектирования РЭА и ЭВА-. - Пенза, 1988. - С. 3-4.

43. Апанович З.В., Марчук А.Г. и др. кремниевый компилятор Лотос// Высокопроизводительные вычислительные системы: Тез. докл. / Третье всесоюз. совещание. - Таллинн. 1988. - С. 6-7.

44. Апанович З.В.. Марчук А.Г. Гибкий подход к топологическому синтезу сверхбольших интегральных схем и его реализация в кремниевом компиляторе "Дотсс"// Школа-семинар молодых ученых и специалистов "Актуальные проблемы создания интеллектуальных САПР РЭА и БИС". - Воронеж. 1989. - С. 47-48.

, 45. G.M.Krecker. T.I.Lelchuk. A.G.Marchuk POLAR - A Programming Language for Multiprocessor Systems// Proceed, of the IFIP 11th World Computer Congress. - San Francisco, USA, 1989. P. 33-37. '

46. Апанович. 3. В.. - Марчук А.Г. Структура и базовые конструкции системы топологического синтеза заказных СБИС// Архитекту-

pa, матобеспечение и средстза интеллектуализации вычислительных систем. - Новосибирск. 1989. - С. 5-16.

47. Марчук А.Г.. Константинов В.И., Апанович З.В. Экспериментальный кремниевый компилятор Лотос// Тр. 1 междунар. научно-практической конф. САПР СВТ-89. - Ленинград, 1989. -С. 225-234.

48. Apanowich Z.W., Marchuk A.G. Flexible Automatic Layout System for Custom and Semicustom VLSI Design// Sixth Sympos. on Microcomputer and Microprocessor Applications. -Budapest, 1989. - P. 83-85.

49. Апанович З.В. Клековкин А.В. Марчук А.Г. Интерактивный иерархический планировщик кристалла// Автоматизация проектирования РЭА и ЭВА: Тез.докл.- Пенза, 1991. - С. 31-32.

50. Апанович З.В., Марчук А.Г. Современные стили проектирования и алгоритмы размещения при проектировании СБИС// Системная информатика. Т.1: Проблемы современного программирования. -Новосибирск: Наука. 1991. - С. 260-292.

51. Apanowich Z.W., Marchuk A.G. An algorithm for standard-cell and gate array placement// Current Topics in Informatics Systems Research. - Novosibirsk, 1991. - P. 167-172.

52. Апанович З.В. Марчук А.Г. Система проектирования заказных и полузаказных СБИС/./ Автоматизированное проектирование в электронике 1991. - N44. - С. 20-24.

53. Apanowich Z.W.. Marchuk A.G. An Algorithm for Standard-cell and Gate Array Placement// Proceed, of Euro ASIC'92, Paris June 1-5, 1992. - Loss Alamitos. California: IEEE Computer Society Press, 1992. - P. 416-421.

54. Apanowich Z.W., Marchuk A.G. An Algorithm for Standard-cell and Gate Array Placement// Seventh Sympos. on Microcomputer and Microprocessor Applications, Budapest. April 22-24, 1992. - P. 133-140.

55. Апанович 3.В., Марчук А.Г. Алгоритм размещения стандартных элементов, реализованный в системе проектирования заказных и полузаказных схем SILS// Теоретические проблемы систем обработки информации. - Новосибирск, 1990. - С. 93-104.

56. V.E.Kotov, A.G.Marchuk. Yu.L.Vishnevsky MARS - A Hierarchical Heterogeneous Modular System//IFIP TC-10

Working Conf. on Fifth Generation Computer Architectures. Proc. - Manchester. 1985. - P. 1-16.

57. Алексеев Г.И.. Креккер Г.М., Марчук А.Г. и др. Поляр-88 -современная система программирования общего назначения// Программирование. - 1991. - N 1. - С. 89-94.

ЛИТЕРАТУРА

[Мар78] Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система (МАРС). - Новосибирск, 1978. - 48с, 51с. -(Препр./ АН СССР Сиб. отд-ние. ВЦ; N 86, N 87)

[Куз86] Кузнецов Д.Н. и др. Процессор Кронос в мультипроцессорной системе// Вычислительные системы и программное обеспечение. - Новосибирск, 1986. - С._13-19.

[Виш82] Вишневский Ю.Л. Архитектурные особенности процессора Мини-МАРС// Высокопроизводительные системы обработки больших массивов данных. - Новосибирск, 1982. - С. 5-33.

[Дор86] Дорожевец М.Н. Основные принципы построения ядра операционной системы процессора Мини-МАРС// Вычислительные системы и программное обеспечение. - Новосибирск, 1986. - С. 32-36.

[Ayr83] Ayres R.F. VLSI, Silicon compilation and the art of automatic microchip design. - Prentice-Hall, 1983.

[Mea80] Mead C.A.. Conway L.A. Introduction to VLSI Systems. -Reading. Mass.: Addison - Wesley. 1980.

[Лел83] Лельчук Т.И. Представление иерархических динамических данных// Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ. - Новосибирск, 1983. -С. 46-58.

[Flу78] Flynn M.J. Computer organization and architecture // Lect. Not. Comp. Sei. - 1978. - Vol. 60. P. 17-98.

[Хок86] Хокни P., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. - М.: Радио и связь, 1986.

[Ден85] Денисов A.C. о рекурсивно - определяемых типах языка Поляр// Теория программирования и средства описания па-

- 43 -

раллелизма дискретных систем. - Новосибирск, 1985. - С. 15-28.

[Кре87] Креккер Г.М.. Лельчук Т. И. Параллельная обработка иерархических динамических структур данных. - Новосибирск. 1987. - 39 с. - (препринт/ АН СССР, Сиб. отд-ние, ВЦ; 742) [Мау84] May D. , Taylor R. OCCAM - an overview// Microprocessors

and Microsystems. - 1984. - Vol. 8, N.2. P. 73-79. [Кот84] Котов B.E. Сети Петри. - M.: Наука. 1984.