Что такое гал в алгоритме
Перейти к содержимому

Что такое гал в алгоритме

  • автор:

Закон Галла: что он гласит и как применяется в IT

Рассказываем, в чем суть закономерности, как она себя проявляет и что бывает, когда эту закономерность не учитывают в процессе проектирования и разработки IT-систем.

Фото — Spencer — Unsplash

В книге «Сам себе MBA. Самообразование на 100%», написанной Джошом Кауфманом (Josh Kaufman), закон Галла приведен в следующей формулировке:

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

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

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

Минутка истории

Автор закона Джон Галл (John Gall) по профессии был педиатром, но в свободное время занимался исследованиями в области теории систем. В 1977 году он опубликовал книгу «Систематизация: как работают системы и как они терпят крах». В ней он рассказывал, что для управления любой системой необходимо понимать, как факторы среды влияют на ее функциональность. Именно в этой книге и был сформулирован закон Галла.

Свою известность закон обрел благодаря упоминанию в книге «Структурированное техническое задание», написанной системным разработчиком Кеном Орром (Ken Orr) в 1981 году. Его работа обрела широкую популярность, и на неё до сих пор ссылаются авторы современной литературы по системному анализу.

Спустя какое-то время после публикации книги Кена Орра, правилом Галла «вооружился» Гради Буч (Grady Booch), когда создавал UML. В этом языке также прослеживается концепция «от простого — к сложному»: для построения абстрактной модели системы используют отдельные классы, типы и интерфейсы.

Фото — Isaac Smith — Unsplash

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

Когда следовать закону Галла

Наиболее ярким примером для иллюстрации закона Галла служит World Wide Web. Она зародилась как локальный проект CERN — организация разрабатывала инструмент для связывания документов посредством гипертекстовых ссылок. Но со временем сеть успешно разрослась до мировых масштабов — её возможности расширялись, структура усложнялась и «обрастала» новыми протоколами (например, HTTPS, который стал развитием HTTP).

Старт разработки с MVP (minimum viable product) дает возможность оперативно протестировать идею и при необходимости изменить функциональность. Например, первая версия сервиса Uber содержала только две простые функции: вызов водителя и оплата поездки банковской картой. С их помощью команда проверила свою концепцию, привлекла пользовательскую базу и продолжила развивать продукт. Сегодня эти базовые функции усложнились: появилась возможность разделить счет между несколькими людьми, отслеживать водителей на карте и проводить автоплатежи.

Закон Галла помогает сделать UI понятнее для пользователей. Например, первая версия приложения Dropbox имела очень простой интерфейс — он представлял собой обыкновенную файловую папку. По словам разработчиков, именно эта особенность позволила привлечь большое количество новых пользователей — за несколько дней список заявок на бета-тестирование Dropbox пополнился на 70 тыс. Дополнительные функции и диалоговые окна — вроде совместного редактирования файлов — начали появляться позже.

Что бывает, когда эту закономерность не учитывают

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

В качестве примера неудачной реализации программного продукта можно привести Digital Media Initiative (DMI) — проект BBC от 2008 года. Его целью было создание масштабной платформы с in-house инструментами для монтажа видео и хранения контента. В основу DMI сразу заложили большое количество спецификаций, реализовать которые на практике не получилось. Разработка тянулась пять лет, но так и не была завершена. Сначала от проекта отказался исполнитель — компания Siemens — а затем и сама BBC. Всего на DMI потратили 100 млн фунтов.

Примером неудачной реализации интерфейса может служить сервис Google Wave. Он должен был объединить функциональность онлайн-форумов, социальных сетей, мессенджеров и систем управления версиями. Создатели платформы предполагали, что она станет универсальным способом общения. Но в попытке заменить «всё и сразу» команда разработчиков перегрузила приложение разными функциями. В результате пользователям приходилось долго разбираться с особенностями интерфейса. Сложности возникали даже с поисковой строкой сервиса — для работы с ней нужно было знать специальные теги. Проект развивали с 2009 по 2010 год — система не оправдала надежды разработчиков и пользователей и проект свернули.

Чтение по теме:
  • Джош Кауфман объясняет закон Галла
  • Закон Галла в применении к стартапам
  • Основные концепции системного подхода
  • Книга: «Компьютерные сети: системный подход» на GitHub
  • Виталий Грицай: о стратегии международного развития ITGLOBAL.COM
  • Зачем клиенту облачного провайдера знать об уровне надежности ЦОД
  • Как бизнесу защититься от троянов-вымогателей
  • ITGLOBAL.COM стала первым официальным реселлером Alibaba cloud в России
  • ITGLOBAL.COM запустила корпоративную облачную площадку в Республике Беларусь
  • ITGLOBAL.COM
  • закон Галла
  • управление разработкой

Собственный опыт изготовления программатора GAL

Для изготовления программатора я взял за основу : GalBlast 1.2. Этот программатор поддерживает 16V8/A/B/C/D/Z/ZD, 18V10/B, 20V8/A/B/C/D/Z/ZD, 20RA10/B, 20XV10/B, 22V10/B/C/Z, 26CV12/B, 6001/B, 6002B. Выпущеные производителями Lattice,National Semiconductors, STMicrosystems. Работает в среде win 3.1/95.

Для чтения GAL используется 12 вольт для программирования от 12,0 до 20,5 вольт.
В исходной схеме используется ЦАП TLC7524 с защелкой и LM78S40 импульсный регулятор напряжения.
Посмотрел на схему и цены на указанные микросхемы и сделал следующие изменения:

ЦАП для генерации напряжения программирования/чтения.

Так как отечественная промышленность не выпускает 8-битные ЦАП с выходом по напряжению и с защелкой, то я приобрел КМОП регистр 74HC573 (1564ИР33) и на резисторах 10 и 20 килоом собрал R-2R матрицу. Но я плохо прочитал документацию и сделал ошибку:
74HC573 при высоком уровне на ножке LE (Latch Enable) пропускает входной код на выход, а защелкивает информацию переходом с высокого в низкий уровень.
В исходной схеме используется ЦАП TLC7524 которая пропускает входной код к преобразователю (DAC) при низком уровне и защелкивает переходом из низкого в высокий.
Так что пришлось собрать на транзисторе инвертор.
Если собирать ЦАП на 74HC373/374 (1564ИР22/23) то инвертор не нужен, но расположение ножек не удобное для сборки R-2R матрицы.
Для развязки от нагрузки я применил ОУ LM358 . Эта микросхема дешевая и имеет отличительную особенность — выходной сигнал может опускаться до 0 вольт. А также спроектирована для однополярного питания от +3 до +32 вольт.
Если выходное напряжение не опускается ниже опорного в регулируемом стабилизаторе(1,23 вольта, смотри ниже) то стабилизатор закроется и на выходе получим 0.
Проверял тестером 0.04 вольта.

Переработаная схема ЦАП.

Напряжение программирования и питание.

Так как мне не попадались 3.3 вольтовые GAL то переключатель(перемычку) 5/3.3V я исключил.
Вместо LM78S40 я использовал микросхему RC2951 . Она выпускается разными производителями и может наименоваться LP2951, AS2951, LP2951(118ЕН2) итд.
Эта микросхема представляет собой линейный регулируемый стабилизатор от 1,24 до 29 вольт при входном напряжении до 30 вольт и токе нагрузки до 100 милиампер. Кроме этого есть специальный вход для отключения выходного напряжения( TTL уровень). Единственный недостаток — обычно корпус узкий SOIC.

Обычно программируемые устройства не «любят» когда на них подается напряжение программирования, а напряжение питания отсутствует.
Этот вариант возможен при неисправности программатора или сбое компьютера. По этому я ввел цепь на транзисторе 2N3904 (любой NPN) которая отключает напряжение программирования при пропадании(не установлении) +5 вольт.

Напряжение питания для устройства я выбрал +12 вольт. Из них вырабатывается +5 вольт для аналоговой части (АЦП и LM358) на микросхеме 78L05(1157ЕН5) и +5 вольт для цифровой части 7805(142ЕН5А) .
Для выработки напряжения считывания/программирования я использовал микросхему таймера 555 (1006ВИ1) в режиме мультивибратора (частота около 10 килогерц) со схемой удвоения напряжения.

В принципе можно исключить стабилизатор на 78L05 и поставить RC цепочку 10 ом и 100 микрофарад, схема должна работать.
Так как основная моя работа — ремонт системных плат и мой рабочий компьютер всегда разобран, то я вытащил +12, +5 вольт из системного блока. Стабилизатор установил только для аналоговой части.

Регулирование выходного напряжения происходит по исходной схеме. На операционный усилитель подается задающее напряжение от ЦАП (вход -) и выходное напряжение регулятора (вход + ). Разностное напряжение подается на вход Feed Back стабилизатора RC2951. Внутри RC2951 это напряжение сравнивается с опорным 1,23 вольта и регулируется выход.
То есть RC2951 это ОУ у которой в цепи обратной связи стоит ОУ LM358 и RC2951 в свою очередь является обратной связью для ОУ LM358.
Таким образом увеличение напряжения ЦАП вызывает увеличение входного сигнала (-) на LM358 и уменьшение выходного сигнала. Это уменьшение воздействует на вход Feed Back RC2951 и она воспринимает это как уменьшение выходного напряжения и увеличивает его. Увеличение выходного напряжения возвращается на на вход «+» LM358 и уравновешивает увеличение на выходе «-«. При уменьшении выходного напряжения ЦАП все происходит на оборот.

Таким образом замыкается отрицательная обратная связь и система из двух ОУ должна прийти к равновесию.

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

Вместо реле включения питания на программируемую микросхему я применил транзисторный PNP ключ в обратном включении.
Транзистор КТ209К использован для ключа по тому что он имеет низкое напряжение насыщения до 0,4 вольта (обычно 0,2).
Резистор между эмиттером и базой прикрывает транзистор в закрытом состоянии, а через резистор в цепи базы протекает ток на землю в открытом состоянии. Этот ток должен превышать ток потребления программируемой микросхемы поделенный на h21э.
К сожалению с увеличение тока коллектора h21э падает и в паспорте транзистора он указан на 10 милиамперах. По этому нужно нагрузить ключ током порядка 100 милиампер и подобрать резистор так чтобы напряжение после ключа было >= 4,8 вольт а выключенном состояние откля. Резистор между базой и эмиттером должен надежно прикрывать транзистор.
Для уменьшения мороки для головы и рук, лучше наверное использовать реле как в исходной схеме, или просто механический выключатель.

Переработаная схема питания.

Буферная развязка сигналов.

Теперь развязка остальных сигналов
В исходной схеме использовались прямые буфера с открытым коллектором 7417 (155ЛП4/1533ЛП17) Как оказалось проблема на рынке купить отечественный аналог. А платить за импортный 40 центов не охота. А вот обычный шинный формирователь типа 74LS245 (1533АП6 ) с удобным расположением выводов есть и стоят 5 центов.
Применение открытого коллектора оправдывается при программировании 3,3 вольтовых GAL. При этом входные сигналы на GAL равны или чуть меньше напряжения питания. Обычно КМОП допускают подачу на вход напряжения не превышающего питания + 0,5 вольт.
Я померял выходное напряжение для 1533АП6 и оно оказалось 3,8 вольта. Так что если хотите программировать GAL с питанием 3,3 то можно применить 555АП6 у нее обычно выходное напряжение 3,5 вольта.
Не задействованые ножки GAL я зашунтировал на землю попавшимися под руку резисторами от 2 до 10 килоом. Садить на землю не рекомендую, так как после снятия напряжения чтения/программирования не задействованные ножки могут оказаться выходами (в соответствии с прошивкой) и при логической 1 пойдет перегрузка выхода по току.

Переработаная схема буфера.

Слева все выходы от порта принтера, справа ножки микросхемы.
Исключение ножка SDOUT — это выход из GAL который подается на вход принтерного порта ACK#.
Можно еще поставить 3 светодиода+резисторы для индикации напряжения питания на плате, напряжения питания и программирования на чипе .

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

Для личного пользования лучше собирать монтажным проводом на макетной плате.
Если будете паять проводом который залуживается паяльнико без зачистки (ПЭВТЛК) то лучше его залуживать отдельно а затем впаивать в схему. Чтобы исклюячить массовые не пропаи.

Я в начале припаял +5 вольт и впаял регистр ЦАПа.
Подал напряжение, Потрогал — микросхема холодная.

Припаял сигнальные провода к регистру ЦАПа.
Подал напряжение, всунул в порт принтера Потрогал — микросхема холодная.

И так далее. От лени рассчитывать/подбирать делитель выходного напряжения поставил подстроечный резистор.

Для проверки прохождения сигнала можно использовать программу debug.

Набираете debug в режиме DOS и вперед.

«o 378 0» — вывели в порт данных 0.
«o 378 4» — все биты в 0, бит D2 в 1.
«i 379» — и на экране входной байт регистра состояния принтера.

И паяльником, тестером, осцилографом, кусачками по плате пока не заработает :-).

Для лентяев три програмки для тестирования с исходниками на TASM 2.0.
Одна защелкивает код 0 в регистре ЦАП, вторая FF,а третья формирует пилу в течении минуты на выходе ЦАП.

Тестирование в полном комплекте.

После того как программатор собран и потестирован можно попробовать запустить программу при подключенном программаторе.
Я пишу обычно свои программки в Delphi или assemblere. Но вот эта часть из исходного текста на C++ :

/* set/reset individual pins of LPT port */
static void SetSTROBE(BOOL on)
<
output(lptbase[lpt]+2,on?input(lptbase[lpt]+2)&~0x01:input(lptbase[lpt]+2)|0x01);
>

Наводит на мысль что при записи в порт, программа считывает последнее выведенное в порт значение, накладывает на него маску и выводит его в порт обратно.
На мой взгляд это справедливо если порт находиться в стандартном режиме(не PS/2, EPP,ECP ). Так что выставтье в Setup BIOS режим порта — стандартный (SPP).

В остальном программа работает великолепно: сама находит адрес порта, считывает параметры для записи и з чипа, корректно читает и пишет Jedec файл и тд.
Скомпилировать исходник на Borland С++ версии 4.5 и 5.0 работающий корректно не удалось. В меню появился порт LPT3.
Мне удалось найти информацию, что исходник написан для WIN 3.1 (по этому под win 98 Debuger не работает ), и копирайт Borland 1990/91 год.
Так что нужно компилировать (если хотите что-то изменить) На C++ более старой версии.

Перед первой установкой программируемой микросхемы в сокет, можно вместо программирующеко напряжения подать +12V.
Таким образом можна настроить чтение из GAL при не работающем/собраном/настроеном ЦАП/регуляторе напряжения.

После настройки чтения можно настроить ЦАП/регулятор напряжения.
. Нужно изьять микросхему и восстановить схему программатора.
В программе Galblast в меню Порт есть пункт Setup. Выберите его и программа защелкнет в ЦАП код предположительно соответствующий 12 вольтам на выходе регулятора. Желательно подкрутить резистором Vpp_MAX к 12 вольтам.
Движение движка MAX вниз по схеме дает увеличение выходного напряжения на выходе.

Для проверки я выставил 11,95 вольт (попасть в 12,00 обычным резистором тяжело).
Я выставил 20,00 вольт и 100 милисекунд время программировани(программа предложила шить в ручном режиме), а за тем измерил выходное напряжение. Оказалось 19,95. Синтервалом 30 минут повторил опыт — 11,97 и 19,89 вольт. Если шить непрерывно и в течении длительного времени то из за теплового дрейфа результат наверное будет хуже. Но это же любительский программатор !
Можно и накрутить 11 или 13 вольт, программа пересчитает и занесет в реестр Windows этот параметр, и подгонит напряжение к 12 вольтам.

Программы для создания Jedec файла.

На предыдущей странице есть несколько ссылок на программы для создания Jedec файла. Я сходил на сайт Atmel и скачал Atmel-WinCUPL, Version 5.1. В последний раз можно было перейти по этой ссылке.
Долго я правда не мог понять почему 16V8 понимает, а 20V8 нет. Понимает только 20V8A, да и от русских букв, даже в коментариях, вываливается. А в остальном можна работать

Какие микросхемы удалось потестить.

Выковырял из плат следующие микросхемы: National GAL20V8A, Lattice GAL16V8A, Cypres PALCE16V8 и PALCE20V8, Atmel ATF20V8.


    National GAL20V8A, Lattice GAL16V8A
    Читаются/пишутся/стираются без проблем.

Применение параллельных вычислений в задачах многокритериальной оптимизации и их реализация в среде MatLab Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Филатова Е.С., Филатов Д.М.

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Филатова Е.С., Филатов Д.М.

Применение генетических алгоритмов для решения задач оптимизации на параллельных и распределённых вычислительных системах

Минимизация потерь энергии при пуске частотно-регулируемого привода на основе генетического алгоритма оптимизации

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

Метод мета-оптимизации поисковых алгоритмов оптимизации
Генетический алгоритм поиска параметров ПИД-регуляторов системы стабилизации шагающего робота
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Применение параллельных вычислений в задачах многокритериальной оптимизации и их реализация в среде MatLab»

сдвигом и поэтому хорошо работают только для неподвижных объектов. При сканировании, человек обычно находится в ортостатическом положении (неподвижном), однако при этом все равно происходят непроизвольные телодвижения. Они приводят к динамическим погрешностям для ВФ, и поэтому, оптимальным методом для определения 3D рельефа человека является метод ПФ, который позволяет по единственному изображению (со спроецированными контрастными полосами) восстановить 3D рельеф с максимальной точностью и достаточным разрешением. В современных медицинских системах [6] точность сканирования достигает 0.1 мм.

1. Salvi J., Pages J., Baffle J. Pattern codification strategies in structured light systems // Pattern Recognition. — 2004. — Vol. 37. — P. 827-849.

2. Geng J. Structured-light 3D surface imaging: a tutorial // Advances in Optics and Photonics. — 2011. — № 3. — P. 128-160.

3. Gorthi S. S., Rastogi P. Fringe Projection Techniques: Whither we are? // Optics and Lasers in Engiering. — 2010. — Vol. 48. — P. 133-140.

4. Yu W. Development of a three-dimensional anthropometry system for human body composition assessment // Ph. D. thesis, University of Texas at Austin, 2008.

5. Womack K.H. Interferometric phase measurement using spatial synchronous detection // Opt. Eng. — 1984. — Vol. 23, No. 4. — P. 391-395.

6. Сарнадский В.Н., Уберт А.И. Алгоритмы автоматического восстановления 3D модели поверхности туловища человека методом компьютерной оптической топографии // Материалы XI международной конференции «Актуальные проблемы электронного приборостроения». — 2012. — Т. V — С. 81-88.

ПРИМЕНЕНИЕ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ В ЗАДАЧАХ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ И ИХ РЕАЛИЗАЦИЯ В СРЕДЕ MATLAB1

© Филатова Е.С.*, Филатов Д.М.Ф

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина), г. Санкт-Петербург

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

1 Работа выполнена при финансовой поддержке гранта Президента Российской Федерации № 14^56.14.3734-МК.

* Доцент кафедры Систем автоматического управления, кандидат технических наук.

* Доцент кафедры Систем автоматического управления, кандидат технических наук.

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

Ключевые слова генетический алгоритм, параллельные вычисления, математический пакет MatLab.

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

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

— модель «мастер-раб» (master-slave GAs). Особенность подхода состоит в синхронной работе популяций. Популяции обладают общим адресным пространством. Мастер или управляющий процесс осуществляет развитие популяции, а подчиненные занимаются расчетом целевой функции;

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

— модель «сетевого взаимодействия» (coarse-grained GAs). Каждый процесс моделирует свою популяцию, используя собственное адресное пространство. Взаимодействие с другими популяциями определяется из описания связей (топологии сети взаимодействия).

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

Организация параллельных вычислений в MatLab

Для реализации технологии параллельных и распределенных вычислений в MatLab предусмотрены два пакета расширения, работающих в связке: DCT (Distributed Computing Toolbox) и MDCE (MatLab Distributed Computing Engine).

Дадим несколько определений основным понятиям, которые будут встречаться далее.

Клиент — текущая сессия MatLab, в которой определяются и из которой отправляются задачи.

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

Главный узел — узел кластера, предназначенный для запуска менеджера задач.

Узел — компьютер, который является частью кластера.

Задача — полностью описанная вычислительная операция большой размерности для выполнения в MatLab, состоящая из набора подзадач.

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

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

Рабочий процесс — системный процесс MatLab, выполняющий вычисление подзадач.

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

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

Рис. 1. Конфигурация распределенных вычислений

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

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

Если используется менеджер задач The MathWorks, каждая машина, на которой запущен рабочий процесс или менеджер задач должна иметь MDCE службу. Служба MDCE восстанавливает рабочий процесс и менеджер задач в случае неисправности машины, то есть она автоматически возобновляет их сессии, которые были запущены перед аварией [3].

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

Типичная сессия параллельных вычислений для клиента включает следующие шаги:

1. Получение ссылки на менеджер задач при помощи специальной функции MatLab.

2. Формирование задачи, в которую будут записаны некоторые подзадачи.

3. Формирование подзадачи — сегмента основной задачи.

4. Постановка задачи в очередь на исполнение в менеджер задач.

5. Получение результатов работы.

6. Удаление задачи и освобождение ресурсов памяти.

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

1. Запуск службы MDCE.

2. Запуск планировщика. Запуск менеджера задач осуществляется при помощи команды Startjobmanager, а при помощи команды Stopjob-manager его остановка.

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

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

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

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

Генетический алгоритм определения параметров адаптивного регулятора

Задачей генетического алгоритма является подбор параметров адаптивного регулятора с сигнальным алгоритмом адаптации [k r2] для электрогидравлического привода рулевой поверхности самолета, при которых обеспечивается наискорейшее затухание переходного процесса разности выходных координат объекта управления и эталонной модели.

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

1. Создание начальной популяции.

Каждая популяция представляет собой набор из 20 хромосом, в свою очередь представляющих собой пары коэффициентов адаптивного регулятора [kj r2J, где i = 1^20. Двоичное кодирование хромосом не применяется, каждая хромосома состоит из двух чисел типа double (см. рис. 2).

хромосома 1 хромосома 2

Рис. 2. Формирование начальной популяции

Обозначения, принятые на рис. 2: к — шаг выполнения генетического алгоритма (0 обозначает начальную популяцию), Р — текущая популяция, К -коэффициенты, входящие в состав хромосомы. Запись К(0) обозначает, что данная хромосома сформирована на начальном шаге (начальная популяция).

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

2. Оценивание приспособленности.

В качестве функции приспособленности каждой хромосомы вычисляется время регулирования для ошибки следования системы за эталонной моделью. Для этого необходимо промоделировать разработанную в Ма1ЬаЪ 81-шиИпк структурную схему электрогидравлического привода, после чего по

[K(0)11 K(0)i2] [K(0)21 K(0)22]

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

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

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

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

3. Применение генетических операторов.

В классическом генетическом алгоритме применяются два основных генетических оператора: оператор скрещивания и оператор мутации.

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

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

mutationChildren(i,:) = parent + scale .* randn(1,length(parent)).

Параметр scale, который входит сомножителем в данном выражении определяет степень мутации. Если этот параметр равен 0, то никаких изменений в особи не происходит.

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

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

5. Условие останова алгоритма.

Условием останова в данном случае является два критерия:

1. Достигнуто конечное число итераций равное 50.

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

Генетический алгоритм поиска наилучшей архитектуры нейро-нечеткой сети

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

Подробно реализация данного генетического алгоритма изложена в [4] и практически аналогична схеме, описанной для предыдущей задачи с двумя отличиями. Первое отличие заключается в размере и виде популяции, которая представляет собой набор особей [Гц r2i r3i r4i], i = 1^30. Каждая хромосома в особи является радиусом кластеризации для каждой из четырех ННС, реализующих систему прогнозирования. Начальная популяция задается случайным образом в интервале [0, 1].

Второе отличие заключается в реализации процедуры отбора турнирным методом.

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

Реализация параллельного генетического алгоритма в среде MatLab

В качестве кластера для реализации распараллеливания были использованы две рабочих станции (ПК) на базе двуядерного процессора. На каждом ПК устанавливается среда MatLab Simulink и пакеты расширений Distributed Computing Toolbox и MATLAB Distributed Computing Engine, а так же вспомогательный инструментарий Genetic Algorithm Toolbox для реализации ГА.

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

пакета MatLab Fcnvectorizer. Эта программа является частью инструментария Genetic Algorithm Toolbox для реализации ГА. Важным шагом, для работы параллельной программы, является запись в корневой программе Fcnvectorizer команд, которые осуществляют подготовку к параллельным вычислениям и по которым происходит непосредственный запуск параллельной программы.

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

1. Программа моделирования Start. В данной программе реализуется настройка и вызов на исполнение генетического алгоритма.

2. Программа Fcnvectorizer (корневая программа Genetic Algorithm Toolbox). В ней происходит настройка кластера состоящего из двух рабочих станций, создание параллельной задачи, её свойств, создание параллельного задания, выполнение задачи и вывод результата. Также в этой программе происходит распараллеливание популяции между двумя узлами кластера при помощи вызова специально созданных подпрограмм Par_chromos и Gal. Таким образом, происходит параллельная работа двух независимых процессов, каждый из которых выполняется в отдельном программном потоке.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Par_chromos — параллельная задача. Здесь происходит процесс распараллеливания исполнения программы Gal на два рабочих процесса.

Gal -программа расчета функции оптимизации для ГА. В ней после параллельного моделирования параметров (для первой задачи — это моделирование в Simulink, для второй — запуск системы прогнозирования) происходит получение значения функции приспособленности.

Параллельная программа Par_chromos является подпрограммой корневой программы Fcnvectorizer.

Алгоритм распараллеливания вычислений следующий:

1. Формирование генетическим алгоритмом популяции состоящей из определенного набора хромосом. Популяция будет делиться на количество узлов в кластере.

2. Распараллеливание процесса моделирования используя уникальный идентификатор labindex в программе Par_chromos. Он присваивает каждому рабочему процессу свой порядковый номер. Наш кластер состоит из двух рабочих станций. Если labindex равен единице, то первый рабочий процесс (первый компьютер) из кластера моделирует первую половину популяции. Если labindex равен двум, второй рабочий процесс (второй компьютер) из кластера моделирует вторую половину популяции.

3. Далее программа Gal запускает работу генетического алгоритма.

Таких итераций может быть множество. Процесс распараллеливания

будет проходить каждый раз.

Особенности распараллеливания, связанные с MatLab и Simulink:

1. Математический пакет MatLab должен быть запущен на всех рабочих станциях входящих в кластер;

2. Брандмауэр операционной системы должен быть либо отключен, либо следует произвести его настройку;

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

4. Все созданные для параллельной работы программы должны находиться на главной рабочей станции;

5. Параметры, которые требуются для настройки схемы Simulink, необходимо прописать как в командной строке MatLab, так и непосредственно в параллельной программе;

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

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

Организация программного распараллеливания работы генетического алгоритма между двумя рабочими станциями позволила повысить быстродействие в среднем в 1,5-2 раза по сравнению с реализацией алгоритма на одном ПК.

1. Второв В.Б., Филатов Д.М. Вопросы расчета параметров адаптивного регулятора в системе с эталонной моделью и сигнальной адаптацией // Известия СПбГЭТУ «ЛЭТИ». — СПб., 2009. — № 10. — С. 39-46.

2. Кныш Д.С., Курейчик В.М. Параллельный генетический алгоритм с нечетким оператором миграции // «Искусственный интеллект». — Донецк, 2010. — № 3. — С. 73-80.

3. Оленев Н.Н. Параллельное программирование в Matlab и его приложения. — М.: ВЦ РАН, 2007. — 120 с.

4. Филатова Е.С., Филатов Д.М., Стоцкая А.Д. Генетический алгоритм поиска наилучшей архитектуры нейронечеткой сети // Тезисы докл. Меж-дунар. конф. по мягким вычислениям и измерениям SCM-2015 (Санкт-Петербург, 19-21 мая 2015 г.). — Saint-Petersburg, 2015. — Vol. 1. — P. 379-382.

PAL, GAL и путешествие в цифровое ретро

Идея сделать цифровые логические микросхемы с изменяемой структурой была всегда. Почему? Достаточно посмотреть на толстенный каталог чипов серии TTL 74xx (или советской К155), чтобы такая идея самозародилась. В СССР почти у каждого инженера и радиолюбителя был справочник В.Л. Шило «Популярные цифровые микросхемы», который вышел каким-то невероятным тиражом. Но всё равно, хотелось иметь некий «универсальный кристалл», из которого можно сделать все остальные микросхемы (ну хорошо, не все, но многие).

Конечно же, полупроводниковая промышленность тоже была не прочь удовлетворить такой спрос. Поэтому, начиная с конца 1960-х, на рынке каждый год появлялось огромное количество подобных устройств из класса PLD (Programmable Logical Device), самых разнообразных архитектур. Это было интереснейшее время! На рынке постоянно появлялось что-нибудь новенькое. Здесь были и различные ULA и БМК и EPROM-устройства на базе пережигаемых перемычек (82Sxxx) и PLA, у которых программировались оба слоя: «И» и «ИЛИ» (привет нашим К556РТ1 и К556РТ2) и т.д. Обзор этих ретро-технологий – тема для отдельной статьи. Мы же сделаем лишь обзор того, что «выстрелило» и стало мэйнстримом.

Сразу хочется попросить извинения у опытных электронщиков и разработчиков FPGA. Эта статья нисколько не имеет цели вторгнуться на их территорию, а только дает исторический обзор «как это было».

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

Так вот, в далекие 1970-е годы компания-производитель ПЗУ Monolithic Memories Inc. (MMI) выпустила на рынок очередное семейство программируемых чипов. Семейство ВНЕЗАПНО оказалось настолько удачным, что в 1978 году MMI зарегистрировала торговую марку PAL® (Programmable Array Logic) и стала лицензировать технологию таким гигантам, как Texas Instruments (серия TIBPAL), National Semiconductor, Philips (PLUS), AMD (AMPAL) и другим.

Даже в СССР не отставали и выпустили клоны, серию К1556.

В чем же секрет? Спроектированное инженерами и для инженеров семейство MMI PAL представляло собой практически чистое воплощение идеи ДНФ (Дизъюнктивная Нормальная Форма).

Здесь надо сделать логическое отступление и взглянуть, что же это такое, ДНФ и откуда оно взялось.

Матлогика

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

Лирическое отступление: есть огромное искушение ничего не писать, а просто посоветовать взять и прочитать недавно переведенный учебник Харрис&Харрис «Цифровая схемотехника и архитектура компьютера», а конкретно главу 2 «Проектирование комбинационной логики». Это отличная книга! Там даже есть параграф про PAL (п.5.6 «Матрицы логических элементов»), но такое ощущение, что его безжалостно сократили в очередной редакции.

А для тех, кто захотел канонично, «от печки», разобраться в предмете поглубже (бывает!) можно порекомендовать книги 60-х годов по проектированию ЭВМ. Например, книгу “Синтез цифровых автоматов” В.М. Глушкова (тот самый, который ОГАС!) (М. Государственное издательство физико-математической литературы, 1962г). Книга настолько олдовая, что фамилия Карно записывается как Карнаут. Или можно предложить книгу ”Синтез схем электронных цифровых машин” (Е.Н.Вавилов, Г.П.Портной М. ”Советское радио” 1963).

В современных отечественных учебниках, чем дальше, тем больше этот раздел ужимается.
Например учебник Угрюмов Е.П. «Цифровая схемотехника» издания 2007 года еще содержал главу про PAL, а издания 2010 — уже нет. В настоящее время данная наука почти полностью перекочевала в пыльные бумажные методички кафедр по специальности 230101. Вдобавок, попытка дать студентам этот материал наталкивается на стойкое сопротивление: разговоры про «основы» воспринимаются учащимися как «too old» то есть как совершенно ненужный, устаревший хлам. Даже тут, на Хабре есть несколько статей на данную тему, и комментарии наполнены стонами ”Да-да! Нас тоже зачем-то насиловали этим весь первый курс!”.

Так вот, автор сбрасывает себя обязанность писать про пресловутые ”основы”. Предполагается, что читатель, который заглянул на огонек, всё-таки понимает, что такое булева алгебра, что такое И, ИЛИ, НЕ, знает теорему де Моргана и умеет читать схемы на логических элементах.

ПРИМЕЧАНИЕ: Мне тут подсказывают, что в современном курсе цифровой электроники эта дисциплина (Дискретная математика) и Цифровая схемотехника чаще всего разделены на два предмета и учебники у них — разные. А Харрис&Харрис в попытке впихнуть все в одну книгу породил монстра на 1600 страниц. Ну OK.

Ах да, ДНФ. В старых книжках говорится (объясняется — почему), что при достаточно сложном логическом выражении его лучше всего представить (и это можно сделать для любого выражения!) в виде дизъюнктивной нормальной формы (sum of product, SOP). Несмотря на страшное название, это очень просто. Возьмем логическую функцию Y от трех переменных, A, B, C. Пусть она принимает значение «истина» тогда и только тогда, когда все три входные переменные равны нулю или же все они равны единице. В ДНФ это запишется крайне просто:

Это так называемая алгебраическая форма. Операция «ИЛИ» тут записывается как «+», а операция «И» — как умножение и, как в обычной алгебре, опускается. Так получилось, что существует множество форматов записи (синтаксисов) булевых выражений. Вот в другой записи:

Си-шное выражение для bool переменных:

Или даже так (синтаксис PALASM):

То есть ДНФ (в алгебраической форме) выглядит как цепочка сложений т.е. многочлен (логическое ИЛИ) из произведений (логическое И) входных переменных (sum of product), причем только тех комбинаций, для которых должна получаться «истина». Интуитивно это довольно понятно: Истина, когда это И это, ИЛИ же когда то И то. Как выше упоминалось, в форме ДНФ можно представить любое логическое выражение (и помним, что мы не углубляемся в СДНФ, КНФ, СКНФ, критерий Поста и т.д.).

Оптимизация, оптимизация

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

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

Для изучения механизма работы карты Карно можно, опять же, отправить к учебнику Харрис&Харрис глава 2.7. Но очень уж изящное решение! Кроме того, карты Карно иногда спрашивают на собеседованиях. Карты Карно предназначены для визуального безкомпьютерного упрощения выражений с количеством переменных до 6.

Давайте посмотрим на типичную карту Карно, например на 4 переменных:

Самое важное (и в чем состоит суть изобретения Мориса Карно) – это то, что соседние клеточки по вертикали и горизонтали отличаются значением ровно одной переменной. А если в соседних ячейках стоят «1» то эту переменную можно исключить. Причем «края» карты Карно подразумеваются «склеенными». Так что наша функция ужимается до

Если попытаться изобразить в 3D карту Карно для 4-х переменных, ее можно будет представить как развертку такого «угловатого тора», имеющего 16 граней (нарисовано в OpenSCAD ).

Возвращаясь к PAL

Обогатившись такими знаниями, давайте вернемся к нашим PAL-кам и посмотрим на их внутреннее устройство. И опять же, хорошим подспорьем тут будет учебник Харрис&Харрис «Цифровая схемотехника и архитектура компьютера», а конкретно параграф про PAL (п.5.6 «Матрицы логических элементов»).

При разработке PAL применяется своеобразная графическая запись, первоначально, видимо, предназначенная для ручного кодирования (до появления PALASM).

Давайте возьмем одну ячейку PAL, самого классического PAL16L8:

Итак, сверху вниз идут колонки – входные переменные. Из них: 10 шт. – это самые настоящие входы, то есть «ножки» микросхемы, а 6 шт. – это «возвраты» внутри чипа, что позволяет создавать более сложные многоступенчатые выражения. Понятно, что каждая из этих 16 переменных существует в прямой и инверсной форме, итого мы видим 16*2=32 колонки. Слева мы видим ввод одной переменной в матрицу, в прямом и инверсном виде (вывод 2).

Все эти «вертикальные» переменные одновременно поступают на элементы «И», которые могут использовать некоторые их них (а могут не использовать). Схема примерно такая (тут нарисованы две входные переменные и два элемента «И»):

Мы видим «плавкие перемычки» (fuse, F1..F4 и F5..F8), которые задают, какие переменные подключены к «И». Именно эти fuse и программируются и задают логическую функцию PAL. Картинка получается довольно громоздкая, поэтому применяют такую сокращенную графическую запись (крестики – это подключенные входы):

Вернемся к схеме ячейки PAL:

Как видите, в каждой строке (горизонтали) можно собрать функцию «И» из 16 (32, учитывая инверсию) возможных входов (переменных). То есть такая вот строка – это на самом деле 32-входовый элемент «И» (программируемый). Чуть позже мы посмотрим, как эти соединения выглядят в прошивке.

Далее по схеме мы видим, что в PAL16L8 имеется 7 штук таких «И-шек», объединенных по «ИЛИ». Структура у «ИЛИ» у PAL фиксированная (в отличии от PLA и других архитектур) и не программируется. Кстати, обратите внимание, можно использовать меньшее количество «ИЛИ» (просто не задавая функций у «И» в ячейке), а вот больше – нельзя!

Как несложно заметить, такая конструкция и является физической реализацией ДНФ или SOP (Sum Of Product – то есть сумма произведений). Бинго!

Такие устройства стали называться SPLD (Simple PLD) в противовес CPLD (Complex PLD) и FPGA. Про CPLD кстати, имеется отдельная статья.

Такая простая и элегантная конструкция быстро стала чрезвычайно популярной и стала быстро вытеснять остальные семейства. Вот почему такие гранды, как AMD, Philips, National Semiconductor лицензировали ее.

Популярность PAL-ок пришлась на середину 80-х и начало 90-х. Многие производители чипов, прямо в Datasheet-ах публиковали листинги на PALASM для подключения своих микросхем к другим чипам и к разнообразным микропроцессорным шинам. Некоторые платы начала 90-х представляли собой «россыпи» PAL-ок, на которых были реализованы сложнейшие схемы. Это позволяло быстро выйти на рынок, до начала производства заказных микросхем LSI. (Погуглите, ну скажем, картинки материнской платы EISA i486 Everex Step Mega Cube или Intel iSBC 386. Все узкие микросхемы с бумажками – это PAL ).

Сейчас эту нишу занимают CPLD и FPGA.

Компания MMI выпускала книжки, содержащие массу примеров применения своих микросхем, которые сопровождались забавными рисунками (извините, утащил).

Или даже так, ужас-ужас (Текст: В этой конструкции одна PAL16R8 заменяет 15 TTL микросхем малой и средней степени интеграции ):

Семейство PAL было довольно обширное. Существовали разновидности на разное количество ячеек и входов. Были разновидности с триггерами, что позволяло делать на них синхронные схемы и даже маленькие конечные автоматы (например PAL16R8). Существовали универсальные (Versatile) разновидности, в которых можно выбирать комбинаторную логику или триггера (PAL16V8). Существовали чуть более крупные PAL-ки в 24-выводном корпусе, типа PAL22V10. Микросхемы могли быть упакованы в различные корпуса и могли быть разной «скорости», от -5 до -25 наносекунд. Наконец, существовали низкопотребляющие варианты и варианты в CMOS исполнении (например Texas Instrument TICPAL или Cypress Semiconductor PALC).

PALASM

Невероятный успех микросхемам PAL фирмы MMI принёс еще один компонент, без которого покорение рынка было бы немыслимо. Это — утилита PALASM. С ее помощью создание прошивки для PAL стало делом настолько легким и простым, что любой инженер с нормальной подготовкой, понимал идею практически сразу. В PALASM вводится названия пинов и логические выражения в человеческой алгебраической форме (которые обычно выглядят как ДНФ), после чего PALASM выдает файл прошивки для программатора (JEDEC). Грубо говоря, компания MMI сделала тот шаг, который когда-то в 1950-е прошли обычные компьютеры, при переходе от ручного выписывания двоичных кодов к более понятной записи выражений машинного языка (ассемблера). А сам PALASM первых версий, в свою очередь, был написан на языке FORTRAN IV и распространялся в исходных текстах, что позволяло запускать его на любой тогдашней машине, где был компилятор, вплоть до ранних персоналок под CP/M и DOS. Да, да, когда-то FORTRAN был общим системным языком для переноса программ…

Позже вышел PALASM2, синтаксис немного изменился, оброс разнообразными возможностями, появилось некоторое подобие макросов, оптимизатор, поддержка конечных автоматов и даже симулятор. Компания MMI тоже претерпела изменения, ее активы были поглощены AMD, потом выделены в отдельную компанию Vantis, которую позже купила Lattice Semiconductor. Сам входной язык PALASM послужил прообразом множества подобных и более продвинутых языков, его следы есть в ABEL, CUPL и в VHDL (а вообще-то он сам вырос из FORTRAN-а ).

Наиболее развитый PALASM – это версия PALASM4 v1.5a от AMD 1992 года. Понятно, что такая ретро-программа требует для запуска ретро-DOS. Но к счастью, этот вопрос давно решен. Тут нам поможет прекрасная утилита DOSBOX, позволяющая запускать DOS-программы даже на современном Windows 10 64-бит. Хотя DOSBOX вообще-то, предназначен для запуска ретро-игр, но и не-игровые DOS-утилиты неплохо в нем живут и PALASM — не исключение. Компания AMD сделала широкий жест и отпустила PALASM в Public Domain, так что пользоваться им можно совершенно легально.

Тут можно найти инструкцию, как поставить PALASM на DOSBOX и также скачать саму программу. Конфигурационный файл DOSBOX хранится в профиле пользователя
C:\Users\%USERNAME\AppData\Local\DOSBox\ dosbox-0.74.conf
Лучше дополнить секцию [autoexec]:

. . [autoexec] # Lines in this section will be run at startup. # You can put your MOUNT lines here. @echo off mount c c:\DOSBOX set PALASM=C:\PALASM set PATH=%PATH%;C:\PALASM C:

Из под Linux тоже можно запустить PALASM например с помощью того же DOSBOX или похожего DOSEMU.

Из PAL в GAL

При всём своём удобстве PAL-ы имели и некоторые проблемы. Одна из таких проблем состоит в том, что PAL – это однократно программируемое устройство (OTP) с плавкими титано-вольфрамовыми перемычками (Ti-W fuse). При появлении исправлений и замене прошивки приходилось старую микросхему просто выкидывать. Так что многие производители стали предлагать ”стираемые” PAL-ки. История тут длинная, можно, например, вспомнить УФ-стираемые чипы с «окошечком», или тот факт, что очень хотелось сохранить совместимость с парком программаторов и алгоритмами прошивки оригинальных PAL (серии PALCE и PEEL от International CMOS Technology (ICT) Corporation) и т.д.

Наконец фирма Lattice Semiconductor в 1985 г. выпустила семейство GAL, которое можно считать своеобразной вершиной PAL-строения. Подобно исходным MMI PAL-ам c буковкой V ( Versatile) (например PAL16V8) чипы GAL (соответственно название будет GAL16V8) могут принимать прошивки ВСЕХ (ну почти) моделей PAL, а вдобавок чип GAL — электрически стираемый и многократно прошиваемый. Устройства GAL практически вытеснили все остальные SPLD, за исключением, пожалуй Atmel (нынче Microchip) серии ATF (аналогичный чип у них будет называться ATF16V8).

Для переноса JEDEC файлов (прошивок) старых PAL фирма Lattice Semiconductor выпустила утилиту PALTOGAL (тоже бесплатную и тоже под DOS).

ПРМЕЧАНИЕ: Фирма Lattice Semicronductor рекомендует использовать для разработки ABEL (пакет ispLEVER), а фирма Atmel – CUPL (WinCUPL или ProChip Designer). National Semiconductor предлагала свой Opal JR. Но мы в ретро-целях останемся верны PALASM.

ПРИМЕЧАНИЕ2: (для совсем нердов) У GAL все же есть некоторые мелкие отличия, связанные с тем, что MMI PAL – это ТТЛШ микросхема, а GAL – CMOS.

И конечно же, для прошивки микросхем GAL (и ATF) потребуется специальный программатор. Существуют и PAL-ы, прошиваемые по JTAG, но это редкость (Lattice ispGAL). Хотя программатор для GAL можно сделать самостоятельно (ищется по именам GALBLAST и ATFBLAST), всё же лучше приобрести готовый. Например, TL866 (известный еще как Minipro), которыми забит Aliexpress:

Сами чипы GAL или ATF можно приобрести на том же Aliexpress. Цена за десяток может доходить до 5$ и менее. Не стоит ожидать чудес, чипы будут б/у (помним, что их можно и нужно(!) стереть) и могут иметь следы пайки и маркировку краской или лазером от погибших неведомых устройств, откуда их вытащили трудолюбивые китайцы. Lattice GAL сняты с производства в 2011, но запасов из старой техники хватит еще на пару десятков лет. ATF еще выпускаются.

7-SEG LED

Если помните, в начале статьи мы собирались зажечь светодиод. А точнее — не один, а целых семь! Да- да, речь пойдет о 7-сегментном индикаторе, а точнее – о реализации банального дешифратора HEX-to-7SEG.

Почему-то так сложилось, что готовых микросхем с такой функцией не так уж и много. Есть десятичные BCD дешифраторы (т.е. без шестнадцатеричных символов ABCDEF), например 7446/7447/7448/7449 и 74246/74247/74248/74249). Полных HEX дешифраторов не так много — например Motorola MC14495 Hexadecimal-to-Seven Segment Driver или Fairchild DM9368.

Но цены на PAL (GAL) упали настолько, что сделать дешифратор на SPLD дешевле и быстрее! Вот и давайте для практики его и сделаем, включая шестнадцатеричные цифры ABCDEF (Нет, ЕГГОГ мы декодировать не будем ). Отличное приложение наших олдскульных знаний по матлогике и старым программируемым микросхемам.

Построение такого дешифратора является каноническим примером комбинационной логики и типовой лабораторной работой. В учебнике Харрис&Харрис «Цифровая схемотехника и архитектура компьютера» пункт 2.7.2 «Логическая минимизация на картах Карно» содержит пример 2.10 построения такого дешифратора, но только BCD.

На Википедии есть статья, в которой даже приведена нужная нам таблица перекодировки для полного HEX.

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

Давайте для примера рассмотрим сегмент D (нижний). Как мы видим, он загорается 11 раз из 16 возможных входных комбинаций (вертикаль «d»). Если выписать ДНФ, то формула будет такой:

Но здесь есть проблема! Как мы писали выше, матрица обычных PAL (например в PAL16L8) имеет только 7 «ИЛИ» (сложений), а у нас — 11. Надо или применять более сложный чип или выражение придется оптимизировать.

ПРИМЕЧАНИЕ: В PALASM4 есть встроенный оптимизатор. Вероятно, он смог бы упростить это выражение, только надо эту оптимизацию включить. Но для сохранения ретро-духа пройдем этот этап вручную.

Давайте оптимизируем это выражение по карте Карно. Можно сделать это вручную и получить удовольствие, а можно воспользоваться сайтами, где на JavaScript реализованы эти алгоритмы, например:

  • http://www.32×8.com/index.html
  • https://charlie-coleman.com/experiments/kmap/

Как видите, наше выражение для сегмента D превращается в короткое:

Тут всего 5 штук «ИЛИ» вместо 11 так что выражение влезает в ячейку PAL. Проделаем это для всех сегментов.

Получается такой файл PALASM 7SEG.PDS

;PALASM Design Description ;-------------- Declaration Segment ------------ TITLE 7-SEG LED decoder PATTERN 7SEG.PDS REVISION A AUTHOR ALECV COMPANY HABR DATE 01/01/90 CHIP DECODER PAL16L8 ;-------------- PIN Declarations --------------- ;PINS 1 2 3 4 5 6 7 8 9 10 NC D0 D1 D2 D3 NC NC NC NC GND ;PINS 11 12 13 14 15 16 17 18 19 20 NC NC G F E D C B A VCC ;--------------- Boolean Equation Segment ------ EQUATIONS /A = /D0*/D2 + /D0*D3 + D1*D2 + D1*/D2*/D3 + D0*D2*/D3 + /D1*/D2*D3 /B = /D2*/D3 + /D0*/D2 + /D0*/D1*/D3 + D0*D1*/D3 + D0*/D1*D3 /C = D0*/D1 + D0*/D2 + /D1*/D2 + D2*/D3 + /D2*D3 /D = D2*/D1*D0 + /D3*/D2*/D0 + /D2*D1*D0 + D2*D1*/D0 + D3*/D1 /E = /D0*/D2 + D2*D3 + /D0*D1 + D1*D3 /F = /D0*/D1 + /D2*D3 + D1*D3 + /D0*D2 + /D1*D2*/D3 /G = D1*/D2 + D0*D3 + /D2*D3 + /D0*D1 + /D1*D2*/D3 ;------------- Simulation Segment ------------- SIMULATION TRACE_ON A B C D E F G SETF /D3 /D2 /D1 /D0 ; 0 SETF /D3 /D2 /D1 D0 ; 1 SETF /D3 /D2 D1 /D0 ; 2 SETF /D3 /D2 D1 D0 ; 3 SETF /D3 D2 /D1 /D0 ; 4 SETF /D3 D2 /D1 D0 ; 5 SETF /D3 D2 D1 /D0 ; 6 SETF /D3 D2 D1 D0 ; 7 SETF D3 /D2 /D1 /D0 ; 8 SETF D3 /D2 /D1 D0 ; 9 SETF D3 /D2 D1 /D0 ; A SETF D3 /D2 D1 D0 ; B SETF D3 D2 /D1 /D0 ; C SETF D3 D2 /D1 D0 ; D SETF D3 D2 D1 /D0 ; E SETF D3 D2 D1 D0 ; F TRACE_OFF

Откомпилируем файл .PDS в файл .JED с помощью PALASM:

Очень интересно, как PALASM разложил наши выражения на плавкие перемычки. Для этого можно заглянут в файл Fuse plot (рисунок перемычек).

Fuse plot файл 7SEG.XPT

PALASM4 PAL ASSEMBLER - MARKET RELEASE 1.5a (8-20-92) (C) - COPYRIGHT ADVANCED MICRO DEVICES INC., 1992 TITLE :7-SEG LED decoder AUTHOR :ALECV PATTERN :7SEG.PDS COMPANY:HABR REVISION:A DATE :01/01/90 PAL16L8 DECODER 11 1111 1111 2222 2222 2233 0123 4567 8901 2345 6789 0123 4567 8901 0 ---- ---- ---- ---- ---- ---- ---- ---- 1 -X-- ---- -X-- ---- ---- ---- ---- ---- 2 -X-- ---- ---- X--- ---- ---- ---- ---- 3 ---- X--- X--- ---- ---- ---- ---- ---- 4 ---- X--- -X-- -X-- ---- ---- ---- ---- 5 X--- ---- X--- -X-- ---- ---- ---- ---- 6 ---- -X-- -X-- X--- ---- ---- ---- ---- 7 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 8 ---- ---- ---- ---- ---- ---- ---- ---- 9 ---- ---- -X-- -X-- ---- ---- ---- ---- 10 -X-- ---- -X-- ---- ---- ---- ---- ---- 11 -X-- -X-- ---- -X-- ---- ---- ---- ---- 12 X--- X--- ---- -X-- ---- ---- ---- ---- 13 X--- -X-- ---- X--- ---- ---- ---- ---- 14 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 15 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 16 ---- ---- ---- ---- ---- ---- ---- ---- 17 X--- -X-- ---- ---- ---- ---- ---- ---- 18 X--- ---- -X-- ---- ---- ---- ---- ---- 19 ---- -X-- -X-- ---- ---- ---- ---- ---- 20 ---- ---- X--- -X-- ---- ---- ---- ---- 21 ---- ---- -X-- X--- ---- ---- ---- ---- 22 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 23 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 24 ---- ---- ---- ---- ---- ---- ---- ---- 25 X--- -X-- X--- ---- ---- ---- ---- ---- 26 -X-- ---- -X-- -X-- ---- ---- ---- ---- 27 X--- X--- -X-- ---- ---- ---- ---- ---- 28 -X-- X--- X--- ---- ---- ---- ---- ---- 29 ---- -X-- ---- X--- ---- ---- ---- ---- 30 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 31 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 32 ---- ---- ---- ---- ---- ---- ---- ---- 33 -X-- ---- -X-- ---- ---- ---- ---- ---- 34 ---- ---- X--- X--- ---- ---- ---- ---- 35 -X-- X--- ---- ---- ---- ---- ---- ---- 36 ---- X--- ---- X--- ---- ---- ---- ---- 37 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 38 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 39 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 40 ---- ---- ---- ---- ---- ---- ---- ---- 41 -X-- -X-- ---- ---- ---- ---- ---- ---- 42 ---- ---- -X-- X--- ---- ---- ---- ---- 43 ---- X--- ---- X--- ---- ---- ---- ---- 44 -X-- ---- X--- ---- ---- ---- ---- ---- 45 ---- -X-- X--- -X-- ---- ---- ---- ---- 46 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 47 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 48 ---- ---- ---- ---- ---- ---- ---- ---- 49 ---- X--- -X-- ---- ---- ---- ---- ---- 50 X--- ---- ---- X--- ---- ---- ---- ---- 51 ---- ---- -X-- X--- ---- ---- ---- ---- 52 -X-- X--- ---- ---- ---- ---- ---- ---- 53 ---- -X-- X--- -X-- ---- ---- ---- ---- 54 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 55 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 56 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 57 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 58 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 59 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 60 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 61 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 62 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 63 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX SUMMARY ------- TOTAL FUSES BLOWN = 1262

Этот файл лучше рассматривать одновременно с документацией на PAL16L8. Ее можно найти, например, на сайте Texas Istruments: pal16r8am.pdf страница 5.

Сегмент D у нас выведен на 16-й вывод микросхемы. Если мы посмотрим схему PAL, то за него отвечают перемычки, начиная с номера 768. Как несложно догадаться 768 / 32 = 24 – это 24-я строка. Сама она отвечает за управление выходом и поэтому пустая. Логические выражения начинаются с перемычки 800, то есть строки 25. Если посмотреть на схему, то в 25-й строке собираются по «И»: прямой вход D0 (вывод микросхемы 2), инверсия D1 (вывод 3) и прямой вход D2 (пин 4). Это в точности соответствует первому минитерму в формуле для сегмента D! Остальные минитермы из выражения также транслируются в перемычки и в конце объединяются по «ИЛИ». Так что PALASM, не мудрствуя лукаво, просто переводит наши ДНФ-выражения в прошивку один в один.

Именно таким способом проектировали прошивки до появления PALASM, в самой старой документации MMI как раз описан этот способ. Надо отметить, что другие семейства, например PLA, не получили вообще или получили утилиты класса PALASM довольно поздно (например ICT PEEL Array PLACE) и не стали такими популярными.

Для программирования GAL полученный файл 7SEG.JED отконвертируем утилитой PALTOGAL:

PALTOGAL –C2 –R 7SEG.JED 7SEG_GAL.JED

При подключении индикатора к FPGA (на VHDL и Verilog) или к микроконтроллеру логические функции раскладывать нет необходимости и просто используют таблицу. Можно погуглить или посмотреть на Youtube, поиск «Семисегментный индикатор».

Практика

Давайте соберем модель декодера семисегментного индикатора (и сдадим курсовик, ха-ха). В качестве генератора импульсов применим обычную микросхемку NE555 (К1006ВИ1). Для наблюдения нам нужен период примерно 1 секунда. Для делителя на 16 в коде 1-2-4-8 можно применить что-нибудь типа К155/К555 ИЕ5 или ИЕ7 (совсем круто было бы сделать счетчик тоже на GAL, но это в следующий раз). В коробочке нашлась К555ИЕ7 (SN74LS193), значит так тому и быть. На вывод «R» подадим ноль, на выводы «V» и «-1» — единицу, на вывод «+1» — тактовые импульсы с NE555. Счетчик начал считать. Возьмем семисегментный индикатор с общим анодом и нашу GAL. Перед этим сотрем её и прошьем JEDEC файлом. Индикатор попался LTS-4801WC, OK. Выводы счетчика Q0,Q1,Q2,Q3 соединим со входами D0,D1,D2,D3 GAL, а выходы GAL – с катодами индикатора через 7 резисторов на 330 Ом.

Получается как-то так:

Заключение

Итак, мы окунулись в историю программируемых логических микросхем (PLD). Мы увидели, что за конструкцией PAL скрывается Древняя Могучая Теория. Выяснилось, что даже сейчас, вполне еще можно применять эти устройства в небольших самоделках. Мы рассмотрели вполне боевой «workflow», как это сделать. И да, PAL и GAL совместимы с олдовой теплой 5V TTL электроникой.

Конечно, в такой короткой статье невозможно отразить все аспекты. Вот кратко, про что мы не рассказали:

Не рассмотрели работу симулятора. В PALASM (2 и 4) встроен довольно мощный симулятор, практически язык программирования, с циклами, условными операторами и т.д.

Не рассмотрели построение на PALASM конечных автоматов. Как-нибудь в другой раз.

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

Не ответили на вопрос: можно ли вводить в PALASM выражения не в ДНФ? Конечно можно. Если выражение синтаксически корректно, PALASM скорее всего его поймет. Но внутри все равно преобразует в ДНФ для воплощения в перемычках.

Не рассмотрели вопрос программирования (прошивки) исходных MMI PAL. Проблема здесь в том, что это однократно программируемые микросхемы и сейчас довольно сложно найти чистые PAL. И их не стереть. А программировались они специальным программатором (например, российский «Стерх» это умеет). Изначально у MMI был даже метод прошивать PAL как ПЗУ 512×4 на старых программаторах с помощью специальной «personality card» — у первых PAL было ровно 2048 перемычек, но ныне этот способ утрачен.

И еще много чего.

  • FPGA
  • История IT
  • Старое железо
  • DIY или Сделай сам

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *