Размещено на http://www.allbest.ru/

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

“ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ”

УДК 681.518:681.326.7

ЕВОЛЮЦІЙНІ МЕТОДИ ПОБУДОВИ ПЕРЕВІРЯЮЧИХ ТЕСТІВ ЦИФРОВИХ СИСТЕМ

Спеціальність 05.13.13 - Обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня кандидата технічних наук

ЕЛЬ-ХАТІБ АДНАН ІБРАГІМ ІССА

Донецьк - 2007

Дисертацією є рукопис

Робота виконана в Державному вищому навчальному закладі “Донецький національний технічний університет” Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор,

Скобцов Юрій Олександрович

ДВНЗ “Донецький національний технічний університет”, завідувач кафедрой автоматизованих систем управління.

Офіційні опоненти: доктор технічних наук, професор,

Кривуля Геннадій Федорович

Харківський національний університет радіоелектроніки, завідувач кафедрою автоматизації проектування обчислювальної техніки, м. Харків;

кандидат технічних наук, доцент, Ладиженський Юрій Валентинович

ДВНЗ “Донецький національний технічний університет”, доцент кафедри прикладної математики і інформатики, м. Донецьк .

Захист відбудеться “ 18 ” жовтня 2007р. о 14:00 на засіданні спеціалізованої вченої ради К11.052.03 Донецького національного технічного університету за адресою: 83000, м. Донецьк, вул. Артема, 58. ауд. 8.704.

З дисертацією можна ознайомитися в бібліотеці ДВНЗ “Донецький національний технічний університет” за адресою:

83000, м. Донецьк, вул. Артема, 58, уч. корпус 2

Автореферат розісланий “ 10 ” вересня 2007 р.

Вчений секретар

спеціалізованої вченої ради К11.052.03

кандидат технічних наук, доцент Г.В. Мокрий

Размещено на http://www.allbest.ru/

Загальна характеристика роботи

кросинговер тест генетичний оператор

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

Важливими компонентами таких систем є підсистеми логічного моделювання та генерації тестів. У теперішній час існує ряд ефективних методів діагностики цифрових схем. Великий внесок у розвиток тестування цифрових схем внесли закордонні дослідники Roth J.P., Zorian Y, Agrawal V.D, Abramovici M., Fujivara H. і вітчизняні вчені Пархоменко П.П., Убар Р.Р., Тоценко В.Г., Романкевич А.М., Дербунович Л.В., Кривуля Г.Ф., Скобцов Ю.О., Хаханов В.І. та інші. Однак дослідження в даному напрямку не припиняються, оскільки методи, що застосовуються, не завжди дозволяють будувати тести необхідної повноти через незадовільні показники швидкодії внаслідок високої розмірності завдання. Найбільш перспективними є алгоритми побудови тестів з використанням методів теорії штучного інтелекту, у першу чергу, генетичних алгоритмів.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана протягом 2004 -2007 р.р. відповідно до наукового напрямку кафедри автоматизованих систем управління Донецького національного технічного університету.

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

Для досягнення поставленої мети в роботі сформульовані та вирішуються наступні задачі:

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

2. Розробка еволюційного методу побудови ініціалізуючих вхідних послідовностей для схем з пам'яттю.

3. Розробка розподілених генетичних алгоритмів генерації перевіряючих тестів на основі структуризації та розпаралелювання процесу побудови тестів.

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

5. Розробка програмного забезпечення генерації перевіряючих тестових послідовностей на основі послідовних і розподілених генетичних алгоритмів.

6. Апробація розроблених методів і програмного забезпечення на схемах міжнародних каталогів, оцінка їх ефективності, швидкодії і якості побудованих тестів.

Об'єкт дослідження - цифрові логічні системи, задані зв'язком логічних елементів, входів і виходів спеціалізованою мовою.

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

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

Наукова новизна одержаних результатів полягає в наступному:

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

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

3. Розроблено методи розподіленого моделювання несправностей і еволюційної генерації тестів на основі моделі “робітник-хазяїн”, які дозволяють домогтися істотного прискорення в рішенні зазначених завдань, одночасно забезпечуючи рівномірне завантаження процесорів клієнтів.

4. Розроблено розподілений генетичний алгоритм генерації тестів на базі “моделі островів”, що дозволяє підвищити якість і повноту перевіряючих тестів,

Практичне значення одержаних результатів:

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

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

Розроблені методи та програмне забезпечення використовуються в Інституті прикладної математики і механіки НАНУ у вигляді модуля системи моделювання і діагностики АСМІД, а також у навчальному процесі при читанні лекційного курсу “Технічна діагностика цифрових систем” і курсовому та дипломному проектуванні на кафедрі “Автоматизовані системи управління” ДВНЗ “Донецький національний технічний університет”.

Особистий внесок здобувача. Всі основні положення та результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно. У роботах, які виконані в співавторстві авторові належать: [1] - модель “робітник-хазяїн” і “модель островів”; [2] - загальний підхід і шляхи використання паралельних ГА в побудові тестів; [3] - розробка моделі “робітник-хазяїн”; [4] - опис реалізації та експериментів по “моделі островів”; [5] - загальний підхід до застосування розподілених ГА в побудові тестів; [6] - метод розподіленого моделювання несправностей; [7] - розподілений генетичний алгоритм побудови тестів; [8, 9] - реалізація розподіленого ГА згідно “моделі островів”.

Апробація результатів роботи. Основні наукові результати роботи доповідалися та обговорювалися на:

- IX міжнародній конференції “Modern problems of Radio Engineering, Telecommunications and Computer Science” (Lviv-Slavsko:2006, February);

- I міжнародній науково-технічной конференції “Гарантоспособные (надежные и безопасные) системы, сервисы и технологии” (Україна, Полтава, 25 - 28 квітня 2006р.);

- 7-й міжнародній науково-практичній конференції “Сучасні інформаційні та електронні технології” (Одеса, травень 2006р.);

- IV міжнародній школі-семінарі “IEEE East-West Design&Test Workshop(EWDT'06, Sochi- September 2006);

- II Всеукраїнській конференції ”Сучасні тенденціїї розвитку інформаційних технологій у науці, освіті та економіці” (Луганськ, - грудень 2006).

Публікації. По темі дисертаційної роботи опубліковано 9 друкованих праць, з них 4 статті у наукових фахових виданнях України: 5 тез доповідей.

Структура та обсяг роботи: Дисертація складається із вступу, 4 розділів, висновків, списку використаної літератури з 103 найменувань. Загальний обсяг роботи 148 стор., ілюстрацій - 51, таблиць -11, 1 додаток.

Основний зміст

У першому розділі “Аналіз моделей цифрових схем и методів побудови тестів” введені поняття, що визначають об'єкт дослідження: математичні моделі цифрових пристроїв і несправностей, визначення тесту. Розглянуто функціональні та структурні моделі цифрових систем, які використовуються в процедурах проектування при моделюванні в даній області, на даному рівні подання ЦС для перевірки відповідності заданим специфікаціям. Представлено сучасну класифікацію типових несправностей, які є моделями фізичних дефектів: одиночні та кратні константні несправності (stack-at faults s-a-0, s-a-1), місткові несправності (bridging faults), несправності “стійке замикання транзистора” ("stuck-on"-SON , "stuck-short" faults,), несправності типу “затримка”, несправності, що перемежовуються, нестійкі несправності, дефектно-орієнтовані несправності (defect oriented faults), функціональні несправності, несправності рівня мов регістрових передач (ЯРП), несправності, що не тестуються (untestable faults).

При розробці алгоритмів генерації тестів і моделювання використовується, в основному, структурна модель цифрового пристрою у вигляді правильної логічної мережі. Виконано аналіз існуючих методів побудови перевіряючих тестів для цифрових систем (ЦС) і використовуваних багатозначних алфавітів.

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

У другому розділі “Розробка генетичних алгоритмів побудови тестів” представлено розроблені генетичні алгоритми побудови перевірюючих тестів для комбінаційних і послідовних цифрових схем.

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

, (1)

де f_i(X) - булева функція, реалізована справною, а ц_i(X) - несправною комбінаційною схемою на i-ому виході.

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

Нехай справна послідовна схема реалізує кінцевий автомат A=(Y,X,Z,,), де Y, X, Z - кінцеві безлічі станів, вхідних і вихідних сигналів відповідно; :YXY - функція переходів, що визначає наступний стан автомата; :YXZ - функція виходу, що визначає вихідний сигнал. Нехай несправність f перетворить автомат A в A^f =(Y,X,Z,^f,^f), де функції ^f,^f стану Y^f і Z^f визначаються в такий же спосіб.

Визначення 2.1. Одиночна константна несправність f називається виявленою у послідовнісний схемі вхідною послідовністью X(1), X(2),..., X(p) щодо стратегії одиночного спостереження виходів, якщо

, (2)

де r - початковий стан справної схеми й q - початковий стан несправної схеми. Це визначення говорить, що при даній стратегії несправність вважається виявленою, якщо найдеться (принаймні один) момент часу (такт) t такий, що для будь-якої пари станів (r,q) справної й несправної схем деякий i-й вихід z_i має різні значення в справній і несправній схемі. Ключовим моментом є те, що будь-яка пара станів справної й несправної схеми повинна видати різні вихідні реакції в той самий такт часу.

Для послідовнісних схем іноді використовується інша стратегія кратного спостереження, при якій різні пари станів справної й несправної схем можуть різнитися в різні такти (моменти) часу.

Визначення 2.2. Одиночна константна несправність f називається виявленою у послідовнісний схемі вхідною послідовністю X(1), X(2),…,X(p) щодо стратегії кратного спостереження виходів, якщо

. (3)

Таким чином, при побудові тесту для схем з пам'яттю необхідно знайти вхідну послідовність X(1), X(2),..., X(p), для якої виконується (2) або (3), залежно від застосовуваної стратегії спостереження виходів. Природно, друга стратегія вимагає більших обчислювальних ресурсів, тому ми будемо, в основному, використовувати першу стратегію одиночного спостереження. Але отримані результати у випадку використання генетичних алгоритмів побудови тестів досить легко переносяться і на другу стратегію, на відміну від структурних методів, де це проблематично.

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

Формально генетичний алгоритм можна описати таким чином:

ГА=(P, N, l, r, k, m, f, p_k, p_m),

де P = (a₁, ..., a) - вихідна популяція;

a_i - рішення задачі, що представляється особиною у вигляді хромосоми;

N - розмір популяції (ціле число);

l - довжина хромосоми популяції (ціле число);

r - оператор репродукції;

k - оператор кросінговера;

m - оператор мутації;

f - фітнес-функція;

p_k - імовірність кросінговера;

p_m - імовірність мутації.

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

При побудові тестів як особина використовується: 1) окремий двійковий вхідний набір - для комбінаційних схем і на першому етапі схем з пам'яттю; 2) двійкова тестова послідовність (таблиця) - для послідовних схем.

Для двійкових наборів при генерації тестів комбінаційних схем застосовуються класичний однокрапковий і двохкрапковий кросінговер і класичні оператори однобітової мутації та інверсії. Для тестових послідовностей модифіковано та розроблено наступні проблемно-орієнтовані оператори кросінговера:

1. Класичний однокрапковий кросінговер.

2. Горизонтальний кросінговер, де батьківські послідовності обмінюються підпослідовностями після рядка k.

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

4. Вільний вертикальний кросінговер, де кожна пара рядків обмінюється підстроками після крапки схрещування.

5. Однорідний кросінговер, де кожний ген нащадка створюється шляхом копіювання відповідного гена з першого або другого батька.

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

Отже, схрещування реалізується у вигляді наведених незалежних операцій, вибір у процесі роботи, між якими, відбувається з імовірністю P₁, P₂,…,P₆, де значення P_i підбираються експериментально і P₁+ P₂+ P₃+ P₄+ +P5+P6=1.

Далі, як звичайно, до отриманих нащадків застосовуються оператори мутації. Тут також відбувається вибір однієї з можливих операцій:

1. Видалення одного вхідного вектора з випадково обраної позиції;

2. Додавання одного вхідного вектора у випадкову позицію;

3. Випадкова заміна бітів у тестовій послідовності.

Вибір між трьома операторами мутації також виробляється випадково з імовірностями P_мут1 і P_мут2 з розподілом 0<P_мут1<P_мут2<1.

Фітнес-функція F(X) використовується для оцінки якості кожного потенційного рішення. Самою природною та точною є фітнес-функція, яка враховує число несправностей, що виявляються. Очевидно, що в цьому випадку необхідно використовувати логічне моделювання несправних ЦС, що вимагає більших обчислювальних ресурсів.

При завданні фітнес-функції для тестових послідовностей послідовних схем частіше застосовують інший підхід, що використовує дані логічного моделювання справної схеми, де насамперед оцінюються зміни сигналів на логічних елементах N_d і тригерах N_t. Після моделювання чергового тестового вектора відбувається обчислення фітнес-функції поточного вектора по формулі:

, (4)

де v - поточний вхідний набір. Як ваги використовуються міри спостерігаємої схеми, що обчислюються на етапі попередньої обробки схеми.

За даними логічного моделювання справної схеми обчислюється значення оцінної функції всієї послідовності:

, (5)

де s - послідовність яка аналізується; - вектор з розглянутої послідовності, i - позиція вектора в послідовності, f - задана несправність,

LH - попередньо задана константа в діапазоні , завдяки якій перевага віддається найбільш коротким послідовностям.

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

генерація_тестів (схема)

{

режим=0;

метод=0;

while(не досягнута задана повнота)

{

ціль=активізувати_несправність_ціль(); // Фаза 1

if( ціль == немає_несправності)

if( режим == 0 ) // якщо псевдовипадковий метод не активізував

{ // несправність, то включаємо режим активізації

режим=1; // за допомогою генетичного алгоритму

continue;

}

else // генетичний алгоритм не активізував несправність,

{ // то пробуємо знову, але не більше встановленого числа разів,

лічильник++;

if(лічильник>МАХ_лічильник) break; //інакше - кінець алгоритму

}

метод=1;

// Фаза 2

послідовність=ГА_генерація_тестової_ послідовності(ціль);

if( послідовність != НЕМАЄ_ПОСЛІДОВНОСТІ )

моделювання_несправностей( послідовність ); // Фаза 3

} // кінець while - досягнута задана повнота

} // кінець алгоритму

Пошук_ що_перевіряє_послідовності( несправність-ціль)

{

for( i=0 ; i<MAX_ПОКОЛІНЬ ; i++)

{

for( кожної особини s у популяції P )

обчислити_оцінку(s, f );

newP=Ж ;

for( k=0 ; k<ЧИСЛО_НОВИХ_ОСОБИН ; k++ )

3 {

вибрати_дві_послідовності_в_P();

застосувати_операцію_схрещування(); //генеруються дві особини

застосувати_операцію_мутації_до_s_c_імовірністю_P_m();

newP=newPИ s;

}

P=(кращі MAX_ОСОБИН з newP і P )

for( кожної особини s у популяції P )

if( s виявляє f )

return s;

}

return( НЕМАЄ_ПОСЛІДОВНОСТІ )

}

Якщо в процесі виконання другої фази генетичний алгоритм побудував тестову послідовність, то відбувається перехід до фази 3. Тут виробляється моделювання всіх невиявлених (на поточному етапі) несправностей на даній тестовій послідовності. За даними моделювання (знову) перевірені несправності викреслюються зі списку несправностей і далі не розглядаються.

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

засновано на моделюванні роботи справної схеми, де

n₁ - відношення числа ініційованих тригерів до їхнього загального числа;

n₂ - активність схеми або число подій моделювання;

n₃ - довжина послідовності;

c₁,c₂, c₃ - коефіцієнти, що нормують.

У третьому розділі ”Розподілені методи побудови перевіряючих тестів”досліджені розподілені генетичні алгоритми побудови перевіряючих тестів. Розроблено та досліджено два основних розподілених генетичних алгоритми побудови тестів: 1) глобальний алгоритм на основі моделі “робітник-хазяїн”; 2) алгоритм на основі “моделі островів”.

Модель “робітник-хазяїн” вимагає найменших змін в існуючій версії програмного забезпечення, що реалізує послідовний ГА генерації тестів і дає гарні результати. При цьому кожний процесор має свою копію популяції. Витрати по обчисленню значень фітнес-функцій (з використанням логічного моделювання) рівномірно розподіляється по всіх процесорах. Для всіх процесорів використовується той самий список несправностей. Тому для n особин і P процесорів ми кожному процесору відносимо n/P особин. Значення фітнес-функції обчислюються відповідними (робітниками) процесорами й посилають в один процесор (хазяїн), що збирає всю інформацію та передає її всім процесорам. Кожний процесор має інформацію про значення фітнес-функції для всіх особин і може на цій основі генерувати наступне покоління.

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

Наприкінці кожного із трьох етапів поміщуються крапки синхронізації. Коли процесор-хазяїн досягає цих крапок, він переходить у режим очікування, поки всі робітники процесори не закінчать свої завдання, що гарантує глобальну коректність алгоритму. При цьому робота між процесором-хазяїном і робітниками розподіляється в такий спосіб.

Процесор-Хазяїн:

- виконує усі вхід-вихідні операції з користувачем і файловою системою: він читає опис схеми та список несправностей і записує побудовану вхідну тестову послідовність;

- спочатку запускає “робочі” процеси на доступних ресурсах;

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

- організує керування процесом генерації тестів: по мірі моделювання несправностей на послідовностях вхідних наборів посилає відповідні повідомлення активації робочих процесорів; по закінченні завдання робочим процесором процесор-хазяїн приймає отримані результати та відповідно змінює глобальні структури даних (загальний список несправностей, значення фітнес-функції для особин і т.п.).

Робочий процесор зберігає локальну копію внутрішнього подання схеми та списку несправностей. Кожний “робітник” приймає вхідну послідовність від “хазяїна” і визначає, які несправності перевіряються цією послідовністю, шляхом логічного моделювання обчислює значення

фітнес-функції для особин, отриманий результат посилає хазяїнові та очікує наступного завдання. Остаточні результати (тестові вхідні послідовності та повнота виявлення несправностей) близькі до тих, що отримано на однопроцесорній комп'ютерній системі з використанням аналогічного алгоритму. Якість рішення (повнота тесту) при цьому не губиться та у більшості випадків поліпшується, а час генерації тестів істотно скорочується. Діаграма потоків даних у даному алгоритмі наведена на рис.1.

У другій “моделі островів” розподіленого ГА при побудові тесту розвиваються декілька підпопуляцій. Тут на кожному процесорі реалізується своя підпопуляція, що спочатку випадково ініціалізується, і далі розвивається незалежно від інших підпопуляцій. Через якийсь час (задане число ітерацій) популяції за певною схемою обмінюються між собою особинами. При цьому кожний процесор відбирає у своєї підпопуляції кращі особини та посилає їх своїм сусідам-процесорам (поняття сусідства також є параметром методу). У сусідньому процесорі ці особини приймаються та впроваджуються у свої популяції, після чого знову відновляється незалежна еволюція на кожному “острові”-процесорі.

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

На відміну від попереднього випадку (моделі “робітник-хазяїн”), де функціонував один ГА на центральному процесорі, а інші процесори використовувалися фактично тільки для обчислення значень фітнес-функцій, тут на кожному процесорі реалізується свій “повнокровний” генетичний алгоритм. Тобто, кожний процесор виконує повний цикл операцій, необхідних для еволюції ГА: проводиться логічне моделювання справних і несправних схем і будується безліч перевірюючих тестових послідовностей. Кожний процесор працює із цілою схемою (а не з її деяким фрагментом) і повним списком несправностей. При цьому можна чекати прискорення часу генерації тесту, принаймні, по двох причинах. Кожний процесор працює на підпопуляції з меншим числом особин, що вимагає менше часу. Завдяки міграції кращих тестів від сусідніх процесорів кожний процесор може виявити несправності швидше, ніж у випадку незалежної обробки в підпопуляціях. Потужність (число особин) підпопуляції (кількість аналізованих одночасно тестових послідовностей) є одним з найважливіших параметрів цієї моделі.

У четвертому розділі “Програмна реалізація, апробація і тестування” представлені експериментальні дані апробації та тестування розробленого програмного забезпечення на основі запропонованих методів і алгоритмів. Програмні модулі, що реалізують розроблені методи, інтегровані в нову версію автоматизованої системи моделювання і діагностування цифрових схем АСМІД, що призначена для використання при контролі та діагностуванні ЦС на етапах їх проектування, виготовлення й експлуатації.

Розроблені методи реалізовані у вигляді комплексу програмних модулів, написаних у середовищі програмування Borland C++ Builder 6.0 (Enterprise Suite, build 10.166). Запропонований алгоритм розподіленого моделювання реалізований програмно за технологією сокетів, що блокують, у середовищі програмування C++ Builder 6. Робота програми апробовувалася на схемах з міжнародного каталогу ISCAS89, на яких за міжнародними стандартами прийнято випробовувати нові методи генерації тестів.

Для проведення експериментів використовувався обчислювальний кластер, побудований на базі локальної мережі 100 Мбіт однієї з навчальних аудиторій. Елементи кластера, включаючи сервер, мають наступні характеристики: процесор Intel Celeron 2000Мгц, обсяг ОЗП - 256 Мбайт, операційна система - Windows XP.

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

- початкова довжина послідовності L;

- імовірність застосування оператора мутації P_m;

- імовірності застосування операторів схрещування P_c;

- ваги компонентів оцінної функції c₁, c₂, c₃.

Значення підбиралися таким чином, щоб алгоритм показував прийнятні результати для всіх контрольних схем. Наприклад, для проведення експериментів по побудові ініціалізуючих послідовностей обрана частково ініціалізована схема s13207, для якої на рис.2-5 наведені результати машинних експериментів.

Це дозволило вибрати наступні значення констант алгоритму: P_c=0.96, P_m=0.01; c₁=1, а константа c₂ дорівнює відношенню числа тригерів до числа вентилів схеми, c₃=0.99, L=1.

При тестуванні розподілених генетичних алгоритмів генерації тестів проводився вимір наступних тимчасових характеристик: загальний час процесу моделювання, число подій при моделюванні справної схеми та схем з несправностями, загальне число подій.

У табл.1 наведені числові дані при проведенні машинних експериментів зі схемою середньої розмірності S9234.ben. У таблиці в дужках при багатопроцесорної реалізації зазначене збільшення швидкодії (для часу моделювання) і вимірюваного параметра при порівнянні з однопроцесорною реалізацією алгоритму.

Таблиця 1

Характеристика	Одно-процесорна реалізація	Багатопроцесорна реалізація (число процесорів)
		1	2	3	4	6	8
довжина тесту	1000	1000
загальний час моделювання, сек.	330	336 (0,98)	194 (1,7)	138 (2,39)	107 (3,08)	86 (3,83)	79 (4,17)
загальне число подій, млн.	441,51	440,05 (1,00)	441,81 (1,00)	443,21 (1,00)	443,78 (1.01)	447,79 (1,01)	449,93 (1,02)
число подій моделювання справної схеми, млн.	0,48	0,48 (1,00)	0,95 (1,98)	1,42 (2,96)	1,90 (3,96)	2,85 (5,93)	3,80 (7,92)
число подій моделювання схем з несправностями, млн.	441,03	439,58 (1,00)	440,86 (1,00)	441,79 (1,00)	441,88 (1,00)	444,94 (1,01)	446,13 (1,01)

На рис.6 наведений графік росту швидкодії при зміні числа процесорів-клієнтів від 1 до 8 за даними моделювання схеми S9234.ben. Для порівняння на діаграмі присутній графік лінійного збільшення швидкодії з коефіцієнтом рівним 1.

На рис.7 представлені дані моделювання з несправностями також для великої схеми s35938 каталогу ISCAS 89, які також показують залежність швидкості моделювання від числа процесорів-клієнтів.

Наведена крива підтверджує наведені висновки. Нарешті, на наступному рис.8 представлені дані моделювання для однієї із самих більших схем каталогу ISCAS89. Ці дані показують, що спостерігається збільшення відносної швидкості моделювання несправностей з ростом розміру схеми. Це можна пояснити тим, що для більших схем “накладні витрати” по організації розподіленого моделювання стають менше в порівнянні з витратами безпосередньо на моделювання несправностей.

ВИСНОВКИ

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

У процесі досліджень вирішені наступні основні завдання:

1. Модифіковані проблемно-орієнтовані генетичні оператори кросінговера та мутації для тестових послідовностей. Проведено експериментальні дослідження модифікованих проблемно-орієнтованих операторів. Показано, що використання розроблених операторів кросінговера та мутації приводить до підвищення повноти на 5% і скороченню обчислювальних витрат на 10-20%.

2. Розроблений і досліджений розподілений генетичний алгоритм побудови тестів на основі моделі “робітник-хазяїн”, експериментально показаний майже лінійне збільшення швидкодії для невеликого числа “процесорів-робітників” і логічних схем великої розмірності. При цьому загальний час рішення скоротився на величину від 80% до 50%, залежно від розмірності оброблюваних схем.

3. Розроблено та досліджено розподілений генетичний алгоритм побудови тестів на основі моделі островів, модифіковано генетичні оператори та визначено раціональні параметри ГА. Показано, що “модель островів” на відміну від моделі “робітник-хазяїн” дає відносно невелике збільшення швидкодії, але дозволяє істотно підвищити якість одержуваних рішень на 7%.

4. Проведено апробацію, тестування та перевірку ефективності розроблених програмних модулів на логічних схемах з міжнародних каталогів ISCAS-85 і ISCAS89, які підтвердили досягнуті високі експлуатаційні характеристики.

СПИСОК ОПУБЛІКОВАНИХ РОБІТ З ТЕМИ ДИСЕРТАЦІЇ

1. Ю.А.Скобцов, А.И.Эль-Хатиб. Параллельные генетические алгоритмы//Наукові праці Донецького национального технічного университету серія: “Обчислювальна техніка та автоматизація”, Випуск 90.-Донецьк : ДонНТУ. - 2005.-С.137-144

2. Д.Е.Иванов, Ю.А.Скобцов, А.И.Эль-Хатиб. Распределенные алгоритмы моделирования и генерации тестов // Радіоелектронні і комп'ютерні системи.-ХАІ:2006.-№6.-С.97-102.

3. Скобцов Ю.А., Єль-Хатиб А.И, Іванов Д.Е. Распределенное параллельное моделирование цифровых схем с неисправностями//Наукові праці Донецького національного технічного університету.Серія:”Обчислювальна техніка та автоматизація”, Донецьк:2006.- Випуск 107.-С.128-134.

4. Ю.А.Скобцов, Д.Е.Иванов, А.И..Эль-Хатиб. Распределенные генетические алгоритмы генерации проверяющих тестов цифровых систем//Радіоелектронні і комп'ютерні системи.-ХАІ:2007.-№7.-С.176-181.

5. Skobtsov Y.A., El-Khatib, Ivanov D.E. Parallel Genetic Algorithm of Test Generation for Digital Circuits // Proceedings of the IX International Conference “Modern problems of Radio Engineering, Telecommunications and Computer Science”.-Lviv-Slavsko:2006.- P.129-131.

6. Ю.А.Скобцов, А.И.Эль-Хатиб. Параллельные генетические алгоритмы построения тестов цифровых схем//Труды 7-й международной научно-практической конференции “Современные информационные и электронные технологии”.-Одесса: 2006.-С.204.

7. Skobtsov Y.A., El-Khatib, Ivanov D.E. Distributed Fault Simulation and Genetic Test Generation of Digital Circuits//Proceedings of IV IEEE East-West Design&Test Workshop(EWDT'06)/-2006: Sochi.- P.89-94.

8. Skobtsov Y.A., El-Khatib, Ivanov D.E. Distributed Genetic Algorithm of Test Generation For Digital Circuits// Proceedings of the 10^th Biennial Baltic Electronics Conference.-Tallinn Technical University,2006.-p.123-128.

9. Скобцов Ю.А., Д.Е.Иванов, А.И.Эль-Хатиб.Распределенный генетический алгоритм генерации проверяющих тестов на основе модели островов//Тезисы II Всеукраинской конференции ”Сучасні тенденціїї розвитку інформаційних технологій в науці, освіті та економіці”.-2006:Луганск.-.C.211-213.

Размещено на Allbest.ru

...