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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Мохамад Алі, Міхаль О.Ф.


Criteria of optimization of forming the informational flow in local-parallel automated training system

At realization of systems of distributed multiuser automated training on local-parallel algorithms, an advantage in its capacity is provided. The local parallelity expects the compact presentation and processing of the information. Method of description is designed and statistical model for randomizations of training samples is made. Criteria of quality of randomizations are offered. The numerical estimations are received for concrete configurations of training systems, essential for optimization on criterion of the minimum of the expense of computer time for reception of qualitative random training samples. The further directions of the model studies and expected results are declared.


Область наук:
  • Комп'ютер та інформатика
  • Рік видавництва: 2011
    Журнал: Вісник Херсонського національного технічного університету

    Наукова стаття на тему 'КРИТЕРІЇ ОПТИМАЛЬНОСТІ ФОРМУВАННЯ ІНФОРМАЦІЙНОГО ПОТОКУ В ЛОКАЛЬНО-паралельного автоматизованої навчальної системи'

    Текст наукової роботи на тему «КРИТЕРІЇ ОПТИМАЛЬНОСТІ ФОРМУВАННЯ ІНФОРМАЦІЙНОГО ПОТОКУ В ЛОКАЛЬНО-паралельного автоматизованої навчальної системи»

    ?КРИТЕРІЇ ОПТИМАЛЬНОСТІ ФОРМУВАННЯ ІНФОРМАЦІЙНОГО ПОТОКУ В ЛОКАЛЬНО-паралельного автоматизованої

    Навчальна система

    У комп'ютерних автоматизованих навчальних системах (АОС) реалізується багаторазове чергується повторення дозованих елементів навчального матеріалу, при якому в процесі діалогу здійснюється запам'ятовування. Центральним моментом автоматизації є формування навчального інформаційного потоку (ІП). Запам'ятовування конкретного елемента інформації залишається індивідуальним актом, оскільки визначається індивідуальними особистісними процесами створення асоціацій. У зв'язку з цим, подача інформації в АОС так само повинна бути індивідуальною, для чого доцільно формування ІП із застосуванням генераторів псевдовипадкових чисел (ГВЧ) з подальшим відбором і перегрупуванням елементів відповідно до частоти правильних відповідей. Автоматизація навчання спочатку передбачає розподілене на багато користувачів застосування, тому доцільно економне витрачання централізованих обчислювальних ресурсів. Суттєву перевагу (компактне зберігання інформації і прискорену обробку) забезпечують локально-паралельні (ЛП) алгоритми [1, 2], спочатку розроблені для обробки нечіткої інформації (АНІ). Перспективність їх використання підтримується так само довготривалими стійкими тенденціями розвитку структури засобів обчислювальної техніки [3]. Навчання, як процес, передбачає просування від нульового знання до все більш повного, тому оцінка стану (ступеня) вивченості матеріалу допускає інтерпретацію в рамках схем і процедур обробки НІ. Подібний підхід на даний момент мало розвинений, але цікавий в методологічному плані, оскільки по суті є антропоморфних: відтворює ключові елементи роботи людської свідомості. У зв'язку з цим перспективні розробки з прикладного використання ЛП алгоритмів в складі АОС.

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

    Вступ. Однотипний навчальний матеріал, наприклад заучувати слова іноземної мови, зберігається у вигляді масиву, з пронумерованими елементами. Формування ІП полягає в оперуванні номерами елементів, але не самими елементами. Елементи, можливо, спочатку поміщені в масив в упорядкованому вигляді, наприклад слова взяті безпосередньо з алфавітного словника. Подібне додаткове впорядкування може негативно впливати на процес утворення асоціацій при заучуванні матеріалу. Тому матеріал доцільно разупорядочіть із застосуванням ГСЧ. Разупорядоченності набір індивідуально самоорганізується в процесі освоєння матеріалу: повторення окремих елементів при формуванні ІП коригується у зв'язку з частотами правильних відповідей. При цьому вивчений матеріал фільтрується, не завантажуючи ІП; а матеріал вимагає додаткових зусиль на вивчення (запам'ятовуванню) - пред'являється багаторазово. Даний процес має ряд особливостей при реалізації його на ЛП алгоритмах. Далі представлені відповідний апарат опису, модель, заснована на використанні ЛП алгоритмів, і основні результати моделювання.

    Апарат опису. Розглядається набір з N об'єктів, що не тотожних один одному, пронумерованих в порядку від 0 до (N-1).

    У початковому стані об'єкти стандартно впорядковані відповідно до нумерації. Для цільового використання об'єкти набору А повинні бути разупорядочени ( "перетасувати"): розташовані у вигляді випадкової послідовності

    А: {ат, аь а'..., а ^}; а, ф а ,; 1,} е {0, 1, 2, ..., (N-1)},

    (1)

    В: {Ьо,'ь Ь2, ..., Ь ^ -1)}; Ь, ф Ь ,; Ь, е {ат, аь а * ..., а ^)}; 1,, е {0, 1, 2, ..., (N-1)}.

    В процесі цільового використання об'єкти Ь повинні послідовно вилучатись в порядку їх розташування в (2). Для внесення разупорядочения (переходу від (1) до (2)) вихідна послідовність А повинна бути рандомізованих: об'єкти а1 повинні бути переставлені з місця на місце. Об'єкт а1 однозначно представлений його номером 1: номер є покажчиком на об'єкт, достатнім для вибору і цільового використання. Рандомізують послідовність чисел 0, 1, 2, ..., (N-1), що є індексами в (1). При рандомізації елементи в А (1) ототожнюються з їх індексами.

    Розглядається ЛП уявлення [1, 2] послідовності чисел (індексів) в (1). Ці індекси розташовані в сусідніх не перетинаються сегментах реєстрових уявлень (РГП):

    (Р-1) (р-2) ... (2) (1) (0);

    (2р-1) (2р-2) ... (р + 2) (р + 1) (р); (3)

    (Т * р-1) (т * р-2) ... ((т-1) р + 2) ((т-1) р + 1) ((т-1) р).

    Одинзв'язні сегменти в РГП впорядковані за зростанням індексів з боку молодших розрядів. Кількість РГП - т, число сегментів в кожному РГП - р, розмір кожного з сегментів - q біт. Нумерація сегментів починається з 0, що відповідає індексації об'єктів в (1). Так само з 0 починається нумерація РГП в (3). Величини N т, р, q жорстко пов'язані між собою і обмежені розміром г регістра процесора:

    N < т * р; г > p * q; N < 211 (4)

    Наприклад в 32-розрядному обчислювальному пристрої (г = 32) для подання набору А (1) при числі елементів N = 60 прийнятні значення р = 5; q = 6. При цьому потрібно 12 РГП: Ль А2, Л3, ..., Л ^. Відповідна структура (3) в двійковому і десятковому посегментних уявленнях має вигляд:

    Л! = (000100) 2 (000011) 2 (000010) 2 (000001) 2 (000000) 2; Л2 = (001001) 2 (001000) 2 (000111) 2 (000110) 2 (000101) 2;

    Л12 = (111011) 2 (111010) 2 (111001) 2 (111000) 2 (110111) 2;

    Л1 = (4) 10 (3) 10 (2) 10 (1) 10 (0) 10 = 67903552 (10); Л2 = (9) ю (8) 10 (7) ю (6) 10 (5) ю = 15312115700);

    Л12 = (59) ю (58) ю (57) ю (56) ю (55) ю = 1005297207 (10).

    Нижні індекси в правих частинах виразів в (5) і (6) позначають показники підстави системи числення. При ЛП подання інформації, для рандомізації елементів набору А доцільно застосовувати дві процедури: зрушення і кросинговер. Для реалізації зсуву псевдовипадковим чином (з використанням генератора псевдовипадкових чисел) вибираються 1-й (1 е (0, 1, 2, ..., (т-1))) РГП і точка розриву - номер} - (? +1) сусідніх сегментів} е (0, 1, 2, ..., (р-1)) в 1-м РГП. Точка розриву поділяє РГП на два фрагмента: фрагмент праворуч від неї містить сегменти від 0-го до? -Го, фрагмент зліва - сегменти від (? +1) -го до (р-1) -го. Далі набори фрагментів, міняються місцями:

    {А (р-1) ... а ^ Ка, а ^ ... а: ав} ^ {aJ а (] - 1) ... а: а0>{А (р-1) ... а (] + 1)}. (7)

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

    {А (р-1) ... а (, + 1)} {а, а ^) ... а1 а0} ^ {а (р-1). а ^ Кь, а ^) ... ь1 Ь0}; (8)

    {Ь (р-1) ... Ь (] + 1)} {видання, а (, - 1) ... ь1 Ь0} ^ {Ь (р-1) ... Ь (, + 1)} {а, а ^) ... а1 а0}.

    Легко бачити, що кожна з цих двох процедур окремо обмежена по переместительности здатності: зрушення (7) переміщують сегменти тільки по рядках в межах одного РГП, а кросинговер (8) - тільки за стовпцями, без зміни позиції всередині РГП. Може бути показано, що з довільної початкової розстановки т * п об'єктів в наборі з т штук п-елементних РГП, послідовним застосуванням операцій зсуву і кросинговеру може бути отримана необхідна наперед задана розстановка об'єктів. Як наперед заданої БТП, може бути взята будь-яка з (т * п)! розстановок. Таким чином, зі стандартної розстановки елементів А (1), за допомогою

    застосування комбінації процедур зсуву і кросинговеру, може бути отримана будь-яка добре (якісно) рандомізованих розстановка В (2).

    Якість рандомізації - ступінь випадковості розташування елементів в наборі - є неформальне судження. Математика не дає остаточного критерію якості випадковості, оскільки це принципово не входить в її завдання. Міра значущості математичного опису (ступінь прийнятності рівня математичної формалізації) встановлюється на критеріальною основі, відповідно до емпіричними уявленнями. В даному випадку вихідним є стандартний упорядкований набір. До нього послідовно застосовуються процедури рандомізації. Твердження про те, що набір рандомізованих якісність є неформальним судженням про достатність числа повторень застосованих процедур. Запропоновано три критерії, що характеризують якість рандомізації розглянутої послідовності даних в ЛП поданні:

    - число нерухомих елементів N5 - елементів в В, які залишилися на вихідних місцях, відповідних їх місцях в А;

    - сумарне отстояние (зміщення) Ц елементів в В від їх стандартної розстановки - їх вихідних місць в А;

    - сумарної довжини Ь2 шляху в масиві елементів В - сумарне відстань між елементами в В згідно їх індексами нумерації в А.

    З урахуванням того, що в рамках процедури рандомізації, елементи в А (1) ототожнюються з їх номерами, які позначаються індексами, критерії уточнюються наступним чином. Елемент Ь, є нерухомим - знаходиться на своєму початковому місці, відповідному його положенню в А, якщо Ь, = 1. Зсув елемента Ь, від його вихідного місця визначається як | Ь, - 1 |. Нехай два елементи Ь, і Ь, в стандартній розстановці були сусідніми: ак, ак + ь Відстань між цими елементами Ь, і Ь, визначається як | , -, |.

    Розробка моделі. Запропоновані три критерії якості реалізовані в складі статистичної моделі процесу рандомізації набору А даних в ЛП поданні. Призначення моделі -дослідження динаміки зміни характеристик N5, Ц і Ь2. На малюнку 1 представлена ​​структурна схема ключового елемента - ядра моделі. Параметрами моделі, вводяться на початку роботи алгоритму (блок 2), є N т, р і q, пов'язані співвідношеннями (4). Ними задається структура розглянутого набору об'єктів (1, 2, 3). В якості вихідних параметрів задаються коефіцієнти кратності повторення процедур зсуву до! і кросинговеру к2. У моделі до! і к2 застосовуються при формуванні критеріїв завершення циклів по зрушень і кросинговер (блоки 5 і 8). Так само задається коефіцієнт кратності повторення процедур рандомізації к3, кожна з яких включає ^ -кратноє повторювані зрушення і к2-кратний кроссинговер. Призначення параметра к3 - формування критерію завершення циклу рандомізації (блок 9) і, таким чином, визначення кроку накопичення даних в роботі моделі. Коефіцієнтами до! к2 і к3 в сукупності в моделі задається варіант структури процесу рандомізації. Представлено два рівня вкладеності циклів: внутрішній і наступний за ним. Внутрішній рівень циклів включає послідовно виконувані цикли зсуву (блоки 3-5) і кросинговеру (блоки 6-8). Наступний рівень - цикл рандомізації в цілому (блоки 3-9). Цикл по набору статистики (не показаний) є зовнішнім і включає рандомізацію і обробку результатів.

    Мал. 1. Структурна схема ядра рандомізації для дослідження динаміки показників N5, Ц і Ь2 ЛП

    моделі представлення даних.

    Дослідження. Модель реалізована на мові Python і досліджена з вихідними даними (5, 6). Отримано математичні очікування (графік 1) і стандартні відхилення (графік 2) для NS, Lj і L2 від

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

    Як випливає з графіків, спостерігаються початковий період рандомізації, який характеризується зміною трендів математичного очікування, а так само стійкий стан - наявністю «полки сталих значень» на графіку. Початковий період може розглядатися як і сталий, перехідний, оскільки стандартні відхилення на відповідних ділянках графіків так само не мають сталих значень. Сталий стан може розглядатися як статистично стабільне, що характеризується постійністю (в статистичному сенсі) стандартного відхилення. Довготривала стабільність поведінки графіків на ділянках, відповідних стійким станам, демонструється на виразках на малюнку 2. Цікавим є перехідна точка: завершення початкового періоду - вихід в сталий стан - мінімальний достатній обсяг виконання процедур рандомізації. Моделювання показало, що для розглянутих трьох критеріїв якості рандомізації перехідні точки - величини одного порядку, і можуть бути оцінені як: N5, = 35; Ьь = 35; Ь2 = 50.

    а)

    50 45 40 35 30 25 20 15 10 5 0

    м

    Н

    0 5 10 15 20 25 30 35 40 45 50 55 60

    б)

    1200-г Ь,

    1000 800 600 400 200 0

    Н

    0 5 10 15 20 25 30 35 40 45 50 55 60

    в)

    1200 1000 800 600 400 4. 200 0

    ь

    0 5 10 1

    --1----

    5 20 25 30 35 40 45 50 55 60

    Н

    Мал. 2. Залежності математичного очікування (1) і стандартного відхилення (2) кількості нерухомих сегментів N5 (а), сумарного отстояния ь1 (б) від стандартної (початкової) розстановки і

    сумарної довжини Ь2 (в) шляхи в масиві з N = 60 сегментів, від числа Н ітерацій процедури рандомізації виду «один зсув - один кроссинговер». На врізки - ті ж залежності при в 5 разів більше

    тривалої рандомізації.

    З використанням моделі малюнок 1 досліджено ступінь випадковості розстановки сегментів при застосуванні процедур тільки зсуву або тільки кросинговеру. Зіставлення процедур виконано для діапазону Н від 1 до 300 з кроком 5, при числі реалізацій- 50 (рисунок 3). Процедура рандомізації «один зсув - один кроссинговер» є найбільш швидкою: графіки проходять найбільш круто. При цьому, як видно з графіків, завжди дотримані умови

    N3 (1) < N3 (2) < N3 (3); Ц 1) > Ц (2) > Ц (3); Ь2 (1) > Ь2 (2) > Ь2 (3).

    (9)

    Цікавим є знаходження оптимального співвідношення числа зрушень і кроссинговеров. Для окремого випадку (5, 6) на основі тієї ж статистичної моделі малюнок 1 досліджена залежність продуктивності від співвідношення кратності процедур зсуву до! і кросинговеру к2 в складі процедури рандомізації. Оцінка продуктивності реалізована за часом виконання цільових процедур з виключенням часу виконання допоміжних процедур (циклоутворення, статистичної обробки та інше). Отримані результати демонструються малюнком 4. Представлені нормовані тимчасові затримки (Тнорм.) Для 25 різних варіантів виконання процедури рандомізації: з варіюванням числа операцій зсуву і кросинговеру в межах від 1 до 5. Дані отримані на основі статистики об'ємом 500 реалізацій. Кожна реалізація - серія з повторенням від 1 до 60 процедур рандомізації, що відповідає щільності розташування точок відліку по осі Н на графіках малюнок 2. Кожна процедура рандомізації включає 5 повторів (зовнішній цикл малюнок 1). Таким чином, в кожній реалізації послідовно проведено 5, 10, 15, ..., 290, 300 процедур рандомізації, щоразу починаючи зі стандартною розстановки сегментів (5). З точки зору хронометражу виконання програми, конкретне наповнення сегментів байдуже, оскільки самі процедури зсуву і кросинговеру не включають обробку інформації всередині сегментів. Відповідно, байдужі початкові умови виконання рандомізації. Тобто в цілому в межах виконання моделі тимчасові витрати пропорційні числу ітерацій. Тому в даному випадку при хронометражі має місце обробка статистично однорідних даних.

    45 40 35 30 25 20 15 10 5 0 Попереднє

    1400 1200 1000 800 600 400 200 0

    100

    Мал. 3. Ключові фрагменти графіків залежностей математичних очікувань для числа нерухомих сегментів N5, сумарного отстояния Ц від стандартної розстановки і сумарної довжини Ь2 шляху в масиві з N = 60 сегментів, від числа Н ітерацій для процедур рандомізації виду «один зсув - один кроссинговер» (1 ), «тільки кроссинговер» (2) і «тільки зрушення» (3).

    Окремі "ступені" на графіку малюнок 4 непорівнянні між собою для вказівки найбільш ефективного (оптимального) співвідношення числа зрушень і числа кроссинговеров в процедурі рандомізації. Різниця в часах виконання процедур рандомізації (різна висота "ступенів") пояснюється двома факторами: різною ефективністю зсуву і кросинговеру і різним наповненням процедури рандомізації. Крім того, хронометраж ніяк не пов'язаний з показниками якості рандомізації N5, ь1, Ь2 і знаходженням перехідною точки. У зв'язку з цим, на основі результатів, ілюстрованих малюнком 4, можуть бути зроблені висновки тільки про співвідношення тривалостей процедур зсуву і кросинговеру.

    Аналіз отриманих чисельних результатів, візуально спостережуваний так само на графіку малюнок 4, показує, що "сходинки" при постійному значенні по кросинговері (в напрямку зміни по зрушень) відрізняються по "крутості" від "сходинок" за фіксованими зрушень (в напрямку зміни по кросинговері ) і співвідносяться як 2/3. Самі "сходинки" мають сенс збільшення за часом виконання відповідної процедури. Тобто, приріст часу при додаванні однієї сдвиговой процедури приблизно співвідноситься з приростом часу при додаванні однієї кроссінговерной процедури як 2 / 3. Ставлення 2/3 відповідає співвідношенню звернень до ГСЧ в процедурах зсуву і кросинговеру. При зсуві ГСЧ використовується двічі (вибір РГП і точки розриву), при кроссинговере - тричі (вибір двох РГП і точки розриву). Для забезпечення порівнянності результатів, що відносяться до різних варіантів процедури рандомізації (різні співвідношення числа зрушень і кроссинговеров), доцільно проводити нормування по числу звернень до ГПСЧ.

    Мал. 4. Залежність нормованого часу виконання Тнорм. процедури рандомізації від числа послідовно проведених в ній процедур зсуву (від 1 до 5) і кросинговеру (від 1 до 5).

    Обговорення результатів. З графіка малюнок 3 видно, що зрушення в порівнянні з кросинговером має істотно меншою "потужністю" щодо можливості рандомізації. Зрозуміло, графіки побудовані для єдиного окремого випадку (5, 6), але примітно, що за всіма трьома застосованим критеріям NS, Li, і L2 демонструється одна і та ж ситуація, з якої повинно випливати, що "потужність" процедури рандомізації повинна зростати з зростанням частки кроссинговеров. З графіка малюнок 4 слід протилежна тенденція: кроссинговер в півтора рази "повільніше" зсуву, тобто за час виконання двох кроссинговеров може бути виконано три зсуву. В обох випадках критерієм оптимальності виконання процедури є мінімум витрат комп'ютерного часу. Поряд з критерієм якості (результативності, ступеня рандомізірованни) отриманого результату, цей критерій є ключовим при виборі конкретної ЛП структури АОС. Подальше дослідження моделі доцільно за трьома напрямками:

    - зіставлення критеріїв якості NS, Li, L2, вибір найбільш прийнятного (дієвого) з

    них;

    - знаходження оптимального співвідношення зрушень і кроссинговеров за критерієм виконання, при введенні нормування результатів за критеріями якості;

    - вивчення аналогічних характеристик для структур відмінних від (5, 6).

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

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

    ЛІТЕРАТУРА:

    1. Міхаль О.Ф., Руденко О.Г. Принципи організації систем нечіткого регулювання на однорідних локально-паралельних алгоритмах // Керуючі системи та машини. - 2001. - № 3. - С. 3-10.

    2. Міхаль О.Ф. Моделювання розподілених інформаційно-керуючих систем засобами локально-паралельних алгоритмів обробки нечіткої інформації // Проблеми біоніки. Всеукраїнська міжвідомча науково-технічний збірник. - Харків: ХНУРЕ. - 2001. -Вип. 54. - С. 28-34.

    3. Мохамад Алі, Міхаль О. Ф. Перспективи реалізації локально-паралельних обчислень на багатоядерних процесорах // Радіоелектронні і комп'ютерні системи. - 2008. - № 6 (33). - С. 234-237.

    Мохамад Алі - аспірант кафедри ЕОМ Харківського національного університету радіоелектроніки.

    Міхаль Олег Пилипович - д.т.н., професор кафедри ЕОМ Харківського національного університету радіоелектроніки.

    Наукові інтереси авторів: нечітка логіка, обробка нечіткої інформації, локально-паралельні алгоритми.


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

    Завантажити