Моделирование и анализ иерархических многопроцессорных систем баз данных
Диссертация
В диссертационной работе были рассмотрены вопросы, связанные с моделированием и анализом иерархических многопроцессорных систем баз данных. Исследованы современные подходы по организации моделей параллельного вычисления. Проведен обзор наиболее популярных на сегодняшний день моделей многопроцессорных систем с общей памятью (RAM, PRAM, YPRAM, HPRAM), моделей с распределенной памятью (BSP, LogP… Читать ещё >
Содержание
- Глава 1. Обработка транзакций в многопроцессорных иерархиях
- 1. 1. Многопроцессорные иерархии
- 1. 2. Организация параллельной обработки запросов
- 1. 3. Обзор моделей многопроцессорных систем
- 1. 3. 1. Аппаратно-архитектурные модели
- 1. 3. 2. Классификация моделей параллельных вычислений
- 1. 3. 3. Параллельные вычислительные модели с общей памятью
- 1. 3. 4. Параллельные вычислительные модели с распределенной памятью
- 1. 3. 5. Параллельные вычислительные модели с иерархией памяти
- 1. 4. Выводы по главе 1
- Глава 2. Модель мультипроцессоров баз данных
- 2. 1. Требования к модели
- 2. 1. 1. Специфика
- 2. 1. Требования к модели
- 2. 1. 2. Иерархическая структура соединительной сети
- 2. 1. 3. Дисковый ввод/вывод
- 2. 1. 4. Фрагментный параллелизм
- 2. 1. 5. Передача сообщений по соединительной сети
- 2. 1. 6. Оценка стоимости запросов
- 2. 1. 7. Специфика реляционной модели данных
- 2. 1. 8. Параллельные транзакции
- 2. 1. 9. Межтранзакционный параллелизм
- 2. 2. Формальное описание модели
- 2. 2. 1. Базовые определения
- 2. 2. 2. Модель аппаратной платформы
- 2. 2. 3. Модель операционной среды
- 2. 2. 4. Стоимостная модель
- 2. 2. 5. Модель транзакций
- 2. 3. Выводы по главе 2
- 3. 1. Модель вариантов использования эмулятора ЭМБ
- 3. 2. Архитектура эмулятора БМ
- 3. 3. Принципы работы эмулятора БМЭ
- 3. 4. Язык описания конфигураций
- 3. 5. Выводы по главе 3
- 4. 1. Параметры вычислительных экспериментов
- 4. 2. Подтверждение адекватности модели БММ
- 4. 3. Моделирование 8МР-узлов
- 4. 4. Влияние интерконнекта и дисков на масштабирование
- 4. 5. Оптимизация стоимости расширения системы
- 4. 6. Выводы по главе 4
Список литературы
- Буч Г., Рамбо Д., Якобсон И. Язык UML. Руководство пользователя. 2-е изд. М.: ДМК Пресс, 2007. 496 с.
- Витковский В.В. и др. Проект Российской виртуальной обсерватории. // Научный сервис в сети Интернет: Труды Всероссийск. науч. конф. (2328 сентября 2002 г., г. Новороссийск). М.: Изд-во МГУ. 2002.
- Воеводин Вл.В. Решение больших задач в распределенных вычислительных средах. //Автоматика и Телемеханика. 2007, No. 5, С. 324−5.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
- Вычислительный кластер «СКИФ Урал». URL: http://supercomputer.susu.ru/computers/ckifural/index.html (дата обращения: 08.11.2009).
- Девитт Д., ГрэйД. Параллельные системы баз данных: будущее высокоэффективных систем баз данных // СУБД. 1995. № 2. С. 8−31.
- Демичев А.П., Ильин В. А., Крюков А.ТТ. Введение в грид-технологии. Препринт НИИЯФ МГУ 2007−11/832, 2007. 87 с.
- КнутД.Э. Искусство программирования, т. 1. Основные алгоритмы, 3-е изд. М.: Издательский дом «Вильяме», 2000. 720 с.
- Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. 800 с.
- Когаловский М.Р., Новиков Б. А. Электронные библиотеки новый класс информационных систем // Программирование, 2000. № 3. С. 3−8.
- Корлеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.
- Костенецкий П. С. Разработка эмулятора виртуальных мультипроцессоров баз данных // Параллельные вычислительные технологии: Труды международной науч. конф. (29 февраля 2 февраля 2007 г., г. Челябинск). Челябинск.: Изд-во ЮУрГУ. 2007. С. 285.
- Костенецкий П. С., Соколинский Л. Б. Свидетельство Роспатента об официальной регистрации программы для ЭВМ «Эмулятор параллельных систем баз данных» № 2 009 616 225 от 11.11.2009.
- Костенецкий П.С., Лепихов A.B., Соколинский Л. Б. Технологии параллельных систем баз данных для иерархических многопроцессорных сред // Автоматика и телемеханика. 2007. No. 5. С. 112−125.
- Куссулъ H.H., Шелестов А.Ю. Grid-системы для задач исследования Земли. Архитектура, модели и технологи. Киев: «Наукова думка», 2008. 452 с.
- Кузнецов С.Д. SQL. Язык реляционных баз данных. -М.: Майор, 2001. -192 с.
- Кузнецов С.Д. Большие хлопоты с большими объемами данных // Открытые системы. СУБД. 2008. № 4. С. 20−27.
- Кузьминский M. Nehalem: микроархитектура и производительность // Открытые системы. 2009. № 8. С. 10−14.
- Лепихов A.B., Соколинский Л. Б. Обработка запросов в СУБД для кластерных систем // Программирование. 2010 (в печати).
- Лескин A.A., Мальцев П. А., Спиридонов A.M. Сети Петри в моделировании и управлении. JI.: Наука, 1989. 133 с.
- Никулина И.О., Старцева Е. Б. Применение аппарата сетей Петри для моделирования экономических процессов: Метод, указания./ Уфимск. гос. авиац. техн. ун-т- Уфа, 2001. 32 с.
- Омаров О.М. Моделирование параллельных алгоритмов с использованием сетей Петри // Искусственный интеллект. 2005. № 4. С. 240−244.
- Параллельная СУБД Омега для многопроцессорных иерархий Сайт проекта. URL: http://fireforge.net/projects/omega/ (дата обращения: 24.10.2009).
- Соколинский Л.Б. Обзор архитектур параллельных систем баз данных // Программирование. 2004. № 6. С. 49−63.
- Соколинский Л.Б. Организация параллельного выполнения запросов в многопроцессорной машине баз дан-ных с иерархической архитектурой // Программирование. 2001. No. 6. С. 13−29.
- Стивене У.P. UNIX: взаимодействие процессов. СПб.: Мастер-класс, 2003. 576 с.
- Федотов И.Е. Некоторые приемы параллельного программирования / ГОУ ВПО «Московский государственный институт радиотехники, электроники и автоматики» М., 2008. 188 с.
- Хаманн Ф. Отказоустойчивая операционная система Tandem NonStop Kernel // Открытые системы. 1997. № 3. С. 32−36.
- Цветков В.Я. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998. 288 с.
- Aggarwal A., et al. A model for hierarchical memory // Proceedings of the 19th Annual ACM Symp. on Theory of Computing. ACM. 1987, P. 305 314.
- Aggarwal A., et al. Hierarchical Memory with Block Transfer // Proceedings of the 28th IEEE Symp. On Foundations of Computer Science. USA. 1987. P. 204−216.
- Agrawal R., Ailamaki A., Bernstein P.A. et al. The Claremont Report on Database Research // Communications of the ACM. 2009. Vol. 52, No. 6.1. P. 56−65.
- Agrawal R., Srikant R., Xu Y. Database technologies for electronic commerce // 28th international conference on Very Large Data Bases, Hong Kong, China, August 20 23, 2002. Proceedings. VLDB Endowment, 2002. P. 1055- 1058.
- Alfawair M., Aldabbas., et al. Grid Evolution // IEEE International Conference on Computer Engineering & Systems, Cairo, Egypt, 27−29 November, 2007, Proceedings. IEEE Computer Society. 2007. P. 158−163.
- Alpern B, et al. The uniform memory hierarchy model of computation // Al-gorithmica. 1994. Vol. 12 No. 2/3 P. 72−109.
- Ballinger C., Fryer R. Born To Be Parallel: Why Parallel Origins Give Te-radata an Enduring Performance Edge // IEEE Data Engineering Bulletin. 1997. Vol. 20, No. 2. P. 3−12.
- Bar-Noy A., Kipnis S. Designing broadcasting algorithms in the Postal model for message passing systems // Proceedings of the SPAA'92, USA. 1992. P. 13−22.
- Bell G., Gray J. What’s next in high-performance computing // Communications of. ACM. 2002. Vol. 45, No. 2, P. 91−95.
- Bell G., Gray J., Szalay A.S. Petascale Computational Systems // IEEE Computer. 2006. Vol. 39, No. 1. P. 110−112.
- Bilardi G. Models for parallel and hierarchical computation // Proceedings of the 4th international conference on Computing frontiers. ACM: New York, 2007. P. 95−96.
- Borkar S. Y. et al. Platform 2015: Intel processor and platform evolution for the next decade: URL: http://www.cs.helsmki.fl/u/kerola/rio/papers/borkar2015.pdf (дата обращения: 08.11.2009). 2005.
- Bosque J.L., Pastor L. A Parallel Computational Model for Heterogeneous Clusters // IEEE Transactions on Parallel and Distributed Systems. 2006. Vol. 17, No. 12. P. 1390−1400.
- Cameron K. W., et al. Lognp and Log3p: accurate analytical model of point-to-point communication in distributed systems // IEEE Transactions on Computers, 2007. Vol. 56 No. 3. P. 314−327.
- Cameron K. W., Sun X.H. Quantifying locality effect in data access delay: memory LogP // Proceedings of the 2003 IEEE International Parallel and Distributed Processing Symposium, France. 2003.
- Cavin R., Hutchby J.A., et al. Emerging Research Architectures // Computer. 2008. Vol. 41, No. 5. P. 33−37.
- Cha H., Lee D. H-BSP: A Hierarchical BSP Computation Model // The Journal of Supercomputing. 2001. Vol. 18, No. 2. P. 179−200.
- Chen H., Decker J., Bierbaum N. Future Networking for Scalable I/O // 24th IASTED international Conference on Parallel and Distributed Computing and Networks, Innsbruck, Austria, February 14—16, 2006, Proceedings, ACTA Press, 2006. P. 128−135.
- Cole R., et al. The APRAM: incorporating asynchrony into the PRAM model // Proceedings of the 1st Annual ACM SPAA'89. USA. 1989. P. 169−178.
- Cook S, Reckhow R. Time Bounded Random Access Computers // Journal of Computer and Systems Sciences. 1973. No. 7. P. 354−375.
- Cormen T.H., Goodrich M.T. A bridging model for parallel computation, communication, and I/O // ACM Computing Surveys. 1996. Vol. 28, No.4.
- Culler D., et al. LogP: A Practical Model of Parallel Computation. Commun. ACM, 1996. Vol. 39, No. 11. P. 78−85.
- Culler D, et al. LogP: towards a realistic model of parallel computation // Proceedings of PPoPP'93 USA. 1993. P. 1−12.
- Dasgupta S. A Hierarchical Taxonomic System for Computer Architectures // IEEE Computer. 1990. Vol. 23, No. 3. P. 64−74.
- De La Torre P., Kruskal C.P. Towards a single model of efficient computation in real parallel computers // Future Generation Computer Systems, Elsevier Science Publishers. 1992, Vol. 8, No. 4. P. 395−408.
- DeWitt D.J., Gray J. Parallel Database Systems: The Future of HighPerformance Database Systems // Communications of the ACM. 1992. Vol. 35, No. 6. P. 85−98.
- Englert S., Glasstone R., Hasan W. Parallelism and its Price: A Case Study of NonStop SQL/MP // ACM SIGMOD Record. 1995. Vol. 24, No. 4. P. 61−71.
- Flynn M.J. Computer Organization and Architecture // Operating Systems, An Advanced Course. Springer, 1978 (Lecture Notes in Computer Science- Vol. 60). P. 17−98.
- Flynn M.J. Very High Speed Computing Systems // Proc. IEEE. 1966. Vol. 54. P. 1901−1909.
- Flynn M.J., RuddK. W. Parallel architectures // ACM Computing Surveys. 1996. Vol. 28, No. 1. P. 67−70.
- Fortune S., Wyllie J, C. Parallelism in random access computers // Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. USA. 1978. P. 114−118
- Foster I. Т., Grossman R.L. Blueprint for the future of high-performance networking: Data integration in a bandwidth-rich world // Communications of the ACM. 2003. Vol. 46, No. 11. P. 50−57.
- Foster I. Т., Kesselman C., Nick J., Tuecke S. The Physiology of the Grid: An Open Grid Service Architecture for Distributed Systems Integration. URL: http://www.globus.org/ogsa (дата обращения: 08.11.2009). 2002.
- Foster I. What is the Grid? A Three Point Checklist. URL: http://www.gridtoday.com/02/0722/100 136.html (дата обращения: 08.11.2009). 2002.
- Frew J., Dozier J. Data Management for Earth System Science // ACM SIGMOD Record. 1997. Vol. 26, No. 1. P. 27−31.
- Gibbons P., et al. The QRQW PRAM: accounting for contention in parallel algorithms. Proceedings of the 5th annual ACM-SIAM SODA'94, USA. 1994. P. 638−648.
- Girone M. CERN Database Services for the LHC Computing Grid // International Conference on Computing in High Energy and Nuclear Physics (CHEP'07). Journal of Physics: Conference Series. Vol.119. 2008.
- Goldschlager L M. A Universal interconnection pattern for parallel computers // Journal of the ACM. 1982, 29(4). P. 1073−1086.
- Gray J., et al. Scientific Data Management in the Coming Decade // SIG-MOD Record. 2005. Vol. 34, No. 4. P. 34−41.
- Handbook of Parallel Computing: Models, Algorithms and Applications. Chapman & Hall/CRC Press, 2007. 1224 p.
- Heywood T., Ranka S. A practical hierarchical model of parallel computation. 1. The model. // Journal of Parallel and Distributed Computing. 1992. Vol. 16. P. 212−232.
- Hill J., McColl B., Stefanescu D.C. et al. BSPlib: The BSP programming library//Parallel Computing, Vol. 24. 1998. P. 1947−1980.
- Hill J., Crumpton P.I., Burgess D.A. The theory, practice, and a tool for BSP performance prediction // EuroPar'96, August 1996. Springer-Verlag, 1996. P. 697−705.
- Hill J., Jarvis S., Siniolakis C., et al. Analysing an SQL application with a BSPlib call-graph profiling tool // EuroPar'98, LNCS, Springer-Verlag, September 1998. Springer Berlin. 1998. P. 157−164.
- JaJa J.F., Kwan W.R. The block distributed memory model // IEEE Transaction on Distributed and Parallel Systems. 1996. Vol. 7, No. 8. P. 830−840.
- Kalakota R., Whinston A. Readings in Electronic Commerce. Addison-Wesley, 1997. 340 p.
- Kim C. Future Memory Technology Trends and Challenges // 7th international Symposium on Quality Electronic Design, March 27−29, 2006, proceedings. IEEE Computer Society. P. 513.
- Kostenetskii P. S., Lepikhov A. V., Sokolinskii L.B. Technologies of parallel database systems for hierarchical multiprocessor environments // Automation and Remote Control. 2007. Vol. 68, No. 5. P. 847−859.
- Leiserson C., Maggs B. Communication efficient parallel algorithms for distributed random access computers // Algorithmica. 1988. Vol. 3. P. 53−77.
- Li Z. Y., et al. Models and resource metrics for parallel and distributed computation // Proceedings of 28th Hawaii International Conference on System Sciences. USA. 1995. Vol. 2. P. 51−60.
- Lu G. Multimedia Database Management System. Artech House, 1999.
- Maggs B M, et al. Models of Parallel Computation: A Survey and Synthesis // Proceedings of 28th Hawaii Int. Conf. on System Sciences. Wailea, USA. 1995. P. 61−70.
- Maertens H. A Classification of Skew Effects in Parallel Database Systems // 7th International Euro-Par Conference, August 28−31, 2001, Manchester, UK, Proceedings. Springer. 2001. Vol. 2150. P.291−300.
- McColl W.F. General purpose parallel computing. Lectures on Parallel Computation // Cambridge University Press. 1993. P. 337−391.
- Meuer H.W. The TOP500 Project: Looking Back Over 15 Years of Supercomputing Experience. Informatik Spektrum 2008. Vol. 31 No. 3 P. 203 222.
- Norman M. G., Zurek T., Thanisch P. Much Ado About Shared-Nothing // ACM SIGMOD Record. 1996. Vol. 25, No. 3. P. 16−21.
- Parkhurst J., Darringer J., Grundmann B. From single core to multi-core: preparing for a new exponential // IEEE/ACM international Conference on Computer-Aided Design, San Jose, California, November 05−09, 2006. ACM, 2006. P. 67−72.
- Peterson J.L. Petri Net Theory and the Modeling of Systems, Englewood Cliffs, Prentice Hall, 1981. 290 p.
- Pfister G. Sizing Up Parallel Architectures // Database Programming Design OnLine. URL: http://www.dbpd.com (дата обращения: 08.11.2009). 1998. Vol. 11, No. 5.
- Rahm E. Parallel Query Processing in Shared Disk Database Systems // ACM SIGMOD Record. 1993. Vol. 22, No. 4. P. 32−37.
- Raman V., Han W., Narang I. Parallel Querying with Non-Dedicated Computers // Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 September 2, 2005. ACM. 2005. P. 61−72.
- ReedD.A. Grids, the TeraGrid, and Beyond // Computer. 2003. Vol. 36, No. l.P. 62−68.
- Roberts L. G. Beyond Moore’s Law: Internet Growth Trends // Computer 2000. Vol. 33, No. 1 P. 117−119.
- Rumbaugh J. Getting Started Using Use Cases to Capture Requirements / J. Rumbaugh // Journal of Object Oriented Programming. 1994. Vol. 7, № 5. P. 8−12.
- Schoene R., Nagel W.E., Oiger S Analyzing Cache Bandwidth on the Intel 2 Core Architecture // Parallel Computing: Architectures, Algorithms and Applications. 2007. Vol. 38. P. 365−372.
- Scherger M., Baker J., Potter J. Using UML to Describe the BSP Model of Parallel Computation // Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications. CSREA Press. 2002. Vol. 2. P. 578−583.
- Selic B. UML 2: a model-driven development tool // IBM Syst. J. 2006. Vol. 45, № 3. P. 607−620.
- Shiers J. The Worldwide LHC Computing Grid (worldwide LCG) // Computer Physics Communications. 2007. Vol. 177 No. 1−2. P. 219−223.
- Skillicorn D.B., Talia D. Models and languages for parallel computation // ACM Computing Surveys. 1998. Vol. 30, No. 2. P. 123−169.
- Snyder L. Type architectures, shared memory, and the corollary of modest potential // Annu. Review of Computer Science, 1986, Vol. 1. P. 289−317.
- Stonebraker M. The case for shared nothing // Database Engineering Bulletin. 1986. Vol. 9, No. 1. P. 4−9.
- Szalay A.S. The Sloan Digital Sky Survey and beyond // SIGMOD Record. -2008. Vol. 37, No. 2. P. 61−66.
- Szalay A.S., et al. The SDSS SkyServer Public Access to the Sloan Digital Sky Server Data // Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, June 3−6, 2002. ACM Press. 2002.
- Szalay A.S., Gray J., Vandenberg J. Petabyte Scale Data Mining: Dream or Reality? // Technical Report MSR-TR-2002−84. Microsoft Research. 2002.
- Szalay A., Gray J. The World-Wide Telescope // Science. 2001. Vol. 293, P. 2037−2040.
- Tsvetovat M., Diesner J., Carley, K.M. Netlntel: a database for manipulation of rich social network data. Technical Report CMU-ISRI-04−135. Carnegie Mellon University, School of Computer Science, Institute for Software Research International. 2005.
- ValiantL.G. A bridging model for parallel computation. Communication of the ACM. 1990. Vol. 33, No. 8. P. 103−111.
- Valiant L.G. General Purpose Parallel Architectures / Handbook of theoretical computer science (Vol. A): algorithms and complexity. Cambridge, MA, USA. MIT Press. 1991. P. 943−973.
- Vangal S. An 80-Tile 1.28TFLOPS Network-on-Chip in 65nm CMOS // Solid-State circuits conference, February 11−15,2007. P. 98−105.
- W3C. Extensible Markup Language (XML) 1.0 (Fifth Edition). World Wide Web Consortium. 2006. URL: http://www.w3.org/TR/2006/REC-xml-20 060 816 (дата обращения: 08.11.2009).
- Wen J., Li Q., Ma W., Zhang H. A multi-paradigm querying approach for a generic multimedia database management system // ACM SIGMOD Record Volume 32, Issue 1, March 2003. Proceedings. ACM, New York, NY, USA. P. 26−34.
- Williams M.H., Zhou S. Data Placement in Parallel Database Systems // Parallel database techniques. IEEE Computer society, 1998. P. 203−218.
- XiangH., Baker M., Nichol R. Experiences Mirroring and Distributing the Sloan Digital Sky Survey // International Conference on Grid and Cooperative Computing Workshops, Hunan, China, 21−23 October, 2006, IEEE Computer Society, 2006. P. 518−521.
- Zhang Y., Chen G., Sun G, Miao Q. Models of parallel computation: a survey and classification // Frontiers of Computer Science in China. 2007. Vol. 1, No. 2. P. 156−165.
- Zhang Y.Q. DRAM (h): a parallel computation model for high performance numerical computing // Chinese Journal of Computers. 2003. Vol. 26, No. 12. P. 1660−1670.
- Zhang Y.Q. Performance optimizations on parallel numerical software package and study on memory complexity. Dissertation of Doctoral Degree Beijing, P.R. China / Institute of Software, Chinese Academy of Sciences, 2000.