Спосіб перетворення булевих виразів для прискорення виконання оцінки повноти тестових наборів
| dc.contributor.advisor | Романкевич, Віталій Олексійович | |
| dc.contributor.author | Шевченко, Анжеліка Олегівна | |
| dc.date.accessioned | 2023-01-05T10:24:07Z | |
| dc.date.available | 2023-01-05T10:24:07Z | |
| dc.date.issued | 2022 | |
| dc.description.abstracten | Actuality of theme. In today's world, the field of application of fault-tolerant multiprocessor computing systems (FTMS) is continuously expanding, covering new areas in various fields of science, business, and production. Such systems are the basis for many developments, especially for control systems. Therefore, the study of FTMS is an urgent issue for developers and scientists. One of the urgent and key issues in the design of FTMS is the solution to the problem of the system testing process. Many approaches and methods of FTMS self-testing have been proposed, however, the execution of test checks takes part of the performance of processors, sometimes quite large, and therefore it is desirable to minimize their number. In [], an approach was proposed that allows for the analysis of a set of test checks before their execution, which can be used, in particular, to determine the optimal set of tests, which in turn will lead to a reduction in calculation time and the load on the system. Today, humanity seeks to implement automation in order to reduce as much as possible the participation of people in processes that require considerable resources. Full or partial automation of tasks is becoming more and more relevant. Because the proposed method [] requires a large number of complex transformations of expressions and this process is quite time-consuming to perform manually. In addition, the conversion of boolean expressions of a special type can take a lot of time, which should be minimized. Thus, the development of a method of converting Boolean expressions to speed up the evaluation of the completeness of test sets and its software implementation is an urgent task. The object of research is the analysis of available methods of self-testing of fault-tolerant multiprocessor systems and methods of assessing the completeness of test sets. The subject of research is a method of transformating Boolean expressions to speed up the evaluation of the completeness of test sets. The purpose of the work: the development of a method of converting Boolean expressions to speed up the evaluation of the completeness of test sets, the development of appropriate software and the conduct of test experiments The scientific novelty consists in the following: 1. A method of converting Boolean expressions is proposed to speed up the evaluation of the completeness of test sets 2. A software implementation of a method for assessing the completeness of test sets is proposed 3. The work confirms the effectiveness of the proposed method of speeding up the assessment of the completeness of test sets within the framework of the conducted experiments The practical value of the results obtained in the work is as follows. The proposed software implementation of the method of assessing the completeness of test sets can be used to determine the optimal set of tests or applied in the case when an unequivocal result was not obtained based on certain test sets. In this case, it allows defining an additional test set sufficient to establish all the states of the system's processors. Developers can evaluate the completeness of the test suite, and by sorting through combinations of test checks, choose the minimum or close to it. In addition, the complex analysis of the results at the self-testing stage can be replaced by a simple procedure of searching for the appropriate row in the table of coefficients. The proposed method of transformating Boolean expressions will allow developers to speed up the assessment of the completeness of test sets. Approbation of dissertation results. The main provisions and results of the work were presented and discussed at the scientific conference of master's and postgraduate students "Applied mathematics and computing" PMK-2022 (Kyiv, November 2022) and the VIII All-Ukrainian scientific and practical conference of young scientists "Information technologies - 2021" ( Kyiv University named after Boris Grinchenko) Structure and scope of work. The master's thesis consists of an introduction, four chapters and conclusions. The introduction provides a general description of the work, assesses the current state of the problem, substantiates the relevance of the research direction, formulates the purpose and tasks of the research, shows the scientific novelty of the obtained results and the practical value of the work, provides information on the approbation of the results and their implementation. In the first section, existing methods of self-testing of processors of fault-tolerant multiprocessor systems are considered and their advantages and disadvantages are analyzed. In the second section, a method of converting Boolean expressions is proposed to speed up the evaluation of the completeness of test sets. In the third and fourth sections, the structure and description of the work of the developed software are presented, and its testing was carried out. Also presented and analyzed are the results of measuring the execution time of the completeness assessment of test sets with and without the proposed method of converting Boolean expressions. The results of the analysis of the work carried out are presented in the conclusions. The work is presented on 80 sheets, contains links to the list of used literary sources. | uk |
| dc.description.abstractuk | Актуальність теми В сучасному світі сфера застосування відмовостійких багатопроцесорних обчислювальних систем (ВБС) безперервно розширюється, охоплюючи нові області в різних галузях науки, бізнесу і виробництва. Такі системи є основою для багатьох розробок, особливо для систем керування. Отже, дослідження ВБС є актуальним питання для розробників та науковців. Одним з актуальних та ключових питань в проєктуванні ВБС є вирішення проблеми процесу тестування системи. Чимало підходів та способів самотестування ВБС було запропоновано, однак виконання тестових перевірок забирає частину продуктивності процесорів, часом досить велику, а отже їх кількість бажано мінімізувати. В був запропонований підхід, який дозволяє виконувати аналіз множини тестових перевірок до їх виконання, що може бути використано зокрема для визначення оптимального набору тестів, що в свою чергу призведе до зменшення часу обрахунків та навантаження на систему. Сьогодні людство прагне впроваджувати автоматизацію, щоб якомога більше зменшити участь людей у процесах, які вимагають чималих ресурсів. Все більшої актуальності набуває повна або часткова автоматизація задач. Оскільки, запропонований метод потребує значної кількості складних перетворень виразів і цей процес є досить трудомістким для виконання вручну. До того ж, перетворення булевих виразів спеціального виду може витрачати чимало часу, який бажано мінімізувати. Таким чином, розробка способу перетворення булевих виразів для прискорення виконання оцінки повноти тестових наборів та його програмна реалізації є актуальною задачею. Об’єктом дослідження є самотестування відмовостійких багатопроцесорних систем та способи оцінки повноти тестових наборів. Предметом дослідження є методи та способи оцінки повноти тестових наборів при тестуванні відмовостійких БС. Мета роботи: прискорення виконання оцінки повноти тестових наборів шляхом перетворення булевих виразів, які відображають міжпроцесорну взаємодію у системі. Наукова новизна полягає в наступному: 1. Запропоновано спосіб перетворення булевих виразів для прискорення виконання оцінки повноти тестових наборів 2. Реалізовано алгоритм та програма запропонованого способу 3. Підтверджено дієвість запропонованого способу прискорення оцінки повноти тестових наборів шляхом проведення необхідної кількості експериментів. Практична цінність отриманих в роботі результатів полягає в наступному. Запропонована програмна реалізація способу оцінки повноти тестових наборів може бути використана для визначення оптимального набору тестів або застосована у випадку, коли на основі певних тестових наборів однозначного результату не було отримано. В такому випадку вона дозволяє визначити додатковий тестовий набір, достатній для встановлення всіх станів процесорів системи. Розробники можуть оцінити повноту тестового набору, та шляхом перебору комбінацій тестових перевірок обрати мінімальний або близький до нього. Окрім цього складний аналіз результатів на етапі самотестування може бути замінений на просту процедуру пошуку відповідного рядка у таблиці коефіцієнтів. Запропонований спосіб перетворення булевих виразів дозволить розробникам пришвидшити оцінку повноти тестових наборів. Апробація роботи. Основні положення і результати роботи були представлені та обговорювались на науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг» ПМК-2022 (Київ, листопад 2022 р.) та VІІІ Всеукраїнської науково-практичної конференції молодих науковців «Інформаційні технології - 2021» (Київський університет ім. Бориса Грінченка) Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів та висновків. У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи, наведено відомості про апробацію результатів і їхнє впровадження. У першому розділі розглянуто існуючі методи самотестування процесорів відмовостійких багатопроцесорних систем та проаналізовано їх переваги та недоліки. У другому розділі запропоновано спосіб перетворення булевих виразів для прискорення виконання оцінки повноти тестових наборів. У третьому та четвертому розділах наведено структуру та опис роботи розробленого програмного забезпечення, проведено його тестування. Також представлені та проаналізовані результати вимірювань часу виконання оцінки повноти тестових наборів із запропонованим способом перетворення булевих виразів та без нього. У висновках представлені результати аналізу проведеної роботи. Робота представлена на 80 аркушах, містить посилання на список використаних літературних джерел. | uk |
| dc.format.page | 96 с. | uk |
| dc.identifier.citation | Шевченко, А. О. Спосіб перетворення булевих виразів для прискорення виконання оцінки повноти тестових наборів : магістерська дис. : 123 Комп'ютерна інженерія / Шевченко Анжеліка Олегівна. – Київ, 2022. – 96 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/51718 | |
| dc.language.iso | uk | uk |
| dc.publisher | КПІ ім. Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | відмовостійкі багатопроцесорні системи | uk |
| dc.subject | самотестування багатопроцесорних систем | uk |
| dc.subject | fault-tolerant multiprocessor systems | uk |
| dc.subject | self-testing of processors | uk |
| dc.subject.udc | 519.718 | uk |
| dc.title | Спосіб перетворення булевих виразів для прискорення виконання оцінки повноти тестових наборів | uk |
| dc.type | Master Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Shevchenko_magistr.pdf
- Розмір:
- 1.8 MB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.1 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: