title: ÐÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ ÑÐ°ÑÐ¿ÑÐµÐ´ÐµÐ»ÐµÐ½Ð½Ð¾Ð¹ ÑÑÐ°Ð½Ð·Ð°ÐºÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸ CUDA-DTM Ð¼ÐµÑÐ¾Ð´Ð¾Ð¼ Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸ Ð¼Ð¾Ð´ÐµÐ»Ð¸
title: Ð²ÑÐ¿ÑÑÐºÐ½Ð°Ñ ÐºÐ²Ð°Ð»Ð¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¾Ð½Ð½Ð°Ñ ÑÐ°Ð±Ð¾ÑÐ° Ð±Ð°ÐºÐ°Ð»Ð°Ð²ÑÐ°
titleType: Subtitle
title: Verification of distributed transactional memory CUDA-DTM by the Model Checking method
Creators: name: ÐÐ°ÑÐ»Ð°Ð¼Ð¾Ð², ÐÐ¼Ð¸ÑÑÐ¸Ð¹
Publisher: name: Ð¡Ð°Ð½ÐºÑ-ÐÐµÑÐµÑÐ±ÑÑÐ³ÑÐºÐ¸Ð¹ Ð¿Ð¾Ð»Ð¸ÑÐµÑÐ½Ð¸ÑÐµÑÐºÐ¸Ð¹ ÑÐ½Ð¸Ð²ÐµÑÑÐ¸ÑÐµÑ ÐÐµÑÑÐ° ÐÐµÐ»Ð¸ÐºÐ¾Ð³Ð¾
Year: 2021
Subjects: cuda-dtm
ÑÑÐ°Ð½Ð·Ð°ÐºÑÐ¸Ð¾Ð½Ð½Ð°Ñ Ð¿Ð°Ð¼ÑÑÑ
ÑÐ¾ÑÐ¼Ð°Ð»ÑÐ½Ð°Ñ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ
Ð¼ÐµÑÐ¾Ð´ Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸ Ð¼Ð¾Ð´ÐµÐ»ÐµÐ¹
ÑÐ¿ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ
ÐºÐ»Ð°ÑÑÐµÑ
Ð³ÑÐ°ÑÐ¸ÑÐµÑÐºÐ¸Ð¹ Ð¿ÑÐ¾ÑÐµÑÑÐ¾Ñ
transactional memory
formal verification
model checking
specification
cluster
graphics processing unit

description: Ð Ð°Ð±Ð¾ÑÐ° Ð¿Ð¾ÑÐ²ÑÑÐµÐ½Ð° Ð¼Ð¾Ð´ÐµÐ»Ð¸ÑÐ¾Ð²Ð°Ð½Ð¸Ñ Ð¸ ÑÐ¾ÑÐ¼Ð°Ð»ÑÐ½Ð¾Ð¹ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ ÑÐ°ÑÐ¿ÑÐµÐ´ÐµÐ»ÐµÐ½Ð½Ð¾Ð¹ ÑÑÐ°Ð½Ð·Ð°ÐºÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸ CUDA-DTM Ð¿ÑÐ¸ Ð¿Ð¾Ð¼Ð¾ÑÐ¸ Ð¼ÐµÑÐ¾Ð´Ð° Model Checking. ÐÐ¾Ð´ÐµÐ»Ñ Ð¿Ð°Ð¼ÑÑÐ¸ CUDA-DTM ÑÐ²Ð»ÑÐµÑÑÑ Ð½Ð¾Ð²Ð¾Ð¹, Ð¸ Ð°Ð²ÑÐ¾ÑÑ ÑÑÐ°ÑÑÐ¸, Ð¾Ð¿Ð¸ÑÑÐ²Ð°ÑÑÐ¸Ðµ ÐµÐµ, Ð½Ðµ Ð¿ÑÐ¸Ð²Ð¾Ð´ÑÑ ÑÐ²ÐµÐ´ÐµÐ½Ð¸Ð¹ Ð¾ ÑÐ¾ÑÐ¼Ð°Ð»ÑÐ½Ð¾Ð¹ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ Ð¼Ð¾Ð´ÐµÐ»Ð¸. Ð ÑÐ¾ Ð¶Ðµ Ð²ÑÐµÐ¼Ñ ÑÐ°Ð·ÑÐ°Ð±Ð¾ÑÐºÐ° Ð¼Ð¾Ð´ÐµÐ»ÐµÐ¹ ÑÑÐ°Ð½Ð·Ð°ÐºÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸ ÑÐ²Ð»ÑÐµÑÑÑ Ð¾ÑÐµÐ½Ñ ÑÐ»Ð¾Ð¶Ð½ÑÐ¼ Ð¿ÑÐ¾ÑÐµÑÑÐ¾Ð¼, Ð² ÐºÐ¾ÑÐ¾ÑÐ¾Ð¼ Ð»ÐµÐ³ÐºÐ¾ Ð´Ð¾Ð¿ÑÑÑÐ¸ÑÑ Ð¾ÑÐ¸Ð±ÐºÑ. Ð¦ÐµÐ»Ñ Ð½Ð°ÑÐµÐ¹ ÑÐ°Ð±Ð¾ÑÑ - ÑÐ¾ÑÐ¼Ð°Ð»ÑÐ½Ð¾ Ð²ÐµÑÐ¸ÑÐ¸ÑÐ¸ÑÐ¾Ð²Ð°ÑÑ Ð¼Ð¾Ð´ÐµÐ»Ñ CUDA-DTM Ð¿ÑÐ¸ Ð¿Ð¾Ð¼Ð¾ÑÐ¸ Ð¼ÐµÑÐ¾Ð´Ð° Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸ Ð¼Ð¾Ð´ÐµÐ»Ð¸. ÐÐ»ÑÑÐµÐ²ÑÐµ Ð¾ÑÐ¾Ð±ÐµÐ½Ð½Ð¾ÑÑÐ¸ CUDA-DTM Ð±ÑÐ»Ð¸ Ð²ÑÐ´ÐµÐ»ÐµÐ½Ñ Ð¿Ð¾ÑÐ»Ðµ ÑÑÐ°Ð²Ð½ÐµÐ½Ð¸Ñ ÐµÑ Ñ Ð´ÑÑÐ³Ð¸Ð¼Ð¸ Ð¼Ð¾Ð´ÐµÐ»ÑÐ¼Ð¸ ÑÑÐ°Ð½Ð·Ð°ÐºÑÐ¸Ð¾Ð½Ð½Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸. Ð¢Ð°ÐºÐ¸Ñ Ð¾ÑÐ¾Ð±ÐµÐ½Ð½Ð¾ÑÑÐµÐ¹ Ð¾ÐºÐ°Ð·Ð°Ð»Ð¾ÑÑ ÑÑÐ¸: ÑÐ°Ð±Ð¾ÑÐ° Ð² ÑÐµÐ¶Ð¸Ð¼Ðµ Ð¿Ð¾ÑÐ¾ÐºÐ° ÑÐ¿ÑÐ°Ð²Ð»ÐµÐ½Ð¸Ñ, Ð¸ÑÐ¿Ð¾Ð»ÑÐ·Ð¾Ð²Ð°Ð½Ð¸Ðµ Ð²Ð»Ð¾Ð¶ÐµÐ½Ð½ÑÑ ÑÑÐ°Ð½Ð·Ð°ÐºÑÐ¸Ð¹ Ð¸ Ð¿Ð¾Ð´Ð´ÐµÑÐ¶ÐºÐ° MPI. ÐÐ»Ñ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ Ð¿ÑÐ¸ Ð¿Ð¾Ð¼Ð¾ÑÐ¸ Ð¼ÐµÑÐ¾Ð´Ð° Model Checking Ð±ÑÐ»Ð¸ Ð²ÑÐ±ÑÐ°Ð½Ñ Ð¸Ð½ÑÑÑÑÐ¼ÐµÐ½ÑÑ Ð¿ÑÐ¾Ð²ÐµÑÐºÐ¸ Ð¼Ð¾Ð´ÐµÐ»ÐµÐ¹ Spin Ð¸ TLC Model Checker. ÐÑÐ»Ð¸ Ð²ÑÐ´ÐµÐ»ÐµÐ½Ñ Ð¾ÑÐ½Ð¾Ð²Ð½ÑÐµ ÑÑÑÑÐºÑÑÑÑ Ð´Ð°Ð½Ð½ÑÑ Ð¸ Ð°Ð»Ð³Ð¾ÑÐ¸ÑÐ¼Ñ, Ð¸ÑÐ¿Ð¾Ð»ÑÐ·ÑÐµÐ¼ÑÐµ Ð² CUDA-DTM. ÐÐ»Ñ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ Ð² Spin Ð±ÑÐ»Ð° Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð° Ð¼Ð¾Ð´ÐµÐ»Ñ Ð½Ð° ÑÐ·ÑÐºÐµ Promela, Ð° Ð´Ð»Ñ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ Ð² TLC Model Checker Ð±ÑÐ»Ð° Ð¿Ð¾ÑÑÑÐ¾ÐµÐ½Ð° Ð¼Ð¾Ð´ÐµÐ»Ñ Ð½Ð° ÑÐ·ÑÐºÐµ Pluscal. Ð ÑÐµÐ·ÑÐ»ÑÑÐ°ÑÐµ Ð² ÑÐ¾Ð´Ðµ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ Ð² Spin Ð±ÑÐ»Ð¾ ÑÐ¾ÑÐ¼Ð°Ð»ÑÐ½Ð¾ Ð´Ð¾ÐºÐ°Ð·Ð°Ð½Ð¾, ÑÑÐ¾ Ð¼Ð¾Ð´ÐµÐ»Ñ CUDA-DTM Ð´Ð»Ñ ÐºÐ»Ð°ÑÑÐµÑÐ¾Ð² Ñ 2 ÑÐ·Ð»Ð°Ð¼Ð¸ Ð¸ 2,4 Ð¸ 8 ÑÑÐµÐ¹ÐºÐ°Ð¼Ð¸ ÑÐ°Ð·Ð´ÐµÐ»ÑÐµÐ¼Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸ ÑÐ´Ð¾Ð²Ð»ÐµÑÐ²Ð¾ÑÑÐµÑ ÑÐ²Ð¾Ð¹ÑÑÐ²Ð°Ð¼ Ð¾ÑÑÑÑÑÑÐ²Ð¸Ñ Ð±Ð»Ð¾ÐºÐ¸ÑÐ¾Ð²Ð¾Ðº Ð¸ Ð²Ð·Ð°Ð¸Ð¼Ð½Ð¾ Ð¸ÑÐºÐ»ÑÑÐ°ÑÑÐµÐ³Ð¾ Ð´Ð¾ÑÑÑÐ¿Ð°. Ð ÑÐ¾Ð´Ðµ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ð¸ Ð² TLC Model Checker Ð±ÑÐ»Ð¾ ÑÐ¾ÑÐ¼Ð°Ð»ÑÐ½Ð¾ Ð´Ð¾ÐºÐ°Ð·Ð°Ð½Ð¾, ÑÑÐ¾ Ð¼Ð¾Ð´ÐµÐ»Ñ CUDA-DTM Ð´Ð»Ñ ÐºÐ»Ð°ÑÑÐµÑÐ¾Ð² Ñ 2 ÑÐ·Ð»Ð°Ð¼Ð¸ Ð¸ 2 ÑÑÐµÐ¹ÐºÐ°Ð¼Ð¸ ÑÐ°Ð·Ð´ÐµÐ»ÑÐµÐ¼Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸ ÑÐ´Ð¾Ð²Ð»ÐµÑÐ²Ð¾ÑÑÐµÑ ÑÐ²Ð¾Ð¹ÑÑÐ²Ñ Ð¾ÑÑÑÑÑÑÐ²Ð¸Ñ Ð±Ð»Ð¾ÐºÐ¸ÑÐ¾Ð²Ð¾Ðº. ÐÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ Ð¼Ð¾Ð´ÐµÐ»ÐµÐ¹ CUDA-DTM Ð´Ð»Ñ ÐºÐ»Ð°ÑÑÐµÑÐ¾Ð² Ñ Ð±Ð¾Ð»ÑÑÐ¸Ð¼ ÐºÐ¾Ð»Ð¸ÑÐµÑÑÐ²Ð¾Ð¼ ÑÐ·Ð»Ð¾Ð² Ð¸ ÑÑÐµÐµÐº Ð¾Ð±ÑÐµÐ¹ ÑÐ°Ð·Ð´ÐµÐ»ÑÐµÐ¼Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸ Ð±ÑÐ»Ð° Ð¾Ð³ÑÐ°Ð½Ð¸ÑÐµÐ½Ð° ÑÐµÑÑÑÑÐ°Ð¼Ð¸ ÑÐ¸ÑÑÐµÐ¼Ñ, Ð½Ð° ÐºÐ¾ÑÐ¾ÑÐ¾Ð¹ Ð¿ÑÐ¾Ð²Ð¾Ð´Ð¸Ð»Ð°ÑÑ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ. Ð Ð±ÑÐ´ÑÑÐµÐ¼ Ð¼Ð¾Ð¶Ð½Ð¾ Ð¿ÑÐ¾Ð²ÐµÑÑÐ¸ Ð²ÐµÑÐ¸ÑÐ¸ÐºÐ°ÑÐ¸Ñ Ð½Ð° Ð±Ð¾Ð»ÐµÐµ Ð¿ÑÐ¾Ð¸Ð·Ð²Ð¾Ð´Ð¸ÑÐµÐ»ÑÐ½Ð¾Ð¹ ÑÐ¸ÑÑÐµÐ¼Ðµ, ÑÐ²ÐµÐ»Ð¸ÑÐ¸Ð² ÑÐ¸ÑÐ»Ð¾ ÑÐ·Ð»Ð¾Ð² Ð¸ ÑÑÐµÐµÐº ÑÐ°Ð·Ð´ÐµÐ»ÑÐµÐ¼Ð¾Ð¹ Ð¿Ð°Ð¼ÑÑÐ¸. Ð¢Ð°ÐºÐ¶Ðµ Ð² Ð±ÑÐ´ÑÑÐµÐ¼ Ð¼Ð¾Ð¶Ð½Ð¾ ÑÐ¾ÑÐ¼Ð°Ð»Ð¸Ð·Ð¾Ð²Ð°ÑÑ Ð±Ð¾Ð»ÐµÐµ ÑÐ»Ð¾Ð¶Ð½ÑÐµ ÑÐ²Ð¾Ð¹ÑÑÐ²Ð° Ð¸ Ð¿ÑÐ¾Ð²ÐµÑÐ¸ÑÑ, ÑÐ´Ð¾Ð²Ð»ÐµÑÐ²Ð¾ÑÑÐµÑ Ð»Ð¸ CUDA-DTM ÑÑÐ¸Ð¼ ÑÐ²Ð¾Ð¹ÑÑÐ²Ð°Ð¼.
description: This thesis is devoted to modeling and formal verification of distributed transactional memory CUDA-DTM using Model Checking method. Memory model CUDA-DTM is new and authors of the article describing this model did not provide information about formal verification of the model. At the same time, the development of transactional memory model is a very complicated process in which it is easy to make a mistake. The objective of this thesis is to highlight the main distinctive features of CUDA-DTM, build a model which will reflect these features and then formally verify it with Model Checking method. The main distinctive features if CUDA-DTM were pointed out after the comparison of CUDA-DTM with other transactional memory models. There are three main distinctive features: the support of MPI, working in control-flow mode and nested transactions support. For verification with Model Checking method, we chose model verification tools Spin and TLC Model Checker. We highlighted the main data structures and algorithms used in CUDA-DTM. For Spin verification we created a model in Promela language and for TLC Model Checker verification we created a model in Pluscal language. During the Spin verification, we formally proved that CUDA-DTM model for clusters with 2 nodes and 2, 4 and 8 shared memory pieces satisfies the requirement of mutual exclusion and being deadlock-free. During the TLC Model Checker verification, we formally proved that CIDA-DTM model for clusters with 2 nodes and 2 shared memory pieces satisfies the requirement of being deadlock-free. The verification of CUDA-DTM model for clusters with bigger number of nodes and shared data objects was limited by the resources of our system where we launched the verification. In the future we will be able to perform the verification on a more productive machine and increase the number of nodes and shared data objects. Also, in the future we will be able to formalize more complicated properties and check if CUDA-DTM satisfies these properties.