|
DOI: 10.14489/vkit.2021.11.pp.037-046
Кукушкин Д. И., Антоненко В. А.
ИСПОЛЬЗОВАНИЕ ЗАВИСИМОСТИ ПО ДАННЫМ ДЛЯ ОРГАНИЗАЦИИ БЕССЕРВЕРНЫХ ВЫЧИСЛЕНИЙ
(с. 37-46)
Аннотация. Рассмотрен подход к планированию бессерверных вычислений на основе анализа зависимостей по данным. Приведено описание разработанного прототипа на базе бессерверной платформы Fission. Показано, что улучшения позволяют существенно сократить время выполнения до двух раз для некоторых типов бессерверных функций.
Ключевые слова: бессерверные вычисления; бесcерверная функция; планирование ресурсов; зависимость по данным; алгоритм списочного планирования; критический путь.
Kukushkin D. I., Antonenko V. A.
SERVERLESS COMPUTATIONS RESOURCE SCHEDULING BASED ON DATA DEPENDENCY
(pp. 37-46)
Abstract. The serverless computing model is becoming quite widespread. This model allows developers to create flexible and fault tolerant applications with an attractive billing model. The increasing complexity of serverless functions has led to the necessity to use serverless workflows – serverless functions invoking other serverless functions. However, such concept imposes certain requirements on the serverless functions that make distributed computations. The overhead of transferring data between serverless functions can significantly increase the execution time of a program using this approach. One way to reduce overhead is to improve serverless scheduling techniques. This paper discusses an approach to scheduling serverless computations based on data dependency analysis. We propose to divide the problem of planning of the computation of a composite serverless function into three stages. For each stage we provide a description by a mathematical model. We carried out a review of algorithms used to schedule resources by compilers and in parallel computing in multiprocessor systems to determine the best algorithm to implement in a prototype scheduler. For each algorithm, it was specified how it could be used for resource scheduling in serverless platforms. We provide a description of the developed prototype based on the Fission serverless platform. The prototype implements the critical path heuristic. It is shown that the improvements can significantly reduce the execution time up to two times for some types of serverless functions.
Keywords: Serverless computing; Serverless function; Resource scheduling; Data dependency; List scheduling, Critical path.
Д. И. Кукушкин, В. А. Антоненко (Московский государственный университет имени М. В. Ломоносова, Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
D. I. Kukushkin, V. A. Antonenko (Lomonosov Moscow State University, Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. MadLINQ: LargeScale Distributed Matrix Computation for the Cloud / Zh. Qian et al. // EuroSys’2012: 7th ACM European Conference on Computer Systems. Berne, Switzerland. 2012. 14 p. URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/04/euro135-qian.pdf (дата обращения: 01.10.2021). DOI 10.1145/2168836.2168857
2. Numpywren: Serverless Linear Algebra / V. Shankar et al. 2018. URL: https://www2.eecs.berkeley.edu/Pubs/TechRpts/2018/EECS-2018-137.pdf (дата обращения: 01.10.2021).
3. AWS Step Functions. Наглядные рабочие процессы для современных приложений. URL: https://aws.amazon.com/ru/step-functions/ (дата обращения: 01.10.2021).
4. Azure Durable Functions. URL: https://docs.microsoft.com/ru-ru/azure/azure-functions/durable/durable-functions-overview (дата обращения: 01.10.2021).
5. Google. Cloud Composer. URL: https://cloud.google.com/composer (дата обращения: 01.10.2021).
6. Serverless Computing: One Step Forward, Two Steps Back / J. M. Hellerstein et al. // Computer Science. 2018. 9 p. URL: https://arxiv.org/pdf/1812.03651.pdf (дата обращения: 01.10.2021).
7. Wen J., Liu Y. An Empirical Study on Serverless Workflow Service. 2021. URL: https://arxiv.org/pdf/2101.03513.pdf (дата обращения: 01.10.2021).
8. Kubernetes: офиц. сайт. URL: https://kubernetes.io (дата обращения: 01.10.2021).
9. Ristov S., Pedratscher S., Fahringer T. AFCL: An Abstract Function Choreography Language for Serverless Workflow Specification // Future Generation Computer Systems. 2021. V. 114. P. 368 – 382. URL: https://www.sciencedirect.com/science/article/pii/S0167739X20302648 (дата обращения: 01.10.2021).
10. Computer and JobShop Scheduling Theory / E. G. Coffman, Jr. (Eds). Wiley New York, 1976. 299 p.
11. A Review of Serverless Use Cases and their Characteristics / S. Eismann et al. 2021. 45 p. URL: https://arxiv.org/pdf/2008.11110.pdf (дата обращения: 01.10.2021).
12. Alibaba Cloud. Products. Serverless Workflow. URL: https://www.alibabacloud.com/ru/product/serverless-workflow (дата обращения: 01.10.2021).
13. Archipelago: A Scalable LowLatency Serverless Platform / A. Singhvi et al. // Computer Science. 2019. 14 p.
14. Scheduling Precedence Graphs in Systems with Interprocessor Communication Times / J. Hwang et al. // SIAM Journal on Computing. 1989. V. 18, No. 2. P. 244 – 257. DOI 10.1137/0218016
15. Instruction Scheduling / K. D. Cooper, L. Torczon (Eds.) // Engineering a Compiler (Second Edition). Boston: Morgan Kaufmann, 2012. P. 639 – 677. URL: https://www.sciencedirect.com/science/article/pii/B9780120884780000128 (дата обращения: 01.10.2021). DOI 10.1016/B978-0-12-088478-0.00012-8
16. A Comparison of List Schedules for Parallel Processing Systems / T. L. Adam et al. // Commun. of the ACM. 1974. V. 17, No. 12. P. 685 – 690. URL: https://doi.org/10.1145/361604.361619 (дата обращения: 01.10.2021).
17. Shirazi B., Wang M., Girish P. Analysis and Evaluation of Heuristic Methods for Static Task Scheduling // Journal of Parallel and Distributed Computing. 1990. V. 10, No. 3. P. 222 – 232. URL: https://www.sciencedirect.com/science/article/pii/074373159090014G (дата обращения: 01.10.2021). DOI 10.1016/0743-7315(90)90014-G
18. Manoharan S., Thanisch P. Assigning Dependency Graphs onto Processor Networks // Parallel Computing. 1991. V. 17, No. 1. P. 63 – 73. URL: https://www.sciencedirect.com/science/article/pii/S0167819105800183 (дата обращения: 01.10.2021). DOI 10.1016/S0167-8191(05)80018-3
19. Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters // Commun. of the ACM. 2008. V. 51, No. 1. P. 107 – 113. URL: https://doi.org/10.1145/1327452.1327492 (дата обращения: 01.10.2021).
1. Qian Zh. et al. (2012). MadLINQ: LargeScale Distributed Matrix Computation for the Cloud. EuroSys’2012: 7th ACM European Conference on Computer Systems. Berne. Available at: https://www.microsoft.com/en-us/research/wp-content/uploads/2012/04/euro135-qian.pdf (Accessed: 01.10.2021). DOI 10.1145/2168836.2168857
2. Shankar V. et al. (2018). Numpywren: Serverless Linear Algebra. Available at: https://www2.eecs.berkeley.edu/ Pubs/TechRpts/2018/EECS-2018-137.pdf (Accessed: 01.10.2021).
3. AWS Step Functions. Intuitive workflows for modern applications. Available at: https://aws.amazon.com/ru/step-functions/ (Accessed: 01.10.2021). [in Russian language]
4. Azure Durable Functions. Available at: https://docs.microsoft.com/ru-ru/azure/azure-functions/durable/ durable-functions-overview (Accessed: 01.10.2021). [in Russian language]
5. Google. Cloud Composer. Available at: https://cloud.google.com/composer (Accessed: 01.10.2021).
6. Hellerstein J. M. et al. (2018). Serverless Computing: One Step Forward, Two Steps Back. Computer Science. Available at: https://arxiv.org/pdf/1812.03651.pdf (Accessed: 01.10.2021).
7. Wen J., Liu Y. (2021). An Empirical Study on Serverless Workflow Service. Available at: https://arxiv.org/pdf/2101.03513.pdf (Accessed: 01.10.2021).
8. Kubernetes. Available at: https://kubernetes.io (Accessed: 01.10.2021).
9. Ristov S., Pedratscher S., Fahringer T. (2021). AFCL: An Abstract Function Choreography Language for Serverless Workflow Specification. Future Generation Computer Systems, Vol. 114, pp. 368 – 382. Available at: https://www.sciencedirect.com/science/article/pii/S0167739X20302648 (Accessed: 01.10.2021).
10. Coffman E. G. Jr. (Ed.) (1976). Computer and JobShop Scheduling Theory. Wiley New York.
11. Eismann S. et al. (2021). A Review of Serverless Use Cases and their Characteristics. Available at: https://arxiv.org/pdf/2008.11110.pdf (Accessed: 01.10.2021).
12. Alibaba Cloud. Products. Serverless Workflow. Available at: https://www.alibabacloud.com/ru/product/server-less-workflow Accessed: 01.10.2021). [in Russian language]
13. Singhvi A. et al. (2019). Archipelago: A Scalable LowLatency Serverless Platform. Computer Science.
14. Hwang J. et al. (1989). Scheduling Precedence Graphs in Systems with Interprocessor Communication Times. SIAM Journal on Computing, Vol. 18, (2), pp. 244 – 257. DOI 10.1137/0218016
15. Cooper K. D., Torczon L. (Eds.) (2012). Instruction Scheduling. Engineering a Compiler. 2nd ed., pp. 639 – 677. Boston: Morgan Kaufmann. Available at: https:// www.sciencedirect.com/science/article/pii/B9780120884780000128 (Accessed: 01.10.2021). DOI 10.1016/B978-0-12-088478-0.00012-8
16. Adam T. L. et al. (1974). A Comparison of List Schedules for Parallel Processing Systems. Communications of the ACM, Vol. 17, (12), pp. 685 – 690. Available at: https://doi.org/10.1145/361604.361619 (Accessed: 01.10.2021).
17. Shirazi B., Wang M., Girish P. (1990). Analysis and Evaluation of Heuristic Methods for Static Task Scheduling. Journal of Parallel and Distributed Computing, Vol. 10, (3), pp. 222 – 232. Available at: https://www.sciencedirect.com/science/article/pii/074373159090014G (Accessed: 01.10.2021). DOI 10.1016/0743-7315(90)90014-G
18. Manoharan S., Thanisch P. (1991). Assigning Dependency Graphs onto Processor Networks. Parallel Computing, Vol. 17, (1), pp. 63 – 73. Available at: https:// www.sciencedirect.com/science/article/pii/S0167819105800183 (Accessed: 01.10.2021). DOI 10.1016/S0167-8191(05)80018-3
19. Dean J., Ghemawat S. (2008). MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, Vol. 51, (1), pp. 107 – 113. Available at: https:// doi.org/10.1145/1327452.1327492 (Accessed: 01.10.2021).
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 450 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2021.11.pp.037-046
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 450 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2021.11.pp.037-046
and fill out the form
.
|
Archive
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»