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

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2007
Автори: Лісовець, В., Цегелик, Г.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України 2007
Назва видання:Фізико-математичне моделювання та інформаційні технології
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/21117
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 5. — С. 109-118. — Бібліогр.: 4 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-21117
record_format dspace
spelling irk-123456789-211172011-06-15T12:07:25Z Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних Лісовець, В. Цегелик, Г. Запропоновано метод m-паралельного послідовного пошуку записів у файлах баз даних, орієнтований на його використання в багатопроцесорних ЕОМ, і досліджено ефективність цього методу для відомих законів розподілу ймовірностей звертання до записів. За критерій ефективності приймається математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Для цих же законів розподілу ймовірностей досліджується також ефективність використання методу m-паралельного послідовного перегляду для пошуку записів у послідовних файлах. За критерій ефективності приймається математичне сподівання загального часу, необхідного для пошуку запису у файлі. The m-parallel method of sequential search of records in a database file is proposed. The method is designed for use in multiprocessors computers. We research the effectiveness of the method for different probability distribution of record request frequency. The mathematical expectation of parallel comparisons number needed for search of a record in file is taken as a criterion of effectiveness. The method effectiveness for record searching in sequential files stored on extermal memory of multiprocessors computers is investigated as well. Предлагается метод m-параллельного последовательного поиска записей в файлах баз данных, ориентированный на его использование в многопроцессорных ЭВМ. Исследуется эффективность этого метода для известных законов распределения вероятностей обращения к записям. В качестве критерия эффективности принимается математическое ожидание количества параллельных сравнений, необходимых для поиска записи в файле. Также исследуется эффективность использования метода m-параллельного последовательного пересмотра для поиска записей в последовательных файлах, содержащихся во внешней памяти многопроцессорных ЭВМ. 2007 Article Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 5. — С. 109-118. — Бібліогр.: 4 назв. — укр. 1816-1545 http://dspace.nbuv.gov.ua/handle/123456789/21117 519.68 uk Фізико-математичне моделювання та інформаційні технології Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
description Запропоновано метод m-паралельного послідовного пошуку записів у файлах баз даних, орієнтований на його використання в багатопроцесорних ЕОМ, і досліджено ефективність цього методу для відомих законів розподілу ймовірностей звертання до записів. За критерій ефективності приймається математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Для цих же законів розподілу ймовірностей досліджується також ефективність використання методу m-паралельного послідовного перегляду для пошуку записів у послідовних файлах. За критерій ефективності приймається математичне сподівання загального часу, необхідного для пошуку запису у файлі.
format Article
author Лісовець, В.
Цегелик, Г.
spellingShingle Лісовець, В.
Цегелик, Г.
Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
Фізико-математичне моделювання та інформаційні технології
author_facet Лісовець, В.
Цегелик, Г.
author_sort Лісовець, В.
title Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
title_short Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
title_full Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
title_fullStr Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
title_full_unstemmed Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
title_sort метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних
publisher Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
publishDate 2007
url http://dspace.nbuv.gov.ua/handle/123456789/21117
citation_txt Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2007. — Вип. 5. — С. 109-118. — Бібліогр.: 4 назв. — укр.
series Фізико-математичне моделювання та інформаційні технології
work_keys_str_mv AT lísovecʹv metodmparalelʹnogoposlídovnogopereglâduzapisívtajogovikoristannâdlâpošukuínformacííuposlídovnihfajlahbazdanih
AT cegelikg metodmparalelʹnogoposlídovnogopereglâduzapisívtajogovikoristannâdlâpošukuínformacííuposlídovnihfajlahbazdanih
first_indexed 2025-07-02T21:40:15Z
last_indexed 2025-07-02T21:40:15Z
_version_ 1836572911532507136
fulltext Метод m-паралельного послідовного перегляду записів та його використання для пошуку інформації у послідовних файлах баз даних Володимир Лісовець1, Григорій Цегелик2 1 Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000, e-mail: kafmmsep@franko.lviv.ua 2 д. ф.-м. н., професор, Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000, e-mail: kafmmsep@franko.lviv.ua Запропоновано метод m-паралельного послідовного пошуку записів у файлах баз даних, орієнтований на його використання в багатопроцесорних ЕОМ, і досліджено ефектив- ність цього методу для відомих законів розподілу ймовірностей звертання до записів. За критерій ефективності приймається математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Для цих же законів розподілу ймовірнос- тей досліджується також ефективність використання методу m-паралельного послідов- ного перегляду для пошуку записів у послідовних файлах. За критерій ефективності прийма- ється математичне сподівання загального часу, необхідного для пошуку запису у файлі. Ключові слова: багатопроцесорні системи, m-паралельний пошук, бази даних. Вступ. Однією з тенденцій розвитку сучасної інформатики є створення інформа- ційно-обчислювальних систем, здатних обробляти величезні об’єми інформації в режимі реального або мінімального масштабів часу. Такі системи повинні харак- теризуватися високою надійністю й ефективністю, адже незначні збої та корот- кочасні простої системи можуть призвести до великих матеріальних втрат. Тому для реалізації таких систем не можна використати сервери зі звичайною архітектурою. Багатопроцесорні ЕОМ мають архітектуру, яка забезпечує високу надій- ність інформаційно-обчислювальних систем. Завдяки особливостям архітектури окремі вузли або елементи системи можна непомітно для користувача замінюва- ти, забезпечуючи безперервну та безвідмовну роботу навіть таких складних про- грам, як системи керування базами даних. Завдяки високій надійності та продуктивності багатопроцесорні ЕОМ ши- роко використовують для підтримки й організації великих баз даних (БД). При розв’язуванні різноманітних задач із використанням БД основний акцент перено- ситься з процедур обробки інформації на процедури організації збереження та пошуку інформації в них. Тому продуктивність обчислювальних систем, орієнто- ваних на роботу з великими БД, значною мірою визначається ефективністю ме- тодів пошуку інформації. У роботі розглядається метод m-паралельного послідовного пошуку запи- сів у файлах БД, орієнтований на його використання в багатопроцесорних ЕОМ, УДК 519.68 109 Володимир Лісовець, Григорій Цегелик Метод m-паралельного послідовного перегляду записів та його використання для пошуку ... 110 досліджується ефективність методу для різних законів розподілу ймовірностей звертання до записів (рівномірного, «бінарного», Зіпфа й узагальненого, частко- вим випадком якого є розподіл, який наближено задовольняє правило «80-20» [1-3]). За критерій ефективності приймається математичне сподівання кількості пара- лельних порівнянь, необхідних для пошуку запису у файлі. Зауважимо, що ефек- тивність звичайного методу послідовного перегляду для різних законів розподілу ймовірностей звертання до записів досліджено в [4]. Крім того, для цих же зако- нів розподілу ймовірностей звертання до записів досліджується ефективність ви- користання методу m-паралельного послідовного перегляду для пошуку записів у послідовних файлах, що містяться в зовнішній пам’яті багатопроцесорної ЕОМ. За критерій ефективності в цьому випадку приймається математичне сподівання загального часу, необхідного для пошуку запису у файлі. Дослідження ефективності методу m-паралельного послідовного перегляду для пошуку записів у послідовних файлах проведемо для рівномірного розподілу ймовірностей звертання до записів і таких законів нерівномірного розподілу ймо- вірностей: • «бінарний» розподіл 1,1, 2 1 −== Nip ii , 12 1 −= NNp , де pi — ймовірність звертання до і-го запису, N — кількість записів у файлі; • закон Зіпфа Ni iH p N i ,1,1 == , ∑ = = N k N k H 1 1 ; • узагальнений закон розподілу Ni Hi p c N ci ,1,1 )()( == , ∑ = = N k c c N k H 1 )( 1 , де с (0 < c <1) — довільний параметр. При розгляді методу m-паралельного пошуку приймаємо, що послідовний файл містить N записів, які пронумеровані послідовними натуральними числами у порядку їх розміщення у файлі. При використанні цього методу для пошуку за- писів вважаємо, що послідовний файл міститься в зовнішній пам’яті багатопро- цесорної ЕОМ. 1. Метод m-паралельного послідовного перегляду та його ефективність для різних законів розподілу ймовірностей звертання до записів Приймаємо, що до складу багатопроцесорної ЕОМ входять m процесорів, які працюють паралельно та мають спільне поле пам’яті. Пронумеруємо процесори ЕОМ натуральними числами від 1 до m. Умовно поділимо усі записи файла ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 5, 109-118 111 на блоки по m записів у кожному. Нехай N = n m — кількість записів у файлі, де n — кількість блоків. Тоді при використанні m-паралельного послідовного перегляду процес пошуку запису буде складатися з низки кроків. На першому кроці і-ий процесор переглядає значення ключа і-го запису. При цьому процес перегляду може бути успішним або неуспішним. Для визначення «успішності» всі процесори повинні обмінятися інформацією. У разі успішного перегляду процес пошуку за- вершується. Якщо перегляд неуспішний, то на другому кроці і-ий процесор пере- глядає значення ключа (m + i)-го запису і т. д. На (k + 1)-му кроці (у випадку не- успішного перегляду на k-му кроці) і-ий процесор переглядає значення ключа (km + i)-го запису. Внаслідок виконання не більше n кроків шуканий запис буде знайдено, якщо він міститься у файлі. Дослідимо ефективність цього методу для різних законів розподілу ймовір- ностей звертання до записів. Нехай pi — ймовірність звертання до і-го запису файла. Тоді математичне сподівання E кількості паралельних порівнянь, необхідних для пошуку запису у файлі, обчислюється за формулою ∑∑ = = +−= n i m j jmiipE 1 1 )1( . Запишемо явний вираз для E у випадку різних законів розподілу ймовір- ностей звертання до записів і дослідимо залежність E від зміни закону розподілу ймовірностей. 1.1. Рівномірний розподіл. Якщо розподіл імовірностей звертання до записів є рівномірним, то для E одержуємо вираз       += 1 2 1 m NE . 1.2. «Бінарний» розподіл. Нехай імовірності звертання до записів задовольняють «бінарний» розподіл. Тоді для E маємо формулу ( )N m m E −− − = 21 12 2 . Нехтуючи нескінченно малою величиною 2– N, із достатньо високою точністю можемо прийняти, що 12 2 − = m m E . Бачимо, що зі збільшенням кількості процесорів математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі, змен- шується від 2 (при m = 1) до 1. Володимир Лісовець, Григорій Цегелик Метод m-паралельного послідовного перегляду записів та його використання для пошуку ... 112 1.3. Закон Зіпфа. Нехай імовірності звертання до записів задовольняють закон Зіпфа. Тоді для E одержуємо вираз [ ])()1(1 nSHn H E mN N −+= , ∑ = = n i imm HnS 1 )( . Використовуючи апроксимацію суми Sm(n) виразом [3] 1ln 2 1)1()( CnHnnS Nm ++−≈ , де C1 = 0,5 ln 2π, із достатньо високою точністю можемо прийняти, що       −−+= 1ln 2 11 C m N m NH H E N N . 1.4. Узагальнений закон. Нехай імовірності звертання до записів задовольняють узагальненому закону розподілу. Тоді для визначення математичного сподівання E маємо формулу [ ])()1(1 )()( )( nSHn H E c m c Nc N −+= , де ∑ = = n i c im c m HnS 1 )()( )( . Використовуючи апроксимацію )()( nS c m виразом [3]       α + − − − +≈ − − c cc c N c m n nn c c c NnHnS 1 )(1 )()( )( 2 1 1 )( , де ( ) ( 1) 2( ) (2 )c c c nn H n c− −α = − − — повільно зростаюча функція, із достатньо висо- кою точністю можемо прийняти, що               α − − − − += − − c cc c Nc N n nn c c c NH H E 1 )(1 )( )( )( 2 1 1 1 . 1.5. Порівняння результатів. Залежність математичного сподівання кількості паралельних порівнянь, необхідних для пошуку запису, при різних законах роз- поділу ймовірностей звертання до записів, різній кількості процесорів і N = 106 ілюструють діаграми на рис. 1. У табл. 1 наведені значення математичного сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі, який містить N = 106 записів, для розглянутих законів розподілу ймовірностей звертання до записів і різної кількості процесорів. Бачимо, що залежність математичного сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі, від зміни закону розподілу ймовірностей звертання до записів є дуже суттєвою. Для кожного ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 5, 109-118 113 Узагальнений розподіл 5 10 20 40 50 100 Кількіcть процесорів М ат ем ат ич не с по ді ва нн я с=0,2 с=0,4 с=0,6 с=0,8 Закон Зіпфа 1 2 4 5 10 20 Кількіcть процесорів М ат ем ат ич не с по ді ва нн я Рівномірний розподіл 1 2 4 5 10 20 Кількість процесорів М ат ем ат ич не с по ді ва нн я 6·105 5·105 4·105 3·105 2·105 105 0 0 2·104 4·104 6·104 8·104 105 9·104 8·104 7·104 6·104 5·104 4·104 3·104 2·104 104 0 Рис. 1. Математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису, за різних законів розподілу ймовірностей звертання до записів і різної кількості процесорів у випадку N = 106 конкретного закону розподілу ймовірностей звертання до записів, окрім «бінар- ного», збільшення кількості процесорів у k разів приводить до зменшення мате- матичного сподівання кількості паралельних порівнянь приблизно в k разів. Для «бінарного» розподілу ймовірностей збільшення кількості процесорів майже не впливає на математичне сподівання. 2. Використання методу m-паралельного послідовного перегляду для пошуку записів у послідовних файлах Нехай a0 = b0 + d0m — час зчитування блоку записів в основну пам’ять; b0 , d0 — деякі сталі; t0 — час виконання операції m-паралельного послідовного перегляду Володимир Лісовець, Григорій Цегелик Метод m-паралельного послідовного перегляду записів та його використання для пошуку ... 114 Таблиця 1 Математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі, для різних законів розподілу ймовірностей звертання до записів і різної кількості процесорів Узагальнений m Рівномірний с=0,2 с=0,4 с=0,6 с=0,8 Зіпфа «Бінар- ний» 1 500000,5 444448,9 375064,50 286605,9 176553,8 69480,0 2,000 2 250000,5 222224,7 187532,50 143303,2 88277,1 34740,3 1,334 4 125000,5 111112,6 93766,50 71651,9 44138,8 17370,4 1,067 5 100000,5 88890,2 75013,31 57321,6 35311,2 13896,4 1,032 10 50000,5 44445,3 37506,90 28661,0 17655,8 6948,5 1,001 20 25000,5 22222,9 18753,70 14330,8 8828,2 3474,5 1,000 40 12500,5 11111,7 9377,10 7165,6 4414,3 1737,6 1,000 50 10000,5 8889,5 7501,80 5732,6 3531,6 1390,2 1,000 100 5000,5 4445,0 3751,10 2866,6 1766,1 695,4 1,000 записів в основній пам’яті; Et — математичне сподівання загального часу, необ- хідного для пошуку запису у файлі. Приймаємо, що для пошуку запису відбува- ється послідовне зчитування блоків записів в основну пам’ять та їх m-паралель- ний послідовний перегляд. Тоді математичне сподівання загального часу, необхідного для пошуку за- пису у файлі, визначається за формулою ∑∑ = = +−+= n i m j jmit iptaE 1 1 )1(00 )( . Запишемо явний вираз Et для різних законів розподілу ймовірностей звер- тання до записів і дослідимо залежність Et від зміни закону розподілу ймовірностей. 2.1. Рівномірний розподіл. Якщо розподіл імовірностей звертання до записів є рівномірним, то для Et одержуємо вираз )(1 2 1 00 ta m NEt +      += . Звідси       + +      += 0 00 0 1 2 1 d tbm m N d Et . 2.2. «Бінарний» розподіл. Нехай імовірності звертання до записів задоволь- няють «бінарний» розподіл. Тоді для Et маємо формулу ( )N m m t taE −− − + = 21 12 )(2 00 . ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 5, 109-118 115 Нехтуючи нескінченно малою величиною 2- N, із достатньо високою точністю можемо прийняти, що ( )0 02 ( ) 2 1m m tE a t= + − . Звідси       + + − = 0 00 0 12 2 d tbm d E m m t . 2.3. Закон Зіпфа. Нехай імовірності звертання до записів задовольняють закон Зіп- фа. Тоді для Et одержуємо вираз [ ] )()()1(1 00 tanSHn H E mN N t +−+= , де ∑ = = n i imm HnS 1 )( . Використовуючи апроксимацію суми Sm(n) виразом ( ) 1ln 2 11)( CnHnnS Nm ++−≈ , де C1 = 0,5 ln 2π, із достатньо високою точністю можемо прийняти, що )(ln 2 11 001 taC m N m NH H E N N t +      −−+= . Звідси       + +      −−+= 0 00 1 0 ln 2 11 d tbmC m N m NH Hd E N N t . 2.4. Узагальнений закон. Нехай імовірності звертання до записів задовольняють узагальнений закон розподілу. Тоді для Et маємо ( )( ) ( ) 0 0( ) 1 ( 1) ( )c c t mNc N E n H S n a t H  = + − +  , де ∑ = = n i c im c m HnS 1 )()( )( . Використовуючи апроксимацію )()( nS c m виразом 1 ( ) ( )( ) 1 1 ( )( ) 1 2 c c cc m N c N c nS n nH n c c n − −  − α ≈ + + − −  , де ( )( ) ( 1) 2( ) 2c c c nn H n c− −α = − − — повільно зростаюча функція, із достатньо ви- сокою точністю можемо прийняти )()( 2 1 1 1 001 )(1 )( )( ta n nn c c c NH H E c cc c Nc N t +               α − − − − += − − . Звідси Володимир Лісовець, Григорій Цегелик Метод m-паралельного послідовного перегляду записів та його використання для пошуку ... 116       + +               α − − − − += − − 0 00 1 )(1 )( )( 0 )( 2 1 1 1 d tbm n nn c c c NH Hd E c cc c Nc N t . 2.5. Порівняння результатів. Діаграми на рис. 2 ілюструють залежність функції Et /d0, яка характеризує математичне сподівання загального часу, необхідного для пошуку запису у файлі, від зміни кількості процесорів для різних законів розпо- ділу ймовірностей звертання до записів і N = 105. У табл. 2 наведені значення функції Et /d0, для згаданих вище законів роз- поділу ймовірностей звертання до записів, різної кількості процесорів, N = 105 і (b0 + t0) / d0 = 100. Бачимо, що на відміну від математичного сподівання кількості паралельних порівнянь, функція Et /d0 спадає дещо повільніше зі збільшенням кількості проце- сорів. Наприклад, для всіх розглянутих законів розподілу ймовірностей звер- тання до записів, окрім «бінарного», зі збільшенням кількості процесорів від 1 до 2 значення функції зменшується приблизно на 98 %, а вже зі збільшенням кількості процесорів від 50 до 100 (тобто теж у 2 рази) значення функції зменшується лише на 50 %. За «бінарного» закону розподілу ймовірностей, функція Et /d0 починає зростати при m > 5. Таблиця 2 Значення функції Et /d0 для різних законів розподілу ймовірностей звертання до записів і різної кількості процесорів Узагальнений m Рівномірний с=0,2 с=0,4 с=0,6 с=0,8 Зіпфа «Бінарний» 1 5050051 4489185 3790120 2908476 1847328 835436 202 2 2550051 2266842 1913848 1468662 932835 421880 136 4 1300052 1155671 975713 748756 475589 215104 111 5 1050053 933437 788087 604775 384141 173749 108 10 550055 488971 412835 316814 201245 91043 110 20 300060 266741 225213 172838 109802 49696 120 40 175070 155634 131409 100858 64089 29033 140 50 150075 133416 112652 86465 54950 24905 150 100 100100 88994 75151 57695 36689 16670 200 Висновки. У роботі запропоновано метод m-паралельного послідовного пошуку записів у послідовних файлах баз даних, який орієнтований на його використан- ня в багатопроцесорних ЕОМ. Досліджено ефективність цього методу для різних законів розподілу ймовірностей звертання до записів, а саме: рівномірного, «бі- нарного», Зіпфа й узагальненого. Досліджено також ефективність використання методу m-паралельного послідовного перегляду для пошуку записів у послідов- них файлах, що містяться в зовнішній пам’яті багатопроцесорних ЕОМ. Порівнюючи ефективність методів послідовного перегляду та m-паралель- ного послідовного перегляду, приходимо до висновку, що розпаралелювання ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології 2007, вип. 5, 109-118 117 Рис. 2. Залежність функції Et /d0 від зміни кількості процесорів для різних законів розподілу ймовірностей звертання до записів у випадку N = 105 і (b0 + t0) / d0 = 100 0 Рівномірний розподіл 5 10 20 40 50 100 Кількість процесорів 5103 ⋅ 5106 ⋅ 5109 ⋅ 51012 ⋅ Закон Зіпфа 5 10 20 40 50 100 Кількість процесорів 4105 ⋅ 41010 ⋅ 41015 ⋅ 41020 ⋅ "Бінарний" розподіл 0 50 100 150 200 250 1 2 4 5 10 20 40 50 100 Кількість процесорів Узагальнений розподіл 1 2 4 5 10 20 40 50 100 Кількість процесорів с=0,2 с=0,4 с=0,6 с=0,8 0/ dEt «Бінарний» розподіл 0/ dEt0/ dEt 0 5105 ⋅ 51010 ⋅ 51015 ⋅ 51020 ⋅ 51025 ⋅ 51030 ⋅ 51035 ⋅ 51040 ⋅ 51045 ⋅ 0/ dEt Узагальнений розподіл Кількість процесорів Кількість процесорів Володимир Лісовець, Григорій Цегелик Метод m-паралельного послідовного перегляду записів та його використання для пошуку ... 118 методу послідовного перегляду для усіх розглянутих законів розподілу ймовір- ностей звертання до записів, окрім «бінарного», підвищує ефективність лише до певних значень m = m . Для значень, які перевищують m , спостерігається незначне збільшення ефективності зі збільшенням кількості процесорів. А у ви- падку «бінарного» закону розподілу ймовірностей — збільшення кількості про- цесорів понад 5 погіршує ефективність роботи. Література [1] Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. — М.: Изд. дом «Вильямс», 2000. — 832 с. [2] Мартин Дж. Организация баз данных в вычислительных системах. — М: Мир, 1980. — 644 с. [3] Цегелик Г. Г. Организация и поиск информации в базах данных. — Львов: Вища школа, 1987. — 176 с. [4] Філяк М. І., Цегелик Г. Г., Дороцька Х. С. Порівняльний аналіз ефективності методу послідовного перегляду для різних законів розподілу ймовірностей звертання до записів // Вісник НУ «Львівська політехніка». Інформаційні системи та мережі. — 2000. — № 406. — С. 226-231. The m-Parallel Sequential Record Browsing Method and its Application for Information Search in Sequential Files of Databases Volodymyr Lisovets, Hryhoriy Tsehelyk The m-parallel method of sequential search of records in a database file is proposed. The method is designed for use in multiprocessors computers. We research the effectiveness of the method for different probability distribution of record request frequency. The mathematical expectation of parallel comparisons number needed for search of a record in file is taken as a criterion of effectiveness. The method effectiveness for record searching in sequential files stored on extermal memory of multiprocessors computers is investigated as well. Метод m-параллельного последовательного пересмотра записей и его использование для поиска информации в последовательных файлах баз данных Владимир Лисовец, Григорий Цегелик Предлагается метод m-параллельного последовательного поиска записей в файлах баз дан- ных, ориентированный на его использование в многопроцессорных ЭВМ. Исследуется эф- фективность этого метода для известных законов распределения вероятностей обраще- ния к записям. В качестве критерия эффективности принимается математическое ожи- дание количества параллельных сравнений, необходимых для поиска записи в файле. Также исследуется эффективность использования метода m-параллельного последовательного пересмотра для поиска записей в последовательных файлах, содержащихся во внешней памяти многопроцессорных ЭВМ. Отримано 25.02.07