Browsing by Author "Sundararajah, Kirshanthan"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Orchard: Heterogeneous Parallelism and Fine-grained Fusion for Complex Tree Traversals
    Singhal, Vidush; Sakka, Laith; Sundararajah, Kirshanthan; Newton, Ryan; Kulkarni, Milind (ACM, 2024)
    Many applications are designed to perform traversals on tree-like data structures. Fusing and parallelizing these traversals enhance the performance of applications. Fusing multiple traversals improves the locality of the application. The runtime of an application can be significantly reduced by extracting parallelism and utilizing multi-threading. Prior frameworks have tried to fuse and parallelize tree traversals using coarse-grained approaches, leading to missed fine-grained opportunities for improving performance. Other frameworks have successfully supported fine-grained fusion on heterogeneous tree types but fall short regarding parallelization. We introduce a new framework Orchard built on top of Grafter. Orchard’s novelty lies in allowing the programmer to transform tree traversal applications by automatically applying fine-grained fusion and extract- ing heterogeneous parallelism.Orchard allows the programmer to write general tree traversal applications in a simple and elegant embedded Domain-Specific Language (eDSL). We show that the combination of fine-grained fusion and heterogeneous parallelism performs better than each alone when the conditions are met.
  • Thumbnail Image
    SparseAuto: An Auto-scheduler for Sparse Tensor Computations using Recursive Loop Nest Restructuring
    Dias, Adhitha; Anderson, Logan; Sundararajah, Kirshanthan; Pelenitsyn, Artem; Kulkarni, Milind (ACM, 2024-10-08)
    Automated code generation and performance enhancements for sparse tensor algebra have become essential in many real-world applications, such as quantum computing, physical simulations, computational chemistry, and machine learning. General sparse tensor algebra compilers are not always versatile enough to generate asymptotically optimal code for sparse tensor contractions. This paper shows how to generate asymptotically better schedules for complex sparse tensor expressions using kernel fission and fusion. We present generalized loop restructuring transformations to reduce asymptotic time complexity and memory footprint. Furthermore, we present an auto-scheduler that uses a partially ordered set (poset)-based cost model that uses both time and auxiliary memory complexities to prune the search space of schedules. In addition, we highlight the use of Satisfiability Module Theory (SMT) solvers in sparse auto-schedulers to approximate the Pareto frontier of better schedules to the smallest number of possible schedules, with user-defined constraints available at compile-time. Finally, we show that our auto-scheduler can select better-performing schedules and generate code for them. Our results show that the auto-scheduler provided schedules achieve orders-of-magnitude speedup compared to the code generated by the Tensor Algebra Compiler (TACO) for several computations on different real-world tensors.
  • Thumbnail Image
    μJUNITER: Automated Unification of Microservices into Modular Monoliths for Versatile Software Architecture Migration
    Martin, Joshua Scott (Virginia Tech, 2024-12-19)
    Although software architecture aims for long-term stability, architectural migrations may be necessary to adapt to evolving business needs and resource availability. In recent years, numerous migrations have occurred within backend architectures. While many of these migrations partition monoliths into microservices, several prominent enterprises have reported having to unite microservices into monoliths to reduce management and communication overheads. The required unification is typically manual, substantial, tedious, and error-prone for complex systems. This thesis presents a novel automated architectural refactoring that transforms a microservice system into a functionally equivalent monolith. Our refactoring relies on abstract syntax tree merging and control flow bridging to unite distributed components into a centralized system. We have implemented our approach as μJUNITER, an automated refactoring tool that operates on Java source files of Spring Boot microservices, producing Spring Boot modular monoliths. Evaluations conducted with third-party and synthetically generated microservice applications, with up to 100 microservices, demonstrate that μJUNITER's refactoring preserves the original system's functionality, as verified by end-to-end and back-end unit testing. The refactoring also reduced latency in certain cases and resource consumption in all cases. μJUNITER's refactoring saves manual programming effort proportional to the number of microservices and their level of inter-service interaction. As software architectures must adapt to changing trends, our approach can complement and enhance the existing automated toolset for architectural migration.