Разработка и исследование алгоритмов управления очередями заданий при организации параллельных вычислений в кластерных вычислительных системах
Диссертация
Третья глава посвящена разработке алгоритмов управления очередями заданий для кластерных систем. Приводятся описания структурных схем алгоритма управления порядком запуска заданий и алгоритма распределения ресурсов между процессами. Кроме этого, посвящается разработке параллельного алгоритма и структурной схемы нахождения минимального остовного дерева, на основе метода Борувки, для проверки… Читать ещё >
Список литературы
- Norros I. A storage model with self-similar input /1. Norros //Queueing Systems AndTheir Applications. 1994. -N16. -P.369−387.
- Kelly P.P. Analysis in Queueing Systems: Brownian models, cut constraints and resource pooling/ Kelly P.P. // Queueing Systems., 1993. N13. — P. 47−86.
- Limic V. On the behavior of LIFO preemptive resume queues in Heavytraffic/ V. Limic // Elect. Comm. in Probab. 1999. — N4. -P. 13−27.
- Kamp A. v., S. Schuster. Metatool 5.0: fast and flexible elementary modes analysis/A. v. Kamp, S. Schuster//Bioinformatics. 2006. -N22. -P. 1930−1931.
- Chen L. Parallel simulation by multi-instruction, longest-path Algorithms/ L. Chen // Queueing Systems. 1997. -N 27. -P. 37−54.
- Karatza H. D. A Simulation Model of Backfilling and I/O Scheduling in a Partitionable Parallel System/ Karatza H. D. //Proceedings of Winter Simulation Conference ACM, IEEE, SCS, Orlando, Florida, December, Orlando , — 2000. -P. 496−505.
- Flynn M. Some Computer Organisations and Their Effectiveness/ M. Flynn // IEEE Transactions on Computers. -1972. -N 9. -P.948−960.
- Wang P., Dual-Direction Backfilling Algorithm for Job Scheduling/P. Wang, Xu Liu, Dan Meng, Jianfeng Zhan, Bibo Tu //HPC Asia conference. Kaohsiung, Taiwan. -2009. P.88−102.
- Ward W., Scheduling Jobs on Parallel Systems Using a Relaxed Backfill Strategy/ W. Ward, L. Carrie //8th International Workshop on Job Scheduling Strategies for Parallel Processing, Spinger-Verlag. -2002. LNCS 2537. — P.88−102.
- Hockney R. Parallel Computers: Architecture and Performance/ RHockney // Proc. Of Int. Conf. Parallel Computing. 1986. -N 85. — P.33−69.
- Lifka D. The ANL/IBM SP scheduling system. In Job Scheduling Strategies for Parallel Processing / D. Lifka //Springer-Verlag, Lect. Notes Comput. -1995.-N. 949.-P. 295−303.
- Mu’alem A. W Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling/ A. W. Mu’alem, D. G. Feitelson // IEEE Trans. Parallel Distributed Syst.-2001.-N12(6). -P. 529−543.
- Maui scheduler. Cluster Resources Электронный pecypc.-2011. Режим доступа: http://www.supercluster.org/maui//, свободный.
- Streit A. On Job Scheduling for HPC-Clusters and the Scheduler. /А. Streit //TR-101, PC2 Paderborn Center for Parallel Computing, PaderbornUniversity. -2001. Электронный ресурс. — Режим доступа http://www.fz-iuelich.de/isc/vsgc/pub/strcit2001-QJS.pdf
- Wiseman Y. Paired Gang Scheduling/ Y. Wiseman, D.G. Feitelson // Proc. Jerusalem Parallel Distributed Processing Symp., Nov. Jerusalem. -2001. -P. 218−222.
- B. B Zhou .: Gang Scheduling with a Queue for Large Jobs/ Zhou B. B., Brent R. P.// IEEE International Parallel and Distributed ProcessingSymposium. -(2001).-N12.-P. 225−233.
- Frachtenberg E. J.: Flexible CoScheduling: Mitigating Load Imbalance and Improvi Utilization of Heterogeneous Resources/ Frachtenberg E., Feitelson D.G. // 17th International Parallel andDistributed Processing Symposium. -2003.-39: 345−456.
- Hockney R. Classification and Evaluation of Parallel Computer Systems /Hockney R.//lecture Notes in Computer Science. 1987.- N 295. — P. 13−25.
- Chapin S.J. et all: Benchmarks and Standards for the Evaluation of Parallel Job Schedulers/ S.J. Chapin // Job Scheduling Strategiesfor Parallel Processing. -1999.-V.1234.-P. 67−90.
- Goes L. F.: Proposal and Development of Reconfigurable Parallel Job Scheduling Algorithm/ L. F. Goes, W. Martins// Master' s Thesis. Belo Horizonte, Brazil (in Portuguese). 2004. -V.29.P. 345−456.
- Low, Y.H. et al., Survey of Languages and Runtime Libraries for Parallel Discrete-Event Simulation//IEEEComputer Simulation. -1999.-N3. -P. 170−186.
- Anderson, Cobb E. An experiment in public-resource computing / Anderson, Cobb E. // Comm. of the ACM. -2002. V. 45, No. 11. — P. 56−61.
- Zhou B. B. An Efficient Resource Allocation Scheme for Gang Scheduling/ B.
- B. Zhou, P. Mackerras, Johnson C. W., Walsh, D.//lst IEEE Computer Society International Workshop on Cluster Computing. Toqi 1999. — P. 18−194.
- Martin R.D. Robust estimation via stochastic approximation/ R.D. Martin &
- Анализ алгоритмов обслуживания очередей в сетях с поддержкой «Качества обслуживания» (QoS) / Е. Б. Фишман // Качество. Инновации. Образование. -2006. -№ 6. С.63- 71.
- Федодеев Д., Алгоритмы управления очередями / Д. Федодеев // Журнал сетевых решений/LAN. 2007. — Т. 13 (137). — С.26−31.
- Климов, Г. П. Приоритетные системы обслуживания с ориентацией/ Г. П. Климов, Г. К. Мишкой.-М.: МГУ, 1979.-222 с.
- Столлингс В. Современные компьютерные сети: Энциклопедия. — 2-е изд- СПб.: Питер. — 2003. — 782 с.
- Таненбаум Э. Компьютерные сети. Классика computer science. 4-е / Э. Таненбаум. -4-е изд. -СПБ. Литер. 2008. — 992 с.
- Меликов А.З. Приоритетное обслуживание в узлах коммутации сетей АТМ / А. З. Меликов, В. Ш. Фейзиев // Автоматика и вычислительная техника. -Харьков, 2005. Т.З. — С.79.
- Kroner Н. Priority management in ATM switching nodes / H. Kroner, G. Hebuterne, P. Boyer, A. Gravey // IEEE J. Select. Areas Commun. 1991. -Vol.9, No.3.-P.418−427.
- Антонов А. В. Оценка эффективности параллельных алгоритмов/ А. В. Антонов // Антикризисное управление в России в современных условиях: материалы VI Всерос. науч.-практ. Молодеж. конф. М.: Изд-во МГТУ им. Н. Э. Баумана, 2004. — С. 21- 22.
- Гугель Ю.В. Характеристики параметров «Качество обслуживания» опорной инфраструктуры научно-образовательной сети / Ю. В. Гугель // Информатизация образования и науки. 2009. — Вып. 4. — С. 66−75.
- Вегешна Ш. Качество обслуживания в сетях IP/ Ш. Вегешна. М.: Изд-во. Вильяме, 2003. -368с.
- Коваленко В.Н. Методы и алгоритмы управления параллельными заданиями в гриде с ресурсами в форме кластеров/ В. Н. Коваленко, Д. А. Семячкин // Вестник Южного научного центра РАН. -2008. № 3(4). -С. 23−34.
- Таненбаум Э. Компьютерные сети. Классика computer science/ Э. Таненбаум. 3-е изд. — СПБ.: Питер, 2002. — 829 с.
- Аль-хулайди А. А. Распределенные вычисления (Кластерные вычисления) с использованием пакета параллельного программирования МР1/ А. А. Аль-хулайди //Современные наукоемкие технологии. (Электронный журнал). -2010.-№ 4-С. 82−83.
- Аль-хулайди A.A. Разбиение кластерного пакета MPI/MPICH на классыфункций / А. А. Аль-хулайди // Российская Академия Естествознания
- Научный электронный архив академии естествознания (Свидетельства от153
- Кутепов В.П. Организация параллельных вычислений на системах / В. П. Кутепов. М.: Изд-во МЭИ, 1988. — 64 с.
- Ластовецкий A.JI. Технологии параллельного программирования шрС Электронный ресурс. -Режим доступа: http://vvww.parallel.m/techympc/mpC-rus.html, свободный.
- Johnston, W. Realtime Widely Distributed Instrumentation Systems. In Foster, I. and Kesselman, C. eds. //The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann. -1999. -P. 75−103.
- Nick J.M. S/390 Cluster Technology: Parallel Sysplex/ J. M Nick, B.B. Moore //IBM Systems Journal. -1997. -36 (2). -P. 172−201.
- Hockney R. Parallel Computers: Architecture and Performance/ R. Hockney // Proc. of Int. Conf. Parallel Computing'85. 1986. -P.33−69.
- Livny M. High-Throughput Resource Management/ M. Livny, C. Kesselman //The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann. -1999.-P. 311−337.
- Casanova H. A Network Server for Solving Computational Science Problems./ H. Casanova, J. Dongarra // International Journal of Supercomputer Applications and High Performance Computing. 1997. -N.ll (3). -P. 212 223.
- Foster I. Globus: A Metacomputing Infrastructure Toolkit /1. Foster., Kesselman // Intl J. Supercomputer Applications.-1997.-N.11.-P.115−128.
- Robin Calkin. Portable programming with the parmacs message-passing library / Robin Calkin, Rolf Hempel, Hans-Christian Hoppe, Peter Wypior//Parallel Computing. -1994. 20(4). -P.615−632.
- Maui scheduler: Электронный ресурс. Режим доступа: http://www.supercluster.org/maui Last Modified on 09/06/2003, last accessed in April 2009, свободный.
- Foster I. Software Infrastructure for the I-WAY High Performance Distributed Computing Experiment /1. Foster, J. Geisler, W. Nickless, W. Smith// Proc. 5th IEEE Symposium on High Performance Distributed Computing. 1997. -P. 562−571.
- Владимиров Д. Кластерная система Condor/ Д. Владимиров // Открытые системы — 2000. -№ 7−8. -С.20−26.
- Ahmar Abbas. Grid Computing/ Ahmar Abbas //Charles River Media. 2004. -P.110−117.
- Michael J. Brim How to install an OSCAR cluster / J. Brim Michael // The Open Cluster Group. -2001 Электронный ресурс. Режим доступа: http://www.csm.ornl.gov/oscar/papers.html, свободный.
- Joseph D. Sloan, High Performance Linux Clusters With Oscar, Rocks, Open Mosix & Mpi/ D. Sloan Joseph // Fast results on terabytes of data. 2004. -P.368.
- Robert L. Grossman, Compute and storage clouds using wide area high performance networks/ Robert L. Grossman, Yunhong Gu, Michal Sabala, Wanzhi Zhang //Future Generation Сотр. Syst. 2009. -N.25(2). -P. 179−183.
- Wunderlich, J.T. Functional verification of SMP, MPP, and vector-register supercomputers through controlled randomness/ J.T. Wunderlich//Computer Engineering Program. -2003. -P.l 17−122.
- Buyya Rajkumar Buyya. High Performance Cluster Computing: Architecturesand Systems// Prentice Hall PTR. -NJ, (USA), 1999. V. 1. -P.227−233.
- Al-khulaidi Abdulmajed Ahmed Parallel computing problems while using MPI / MPICH cluster package// Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симпозиума/-ДГТУ-Ростов н/Д: Издательский центр ДГТУ, 2011.
- Blumofe R. Scheduling multithreaded computations by work stealing/ R. Blumofe, C. Leiserson // 35th Annual IEEE Conf. on Foundations of Computer Science. FOCS'94. Santa Fe, (New Mexico). -1994. -P. 356−368.
- Casavant T. A taxonomy of scheduling in generalpurpose distributed computing systems/ T. Casavant, J. Kuhl // IEEE Trans. О Software Engineering. -1988. -V. 14.-No 2.-P. 141−154.
- Feitelson D.G. A Survey о Scheduling in Multiprogrammed Parallel Systems/ D.G. Feitelson // Research Report RC 19 790 (87 657). IBM T. J. Watson ResearchCenter. -1994. -P. 171.
- Streit A. On Job Scheduling for HPC-Clusters and the dynP Scheduler / A. Streit // Lect. Notes Comput. Sci Berlin, — 2001. -V. 2228. — P. 58−67.
- Brando T. J. Comparing DCE and CORBA / T. J. Brando // Technical Report MP, MITRE. -1995. -P.93−95.
- Сайт проекта TORQUE. Электронный ресурс. Режим доступа: http://www.clusterresources.com/pages/products/torque-resource-manager.php, свободный.
- Сайт проекта TORQUE Resource Manager^eKTpoHHbift ресурс.- Режим доступа: http://en.wikipedia.org/ wiki/TORQUE ResourceManager, свободный.
- Bharucha-Reid А. Т., Elements of the theory of Markov processes and their applications/ A. T. Bharucha-Reid // New York, McGraw-Hill
- Book Co. (РЖМат, 1961, 4B29 К). -I960, — XI. -1960. -N468. -P. 11−50.
- Boyer R. H. An integro-differential equation for a Markov process.
- R. H. Boyer //Industr. and Appl. Math-1959. V7, № 4. — P. 473186.
- Clarke A. B. Waiting line process of Markov type / A. B. Clarke // Ann. Math Statistics. 1956. — V. 27, № 2. — P. 452 -459.
- Udagawa K. Note on a relation between the Markov chain and the birth and death process/ K. Udagawa // J. Operat. Res. Soc. 1арап (РЖМат, 1962, 7B21). 1961. — V. 4, № 1.-P. 27−45.
- Vere-Jones D., Geometric ergodicity in denumerable Markov chains// Quart. J. Math.- 1962, — V.13, № 49. P.7−28.
- Ивченко Г. И., Коваленко И. Н. Теория массового обслуживания/ Г. И. Ивченко, В. А. Каштанов. — М.:Высш. Шк., 1982. — 256 с.
- Гнеденко Б.Б. Введение в теорию массового обслуживания/ Гнеденко Б. Б., И. Н. Коваленко. — М.: Наука, 1966.-255 с.
- Сейфулин А.И. Ситуационное моделирование полиграфических процессов:дисс. Канд. Техн. Наук/ А. И. Сейфулин. — М., 2002.
- Кофман А. Массовое обслуживание. Теория и приложения/ А. Кофман, Р. Крюон — М.:Мир, 1965. — 304 с.
- Клименок В.И. Теорема Руше в задаче нахождения стационарного распределения квазитеплицевой цепи Маркова / В. И. Клименок // Автоматика и вычислительная техника. 1998. -№ 1. — С.23−29.
- Дудин А.Н. Системы массового обслуживания с коррелированными потоками/ А. Н. Дудин, В. И. Клименок Минск: БГУ, 2000. — 175 с.
- Климов Г. П. Стохастические системы обслуживания/ Г. П. Климов М.: Наука, 1966.-244 с.
- Кормен Т. Алгоритмы: построение и анализ/ Т. Кормен, Ч. Лейзерсон, Р. РивестМ. :МЦНМО, 2001.-960с.
- Альфред Ахо Структуры данных и алгоритмы/ Ахо Альфред, Э. Джон, Д. Ульман М. — СПб — Киев: Вильяме, 2000 г. — 384 с.
- Курейчик В.М. Дискретная математика. Ч. З. Оптимизационные задачи на графах/ В. М. Курейчик. Таганрог: Изд-во ТРТУ, 1998. — 296 с.
- Кормен Т. X. Алгоритмы: построение и анализ/ Т. X. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн- 2-е изд.— М.: Вильяме, 2005. — 1296 с.
- Graham. R. L. On the history of the minimum spanning tree problem. / R. L. Graham and P. Hell. // Annals of the History of Computing. 1985. — N 7(1).-P. 43−57.
- Chung S. Parallel implementation of Boruvka’s minimum spanning tree algorithm. / S. Chung, A. Condon // Parallel Processing Symp. (IPPS'96). -1996.-P. 302−315.
- Chazelle. B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity / B. Chazelle// Journal of the ACM. 2000. -N47. — P. 10 281 047.
- David R. Karger. A randomized linear-time algorithm to find minimum spanning trees/ David R. Karger, Philip N. Klein, and Robert E. Tarjan // Journal of the ACM. -1995. N.42 (2). -P. 321−328.
- King V. A simpler minimum spanning tree verification algorithm/ V. King //Algorithmic. -1997. -18. -P. 263−270.
- Ш. Бурков В.H. Прикладные задачи теории графов / В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий Тбилиси: Мецниереба. — 1974. — 234 с.
- Алексеев А.О. Транспортная задача по критерию времени при ограниченном количестве транспортных средств/ А. О. Алексеев // Математические методы оптимизации и управления в сложных системах /-КГУ. Калинин, — 1984. — с. 60- 65.
- Математическое моделирование экономических процессов на железнодорожном транспорте / А. Б. Каплан, А. Д. Майданов, A.M. Макарочкин и др. М.: Транспорт. -1984. -256 с.
- Кузнецов Ю.Н. Математическое программирование / Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. М.: Высш. Шк, 1976. -352с.
- Высшая математика: Математическое программирование: Учеб. / A.B. Кузнецов, В. А. Сакович, Н. И. Холод. Минск.: Высш.шк., 1994. — 286 с.
- Барский А. Б. Параллельное программирование/ А. Б. Барский СПб.: Бином, 2007. — 504 с.
- Северин А. А. Исследование эффективности реализации численных методов на кластерах персональных ЭВМ/ А. А. Северин Минск, 2005.
- Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации/ В. И. Хохлюк. М., 1987. — 224с.
- Каныгин Т.П., Месхи Б. Ч., Соболь Б. В. Методы оптимизации / Г. И Каныгин., Б. Ч. Месхи, Б. В. Соболь — М.: Феникс, 2009. — 384 с.
- Аппроксимация Электронный ресурс. -Режим доступа: http://ru.wikipedia.org/wiki/AппpoкcимaцияПaдe (дата обращения 11.2.2011 г), свободный.
- Грид Электронный ресурс. http://ru.wikipedia.org/wiki/rpHa (дата обращения 23.03.2011), свободный.
- Аль-хулайди A.A. Использование метода формульного анализа масштабируемости в кластерных сетях/ A.A. Аль-хулайди // Математические методы в технике и технологиях-ММТТ-23: сб.тр. XXIII Междунар. науч. конф/ СГТУ.- Саратов, 2010. -Т.9. -С. 173−174.
- Аль-хулайди A.A. Разработка алгоритмов управления заданиями при организаций параллельных вычислений в кластерных вычислительных системах/ A.A. Аль-хулайди, Ю.О. Чернышев// Вестник ДГТУ. -2011. -Т.11,№ 5(56) С. 715 — 722.
- Аль-хулайди A.A. Разработка параллельного алгоритма нахождения оптимального решения транспортной задачи для выполнения на кластере/ A.A. Аль-хулайди, Ю. О. Чернышев // Инженерный вестник Дона .
- Электронный научно-инновационный журнал, 2011. № 2. — № гос.161регистрации421 100 096. Электронный журнал.: Режим доступа: http://ivdon.ru/magazine/latest/n2y2011/445/
- Аль-хулайди Абдулмаджид Ахмед. Реализация функций кластерного пакета MPI/MPICH / Абдулмаджид Ахмед Аль-хулайди // Российская Академия Естествознания: Научный электронный архив академии естествознания (Свидетельства от российской
- Академия Естествознания) -URL:http://econf.rae.ru/pdf/201 l/08/525.pdf
- Коваленко В.Н. Метод опережающего планирования для грид/ .Н.Коваленко, Е. И. Коваленко, Д. А. Корягин, Э. З. Любимский // Ордена Ленина институт прикладной математикой имени М. В. Келдыша. Москва. -2005.-33с.
- Al-khulaidi A. A. Algorithm development of resource allocation between processes for parallel systems/ A. A. Al-khulaidi //Современные проблемы многоуровневого образования: сб. тр. VI междунар. науч. -метод.симп. /ДГТУ- Ростов н/Д, 2011. С. 234 — 237.