Обзор систем параллельной обработки заявок. Часть II

Обложка

Аннотация


Данная работа является продолжением обзора методов исследования системы массовогообслуживания вида «fork-join» (в западной классификации) или системы с расщеплениемзапросов. Интерес к рассматриваемой системе объясняется широким спектром задач, которые могут быть решены с её помощью, поскольку фактически речь идёт о параллельнойобработке данных и их приложениях. К примеру, это может касаться анализа работы дисковых массивов, облачных вычислений, высокопроизводительных сервисов и даже процессакомплектации заказов на складе. Если в первой части обзора были описаны особенностипостроения данной модели и родственных ей систем, а также приведено подробное описание подхода к получению точного выражения среднего времени отклика в случае двухприборов и представлено несколько методов приближенного анализа данной характеристики в случае, когда число приборов больше двух, то во второй части обзора представленоописание других существующих методов аппроксимации среднего времени отклика. В частности, к рассматриваемым подходам приближенного анализа времени отклика относятся:матрично-геометрический метод, анализ с помощью порядковых статистик для различныхтипов распределения времени пребывания подзапросов.


А В Горбунова

Лицо (автор) для связи с редакцией.
gorbunova_av@rudn.university
Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Горбунова Анастасия Владимировна - кандидат физико математических наук, ассистент кафедры прикладной информатики и теории вероятностей РУДН

И С Зарядов

zaryadov_is@rudn.university
Российский университет дружбы народов; Институт проблем информатики Федеральный исследовательский центр «Информатика и управление» РАН ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198; ул. Вавилова, д. 44, кор. 2, Москва, Россия, 119333

Зарядов Иван Сергеевич - кандидат физико математических наук, доцент кафедры прикладной информатики и теории вероятностей РУДН, старший научный сотрудник ИПИ ФИЦ ИУ РАН

К Е Самуйлов

samuylov_ke@rudn.university
Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Самуйлов Константин Евгеньевич - профессор, доктор технических наук, заведующий кафедрой прикладной информатики и теории вероятностей РУДН

  • Обзор систем параллельной обработки заявок / А. В. Горбунова, И. С. Зарядов, К. Е. Самуйлов, Э. С. Сопин // Вестник РУДН. Серия: Математика, информатика, физика. - 2017. - Т. 25, № 4. - С. 350--362.
  • Tsimashenka I., Knottenbelt W. J. Reduction of Subtask Dispersion in Fork-Join Systems // Computer Performance Engineering. - Springer Berlin Heidelberg, 2013. - Pp. 325-336.
  • Башарин Г. П. Лекции по математической теории телетрафика. - Москва: РУДН, 2009. - 342 с.
  • Бочаров П. П., Печинкин А. В. Теория массового обслуживания. - Москва: Изд-во РУДН, 1995. - 529 с.
  • Queueing Theory / P. P. Bocharov, C. D’Apice, A. V. Pechinkin, S. Salerno. - Brill Academic Publishers, 2004. - 457 p.
  • Мокров Е. В., Самуйлов К. Е. Модель системы облачных вычислений в виде системы массового обслуживания с несколькими очередями и с групповым поступлением заявок // T-Comm - Телекоммуникации и Транспорт. - 2013. - Т. 11, № 7. - С. 139-141.
  • Мокров Е. В., Чукарин А. В. Анализ показателей эффективности системы облачных вычислений с миграцией серверов // T-Comm - Телекоммуникации и Транспорт. - 2014. - Т. 8, № 8. - С. 64-67.
  • Balsamo S., Mura I. Approximate Response Time Distribution in Fork and Join Systems // SIGMETRICS Performance Evaluation Review. - 1995. - Vol. 23, No 1. - Pp. 305-306.
  • Balsamo S., Mura I. On Queue Length Moments in Fork and Join Queuing Networks with General Service Times // Computer Performance Evaluation Modelling Techniques and Tools. LNCS. - 1997. - Vol. 1245. - Pp. 218-231.
  • Balsamo S., Donatiello L., Van Dijk N. M. Bound Performance Models of Heterogeneous Parallel Processing Systems // IEEE Transactions on Parallel and Distributed Systems. - 1998. - Vol. 9, No 10. - Pp. 1041--1056.
  • Perros H. G. On the / / Queue // Performance Evaluation. - 1983. - Vol. 3, No 2. - Pp. 83-93.
  • Neuts M. F. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. - Courier Corporation, 1981. - 332 p.
  • Rao B. M., Posner M. J. M. Algorithmic and Approximation Analyses of the Split and Match Queue // Stochastic Models. - 1985. - Vol. 1, No 3. - Pp. 433-456.
  • Takahashi M., ¯ Osawa H., Fujisawa T. On a Synchronization Queue with Two Finite Buffers // Queueing Systems. - 2000. - Vol. 36. - Pp. 107-123.
  • Takahashi M., Takahashi Y. Synchronization Queue with Two MAP Inputs and Finite Buffers // Proc. of the Third International Conference on Matrix Analytical Methods in Stochastic Models. - 2000. - Pp. 375-390.
  • Generalized Parallel-Server Fork-Join Queues with Dynamic Task Scheduling / M. S. Squillante, Y. Zhang, A. Sivasubramaniam, N. Gautam // Annals of Operations Research. - 2008. - Vol. 160, No 1. - Pp. 227-255.
  • Joshi G., Soljanin E., Wornell G. Efficient Redundancy Techniques for Latency Reduction in Cloud Systems // arXiv preprint arXiv:1508.03599. - 2015.
  • David H. A. Order Statistics. - Wiley, New York, 1981.
  • David H. A., Nagaraja H. N. Order Statistics. - John Wiley & Sons, 2003. - 458 p.
  • Gumbel E. J. Statistics of Extremes. - New York: Columbia University Press, 1958. - 375 p.
  • Allen A. O. Probability, Statistics, and Queueing Theory: With Computer Science Applications. - Gulf Professional Publishing, 1990. - 740 p.
  • Kleinrock L. Queueing Systems, Volume I: Theory. - Wiley Interscience, 1975. - 448 p.
  • Trivedi K. S. Probability and Statistics with Reliability, Queueing, and Computer Science Applications (2nd ed.). - John Wiley & Sons, 2002. - 830 p.
  • Gravey A. A Simple Construction of an Upper Bound for the Mean of the Maximum of Identically Distributed Random Variables // Journal of Applied Probability. - 1985. - Vol. 22. - Pp. 844--851.
  • The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests / A. V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin // Distributed Computer and Communication Networks. DCCN 2016. Communications in Computer and Information Science. - 2016. - Vol. 678. - Pp. 418-429.
  • Самуйлов К. Е., Зарядов И. С., Горбунова А. В. Анализ времени отклика системы облачных вычислений // T-Comm: Телекоммуникации и транспорт. - 2015. - Т. 9, № 11. - С. 57-61.
  • Thomasian A. Analysis of Fork/Join and Related Queueing Systems // ACM Computing Surveys (CSUR). - 2014. - Vol. 47, No 2. - Pp. 17:1-17:71.
  • Harrison P., S. Z. Queueing Models with Maxima of Service Times // Computer Performance Evaluation. Modelling Techniques and Tools. - Springer Berlin Heidelberg, 2003. - Pp. 152-168.
  • Thomasian A., Menon J. RAID5 Performance with Distributed Sparing // IEEE Transactions on Parallel and Distributed Systems. - 1997. - Vol. 8, No 6. - Pp. 640-657.
  • Johnson N. L., Kotz S., Balakrishnan N. Continuous Univariate Distributions. - Wiley Series in Probability and Statistics, 1995. - Vol. 1, 752 p.
  • Lebrecht A. S., Knottenbelt W. J. Response Time Approximations in Fork-Join Queues // In Proceedings of the 23rd Annual UK Performance Engineering Workshop (UKPEW’07). - 2007.
  • Arnold B. C. Distribution-Free Bounds on the Mean of the Maximum of a Dependent Sample // SIAM Journal on Applied Mathematics. - 1985. - Vol. 38, No 1. - Pp. 163-167.
  • Petzold M. A Note on the First Moment of Extreme Order Statistics from the Normal Distribution // rapport nr.: Seminar Papers. - 2000.
  • Thomasian A., Tantawi A. N. Approximate Solutions for // Fork/Join Synchronization // Proceedings of the 26th conference on Winter simulation (WSC’94) / Society for Computer Simulation International. - 1994. - Pp. 361-368.

Просмотры

Аннотация - 105

PDF (Russian) - 22


© Горбунова А.В., Зарядов И.С., Самуйлов К.Е., 2018

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.