http://hdl.handle.net/123456789/14 http://hdl.handle.net/123456789/5792 PREBROJAVANJE KLASA EKVIVALENCIJE BULOVIH FUNKCIJA Carić, Marko In this dissertation, the problem of calculating the number of equiva- lence classes of Boolean functions is discussed. The difficulty of determining the number of equivalence classes increases sharply with the number of variables n. The motivation for choosing this topic lies in the fact that concrete numbers have been known so far only for relatively small values of n, although the problem itself was theoretically solved a long time ago. Let G be the group of permutations of the set Bn = {0, 1}n. The effect of the group G on scalar, Bn 7 → B1, that is, vectorial invertible Boolean functions, Bn 7 → Bn. Two scalar Boolean functions f (x) and g(x), defined on Bn, are considered equivalent with respect to the group G, i.e. f ∼ g, if for some σ ∈ G for every x ∈ Bn f (x) = g(σ(x)) holds. Two vector invertible Boolean functions f (x) and g(x), are considered equivalent with respect to the group G, i.e. f ∼ g, if for some pair (σ, ρ) ∈ G × G for each x ∈ Bn holds g(x) = ρ(f (σ(x))). The equivalence relation ∼ decomposes the set of all Boolean functions into equivalence classes. Equivalence of Boolean functions has significant applications in the logical synthesis of combinatorial circuits and in cryptography, especially in connection with the design of S-boxes. Let Un(G) and Vn(G) denote number of equivalence classes of scalar, i.e. vector invertible Boolean functions of n variables in relation to the group G. The numbers Un(G) and Vn(G) can be calculated relatively simply if the cycle index of the group G is known. The dissertation considers four groups G of permutations of the set Bn: • group S′ n induced by group Sn permutations of coordinates elements x = (x1, x2, . . . , xn) ∈ Bn, • group Gn, induced by permutations and complementations of coordinates, • group of GLn linear invertible transformations elements of the vector space Bn, i • group of AGLn affine invertible transformations elements Bn. If the permutation σ ∈ G has ik cycles of length k ⩾ 1, its cycle structure is i(σ) = (i1, i2, . . .). The cyclic index of the group G is the generatrix ZG(f1, f2, . . .) = 1 |G| X σ∈G Y k⩾1 f ik k of cycle structures of all permutations σ ∈ G. General expressions for cycle indices the four considered groups are known, but the cycle indices themselves, i.e. the numbers Un(G) and Vn(G), are practically calculated only for relatively small values, for e.g. n ⩽ 10. The dissertation presents original results in the field of enumeration of equiv- alence classes of Boolean functions in relation to these four groups of transfor- mations. A similar expression was derived for all four groups of transformations for the cycle index in the form of sum over partitions of the number n. Based on that expression and previously calculated tables, the cycle index is calculated much more efficiently. An overview of known results for relatively small n and new results in the thesis for larger n is shown in the following table: Number\ G S′ n Gn GLn AGLn Un(G) 11 → 33 10 → 32 8 → 31 10 → 31 Vn(G) 6 → 30 7 → 27 6 → 26 6 → 26 Specially, in the case of the permutation group S′ n, an effective direct procedure for calculating the number of equivalence classes that does not use a cycle index is shown, and is described in the third paper from the introductory chapter. The second part of the dissertation concerns monotone Boolean functions — scalar Boolean functions which satisfy the monotonicity condition (from x ⩽ y follows f (x) ⩽ f (y)). Let rn, i.e. dn (the n-th Dedekind number), denote the number of equivalence classes of monotone Boolean functions in relation to the group S′ n, that is, the total number of monotone Boolean functions of n variables. The difficulty of calculating the number rn increases rapidly with n, so that until recently the last calculated member of the sequence was r7. The procedure described in the dissertation is based on the Frobenius theorem, by which it was determined number r8. In doing so, the known value of the number d8 is used. The dissertation consists of the first - introductory chapter and the following three chapters. In the second chapter, theoretical terms related to the material from chapters 3 and 4 are introduced, and they refer to discrete mathematics, combinatorics and cycle indices of the considered four groups of transformations. Chapter 3 describes the procedure for calculating the cycle indices for the four considered groups of permutations, as well as numbers Un(G) and Vn(G) equivalence classes of Boolean functions in relation to these groups. First, common improvements for all four groups are considered, and then specific accelerations related to individual groups. These results are published in the second paper listed in the introductory chapter. In chapter 4, the problem of finding the number of equivalence classes of monotone Boolean functions is solved. First, a general expression for calculating the number rn is given based on the Frobenius theorem in the form of the sum (by partitions of the number n) of the number of fixed points of the permutation corresponding to the partition. After that, depending on the graphs corresponding to different partitions, different ways of calculating the number of fixed points for n ⩽ 8 are shown. The procedure based on which the number r8 was calculated, which also represents the original contribution of this dissertation is presented - see the first paper from the list from the introductory chapter. Applying a similar procedure, Pawelski [31] calculated r8 practically at the same time as the obtained result described in the dissertation. http://hdl.handle.net/123456789/5786 DIRECT DATA-SNAPSHOTTING AND SNAPSHOT SHARING ACROSS CLOUD-NATIVE APPLICATIONS Ristović, Ivan Cloud-computing platforms provide services to consumers through multiple serviceoffering models. Recent advances in these models have led to the emergence of serverless computing, or simply serverless, where infrastructure is managed by the service provider. Serverless is usually coupled with function-based programming model in which software systems are composed of reusable, lightweight units of code executed within isolated sandboxed environments. Major cloud-computing platforms, including Amazon Web Services (AWS), Microsoft Azure, and Google Cloud, report that a substantial proportion of their customers employ serverless solutions. Most cloud-computing providers employ a pay-as-you-go billing model. Inefficient utilization of computing resources, particularly CPU time and working memory, which constitute the most costly resources, leads to increased overall operational costs. Moreover, the requirement for resource isolation adversely affects initialization latency and results in additional CPU and working-memory overhead. Serverless sandboxes are typically deployed on top of heavyweight virtualization stacks that includeJava, JavaScript, or Python runtime environments with accompanying frameworks, further increasing working-memory consumption. Modern cloud-computing architectures use Checkpoint/Restore (abbr. c/r) techniques to freeze initialized sandboxes into a continuable form. Such techniques, in combination with cloud-native deployments, allow the virtualized environment to optimize resource consumption and share code and pre-initialized data across multiple sandboxes. However, such solutions either operate at application-build time to support data pre-initialization or sharing, or operate at execution time with limited sharing potential for data available during application execution. Such data is processed multiple times and duplicated in each sandbox. This dissertation presents Doss, a direct object snapshotting and sharing system that performs data c/r during application execution. Doss persists data directly, without transformations, into reusable and shareable snapshots. Direct snapshotting allows Doss to achieve near-constant data deserialization time, greatly improving initialization times and reducing CPU usage. Doss architecture enables snapshot sharing across application instances, eliminating the excess memory footprint associated with data re-processing and duplication. GraalDoss, a Doss implementation for Java, is integrated into the GraalVM ecosystem. GraalDoss is evaluated using 106 correctness and robustness tests and a novel set of cloudnative micro and macro benchmarks that exercise real-world scenarios. A comprehensive evaluation of GraalDoss shows a consistent near-constant data-deserialization overhead with serialization times comparable to state-of-the-art Java JSON and binary serialization libraries. GraalDoss reduces the memory footprint of web API microservice caches by sharing populated cache snapshots across microservice instances, improving the overall density by 41% for 8 microservice instances and improving first-response times by 34%. In NLP applications, GraalDoss improves the pipeline execution times by six orders of magnitude by snapshotting pipeline results and subsequently loading the snapshots. http://hdl.handle.net/123456789/5782 Metode za efikasno rešavanje dominacijskih problema na velikim grafovima Kapunac, Stefan This dissertation addresses methods for efficiently solving several important variants of domination problems on graphs, with a particular focus on large-scale instances that frequ- ently appear in real-world systems. Domination problems have numerous applications in the analysis and management of complex networks, including social, telecommunication, transport, and biological networks. The study covers four problems: minimum weight total domination, minimum weight independent domination, k-strong Roman domination, and the canonical mi- nimum domination problem on large graphs. For the minimum weight total domination problem, a variable neighborhood search approach is proposed, with carefully designed mechanisms for shaking, local search, and fitness function evaluation. The results show that the proposed algorithm achieves optimal solutions on small and medium instances and outperforms competing approaches on large graphs. Additionally, an application of this problem for accelerating information spreading in social networks is proposed. For the minimum weight independent domination problem, two new integer linear pro- gramming models are developed. Solving these models finds optimal solutions for all smaller instances while demonstrating superior performance compared to competing exact approaches on larger graphs. In addition, a greedy heuristic is proposed that outperforms competing greedy methods on most instances. In the case of k-strong Roman domination, a greedy heuristic based on node coverage information is developed, along with a metaheuristic approach based on variable neighborhood search that uses the greedy algorithm for initialization. This problem is particularly challenging due to the exponential complexity of solution feasibility verification, leading to the introduction of the concept of quasi-feasibility that enables efficient feasibility assessment during the search. Experimental results show that the proposed algorithm consistently outperforms the greedy approach and existing competing methods, especially on larger graphs. The practical value of the algorithm is illustrated through a case study involving the optimal positioning of fire stations and vehicles in urban municipalities to ensure the entire city is safe in the event of k simultaneous fires. For the minimum domination problem, a new hybrid approach called IRIS is proposed. IRIS is designed as a general-purpose framework that bridges the gap between exact integer linear programming solvers and heuristic search by iteratively fixing selected variables to reduce the search space. Тhe novelty lies in its flexible subproblem construction mechanism, which can be tailored using various selection strategies. In this study, we implement and evaluate a specific configuration of IRIS that utilizes historical statistical data and a node-coverage-based heuristic to intelligently identify variables for fixing. This targeted approach allows the ILP solver to find high-quality solutions for large-scale instances that are computationally prohibitive for exact methods. Experimental results demonstrate that IRIS achieves competitive performance com- pared to the best existing methods, establishing it as a valid alternative for solving domination and potentially other NP-hard problems. http://hdl.handle.net/123456789/5778 PREDVIĐANJE PROFILA IZVRŠAVANJA PROGRAMA TEHNIKAMA MAŠINSKOG U ČENJA Čugurović, Milan Compilers use program profiles to perform profile-guided optimizations and pro- duce efficient programs. Although dynamic profilers generate high-quality profiles, they have significant drawbacks. They complicate the application build pipeline by requiring two compi- lation steps and an additional profile collection run. Dynamic profilers also consume substantial time and memory and place a heavy burden on developers to create suitable workloads that accurately reflect typical application usage, cover important code paths, and generate well- distributed profiles. In response to the shortcomings of dynamic profilers, modern static profilers employ ma- chine learning (ML) techniques to predict program profiles. However, state-of-the-art ML-based static profilers often rely on handcrafted features that are platform-specific and difficult to adapt across different architectures and programming languages. They also tend to use computation- ally intensive deep neural networks, which increase application compilation time. Moreover, ML-based static profilers can degrade the performance of optimized programs due to inaccurate profile predictions. This dissertation presents GraalSP , an ML-based static profiler that is portable, polyglot, efficient, and robust. GraalSP achieves portability by defining features on a high-level, graph- based intermediate representation and by partially automating the feature extraction process. This design makes GraalSP polyglot, allowing it to predict profiles for programs written in any language that compiles to Java bytecode, such as Java, Scala, or Kotlin. GraalSP is efficient due to its use of a lightweight XGBoost model based on decision trees, and robust because it relies on carefully designed heuristics that correct machine learning predictions and ensure high performance in programs optimized using the predicted profiles. We integrate GraalSP into the Enterprise GraalVM Native Image compiler and evaluate it on 28 benchmarks from the Renaissance, DaCapo, and DaCapo Scala benchmark suites. These suites represent a modern and diverse collection of benchmarks, featuring numerous real-world workloads across a variety of programming paradigms. Our comprehensive evaluation shows that GraalSP achieves a geometric mean speedup of 7.46% in execution time compared to the default compiler configuration, which models program profiles using a uniform distribution. This dissertation also presents a detailed qualitative and quantitative analysis to position and compare the proposed solution against state-of-the-art static profilers. Additionally, to enhance and expand the evaluation and support developers in analyzing GraalSP ’s predictions, this dissertation introduces the GraalSP-PLog tool. This tool allows developers to run the GraalSP static profiler on any program and generate detailed prediction reports, making it easier to inspect individual predictions and identify model mispredictions. Since GraalSP provides substantial performance gains, has minimal impact on binary size and compile time, and includes a modern, fully automated model retraining pipeline, it is well- suited for commercial deployment. As a result, GraalSP has been the default static profiler for the Enterprise GraalVM Native Image compiler since June 2023, consistently improving performance with every build.