МИНИМИЗАЦИЯ СХЕМ ЦВМ
— процесс улучшения структур различных компонентов цифровой вычислительной машины, ведущий к сокращению затрат аппаратуры. Задачу М. с. решают на этапе элементного синтеза ЦВМ, ее цель — повысить экономичность схем при условии сохранения (или улучшения) характеристик их эффективного функционирования (быстродействия и надежности). Эту задачу можно рассматривать в отдельности для блоков ЦВМ типовых и аппаратуры устр-в управления — автоматов управляющих. Поскольку число различных типов блоков ЦВМ сравнительно невелико (сумматоры, счетчики, регистры и дешифраторы) и для каждой элементной структуры ЦВМ, как правило, определены различные конфигурации этих блоков, задача М. с. типовых блоков ЦВМ сводится в основном к выбору (в соответствии со спецификой использования блока в ЦВМ) из известных наборов типовых схем наиболее экономичных для используемой элементной структуры.
Большое разнообразие схем управляющих автоматов не позволяет аналогично решать задачу их минимизации. В настоящее время нет общих методов М. с. автоматов при произвольном выборе функционально полной системы операторов элементарных. В связи с этим решение общей задачи М. с. автоматов сводится, как правило, к решению нескольких частных подзадач. Так, напр., в рамках широко распространенного канонического метода синтеза автоматов структурного задача минимизации сводится к задаче минимизации числа состояний автомата (памяти автомата) и к задаче минимизации комбинационных схем автомата, описываемых системами переключательных функций. Первая из них решается в рамках абстрактной теории автоматов (напр., метод Ауфенкампфа — Хона), вторая — в рамках структурной теории автоматов с привлечением разработанных в алгебре логики (булевой алгебре) методов минимизации переключательных ф-ций (см. Блейка алгоритм, Квайна метод минимизации, Мак-Кла-ски алгоритм, Карнау карта) и последующим учетом реальных физ. характеристик, применяемых логических элементов ЦВМ и элементов памяти.
Более естественной является постановка задачи М. с. автоматов, при которой стремятся минимизировать общее к-во затрат аппаратуры, необходимой для реализации всего автомата, а не отдельных его частей — комбинационной и запоминающей, поскольку последнее в общем случае не обеспечивает минимума суммарных затрат аппаратуры на схему в целом. Идея такой постановки состоит в представлении схемы автомата в виде сети из более простых автоматов частичных, удовлетворяющих тем или иным свойствам (напр., свойству независимости ф-ций дешифрования автомата от числа его состояний и т. п.). В результате этого к-во элементарных автоматов, выбираемых для реализации автомата, оказывается больше необходимого минимума, но ф-ции комбинационной части схемы, состоящие из ф-ций возбуждения, выходов и дешифрования, получаются достаточно простыми. В целом же к-во логич. операторов, реализующих синтезируемую схему, значительно сокращается.
Рассмотренные выше методики М. с. широко использовались при проектировании схем ЦВМ 1-го и 2-го поколений. Это объясняется тем, что минимизация общего к-ва логич. операторов схемы приводила к сокращению общего к-ва операторов элементных, поскольку в ЦВМ первых поколений каждый логич. оператор, как правило, реализовался на базе самостоятельно конструктивно оформленного элементного оператора. Однако для ЦВМ 3-го поколения (а тем более для машин последующих поколений) рассмотренные выше методики М. с. оказываются менее эффективными. Причина этого — значительно возросший за последние годы уровень развития элементно-технологической базы ЦВМ, в частности, высокая степень интеграции, приводящая к тому, что один технологический неделимый элементный оператор (модуль) содержит несколько десятков (а в будущем — и сотен) логич. операторов.
В этих условиях эффективное использование рассмотренных методик ограничивается минимизацией числа элементарных компонент (
-переходов) отдельных модулей, но это практически не сокращает общего к-ва модулей, составляющих синтезируемую схему. Поэтому при решении проблемы М. с. современных ЦВМ, с одной стороны, приходится решать ряд новых задач (напр., таких, как задача минимизации общего числа модулей, реализующих схему, задача выбора наборов типовых модулей для синтеза схем ЦВМ, различные оптимизированные задачи покрытия функциональных схем ЦВМ наборами типовых модулей и т. п.), а с другой стороны, проблема М. с. получает интерпретацию в терминах задач оптимизации алгоритмов функционирования схем устройств ЦВМ.
Комплексное решение упомянутых задач переносит решение проблемы М. с. современных ЦВМ с этапа элементного синтеза схем на более высокие этапы- алгоритмического синтеза ЦВМ и блочного синтеза ЦВМ. Эффективная реализация последних осуществляется в рамках систем автоматизации проектирования ЦВМ.
Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469]; Рабинович 3. Л. Элементарные операции в вычислительных машинах. К., 1966 [библиогр. с. 299—301]; Рабинович 3. Л., Капитонова Ю. В., Комухаев 9. И. Методика кодирования состояний конечных автоматов с точки зрения минимизации аппаратурных затрат. В кн. Теория дискретных автоматов. Рига, 1967. В. Н. Коваль.
