Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність
Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномірного, "бінарного", Зіпфа й узагальне...
Збережено в:
| Опубліковано в: : | Фізико-математичне моделювання та інформаційні технології |
|---|---|
| Дата: | 2008 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/21875 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2008. — Вип. 7. — С. 103-111. — Бібліогр.: 11 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859856860445671424 |
|---|---|
| author | Лісовець, В. Цегелик, Г. |
| author_facet | Лісовець, В. Цегелик, Г. |
| citation_txt | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2008. — Вип. 7. — С. 103-111. — Бібліогр.: 11 назв. — укр. |
| collection | DSpace DC |
| container_title | Фізико-математичне моделювання та інформаційні технології |
| description | Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномірного, "бінарного", Зіпфа й узагальненого, частковим випадком якого є розподіл, який наближено задовольняє правило "80-20"). За критерій ефективності прийнято математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Побудовано оптимальні схеми методу, тобто схеми, за яких математичне сподівання досягає мінімуму. Зі збільшенням кількості процесорів у k разів ефективність запропонованого варіанта методу зростає в k разів, порівняно з ефективністю звичайного блочного методу, для всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім "бінарного".
A version of m-parallel block record browsing method in a database file is proposed. The method is designed for application in multiprocessors of computers. The effectiveness of the method for different probability distribution of record request frequency (discrete uniform, binomial, Zipf and generalized, the partial case of which is the probability distribution approximately satisfying the rule "80-20") is investigated. The mathematical expectation of the parallel comparisons number needed for the search of a record in a file is taken as a criterion of effectiveness. The optimal schemes of the method i. e. the scheme in which the mathematical expectation attains its minimum are proposed. When the number of processors increases in k times the effectiveness of the proposed method increases in k times as compared with the effectiveness of the conventional block method for all examined probability distributions of record request frequency except for binomial one.
Предлагается вариант метода m-параллельного блочного поиска записей в файлах баз данных, ориентированный на использование в многопроцессорных ЭВМ. Исследуется эффективность этого метода для известных законов распределения вероятностей обращения к записям (равномерного, "бинарного", Зипфа и обобщенного, частным случаем которого является распределение, приближенно удовлетворяющее правило "80-20"). В качестве критерия эффективности принимается математическое ожидание количества параллельных сравнений, необходимых для поиска записи в файле. Построены оптимальные схемы метода, при которых математическое ожидание достигает минимума. С увеличением количества процессоров в k раз эффективность предложенного варианта метода возрастает в k раз по сравнению с эффективностью обычного блочного метода для всех рассмотренных законов распределения вероятностей обращения к записям за исключением "бинарного".
|
| first_indexed | 2025-12-07T15:44:10Z |
| format | Article |
| fulltext |
103
Один із варіантів методу m-паралельного блочного
пошуку записів і його ефективність
Володимир Лісовець1, Григорій Цегелик2
1 Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000,
e-mail: kafmmsep@franko.lviv.ua
2 д. ф.-м. н., професор, Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів,
79000, e-mail: kafmmsep@franko.lviv.ua
Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах
баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його
ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномір-
ного, «бінарного», Зіпфа й узагальненого, частковим випадком якого є розподіл, який набли-
жено задовольняє правило «80-20»). За критерій ефективності прийнято математичне
сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Побудо-
вано оптимальні схеми методу, тобто схеми, за яких математичне сподівання досягає мі-
німуму. Зі збільшенням кількості процесорів у k разів ефективність запропонованого варі-
анта методу зростає в k разів, порівняно з ефективністю звичайного блочного методу, для
всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім «бінарного».
Ключові слова: багатопроцесорні системи, m-паралельний пошук, блочний по-
шук, бази даних.
Вступ. Застосування паралельних обчислювальних систем є стратегічним напрям-
ком розвитку обчислювальної техніки. Це викликано обмеженістю максимально
можливої швидкодії звичайних послідовних ЕОМ, а також наявністю обчислю-
вальних задач, для розв’язування яких можливості існуючих засобів обчислю-
вальної техніки недостатні.
Проблема створення високопродуктивних обчислювальних систем належить
до переліку найскладніших науково-технічних задач. Організація паралельних
обчислень здійснюється, в основному, за рахунок уведення надлишкових функці-
ональних пристроїв (декількох процесорів). Якщо здійснити поділ алгоритмів, які
застосовуються, на інформаційно-незалежні частини й організувати виконання
кожної частини обчислень на різних процесорах, то можна прискорити процес
обчислень. Такий підхід дозволяє виконувати необхідні обчислення з меншими за-
тратами часу. Одержання максимально можливого прискорення обмежується тіль-
ки кількістю наявних процесорів і «незалежних» частин алгоритму.
Однак слід відзначити, що на даний час застосування паралельних обчис-
лень не одержало настільки широкого поширення, як це очікувалося багатьма до-
слідниками. Однією з можливих причин такої ситуації була донедавна висока
вартість високопродуктивних багатопроцесорних систем. Кардинальні змінили
відбулися з впровадженням порівняно дешевих багатоядерних процесорів, які вже
УДК 519.68
Володимир Лісовець, Григорій Цегелик
Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність
104
набули масового застосування. Інша причина стримування поширення паралель-
них систем полягає в тому, що для проведення обчислень необхідно змінити
традиційну послідовну технологію розв’язування задач на ЕОМ на паралельну.
Завдяки високій надійності та продуктивності багатопроцесорні ЕОМ ши-
роко використовують для підтримки й організації великих баз даних (БД). Під
час розв’язування різноманітних задач із використанням БД основний акцент пе-
реноситься з процедур обробки інформації на процедури організації збереження
та пошуку інформації в них. Тому продуктивність обчислювальних систем, орі-
єнтованих на роботу з великими БД, значною мірою визначається ефективністю
методів паралельного пошуку інформації в БД.
У працях [2, 3] розглянуто два паралельних методи пошуку інформації у
файлах БД: метод m-паралельного послідовного перегляду та метод m-па-
ралельного блочного пошуку. Вивчено ефективність цих методів для різних законів
розподілу ймовірностей звертання до записів таких, як: рівномірний, «бінарний»,
Зіпфа й узагальнений, частковим випадком якого є розподіл, що наближено задо-
вольняє правило «80-20» [1, 4, 8].
У роботі запропоновано інший варіант методу m-паралельного блочного
пошуку записів у файлах БД, проведено дослідження його ефективності для різ-
них законів розподілу ймовірностей звертання до записів. За критерій ефектив-
ності прийнято математичне сподівання кількості паралельних порівнянь, необ-
хідних для пошуку запису у файлі. Побудовано оптимальні схеми методу, за
реалізації яких математичне сподівання досягає мінімуму.
Дослідження ефективності m-паралельного блочного методу проведено для
рівномірного розподілу ймовірностей звертання до записів і таких законів нерів-
номірного розподілу ймовірностей:
• «бінарний» розподіл
1,1,
2
1
−== Nip ii , 12
1
−= NNp ,
де pi — ймовірність звертання до і-го запису, N — кількість записів у файлі;
• закон Зіпфа
1
1 1, 1, ,
N
i N
N k
p i N H
iH k=
= = =∑ ;
• узагальнений закон розподілу
Ni
Hi
p c
N
ci ,1,1
)( == , ∑
=
=
N
k
c
c
N k
H
1
)( 1 ,
де с (0 < c <1) — довільний параметр.
Слід зауважити, що у випадку однопроцесорних ЕОМ ефективність мето-
дів пошуку для різних законів розподілу ймовірностей звертання до записів, а та-
кож порівняння методів за ефективністю проведено у працях [5-7, 9-11]. Деякі
часткові випадки ефективності методів розглянуто в дослідженнях [1, 4].
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2008, вип. 7, 103-111
105
1. Варіант методу m-паралельного блочного пошуку та його ефективність
Розглянемо впорядкований файл, який містить N записів. Приймаємо, що записи
файла поділено на nm блоків, у кожному з яких є sm записів. Зауважимо, якщо
дане розбиття для цілих значень n, m, s не можна реалізувати, то доповнюємо
файл пустими записами. Тоді сумарна кількість записів у файлі буде N = snm2.
Пошук запису у файлі здійснюється так. Спочатку знаходимо блок, який містить
шуканий запис, використовуючи метод m-паралельного послідовного перегляду
серед останніх елементів блоків. Після цього з допомогою методу m-паралельного
послідовного перегляду продовжуємо пошук у локалізованому блоці.
Дослідимо ефективність цього методу для різних законів розподілу ймовір-
ностей звертання до записів.
Нехай pi — ймовірність звертання до і-го запису файла. Математичне спо-
дівання E кількості паралельних порівнянь, необхідних для пошуку запису у файлі,
подамо як суму математичного сподівання кількості паралельних порівнянь, що
потрібні для локалізації блоку записів, і математичного сподівання кількості па-
ралельних порівнянь, потрібних для пошуку запису в локалізованому блоці. Тоді
( ) ( ) ( ) ( ) ( )∑∑∑∑∑ ∑∑
= = =
+−+−
= = = =
+−+−−− +
=
nm
k
s
i
m
j
jmimsk
n
k
m
l
s
i
m
j
jmimslsmk ippkE
1 1 1
11
1 1 1 1
111 2 .
Знайдемо явний вираз для E у випадку різних законів розподілу ймовірнос-
тей звертання до записів і дослідимо залежність E від зміни закону розподілу
ймовірностей. Побудуємо оптимальні схеми m-паралельного блочного пошуку
для розглянутих законів розподілу ймовірностей звертання до записів.
1.1. Рівномірний розподіл. Якщо розподіл імовірностей звертання до записів є
рівномірний, то для E одержуємо вираз
)1(
2
1)1(
2
1
+++= snE .
Функція Е досягає мінімуму, якщо n s N m= = . Тоді min 1E N m= + .
1.2. «Бінарний» розподіл. Нехай імовірності звертання до записів задовольняють
«бінарний» розподіл. Тоді для E матимемо формулу [8]
( )
2
2
2 2 1 2
2 2 1 2 12 1
m s m
N
N m msm s
s sE −
= + + − −
− −−
.
Нехтуючи нескінченно малою величиною 2 – N, із достатньо високою точністю
можемо прийняти
1212
2
12
2
2
2
−
−
−
+
−
−
= msm
m
sm
sm ssE .
Володимир Лісовець, Григорій Цегелик
Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність
106
Оскільки m фіксований параметр, то функція E залежить лише від s. Обчислимо
похідну від функції E по s. Одержимо
2
2
2
2 2
2 ( ln 2 1) 1 2 ln 2
(2 1) (2 1)
ms m s
ms m s
dE sm m
ds
− +
= −
− −
або
( ) ( ) ( )( ){2 2 222
2 1 2 1 2 2 2 ln 2 1ms m s m s ms m sdE sm
ds
−− + = − − − − −
( ) ( ) ( ) }2 22 22 2 ln 2 2 2 ln 2 2 2 ln 2 1 1ms m s m s msm m sm − − + − − + − +
.
Покажемо, що для m ≥ 2, s ≥ 2 виконується умова E' > 0, тобто, якщо s ≥ 2, m ≥ 2,
то функція E монотонно зростає. Справді, якщо s ≥ 2, m ≥ 2, то завжди викону-
ються нерівності
022ln2 22
>−−msm , 112ln >−sm .
Тому достатньо довести, що для s ≥ 2, m ≥ 2 справджується така нерівність
02ln)22()12ln)(22( 22
>−−−− msm mssm .
Із очевидної нерівності 2m (m – 1) > m2ln2, яка виконується для m ≥ 2, s ≥ 2, отримаємо
2ln2 2)1( mmms >− або 02ln2 22
>−− mmssm .
Якщо m ≥ 2, s ≥ 2, то (2 – 2m2ln2) / 2ms < 0. Тоді
ms
mssm mm
2
2ln222ln2
2
22 −
>−− .
Звідси можна одержати, що 2ln)22(22 22
mmssm −>− , або
2ln)22()12ln)(22( 22
msm mssm −>−− .
Що і треба було довести. Тому E' > 0, якщо s ≥ 2, m ≥ 2.
Отже, якщо s ≥ 2, m ≥ 2, то функція E монотонно зростає. Оскільки s — ціле,
то в області s ≥ 1 функція досягає мінімального значення при s = 1 або s = 2.
Обчислимо значення E у цих точках
12
1
12
1
12
2
12
11
12
2
12
2
12
2)2( 22
2
222
2
+
+
−
−
−
+
−
+=
−
−
−
+
−
= mmm
m
mmm
m
m
m
E ,
12
1
12
2
12
11
12
2
12
2
12
2)1( 22
22
−
−
−
+
−
+=
−
−
−
+
−
= mm
m
mmm
m
m
m
E .
Оскільки 0
12
1
12
2
12
1)1()2( 222
>
−
−
+
+
−
=−
mm
m
m
EE для довільних m ≥ 2, то
E(2) > E(1). Отже, в області s ≥ 1 функція E досягає мінімуму, якщо s = 1.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2008, вип. 7, 103-111
107
1.3. Закон Зіпфа. Нехай імовірності звертання до записів задовольняють закон
Зіпфа. Тоді для E одержуємо вираз
2
1 ( 2) ( ) ( ) ( )N ms mm s
N
E n H sS nm S n S nms
H
= + + − − ,
де
∑
=
=
nm
k
kmsms HnmS
1
)( , ∑
=
=
n
k
skmsm HnS
1
22 )( , ∑
=
=
nms
k
kmm HnmsS
1
)( .
Використаємо для сум Sms(nm), )(2 nS sm та Sm(nms) апроксимації [8]
( ) 1
1( ) 1 ln( )
2ms NS nm nm H nm C≈ − + + ,
( )2 1
1( ) 1 ln
2Nm sS n n H n C≈ − + + ,
( ) 1
1( ) 1 ln( )
2m NS nms nms H nms C≈ − + + ,
де C1 = 0,5ln2π. Тоді з достатньо високою точністю можемо прийняти
1
1 1 1 12 ln( ) ln( ) ln ( 2)
2 2 2N
N
E H n s nm nms n s C
H
= + + − − + −
,
або
12 2
1 1 1 12 ln( ) ln ln 2
2 2 2N
N
N N NE H n nm n C
H mm n m n
= + + − − + −
.
Оскільки
[ ]12 2
1 11 1 ln( ) 2
22N
dE N nm C
dn H nm n
= + − − −
,
то для знаходження значення параметра n, за якого E досягає мінімуму, одер-
жуємо рівняння
)12ln(ln2 12
2 −++=− Cmn
m
Nnn .
1.4. Узагальнений закон. Нехай імовірності звертання до записів задовольняють
узагальнений закон розподілу. Тоді для визначення математичного сподівання E
маємо формулу [8]
2
( ) ( )( ) ( )
( )
1 ( 2) ( ) ( ) ( )c cc c
ms mNc m s
N
E n H sS nm S n S nms
H
= + + − − ,
де
∑
=
=
nm
k
c
kms
c
ms HnmS
1
)()( )( , ∑
=
=
n
k
c
skm
c
sm
HnS
1
)()(
22 )( , ∑
=
=
nms
k
c
km
c
m HnmsS
1
)()( )( .
Володимир Лісовець, Григорій Цегелик
Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність
108
Використовуючи для )()( nmS c
ms , )()(
2 nS c
sm
та )()( nmsS c
m відповідні апроксимації [8]
1 ( )
( )( )
1
1 ( )( )
1 2 ( )
c c
cc
ms N c
N c nmS nm nmH nm
c c nm
−
−
− α
≈ + + − −
,
2
1 ( )
( ) ( )
1
1 ( )( )
1 2
c c
c c
N cm s
N c nS n nH n
c c n
−
−
− α
≈ + + − −
,
1 ( )
( )( )
1
1 ( )( )
1 2 ( )
c c
cc
m N c
N c nmsS nms nmsH nms
c c nms
−
−
− α
≈ + + − −
,
де
cc
n
c n
c
Hn −−
−
−=α 2)1()(
2
1)( , cc
nm
c nm
c
Hnm −−
−
−=α 2)1()( )(
2
1)( ,
cc
nms
c nms
c
Hnms −−
−
−=α 2)1()( )(
2
1)(
є повільно зростаючими функціями, з достатньо високою точністю можемо при-
йняти, що
1 ( ) ( ) ( )
( )
( ) 1 1 1
1 1 ( ) ( ) ( )2
1 2 ( ) ( )
c c c c
c
Nc c c c
N
N c s nm n nmsE H n
c c nm n nmsH
−
− − −
− α α α = + + − − − −
або
1 ( ) ( ) ( )
( )
( ) 2 1 1 1
1 1 ( ) ( ) ( / )2
1 2 ( ) ( / )
c c c c
c
Nc c c c
N
N c N nm n N mE H n
c c m n nm n N mH
−
− − −
− α α α = − + − − − −
.
Обчислимо похідну від функції E по n, підставляючи замість похідних від α(c)(n) і
α(c)(nm) відповідно різниці α(c)(n + 1) – α(c)(n) і α(c)(nm + 1) – α(c)(nm). Одержимо
1
( ) ( )
( ) 3
1 1 ( 2 ) ( ) ( 1)
1 2 ( )
c
c c
c c
N
dE N c N n c nm n nm
dn c c mnH
−
−
− ≈ − + − α − α + − − −
( ) ( )
2
1 ( 1) ( 1 ) ( )c c
c n n n c n
n −
− α + − + − α
.
Тому, для наближеного обчислення значень параметра n, за яких функція Е дося-
гає мінімуму, маємо рівняння
( ) ( )3 2 ( 1 ) ( ) ( 1)
1
c cc cn n n c n n n
c
− − + + − α − α + = −
( ) ( )
3
2 ( 2 ) ( ) ( 1)
1
c c
c
N c n c nm n nm
cm −
− = + − α − α + −
.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2008, вип. 7, 103-111
109
1.5. Порівняння результатів. Оптимальні значення параметра n, за яких мате-
матичне сподівання кількості паралельних порівнянь, необхідних для пошуку за-
пису у файлі, досягає мінімуму, й оптимальні значення математичного споді-
вання для N = 106, деяких m і різних законів розподілу ймовірностей звертання
до записів приведені відповідно в табл. 1 і 2.
Таблиця 1
Оптимальні значення параметра n для різних законів
розподілу ймовірностей і різної кількості процесорів
Узагальнений m Рівномірний
с = 0,2 с = 0,4 с = 0,6 с = 0,8
Зіпфа «Бінарний»
1 1000 1060 1150 1297 1556 2058 1000000
2 500 530 575 648 778 1029 250000
4 250 265 288 324 389 515 62500
5 200 212 230 259 311 412 40000
10 100 106 115 130 156 206 10000
20 50 53 58 65 78 103 2500
40 25 27 29 32 39 52 625
50 20 21 23 26 31 41 400
100 10 11 12 13 16 21 100
Таблиця 2
Оптимальні значення математичного сподівання кількості паралельних
порівнянь для різних законів розподілу ймовірностей і різної кількості процесорів
Узагальнений m Рівномірний
с = 0,2 с = 0,4 с = 0,6 с = 0,8
Зіпфа «Бінарний»
1 1001 943,44 865,01 748,60 561,44 303,93 3,00
2 501 472,22 433,01 374,81 281,26 152,58 2,07
4 251 236,61 217,01 187,92 141,18 76,92 2,00
5 201 189,49 173,81 150,54 113,17 61,80 2,00
10 101 95,25 87,41 75,79 57,15 31,57 2,00
20 51 48,13 44,22 38,43 29,16 16,48 2,00
40 26 24,57 22,62 19,75 15,18 8,95 2,00
50 21 19,86 18,30 16,02 12,39 7,46 2,00
100 11 10,44 9,68 8,57 6,82 4,48 2,00
Висновки. У роботі запропоновано один із варіантів методу m-паралельного блочного
пошуку записів у файлах баз даних, який орієнтований на використання в багатопро-
цесорних ЕОМ. Досліджено ефективність цього методу для різних законів розподілу
ймовірностей звертання до записів: рівномірного, «бінарного», Зіпфа й узагальненого.
За критерій ефективності прийнято математичне сподівання кількості паралельних по-
рівнянь, необхідних для пошуку запису у файлі. Виведено співвідношення для опти-
мальних значень параметра n, при яких математичне сподівання досягає мінімуму.
Володимир Лісовець, Григорій Цегелик
Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність
110
Порівнюючи ефективність методу блочного пошуку [11] і запропонованого
варіанта методу m-паралельного блочного пошуку, приходимо до висновку, що
розпаралелювання методу блочного пошуку для всіх розглянутих законів розпо-
ділу ймовірностей звертання до записів, окрім «бінарного», суттєво підвищує ефек-
тивність. У випадку «бінарного» закону розподілу ймовірностей збільшення кіль-
кості процесорів не підвищує ефективності роботи. Якщо порівняти ефективність
даного варіанта m-паралельного блочного пошуку з варіантом, запропонованим
раніше в [3], то приходимо до такого висновку: якщо m = 1, то обидва варіанти
методу однаково ефективні; але зі зростанням кількості процесорів ефективність
запропонованого тут варіанта методу значно зростає, порівняно з ефективністю ме-
тоду, запропонованого в праці [3].
Література
[1] Кнут Д. Искусство программирования для ЭВМ.— М.: Изд. дом «Вильямс», 2000.
— Т. 3: Сортировка и поиск. — 832 с.
[2] Лісовець В. Я., Цегелик Г. Г. Метод m-паралельного послідовного перегляду
записів та його використання для пошуку інформації у послідовних файлах баз
даних // Фізико-математичне моделювання та інформаційні технології. — 2007. —
Вип. 5. — С. 109-119.
[3] Лісовець В. Я., Цегелик Г. Г. Метод m-паралельного блочного пошуку записів у фай-
лах баз даних та його ефективність // Відбір та обробка інформації. — 2007. —
Вип. 27(103). — С. 87-92.
[4] Мартин Дж. Организация баз данных в вычислительных системах. — М: Мир,
1980. — 644 с.
[5] Мельничин А. В., Цегелик Г. Г. Аналіз методів пошуку інформації в файлах баз да-
них для різних законів розподілу ймовірностей звертання до записів // Комп’ютерні
технології друкарства. — 2006. — № 15. — С. 95-112.
[6] Мельничин А. В., Цегелик Г. Г. Ефективність методу двійкового пошуку інформації
у файлах баз даних для різних законів розподілу ймовірностей звертання до запи-
сів // Вісн. Львів. ун-ту. Сер. прикл. матем. та інформ. — 2006. — Вип. 11. —
С. 225-229.
[7] Мельничин А. В., Цегелик Г. Г. Методи пошуку інформації у файлах баз даних та їх
ефективність для різних законів розподілу ймовірностей звертання до записів //
Комп’ютерні технології друкарства. — 2006. — № 16. — С. 41-52.
[8] Цегелик Г. Г. Организация и поиск информации в базах данных. — Львов: Вища
шк., 1987. — 176 с.
[9] Цегелик Г. Г., Мельничин А. В. Порівняльний аналіз ефективності методів пошуку
інформації у файлах баз даних // Відбір і обробка інформації. — 2005. — № 23. —
С. 135-142.
[10] Цегелик Г., Мельничин А. Метод пошуку інформації у файлах баз даних, який вра-
ховує розподіл імовірностей звертання до записів // Фізико-математичне моделю-
вання та інформаційні технології. — 2006. — Вип. 4. — С. 169-176.
[11] Філяк М. І., Цегелик Г. Г., Дороцька Х. С. Порівняльний аналіз ефективності
методу послідовного перегляду для різних законів розподілу ймовірностей
звертання до записів // Вісник НУ «Львівська політехніка». «Інформаційні системи
та мережі». — 2000. — № 406. — С. 226-231.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2008, вип. 7, 103-111
111
One of the version of m-parallel block record
browsing method and its effectiveness
Volodymyr Lisovets, Hryhorii Tsehelyk
A version of m-parallel block record browsing method in a database file is proposed. The method
is designed for application in multiprocessors of computers. The effectiveness of the method for
different probability distribution of record request frequency (discrete uniform, binomial, Zipf and
generalized, the partial case of which is the probability distribution approximately satisfying the
rule «80-20») is investigated. The mathematical expectation of the parallel comparisons number
needed for the search of a record in a file is taken as a criterion of effectiveness. The optimal sche-
mes of the method i. e. the scheme in which the mathematical expectation attains its minimum are
proposed. When the number of processors increases in k times the effectiveness of the proposed
method increases in k times as compared with the effectiveness of the conventional block method
for all examined probability distributions of record request frequency except for binomial one.
Вариант метода m-параллельного блочного поиска
записей и его эффективность
Владимир Лисовец, Григорий Цегелик
Предлагается вариант метода m-параллельного блочного поиска записей в файлах баз дан-
ных, ориентированный на использование в многопроцессорных ЭВМ. Исследуется эффек-
тивность этого метода для известных законов распределения вероятностей обращения
к записям (равномерного, «бинарного», Зипфа и обобщенного, частным случаем которого
является распределение, приближенно удовлетворяющее правило «80-20»). В качестве кри-
терия эффективности принимается математическое ожидание количества параллельных
сравнений, необходимых для поиска записи в файле. Построены оптимальные схемы метода,
при которых математическое ожидание достигает минимума. С увеличением количества
процессоров в k раз эффективность предложенного варианта метода возрастает в k раз
по сравнению с эффективностью обычного блочного метода для всех рассмотренных за-
конов распределения вероятностей обращения к записям за исключением «бинарного».
Отримано 15.11.07
|
| id | nasplib_isofts_kiev_ua-123456789-21875 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1816-1545 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:44:10Z |
| publishDate | 2008 |
| publisher | Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| record_format | dspace |
| spelling | Лісовець, В. Цегелик, Г. 2011-06-20T06:45:49Z 2011-06-20T06:45:49Z 2008 Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2008. — Вип. 7. — С. 103-111. — Бібліогр.: 11 назв. — укр. 1816-1545 https://nasplib.isofts.kiev.ua/handle/123456789/21875 519.68 Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномірного, "бінарного", Зіпфа й узагальненого, частковим випадком якого є розподіл, який наближено задовольняє правило "80-20"). За критерій ефективності прийнято математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Побудовано оптимальні схеми методу, тобто схеми, за яких математичне сподівання досягає мінімуму. Зі збільшенням кількості процесорів у k разів ефективність запропонованого варіанта методу зростає в k разів, порівняно з ефективністю звичайного блочного методу, для всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім "бінарного". A version of m-parallel block record browsing method in a database file is proposed. The method is designed for application in multiprocessors of computers. The effectiveness of the method for different probability distribution of record request frequency (discrete uniform, binomial, Zipf and generalized, the partial case of which is the probability distribution approximately satisfying the rule "80-20") is investigated. The mathematical expectation of the parallel comparisons number needed for the search of a record in a file is taken as a criterion of effectiveness. The optimal schemes of the method i. e. the scheme in which the mathematical expectation attains its minimum are proposed. When the number of processors increases in k times the effectiveness of the proposed method increases in k times as compared with the effectiveness of the conventional block method for all examined probability distributions of record request frequency except for binomial one. Предлагается вариант метода m-параллельного блочного поиска записей в файлах баз данных, ориентированный на использование в многопроцессорных ЭВМ. Исследуется эффективность этого метода для известных законов распределения вероятностей обращения к записям (равномерного, "бинарного", Зипфа и обобщенного, частным случаем которого является распределение, приближенно удовлетворяющее правило "80-20"). В качестве критерия эффективности принимается математическое ожидание количества параллельных сравнений, необходимых для поиска записи в файле. Построены оптимальные схемы метода, при которых математическое ожидание достигает минимума. С увеличением количества процессоров в k раз эффективность предложенного варианта метода возрастает в k раз по сравнению с эффективностью обычного блочного метода для всех рассмотренных законов распределения вероятностей обращения к записям за исключением "бинарного". uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України Фізико-математичне моделювання та інформаційні технології Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність One of the version of m-parallel block record browsing method and its effectiveness Вариант метода m-параллельного блочного поиска записей и его эффективность Article published earlier |
| spellingShingle | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність Лісовець, В. Цегелик, Г. |
| title | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність |
| title_alt | One of the version of m-parallel block record browsing method and its effectiveness Вариант метода m-параллельного блочного поиска записей и его эффективность |
| title_full | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність |
| title_fullStr | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність |
| title_full_unstemmed | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність |
| title_short | Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність |
| title_sort | один із варіантів методу m-паралельного блочного пошуку записів і його ефективність |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/21875 |
| work_keys_str_mv | AT lísovecʹv odinízvaríantívmetodumparalelʹnogobločnogopošukuzapisívíiogoefektivnístʹ AT cegelikg odinízvaríantívmetodumparalelʹnogobločnogopošukuzapisívíiogoefektivnístʹ AT lísovecʹv oneoftheversionofmparallelblockrecordbrowsingmethodanditseffectiveness AT cegelikg oneoftheversionofmparallelblockrecordbrowsingmethodanditseffectiveness AT lísovecʹv variantmetodamparallelʹnogobločnogopoiskazapiseiiegoéffektivnostʹ AT cegelikg variantmetodamparallelʹnogobločnogopoiskazapiseiiegoéffektivnostʹ |