|
Оглавление
Предисловие
Предлагаемая вниманию читателя книга посвящена проблеме логического управления. В ней обобщаются результаты многолетних исследований автора по разработке методов автоматизированного проектирования устройств логического управления, реализующих параллельные алгоритмы. Для описания таких алгоритмов был предложен формальный язык ПРАЛУ, использованный затем в качестве входного языка в нескольких системах автоматизированного проектирования. Были разработаны средства обеспечения корректности выражений в этом языке и стандартизация этих выражений, результаты которой интерпретировались в терминах теории автоматов как "параллельный автомат, который может находиться одновременно в нескольких состояниях (частичных)". Были разработаны также методы кодирования таких состояний, преобразующие параллельный автомат в секвенциальный – систему выражений типа продукций "если ..., то ...". Наконец, были предложены методы трансляции секвенциального автомата в систему булевых функций и реализации последней на программируемых логических матрицах. Данные исследования были начаты автором в начале 80-х годов [10, 12–21]. Естественно, они проводились не на пустом месте. Определенное влияние оказали на автора работы по параллельному программированию [3, 46] и языку Grafset [70], а также по "инженерным" методам проектирования систем автоматики [58]. Существенно использовался аппарат сетей Петри [47, 68, 72 и др.]. Рассматриваемая проблема весьма актуальна и по ней проводятся исследования в разных странах. Среди них наиболее близкими по духу и результатам оказались исследования, проводимые профессором Адамским (Польша), начатые почти одновременно с исследованиями автора. В опубликованных им работах [60–68, 71 и др.] вводятся и развиваются аналогичные понятия параллельного алгоритма и параллельного автомата, решаются комбинаторные задачи кодирования частичных состояний последнего, используются средства секвенциального описания параллельного алгоритма логического управления и рассматривается задача его реализации на программируемых логических матрицах. Замечу, однако, что данная книга не претендует на освещение общего состояния исследований в рассматриваемой области, а ограничивается изложением оригинальных результатов автора, рассеянных до этого по множеству отдельных публикаций. Выражаю благодарность Международному научно-техническому центру (проект В 104–98) и Фонду фундаментальных исследований республики Беларусь, поддержавшим издание настоящей монографии, а также Оксане Клачко, оказавшей неоценимую помощь в ее оформлении. Введение
Логическое управление. Современное производство становится все более дискретным: технологический процесс расчленяется на последовательность разнообразных операций, выполняемых комплексом различных технических устройств и систем, станков, роботов, средств контроля, станочных линий и т.д., четко взаимодействующих между собой. Это взаимодействие организуется с помощью многочисленных датчиков, расположенных в устройствах и сигнализирующих об их состояниях, а также, возможно, о состоянии внешней среды, в которой функционирует система, или о фазе самого технологического процесса, например о степени приближения формы обрабатываемой на станке детали к требуемой. Сигналы с датчиков поступают на вход системы управления, которая должна анализировать текущую ситуацию и вырабатывать адекватную реакцию, посылая на компоненты комплекса воздействия, непосредственно управляющие исполнительными механизмами: переключателями, клапанами, двигателями, насосами, электромоторами и т.д. Как сигналы с датчиков, так и управляющие воздействия дискретны, а чаще всего двоичны (например, включено-выключено), т.е. управление становится логическим, и в этом случае системы управления называются системами логического управления. Системы логического управления находят широкое применение не только на производстве, но также на транспорте и в сетях связи, в информационно-справочных системах, в компьютерах и бытовой аппаратуре, включая автоматические игрушки. Проектирование систем логического управления представляет собой сложную проблему, решаемую с использованием богатого арсенала современной дискретной математики, в первую очередь алгебры логики. Этой проблеме и посвящается предлагаемая вниманию читателя книга, в которой излагается определенный подход к ее практическому решению. Проектирование систем логического управления удобно разбить на три крупных этапа. На первом этапе определяется, как должны взаимодействовать компоненты технического комплекса, реализующего заданную технологию. Другими словами, разрабатывается алгоритм взаимодействия этих компонент, алгоритм управления ими. Его выполнение будет затем возложено на систему логического управления. Это – этап алгоритмического проектирования. На втором этапе проектируется логическая структура системы управления, в результате чего определяется ее состав, перечисляются элементы с указанием их функций и связи между ними. Технические средства, на которых выполняется затем система управления, могут оказаться различными. Так, в качестве элементов логической структуры могут использоваться и простейшие логические элементы, реализующие элементарные булевы функции типа И, ИЛИ, НЕ, и существенно более сложные изделия микроэлектроники типа программируемых логических матриц и микропроцессоров, и даже целые вычислительные машины, специализированные или универсальные. При этом синтез схем из логических элементов может заменяться разработкой программ, выполняемых затем на микропроцессоре или на ЭВМ и реализующих аналогичные функции. Второй этап называется этапом логического проектирования. Третий этап – заключительный. На нем учитываются свойства реальных технических элементов, производится их компоновка и размещение по конструктивным единицам (ячейкам, платам, блокам и т.п.), решаются задачи трассировки соединяющих элементы электрических цепей и выполняется масса другой работы, необходимой при технической реализации логического проекта и при подготовке к производству реальных систем логического управления. Это – этап технического проектирования. Технической базой современных систем логического управления служит микроэлектроника. Она позволяет создавать мощные вычислительные комплексы, эффективные сети связи, сложные системы управления производственными процессами, содержащие тысячи и миллионы простейших логических элементов (или команд в управляющих программах). В то же время она предъявляет и более жесткие требования к методам проектирования дискретных систем. Чем сложнее эти системы, тем очевиднее становится необходимость автоматизации процессов их проектирования на базе ЭВМ. В проектных организациях автоматизацией охвачен, как правило, лишь этап технического проектирования и, в гораздо меньшей степени, этап логического проектирования. Здесь автоматизация ограничивается моделированием на ЭВМ уже заданных логических структур и полуавтоматической разработкой проверяющих и диагностических тестов для них. Между тем специфика микроэлектронной технологии такова, что малейшая ошибка на начальных этапах проектирования, если только она не будет своевременно обнаружена и исправлена, может привести к необходимости полного повторения всего цикла проектирования. Повысить надежность проектов до требуемого уровня можно лишь при надлежащей автоматизации всех этапов проектирования. А автоматизация, как известно, должна опираться на формализацию: разработку формальных моделей объектов проектирования и формальных методов проектирования. Такая формализация уже десятки лет расшивается в рамках логической теории дискретных устройств, включающей, в частности, теорию автоматов, теорию булевых функций и теорию логических сетей. Здесь накоплено много полезных результатов, но большинство из них относится к первому этапу развития теории, когда она ориентировалась на разработку сравнительно несложных логических устройств, конструируемых из элементов И, ИЛИ, НЕ, НЕ ИЛИ и т.п., и реализующих последовательные алгоритмы, вычисляющие или управляющие. К настоящему времени элементный базис существенно изменился: роль элементов играют большие и сверхбольшие интегральные схемы (БИС и СБИС), выполненные на одном кристалле и составленные из тысяч и миллионов элементарных (логически неразложимых) вентильных схем. Яркими представителями СБИС служат микропроцессоры и программируемые логические интегральные схемы (ПЛИС), хорошо дополняющие друг друга. Микропроцессор подобен универсальной вычислительной машине (без терминальных устройств) и может решать практически любую задачу, если только для нее составлена программа, хотя и не всегда достаточно быстро. А, например, разновидность ПЛИС – программируемая логическая матрица (ПЛМ) – представляет собой специализированное однокристальное устройство, с высокой скоростью (десятки наносекунд) реализующее любую заданную систему булевых функций, ограниченную лишь тремя параметрами: числом функций, числом аргументов и общим числом элементарных конъюнкций (функции заданы в дизъюнктивной нормальной форме). Изменился и класс проектируемых дискретных устройств. Однопроцессорные ЭВМ вытесняются многопроцессорными, все большее внимание уделяется дискретным системам, управляющим взаимодействующими производственными процессами, переплетающимися в пространстве и времени, Реализуемые при этом алгоритмы оказываются параллельными – в них предусматривается одновременное выполнение нескольких операций. Алгоритмы логического управления. Приступая к проектированию системы логического управления, нужно прежде всего выяснить, что должна делать система, задать условия ее работы, определить ее функции, выразив их в некотором формальном языке, не допускающем неоднозначности толкования. Лучше всего это можно сделать, описав алгоритм решения поставленной перед системой задачи, т.е. алгоритм управления. "Моделирование любой управляющей системы всегда начинается с алгоритмического описания процесса управления" [45]. Лишь после четкого описания алгоритма, его проверки, отладки и приведения к надлежащему виду можно перейти к конструированию технической системы, реализующей этот алгоритм. Если в описание алгоритма вкрадутся ошибки, дальнейшая его реализация может оказаться бессмысленной. Отсюда становится ясной важность качественной разработки и отладки алгоритма управления, который подлежит реализации на проектируемом устройстве. Алгоритмическое описание полезно не только на этапе разработки функций управляющей системы. При наличии соответствующих средств в используемом алгоритмическом языке возможно выполнение таких формальных преобразований в рамках языка, которые приближают описание вплотную к схеме или программе – конечной цели проектирования. После этого получение схемы или программы сводится в основном к смене интерпретации формул, описывающих алгоритм, например: операторы преобразования значений переменных трактуются как аппаратурные блоки с соответствующими функциями, а операторы следования и информационного обмена – как проводные связи между блоками. Такой подход получил название стандартной реализации алгоритма [44]. Но чтобы такие преобразования в рамках алгоритмического языка были возможны, надо чтобы в нем могли описываться алгоритмы двух типов, которые назовем алгоритмами планирования и алгоритмами поведения. Четкой границы между ними нет, и функции планирования и поведения могут переплетаться в едином формальном описании. Именно это и позволяет проводить указанные преобразования. Однако можно сказать, что алгоритм планирования соответствует более привычному представлению об алгоритме как инструкции, содержащей указания о том, что и в каком порядке надо делать, чтобы достичь некоторой цели. Это, так сказать, план без исполнителей. Кто конкретно будет его выполнять считается не таким уж важным, требуется лишь чтобы исполнитель четко придерживался заданных инструкций. С другой стороны, алгоритмы поведения, получившие развитие преимущественно в теории автоматов, представляют функциональные свойства реально существующих (а также мыслимых, например при проектировании) технических систем, описывая реакции системы на внешние воздействия. Впрочем, алгоритмы этого типа годятся и для описания поведения естественных систем, в том числе и живых. Это можно увидеть из следующего определения, где вместо термина "алгоритм" используется "программа": "Под программой следует понимать определенную последовательность изменения системы (или ее подсистемы), которая заложена в ее структуре и реализуется при определенном входном воздействии. Совокупность программ системы характеризует, следовательно, совокупность ее возможных изменений во времени, присущих системе потенциально, определяемых ее структурой и реализующихся при поступлении на ее вход тех или иных воздействий" [2]. Разработка и уточнение понятия алгоритм долгое время велись исключительно с точки зрения планирования. Так, в [1] говорится: "Вообще под алгоритмом мы интуитивно понимаем некоторое формальное предписание, действуя согласно которому можно получить нужное решение задачи". Причем "алгоритмом традиционно называют лишь строго определенную систему правил ...". И наконец, определение, удовлетворяющее математика: "Алгоритмом называется любая процедура, сводящаяся к вычислению значений целочисленной функции на соответствующей машине Тьюринга". Выработке такой точки зрения способствовали два обстоятельства. Во-первых, алгоритм традиционно рассматривался как предписание, адресованное человеку, который в одиночку может решить некоторую задачу, причем строго последовательно, выполняя друг за другом некоторые достаточно простые операции. Именно это имел в виду аль-Хорезми (имя которого обессмертилось, когда в Европе был введен термин "алгоритм"), следующим образом описывая правила ведения торговых расчетов; "Величина предлагаемого сопоставлена цене запрашиваемого и цена предлагаемого сопоставлена величине запрашиваемого. Из этих четырех чисел три всегда известны и одно неизвестно. И правило таково: ты смотришь на три известных числа и нет другого способа, как взять два известных сопоставленных числа и перемножить, каждое со своим сопоставленным, и то, что получится, разделить на оставшееся известное число, сопоставленное к которому неизвестно. И то, что ты получишь, будет неизвестным числом, о котором был вопрос, и оно сопоставлено числу, на которое ты делил" [37]. Во-вторых, понятие алгоритма развивалось в основном на почве математических задач с привычной схемой "дано ..., найти ...". При этом считалось, что исходные данные однозначно определяют результат и алгоритм представляет способ получения последнего, причем за конечное число шагов. В теории автоматов такому алгоритму соответствует автономный автомат, исходное состояние которого детерминированно переводится в заключительное. Оба отмеченных выше свойства, последовательность выполнения и детерминированность результата, слиты в следующем определении: "Алгоритм – это точное предписание, которое задает процесс последовательного преобразования конструктивных объектов, происходящий дискретными "шагами", начинающийся с произвольного начального данного и направленный на получение некоторого искомого результата, однозначно определяемого этими начальными данными" [3]. Аналогичное, слегка уточненное определение зафиксировано в Математической энциклопедии: "АЛГОРИТМ, алгоритм, – точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного А. исходных данных) и направленный на получение полностью определяемого этим исходным данным результата" [54]. Ясно, что здесь речь идет об алгоритме планирования, который задает разложение во времени задачи в целом на серию подзадач, решаемых на отдельных шагах. С появлением ЭВМ и других устройств и систем дискретной переработки информации алгоритмы стали реализовываться автоматически, машиной. Саму машину, а точнее ее функциональные свойства, также можно описывать посредством алгоритмов, но такие описания лучше рассматривать не как алгоритмы планирования, а как алгоритмы поведения. Такими формальными описаниями представляются как функциональные свойства отдельных частей машины, которые могут при этом дробиться вплоть до логически неделимых элементов, так и способ их взаимодействия. С точки зрения классических представлений об алгоритме такие формы кажутся непривычными, однако они хорошо согласуются с новыми воззрениями, получившими развитие в связи с исследованиями алгоритмов управления. Итак, мы подошли к определению основного в данной работе понятия – алгоритма логического управления. Приведенные выше определения направлены, по существу, на вычислительные алгоритмы. Однако алгоритмы управления, в том числе и логического, принципиально отличаются от вычислительных. Они описывают способ общения гипотетической управляющей системы с некоторой средой, или объектом управления, такой способ, при котором ведется постоянный обмен информацией между системой и объектом управления. При этом теряет смысл понятие исходного данного, поскольку обрабатываемые алгоритмом управления данные могут поступать на его вход нескончаемым потоком. Целью алгоритма является уже не получение некоторого конкретного искомого результата в концентрированной форме, а выдача ответной последовательности управляющих сигналов, регулирующих поведение объекта управления. Алгоритм управления естественно понимать в широком смысле, интерпретируя его иногда как алгоритм выполнения некоторой сложной операции, а иногда – как алгоритм регулирования определенных параметров объекта управления или как алгоритм поведения некоторой системы в окружающей среде. Формально можно определить его как схему разложения во времени некоторой сложной операции управления на более простые, играющие роль базисных в данном алгоритмическом разложении. В алгоритмах логического управления все эти операции описываются посредством логических переменных – дискретных переменных с конечным числом значений, чаще всего двоичных, т.е. булевых. В терминах таких переменных представляются как информация, поступающая от разнообразных датчиков, расположенных в объекте управления, так и управляющие сигналы, вырабатываемые устройством управления. Более точные определения можно дать, конкретизировав класс рассматриваемых алгоритмов и определив способ их описания. Последнее означает, что требуется задать синтаксис и семантику схем алгоритмического разложения и уточнить порядок выбора его базиса. Другими словами, предложив для описания интересующих нас алгоритмов некоторый формальный язык, можно заодно и уточнить понятие алгоритма логического управления. Языки логического управления. Для описания алгоритмов логического управления нужен язык. Прежде всего, он должен быть формальным, не допуская неоднозначности толкования представленных в нем алгоритмов, нежелательной и при "ручном" проектировании, а при автоматизированном – особенно вредной. Кроме того, язык должен быть достаточно универсален, чтобы с его помощью можно было описывать широкий класс алгоритмов логического управления. Наконец, он должен быть и достаточно простым, чтобы можно было рассчитывать на успешное его внедрение в инженерную практику, а также для того, чтобы облегчить развитие теории формальных преобразований в рамках этого языка, способствуя тем самым автоматизации процессов проектирования. При всем при том алгоритмический язык должен быть эффективным. Это значит, что алгоритмы должны представляться сжато и понятно, в форме, удобной для обозрения. Предпочтительно наличие в языке двух форм: графической и символьной. Как показывает практика, графическая форма удобна при обучении, когда описываются сравнительно простые алгоритмы, а символьная – при представлении более сложных алгоритмов, при выполнении формальных преобразований над алгоритмами и, конечно, при работе с ЭВМ. Добиться высокой эффективности языка поможет его проблемная ориентация, учет особенностей алгоритмов рассматриваемого класса. Характерными особенностями алгоритмов логического управления являются параллелизм и асинхронность. В самом общем виде параллельный алгоритм можно определить как такой алгоритм, в котором допускается и предусматривается возможность одновременного выполнения нескольких операций. Заметим, что в некоторых работах термин "алгоритм" сохраняется для чисто последовательных алгоритмов, а вместо термина "параллельный алгоритм" используется "коллектив алгоритмов" [43]. Вероятно, такой терминологический подход обусловлен проблематикой конструирования и программирования многопроцессорных вычислительных машин, в которых число процессоров фиксировано и каждый из них выполняет свой последовательный алгоритм, взаимодействуя при этом с другими через общую память. Здесь на первый план выступает именно поведенческий аспект: "коллектив алгоритмов" описывает поведение соответствующего коллектива процессоров. Однако такое представление о параллельном алгоритме не всегда удобно. Допустим, что алгоритм должен описать способ решения некоторой сложной производственной задачи путем ее разложения на операции, для реализации которых создаются специальные бригады, причем только на время выполнения операции, после чего бригада расформировывается. В таком случае алгоритм лучше уподобить сетевому графику, дополненному условиями выбора ветвей, а это уже будет алгоритм планирования, причем параллельной. Он указывает лишь порядок выполнения операций, безотносительно к их возможным исполнителям [20]. Первоначальное развитие теории параллельных алгоритмов было связано, по-видимому, с распараллеливанием вычислительных алгоритмов с целью их реализации на многопроцессорных вычислительных комплексах. Основа этой теории уходит, таким образом, в теорию вычислений, а практический выход – в практику параллельного программирования. Параллелизм логического управления – другой природы. Он, как говорится, естественный. Этот параллелизм обусловлен существованием множества параллельно протекающих процессов в объекте управления – технической системе, реализующей некоторую производственную технологию. Алгоритм управления этими процессами должен обеспечить их правильное взаимодействие, надлежащим образом реагируя на сигналы, приходящие от различных компонент системы. Традиционное управление с использованием управляющей ЭВМ осуществляется последовательным алгоритмом. При этом, как правило, проводится циклический опрос всех датчиков объекта управления, последовательно обрабатывается получаемая при этом информация и циклически же распределяются вырабатываемые управляющие воздействия. Однако, последовательный алгоритм управления параллельными процессами, ориентированный на реализацию на одном процессоре, может оказаться недостаточно быстрым, в связи с чем потребуется его распараллеливание с целью построения многопроцессорной системы управления. Нужда в такой системе может возникнуть и при децентрализации управления, когда структура управляющей системы должна в какой-то степени повторять структуру разнесенной в пространстве технической системы, являющейся объектом управления. Стоит ли разрабатывать последовательный алгоритм управления параллельными процессами, если затем он будет распараллеливаться? Не лучше ли сразу разрабатывать параллельный алгоритм, непосредственно в нем фиксируя правила взаимодействия параллельных процессов в объекте управления, заодно уточняя их и, возможно, оптимизируя по некоторым критериям. Очевидно, что такой подход более перспективен. Непосредственная разработка параллельных алгоритмов логического управления особенно важна в том случае, когда управление требуется реализовать не программно, а схемно, например посредством логической сети, функциональные свойства которой описываются системой булевых уравнений. Очевидно, что в такой сети все элементы работают параллельно. В этом случае параллелизм объекта управления должен быть отображен соответствующим параллелизмом в алгоритме управления, а последний – реализован логической сетью, которую также можно трактовать как своеобразную форму алгоритма логического управления, выраженную в заданном элементном базисе. Присущий техническим системам параллелизм объекта управления обычно неразрывно связан с асинхронностью. Она выражается в некоторой неопределенности в затрате времени на выполнение входящих в алгоритм операций. Как известно, последовательные алгоритмы некритичны к такой неопределенности, поскольку последняя не оказывает никакого влияния на выполнение алгоритма, кроме влияния на скорость выполнения. Для параллельных алгоритмов положение в корне меняется: указанная неопределенность может приводить к состязаниям между одновременно выполняемыми операциями, и в ряде случаев эти состязания могут оказаться опасными, вызывая нарушения в работе алгоритма. Говорят, что в таких случаях алгоритм некорректен. Таковы особенности алгоритмов интересующего нас класса, которые следует учитывать при разработке языков логического управления. Об авторе
Окончил Томский гос. университет (1956), В 1959–71 гг. ассистент, старший научный сотрудник, заведующий лабораторией счетно-решающих устройств, профессор, заведующий кафедрой математической логики и программирования в Томском университете. В 1971–94 гг. заведующий лабораторией логического проектирования, с 1994 г. главный научный сотрудник Института технической кибернетики Национальной АН Беларуси, одновременно профессор Белорусского государственного университета информатики и радиоэлектроники. Работы по теории автоматов, системному программированию, логико-комбинаторным методам в технике и информатике. Предложил язык программирования логических задач ЛЯПАС, на базе которого была создана серия систем автоматизированного проектирования дискретных устройств, и методы реализации параллельных алгоритмов логического управления взаимодействующими процессами. Разработал серию практически эффективных алгоритмов минимизации булевых функций и систем, решения больших систем логических уравнений и переопределенных систем линейных логических уравнений с приложениями в логическом синтезе и защите информации. Обобщил методы теории булевых функций на конечные предикаты, разработал логический подход к распознаванию образов в пространстве булевых и многозначных признаков. Автор более 400 научных работ, в т. ч. 11 монографий. Основные труды: LYaPAS: A programming language for logic and coding algorithms (with M. A. Gavrilov). Academic Press, N.-Y., L., 1969; Алгоритмы синтеза дискретных автоматов. М., 1971; Логический синтез каскадных схем. М, 1981; Логические уравнения. Мн., 1975; Boolesche Gleichungen: Theorie, Anwendung, Algorithmen (mit D. Bochmann und Ch. Posthoff). VEB Verlag Technik, Berlin, 1984; Логика распознавания. Мн., 1988; Параллельные алгоритмы логического управления. Мн., 1999; Полиномиальная реализация частичных булевых функций и систем. Мн., 2001 (совм. с Н. Р. Тороповым). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||