Proceedings of computer engineering courses projects 2023-2024 of the Faculty of Applied Science of Ukrainian Catholic University
Table of contents
- Table of contents
- Preface
- HPC, simulations and visualisation
- Modelling Of Protein Systems Using Monte-Carlo Simultaion
- Real-Time Raytracer: iterative approach
- Real-time Deep-Learning Image Matching on Edge
- Numerical modeling of fluid behavior using Smoothed Particle Hydrodynamics method
- Development of High-Performance Methods for Modeling Gravitational Interaction on Large Scales
- Concurrent Real-Time Raytracer 1
- Exploration of the Apple Neural Engine
- Hardware
- System programming
- Computer engineering for the AI/ML
- Purgatory
Preface
By the scientific editor
During the computer engineering courses of the Faculty of Applied Science of Ukrainian Catholic University, which I am responsible for, students perform course projects. Most projects are mentored by highly skilled experts from the Academy and Industry. For many years, I have been impressed by their quality and deepness. Two years ago, as a part of academic writing and coherent storytelling practice, I introduced the requirement to write a report in the form of an IEEE conference paper. And I then noticed that, sometimes, their reports are on par with conference papers. So, the idea of this preprint collection – the proceedings of our courses, was born.
Those courses are: “Computer Organization Basics” (POC), “Architecture of the Computers” (AKS), “Operating Systems” (OS), and “Modern C++,” so the topics of the projects are very broad: from the hardware design and characterization to the development of renderers, from neural networks optimization to the general relativity related problems modeling. However, they are connected to either developing the hardware, squeezing most from the existing hardware – so-called high-performance computing, or teaching all the mentioned.
Due process was used to select works for publication, and an anonymous peer review was performed. Each work was reviewed by at least two persons, selected among the students of our faculty, who were competent in the corresponding topics. Then, each paper was read and, if necessary, edited by Anastasiia Beheni, the editor-in-chief of the collection, and me.
In addition to the high-quality preprints, we decided to add Purgatory – a collection of the often not less interesting works, though with substantial problems and authors unwilling or unable to fix them. All of them passed the peer review, with some requests for corrections or improvements. One substantial case is the usage of illustrations from other works without citing their sources in the picture captions – authors in no way pretend they created those illustrations, and corresponding sources are mentioned in the references list – just without adhering to the proper procedure.
This project would be impossible without the students and mentors working on the projects – and the Faculty and the University, bringing all of us together; reviews: Daria Minieieva, Dmytro Shumskyi, Dzvenyslava Butynets, Iryna Kokhan, Ivan Shevchenko, Kostyantin Savorona, Mariia Ivanchenko, Marta Sumyk, Oleksandr Ivaniuk, Oles Yarish. Olesia Omelchuk, Ostap Seryvko, Petro Mozil, Roman Mutel, Serhii Ivanov, Sofiia Folvarochna, Svitlana Hovorova, Viktoriia Kocherkevych, Yaroslav Klym and last but not least, without the Anastasiia Beheni, who agreed to serve as a manager of the project!
Many thanks to the Ukrainian Armed Forces for making this project possible!
I hope we continue our practice for the future years of our courses.
Oleg Farenyuk,
Robotics program coordinator,
Applied Science Faculty,
Ukrainian Catholic University
By the editor-in-chief
Team projects are a huge part of studying at the Applied Science Faculty. We have them on almost every course. If these projects aren’t thought of as an obligation, they can become a playground. With the resources of UCU, students can follow their curiosity with a zero error cost (but please don’t burn all the microcontrollers). A bad grade isn’t given for trying and failing; it’s given for not trying.
However, implementing a project is not the only important thing. It’s also necessary to be able to explain what has been done even to people without very specific knowledge. No matter what someone does in life, the ability to communicate ideas is major. It’s not always easy, but it’s a needed mental exercise to build discipline and clarity of mind. The clearer the thinking, the better the writing, and vice versa. That’s how the motivation for writing all those reports can be seen, and they are welcome to be read on this page.
I want to thank all the volunteers who agreed to help us review the reports. And I want to express gratitude to my teammates, Ostap, Sofiia, Olesia, and Roman, with whom we worked on two of the projects listed here and on many more. We’ve learned a lot together, and I’ve learned a lot from them. Those 3 years at the Applied Science Faculty were quite a journey for me.
I am very grateful to Ukrainian Armed Forces for the ability to live and study in Ukraine.
Anastasiia Beheni,
4th year Computer Science student
Applied Science Faculty,
Ukrainian Catholic University
HPC, simulations and visualisation
Modelling Of Protein Systems Using Monte-Carlo Simultaion
Authors: Anna Yaremko, Bohdan Pavliuk, Iryna Kokhan, Petro Mozil, Taras Patsagan
Published: 1 September 2024. Performed in AKS-2024.
Abstract: This document describes the general workflow of particle simulation using patchy particles and the structure of the particular realization of it for two ensembles: $NVT$ and $\mu VT$. The implementation relies on CUDA to improve performance, and a big part of the work focuses on describing the optimizations for parallel implementation of the simulation.
Real-Time Raytracer: iterative approach
Authors: Kateryna Kovalchuk, Radomyr Husiev, Bohdan Opyr, Roman Zaletskyi, Ostap Trush,
Published: 1 September 2024. Performed in AKS-2024.
Abstract: This report describes the implementation of a ray tracer, a rendering algorithm that simulates light propagation to create realistic 3D images. The goal is to implement it iteratively, from basic to progressively more advanced techniques, and explore the trade-off between visual fidelity and performance.
Real-time Deep-Learning Image Matching on Edge
Authors: Mykhailo Buleshnyi, Maksym Buleshnyi, Artur Pelcharskyi, Davyd Ilnytskyi, Roman Milishchuk, Vasyl Borsuk, Mykola Morhunenko.
Published: 1 September 2024. Performed in AKS-2024.
Abstract: In recent years, machine learning has experienced an immense surge in popularity. As the accuracy of models has significantly improved, there has been a corresponding increase in the resources required to execute them. In certain scenarios, it becomes crucial to employ complex deep-learning models on embedded devices in real-time. The objective of this work is to enhance the ALIKE model’s speed while minimizing any potential loss in accuracy, targeting the embedded platforms, such as a BeagleBone AI-64.
Numerical modeling of fluid behavior using Smoothed Particle Hydrodynamics method
Authors: Olena Azarova, Anna Monastyrska, Oles Yarish, Elizaveta Arnauta, Mykhailo Moroz
Published: 1 September 2024. Performed in AKS-2024.
Abstract: This document describes our work on the Numerical modeling of fluid behavior using the Smoothed Particle Hydrodynamics (SPH) method. In this project, we discuss the theory of SPH and its implementation to simulate fluid behavior.
Development of High-Performance Methods for Modeling Gravitational Interaction on Large Scales
Authors: Roman Naumenko, Anastasiia Beheni, Olesia Omelchuk, Sofiia Folvarochna, Mykhailo Moroz
Published: 1 September 2024. Performed in AKS-2023.
Abstract: The project demonstrates the implementation of high-performance methods for modeling gravitational interaction in a dynamic system with a large number of homogeneous particles in three-dimensional space. To optimize the calculations, we approximated the task’s solution using the Barnes-Hut algorithm. It groups nearby bodies and approximates them as a single body.
For effective parallel building of the BVH tree that minimizes divergence and maximizes occupancy, we used Linear BVH construction that first chooses the order in which the leaf nodes are stored in the tree and then generates the internal nodes in a way that respects this order. We choose that order using the space-filling z-order curve that associates each particle with the corresponding Morton code depending on its position in space. Using sorted with Bitonic sort Morton codes, we are able to build a BVH tree processing each node in parallel.
To maximize and utilize the possible substantial gains for the mentioned algorithms in a parallel setting, we perform all the calculations on the Graphics Processing Unit (GPU). We used Open Graphics Library (OpenGL) and the compute shaders written in Graphics Library Shader Language (GLSL) to interact with the GPU.
Concurrent Real-Time Raytracer 1
Authors: Andrii Yaroshevych, Pavlo Kryven, Oleksandr Shchur, Ostap Trush
Published: 1 September 2024. Performed in AKS-2023.
Abstract: This project aimed to create a real-time ray tracer program on the CPU, utilizing the wide possibilities for parallelization. Blinn-Phong~\cite{Blinn} reflection model is used as a backbone of lighting effects. Ray-objects intersection testing is conducted using the Möller–Trumbore algorithm~\cite{moller_trumbore} for triangles and simple linear algebra operations for plains, spheres, and ellipses. Global and local view concepts are introduced to implement the 3D object sizing, rotation, and positioning. The camera obscura model is used to reproduce the properties of the camera, such as field of view and perspective. As expected, the overall conclusion is that the CPU is insufficient to perform a high-resolution real-time rendering. However, GPU rendering also had some downsides~\cite{Wald}, so the investigated problem is still relevant.
Exploration of the Apple Neural Engine
Authors: Kseniia Kretsula, Khrystyna Mysak, Mariia Ivanchenko, Dzvenyslava Butynets, Ihor Babin, Yaroslav Romanus
Published: 1 September 2024. Performed in AKS-2024.
Abstract: This report presents an in-depth exploration of the Apple Neural Engine (ANE) as a key player in the on-device AI inference trend. The project is structured into three parts, each addressing specific aspects of ANE functionality, optimization, and potential contributions to the broader AI community.
Hardware
Visual odometry for real-time localization of dynamic locomotion devices
Authors: Savorona Kostyantin, Ivaniuk Oleksandr, Humeniuk Denis, Parnosov Nazar, Krasnianskiy Tymur
Published: 1 September 2024. Performed in AKS-2024.
Abstract: This project explored different methods of visual odometry for real-time localization, highlighted their main advantages and disadvantages, what is used in choosing the most suitable one, and what can be applied to dynamic locomotion devices and also considered hardware specifications and requirements for using that algorithm with microcomputers.
Creating a homemade smartphone for educational purposes
Authors: Ivaniuk Oleksandr, Savorona Kostyantin, Parnosov Nazar, Humeniuk Denis, Haiduk Kostianty
Published: 1 September 2024. Performed in POC-2023.
Abstract: This document describes our development of a homemade smartphone for educational purposes using the STM32 MCU. We describe the electronic components utilized, the code development process, and the current functionality. Our goal is to present our experience clearly and accessibile for all readers
System programming
Joker: Implementing Docker Containerization Functionality
Authors: Taras Yaroshko, Nazar Demchuk, Oleksandr Shchur, Liubomyr Oleksiuk, Hermann Yavorskyi
Published: 1 September 2024. Performed in OS-2023.
Abstract: This report presents the implementation of Joker, which is the analog of Docker written in Rust and C++. The report reveals the design, features, and challenges encountered during the software development process.
ICMP-based Rootkit
Authors: Roman Bernikov, Nazar Kononenko, Ivan-Vitalii Petrychko
Published: 1 September 2024. Performed in OS-2023.
Abstract: The paper’s aim is to introduce Rootkit – a collection of computer software designed to enable access to a computer without being detected. This package is designed strictly for educational and research purposes. Here, we will discuss our main findings and implementations.
The paper consists of several sections:
- Introduction. This section provides a brief review of our rootkit, its capabilities, and core concepts.
- Implementation. Here, the main implementation choices are explained, as well as the reasons that lead to them.
- Performance impact. In this section, we compare the performance of different rootkit implementations.
- References. This page mentions all materials and articles that we’ve used in our work.
UEFI-game with bootloader functions
Authors: Ivan Shevchenko, Viktoriia Kocherkevych, Yaroslav Klym, Volodymyr Kuchynskiy
Published: 1 September 2024. Performed in OS-2023.
Abstract: This report demonstrates and describes the implementation of three different games with boot managing capabilities for the UEFI environment. The project’s objective was to explore the feasibility of game development based on the EDK-II framework for UEFI. Three games were implemented, namely Wordle, 2D Maze and 3D Maze.
Computer engineering for the AI/ML
MacTell: an LLM-Based Code Interpreter
Authors: Anastasiia Senyk, Yaroslav Korch, Liliana Hotsko, Matvii Prytula
Published: 1 September 2024. Performed in OS-2023.
Abstract: Mactell is a Swift-powered project designed to integrate multiple functionalities into a macOS application. By employing natural language processing, Mactell interprets user commands into executable actions, significantly improving user interaction within OS and productivity. Key functionalities include command-line interface (CLI) management, web browsing, code execution, media playback, and other OS-accessible tasks, all presented through an intuitive, unified interface.
DeepDendro: Parallel C++ Neural Network Framework
Authors: Yaroslav Korch, Matvii Prytula, Anastasiia Senyk
Published: 1 September 2024. Performed in AKS-2023.
Abstract: Deep learning models often require large amounts of data to be trained effectively. Hierarchical clustering algorithms can be used to group similar data points together and reduce the amount of data required for training. However, traditional hierarchical clustering algorithms can be computationally expensive and not scalable to large datasets. In this paper, we propose DeepDendro, a parallel system designed specifically for deep learning applications. We implement DeepDendro using C++ and Intel’s TBB library for parallelization. Our algorithm uses a PipeDream approach for parallel training of Neural Networks. The proposed algorithm achieves significant speedup compared to traditional hierarchical clustering algorithms while maintaining high accuracy in results.
Purgatory
All works in this category should be perceived as drafts. They all passed the peer review, with some requests for corrections or improvements that were not fulfilled. But because of their potential interesting points, we decided to post them with the corresponding note.
HPC, simulations and visualisation
Solving a rendering equation using the Monte Carlo Method
Authors: Severyn Shykula, Petro Prokopets, Mykola Vysotskyi, Nazar Tkhir, Mykhailo Moroz
Published: 1 September 2024. Performed in AKS-2024.
Abstract: Solving a rendering equation using the Monte Carlo method is a computational approach in computer graphics to simulate the complex process of light transport within a scene. The rendering equation describes the distribution of light in a three-dimensional environment. It accounts for how light interacts with surfaces, materials, and the surrounding medium, making it a fundamental equation in computer graphics for realistic image synthesis. The Monte Carlo method, in this context, involves using random sampling techniques to approximate the solution to the rendering equation. Instead of trying to solve the equation analytically, which can be extremely challenging due to its complexity, Monte Carlo methods rely on statistical sampling to estimate the integral of the rendering equation.
Cross-platform Renderer for Volumetric Bodies with Vulkan API
Authors: Roman Naumenko
Published: 1 September 2024. Performed in OS-2023.
Abstract: This project demonstrates the implementation of a cross-platform rendering engine, leveraging the Vulkan API’s capabilities to render volumetric bodies efficiently. Building upon a foundational understanding of OpenGL, it explores Vulkan’s functionality as a modern, efficient, and low-overhead graphics API. The robust application developed not only serves as a scene renderer but also supports a graphical user interface, showcasing Vulkan’s versatility in complex rendering tasks. Utilizing raw Vulkan API for rendering and GLFW for window creation and OS interaction on both Windows and Linux, the project underscores Vulkan’s comparative advantages over traditional APIs like OpenGL and highlights the developmental journey and learning curve associated with it.
To achieve high-fidelity images when rendering volumetric objects like clouds, smoke, and fog, the method of ray marching was employed. This particular method is often utilized in modern game engines for the same purpose, as it not only can produce visuals indistinguishable from reality but also possesses significant potential for optimization and parallelization. This allows it to operate efficiently on GPUs and be executed exclusively in the fragment shader.
Concurrent Real-Time Raytracer 2
Authors: Serhii Ivanov, Sviatoslav Lushnei, Oleh Omelchuk, Ivan-Vitalii Petrychko
Published: 1 September 2024. Performed in AKS-2023.
Abstract: The Real-Time Raytracer Project aims to create a high-performance, interactive rendering system capable of generating realistic and immersive graphics in real time. This project report outlines the key objectives, methodologies, and outcomes of our endeavor to develop a state-of-the-art raytracer capable of rendering complex scenes with accurate lighting, shadows, reflections, and refractions.
GUI Toolkit for Wayland
Authors: Oleh Omelchuk, Sviatoslav Lushnei
Published: 1 September 2024. Performed in OS-2023.
Abstract: This document is a report on our implemented GUI Toolkit for Wayland as a part of the academic project in the Operating Sytems Fall-2023 Course at CS Program. It will describe the main features of our toolkit, the way it works, and the way it was implemented. Also, we will overview of the Wayland protocol and Cairo library, which were used in our project.
Hardware
CCTV Camera Software Customization for Precise Frame Capture Time Retrieval
Authors: Serhii Matsyshyn, Oleksii Mytnyk, Tymur Krasnianskyi
Published: 1 September 2024. Performed in OS-2023.
Abstract: We present a series of steps that allow for the injection of high-precision timestamps. Most CCTV cameras do not provide an absolute timestamp of the frame, which is crucial in solving real-time computer vision tasks. A common approach for timestamp estimation is to subtract the average delay from the frame retrieval time on the client’s side. However, the delay accumulates from many stages of image processing and varies substantially. Whereas our approach is to inject timestamps into the video stream on the camera’s side. Our customized software provides highly accurate results: the standard deviation of the difference between predicted and actual frame capture time is 10ms. Furthermore, video stream delay decreased from 200ms to 115ms on average.
The effect of power quality on photos taken by the camera module. Software image enhancement affected by noisy power supply
Authors: Mykhailo Buleshnyi, Maksym Buleshnyi, Anna Yaremko, Iryna Kokhan, Denys Levchunets
Published: 1 September 2024. Performed in POC-2023.
Abstract: The objective of this project is to explore both hardware and software methodologies for enhancing image quality. Specifically, the focus of this report will be on the hardware aspect related to power supply. The investigation aims to understand the impact of a camera operating with a noisy power supply and seeks to implement software-based solutions to improve the overall image quality. For this project, we used a Raspberry Pi image sensor.
System programming
Building and Measuring the Efficiency of a Distributed Parallel Web Crawler
Authors: Teodor Muzychuk, Roman Mutel, Bohdan Ruban, Mykhailo Bondarenko
Published: 1 September 2024. Performed in AKS-2023.
Abstract: World Wide Web is one of the biggest sources of data in the modern world. Due to its size, in the last 30 years, there exists a challenge to effectively traverse and index the web pages it contains. Google Search is one of the well-known leaders in the industry because of its complex experience in the topic and huge computational power. However, less advanced systems are also worth the attention of developers and researchers. In this paper, we present our solution to the task of web crawling, describe the existing tradeoffs and problems we encountered, and analyze the efficiency of the parallel distributed system we developed.
MYDOCKER: Implementation of Containerization Using Linux Kernel Features
Authors: Ostap Seryvko, Sofiia Folvarochna, Olesia Omelchuk, Anastasiia Beheni, Hermann Yavorskyi
Published: 1 September 2024. Performed in OS-2023.
Abstract: This project demonstrates the implementation of the Docker analogue using Linux kernel features.
Computer engineering for the AI/ML
Parallel genetic algorithms library
Authors: Dmytro Shumskyi, Marta Samoilenko, Victor-Mykola Muryn, Yurii Sahaidak, Roman Milischuk
Published: 1 September 2024. Performed in AKS-2024.
Abstract: There are plenty of NP-complete algorithms, which require a lot of time to be solved. The genetic algorithms allow us to reach great results with significantly lower complexity. The project’s main topic is the development of different techniques for genetic algorithms and comparing them with each other. The Traveling Salesman Problem (later TSP) is an NP-hard problem. The most popular exact algorithm - Held-Karp algorithm has complexity $O(n^22^n)$.
Ant colony optimization algorithms
Authors: Viktoria Kocherkevych, Yaroslav Klym
Published: 1 September 2024. Performed in AKS-2023.
Abstract: This is a project for an Architecture of Computer Systems course, and the main topic of this project is to introduce ant colony optimization (ACO) algorithms. The project report starts with an introduction, then we describe the first problem we solved using the Ant System (AS) while showing sufficient results of experiments. Then we introduce the second problem, discuss solutions and show results.