Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність
Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномірного, "бінарного", Зіпфа й узагальне...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2008
|
| Назва видання: | Фізико-математичне моделювання та інформаційні технології |
| Онлайн доступ: | http://dspace.nbuv.gov.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| id |
irk-123456789-21875 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-218752011-06-20T12:04:27Z Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність Лісовець, В. Цегелик, Г. Запропоновано один із варіантів методу 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 раз по сравнению с эффективностью обычного блочного метода для всех рассмотренных законов распределения вероятностей обращения к записям за исключением "бинарного". 2008 Article Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2008. — Вип. 7. — С. 103-111. — Бібліогр.: 11 назв. — укр. 1816-1545 http://dspace.nbuv.gov.ua/handle/123456789/21875 519.68 uk Фізико-математичне моделювання та інформаційні технології Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномірного, "бінарного", Зіпфа й узагальненого, частковим випадком якого є розподіл, який наближено задовольняє правило "80-20"). За критерій ефективності прийнято математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Побудовано оптимальні схеми методу, тобто схеми, за яких математичне сподівання досягає мінімуму. Зі збільшенням кількості процесорів у k разів ефективність запропонованого варіанта методу зростає в k разів, порівняно з ефективністю звичайного блочного методу, для всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім "бінарного". |
| 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 |
2008 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/21875 |
| citation_txt |
Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність / В. Лісовець, Г. Цегелик // Фіз.-мат. моделювання та інформ. технології. — 2008. — Вип. 7. — С. 103-111. — Бібліогр.: 11 назв. — укр. |
| series |
Фізико-математичне моделювання та інформаційні технології |
| work_keys_str_mv |
AT lísovecʹv odinízvaríantívmetodumparalelʹnogobločnogopošukuzapisívíjogoefektivnístʹ AT cegelikg odinízvaríantívmetodumparalelʹnogobločnogopošukuzapisívíjogoefektivnístʹ |
| first_indexed |
2023-10-18T17:11:31Z |
| last_indexed |
2023-10-18T17:11:31Z |
| _version_ |
1796140907511152640 |