Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”

ЛІСОВЕЦЬ ВОЛОДИМИР ЯРОСЛАВОВИЧ

УДК 004.272.26

МОДЕЛЮВАННЯ ТА ОПТИМІЗАЦІЯ ПАРАЛЕЛЬНОГО 
ПОШУКУ ІНФОРМАЦІЇ У ФАЙЛАХ БАЗ ДАНИХ 

Спеціальність 01.05.03 – математичне та програмне
 забезпечення обчислювальних машин і систем

А В Т О Р Е Ф Е Р А Т
дисертації на здобуття наукового ступеня
кандидата  технічних наук

Львів  – 2012
Дисертацією є рукопис.
Робота виконана у Львівському національному університеті імені Івана Франка Міністерства освіти і науки, молоді та спорту України

Науковий керівник:	доктор фізико-математичних наук, професор 
Цегелик Григорій Григорович,  
Львівський національний університет 
імені Івана Франка,
завідувач кафедри математичного моделювання соціально-економічних процесів,
заслужений діяч науки і техніки України, 
м. Львів

Офіційні опоненти:	доктор технічних наук, доцент
	Пелещишин Андрій Миколайович,
	Національний університет “Львівська політехніка”,
	завідувач кафедри соціальних комунікацій та інформаційної діяльності
	
	кандидат технічних наук, доцент
Пастух Олег Анатолійович,
Тернопільський національний технічний університет імені Івана Пулюя, доцент кафедри комп’ютерних систем та мереж

Захист відбудеться 15 березня 2012 року о 14 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Львівському національному університеті “Львівська політехніка” за адресою: 79013, м. Львів, вул. С. Бандери, 12.

З дисертацією можна ознайомитися в бібліотеці Національного університету “Львівська політехніка” за адресою: 79013, м.Львів, вул. Професорська, 1.

Автореферат розісланий         лютого  2012  року.

Вчений секретар 
спеціалізованої вченої ради        		 Р. А. Бунь

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Завдяки високій надійності та продуктивності багатопроцесорні ЕОМ широко використовують для підтримки й організації великих баз даних (БД). Під час розв’язування різноманітних задач із використанням БД основний акцент переноситься з процедур опрацювання інформації на процедури організації збереження та пошуку інформації в них. Тому продуктивність обчислювальних систем, орієнтованих на роботу з великими БД, значною мірою залежить від ефективності методів паралельного пошуку інформації в БД.
У наш час паралельний пошук інформації у файлах баз даних можливий лише із застосуванням стандартних методів розпаралелювання алгоритмів, але жоден з цих методів не враховує закону розподілу ймовірностей звертання до записів БД.
Найвідоміший підхід для реалізації паралельного доступу до бази даних ґрунтується на попередній сегментації БД. Для цього базу даних ділять на інформаційно незалежні сегменти, і надалі робота ведеться із сегментом на окремому процесорі як із повноцінною базою даних. Над таким підходом працювали Аарон Дарлінг, Лукас Кері, Вільям Гропп, Евінг Луск, Нагіза Саматова та ін. Цей підхід не враховує закону розподілу записів у БД і в багатьох випадках неефективно використовує наявні процесори.
Моделювання та оптимізація пошуку інформації у базах даних є доволі складним завданням. Зазвичай за критерій ефективності беруть середню кількість порівнянь, необхідних для пошуку запису. На практиці це теоретичне середнє досить часто відрізняється від реальної середньої кількості порівнянь. Насамперед це пов’язано з тим, що ймовірності звертання до записів у файлах баз даних підпорядковані нерівномірним законам розподілу: одні записи шукають досить часто, інші дуже рідко. Тобто в багатьох системах опрацювання інформації типовими є випадки нерівномірного розподілу ймовірностей, на що вказують багато зарубіжних авторів, зокрема Д. Кнут, Б. Шнейдерман та ін. Моделювання та оптимізацію методів пошуку інформації для однопроцесорних ЕОМ за різних законів розподілу ймовірностей звертання до записів файла здійснювали Д. Кнут, Дж. Мартін, Г. Г. Цегелик, А. В. Мельничин та ін.
Оскільки в більшості БД переважають саме нерівномірні закони розподілу ймовірностей звертання до записів, актуальною є проблема розроблення ефективних методів паралельного пошуку, які б враховували закон розподілу, за яким розподілено записи у файлах БД, та ефективно використовували наявні ресурси багатопроцесорної ЕОМ.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в межах держбюджетних науково-дослідних робіт кафедри математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка.
1. “Математичне моделювання природничих, інформаційних та соціально-економічних процесів”. Номер держ. реєстрації 0106U005905 (2006–2008 рр). Автор розробив метод m-паралельного послідовного перегляду та два варіанти методу m-паралельного блочного пошуку; дослідив ефективність цих методів для різних законів розподілу ймовірностей звертання до записів файла баз даних.
2. “Математичне та комп’ютерне моделювання природничих, інформаційних та соціально-економічних процесів. Розробка інтелектуальних систем підтримки прийняття рішень”. Номер держ. реєстрації 0109U004325 (2009–2011 рр). Автор побудував оптимальні схеми доступу до інформації послідовних файлів, що зберігаються в зовнішній пам’яті багатопроцесорних систем та розробив програмне забезпечення, що реалізує паралельні методи пошуку в базі даних.
Мета і завдання дослідження. Метою дисертаційної роботи є розроблення методів паралельного пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів у випадку багатопроцесорної системи та побудова оптимальних схем доступу до інформації файлів, які зберігаються у зовнішній пам’яті багатопроцесорної ЕОМ.
	Мета дисертаційної роботи визначає необхідність розв’язання таких завдань:
•	проаналізувати відомі результати досліджень ефективності методів пошуку інформації та оптимальні схеми доступу до інформації послідовних та індексно-послідовних файлів баз даних для однопроцесорних систем за різних законів розподілу ймовірностей звертання до записів файлів;
•	здійснити розпаралелення алгоритму послідовного перегляду та методу блочного пошуку, ввести поняття методу m-паралельного послідовного перегляду та методу m-паралельного блочного пошуку;
•	дослідити ефективність запропонованих паралельних методів пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів і для кожного конкретного закону розподілу ймовірностей звертання до записів файла визначити найкращий паралельний метод;
•	розробити оптимальні схеми доступу до інформації послідовних файлів, що зберігаються в зовнішній пам’яті багатопроцесорних систем, та дослідити їх ефективність.
Об’єктом дослідження є процес паралельного пошуку інформації у файлах баз даних.
Предметом дослідження є методи паралельного пошуку інформації у файлах баз даних та побудова оптимальних схем доступу до інформації послідовних файлів для різних законів розподілу ймовірностей звертання до записів.
Методи дослідження. В основу досліджень покладено підхід, який запропонував керівник дисертаційної роботи проф. Г. Г. Цегелик для розв’язання задач у межах проблеми оптимізації сучасних інформаційних технологій. Результати дослідження одержано з використанням теорії організації БД – для побудови методів паралельного пошуку інформації у файлах БД; чисельних методів аналізу, методів теорії ймовірностей, математичної статистики – для визначення ефективності методів за різних законів розподілу ймовірностей звертання до записів; дослідження операцій та системного аналізу – для побудови оптимальних стратегій доступу до записів; а також експериментальних методів досліджень – для підтвердження одержаних теоретичних результатів.
Наукова новизна одержаних результатів. В результаті проведених досліджень у дисертації отримано такі нові наукові результати:
•	вперше розроблено метод m-паралельного послідовного перегляду та два варіанти методу m-паралельного блочного пошуку за допомогою розпаралелювання методів послідовного перегляду та блочного пошуку інформації у файлах баз даних, що дало змогу використовувати ці методи в паралельних системах;
•	одержано математичні співвідношення для оцінювання ефективності запропонованих методів паралельного пошуку для таких законів розподілу ймовірностей звертання до записів, як рівномірний, “бінарний”, Зіпфа та узагальнений, завдяки чому, для кожного закону розподілу ймовірностей звертання до записів файла визначено найкращий метод;
•	виведено математичні співвідношення для визначення оптимальної кількості блоків, на яку необхідно розділити послідовний файл, у випадку різних законів розподілу ймовірностей звертання до записів за допомогою мінімізації математичного сподівання загального часу, потрібного для пошуку запису у файлі, що дало можливість побудувати оптимальні схеми паралельного доступу до інформації послідовних файлів, які зберігаються в зовнішній пам’яті багатопроцесорної системи;
•	визначено частку процесорів, задіяних під час пошуку для запропонованих методів паралельного пошуку інформації за різних законів розподілу ймовірностей звертання до записів, обчисленням таких показників, як “паралельна ефективність” та “прискорення”, що дало можливість визначати, скільки процесорів доцільно задіяти в паралельному пошуку.
Практичне значення одержаних результатів. Результати дослідження можна застосовувати для побудови нових систем керування базами даних та машин баз даних. Розроблена крос-платформна бібліотека здійснює пошук в базі даних за допомогою запропонованих методів паралельного пошуку. Завдяки цьому можна використовувати готову реалізацію методів паралельного пошуку та перевірити результати теоретичних досліджень. На основі цієї бібліотеки розроблено систему паралельного опрацювання даних, яка надає можливість створення, накопичення, модифікації та пошуку інформації. 
	Основні результати використано для розроблення системи паралельного опрацювання даних у торгово-виробничій компанії “Львівхолод”, в Інституті інформаційних технологій “Інтелліас”, у НДР, виконаних на кафедрі математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка, а також впроваджені у навчальний процес на факультеті прикладної математики та інформатики Львівського національного університету імені Івана Франка: під час викладання курсів “Основи інформаційних технологій” та “Сучасні інформаційні технології”, підготовки курсових та дипломних робіт.
 	Особистий внесок здобувача. Всі наукові результати, викладені у дисертації, одержав здобувач особисто. У друкованих працях, опублікованих у співавторстві, автору належать: [8, 11, 13, 22, 23] – метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних; [7] – перший варіант методу m-паралельного блочного пошуку записів у файлах баз даних та дослідження його ефективності; [6] – другий варіант методу m-паралельного блочного пошуку записів та аналіз його ефективності; [10, 12, 17, 18] – порівняльний аналіз ефективності методів паралельного пошуку записів у файлах баз даних; [1, 15, 19, 24] – моделювання та оптимізація паралельного доступу до інформації послідовних файлів баз даних для багатопроцесорних ЕОМ; [3, 16, 21] – побудова оптимальних стратегій паралельного пошуку інформації у послідовних файлах; [2, 5, 20] – використання методу m-паралельного блочного пошуку з повним завантаженням блока записів в основну пам’ять; [4, 5, 20] – використання методу m-паралельного блочного пошуку із завантаженням m записів в основну пам’ять; [9, 14] – використання методу m-паралельного блочного пошуку з мінімальним завантаженням записів в основну пам’ять.
Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися на міжнародних та всеукраїнських наукових конференціях і семінарах, а саме:  Міжнародній науково-технічній конференції “Системний аналіз та інформаційні технології” (Київ, 2008–2009); третій Міжнародній науково-технічній конференції “Комп’ютерні науки та інформаційні технології” (Львів, 2008); III Міжнародній конференції молодих вчених “Комп’ютерні науки та інженерія” (Львів, 2009); XV Міжнародній науково-практичній конференції “Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти” (Київ, 2010); II Всеукраїнській науково-практичній конференції “Інформатика та системні науки” (Полтава, 2011); Міжвузівській науково-практичній конференції “Сучасні інформаційні технології в економіці, менеджменті та освіті” (Львів, 2008); Всеукраїнських наукових конференціях “Сучасні проблеми прикладної математики та інформатики” (Львів, 2006–2009) та на семінарах кафедри математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка (2008 – 2011).
Публікації. Основні результати дисертаційного дослідження висвітлено у 23 наукових публікаціях. З них 12 праць опубліковано у фахових наукових виданнях, в тому числі 9 статей у фахових виданнях з технічних наук і 3 статті у фахових виданнях з фізико-математичних наук, та 11 публікацій у вигляді матеріалів та тез доповідей наукових конференцій.
Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, додатків та списку використаної літератури. Загальний обсяг дисертації 169 сторінок, на яких представлено 33 таблиці, 64 рисунки, 126 найменувань літературних першоджерел, що розміщені на 16 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ 
У вступі обґрунтовано актуальність теми, показано її зв’язок з науковими програмами та темами, сформульовано мету та завдання дисертаційної роботи, висвітлено наукову новизну та практичне значення одержаних результатів, а також наведено відомості про апробацію отриманих результатів.
У першому розділі здійснено огляд літератури за темою дисертації. Зокрема, розглянуто особливості архітектур багатопроцесорних ЕОМ та проведено їх аналіз і порівняння. Проаналізовано алгоритми пошуку інформації у файлах баз даних для однопроцесорних ЕОМ за різних законів розподілу ймовірностей звертання до записів файла.
Оскільки для більшості систем опрацювання інформації типовими є випадки нерівномірного закону розподілу ймовірностей звертання до записів, то дослідження ефективності методів пошуку інформації у файлах баз даних здійснюється як для рівномірного, так і для різних законів нерівномірного розподілу ймовірностей звертання до записів, зокрема: 
•	“бінарний” розподіл
,    ,                                 (1)
де pi – ймовірність звертання до і-го запису, N – кількість записів у файлі;
•	закон Зіпфа 
,                                             (2)
де  – частинна сума гармонічного ряду;
•	узагальнений
,                                           (3)
де с (0 < c <1) – довільний параметр,  – частинна сума узагальненого гармонічного ряду (якщо с = 0.8614, частковим випадком цього закону є розподіл, що наближено задовольняє правило “80 – 20”).
За критерій ефективності прийнято математичне сподівання кількості порівнянь, потрібних для пошуку запису в файлі, під час дослідження ефективності методів пошуку та математичне сподівання загального часу, необхідного для пошуку запису у файлі, в разі знаходження оптимальних стратегій доступу до інформації файлів БД. Вибраний підхід дає можливість не тільки дослідити ефективність різних методів пошуку інформації у файлах баз даних для кожного конкретного закону розподілу ймовірностей звертання до записів, але й з’ясувати залежність ефективності пошуку як від зміни методу, так і від зміни закону розподілу ймовірностей звертання до записів. Крім цього для кожного конкретного закону розподілу ймовірностей звертання до записів визначено найкращий метод пошуку.
У другому розділі дисертаційної роботи розроблено метод m-паралельного послідовного перегляду та два варіанти методу m-паралельного блочного пошуку у файлах баз даних та встановлено їх ефективність.  Дослідження здійснено для рівномірного закону розподілу та різних законів нерівномірного розподілу ймовірностей звертання до записів (1)-(3).
Зроблено припущення, що до складу багатопроцесорної ЕОМ входять m процесорів, які працюють паралельно та мають спільне поле пам’яті. За   критерій ефективності взято математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі.
Під час розроблення методу m-паралельного послідовного перегляду розглянуто послідовний файл, який містить N записів. Усі записи файла умовно поділені на n блоків по m записів у кожному (). Метод m-паралельного послідовного перегляду складається з низки кроків. На (k+1)-му кроці і‑й процесор переглядає значення ключа (mk+i)-го запису. Через максимум n кроків шуканий запис буде знайдено, якщо він міститься у файлі.
Математичне сподівання кількості паралельних порівнянь, потрібних для пошуку запису в файлі, виражається формулою
,                                               (4)
де pi –  ймовірність звертання до і-го запису файла.
Значення математичного сподівання кількості паралельних порівнянь для різних законів розподілу ймовірностей звертання до записів, виражених формулами (1)-(3), є такими:
−	для рівномірного закону розподілу
;                                                  (5)
−	для “бінарного” закону розподілу 
;                                                    (6)
−	для закону Зіпфа 
, де ;        (7)
−	для узагальненого закону 
,                (8)
де  – повільно зростаюча функція.
		Проведено порівняльний аналіз ефективності методу для розглянутих законів розподілу ймовірностей звертання до записів файла та різної кількості процесорів. Виявлено, що розпаралелювання методу послідовного перегляду підвищує ефективність приблизно в m разів для всіх розглянутих законів розподілу ймовірностей звертання до записів, крім “бінарного”.
		Стосовно першого варіанта методу m-паралельного блочного пошуку вважаємо, що записи впорядкованого файла поділені на n блоків по sm записів у кожному. Розглянемо, як відбувається пошук запису в файлі. Спочатку шукається блок, який містить шуканий запис, переглянувши m останніх записів блоків. Після цього пошук продовжується у локалізованому блоці за допомогою методу m-паралельного послідовного перегляду. Блок-схему реалізації методу зображено на рис. 1. Математичне сподівання E кількості паралельних порівнянь, потрібних, щоб знайти запис у файлі, подано у вигляді суми математичного сподівання кількості паралельних порівнянь, необхідних для локалізації блока, який містить шуканий запис, і математичного сподівання кількості паралельних порівнянь, потрібних для пошуку запису в локалізованому блоці. Тоді E виражається формулою
.                                  (9)
Виведено явний вираз математичного сподівання для різних законів розподілу ймовірностей та обчислено оптимальні значення параметра n, за яких математичне сподівання (9) досягає мінімуму. Знайдено оптимальні значення математичного сподівання.
Математичне сподівання E залежить від розглянутих законів розподілу ймовірностей звертання до записів та кількості процесорів. Розпаралелювання методу блочного пошуку для всіх охоплених законів розподілу ймовірностей звертання до записів, окрім “бінарного”, істотно підвищує ефективність методу. За “бінарного” закону розподілу ймовірностей збільшення кількості процесорів не забезпечує зростання ефективності.
	
Ні, l > s

Початок

N, m, k=1, l=1
Знайти оптимальне n

Зчитати останні m записів блока k

k:= k+1, перевірити, чи блок знайдений

Результат

Зчитати l-ті m записів знайденого блока

l:= l+1, перевірити, чи запис знайдений

Ні

Так

Ні, l ≤ s

Так

Рис. 1. Блок-схема реалізації першого варіанта методу m-паралельного блочного пошуку

		Для другого варіанта методу m-паралельного блочного пошуку приймаємо, що записи файла поділено на nm блоків по sm записів у кожному, тоді кількість записів у файлі буде N = snm2. Пошук запису у файлі відбувається так. Спочатку локалізується блок, який містить шуканий запис, використовуючи метод m‑паралельного послідовного перегляду серед останніх елементів блоків. Після цього пошук продовжується в локалізованому блоці також за допомогою методу m-паралельного послідовного перегляду. Тоді математичне сподівання E має вигляд:
.           (10)
		Явний вираз математичного сподівання для кожного з розглянутих законів розподілу ймовірностей звертання має такий вигляд (1)-(3):
−	рівномірний закон розподілу 
;                                         (11)
−	“бінарний” закон розподілу 
;                            (12)
−	закон Зіпфа
, (13) 
де ;
−	узагальнений закон 

, (14)
де , – повільно зростаючі функції.
Знайдено також оптимальні розміри блоків, за яких математичне сподівання (11)-(14) досягає мінімуму. З порівняння ефективності другого варіанта методу m‑паралельного блочного пошуку з першим випливає такий висновок: якщо m = 1, то обидва варіанти методу однаково ефективні; якщо кількість процесорів зростає, то ефективність другого варіанта методу значно зростає порівняно з ефективністю першого. Слід зауважити, що перший варіант методу блочного пошуку є простішим в реалізації.
	Для кожного з розглянутих методів паралельного пошуку проаналізовано такі показники ефективності паралельних алгоритмів як “прискорення” та “паралельна ефективність”. Це дало можливість з’ясувати доцільність використання більшої кількості процесорів та визначити наскільки ефективно паралельний алгоритм використовує процесори під час розв’язання задачі.
	У третьому розділі розроблено оптимальні схеми доступу до інформації БД. Для цього використано метод m-паралельного  послідовного перегляду та два варіанти методу m-паралельного блочного пошуку. Критерієм ефективності слугує математичне сподівання загального часу, потрібного для пошуку запису в файлі.
	Використовуючи метод m-паралельного послідовного перегляду зроблено деякі припущення. Вважається, що у послідовному файлі, який міститься у зовнішній пам’яті багатопроцесорної ЕОМ, є N записів і всі ці записи умовно поділені на n блоків по m записів у кожному. Для пошуку запису відбувається послідовне зчитування блоків записів в основну пам’ять і їх m‑паралельний послідовний перегляд. Введено такі позначення: a0 = b0 + d0m – час зчитування блока записів в основну пам’ять, де b0 , d0 – сталі, t0 – час виконання операції m-паралельного послідовного перегляду записів в основній пам’яті; pi – ймовірність звертання до i-го запису файла; 
Et – математичне сподівання загального часу, необхідного для пошуку запису в файлі. Тоді для визначення Et одержано формулу
.                                 (15)
Виведено явні вирази Et для кожного з розглянутих законів розподілу ймовірностей звертання до записів. Оскільки на практиці здебільшого знайти значення сталих b0, d0 та t0 досить складно. І ці значення доволі сильно відрізняються для різних обчислювальних машин, то зроблено припущення, що нам відомі значення відношень b0/d0 та t0/d0, які достатньо близькі для різних обчислювальних машин. Крім того, для практичних обчислень дослідження функції Et замінено на вивчення функції Et/d0.
Так, на рис. 2 показано залежність функції Et /d0 від закону розподілу ймовірностей звертання до записів у разі використання методу m-паралельного послідовного перегляду, різної кількості процесорів, N = 105 і (b0 + t0)  / d0 = 100.

		

Рис. 2. Значення функції Et /d0 для різних законів розподілу ймовірностей звертання до записів, різної кількості процесорів, N = 105 і (b0 + t0) / d0 = 100

У разі застосування методу m-паралельного послідовного перегляду для всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім “бінарного”, ефективність пошуку підвищується лише до певної кількості процесорів m = . Якщо ж кількість процесорів зростає до значень, які перевищують , спостерігається незначне зниження ефективності методу. 
Якщо припустити, що файл, який містить N записів, умовно поділений на n блоків по ml записів у кожному (N = nml), a0 = b0 + d0ml – час зчитування блока записів в основну пам’ять, для пошуку запису відбувається послідовне зчитування блоків записів в основну пам’ять і їх m-паралельний послідовний перегляд, то
.               (16)
Визначено явний вираз для Et для різних законів розподілу ймовірностей звертання до записів і встановлено оптимальні значення параметрів n і l, за яких математичне сподівання є мінімальним. 
У цьому розділі також розглянуто три підходи до організації пошуку запису в файлі у випадку використання методу m-паралельного блочного пошуку. Вважаємо, що записи впорядкованого файла поділено на n блоків по sm записів у кожному, тоді N=nsm.
Застосовуючи метод m-паралельного блочного пошуку з повним завантаженням блока записів в основну пам’ять, спочатку в основній пам’яті локалізуємо блок, який містить шуканий запис, шляхом зчитування m останніх записів кожного блока. Після цього пошук продовжується вже у локалізованому блоці за допомогою методу m-паралельного послідовного перегляду [6, 7]. Якщо a0 = b0 + d0ms – час зчитування блока записів в основну пам’ять, то математичне сподівання загального часу, потрібного для пошуку запису, подається формулою
.                     (17)
Виведено явні вирази математичного сподівання Et, знайдено оптимальні значення параметра n, за яких Et досягає мінімуму, та досліджено поведінку Et в околі точки мінімуму. Виявлено, що оптимальний вибір значення параметра n пришвидшує роботу методу на 10-20%.
Використовуючи метод m-паралельного блочного пошуку із завантаженням m записів в основну пам’ять спочатку у зовнішній пам’яті локалізуємо блок, який містить шуканий запис, зчитуючи m останніх записів кожного блока. Після цього локалізований блок зчитуємо в основну пам’ять і пошук продовжуємо за допомогою методу m-паралельного послідовного перегляду. Якщо a0 = b0 + d0m – час зчитування блока записів в основну пам’ять, то математичне сподівання загального часу, необхідного для пошуку запису, має вигляд:
.    (18)
Знайдено явні вирази функції Et для кожного з розглянутих законів розподілу ймовірностей та оптимальні значення параметра n, за яких математичне сподівання (18) досягає мінімуму. Зокрема, оптимальні значення параметра n для N = 106, b0/d0 = 100, t0/d0 = 0.003, деяких m і різних законів розподілу ймовірностей звертання до записів наведено в таблиці.
Для цього методу одержано такі практичні результати. Збільшення кількості процесорів у два рази для m ≤ 32 пришвидшить роботу алгоритму на 25-40%. Зростання кількості процесорів, якщо m ≥ 64, незначно підвищить ефективність розглянутого методу. Натомість у випадку “бінарного” закону розподілу ймовірностей збільшення кількості процесорів призведе до зменшення ефективності методу для всіх m > 2. Вибір оптимального значення параметра n, що враховує закон розподілу ймовірностей звертання до записів файла, в найкращому випадку підвищить ефективність роботи методу в декілька разів.
Таблиця 
Оптимальні значення параметра n для різних законів 
розподілу ймовірностей та різної кількості процесорів
m	 Рівномірний 	Узагальнений	Зіпфа	
		с=0.2	с=0.4	с=0.6	с=0.8		
1	1414	1500	1633	1868	2380	3794	
2	1000	1061	1155	1321	1683	2683	
4	707	750	816	934	1190	1897	
8	500	530	577	660	841	1342	
16	354	375	408	467	595	949	
32	250	265	289	330	421	671	
64	177	188	204	234	298	474	

У разі використання методу m-паралельного блочного пошуку з мінімальним завантаженням записів в основну пам’ять розроблено оптимальні стратегії пошуку записів у файлах, які зберігаються у зовнішній пам’яті багатопроцесорної ЕОМ. В цьому випадку файл умовно ділять на n блоків по m2s записів у кожному, а кожний блок – на m підблоків по ms записів у кожному (N = nm2s). І пошук потрібного запису відбувається так. Спочатку локалізується блок зчитуванням в основну пам’ять m записів, взятих по одному останньому запису з кожного підблока фіксованого блока. Тобто для локалізації підблока використовується другий варіант методу m-паралельного блочного пошуку. Після цього в локалізованому підблоці ведеться пошук необхідного запису за допомогою методу m-паралельного послідовного перегляду. Якщо a0 = b0 + d0m – час зчитування блока записів в основну пам’ять, то Et виражається формулою
.         (19)
	Для цього випадку також виведені явні вирази математичного сподівання Et (19) для різних законів розподілу ймовірностей звертання до записів і знайдено значення параметрів n і s, за яких математичне сподівання досягає мінімуму. На рис. 3 показано залежність функції Et/d0 від закону розподілу ймовірностей звертання до записів та різної кількості процесорів за знайдених оптимальних n у випадку N = 106, b0/d0 = 100 та t0/d0 = 0.003. Як бачимо з рисунка, функція Et/d0 досить істотно залежить як від закону розподілу, так і від кількості процесорів. 
Виявлено, що у разі використання цього методу збільшення кількості процесорів для m > 64 недоцільне і не підвищує істотно ефективності методу. Натомість зростання кількості процесорів удвічі для 1 < m < 64 забезпечує пришвидшення роботи алгоритму на 15-40%. 

Рис. 3  Залежність функції Et/d0 від закону розподілу ймовірностей звертання до записів та різної кількості процесорів за знайдених оптимальних n у випадку N = 106, b0/d0 = 100 та t0/d0 = 0.003

У результаті порівняння розглянутих підходів встановлено, що метод m-паралельного блочного пошуку із завантаженням m записів в основну пам’ять значно ефективніший, ніж метод m-паралельного блочного пошуку з повним завантаженням блока записів в основну пам’ять. Але ефективність підходу із мінімальним завантаженням записів в основну пам’ять практично така сама, що і підходу із завантаженням m записів в основну пам’ять.
	У четвертому розділі описано розроблену крос-платформну бібліотеку parallelSearch.lib, яка для пошуку використовує запропоновані методи паралельного пошуку інформації у файлах баз даних, та створену систему паралельного опрацювання даних, яка для паралельного пошуку враховує закон розподілу ймовірностей звертання до записів файла. Розроблене програмне забезпечення реалізовано об’єктно-орієнтованою мовою програмування С++ із застосуванням стандартної бібліотеки шаблонів STL та крос-платформної бібліотеки boost, що дало змогу використовувати розроблене програмне забезпечення на операційних системах Linux та Windows.
Програмна реалізація бібліотеки parallelSearch.lib складається з декількох компонент, що відповідають за опрацювання вхідних даних, роботу з БД, здійснення паралельного пошуку, збір статистики, визначення закону розподілу ймовірностей звертання до записів БД та одержання структурованих результатів пошуку. Перелік компонент зображено на рис 4.

Рис. 4. Діаграма компонент бібліотеки parallelSearch.lib

Компоненти умовно поділяють на п’ять модулів: 
1.	Input/output processor – модуль, що відповідає за опрацювання вхідних даних, реєстрацію користувачів, аналіз команд та одержання структурованого результату.
2.	Running machine – модуль, що реалізує пул потоків, для здійснення паралельного пошуку інформації та виконання команд до бази даних.
3.	Frequency Analyzer – модуль, що зберігає статистичну інформацію про доступ до кожного запису у базі даних та на основі статистичної інформації, за допомогою методу найменших квадратів, визначає закон розподілу, за яким розподілено записи у файлі.
4.	Data Storage – модуль для роботи з даними.
5.	Parallel search manager – відповідає за міжкомпонентну взаємодію.
Розроблена система паралельного опрацювання даних надає можливість створення, накопичення, модифікації та обробки інформації, що знаходиться в зовнішній пам’яті багатопроцесорної ЕОМ. У ході роботи система збирає статистику про доступ до даних. На підставі статистичних даних вона наближено визначає закон розподілу, за яким розподілені дані. Далі система здійснює пошук необхідних даних, враховуючи закон розподілу. Захист інформації організований у трьох рівнях: автентифікація користувачів, управління доступом користувачів до бази даних та шифрування даних.
Статистичні дані, одержані в результаті використання розроблених засобів програмного забезпечення, повністю підтверджують обчислені теоретичні результати.
У додатках подано акти про впровадження результатів дисертаційного дослідження.
Висновки
У дисертаційній роботі розв’язано актуальну наукову задачу розроблення та оптимізації методів паралельного пошуку інформації у файлах баз даних для різних законів розподілу ймовірностей звертання до записів. У роботі одержано такі результати:
1.	На підставі аналізу відомих методів пошуку інформації встановлено, що математичне сподівання кількості порівнянь, необхідних для пошуку запису, істотно залежить від закону розподілу ймовірностей звертання до записів БД. З’ясовано, що алгоритми пошуку піддаються розподілу на інформаційно незалежні частини для подальшого їх розпаралелювання та обґрунтовано необхідність створення паралельних методів пошуку, що враховують закон розподілу, за яким розподілено записи в БД.
2.	Удосконалено методи послідовного перегляду та блочного пошуку інформації у файлах баз даних, шляхом їх розпаралелення, запропоновано та обґрунтовано метод m-паралельного послідовного перегляду та два варіанти методу m-паралельного блочного пошуку для використання цих методів в обчисленнях на паралельних системах.
3.	Досліджено ефективність розроблених методів паралельного пошуку  для таких законів розподілу ймовірностей звертання до записів, як рівномірний, “бінарний”, Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило “80 – 20”. Одержано математичні співвідношення для оцінювання ефективності розроблених методів паралельного пошуку, що дає можливість для кожного закону розподілу ймовірностей звертання до записів файла визначити найкращий метод.
4.	Виведено математичні співвідношення для визначення загального часу, потрібного для пошуку інформації послідовних файлів, що знаходяться в зовнішній пам’яті багатопроцесорної ЕОМ, для різних законів розподілу ймовірностей звертання до записів файла, встановлено оптимальну кількість блоків та обґрунтовано різні стратегії доступу до пам’яті, що дає змогу для кожного конкретного закону розподілу використовувати свою оптимальну схему доступу до послідовних файлів, що зберігаються в зовнішній пам’яті багатопроцесорної системи.
5.	Обчислено такі показники ефективності паралельних алгоритмів як “паралельна ефективність” та “прискорення” для запропонованих методів паралельного пошуку інформації за різних законів розподілу ймовірностей звертання до записів, що дає можливість визначати доцільну кількість процесорів для паралельного пошуку.
6.	Розроблено програмне забезпечення, що здійснює пошук у файлах баз даних за допомогою запропонованих методів паралельного пошуку, враховуючи ймовірності звертання до записів файла, що дало змогу повністю підтвердити одержані теоретичні результати. 

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
1.	Лісовець В. Я. Моделювання та оптимізація паралельного доступу до інформації файлів баз даних для багатопроцесорних ЕОМ / В. Я. Лісовець, Г. Г. Цегелик  // Міжн. наук.-техн. журнал „Комп’ютинг”. – 2009. – Том 8, Вип. 2. – С. 24-32. 
2.	Лісовець В. Я. Побудова оптимальних стратегій вибору інформації у послідовних файлах баз даних за використання методу m-паралельного блочного пошуку / В. Я. Лісовець, Г. Г. Цегелик  // Фізико-математичне моделювання та інформаційні технології. – 2010. – Вип. 12. – С. 161-169.
3.	Лісовець В. Я. Оптимальні стратегії паралельного пошуку інформації у послідовних файлах / В. Я. Лісовець, Г. Г. Цегелик // Вісник Національного університету „Львівська політехніка”. Серія „Інформаційні системи та мережі”. – 2008. – № 631. – C. 207-211.
4.	Лісовець В. Я. Оптимізація m-паралельного блочного пошуку інформації у послідовних файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик  // Відбір і обробка інформації. – 2009. – Вип. 31(107). – С. 105-111.
5.	Лісовець В. Я. Порівняльний аналіз двох підходів до побудови оптимальних стратегій пошуку інформації у файлах баз даних для багатопроцесорних ЕОМ / В. Я. Лісовець, Г. Г. Цегелик  // Вісник Національного університету „Львівська політехніка”. Серія „Інформаційні системи та мережі”. – 2010. – № 673. – C. 135-145.
6.	Лісовець В. Я. Один з варіантів методу m-паралельного блочного пошуку записів і його ефективність / В. Я. Лісовець, Г. Г. Цегелик // Фізико-математичне моделювання та інформаційні технології. – 2008. – Вип. 7. – С. 103-111.
7.	Лісовець В. Я. Метод m-паралельного блочного пошуку записів у файлах баз даних та його ефективність / В. Я. Лісовець, Г. Г. Цегелик  // Відбір і обробка інформації. – 2007. – Вип. 27(103). – С. 87-92.
8.	Лісовець В. Я. Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик // Фізико-математичне моделювання та інформаційні технології. – 2007. – Вип. 5. – С. 109-119.
9.	Цегелик Г. Г. Побудова оптимальних стратегій  пошуку інформації у послідовних файлах баз даних у випадку використання одного з варіантів методу m-паралельного блочного пошуку / Г. Г. Цегелик, В. Я. Лісовець // Вісник Хмельницького національного університету. Технічні науки. № 5'2009. – C. 109-115.
10.	Лісовець В. Я. Порівняльний аналіз ефективності методів паралельного пошуку записів у файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик // Вісник Львівського університету. Серія: прикладна математика та інформатика. – 2008.  – Вип. 14. –  С. 185-193.
11.	Лісовець В. Я. Метод m-паралельного послідовного пошуку записів у файлах баз даних і його ефективність / В. Я. Лісовець, Г. Г. Цегелик  // Вісник Львівського університету. Серія: прикладна математика та інформатика. – 2007.  – Вип. 13.  –  С. 177-186.
12.	 Лісовець В. Я. Коефіцієнти прискорення й паралельної ефективності методів паралельного пошуку / В. Я. Лісовець, Г. Г. Цегелик  // Науковий вісник Ужгородського університету. Серія: математика і інформатика. Вип. 21. – Ужгород, 2010. – С. 86-93. 
13.	 Лісовець В. Я. Порівняльний аналіз ефективності методу m-паралельного послідовного пошуку записів у файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик  // Гуманітарно-економічні проблеми суспільства. Зб. наук. праць. Число 3. – 2007. – С. 318-325.
14.	 Лісовець В. Я. Побудова оптимальних стратегій паралельного пошуку у випадку з використанням одного з варіантів методу m-паралельного блочного пошуку / В. Я. Лісовець, Г. Г. Цегелик // Тези доп. XV Міжнар. наук.-практ. конф. “Інформаційні технології в економіці, менеджменті і бізнесі. Проблеми науки, практики і освіти” (Київ, 25-26 лютого 2010 р.).– Київ, 2010. – С. 156-157.
15.	 Лісовець В. Я. Моделювання та оптимізація паралельного пошуку інформації у файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик // Матеріали третьої Міжнар. конф. “Комп’ютерні науки та інформаційні технології” (Львів, 25 – 27 вересня 2008 р.). – Львів, 2008. – С. 277-280.
16.	 Лісовець В. Я. Оптимальні стратегії пошуку інформації у послідовних файлах / В. Я. Лісовець, Г. Г. Цегелик // Матеріали XI Міжн. наук.-техн. конф. “Системний аналіз та інформаційні технології” (Київ, 26-30 травня 2009 р.). – Київ, 2009. – С. 508.
17.	 Лісовець В. Я. Методи паралельного пошуку інформації у файлах баз даних та їх ефективність / В. Я. Лісовець, Г. Г. Цегелик  // Матеріали X Міжнар. наук.-техн. конф. “Системний аналіз та інформаційні технології” (Київ, 20-24 травня 2008 р.). – Київ, 2008. – С. 370.
18.	 Лісовець В. Я. Дослідження ефективності методів паралельного пошуку інформації в файлах баз даних / В. Я. Лісовець // Матеріали III Міжнар. конф. молодих вчених CSE-2009 “Комп’ютерні науки та інженерія” (Львів, 14 – 16 травня 2009 р.). – Львів, 2009. – С. 238-239.
19.	Лісовець В. Я. Моделювання та оптимізація доступу до інформації файлів баз даних для багатопроцесорних систем / В. Я. Лісовець, Г. Г. Цегелик // Матеріали II Всеукр. наук.-практ. конф. “Інформатика та системні науки” (Полтава, 17-19 березня 2011 р.). – Київ, 2011. – С. 191-194.
20.	 Лісовець В. Я. Оптимальні стратегії пошуку інформації у послідовних файлах у випадку використання методу m-паралельного блочного пошуку / В. Я. Лісовець, Г. Г. Цегелик // Матеріали XVI Всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики” (Львів, 8 – 9 жовтня 2009 р.). – Львів, 2009. – С. 126-127.
21.	 Лісовець В. Я. Оптимальні стратегії паралельного пошуку інформації у послідовних файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик // Матеріали XV Всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики” (Львів, 23 – 25 вересня 2008 р.). – Львів, 2008. – С. 113.
22.	 Лісовець В. Я. Імовірнісні характеристики ефективності методу послідовного перегляду записів у файлах баз даних / В. Я. Лісовець, А. В. Мельничин, Г. Г. Цегелик // Матер. Міжвуз. наук.- практ. конф.  “Сучасні інформ. техн. в економіці, менеджменті та освіті” (Львів, 6-7 листопада 2008 р.).  Львів, 2008.  С. 52-56.
23.	 Лісовець В. Я. Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних / В. Я. Лісовець, Г. Г. Цегелик // Матеріали XIV Всеукр. наук. конф. “Сучасні проблеми прикладної математики та інформатики” (Львів, 2 – 4 жовтня 2007 р.). – Львів, 2007. – С. 94.
24.	 Лісовець В. Я. Аналіз та перспективи розвитку багатопроцесорних обчислювальних систем / В. Я. Лісовець // Тези доп. XIII Всеукр. наук.-практ. конф. “Сучасні проблеми прикладної математики та інформатики” (Львів, 3-5 жовтня 2006 р.). – Львів, 2006. – С. 84.

АНОТАЦІЇ
Лісовець В. Я. Моделювання та оптимізація паралельного пошуку інформації у файлах баз даних. – Рукопис.
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.03 – “математичне та програмне забезпечення обчислювальних машин і систем”. – Національний університет “Львівська політехніка”, Львів, 2012.
У дисертаційній роботі розроблено метод m-паралельного послідовного перегляду та два варіанти методу m-паралельного блочного пошуку інформації у файлах баз даних. Виведено явні вирази математичного сподівання кількості паралельних порівнянь, необхідних для пошуку запису за рівномірного закону розподілу ймовірностей звертання до записів та таких нерівномірних законів як: “бінарний”, Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило “80 – 20”. Для двох варіантів методу m-паралельного блочного пошуку знайдено оптимальну кількість блоків, за яких математичне сподівання кількості паралельних порівнянь досягає мінімуму. 
Розроблено оптимальні схеми доступу до інформації послідовних файлів для різних законів розподілу ймовірностей звертання до записів за допомогою поділу файла на оптимальну кількість блоків та вибору різних стратегій доступу до пам’яті. За критерій ефективності взято математичне сподівання загального часу, необхідного для пошуку запису.
Розроблено систему паралельного опрацювання даних, яка надає можливість створення, накопичення, модифікації та оброблення інформації, а для пошуку запису використовує розроблені оптимальні схеми доступу до інформації, враховуючи закон розподілу ймовірностей звертання до записів файла.
Ключові слова: багатопроцесорні системи, m-паралельний пошук, блочний пошук, бази даних, закон розподілу ймовірностей.

Лисовец В. Я. Моделирование и оптимизация параллельного поиска информации в файлах баз данных. – Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.03 – “математическое и программное обеспечение вычислительных машин и систем”. – Национальный университет “Львовская политехника”, Львов, 2012.
В диссертационной работе разработаны метод m-параллельного последовательного просмотра и два варианты метода m-параллельного блочного поиска. Найдены явные выражения математического ожидания количества параллельных сравнений, необходимых для поиска записи в файле для равномерного закона распределения вероятностей обращения к записям и таких неравномерных законов распределения как: “бинарный”, Зипфа и обобщенный, частным случаем которого является распределение, приближенно удовлетворяющее правило “80-20”. 
Разработаны оптимальные схемы доступа к информации последовательных файлов для разных законов распределения вероятностей обращения к записям файла путем разбиения файла на оптимальное количество блоков и выбора различных стратегий доступа к памяти. В качестве критерия эффективности использовано математическое ожидание общего времени, необходимого для поиска записей в файле.
Разработана система параллельной обработки данных, которая предоставляет возможность создания, накопления, модификации и обработки информации, а для поиска записи использует разработанные оптимальные схемы доступа к информации, учитывая закон распределения вероятностей обращения к записям файла.
Ключевые слова: многопроцессорные системы, m-параллельный поиск, блочный поиск, базы данных, закон распределения вероятностей.

Lisovets V. Y. Modeling and optimization of parallel search for information in the database files. – Manuscript.
Theses for Ph.D degree on technical sciences in specialty 01.05.03 – “mathematical and software support of computer machines and systems”. – Lviv Polytechnic National University, Lviv, 2012.
This thesis addresses the realization of parallel modification of sequential field searching method and block field searching method. The m-parallel method of sequential field searching and two variants of m-parallel block field searching method are offered. These methods are oriented to be used in multiprocessing system for information searching in files of database. The effectiveness of these methods is analyzed for different probability distribution laws of field access as a discrete uniform, binomial, Zipf, and generalized the partial occasion of witch is the probability distribution approximately satisfying the rule “80 – 20”. The mathematical expectation of number of parallel comparisons necessary for field searching in files was taken as a criterion of the effectiveness. The explicit expression of mathematical expectation of number of parallel comparisons is found for each considered probability distribution law. In case of two variants of m-parallel block field searching method it was found the optimal number of blocks in which the mathematical expectation of parallel comparisons reached its minimum, for each considered distribution law of field access.
Indicators of performance of parallel algorithm such as „speedup‟ and „parallel efficiency‟ were calculated for each proposed method in case of different probability distribution laws. It was obtained that the effectiveness of the m-parallel method of sequential field searching increased proportionally to the number of processors and all processors are fully used during the execution of the method. The analysis of the obtained indicators of „speedup‟ for the first variant of m-parallel block field searching showed us that increasing the number of processors leaded only to a slight increase of efficiency. And the „parallel efficiency‟ showed us a small processors usage during the execution of the method. The effectiveness of the second variant of m-parallel block field searching increases almost proportionally increasing the number of processors. During the execution of this method the processors used more than 90% CPU.
The optimal strategies of field searching in sequenced files stored in external memory of multiprocessing system are made. The optimal strategies indicate how to split the file on the optimal number of blocks considering different probability distribution laws. This makes it possible for each considered distribution law to use its optimal access to sequential files stored in external memory of multiprocessor system. In this case the mathematical expectation of total time needed for field searching in files was taken as a criterion of effectiveness.
The analysis of obtained optimal strategies in case of using m-parallel method of sequential field searching showed that increasing the number of processors increased the effectiveness only to a specific number of processors for each considered probability distribution law except binomial law. 
It was investigated three variants of using the method of m-parallel block field searching in case of different probability distribution laws, such as: using the method of m-parallel block field searching with loading of full block in RAM, with loading of m records in RAM and with a minimum loading of records in RAM. The effectiveness of three variants of using the method of m-parallel block field searching was compared and analyzed for different probability distribution laws and different number of processors.
The system of parallel data processing is developed. It provides the creation, storage, modification and processing of information. This system of parallel data processing uses developed optimal strategies of field searching considering different probability distribution laws. The theoretical calculated results were fully confirmed by obtained statistical data from developed software.
Key words: multiprocessor systems, m-parallel search, block search, database, probability distribution law.