У статті наведено аналітичний огляд реконфігурованих гібридних еволюційних апаратних систем. Розглянуто класифікацію паралельних генетичних алгоритмів, що є основою еволюційних апаратних систем. Наведено структурну схему реконфігурованою еволюційної системи для реалізації на ПЛІС.

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Бегляров Вадим Валерійович, Береза ​​Андрій Миколайович, Ляшов Максим Васильович


ANALYTICAL REVIEW OF HYBRID EVOLUTION RECONFIGURABLE HARDWARE SYSTEMS

In article is considered the review of reconfigurable hybrid evolutionary hardware and classification of the parallel genetic algorithm being a basis of evolutionary hardware. Adduce the block diagram reconfigurable hybrid evolutionary system for realization on FPGA.


Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2009


    Журнал: Известия Південного федерального університету. Технічні науки


    Наукова стаття на тему 'Аналітичний огляд реконфігурованих гібридних еволюційних апаратних систем'

    Текст наукової роботи на тему «Аналітичний огляд реконфігурованих гібридних еволюційних апаратних систем»

    ?БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Курейчик В.В., Сороколетов П.В. Концептуальна модель представлення рішень в генетичних алгоритмах // Известия ПФУ. Технічні науки. - 2008. - № 9 (86). - С. 7-12.

    2. Бакало М.А., Курейчик В.В. Модифікований алгоритм розміщення методом парних перестановок // Известия ТРТУ. Тематичний випуск «Інтелектуальні САПР». 2007. - С. 77-84.

    3. Курейчик В.В., Курейчик В.М., Генетичний алгоритм розміщення графа // Известия РАН. Теорія і системи управління. - 2000. - № 5. - С. 67-74

    4. Курейчик В.М., Лебедєв Б.К., Лебедєв О.Б. Рішення завдання розміщення на основі еволюційного моделювання // Известия РАН. Теорія і системи управління. - 2007.

    - № 4. - С. 78-90.

    5. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Біоінспірірованние методи в оптимізації. - М .: Физматлит 2009.

    Курейчик Володимир Вікторович

    Технологічний інститут федерального державного освітнього закладу вищої професійної освіти «Південний федеральний університет» в м Таганрозі.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    347928, м Таганрог, пров. Некрасовський, 44.

    Тел .: 88634383451.

    Кафедра систем автоматизованого проектування; завідувач кафедри, професор.

    Kureichik Vladimir Viktorovich

    Taganrog Institute of Technology - Federal State-Owned Educational Establishment of Higher Vocational Education "Southern Federal University".

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    44, Nekrasovskiy, Taganrog, 347928, Russia.

    Phone: 88634383451.

    The Department of Computer Aided Design; head the Department; professor.

    Бушин Сергій Олексійович

    ТОВ «Астор-Трейд», м Москва

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    105484, г. Москва, ул. 16-я Паркова, 26.

    Тел .: 84954684334.

    Начальник конструкторського відділу.

    Bushin Sergey Alekseevich

    «Astor-Trade» Company.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    16 Parkovaya Street, 26, Moscow, 105484, Russia.

    Phone: 84954684334.

    Head of the design apparatus department.

    УДК 004.386

    В.В. Бегляров, А.Н. Береза, М.В. Ляшов

    АНАЛІТИЧНИЙ ОГЛЯД реконфігурованих ГІБРИДНИХ Еволюційної АПАРАТНИХ СИСТЕМ

    У статті наведено аналітичний огляд реконфігурованих гібридних еволюційних апаратних систем. Розглянуто класифікацію паралельних генетичних алгоритмів, які є основою еволюційних апаратних систем. Наведено структурну схему реконфігурованою еволюційної системи для реалізації на ПЛІС.

    Генетичний алгоритм; бионические системи; гібридні системи; еволюційні апаратні засоби; еволюційна електроніка; Реконфігуровані інтелектуальні системи.

    V.V. Begliyrov, A.N. Bereza, M.V. Liyshov

    ANALYTICAL REVIEW OF HYBRID EVOLUTION RECONFIGURABLE

    HARDWARE SYSTEMS

    In article is considered the review of reconfigurable hybrid evolutionary hardware and classification of the parallel genetic algorithm being a basis of evolutionary hardware. Adduce the block diagram reconfigurable hybrid evolutionary system for realization on FPGA.

    Genetic algorithm; hybrid system; evolutionary hardware; evolutionary electronics; reconfigurable intellectual systems.

    Вступ. Еволюційні апаратні системи (ЕАС) - це новий тип апаратних систем, який включає в себе Реконфігуровані і автономні системи, штучний інтелект, а також еволюційні алгоритми (ЕА). Основна особливість ЕАС - можливість зміни архітектури системи в залежності від зовнішніх умов. В основі ЕАС лежать еволюційні алгоритми - методологія пошуку рішень для отримання відповідної архітектури. В якості апаратної платформи при створенні ЕАС виступають Реконфігуровані пристрої.

    Еволюційні апаратні засоби мають такі особливості:

    | Система еволюціонує, а не розробляється;

    | Може вийти не оптимальне рішення, але придатне для поставленого завдання;

    | Адаптивність до зовнішніх змін.

    ЕАС поділяються на зовнішній і внутрішній типи використовуваного еволюційного моделювання. Зовнішній тип передбачає відділення еволюційного процесу від апаратної частини. Архітектура або принципова схема створюється спочатку на комп'ютері за допомогою еволюційних алгоритмів і потім переноситься на реформуються платформу. Внутрішній тип означає, що розвиток і оцінка знайдених рішень виконуються на апаратному рівні і система може працювати автономно.

    Гібридні еволюційні апаратні системи (ГЕАС) - це апаратні системи, які виходять в результаті об'єднання компонентів м'яких обчислень, таких як нейронні мережі, генетичні алгоритми та елементи нечіткої логіки. В останні роки цій темі приділяється велика увага [1-6]. Недоліки одних компенсуються достоїнствами інших, при цьому ГЕАС дозволяють отримувати кращі результати. Незважаючи на велику кількість розроблених методів і алгоритмів гібридних м'яких обчислень у вигляді програмних продуктів, недостатньо уваги приділялося їх апаратної реалізації. Досягнення сучасної мікроелектроніки дозволяють створювати апаратні модулі, що реалізують алгоритми м'яких обчислень, які можуть бути складовими частинами сучасних інформаційних систем. Одними з таких систем є сучасні системи автоматизованого проектування (САПР) [7,8]. Основна тенденція розвитку САПР - це інтелектуалізація. Інтелектуальні процедури і алгоритми можуть вбудовуватися як в програмні, так і в апаратні компоненти САПР, для розширення їх функцій і збільшення ефективності. Застосування апаратних модулів дозволить значно збільшити продуктивність САПР в цілому і, відповідно, ставити і вирішувати більш масштабні завдання.

    Паралельні генетичні алгоритми. Основою ГЕАС є генетичний алгоритм. Генетичні алгоритми (ГА) - ефективні методи пошуку, засновані на принципах природного відбору і генетики. Вони намагаються знайти оптимальне рішення задачі, керуючи популяцією альтернативних рішень. Популяція оцінюється, і кращі рішення відбираються для формування наступного покоління. Після кількох поколінь, хороші ознаки домінують в популяції, в результаті підвищуючи якість рішень. ГА успішно застосовуються для знаходження квазіоптимальних рішень в різних завданнях, де класичні методи виявляються неефективними. Для типової ГЕАС довжина хромосоми може досягати сотні і навіть тисячі генів, і місце пошуку буде дуже великим (прокляття розмірності). Тому пошук рішення із застосуванням ГА може займати досить великий час. Дослідники робили чимало спроб для прискорення роботи ГА [9-12]. Найперспективнішим є паралельне виконання ГА [13].

    Паралельні ГА класифікуються на три основних типи [14]:

    1. Глобальні однопопуляціонние «майстер-помічник» ГА (master-slave GAs).

    2. Однопопуляціонние дрібнозернисті ГА (fine-grained GAs).

    3. Многопопуляціонние грубозернисті ГА (coarse-grained GAs).

    В ГА «майстер-помічник» існує одна популяція, але оцінка функції фітнесу розподілена серед декількох процесорів. Дрібнозернисті ГА складаються з однієї просторово-структурованої популяції. Селекція і схрещування обмежені маленьким сусідством, але сусіди перекривають допущення деякого взаємодії серед всіх індивідуумів.

    Многопопуляціонние - більш складні ГА, так як вони складаються з декількох подпопуляцій, які періодично обмінюються індивідуумами. Цей обмін індивідуумами називається міграцією і управляється кількома параметрами.

    Апаратна реалізація ГЕАС. Серед відомих рішень апаратної реалізації гібридних еволюційних апаратних систем слід зазначити наступні:

    | Генетичні нечіткі контролери для автономних мобільних роботів, здатних самостійно орієнтуватися на місцевості [3-5];

    | Пристрої еволюційного синтезу цифрових кінцевих автоматів для різних систем управління технічними і технологічними об'єктами [4];

    | Апаратні еволюційні нейронні мережі для інтелектуальних систем обробки інформації [5];

    | Реконфігурованих еволюційний нечіткий контролер для комутації пакетів в мережах передачі даних [3].

    На сьогоднішній день можна виділити три основні напрями апаратної реалізації ГЕАС:

    1. ЕАС будуються на базі каскадного з'єднання універсальних RISC або CISC мікропроцесорів. Такі пристрої відносяться до емуляторам, так як алгоритми, що моделюють еволюцію, виконуються на програмному рівні. Основний недолік таких систем - це відносно невисока швидкодія і, як наслідок, обмежене коло їх застосування.

    2. ЕАС на основі спеціалізованих процесорів. Функціонально закінчені системи, реалізовані за цим напрямком, відносяться до нейрокомп'ютерів, нечітким комп'ютерів і т. П., Так як всі операції виконуються в спеціальному логічному базисі. Основний недолік таких систем - це складність створення спеціалізованих процесорів

    і, як наслідок, їх висока вартість.

    3. ЕАС на базі програмованих логічних інтегральних схем (ПЛІС). Спецобчислювача реалізуються у вигляді плат розширення стандартних обчислювальних систем і називаються апаратними прискорювачами.

    Основні переваги ПЛІС для реалізації гібридних еволюційних апаратних систем є:

    1) високу швидкодію. Сучасні ПЛІС працюють на частотах понад 500 МГ ц, і виконуються з технологічними нормами до 40 нм;

    2) можливість апаратної реалізації паралельних алгоритмів;

    3) можливість перепрограмування в системі (In-system reprogrammable);

    4) можливість реалізації швидкісних інтерфейсів обміну даними;

    5) наявність бібліотек IP-ядер, що описують складні алгоритми.

    Безпосередня реалізація архітектури ГЕАС на ПЛІС має такі переваги:

    | Висока паралельність обробки даних;

    | Можливість реалізації будь-якої топології мережі межсоединений;

    | Реконфігурованих архітектури на апаратному рівні.

    Недоліками цього рішення є:

    | Відсутність готових рішень;

    | Висока схемотехнічна складність реалізації окремого функціонального блоку.

    Апаратні прискорювачі. Один із перспективних напрямів використання ГЕАС - їх застосування в якості апаратних прискорювачів в складі інтелектуальних систем обробки інформації (рис. 1).

    Flash

    інтерфейс

    SelectMap

    плата PCI

    Мал. 1. Плата реконфігурованих апаратного прискорювача

    Плата реконфігурованих апаратного прискорювача (див. Рис. 1) містить два основних компоненти ПЛІС і мікросхему Flash пам'яті. Програмована логічна інтегральна схема розташована близько до контактних площадок інтерфейсу PCI, згідно з вимогами специфікації для довжин сигнальних ліній. Flash пам'ять містить конфігураційні дані ядра шини PCI і контролера реконфігурації.

    плис

    ІІ

    Використання однієї ПЛІС замість декількох звільняє проектувальника від створення специфікації протоколу зв'язку між мікросхемами і розбиття проекту на частини.

    На рис. 2 показано розбиття ПЛІС на дві частини - фіксована і реконфігурованих. Фіксована частина містить ядро ​​контролера шини РСІ і контролер реконфігурації. Конфігураційні дані цієї частини міститься у зовнішній Б ^ І-пам'яті і передаються в ПЛІС на початковому етапі завантаження комп'ютера. Реконфігурованих частина динамічно формується відповідно до виконуваного алгоритму через шину РСІ. Обидві частини пов'язані шиною ВшМасгоз. Контролер реконфігурації використовує порт ІСАР ПЛІС для завантаження конфігураційних даних.

    Н н Фіксована

    Рекеіфігуріруемая частина В і Б М А С Р Ядро РСІ

    Про

    контролер реконфігурації

    Мал. 2. Розбиття ПЛІС

    Інтерфейс РСІ використовується для передачі конфігураційних даних реконфігурованою частини, а також для обміну даними між прискорювачем і програмним забезпеченням.

    Структурна схема ГЕАС для реалізації на ПЛІС показана на рис. 3.

    Адреса 1

    дані 1

    Шина Шина адреси 1 даних 1

    Шина Шина даних 2 адреси 2

    регістри

    Адреса 2

    дані 2

    вихід

    Мал. 3. Структурна схема ГЕАС

    Блок генетичного алгоритму виконує генетичний пошук рішення на функціонально-логічному рівні проектування для реконфігурованих блоку. Ініціалізація генетичного алгоритму відбувається в блоці мікропроцесорного управління. Проміжні хромосоми зберігаються в блоці регістрів.

    Висновки. Постійне збільшення, відповідно до закону Мура, кількості транзисторів на кристалі НВІС ставить перед проектувальниками і творцями систем автоматизованого проектування все більш складні завдання, які повинні вирішуватися в стислі терміни. Застосування методів еволюційного пошуку в системах автоматизованого проектування мікроелектронних засобів дозволить знаходити Квазіоптимальний вирішення завдань, які є труднорешаемой для класичних методів. Використання апаратного прискорення для процедур еволюційного пошуку дозволить значно збільшити продуктивність створюваних ІСАПР. Надалі планується створення апаратного прискорювача для збільшення швидкодії процедур еволюційного моделювання в електронних САПР.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Nedjah N. Evolvable Machines: Theory and Practice. Studies in Fuzziness and Soft Computing, Volume 161 / N. Nedjah. - 2004. - 260 р.

    2. Garrison W. Introduction to Evolvable Hardware: A Practical Guide for Designing Self-Adaptive Systems // IEEE Press Series on Computational Intelligence. - 2006. - 208 р.

    3. Higuch, T. Evolvable Hardware [Текст] / T. Higuchi, Y. Liu, X. Yao. - 2006. - 224 р.

    4. Yao X., Higuchi T. Promises and Challenges of Evolvable Hardware // IEEE Trans on Syst., Man and Cybern., Part C, Applications and Reviews, vo1.29, no.1, pp: 87-97, Feb . 1999.

    5. Gordon Т. On Evolvable Hardware // In Ovaska, S. and Sztandera, L. (Ed.) Soft Computing in Industrial Electronics. Physica-Verlag, Heidelberg, Germany. - 2002. - Р. 279-323.

    6. Iwata M. mplementation of a Gate-Level Evolvable Hardware Chip // 10 (ICES2001). - Р. 38-49, Springer Verlag, 2001..

    7. Норенков І.П. Основи автоматизованого проектування // Изд. 2-е, перераб. і доп.

    - М .: Изд-во МГТУ ім. Н. Е. Баумана, 2002. - 336 с.

    8. казенний Г.Г. Основи проектування інтегральних схем і систем // Лабораторія знань. - М .: БІНОМ, 2005. - 295 с.

    9. Hauser R. Implementation of standard genetic algorithm on MIMD machines // Parallel Problem Solving fron Nature, PPSN III, Р. 504-513, Springer-Verlag (Berlin), 1994.

    10. Grosso P.B. Computer simulations of genetic adaptation.Parallel subcomponent interaction in a multilocus model: Unpublished doctoral dissertation // The University of Michigan, 1985.

    11. Cohoon J.P. Genetic Algorithms and punctuated Equilibria in VLSI // In SCHWEFEL H.-P., MANNER R., Eds., Parallel Problem Solving from Nature, p. 134-144, Springer-Verlag (Berlin), 1991.

    12. Tanese R. Distributed genetic algorithms // In SCHAFFER J. D., Ed., Proceedings of the Third International Conference on Genetic Algorithms, p. 434-439, Morgan Kaufmann (San Mateo, CA), 1989.

    13. Adamidis P. Review of parallel genetic algorithms bibliography // Tech. rep. version 1, Aristotle University of Thessaloniki, Thessaloniki, Greece, 1994.

    14. Lin S.-C, Coarse-Grain Parallel Genetic Algorithms: Categorization and New Approach // In Sixth IEEE Symposium on Parallel and Distributed Processing, IEEE Computer Society Press (Los Alamitos, CA), October 1994.

    Бегляров Вадим Валерійович

    Південно-Російський державний університет економіки і сервісу.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    346500, м Шахти, вул. Шевченко, д. 147.

    Тел .: 89081760312.

    Кафедра інформаційних систем і радіотехніки; аспірант.

    Begliyrov Vadim Valeryevich

    South Russian State University of Economics and Service.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    147, Shevchenko street, Shakhty, 346500, Russia.

    Phone: 89081760312.

    Department of Information Systems & Radio Engineering; postgraduate student.

    Береза ​​Андрій Миколайович

    Південно-Російський державний університет економіки і сервісу. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    346500, м Шахти, вул. Шевченко д. 147.

    Тел .: 89281574449.

    Кафедра інформатики ВІС ЮРГУЕС; завідувач кафедри; доцент. Bereza Andrew Nikolayevich

    South Russian State University of Economics and Service.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    147, Shevchenko street, Shakhty, 346500, Russia.

    Phone: 89281574449.

    Head the Department; associate professor.

    Ляшов Максим Васильович

    Південно-Російський державний університет економіки і сервісу. E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    346500, м Шахти, вул. Шевченко, д. 147.

    Тел .: 89604591974.

    Кафедра інформаційних систем і радіотехніки; аспірант.

    Liyshov Maxim Vasilyevich

    South Russian State University of Economics and Service.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її..

    147, Shevchenko street, Shakhty, 346500, Russia.

    Phone: 89604591974.

    Department of Information Systems & Radio Engineering; postgraduate student.

    УДК 681.3.001.63

    О.Б. Лебедєв ПОКРИТТЯ НА ОСНОВІ МЕТОДУ мурашиної КОЛОНІЇ *

    Пропонуються нові технології, принципи і механізми розв'язання задачі покриття, що використовують математичні методи, в яких закладені принципи природних механізмів прийняття рішень. Для компактного представлення рішення задачі покриття використовується матриця граничних вимог. Це дозволило організувати простір рішень, в рамках якого організовано пошуковий процес, який базується на моделюванні адаптивного поведінки мурашиної колонії. У порівнянні з існуючими алгоритмами досягнуто поліпшення результатів.

    покриття; мурашина колонія; оптимізація.

    O.B. Lebedev COVERING ON THE BASIS OF THE METHOD OF THE ANT COLONY

    New technologies, principles and mechanisms of the decision of a problem the coverings using mathematical methods in which principles of natural mechanisms of decision-making are put in pawn are offered. For compact representation of the decision of a problem of a covering the matrix of boundary requirements is used. It has allowed to organize space of decisions in which

    * Робота виконана за підтримки: РФФД (грант № 09-01-00509), г / б № 2.1.2.1652.


    Ключові слова: ГЕНЕТИЧНИЙ АЛГОРИТМ /біонічної СИСТЕМИ /ГІБРИДНІ СИСТЕМИ /ЕВОЛЮЦІЙНІ Апаратні засоби /ЕВОЛЮЦІЙНА ЕЛЕКТРОНІКА /Реконфігурованих ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ /GENETIC ALGORITHM /HYBRID SYSTEM /EVOLUTIONARY HARDWARE /EVOLUTIONARY ELECTRONICS /RECONFIGURABLE INTELLECTUAL SYSTEMS

    Завантажити оригінал статті:

    Завантажити